CS 452/652 Fall 2019 - Lecture 28

November 13, 2019 prev next

thought experiment... what would an ideal solution be?
need exact problem specification, example:
- given a topology, a set of trains, and a list of destinations for each train
  → determine optimal schedule
- but: what is optimal?
  - time to last train at last destination?
  - average trip duration?
  - many other criteria possible
- also: assume error-free operation
with exact problem specification
- formulate and solve optimization problem - computational complexity
- use formal heuristics to reduce complexity
- or: design ad-hoc solution accommodate uncertainty (our approach)
our goal is not overall perfection (which is not even properly specified), but:
- build interesting multi-task, real-time application
- model decentralized aspects of real-world system

reservation server
- continuous reservations (no leapfrogging)
- reservation interface: train, segment → accepted
- query interface: segment → train
sensor server
- check for existing reservation → notify train task
- else: error handling
route server
- determine path & feasibility (e.g. short move?)
- compute only for slow/stopped trains? offload with lower priority
train task
- report source/dest -> obtain route from route server
- drive train
  - reserve (reserve beyond error branches)
    - no reservation possible: slow/stop
    - reservation invariant: reservation time/distance > stop time/distance
  - release track segments
    - leave segment → release segment
    - pass switch → release error path
    - stop → release rest of path
    - periodic or sensor-based updates
  - switch reserved turnouts
  - handle sensor, timeout notifications
refinement: route server → travel planner
- travel plan = path + timing
- advanced conflict resolution (in time and space)
  - move conflict location by requesting different speeds
  - find cheap alternative path for (new) conflict location
  - computational overhead with more trains?
refinement: asynchronous train task notification
- travel planer notifies running train about speed/route change
- only for non-reserved portions of the path!
reservation server and route server / travel planner could potentially be merged
but it seems cleaner and simpler to implement as two different servers