Transportation System Design
Transportation plays an important part in everyone's life as it not only influences our daily activities but also plays a vital part in the maintaining the stability of the environment. A poorly designed transport system results in excessive emission greenhouse gases from the fuel consumed by idle cars, which contribues to global warming. To solve this problem and design a efficient traffic system Ricardo Hoar and Joanne Penner suggested SuRJE, a tool that uses the GA approach.
SuRJE: Interactive Traffic Simulation and Optimization Tool
SuRJE is a micro model simulation using artificial intelligence to provide solutions for particular transportation scenarios. Through the interface one can build road infrastructure and set traffic densities. Scenarios can then be run to check how efficient the infrastructure is in relation to a given density 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.
Artificial intelligence plays major role in two major aspects of SuRJE. Firstly, the cars use heuristics in order to make decisions on intersections trying to implement same kind of decisions human drivers take at similar situations. Secondly, SuRJE uses an evolutionary approach to evolve traffic light timings to minimize the waiting time of the drivers. The way in which the cars drive has are related to the light timings. This behaviour of the system is seemingly intelligent because it automatically optimizes for the type of traffic that the user defines.
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, 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.
SuRJE evolves with the set of traffic light timings as its key parameter. The alternating color sequence for each light is encoded into a genome. Each generation, a parent individual results in 10 offsprings, 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 1). 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 2) indicates a lower collective waiting time. These results are verifiable quite intuitively by observing the fact that traffic is flowing more freely.
Figure 1: Evolutionary Strategy ( © Hoare & Penner)
Figure 2: Fitness function for sequence evaluation where denotes w total waiting time and d denotes total driving time for car i. ( © Hoare & Penner)
Effectiveness of GA Approach in Different Situations
The result of using the GA approach has been quite successful with SuRJE reducing waiting times for different kinds of roads.
Figure 3: Improvement in fitness over 130 generations for a simple alley ( © Hoare & Penner)
The graph above shows how after 130 generations there is an improvement of 59% in the fitness of the solution.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 4: Improvement in fitness over 200 generations for a boulevard. ( © Hoare & Penner)
This second graph is for a more complex scenario (a boulevard).The roads curve, the intersections are not all the same and traffic can make a wider variety of choices . 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.
Conclusions and Future Applications
The use of an evolutionary strategy to optimize traffic light timings has been shown to be effective. 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 travellers 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.
Back to EA In Action.