Scheduling with NetLogo
The idea for this project was hatched during a brainstorming session with Michelle Hutton, Computer Science Teacher at the Girls’ Middle School in Mountain View (where I am volunteering as a teaching assistant). While we pondered the content and form of the next unit, I proposed that we present the core computer science concept of scheduling using a local intersection as a metaphor. Fundamentally, the objective of scheduling is the equitable allocation of scarce resources for use by a set of pending tasks. In the case of an intersection, the scarce resource is the shared road space, while the pending tasks are the crossings of vehicles and pedestrians. The traffic light, then, is responsible for the scheduling algorithm governing the space.
We conceived of students learning about scheduling by way of observing and attempting to model typical scenarios at their local intersection. Furthermore, we wished to provide a mechanism by which students could implement scheduling algorithms to govern the intersection as they deemed appropriate. NetLogo appeared to be a perfect technology for integrating the configuration of testable traffic scenarios, implementing scheduling algorithms, and providing a visual representation that would encourage exploration and experimentation. By encouraging interaction with such a model, we hope to engender not only an understanding of scheduling, but, more importantly, the realization that values and preferences can be (and are) encoded in perfunctory yet powerful pieces of technology (i.e. the traffic light).
The intersection of focus is that of Central Expressway and Rengstorff Avenue in Mountain View. In addition to the typical four directions of traffic, a railway line crosses Rengstorff just to the West of the intersection. The train adds an additional layer of complexity to the scheduling behavior of the traffic light, one which we wanted the students to both model and account for in their algorithms. Below is a screenshot of the model interface next to a satellite-based rendering of the actual intersection:
The model consists of a simplified, normalized version of the Rengstorff x Central Expressway intersection. Although the number of lanes is reduced to one in each direction, additional characteristics remain, including the train and tracks, pedestrians and crosswalks, cars, trucks, emergency vehicles, traffic lights, railroad crossing guards, traffic sensors, and emergency vehicle sensors. The following aspects of the model are configurable:
Charts of maximum, minimum, and average wait time for vehicles and pedestrians are also provided:
The vehicles and pedestrians in the model are created with random speeds (within a range). They attempt to cross the intersection and exit the opposite side of the screen, but are constrained by rail-road crossing guards (which prevent crossing the tracks when a train is on screen), the tracks themselves if another vehicle is stopped directly on the other side, red traffic lights, the intersection itself if another vehicle is stopped directly on the other side, and vehicles directly in front of them. Packaged with the model is a simplistic round-robin traffic light scheduling algorithm. This algorithm cycles through the three traffic directions (North-South, East-West, and Pedestrian), giving them each an equal time slice as configured by the user.
There are two complementary behaviors encouraged by the model. The first is to explore the ramifications of the configurable parameters with respect to the scheduling algorithm. The hope here is to encourage the discovery of emergent phenomena within this system of independent actors. The second is to write more intelligent scheduling algorithms to maximize vehicle and pedestrian throughput (and safety). Presumably, these algorithms would avail of the various sensors provided, such as vehicle sensors at the edge of intersections, emergency vehicle sensors further down the road, pedestrian crosswalk sensors, and train sensors.
In the spirit of exploring emergent behavior, I ran two rounds of BehaviorSpace automated testing to explore the effect of changing just the green traffic light duration in a standard simulation with a high train frequency. The results were surprising. Indeed, I do not fully understand the results (the patterns of which were consistent across test runs). Here are charts of the average and maximum wait times for these sessions:
The dips in maximum wait time for 200 and 400 tick green light durations, relative to test runs where the durations are 100, 300, and 500 suggest either emergent behavior or an idiosyncrasy of my model that is exposed by this level of testing. Although I can’t explain the pattern, the fact that BehaviorSpace can be used to rapidly expose these results will be instrumental in both my understanding and further refinement of the code.
On Monday, May 3, I engaged in a more qualitative form of testing by introducing the model to three sections of eighth grade computer science at the Girls’ Middle School (in the context of the unit described above). The reception ranged from neutral to quite positive. Some students wondered how long it took to make, while others commented on how “cute” the pedestrian schoolchildren and the train were. Students found (or were prompted by me to find) the 3-D rendering, and became further excited. The 3-D view gives a feel for individual interactions while the top-level view reveals system dynamics. Both seemed to be of interest to the students. I asked them for suggestions for improvements and received the following (mostly from Carly): control over pedestrian speed, smaller train guard window, control over pedestrian light time, sports cars, and the ability to make cars crash. I encouraged them to play with the model over the next week, and consider how they might design a smarter traffic light. In the meantime, I will update the model to accommodate some of their wishes, and prepare instructions to scaffold their code-based scheduling algorithm additions.
The project can be found here