4. Control algorithm

Dynamic Programming is well suited for controlling the system described. Its upper bound of complexity is exponential, though mostly the bound is not met.

4.1 Basic ideas, Dynamic Programming and implementation for traffic lights

Each state of the finite state machine is called a node K in the tree of Dynamic Programming. At the very beginning the state is all lights red and all queues empty; it is called the root node. The following 5 conditions must apply [4]:

1. There has to be defined a Generating Rule g(K). The function g determines all nodes which can follow directly after K: g(K) = {g1(K),…,gn(K)}. Note that the time is not relevant for this rule, except for laying down the order of states.

The Generating Rule follows directly from the state diagram of the crossing. Remember the grid-like graph mentioned; it defines all states. Later when looking at coupled crossings, there will be additional constraints for the transitions because blocking the crossing by customers is forbidden.

2. There must exist a Generating Strategy G telling at what point of time g(K) should be applied, i.e. when the next nodes have to be generated.

It is never smart to break up a queue of customers. Thus we formulate the Generating Strategy as follows: Stay as long green as the queue is not yet empty, never break up a queue. Then allow other green states to follow.

3. There must be a Cost Function c(K) describing the costs for node K. The Cost Function must be additive [2], the costs of a following node must result from an addition of costs of the last node with some increment: c(gi(K)) = c(K) + D K® gi(K)c.

The costs of the final node must be minimized, either being the waiting or throughput.

4. There must exist a Comparison Condition V which determines whether two nodes KA and KB are comparable or not: (KA, KB) Î V or not?
5. And finally there must be a Comparison Rule "=" for comparable states KA and KB, as usual: is c(KA) = c(KB)?

The system is represented by an n-dimensional, non-intersecting graph[3], n being the number of approaches. Both Comparability and Comparison Rule can be stated with the following proposition:

Proposition: Two paths through the n-dimensional grid can be compared when they come across the same node and if they leave the node in the same direction. The only node excluded from the direction condition is the last node not being left any more. For the throughput as objective, the path with the least duration up to a compared node is better; otherwise the path is worse. For the waiting time as objective, the path having less waiting time accumulated and needing less time to reach the node is better; otherwise no conclusion can be drawn.

Idea for the proof: If one path is better than the other path it must be clear that the better path never can be overtaken by the path identified as worse; then Dynamic Programming can be used.

Proof (throughput): Remember the visualization of the customers by marked intervals (figure 6), as by sticks. To let them drive over the crossing means to arrange the sticks in a non-conflicting way. Being at the same node in the graph implies that the same amount of sticks has been arranged for every approach, thus the number of sticks remaining is equal as well. The path looking into the same direction means that the starting conditions for further search are equal, that there are no more somehow hidden intermediate times.

For arranging the remaining sticks there is an optimal solution with respect to processing time; when starting arranging earlier, it is not possible to finish arranging later because one could simply wait until the starting time of the better solution reaches the starting time of the worse solution, and then apply the optimal solution thus, and reach an equally good solution.

Proof (waiting time): Accumulating less waiting time can happen at the cost of needing more time for doing it (refer to section 2.4); being later means to be later, too, starting to arrange the remaining sticks; being later yields more distance used to move the sticks; due to the moving distance dependency of accumulated waiting time, it follows that more waiting time (or at least equally much) will be accumulated for the remaining sticks. If less waiting time is accumulated and the point of time is earlier, then the final point of time won’t be later (as proven just before), moving the sticks not so far, and accumulating less waiting time.

The Generating Strategy (2.) makes the problem easier to handle in its complexity by limiting the number of states to calculate explicitly. The Cost Function (3.) makes the solutions comparable. The Comparability Rule (4.) finds equal states, reached on different paths but being in fact the same states. If a node is reached on different paths, the more expensive paths are crossed out.

At the end only one path remains because there is only one final state (all customers being processed). If the Comparison Rule is weakened from "=" to "<", several paths from the root to the final state remain because equally good paths wouldn’t be dropped out as we did.

4.2 Practical aspects

Due to the Generating Strategy paths might have few bends. When two paths stop at the same node in the grid (to follow a bend) they can be compared, sure. But it is possible to compare them between the stopping points, too:

