The Application of Artificial Intelligence to Transportation System Design
by Ricardo Hoar and Joanne Penner
Introduction
The negative effects of a poorly designed transportation system affect everyone. Time wasted in traffic affects our health, our economy, and our environment. People stuck in traffic are not working, shopping or enjoying leisure time and can suffer emotional distress. Furthermore, fuel consumed by idling cars produces additional greenhouse gases that may contribute to global warming. In 1995, 26% of all emissions were found to come from transportation, and those emissions are rising [5]. Reducing automobile emissions will be an essential part of meeting the Kyoto Accord's target emission levels.
The challenge of reducing congestion lies in the design of an efficient and adequate transportation infrastructure. As cities grow, old solutions to transportation problems fail, and new solutions must be proposed to deal with the more complex problems. This article discusses the current research of SuRJE, a traffic simulation tool that uses biologically inspired techniques to improve traffic light timings.
To gain insight into modeling traffic, analogues in the biological world are considered. Social insects exhibit seemingly intelligent collective behavior, emergent from the large number of parallel interactions in the population. Ants communicate through leaving and detecting pheromones in their environment, and can orchestrate complex group behavior without centralized control [3]. These concepts from social insects form the basis for the cars' behavior and interaction in SuRJE. Evolutionary theory, explaining the adaptation of species, is another biological idea exploited in SuRJE. Through the evolution of successive generations of traffic light timings, it is possible to reduce overall traffic congestion [4].
This article will explore existing simulation software, and explain in detail how the SuRJE researchers aim to improve transportation infrastructure through the use of evolutionary and swarm design.
Current Simulation Software
The ability to model transport scenarios through simulation has already proven an effective tool in traffic management and infrastructure planning [1]. Simulations are important because they can evaluate proposed solutions quickly, giving the engineers feedback on their ideas before any pavement is ever laid.
Simulations can be classified into two groups. Macro model simulations use mathematical formulae based on fluid dynamics to calculate the approximate flow of the cars [2]. Conversely, a micro model is one where each car is individually simulated and the interaction of the individuals produces realistic traffic flows [1]. The advantage of the micro model is that traffic behaviors arise from the interaction of many local drivers, allowing for dynamic and adaptive traffic flows.
Why Current Systems are Insufficient
Of the over 58 commercial simulation packages currently available, none address the transport problem in a holistic manner, taking into account all modes of transportation [1]. Some of these tools incorporate visualization and interactivity into the interface, but none use artificial intelligence strategies to adapt preferable traffic light timings. Although these tools are useful for testing, they are unable to propose intelligent solutions to traffic congestion issues.
The SuRJE researchers expect that artificial intelligence strategies applied to computer simulation will prove essential in solving the world's increasingly complex traffic problems. If growth is to continue, alternative means of transportation must be taken into account when planning a city and when designing a simulation. This increased complexity will create new problems that can be solved by computers through the creation of an accurate and intelligent simulation.
SuRJE Interactive Traffic Simulation and Optimization Tool
Overview
SuRJE is a micro model simulation that uses artificial intelligence to propose solutions to particular transportation scenarios. Through the interface a user can build road infrastructure and set traffic densities. Scenarios can then be run to test the efficiency of the infrastructure for the given traffic flow. These tests can also be used in conjunction with an evolutionary engine to propose improvements to the traffic scenarios being evaluated. SuRJE currently adapts the traffic light timings with the single-objective aim of reducing the overall waiting time in the system.
Implementation
Object-oriented programming techniques are used to implement SuRJE for Linux Version 1.0 using C++, QT GUI libraries [9], and the graphics libraries of OpenGL [7]. The integration of the map builder, micro simulation, and evolutionary engine into a single software package provides a powerful solution to design and testing.
Interface
SuRJE emphasizes the interaction between human and computer by using an interface that visualizes the infrastructure of a city as well as the cars (Figure 1). The development of the intuitive map viewer as an alternate means of evaluating sequences is crucial because it allows users to identify potential solutions at a glance while retaining traditional statistical output. The interface gives the user control over all aspects of the simulation and evolution. Being able to design a scenario with roads, lights, rules, and traffic flows from scratch ensures any idea can be easily implemented and tested. Once a scenario is loaded the user retains control over the cars behaviors and the probabilities associated with the evolutionary engine.
Figure 1: Collage of the SuRJE Interface.
Micro Model
SuRJE simulates the decisions and behaviors of each driver through the ant inspired method of stigmergy (communication through signs in the environment). The drivers in SuRJE are like ants in that they leave metaphoric pheromones in the lanes. Through the pheromones, a driver knows approximately how far it is from other cars and can signal upcoming actions such as lane changes. Local traffic rules and communication through pheromones allow for localization of the area with which each agent must interact, speeding up computation. It is through the interaction of the agents on a large scale that one observes emergent behaviors similar to real traffic [7].
Agents
Every car is assigned a destination based on the user-defined number of destination regions and associated probabilities. From the time a car is seeded it seeks out that destination abiding by the laws along the way. As each car is created, it is assigned its own parameters that have an affect on its behavior. Each car has an ideal speed abidance ratio, which is used to determine their desired speed. Cars with ratios over 1 have a tendency to exceed the speed limit while cars with ratios below 1 travel slower than the speed limit. Additional parameters relating to impatience and lane changing are implemented in a similar fashion. These parameters are input by the user as mean values and deviation from that value.
Because the cars manifest slightly different behavior, the interaction of different drivers produces interesting and realistic results. This ability to control the type of drivers in the simulation can also prove a powerful strategy in design. For example, solutions could be evolved that favor law abiding drivers while disfavoring speeding. On the other hand, a more realistic mix of speeds and aggressiveness could be combined to evolve the lights to favor a realistic distribution of behaviors. The user ability to decide and easily change these parameters is essential for a useful and adaptable program.
Artificial Intelligence used for Infrastructure Planning
Artificial intelligence plays a role in two major aspects of SuRJE. Firstly, the cars use heuristics to determine which decision to make at intersections, mimicking the intelligent decisions made by human drivers. Secondly, SuRJE uses an evolutionary strategy to evolve traffic light timings with the intent of minimizing the overall waiting times for the drivers [8]. The way in which the cars drive has a direct effect on the light timings that will emerge as optimal. This behavior of the system is seemingly intelligent because it automatically optimizes for the type of traffic that the user defines.
Car Intelligence
One technique used to give the cars some intelligent decision-making behavior uses a nearest-vector heuristic. When a car approaches an intersection, it compares the direction vector to its destination with all of the possible choices, and then chooses the one pointing in the closest direction (Figure 2). This routing mechanism will fail for certain road maps [6], but can be combined with variables such as speed limits and current congestion levels to form a more robust and dynamic heuristic. Although incomplete in version 1.0, this technique provides acceptable decisions for many scenarios and, more importantly, illustrates the strategy of local decision making.
Figure 2: Car choosing between green paths A and B. The angle b
between B and ideal vector X is smallest so the car chooses path B.
Evolutionary Strategy
Adapting scenarios to optimize for various types of drivers, cities, and designs requires an algorithm that is both adaptive and general. Although calculations can be done to coordinate consecutive traffic lights on one street [2], there is no known formula that will phase all lights together in an optimal fashion for every scenario or for more complex sections of the city. An evolutionary strategy is capable of exploring diverse potential solutions while adapting to dynamic variables. Therefore, the researchers chose an evolutionary strategy to improve the light timings. They hypothesize that in future versions this strategy will also be able to improve other aspects of infrastructure planning.
SuRJE Version 1.0 evolves the set of light timings for a map. The alternating color sequence for each light is encoded into a genome. The set of light timings for a map composes one individual in the population. In each generation, a parent individual spawns 10 children, each with slight mutations. All 10 children and the parent are evaluated for fitness in the simulation, and the individual with the best score survives to produce the next generation of offspring (Figure 3a). The fitness function measures how well the set of light timings satisfies the optimization objective. In this case, a reduction in the value of the fitness function (Figure 3b) indicates a lower collective waiting time. These results are verifiable by an intuitive observation of the model where the traffic is flowing more freely.
Figure 3a: Diagram of Evolutionary Strategy.
Figure 3b: Fitness function for sequence evaluation where
wi denotes total waiting time and di
denotes total driving time for car i.
Examples of Evolution
Straight Alley
This scenario demonstrates the effectiveness of the algorithm on a relatively simple problem. The main road has three lanes in each direction, and the speed limit is 50 mi/hr. The side road has one lane in each direction, and the speed limit is 30 mi/hr (Figure 4a). In the example demonstrated here, 90% of the traffic is seeded at each end of the main road and the remaining 10% at each end of the smaller road. A default traffic light timing sequence is initialized such that all lights are uniform.
After 130 generations there is an improvement of 59% in the fitness of the solution (Figure 4b). The evolved sequence is similar in appearance to a well-known solution for coordinating consecutive traffic lights. The three lights are offset from each other such that a car passing through one green light will arrive to the next intersection at a green light, maintaining a flow of traffic. Also, the lights along the main road remain green longer than for the side road, to account for the higher volume of traffic and the faster speed limit. This solution, generated entirely by computer software, is comparable to a solution that could be conceived by a human engineer; lending credence to the notion that the software is artificially intelligent.
Figure 4a: Screenshot of Straight Alley.
Figure 4b: Improvement in fitness over 130 generations.
Boulevard
This scenario is more complex than the aforementioned Straight Alley scenario. The roads curve, the intersections are not all the same, and traffic can make a wider variety of choices (Figure 5a). For this test 90 % of the traffic was seeded from both sides of the northern road. The remaining 10% was seeded from the south. Despite the wider variety of choices being made by the cars, the evolutionary strategy was still able to improve fitness (Figure 5b).
Figure 5a: Screenshot of Boulevard.
Figure 5b: Improvement in fitness over 200 generations.
Conclusions and Further Applications
The use of an evolutionary strategy to optimize traffic light timings has been shown to be effective. The micro model simulation where drivers are individual agents and communicate like ants has been shown to be a useful means of modeling real traffic. The application of these techniques to a more holistic simulation of human transportation may yield important and creative results applicable in the domain of transportation planning and design.
Future versions of SuRJE will expand the evolutionary strategy to consider multiple objectives. For example, in addition to placing a weight on the waiting time of the cars, a weight will be placed on the waiting time of travelers waiting for the bus. Additional objectives could also be considered such as to minimize fuel emissions or to minimize the longest individual waiting time. Increased driver intelligence will also be implemented, allowing drivers to negotiate more realistic and complex scenarios such as merging and traffic circles. Additionally, drivers will be able to use multiple heuristics based on speed, congestion, and direction to determine their route and will be able to adapt their route based on changing conditions.
References
- 1
- Figueiredo, L., et al. Intelligent Transportation Systems. In Proceedings of the IASTED International Conference Applied Simulation and Modeling. (June 25-28, Crete, Greece). ACTA Press, Calgary, Alberta. 2002, pp. 467-472.
- 2
- Garber, N.J. and Hoel, L.A. Traffic and Highway Engineering (3rd ed). Brooks/Cole, Pacific Grove, CA, 2002.
- 3
- Gordon, D. Ants at Work. The Free Press, New York, NY. 1999.
- 4
- Hoar, R., Penner J., and Jacob, C., Evolutionary Swarm Traffic: If Ant Roads had traffic lights. In Proceedings of the 2002 Congress on Evolutionary Computation. (May 12 - 17, Honolulu, Hawaii). IEEE, Piscataway, NJ. 2002, pp. 1910-1916
- 5
- Kohn, H. Bus Versus the Automobile: An Element of Canada's program to fulfill the Kyoto Agreement. In Passenger Bus and Urban Transit Statistics, 1997. Statistics Canada, Minister of Industry, Ottawa, ON. 1999, pp. 51-66.
- 6
- Kranakis, E., Singh, H.,Urrutia, J. Compass Routing on Geometric Networks. In Proceedings of 11th Canadian Conference on Computational Geometry. (August 15-18, Vancouver, Canada), 1999.
- 7
- OpenGL Architecture Review Board, Woo, M. et al. OpenGL Programming Guide (3rd ed). Silicon Graphics, Addison Wesley, Reading, MA, 1999.
- 8
- Penner, J., Hoar, R, and Jacob, C. Swarm-Based Traffic Simulation With Evolutionary Traffic Light Adaptation. In Proceedings of the IASTED International Conference Applied Simulation and Modeling. (June 25-28, Crete, Greece). ACTA Press, Calgary. 2002, pp. 467-472.
- 9
- Trolltech. Qt Reference Documentation (QT Version 3.0.5). 17 September 2002. <http://doc.trolltech.com/3.0/index.html>. (26 September 2002).
Ricardo Hoar (hoarr@cpsc.ucalgary.ca) and Joanne Penner (pennerj@cpsc.ucalgary.ca) are graduate students of computer science at the University of Calgary. They completed their B.Sc. degrees in 2002. For more information, videos and screenshots, the SuRJE website is available at http://www.cpsc.ucalgary.ca/~pennerj/SuRJE.
The SuRJE project was inspired by environmental concerns with the goal of creating a more efficient transportation system. Ricardo Hoar and Joanne Penner implemented the first version of SuRJE in an undergraduate course with Dr. Christian Jacob. The project showed promising results so Ricardo and Joanne continue to research SuRJE as an application of swarm intelligence and evolutionary design. They are currently seeking partners in industry to facilitate the further development and deployment of SuRJE on a real city.