CS 452/652 Winter 2022 - Train Control (Part 2)

(Version: 1)

Demo Date: Wed, Mar 23, 2022 (submit code & documentation at 9:00am)

Introduction

The traffic control milestones each require a capability that is likely to be useful for almost any project. The second milestone is concerned with driving multiple trains at the same time while avoiding collisions. Trips should be completed as fast as possible (speed, path).

Description

Sharing the track is accomplished by moving the trains so that if they use the same section of track, they do so at different times. This is a real-time problem because arriving too early is as serious a problem as arriving too late. In this milestone, you are required to add two features to the user interface you created for TC1:
  1. Your interface should show the current destination of each train.
  2. The user should be able to give a train a new destination, to which the train must move.
This milestone is usually accomplished by adding the following capabilities to your implementation.

Route Finding

You must implement route finding, which provides a train with a route to a given destination. The route finder should also find routes that require the train to change direction. There are many more routes including direction changes than there are without, which is important to you for two reasons. When you include the possibility of a direction change, you can often find a much shorter route to a destination. With shorter routes, multiple trains have a higher chance for fewer overlapping sections in the their routing.

Sensor Attribution

You must implement sensor attribution. When two or more trains are moving simultaneously, each sensor report is either spurious or caused by one of the trains. Your implementation should consistently attribute sensor reports to the correct train.

Collision Avoidance

You must implement collision avoidance. This requires you to define a policy that makes it impossible for two trains to occupy the same location at the same time, and to implement your policy. You can avoid collisions in the time domain (slowing, pausing) and/or space domain (alternative path). However, trivial non-collision algorithms, such as only running one train at a time, are not acceptable.

Robustness

Your application is expected to be robust against a 'reasonable' level of errors in sensor reports and changes in the state of the turn-outs. In addition, it should avoid typical problems, such as switching a turnout while a train is passing. The route finder should be able to respond to changes in track configuration caused by unavailability of track segments. Train control should drive a train fast enough to not get stuck.

Demo

For the demo create an application that demonstrates the success of sensor attribution in the presence of single errors, and that two trains that attempt to use the same track at the same time are prevented from doing so.

The gold standard has multiple trains on the track. Whenever a train stops at its destination it receives or generates a new destination at random. The program should run for several minutes without breaking.

A good starting point might be two trains in the same loop that follow each other while keeping a minimum distance.

Notes

  1. You may find that creating a track server, which maintains the current state of the track, including reservations, and which answers questions about the track from other components, is an effective way of minimizing communication overhead.
  2. During the demo you are certain to be asked what parts of the track are reserved. Putting reservations into your display of the track status is a good idea, and might well reduce debugging time.
  3. When considering design choices or trade-offs, keep in mind the overall optimization criterion that trips should be completed as fast as possible.
  4. On possible implementation strategy starts conservatively, making generous track reservations. You will probably notice that the more conservative the reservation system, the more time the trains spend motionless. When you think things are robust you can then make your reservations more aggressive and get better performance.

Hand In

Hand in the following, nicely formatted and printed.
  1. A pointer to your code repository, readable by the TAs and instructor, containing the source code of your assignment, instructions how to make the executable, and documentation (see below). The code and documentation must remain unmodified after submission until the assignments have been marked. Email the commit SHA to the instructor before the deadline.
  2. A description of how to access, make, and operate your program in a README file, including the full pathname of your executable file, which we might download for testing.
  3. The names of your group members in the same README file.
  4. A description of the structure of your kernel and application so far, highlighting the changes for this assignment. We will judge your application primarily on the basis of this description. Describe which algorithms and data structures you used and why you chose them.
  5. Note that we might perform another round of code reviews. A TA and/or instructor might contact you to set up a (virtual) meeting.