Chapter 1: Introduction
This project focuses on the use of traffic simulation in helping traffic engineers reduce congestion, in particular by use of high occupancy vehicle (HOV) lanes. Traffic congestion is a major problem, and with the volume of traffic increasing at a steady rate, it is set to get worse. There are many schemes for reducing congestion; one is the use of HOV lanes, which are now being introduced on congested roads in the UK and are used often in the USA. Traffic simulation can help to determine the likely effects of introducing various schemes without costly infrastructure changes.
Traffic simulation can be implemented using agent-based modelling (ABM), which enables dynamic objects such as vehicles to be modelled individually and have control over their behaviour. NetLogo is chosen as the ABM environment to be used in the project, and is used to develop a traffic simulator, which is then calibrated and verified with data from traffic research. The simulator is used to model part of a local road network with and without a HOV lane, and results are compared to claims of success from the local council.
The purpose of the project is to show that traffic simulation is a worthy tool for traffic engineers evaluating alternative schemes. It aims to develop a unique traffic simulation system that can be used to study traffic theory and assess network infrastructure and control changes. Main objectives include gaining an understanding of traffic theory, learning the major features and issues of traffic simulation, and evaluating agent-based modelling as a means of simulating traffic.
This report is structured as follows: Chapter 2 examines the problem of traffic congestion, various schemes for reducing congestion, and traffic flow theory. Chapter 3 looks in detail at the design features of traffic simulation systems, and Chapter 4 introduces agent-based modelling along with its application to traffic. Chapter 5 follows the design of the traffic simulator, and Chapter 6 follows its implementation in prototypical stages with details of results from testing on the problem. Project conclusions are presented in Chapter 7.
Chapter 2: Traffic Design & Analysis
2.1 Traffic Congestion
Traffic congestion has been a major problem on roads around the world for many years. Roman history indicates that in the first century, the streets of Rome became so congested that all non-official vehicles were banned from entering the city [39]. In modern cities, traffic on major roads is abundant, and steps have to be taken to keep the traffic flowing at an acceptable speed.
The volume of road traffic has increased rapidly in recent years. In the UK, total road traffic has almost doubled since 1980 (see Figure 2.1). Forecasts from the Department for Transport show that the volume of road traffic will continue to increase at an alarming rate. These forecasts, which in the past have been conservative estimates, suggest that traffic levels will increase by approximately 50% between the years 2000 and 2020 [43]. If this is the case, then the causes and effects of traffic congestion need to be understood now or it is could become much worse a problem in the near future.
Figure 2.1: Estimated UK Road Traffic Volume. Source: [55]
At its most basic, congestion is caused when the volume of traffic exceeds road capacity. This holds for most perceived causes of congestion; for example, accidents, breakdowns and road works decrease the available road capacity, while school-run and holiday traffic increase the volume of traffic [50]. The Government has set targets for reducing congestion in its “10 Year Plan for Transport” [51]. This plan was published in the year 2000, and it outlines the Government’s goal of improving transport by the year 2010. In the plan, a simple definition of congestion has been adopted, which makes it quantifiable:
Congestion in this Plan is defined as the average delay experienced for each kilometre travelled compared to driving at speeds typical when traffic is light.
[51]
Using this definition, the Department for Transport has attempted to measure and forecast congestion levels by conducting studies on the existing road network. Without the effects of the plan, congestion was predicted to rise by 15% across the whole road network. The Government deemed this an unacceptable rise, and the plan sets the target to reduce congestion below current levels by 2010, particularly in large urban areas. Various strategies are outlined in the plan to help improve congestion; these are detailed in section 2.2. Critics argue that so far, congestion has risen since the start of the plan; however, the Government’s response was that this is expected because congestion trends take time to reverse. [51], [52]
Traffic congestion is a major issue for many drivers; it results in journey delays, wasted time, increased pressure and can make people late or cause loss of business [50]. Congestion also adversely affects passengers, pedestrians, cyclists, and users of buses and taxis, causing more delay, stress and even danger. The environment and local residents may be affected by emissions or noise pollution associated to vehicles. Congestion reduces the quality of life for many people and deserves to be tackled to improve transport for everyone. [39]
2.2 Tackling Traffic Congestion
Many schemes have been designed and implemented with relieving congestion as a primary objective. These schemes have varying effectiveness, and it is not always obvious which measures will work best in a given situation. The most common methods are considered in section 2.2.1, with an indication of their effectiveness. A new scheme receiving a good deal of attention at present is the introduction of high occupancy vehicle lanes; this is discussed in section 2.2.2.
2.2.1 Existing Schemes
The immediately obvious strategy is to increase road capacity by building new roads or improving existing roads, but this rarely works to reduce long-term congestion. Congestion is self-managing, because traffic is governed by what is regarded as a tolerable level of congestion; as road capacity increases, demand (traffic) increases to fill the new capacity. This concept is known as Braess’ Paradox or Pigou-Knight analysis, and suggests that increasing the network capacity can often be not only ineffective, but also counterproductive. This is also one of the most expensive ways of tackling congestion. [37], [25]
Improving public transport is an accepted way to improve overall transport in busy congested areas such as town centres. This covers bus lanes, improving other modes of transport and increasing awareness of the benefits of walking and cycling. It is one of the aims of the Government’s plan for transport, and it is thought that if people feel there are real alternatives to driving, then travelling will be easier for everyone. [39], [51].
An attractive remedial measure for reducing congestion is Intelligent Transport Systems (ITS), which is concerned with the application of electronic information systems to control, manage and improve transport. This includes real-time route guidance systems, variable speed limits controlled by computer systems, real-time transport information (e.g. congestion levels, delay expected for public transport, variable message signs), and dynamic signal timings. [36], [43]. ITS makes possible many new traffic management opportunities, which help to reduce congestion by making the best use of the existing transport network. [8]
Congestion charging, a form of road pricing implemented in London, is a way of reducing demand (traffic) by forcing drivers to pay a fee when driving through a congested area such as a city centre. This form of restraint is designed to encourage drivers to use other forms of transport when travelling in an extremely congested area, and is very effective at reducing or eliminating congestion as well as increasing air quality and road safety, more predictable travel, and possibly profits. However, drivers often see it as an unfair money making scheme, congestion can be increased around the edge of the charging zone as drivers avoid it, more costs for businesses travelling within the zone, and reduced profits for businesses just inside the zone. [51], [53]
2.2.2 High Occupancy Vehicle Lanes
One attempt to improve efficiency of congested roads is to implement one or more high occupancy vehicle (HOV) lanes. These lanes are only to be used by vehicles carrying more than a certain number of passengers. Similar to bus lanes, they can be used by buses, taxis, but also by any other vehicle making efficient use of the road by carrying more passengers. HOV lanes are intended to promote the use of public transport and car sharing (car pools), to ease congestion by reducing the number of cars on the road, and to improve efficiency by increasing the throughput of vehicles carrying more people. [54]
HOV lanes appear to be a state-of-the-art technique for tackling traffic congestion in the United Kingdom. Only a few schemes have been implemented to date, and have involved dual carriageways in Leeds and South Gloucestershire. However, there are now proposals in place to convert one lane on motorways into a HOV lane during peak periods, on sections of the M1, M3, M61 and M62. There is a fair amount of controversy on HOV lanes, as many drivers only perceive larger amounts of congestion because of them, especially for single occupant vehicles. The USA has been at the forefront of using HOV lanes, and has common standards are in place for their planning and design. The majority of schemes involve restricting use of the HOV lane to vehicles with two or more occupants. [54]
The measure used to evaluate the performance of HOV lanes is the average vehicle occupancy (AVO) of a road. In the USA, the primary objective is to increase the AVO, regardless of resulting traffic flows. It is generally accepted that the introduction of a HOV lane will increase the AVO by 10-15%, however the resulting volume of vehicles is not so readily available. Depending on local conditions, the introduction of a HOV lane is expected to reduce the number of vehicles by approximately 10% through increased occupancy and some vehicles taking different routes. [54]
2.2.3 Local Traffic Study
In South Gloucestershire, traffic and congestion have increased significantly more than the national or county average, especially in the northern fringe of the Bristol area, due to the location of the area along the M4/M5/M32 corridors [49]. The University of the West of England is located along this north fringe, supporting over 2,000 staff and 16,000 students. The following map shows the location of the UWE campus in relation to the motorways and the Avon Ring Road/Coldharbour Lane HOV lanes (shown in green).
Figure 2.2: UWE Local Traffic Area. Source: [44]
In 1998, HOV lanes were introduced on the Avon Ring Road for use by cars and vans with two people or more, buses, coaches, motorcycles and emergency vehicles. South Gloucestershire Council considered the options, and found that HOV lanes were the best value for money improvement available to decrease congestion. The aim of the project is to give an advantage to car sharers and bus users, i.e. decreased journey times. An online car-sharing database was also setup to allow drivers to find a car-sharing partner.
The Council claims that the HOV lanes have increased traffic flows by over 1000 vehicles (+36%) in the three-hour morning peak period and decreased journey times for all vehicles by 10 minutes. These statistics are surprising because one would suppose that the journey time for single-occupant vehicles would rise, and it is expected that the number of vehicles decrease by 10%. Compliance with the new rules has been measured at around 90%, and the AVO (average vehicle occupancy) has increased by approximately 7%. This is slightly lower than the expected increase of 10-15% but reasonable nonetheless. The data received from the Council can be seen in appendix A-1. This data can later be used to calibrate and test the traffic simulation system for use with HOV lanes.
2.3 Traffic Theory
2.3.1 Measuring Traffic Flow
The study of how traffic flows is essential to the design of better road networks. If traffic flow could be completely understood, then traffic levels could be predicted and congestion could be forecasted and avoided. In order to understand this phenomenon, we need to start by looking at what already happens on the roads. Traffic surveys are used to provide measurements of the current situation, and involve counting the number of vehicles going past a point in a certain amount of time. They can be undertaken manually or can be automated using an inductive loop or pressure tube counter. The standard flow/capacity of the average road at optimal conditions is generally accepted to be 2,000 vehicles per hour, per lane. [43]
However, simply knowing the flow rate is not too useful because, for example, 10 vehicles could pass a counter in one minute spaced-out at 60mph or nose-to-tail in a jam. The traffic density describes the number of vehicles in a certain amount of road, and requires the vehicle speed in addition to flow rate for calculation. Density is usually measured in vehicles per km, per lane. The optimal density on a standard road should be around 40 vehicles per km, per lane. At this density, the flow rate should be at maximum, i.e. 2,000 vehicles per hour, per lane. [6]
This method allows one to learn about the traffic flow through a junction or small number of roads, but to gain an overall picture of traffic more is required. Individual trips can be represented as an origin-destination (O-D) matrix, which allows one to represent the number of trips to and from any two destinations. The O-D matrix is an n * n array, where n is the number of origins or destinations considered. [43]. More detailed data can be gathered by examining the daily activities of individuals, however this is outside the scope of the project. [28]
2.3.2 Modelling Traffic Flow
Physicists have been trying to describe the phenomena of traffic for at least half a century. In the 1950s, James Lighthill, an expert on the physics of fluid flow, suggested that the flow of traffic on a road was akin to the flow of liquid in a pipe. This theory (the Lighthill-Whitham-Richards model) represented the flow of traffic entirely with mathematical equations, and ignored the individual drivers. This sort of model is called macroscopic, and can often produce realistic output, but lacks the complexity to model realistic driver behaviours. [6]
The next approach was to treat vehicles as individual units instead of a continuous flow, and see what behaviour emerges when the vehicles are given simple rules to follow. Each vehicle would move according to the vehicle ahead, speeding up or slowing down to match its speed while maintaining a safe distance between cars. This is a type of microscopic model, which can vary in complexity depending on the aims of the simulation. One well-known model is a cellular automata model designed by Nagel and Schreckenberg. It was very simplistic and followed mainly the rules above, yet exhibits complex phenomena found in real traffic, as described below. [6], [27]
The results from these models and from traffic studies show that flow rate and traffic density are linked in an interesting way. Normally, flow rate increases as density increases, that is, more vehicles are on the road without any having to slow down. However, when the density reaches a so-called ‘critical density’, the flow rate begins to decrease and the traffic becomes congested. An interesting observation is a hysteresis[1] effect that as the density increases above the critical density it is possible for the flow to continue to increase in a metastable or bi-stable state. In this state, any hiccup in the flow can cause the traffic to become congested. [6], [28]
Figure 2.3: Stylised traffic flow-density diagram. Source: [28]
Figure 2.3 shows this fundamental relationship between flow and density. Point A represents the critical density as described above. As the traffic gets denser past this point, either it breaks down into a congested state towards point D, or it continues to flow in a bi-stable state until point B, where some anomaly causes it to become congested. It is worth noting that once the flow has moved to the unstable state, it cannot return to the bi-stable or free-flow state until the density is lower than the critical density (A). That is, the hysteresis effect happens in one direction only, as the density increases. These conditions are also observed in solids, liquids and gases during phase transitions. This effect can be achieved in cellular models by implementing a ‘slow-to-start’ rule. This is done by making traffic accelerate slower out of stopped traffic than at any other time. [28]
An effect of all this modelling is a better understanding of why traffic jams tend to form with no apparent cause. When the density exceeds the critical density, at any point a fluctuation can cause start-stop traffic. Traffic jams of this form (with no bottleneck cause) move upstream through the traffic, which is easily observed on a graph of space-time showing the position of each vehicle in time (see Figure 2.4). Until the density decreases, the traffic jam will live on, often get worse and sometimes split into multiple regions of stop-start traffic. [6]
Figure 2.4: Space-time diagram where lines represent vehicles,
observed using aerial photography. Source: [27]
Therefore, we can model a traffic jam on a motorway with the free flow, metastable and congested state transition, however real traffic exhibits more behaviours than these states provide. Kerner and Rehborn proposed that there are two different states of congested traffic: one is the traffic jam where no one moves (point D on Figure 2.3) and the other being a ‘synchronised’ state. This state is possible if the speed of all the traffic is more or less the same, and no vehicles stop completely. In this state, high-density traffic can maintain a reasonably high flow rate without breaking down into stop-start traffic (see Figure 2.5). This state can be reached from either the free-flow or metastable states discussed above. Synchronised traffic can be modelled by incorporating a ‘comfort factor’ where drivers aim to drive smoothly with less hard acceleration or deceleration. Researchers still debate the conditions that lead to synchronised traffic; it often occurs at road features such as entry and exit ramps, but sometimes occurs out of nowhere in normal conditions. [6]
Figure 2.5: Flow-density diagram incorporating synchronised flow. Source: [33]
2.3.3 Understanding Drivers
Drivers are difficult to analyse because they are human and therefore unpredictable and individual. In general, drivers are not aware of the global state of the traffic system, and they only perceive local conditions. Drivers are also emotionally complex, and can change their behaviour for no apparent reason. One problem with many schemes is that they rely on drivers heeding the advice given to them. For example, on the M25 motorway, variable message signs are used to alter the speed limits of the carriageways to optimise traffic flow. Without penalties such as speed cameras, many drivers would simply ignore these limits and decide that they know better. Drivers cannot always be expected to do what seems rational, but for the purposes of this project, it will be assumed that they regard safety with utmost importance, and otherwise try to maximise the utility of their situation through their driving decisions.
Chapter 3: Traffic Simulation
3.1 Introduction to Traffic Simulation
Champion et. al [10] describe simulation as an effective tool used for reproducing and analysing a broad variety of complex problems, difficult to study by other means that might be too expensive or dangerous. Traffic can be viewed as a complex system [Faieta et. al., Sanford in [17]], therefore simulation is a suitable tool to analyse traffic systems. Traffic simulation is the state-of-the-art method used to assess and evaluate transport schemes for reducing congestion [13]. Rather than implementing a scheme without knowing whether the outcome will be a success, the scheme can be implemented in a simulation to determine its effectiveness:
Infrastructure improvements are very costly and each modification must be carefully evaluated for its impact on the traffic flow. Computer traffic simulations form a cost effective method for making those evaluations.
[16]
A study by Leeds University found that the users of traffic simulators include research organisations (including simulator developers), road authorities, consultants and manufacturers. The most frequent applications of traffic simulation are for design and testing of control strategies and evaluation of large schemes. Other applications include on-line traffic management, evaluating product performance, research and education. The majority of these users regard simulation as a necessary or useful tool for the applications listed above. [1]
The APAS assessment of road transport models and system architectures identified four major uses of traffic simulation: simulating networks including interactions between vehicles and new responsive control and information systems, short term forecasting, enhancing assignment models and providing inputs to car driving simulators [5]. The scenarios simulated most often are corridors (areas containing main transport lines) and intersections, followed by city and single-road simulation. Most users utilize simulation to investigate the present situation or the near future (1-5 years ahead) and a few users are interested in longer-term planning. [1]
3.2 Simulation Classifications
Ferber [18] describes simulation as a very active branch of computer science, which consists of analysing the properties of theoretical models of the surrounding world. There are many types of computer simulation; the relevant classifications are summarised below.
Stochastic simulations use random number generators to model chance and randomness. It is unlikely that two runs of a stochastic simulation would be the same, but most generators use seeds that can be set to produce the same set of numbers each time, making reproducible results possible. Deterministic simulations are those that are inherently predictable, always producing the same output for a given input. Deterministic models are useful for experiments where the results need to be reproducible, however most real-world phenomena such as traffic have some degree of chance and therefore require stochastic simulation. [10]
Simulations can be classed as continuous or discrete. Continuous models take the form of equations using variables that correspond to real values. By solving the equations, the state of the model at any given point in the simulation can be calculated. Discrete simulations represent reality by modelling the state of the system and its state changes after time or events have passed. There are two types of discrete simulation: discrete time models and discrete event models. Discrete time models (time-sliced) are those that split the simulation into fixed time intervals. At each interval, the state of the model is updated using functions that describe the interactions. Discrete event models (event-oriented) are those which maintain a queue of events scheduled to happen in order of time, each event representing the change of state of an element in the model. The simulator processes the events in order, and each one can alter the event queue. Section 3.6.4 looks at the implementation issues presented by discrete time and discrete event simulation. [40], [1], [10]
3.3 Macroscopic vs. Microscopic
Traffic simulators can be microscopic or macroscopic depending on the level of detail required. Macroscopic simulators model the flow of traffic using high-level mathematical models often derived from fluid dynamics, thus they are continuous simulations. They treat every vehicle the same, and use input and output variables such as speed, flow and density. These simulators cannot differentiate between individual vehicles, and usually do not cater for different vehicle types. They lack the ability to model complex roadways, detailed traffic control features or different driver behaviours. [16], [8], [31]. Macroscopic simulators are most useful for the simulation of wide-area traffic systems, which do not require detailed modelling, such as motorway networks and interregional road networks [40]. This approach is not very realistic because in real life there are many different types of vehicle driven by different individuals who have their own styles and behaviours. However, it is fast and can be useful and accurate, but is not suited to urban models. [16]
Microscopic simulators model individual entities separately at a high level of detail, and are classed as discrete simulations. Each vehicle is tracked as it interacts with other vehicles and the environment. Interactions are usually governed by car-following and lane-changing logic. Rules and regulations are defined to control what can and cannot be done in the simulation, for example speed limits, rights of way, vehicle speed and acceleration. [40], [31]. Traffic flow details usually associated with macroscopic simulation are the emergent properties of the microscopic simulation. Microscopic simulators can model traffic flow more realistically than macroscopic simulators, due to the extra detail added in modelling vehicles individually [16]. Microscopic simulators are widely used to evaluate new traffic control and management technologies as well as performing analysis of existing traffic operations [31].
A very simple form of microscopic simulation is cellular simulation, which involves modelling the road as a series of cells and moving the vehicles between cells based on vehicle parameters. This method can implement links using an array with length equal to the number of cells in the link. Cell length has to be determined and must be the same for all cells, which is a disadvantage because it assumes all vehicles occupy the same amount of space. When the simulation is run, each cell can be either empty or occupied by one vehicle. Vehicles are moved forwards by their speed and are restricted by vehicles in front. Links are connected to nodes and rules exist which determine where vehicles go when they reach a node. This method can be very efficient because of the simple array structure, but it lacks some realism. [45], [28]. An even simpler approach is queue-based simulation, where vehicles always move at a set speed until they reach a queue at the end of each link. [27], [26]
3.4 Simulation Scenarios
Traffic simulations can be broadly classified by the type of road network and features they can simulate. The two main classes for simulators are those designed for motorway and urban environments. Simulators supporting a motorway environment focus on multiple-lane high-speed motorways. Much of the complexity required for a city environment does not need to be modelled, and the simulation can focus on vehicle behaviour and interaction. Motorway environments can be simulated accurately by both macroscopic and microscopic simulators. [38]. The main features of a microscopic motorway simulator are car-following and lane-changing behaviours. Junctions are sometimes modelled, allowing entry/exit rate to be varied to test the efficiency of the motorway under varying traffic load. Practical uses include studying the effect of motorway accidents, stop-start congestion, speed limits, ramp metering and lane closures on traffic flow. [9], [38]
An urban environment is one of the most difficult and complex traffic scenarios [16]. In contrast to motorway environments, urban environments have a traffic flow that is interrupted by intersections, traffic lights, roundabouts and other features. In addition to the extra road features, realistic urban simulators should model not only different classes of vehicle, but also pedestrians, cyclists and public transport systems. [14]. Urban traffic networks are usually very complex with many road sections and intersection points, often with conflicting traffic flows [25]. They usually have to manage a large number of vehicles on small road sections, which can result in a large amount of congestion [48]. Microscopic simulators are well suited to urban environments as vehicles can respond individually to the road features. Macroscopic simulators are not able to model the complexity of urban environments; they are only used to provide abstract flow details.
Some simulators can model both motorway and urban environments at the same time; these are classed as integrated or combined simulators. This is useful for the simulation of large areas encompassing both motorway and urban roads, especially where the performance of one affects the other, and is advantageous to the user as one package can simulate various scenarios. [34], [8]. Some simulators have focussed instead on modelling specific objectives such as to test intelligent vehicle control units, to analyse vehicle safety and comfort, or traffic at toll booths [1]. This project will focus on microscopic urban simulation, as it enables the modelling of congestion in urban scenarios.
3.5 Modelling Issues
Defining the model is one of the first stages of building a traffic simulation. This involves deciding how to represent objects (e.g. vehicles, traffic lights and pedestrians) in the simulation, and what parameters each object will require. It also involves determining how to represent the environment (e.g. road, lanes and intersections), and the effects it has on the other objects.
3.5.1 Modelling Vehicles
In a simulation, vehicles and drivers would most likely be modelled as one entity. However, in the real world they obviously are not, so when deciding on how to model them it makes sense to look at each in turn. Modelling a vehicle is quite straightforward; a few parameters can describe its features and behaviour: maximum speed, maximum vehicle acceleration and deceleration. Acceleration is especially important as it affects the rate of queue discharge. Dimensions are often implemented, enabling trucks and buses to be distinguished from cars. During simulation, current position and heading in the environment are required to keep track of the current state. Other details are not usually required because they add to the complexity without improving realism, however some simulators provide a detailed physics or engine models; these are useful when investigating emissions or the detailed effects of impact. [40], [1]
3.5.2 Modelling Drivers
Paruchuri et. al [32] suggest that the decisions drivers have to make can be split into micro and macro goals. Macro goals are the destination and route taken, while micro goals involve decisions at each point of time in the interest of achieving the macro goal. The macro goal involves daily planning and route generation functionality, often input from O-D data. Micro goals are decisions involving controlling the vehicle, such as desired speed, overtaking and turning. Drivers all have different driving styles, which are governed by their individual characteristics, such as aggressiveness, confidence and driving experience. Driving styles are often approximated using parameters for important behavioural features and then these values are used as part of the reasoning process to work out the decision a driver would take at any instant. [16], [32]. Examples of these parameters are:
- Preferred speed; the speed the driver likes to maintain on an empty road.
- Preferred rate of acceleration, which is not usually the vehicle’s maximum rate, but a rate influenced by a driver’s aggressiveness and desire for comfort among other characteristics.
- Preferred rate of deceleration, which is similar to that for acceleration.
- Gap acceptance, which is the distance a driver prefers to leave between them and the vehicle in front.
These parameters can model a fair amount of driver characteristics. An aggressive driver would have a high preferred speed, a high preferred rate of acceleration and deceleration, and a small gap acceptance. A cautious driver would be much the opposite. Many simulators incorporate all of these parameters, and demonstrate realistic driving behaviour. To convert these parameters into actions, a reasoning process must be evaluated at each stage of the simulation; this is discussed in section 3.6 below. [16], [32]
3.5.3 Modelling the Environment
In traffic simulation, the environment in which vehicles drive is a road network which is made up of link segments, nodes (junctions and intersections) and control features which are usually part of the node. Each link can have one or more lanes, and may operate in one or both directions. Nodes can be broken down into the following basic types: uncontrolled non-priority junctions, priority junctions, roundabouts, signal controlled junctions and grade separation junctions. Special cases of link exist such as merges where two lanes must merge into one, diverges where one lane splits into two and weaving sections where a diverge closely follows a merge. Examples of other control features are traffic calming schemes and pedestrian crossings. [43]
Models usually represent the network as a collection of links joined by nodes. Nodes have properties such as location (e.g. coordinates) and type of node. Links have properties such as length, number of lanes, speed limit, etc. For road networks that are not self-contained, sources and sinks are created as positions in the network where vehicles arrive and leave respectively. Sources have parameters that determine the rate of entry of vehicles into the network, and sinks always remove vehicles that reach them. [28]
3.6 Simulation Issues
Models of vehicles, drivers and the environment are of no use unless they can be manipulated during simulation. Simulation involves using behavioural rules to change the model over time. This involves moving each vehicle based on its parameters and its driver’s decisions. To simulate a single car on a long straight road is rather simple, as the vehicle would just accelerate to the driver’s preferred speed. It becomes increasingly complex as other vehicles, more lanes, and more roads are introduced; to deal with these, vehicle following and lane changing models are used. [24]
The heart and soul of a microscopic traffic simulation is the car-following and lane-changing logic.
[31]
3.6.1 Vehicle Following
Vehicle following models are those that attempt to describe how a vehicle behaves in standard conditions. These models are called such because they focus primarily on the relationship between the current car and its leader [40]. Many vehicle following models are discussed in the literature, and many of these are based on anti-collision concepts. One well-known model of this type is the Gipps model, developed in 1981. It assumes that a vehicle always aims to be able to stop safely if its leader performs an emergency stop. It calculates the new speed of the following vehicle using the current speed of both vehicles, the following driver’s desired speed, maximum acceleration and deceleration, and the gap between vehicles. It calculates two possible values for speed; one based on the driver’s desired speed limited by vehicle performance, and one based on safety, i.e. the speed that must be taken to ensure there is no collision. It then selects the minimum of these possible speeds to use in the simulation, which ensures both limitations are applied. [11]
Another class of models are known as psycho-physical vehicle following models, proposed by Wiedemann in 1974. These models attempt to capture both physical and human components of vehicle control. They do this by maintaining a vehicle state, where the current state is determined through differences in speed and distance to the leading vehicle. Each state has a different method of calculating the acceleration of the vehicle, and upon a state change, the new acceleration is calculated once and is then constant until the next change of state. Since the acceleration is not calculated at each time step in the simulation, it has been shown that the event-oriented time advance method (see section 3.2) is very efficient for this model. State changes can be determined and listed in a queue so they can be processed in order. Some examples of vehicle states and the situations that cause them are shown in the observation-decision diagram below. [40]
Figure 3.1: Observation-decision diagram showing limits in different of speed (DV) and distance (DX) for selecting vehicle states. Source: [40]
Fuzzy logic can be used to model driver inaccuracy and uncertainty, and can lead to more realistic models than those purely based on accurate mathematics [4]. Vehicle following models range from simple relationships between speed and distance to complicated models of driver behaviour and emotion. All of these can model the main features of the macroscopic traffic flow with acceptable accuracy. [24]
3.6.2 Lane Changing
Figure 3.2: Basic notation for lane change manoeuvres. Source: [20]
Lane changing models are those that describe when and how vehicles change lanes on a multi-lane road such as a motorway. A lane change scenario can be summarised as in Figure 3.2. The behaviour of each vehicle depends on the vehicles around it, and each vehicle has to make decisions based on its knowledge of the environment [20]. Lane changing models have been studied in the literature to a similar extent as vehicle following models, and several important models have been devised [24]. The basic lane changing rules are described in the following quote.
All lane changing rules, no matter if for CA or other models, follow a similar scheme (e.g. Sparmann, 1978): In order to change lanes, drivers need an incentive, and the lane change needs to be safe. An incentive can be that the other lane is faster, or that the driver eventually needs to make a turn. Safety implies that one needs enough space on the target lane.
[28]
Using this model produces a lane-changing system made up of two rules: incentive and safety. If both are true, then the lane change takes place. Incentive could be true if the gap in front of the vehicle in the other lane is larger than the current gap, in which case an immediate speed increase would be possible. Safety can be determined by checking whether the gap behind on the target lane is large enough that the vehicle behind doesn’t have to brake immediately. This has been shown to model U.S. traffic quite well, but there are other issues to consider, e.g. vehicles may need to change lanes in order to be in the correct lane at the intersection or motorway exit. [11]
Other lane change issues emerge from road rules, for example in the U.K. passing is normally only allowed on the right and vehicles should try to keep to the left lane if possible. Driver characteristics can also play a part, since some drivers prefer to stay in the same lane even if changing lanes would result in a higher speed, and some drivers prefer to stay in outer lanes even if there is space in inner lanes. [11], [28]. Details of some more complex recent lane changing models can be found in [20] and [24].
3.6.3 Urban Simulation Issues
Specific behavioural rules are required to achieve realistic traffic simulation in an urban environment. Some examples of features that can be implemented are traffic lights, roundabouts, traffic signs, obstacle avoidance, overtaking using the oncoming lane, turning into side-roads and turning at junctions. These can be implemented using specific vehicle behaviour rules for each feature, which need to interoperate well with the vehicle following and lane changing behaviours. The rule that takes precedence can be decided by the situation and priority weighting of each rule, so that time- or safety-critical incidents are dealt with immediately. [16], [38]
3.6.4 Accuracy and Time Issues
The two types of discrete simulation mentioned in section 3.2 are discrete time models and discrete event models. The accuracy and run time of microscopic simulators depend to an extent on the method of time advance implemented. The accuracy of discrete event simulators is perfect, because the exact simulation time of each event is calculated to determine its position in the event queue. However, the run time of such a simulation depends on the number of events that need to be processed. This in turn depends on the number of dynamic objects (e.g. vehicles) in the simulation. It is not usually possible to predict the number of events which will occur and therefore not possible to predict the run time of such a simulation. [40]
The accuracy and run time of discrete time simulators depends on the number of dynamic objects and the chosen time interval. The value used in many existing simulators is 1.0 seconds, which corresponds to the average reaction time of the driver. This means that every one second in simulated time, the behaviour rules are evaluated and all vehicles positions are updated. The smaller the time slice, the more times every object must be evaluated and therefore the longer the overall run time. Smaller time slices give results that appear more accurate because the vehicle interactions are evaluated more often. This means there is a trade-off between run time and accuracy when using discrete time simulation. [40]
A study by Schulze and Fliess [40] evaluates discrete event and discrete time methods in traffic simulation. It compares event based to time sliced with values of 1.0, 0.5 and 0.2 seconds. It recommends event based methods for use in psycho-physical vehicle following models and concurs that this is both faster and more accurate than time sliced methods. It shows that a smaller time slice gives more accurate (closer to the event-oriented result) and more consistent results than a large time slice, and suggests that a time slice value of 0.2 seconds is preferable especially when simulating high volumes of traffic. It is possible though, that while the event-oriented method is accurate, it is not realistic, as it does not model driver reaction time or fuzzy driver perception.
3.7 Requirements of Traffic Simulators
The SMARTEST project conducted by Leeds University performed an in-depth study on the importance of various features for traffic simulations. The study identified 58 microscopic simulators from across the world, including commercial, free and under-development systems. Of these, 32 were chosen for in-depth analysis, shown below as classified by their developers. [1]
|
Motorway |
Urban |
Integrated |
Other |
|
CASIMIR |
AUTOBAHN |
AIMSUN2 |
ANATOLL |
|
DRACULA |
FREEVU |
CORSIM |
PHAROS |
|
HUTSIM |
FRESIM |
FLEXSYT II |
SHIVA |
|
MICSTRAN |
MIXIC |
INTEGRATION |
SIMDAC |
|
NEMIS |
SISTM |
MELROSE |
|
|
NETSIM |
|
MICROSIM |
|
|
PADSIM |
|
MITSIM |
|
|
SIGSIM |
|
PARAMICS |
|
|
SIMNET |
|
PLANSIM-T |
|
|
SITRA-B+ |
|
TRANSIMS |
|
|
SITRAS |
|
VISSIM |
|
|
THOREAU |
|
|
|
Table 3.1: Selection of Traffic Simulators by Type. Source: [1]
Most of the simulators use a time-sliced approach as described in section 3.6.4. The developers of the above simulators completed a questionnaire for SMARTEST to discover the features they have implemented. A similar questionnaire was completed by 44 known users of traffic simulation tools to identify the most important requirements. The following chart shows the common features identified by SMARTEST along with the percentage of simulators that implement each feature and the percentage of users who thought it was crucial or important. It is in decreasing order of importance as rated by the users of simulation systems, apart from queue spill back and weaving which were not on the users’ questionnaire but are implemented by most systems in any case. [2]
Figure 3.3: Importance of Traffic Simulator Features. Data sources: [1], [2]
Note that the ability to model road networks, vehicle following, lane changing and intersections are essential features and therefore are not included. Although the two data sets are not intended for comparison, it gives an idea of the percentage of developers versus users who consider each feature important. The data shows that the most required features are incidents, public transports and roundabouts. A few features appear to be more important to the users than to some developers: incidents, public transport, pedestrians and bicycles/motorbikes; perhaps these features deserve more attention in future simulators. Only one of the respondents (PARAMICS) mentioned the ability to model HOV lanes, although this was not explicitly asked by the questionnaire.
The study found that a user-friendly graphical interface is crucial for both input and editing the model and presentation of results. The majority of uses are to simulate traffic over a 0.5 to 2 hour period, i.e. the peak rush hours. The required speed of simulation execution is faster than real-time; about half the users are content with 1-5 times faster while the remainder require over 5 times faster. The most important model properties identified were that the model must have been verified, and that it allows user-defined key parameters and provides defaults for these parameters. Simulators provide results in the form of macroscopic indicators; the required and implemented indicators are shown below in the same form as the previous chart. [2]
Figure 3.4: Importance of Simulator Indicators. Data sources: [1], [2]
It is clear that many indicators are considered less important to developers than to users; many in the area of safety, environmental and public transport. The most required efficiency indicators are provided by most simulators but are still omitted from many. These could be areas of improvement for indicators of future traffic simulators. Features in the transport telematics[2] and technological functions categories and are shown in the chart below, and also leave room for improvement. The most important functions are concerned with urban traffic control, such as traffic signals. Public transport support is still lacking in simulators although it is considered of great importance to users.
Figure 3.5: Transport Telematics and Technological Functions. Data source: [1]
Chapter 4: Agent-Based Traffic Simulation
4.1 Multi-Agent Systems
4.1.1 Agents
Agent-based systems are a relatively new concept in computing, having been studied since about 1980, and are currently of great interest to researchers. Agent systems are all about autonomy; building systems with some degree of intelligence. Although there is no universally accepted definition, one definition of the term ‘agent’ is presented below.
An agent is a computer system that is situated in some environment, and that is capable of autonomous action in this environment in order to meet its design objectives.
[56]
Agents are computing entities that receive sensor input from their environment, and can produce actions that influence their environment. Agents usually have a set of actions they can perform, each action having preconditions and aiming to affect their environment. Agents can communicate with each other, allowing them to cooperate, negotiate and coordinate their actions. Agents have objectives and goals, can make plans of actions to perform, and aim to achieve their goals through these plans. [18]
A multi-agent system (MAS) is one in which a number of agents exist and interact in the same environment. Each agent is able to perceive and influence part of the environment; this area is known as the agent’s sphere of influence. The environment can contain passive objects that can only be acted on by agents and therefore have no control over themselves. [18], [56]. In agent-based traffic simulation, the environment is the road network, and the agents are principally vehicles who can affect the agents surrounding them. Control features such as traffic lights could also be modelled using agents.
4.1.2 Agent Environments
Russell and Norvig suggest that agent environments can be classified by their various properties, which are summarised below. [56]
- An accessible environment is one in which an agent can reliably obtain information about the current state of the environment. Environments can be inaccessible if there is an amount of uncertainty or if some information is simply unavailable to an agent.
- A deterministic environment is one in which an agent’s actions has guaranteed effects. The agent can be certain of the effect of its actions without worrying about failure. Most non-trivial agent environments are non-deterministic; therefore, agents must be able to cope with failed actions and unexpected circumstances.
- A static environment is one that will be unchanged except by the actions of the agent. A dynamic environment is one that can be altered by other processes such as other agents. Most environments are dynamic, therefore agents must be reactive, i.e. they must be able to respond to changes in the environment.
- A discrete environment is one that has a finite number of states, whereas a continuous environment has an infinitely large number of states.
The most complicated type of agent environment is one that is inaccessible, non-deterministic, dynamic and continuous; these can be referred to as open. Most agent environments are also real-time, in the sense that time plays a part in an agent’s interactions in that environment. In a real-time environment, agents cannot spend an indefinite amount of time deciding the best action and usually aim to make decisions in a short amount of time. [56]. The traffic environment can be described as both open and real-time.
4.1.3 Differences to Object-Oriented Programming
To aid understanding, the agent-oriented approach could be thought of as an extension to the object-oriented (OO) approach. Objects are computing entities that encapsulate some state, have methods to modify their state, and communicate by passing messages. Objects therefore have some form of control over their state, but they do not have control over their behaviour. Agents are considered to have control over their behaviour, meaning that each agent has its own thread of control and can perform actions whenever it chooses without being acted on by any other entity. Although it is possible for all objects to have their own thread of control, it is not central to the OO concept.
Agents also exhibit flexible behaviour, which is not part of the OO paradigm. This means they are capable of reactive, proactive and social behaviour. Reactive means they can perceive and respond to changes in their environment, proactive means they can take the initiative to achieve their goals, and social means they can interact with other agents to satisfy their objectives. The natural evolution of agent-based programming is depicted in Figure 4.1. [56]
Figure 4.1: Evolution of Agent Programming. Source: [30]
This suggests that agent programming is more declarative than imperative programming. In imperative programming, an explicit algorithm is specified that describes the steps required to reach the goal. Declarative programming, in contrast, specifies the goals and rules that can be used, and leaves the algorithm unspecified. Agents can use intelligence to define their own steps required to reach the goal, based on the rules they have available.
4.2 Agent-Based Modelling (ABM)
4.2.1 Multi-Agent Modelling and Simulation
Simulation can be implemented using multi-agent systems; this is known as multi-agent simulation or agent-based modelling. The agent paradigm maps neatly onto many modelling scenarios because each individual in the scenario can be directly represented as an agent. Behaviours can be programmed into the agents so that individuals behave in the same way as the entity they are modelling. An interesting point is that individuals are given simple behaviours, and when many agents are simulated as a group, behaviours often emerge that were not explicitly programmed into the agents; these are known as emergent phenomenon. [18]
In contrast to the classic approaches, multi-agent simulation does not boil down to implementing a model and then analysing the response from this model as against the input parameters, but participates in the process of searching for models.
[18]
This suggests that multi-agent simulation can be an excellent prototyping tool for developing and refining models. Because it can allow parameters of the individuals and the environment to be varied easily, it is possible to experiment with many alternatives and gain results in real-time.
4.2.2 Calibration and Validation
Calibration is the process of setting model parameters and behaviour so that it matches real-world data. This usually requires data on the microscopic or individual level, such as vehicle speeds, reaction times and driver behavioural parameters. Calibration also involves optimising the model for the individual scenario to ensure results are realistic. Validation is the process of comparing simulation outputs with real life data to ensure the results are plausible. The data used in validation should differ from the data used for calibration, or inaccuracies may not show up. Validation data is usually macroscopic statistics such as flow rate, speeds and queue time, which can easily be compared with data from real traffic experiments. [3], [28]
A related issue in agent-based modelling is understanding causality. This problem is that unexpected results can be either useful or the result of mistakes or inaccuracies in the model. It can be difficult to understand the cause of certain behaviours, and tools to assist in this are generally lacking. [35]
4.2.3 System Development
The design and development process for multi-agent simulations is inherently different to traditional systems. The focus is on accurate modelling of individual agents rather than the design of passive functions. When designing an agent, the important decisions involve its behaviour, actions, plans, goals, and how it interacts with other agents and the environment. At the Center for Agent-Based Modelling, it is suggested that modelling is a 7-stage process: brainstorming, theory, hypothesis, flowchart, code, analyse and publish. [46]
Because multi-agent systems are relatively new, there is not a generally accepted methodology for the design and development process, and existing OO methodologies do not cover them to a sufficient extent [12]. However, many new methodologies are being proposed, such as Agent UML, where features of the popular UML standards are being adapted to fit in with the design of multi-agent systems [42]. Other methodologies in use include MESSAGE, PASSI, Tropos, Prometheus and MaSE [30]. For the purposes of this project however, existing development methodologies and UML will suffice, making note of suggestions from the 7-stage process.
Multi-agent systems are often written in an object-oriented language like Java or C++, because agents can be easily viewed as an extension to objects [28]. When developing a multi-agent simulation, it makes sense to use a helper package designed for this purpose. This is because the important part of such a system is the accuracy of the model parameters and behaviour, and a helper package can abstract the design of the model from the programming of it. This allows the modeller to focus on tweaking the model rather than solving unrelated coding issues.
To assist with agent-based modelling and simulation development, there are integrated development environments (IDEs) and toolkits/libraries. IDEs are all-in-one modelling and simulation environments, which allow the model development, any code required, and running of the simulation to all be done in the same graphical environment. Because the IDE can be designed with agent-based modelling in mind, graphical tools and abstract language can make it easier and more accessible to modellers. Toolkits or libraries intend to make simulation facilities available to existing programming languages such as Java or C++. They are generally less accessible to modellers because the user must be able to program in the toolkit’s language to start with, and then must learn how to interface with the toolkit. [47]
Some examples of popular toolkits/libraries are Swarm, Repast, Cybele, JAS and MASON. These are all free open source packages available for Java. They provide efficient simulation facilities and can support any behaviour that can be programmed in the base language. Swarm, Repast and MASON are compared in [35], which concluded that they are fast and powerful but less intuitive and more difficult to learn than NetLogo, an IDE that is described below. [35]. Since the aim of this project is to experience agent-based modelling, the decision has been made to use an IDE so that modelling issues can be paramount rather than programming issues.
4.2.4 Integrated Development Environments
These systems provide a complete environment for developing a model and running the simulation, and offer various levels of abstraction. A screenshot of each environment is shown, along with a brief overview of the system. Only software that is free to use and provides a visual representation of the simulation has been considered.
NetLogo [47]
NetLogo is an agent-based modelling environment designed for simulating complex natural and social phenomena. It is written in Java and is therefore cross-platform, it is freeware, and has a large friendly user group. It enables the user to model any number of agents in a variable-size environment using a simple programming language derived from Logo. It is designed for use by students and researchers to explore the behaviour of programmed agents under varying conditions. It follows the philosophy of ‘low threshold, no ceiling’, meaning that new users should find it easy to get started, but advanced users should not find it limiting.
NetLogo comes with extensive documentation, tutorials, and over 300 sample models that demonstrate all aspects of the tool. Models can be saved as Java Applets and run on web pages by any user with the Java Virtual Machine installed. It is possible to view the current state of the environment and agents in 2D or 3D, and agents can be given any vector shape to display their type. Commands can be in the form of procedures that are called by buttons on the interface, or entered directly in the command console on the main panel. Its logo-esque language is quite natural, allowing code to be easy to read, write and understand.
Figure 4.2: NetLogo Interface
NetLogo has a well-designed graphical interface and interface builder in one that allows the novice and expert alike to run, alter and develop models with ease. It provides many built-in widgets to alter simulation parameters at runtime, including sliders, buttons, and drop-down menus, and allows output in the form of graphs and variable monitors. Simulation time is measured in discrete ‘ticks’, and simulation speed can be adjusted by a slider above the display. It can provide deterministic simulation if the random seed is set before the simulation is run.
Breve [23]
Breve is described by the author as a 3D simulation environment for the simulation of decentralized systems and artificial life. It provides simulation of continuous time and space, a physics engine, collision detection, and allows realistic 3D physical simulations to be easily defined by the behaviour of agents. Simulations are programmed in an interpreted object-oriented language called ‘steve’, which is specifically designed for implementation of 3D simulations, and uses natural language structures to simplify coding. Breve is free, cross-platform, and comes with around 40 example models, which help the user to learn the system.
Figure 4.3: Breve Interface
The breve GUI is presented in the form of a window for each part of the simulation. One shows the 3D display with simulation controls and system menu options, and others open for command log, simulation code, and object inspector. The visualised world can be manipulated using the mouse, and objects in it can be interrogated through context menus. This sophisticated system is best for simulating physical entities in an extensive 3D continuous world.
SB-MASE [21]
Subsumption-Based Multi Agent Simulation Environment (SB-MASE) is a cross-platform Java application designed to assist in the development of control software for simulated and real agents, such as robots. It is based on the subsumption architecture, which is an AI concept to describe behaviours. It allows complex behaviour to be split into layers of more and more abstract behaviour, where each layer can use (subsume) the layers below it. SB-MASE allows agent tasks to be modelled as processes, with sensors as inputs and actuators as output.
Figure 4.4: SB-MASE Interface
SB-MASE provides a number of windows within a main frame; program controls, simulated world, map editor, agent editor, and more. Although multiple agents can exist in the world, since it is designed to interact with real-world agents, usually only a preset number of predefined agents are used. Agents are inserted and removed explicitly by the user, and their behaviour is designed using a drag-and-drop process editor that can connect outputs from one process to the input of another. This system would be best used to develop control systems for physical agents such as robots.
SeSAm [41]
SeSAm (Shell for Simulated Agent Systems) is an integrated environment written in Java, intended for general agent-based modelling and simulation. It is designed to allow complex models to be easily designed and run in a single modelling environment. Agent reasoning is represented using a UML-style activity diagram, where each activity exists as a script of actions that run predefined functions, and the current state is determined by rules. All functionality can be designed through the graphical interface by selecting operators and methods. The tool currently comes with seven example models to try out.
Figure 4.5: SeSAm Interface
Again, the SeSAm i