5. ALGORITHM

It can be shown (Riedel, 1991; Riedel and Brunner, 1992) that generally for an optimal decision the controller must know all future events (arrivals of customers); i.e. an optimal controller is non-causal. However, it is sufficient in practice to guess the future events by an estimator. The estimator receives messages from detectors (which are mounted in good distance from the intersection) when customers are about to pass the intersection. Detectors should be reliable, redundant detectors are recommended. The more detectors and the farther they are, the better the estimate of the future is. Estimation issues are investigated in details in (Wirth, 1992).

For finding the optimum Dynamic Programming is used. Its complexity is exponential, though often this worst case does not happen. If the algorithm does not stop before reaching the end of the estimated data (i.e. the optimal signal switching sequence is not found), the problem becomes a Finite Time Horizon optimisation and thus its result is sub-optimal.

5.1 Basic ideas and Dynamic Programming

Each state 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 hold (Riedel, 1991):

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)}. Time is not relevant for this rule.

The Generating Rule follows directly from the state diagram of the intersection. Remember the grid-like graph mentioned; it defines all states. When looking at coupled intersections, there will be additional constraints for the transitions because blocking the intersection 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 (Bertsekas, 1987), 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) + DK®gi(K)c.

The costs (being the global waiting time) of the final node must be minimised.

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 (Läuchli, 1991), 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. (This condition obviously does not apply for the last node not.) 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 outperformed by the path identified as worse; then Dynamic Programming can be used. This can be shown for both objectives: throughput and waiting time (Riedel, 1991; Riedel and Brunner, 1992).

The Generating Strategy (2.) makes the problem easier to handle in its complexity by limiting the number of states to be calculated 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.

5.2 Practical aspects

Due to the Generating Strategy paths might have few bends (mostly for individual traffic). 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 Fig. 12). At the crossing point path A can do an experiment: Would it 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 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 state space 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.

Crossing paths and skew paths.

Fig. 8. Crossing paths and skew paths.

The algorithm is implemented as 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 have only a few other paths to be compared with as paths in the center of the cube.

5.3 Coupled intersections

Coupling intersections extends the Generating Strategy. The Generating Strategy for one intersection is as follows:

light A stays green until queue A is empty,

B is green until B empty.

Extension to 2 intersections.

Fig. 9. Extension to 2 intersections.

Now, two intersections are coupled. If the queue in front of light C increases too much, intersection (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 intersection (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.