Genetic Programming Applied to Traffic Control

The goal in our project was to generate creatures that controlled traffic signals in a way that let traffic efficiently pass through a small network of streets. Specifically, we measured the performance of each creature through the use of a traffic simulator, provided by FHWA, the funding agent for the research. The simulator used the individual creature to control the traffic signals in the network for, usually, 30 minutes of simulation time. At the end of this run, statistics produced by the simulator were used to assign a ranking to the creature. For our final implementatin, we attempted to maximize the statistic

This statistic provides a tradeoff between efficiency and equity, weighting the average delay for the heavily traveled approaches more but still ensuring that the lightly traveled intersections are not excessively delayed.

In order to implement signal control through GPs, we first had to develop a set of functions that GP creatures could use in order to access information about intersection conditions. Below is a table of the most common functions we implemented and used.

FunctionDescriptionResult Type
QUEUE_FULLIs the traffic backed up to the sensors?boolean
WAITINGIs a car waiting at the intersection?boolean
TIME_SINCE_CHANGEHow many seconds ago was the light last changed?integer
APPROACHINGIs a car current approaching the intersection?boolean
CONSTANT_XGet the value of the constant X for the current signal and the current active streetinteger

 

Of course, one issue with this structure is, how do you refer to individual streets? The creature is being executed on the entire intersection at once. To this end, we use two addition functions STOPPED and MOVING that allow the GP to refer to the approaches to the intersection that either have a red light or a green light (respectively). Functions like QUEUE_FULL take in either STOPPED or MOVING as an argument, to specify which streets the QUEUE_FULL function should examine. For example, if the north-south streets are green, and the west-east streets are red, when a GP creature executes a (WAITING STOPPED), it will return back true if either the west or eastbound streets have a car waiting.

In addition to the functions, we also gave the GP creatures the ability to create and learn constants. These constants could be used in the a creature's execution as threshold values. However, since only one creature was being executed on each of the intersections, it made sense to make a new constant representation that allowed for the constant to take different values, depending on which intersection was being examined, and which streets were active.

For example, CONSTANT_1, might evaluate to 10, when the creature was considering intersection 1, with the north-south streets moving, but it might evaluate to 23, when considering intersection 2, with the east-west moving. In this way, the same creature can act slightly different based on the constants it had for the individual intersections, due to the varying traffic flows at each intersection. So, if intersection 2 had a lot of east-west traffic, it might have constant that says it should allow 20 seconds of green light time for the east-west street. However, if intersection 1 had a small amount of east-west traffic, it might use a smaller constant. See the demonstrations for the interesting ways the constants were used by the genetic creatures.

We represented the creatures as rooted trees that returned true or false, based on whether or not the creature wished to change the traffic signal it has just examined. The tree was made up of boolean combinations of the above functions, along with two constants. These creatures were used to control the traffic in the following manner: At every one second interval in simulation time, the traffic simulator would execute the given control creature once for each intersection in the network. When it executed a creature on a given intersection, the simulator provided the current status of that intersection through the accessory functions, such as QUEUE_FULL and WAITING. If the creature returned true for an intersection, the simulator would change the traffic signal, so that after 5 seconds of amber time, the red light would change to green. After having done this for each of the intersections, the simulation continued. After thirty minutes of simulation time was up, the simulator collected all the important statistics and used them to assign a ranking to the creature.

One important point to make is that the creature is being executed for each intersection every second. How this creature performs for one intersection affects the traffic flow of the other intersections. Because we are jointly evolving behaviors for the intersections such that the aggregate behavior of the network is optimized, this is an example of evolution of cooperative behavior. This is an area of research in the field of Artificial Life. Coordination between the signals (where downstream signals exploit the fact that the upstream signals put the vehicles into clusters) is evident in one of the demonstrations.