CS 452/652 Fall 2023 - Train Control (Part 2)

(Version: 1)

Due Date: Wed, Nov 22, 2023, 8:30am

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 - that is, try to find a fast route and traverse it quickly.

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 space of routes considered by your route finder should include 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

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

Train collisions should be avoided. 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

We will be scheduling a demo with each group on or near the assignment due date. Your demonstration should show that trains can be routed and moved successfully even in the presence of (at least) a single sensor error. It should also show 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 likely 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

Besides the demo, you should submit a PDF document to the TC2 dropbox on Learn before the assignment deadline. Documents are due by the deadline, regardless of when your demo is scheduled. The document should include:
  1. The names and student IDs of your group members.
  2. The name of your group's code repository in GitLab (git.uwaterloo.ca), readable by the TAs and instructor, containing the source code of your assignment. Your repository should include a README file that describes how to build and run your code.
  3. The commit SHA for the repository commit that you will demo, and that we can review. The commit must have been created before the assignment deadline.
  4. A description of your work for this assignment. It should explain how you route trains, how you handle sensor attribution, and how you manage track reservations and otherwise prevent trains from colliding. You should describe any predictive models that you have created, and how they are used for train control.