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

(Version: 1)

Due Date: Thu, Mar 28, 2024, 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 - 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.

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.

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.

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.

Demo and Submission

We will be scheduling a demo with each group on the assignment due date. Besides the demo, your readable and documented source code should be in your repository at https://git.uwaterloo.ca. The repository must be set to 'Private' with instructor and TAs added as 'Reporter'. Your repo should include a README-TC2 file, which describes how to make and operate your program. Each group should be working from a single repository.

Each group should submit a single PDF file into the TC2 dropbox for this course in Learn. The PDF should include the following information:

  1. The names, userids, and student IDs of your group members.
  2. The name of your group's code repository on git.uwaterloo.ca and the SHA of the commit that we should be using for this assignment. The commit must be dated before the assignment deadline.
  3. A description of your work for this assignment. It should explain how you route the train, and how you get the train to stop at a target location. It should describe how you are modeling the train, including a description of any calibration data you have collected for modeling, and a description of how it was collected. Finally, it should describe how your train control system is implemented. In particular, it should describe the purpose and design of any tasks that are running, and their priorities. If you have made any modifications to your kernel to support TC2, explain those as well.
  4. Your raw calibration data should be stored in a subdirectory in your code repository. Please identify the subdirectory in your documentation.