CSCI P545 Computer Science Department Indiana University Mon Mar 3 15:04:47 EST 2008 © [SDJ]

Island Tunnel Controller
Contents
[HTM] Problem Statement
[HTM] Modeling Requirements
[HTM] Sample Answer

Informal Description

This problem is a refinement of the standard Traffic Light Control problem and has also been compared to the Clayton Tunnel Disaster. It is a metaphor for coordinating access to a restricted resource. Concurrent entry/exit is allowed under certain conditions, represented by a one-lane tunnel between the Mainland and an Island that may at any time contain several vehicles. There is a bound on the number of vehicles that may be on the island.

We want to design a controller for the red (MR and IR) and green (MG and IG) traffic lights at the each end of this tunnel. There are four sensors for detecting the presence of vehicles: one at tunnel entrance on the island side (IE), one at tunnel exit on the island side (IX), one at tunnel entrance on the mainland side (ME), and one at tunnel exit on the mainland side (MX).

Environmental Properties

The controller design may assume the following constraints on its environment, described in terms of the behavior of vehicles that entering the system.
E1 The vehicle sensors are conditioned signals, that is, clean pulses of significant duration, which may also be assumed synchronous in clocked designs.
E2 Every vehicle that crosses a sensor is detected and every gap between vehicles that cross a sensor is detected.
E3 Vehicles going into the tunnel are detected before they reach the traffic light; vehicles leaving the tunnel are detected after they leave the single-lane portion of the roadway.
E4 Vehicles don't break down. They obey the traffic signals in finite time, and, if necessary, a bound may be placed on this time. Every vehicle that approaches the tunnel is committed to entering it.
E5 Having arrived on The Island every vehicle eventually tires to leave.

Design Properties

D1 Light Behavior. The traffic lights each follow a red, green, red, green,  . . .  sequence. For simplicity, it is assumed that all vehicles can react instananeously to a change in the traffic light, so that neither ``caution'' lights nor duration timers are required, although these may be added if desired. For this reason, additional system outputs MY and IY are provided but not required.
D2 Safety. At no time are there two vehicles in the tunnel that are traveling in opposite directions.
D3 Liveness. Any vehicle attempting to reach or leave the island eventually succeeds.
D4 Access. Traffic on the island is limited. Variants include:
(1) At no time are there more than 16 vehicles on the island.
(2) At no time are there more than N vehicles on the island, N a fixed but undetermined constant.
(3) The system strives to keep the number of vehicles on the island below n, a dynamically varying input.
D4 Single Controller. One may design a single controller for both the mainland and island entries. As a variation, one may optionally require seperate, asynchronous controllers at both ends of the tunnel, and impose constraints on communication bandwidth between them. However, under any such variation, the external signature (IE, IX, IR, (IY), IG, ME, MX, MR, (MY), MG)