CS 177 CSIM Programming Project -- Part 1

Modeling Cars on a Roadway

DUE DATE: FRIDAY, FEB XX, 2016 in LAB

In this section of the project, every student must work independently, including writing their own code, running their own experiments, and documenting the results. However, I will allow students to form teams to carry out later parts of the project.

The goal of this part of the project is to build the first stage of a CSIM model of cars traveling along a section of roadway. In this case, your program is a caricature of people driving in circles around the Ontario airport until they can pick up their arriving passengers from the loading zone along the curb directly in front of the airport terminal building. Drivers don't want to take the time and effort (or spend the money!) to leave their cars in the parking lot and walk to the terminal to meet the passenger. Moreover, it is illegal to park your car at the curb and wait for your passenger to come out of the terminal building. "This area is for immediate loading and unloading only!" Thus, a common strategy is just to drive around the outside of the main parking lot between visits to the terminal entrance, until one time you see your passenger standing at the curb and stop to pick him up.

There is also an alternative strategy (much preferred by the airport management), where drivers park for free in a distant "cell phone lot" until their passenger calls from the curb to request a pickup. The question is this. If saving time (valued at $50 per hour) and gas money (valued at $0.01 per "cell") are both important, should the driver park in the "cell phone lot" or simply drive in circles? Furthermore, if the driver knows approximately when his passenger will reach the curb, should he wait for the call or leave the cell phone lot early?

Experiments

In later weeks, you will add more features to your simulator and run more experiments. For Part 1 (due on Feb XX) you are only responsible for completing only the following.
  1. Demonstrate car movement without crashes. Begin your experiments by testing a simplified version of the program. In this case, make every car a "zombie driver", so nobody ever tries to enter or leave the roadway. Start with one zombie and show that it go around the loop multiple times without being blocked from entering an already-reserved cell. Now increase the number of zombies and show that they can go around the loop together without crashing. Measure the throughput (number of trips completed around the loop per hour) as a function of the number of zombies and find its maximum. What happens at "rush hour" when the roadway is (almost) completely filled with zombie cars?
  2. What happens when you add a single traffic light? Repeat experiment 1 when cells 118 amd 119 represent a pedestrian cross-walk controlled by a traffic light (described below).
Reference Material about the Model Specifications

Representation of the Roadway

For this assignment, the roadway is just a one-way "loop" that carries a single lane of traffic around a circle in front of the airport terminal. (This means you cannot pass the car in front of you, even if its speed is below your own target.)

The roadway will be modelled by a linear sequence of discrete "cells", each representing a short segment of road (11 feet long, say) that is half the length of a car. The entire roadway is a loop with exactly 120 cells, and represents a distance of exactly 1/4 mile. For now, we will assume that "zombie" cars simply drive around in a circle forever, without ever trying to enter or leave it.

Low-level functions describing how cars move along the Roadway

A stopped car occupies two consecutive cells, whereas we say that a moving car occupies three cells at a time to account for the two partially-occupied cells from which the car's tail of the car is leaving and its nose is entering. To make sure that only one car at a time can occupy a particular cell, we will represent them as individual CSIM facilities.

For example, suppose cells are numbered 0, 1, 2, etc while cars are labelled A, B, C, etc. Initially, let's assume that both cars are stopped so that cells 2 and 3 reserved by car A, and cells 0 and 1 reserved by car B. In order for car A to start moving, it must immediately reserve cell 4, then after moving ahead by one cell, car A reserves cell 5 and immediately releases cell 2, and so on.

In order for prevent crashes, a moving car monitors the status of the roadway up to 4 car-lengths (or 8 cells) ahead of its current position, depending on its speed. To allow this, each car sets the following variables associated with each of its currently-reserved cells:
Cars always travel at constant speed for one car length, and then can increase their speed by one step when accelerating, or decrease their speed by up to 2 steps when stopping. Notice that the loop or roadway contains even numbers of cells, so cars always have the opportunity to stop or change speed at the edge of the pedestrian cross-walk.
 
At the beginning of the model, and any time a car is waiting car at the cross-walk for the traffic light to turn green, its current speed will be zero. However, as soon as the car has permission to move forward, it will try to adjust its current speed to match its target speed as quickly as possible, with the following exceptions. First, the car may be forced to slow down or stop to avoid hitting the car in front of it. Second, the car must avoid entering the cross-walk when the traffic light is red.

Cars Accelerating

To accelerate from speed=0 to speed=5, a car needs 6.5 seconds and advances by 9 cells, as shown below for car A in the example below, where initially car A is occupying cells 2 and 3, with car B behind it occupying cells 0 and 1:

Time
 Reserve
 Set
 Clear and Release
0
 cell 4
 cell 2: speed=1, exit time=1.5
1.5
 cell 5
 cell 3: speed=1, exit time=3
 cell 2
3
 cell 6
 cell 4: speed=2, exit time=3+11/12 cell 3
3+11/12
 cell 7
 cell 5: speed=2, exit time=4+5/6 cell 4
4+5/6 cell 8
 cell 6: speed=3, exit time=5+1/3 cell 5