• Two paths are crossing each other (see figure 12). At the crossing point path A can do an experiment whether it would be better than path B when following B after the crossing point. If yes, path A is better than path B, otherwise no conclusion is possible. But bending path A contradicts the Generating Strategy. Therefore it is not optimal. Consequently both, path B and the (experimental) bent path A, being better, cannot be a part of the optimal path. Of course the same experiment is possible for path B trying to follow path A.
• When paths are in a cube or in a hyper-cube with more than 3 dimensions they can be skew. But they can be compared, too, at the points with the least distance to each other.

The algorithm should be implemented as a Depth First Search (DFS) following a path, once begun, until its end; the final state will be reached very soon by some paths, but they might be cancelled later on. An advantage of the DFS implementation is that we can obtain very quickly a bound for the objective (following a reasonable path) and then apply Branch and Bound in addition to Dynamic Programming. A bound is useful for nodes "in the periphery" of the n-dimensional cube, because these nodes do not have so much other paths to be compared with as paths in the center of the cube.

Figure 13: skew paths

4.3 Coupled crossings

Coupling crossings extends the Generating Strategy. The Generating Strategy for one crossing is as follows:

• light A stays green until queue A is empty,
• B is green until B empty.

Figure 14: extension to 2 crossings

Now, two crossings are coupled. If the queue in front of light C increases too much, crossing (A,B) is blocked; therefore light A is forced by light C to switch to red. Or light A itself can force light C to switch to green to let pass the arriving traffic and not to block crossing (A,B). Or finally light C wants to switch to green and asks A to send customers. The modified Generating Strategy looks as follows:

• light A is green until queue A is empty or blocked by queue C,
• B is green until B empty or A polled by C,
• C is green until C empty,
• D is green until D empty or C forced by A.

Although the number of states is not reduced (it is still the shuffle product of the states of both crossings), the number of transitions is reduced.

4.4 Combined phases

Real crossings are complex, often there are combined phases; right or left turns are combined with straight ahead traffic, and customers circulate in both directions. This influences the path through the grid. Suppose phase A can exist alone or in combination with phase B. Combining A and B equals to moving diagonally through the grid. It is possible as well that the bending point is not on a node of the grid, when B gets green during a manoeuvre of a car on side A (shown by the dashed path in figure 15).

4.5 Saturated system

A system is called saturated if not all customers waiting in the queue can pass the crossing within one phase. Without constraints for maximal green durations saturation is not possible, as we assume that the system is stable. There are different constraints for a crossing:

• Maximal phase duration: For a certain phase (or for all of them) it is allowed to define a maximal green duration after which another approach road has to be given green to. It limits the algorithm to a sub-optimal solution, but the individual waiting times of the customers cannot increase arbitrarily.
• Fairness: Consider a car waiting in an alley crossed by several principal roads. The algorithm would look very seldom at the one single car in that little alley because doing so means loosing time by intermediate times. Thus the car waiting in the alley had to wait during quite a long time. Therefore justice-constraints can be introduced to force the algorithm after a certain time limit to process also little alleys. If there are several alleys, there can arise a waiting queue of phases to be processed next.

Both constraints lead to saturation. In a saturated system the algorithm bases its decisions not any more upon the waiting queues.

The system is called completely saturated if all waiting queues contribute to the saturation. The duration of the green phases is given thus, and the only influence on the length of one phase cycle is by the intermediate times. A phase cycle is a sequence of phases, starting and ending at the same phase, a steady state. The new problem can be stated as follows:

Given: a starting phase, a stopping phase and the phase durations (in the stationary case starting and stopping phase are equal).

Searched: the sequence of phases such that the time for one cycle is minimal.

The problem is known as the Travelling Salesman Problem (TSP) [1] in a complete graph formed by the phases being the nodes, and the intermediate times being the edges.

If the system is partially saturated the Travelling Salesman Problem has to be solved only with the participating queues. It can be due to some queues being empty, some queues not being handled during the next time, or if a comparison of two skew paths (as described in 4.2) shall be undertaken.

Finally also combined phase crossings can be treated, as the travelling salesman can visit several cities at the same time. The Travelling Salesman Problem itself is already NP complete and does not significantly increase in complexity.