4. 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). However, it is sufficient in practice to guess the future events by an estimator. The estimator receives messages from detectors when customers are about to pass the crossing. It is noted that only in absence of measuring noise and detector failures the sensor readings report accurately the input events.

For finding the optimum, Dynamic Programming (Bertsekas, 1987) 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, the problem becomes a Finite Time Horizon optimisation and thus its result is sub-optimal.

Each state is called a node K in the tree of Dynamic Programming. At the very beginning the state is all lights red; it is called the root node. The following 5 conditions must hold (Riedel, 1991):

  1. There has to be a Generating Rule g(K). Time is not relevant for this rule. It follows directly from the state diagram of the crossing.
  2. There must exist a Generating Strategy G discretising the timed state space. Only points in time are considered where a decision of the controller is required. The simplest strategy is: it is never smart to break up a queue of customers.
  3. There must be a Cost Function c(K) describing the costs for node K. The Cost Function must increase from step to step. The costs of the final node are to be minimised.
  4. There must exist a Comparison Condition V which determines whether two nodes are comparable or not. It forces the Dynamic Programming tree to follow the state-grid of the crossing.
  5. And finally there must be a Comparison Rule for comparable states to determine the better path.

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 as follows: 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 (except the last node). 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 (Riedel, 1991).