5+1/3 cell 9
 cell 7: speed=3, exit time=5+5/6 cell 6
5+5/6 cell 10
 cell 8: speed=4, exit time=6+1/6 cell 7
6+1/6 cell 11
 cell 9: speed=4, exit time=6+1/2 cell 8
6+1/2 cell 12
 cell 10: speed=5, exit time=6+3/4 cell 9


Notice that the nose of car A has advanced from cell 3 to cell 12 and it is now moving at its maximum speed.
staircase chart showing movement of 2 cars

Figure 1 shows a plot of occupied cells by cars A and B as a function of time, assuming the initial conditions consist of car A stopped in cells 2 and 3, and car B stopped in cells 0 and 1, wishing to start accelerating at time 0 seconds. (The full details of the calculation are can be found in the following MS Excel spreadsheet.) Notice that car B does not begin moving until car A has moved far enough to leave two unoccupied cells between the two cars because a moving car cannot change its speed until it has advanced by one car length (or two cells). Thus, the actions of car B trail the corresponding actions of car A by 3 seconds, which results in a gap of 5.5 car lengths (or 11 cells) when both cars have attained speed=5.

Cars Slowing Down and Stopping

While a car is slowing down, its speed can drop by up to two steps when it crosses the next car-length boundary. Therefore, a car moving at speed=5 needs only 4 seconds to stop and advances by 4 cells, since it can jump directly to speed =3 for one car length and then to speed=1 for one car length before has stopped completely.

The effect of different initial speeds is shown below in Figure 2. In most cases, stops from lower speeds take less time and distance. However, the figure also includes the effect of a one-second reaction time -- which can sometimes delay the onset of braking for more than one second because speed changes can only occur once per car length (or once every second cell). The assumption of a one second reaction time is a pretty standard for modeling drivers, for example see: http://www.visualexpert.com/Resources/reactiontime.html
After 1 second reaction time, stops from higher speeds take longer.

Look-Ahead to Avoid Crashing

If the car detects an obstruction (i.e., a slower moving, or stopped, car) within its monitoring range, the car continues at its present speed for 1 second to allow for the driver's reaction time, then reduces its speed as it crosses the next car-length boundary. Note that the car only experiences a single reaction-time delay per slow-down event, since the driver should be paying close(r) attention to the situation after seeing a potential traffic hazard ahead. The new speed is set to the maximum of: (a) two steps below its current speed, or (b) the speed of the car ahead.

Including the effect of a one-second reaction time, Figure 2 shows that a car moving at speed 5 requires 5 seconds and 3.5 car lengths to stop.Thus, we should be able to avoid crashes with a monitoring range of 4 car lengths at speed 5. On the other hand, if the car is moving at speed 4, then we see that the stop only requires about 3.2 seconds and 2.5 car lengths, so a monitoring range of 3 car lengths is sufficient. Similarly, a car moving at speed 2 or 3 can use a monitoring range of 2 car lengths because stopping from speed 3 requires 4 seconds and 1.5 car lengths, and stopping from speed 2 requires 2.75 seconds and 1 car length.

Cars moving at speed 1 are treated as a special case where we will use a monitoring range of 1 car length. This is sufficient to avoid crashes, since a car moving at speed 1 can stop in exactly 3 seconds and 1 car length. It also allows a line of stopped cars to begin moving as soon as the inter-car gap has reached one car length (see Figure 1).

High-level description of the actions/policies controlling each "Zombie Driver"

Each "zombie driver" simply attempts to drive around the loop continuously, and as close as possible to its target speed consistent with the two goals of:
  1. not crashing into the car in front (if any), and
  2. not entering the crosswalk when the traffic light is red.
The zombies serve two purposes. First, in Part 1 of the experiment they allow you to test whether cars can navigate the loop without crashing without worrying about the extra complications of regular cars having to enter/exit from the loop. Second, adding a few zombies into the mix of the regular drivers is an easy way to create some traffic congestion, forcing cars to travel slower than their target speed or to wait for traffic to clear before entering the roadway.

At the beginning of execution, all zombies are stopped in a row of consecutive cells, like the starting grid on a race track. (see below.) Thereafter, each zombie randomly chooses its target speed from {speed=2, speed=3, speed=4, speed=5] with equal probability, waits for a random time that is uniformly distributed between 1 and 2 minutes, and then makes another random speed choice. The "clock" for making speed changes runs continuously, whether or not the car is currently moving. Consider making the target speed for each under the control of a separate process, which updates a variable containing the speed limit for the associated car according to its update schedule. The car reads speed limit variable every time it reaches an even-cell boundary where it is allowed to modify its actual speed.

Initial Conditions

Assume that at time zero, all cars line up like race cars on the starting grid: the front car occupies cells 2n and 2n+1, the back car occupies cell 1 and 0, and cars move in the direction of increasing cell numbers. (Thus the group of cars does not encounter the traffic light until the end of its first ``lap'' of the course.)

Assume that the traffic light just turned green (for the cars) at time zero. Thereafter, it cycles through green/yellow/red
perios with the durations: