Conflict detection
This document is a work in progress
Conflict detection is a process which enables figuring out if a timetable, comprised of many train paths, can be performed as planned.
If a train has to slow down because of another train, or undergoing work on rail infrastructure, these actors are in conflict, which causes the timetable to become impossible to perform.
Conflict detection relies on interlocking and signaling simulation to:
- figure out what each actor requires to perform its duty undisturbed
- detect conflicting requirements
This system has to:
- produce conflicts which can be linked back to a root cause
- operate in way that can be visualized and interpreted
- be scalable: it should work just as fast given a massive number of train paths to intersect
- enable threading new train paths into an existing timetable
The design of this system is guided by a number of constraints:
- it must not cause false-negatives: if no conflicts are detected, a multi-train simulation of the same timetable must not yield any slowdowns
- it cannot rely on data we do not have
- it has to enable later support of mobile block systems
- it has to rely on existing signaling and interlocking simulation
- it has to enable detecting conflicts regardless of the signaling system in use
- it has to support transitions between signaling systems
- it has to support conflicts between different signaling systems
Conflict theory
Conflict detection relies on an abstract model:
- objects where conflicts happen are resources
- resources are used by actors
- resource uses can be incompatible
- overlapping incompatible ressource uses generate a conflict
Actors
Actors are objects which cause resources to be used:
- train paths (or someone / something on the behalf of the train)
- planned infrastructure work
Resources
Resources have the following properties:
- can be used by actors
- have multiple states
- can only be in a single state at any given time
- may take time changing state
The current model only considers the following two resources:
- zones, which have one state per way to traverse it
- switches, which have one state per position
Station platforms could also be resources, which would enable modeling platform use conflicts: if two tracks share a tiny platform, it may not be allowed to use both sides of the platform at once.
Requirements and conflicts
A requirement describes what resource is needed by an actor, and when.
There are a few types of requirements:
- shareable: the resource is required to be in a given configuration, for a given time lapse. Other shareable requirements with the same configuration can stack up.
- exclusive: the resource is required to be in a given configuration, for a given actor, for a given time lapse. This requirement cannot be combined with others.
Conflicts are both real-life disturbances and the incompatible resource requirements which cause them. A disturbance is something that would cause a train to be unable to run as planned.
- route setup delays due to unavailable resources
- spacing conflicts due to a train catching up with another
These real-life issues can be linked to conflicts, which arise from incompatible resource requirements:
- an exclusive requirement overlaps another requirement
- a shareable requirements overlaps an incompatible requirement
- a resource does not have time to change state between non-overlapping, yet close, requirements
For example, there are no conflicts when:
- a resource has non-overlapping exclusive requirements
- a resource is shared by requirements which require the same configuration
Generating requirements
For conflict detection to work, resource requirements have to strictly match what’s required to garantee that a simulated train will not be disturbed.
Routing requirements
For a train to be routed across rail infrastructure without any trouble, some resources have to be available for routes to set in time. A route does not set in time if a train is disturbed by a route being set too late.
A route might be set too late for a couple of reasons:
- one of the zones required may be unavailable
- a switch may be unavailable, or still moving
Routing requirements are generated by the following algorithm:
- compute a route calling timeline, so that the train never slows down due to late route setting. It can be done by finding when the driver would be constrained by signaling, and using that minus an allowance as the deadline.
- for each zone in each route, simulate when it would be released, and thus not required anymore
- use the route calling deadline as the requirement start time for each zone, and the release time as the requirement end. It is a shareable requirement. Switch requirements use the same time bounds.
Implementing route overlaps alternatives would require a richer model for requirements, such as a hierarchy and alternatives
Spacing requirements
Trains can also be slowed down by catching up with another train. When this happens, signaling forces the following train to slow down, or even stop if the train being followed does not clear the way fast enough.
These slowdowns are conflicts, and thus need to be avoided by emitting sufficient requirements.
At any time, exclusive requirements are emitted for zones which if occupied, would trigger a slowdown
These requirements are emitted as follows:
- the route calling timeline is followed
- every time the driver sees a signal:
- start by assuming routes reserved for routing should be reserved for spacing as well
- until the driver sees a signal which would cause a slowdown:
- attempt to make the last reserved zone occupied by a virtual train
- if the signal now causes a slowdown, the currently reserved zones are correct, continue to the next signal
- if not, unreserve the last zone of the path