This is the multi-page printable view of this section. Click here to print.
This module handles the search for solutions.
To reduce the problem to its simplest form and for easy and efficient testing, inputs and outputs are strongly simplified and abstracted.
To summarize its behavior: the solution space is described as a graph that encodes locations, time, and speed. A pathfinding is run on this graph to find a solution.
This graph could, in a way, be seen as a decision tree, but different paths can lead to the same node.
The first thing we need to define is how we move through the infrastructure, without dealing with conflicts yet.
We need a way to define and enumerate the different possible paths and explore the infrastructure graph, with several constraints:
To do this, we have defined the class InfraExplorer. It uses blocks
(sections from signal to signal) as a main subdivision.
It has 3 sections: the current block, predecessors, and a “lookahead”.
In this example, the green arrows are the predecessor blocks. What happens there is considered to be immutable.
The red arrow is the current block. This is where we run train and signaling simulations, and where we deal with conflicts.
The blue arrows are part of the lookahead. This section hasn’t
been simulated yet, its only purpose is to know in advance
where the train will go next. In this example, it would tell us
that the bottom right signal can be ignored entirely.
The top path is the path being currently evaluated.
The bottom section of the path will be evaluated in a different
and already instantiated InfraExplorer
The InfraExplorer is manipulated with two main functions
(the accessors have been removed here for clarity):
interface InfraExplorer {
/**
* Clone the current object and extend the lookahead by one route, for each route starting at
* the current end of the lookahead section. The current instance is not modified.
*/
fun cloneAndExtendLookahead(): Collection<InfraExplorer>
/**
* Move the current block by one, following the lookahead section. Can only be called when the
* lookahead isn't empty.
*/
fun moveForward(): InfraExplorer
}
cloneAndExtendLookahead() is the method that actually enumerates the
different paths, returning clones for each possibility.
It’s called when we need a more precise lookahead to properly identify
conflicts, or when it’s empty and we need to move forward.
A variation of this class can also keep track of the train simulation
and time information (called InfraExplorerWithEnvelope).
This is the version that is actually used to explore the infrastructure.
Once we know what paths we can use, we need to know when they can actually be used.
The documentation of the conflict detection module explains how it’s done internally. Generally speaking, a train is in conflict when it has to slow down because of a signal. In our case, that means the solution would not be valid, we need to arrive later (or earlier) to see the signal when it’s not restrictive anymore.
The complex part is that we need to do the conflict detection incrementally Which means that:
For that to be possible, we need to know where the train will go after the section that is being simulated (see infra exploration: we need some elements in the lookahead section).
To handle it, the conflict detection module returns an error when more lookahead is required. When it happens we extend it by cloning the infra explorer objects.
The problem is still a pathfinding problem in a given graph. Once the problem is encoded as a graph search, it is possible to reuse our existing tools for this purpose.
We consider the product graph of position, time, and speed. This means that every graph element contains these 3 variables (among other things)
Every graph edge is computed using running-time calculation to get speed and positions as functions of time.
Space is encoded with a graph that contains the physical infrastructure.
It is then “duplicated” at different times.
The nodes are then linked together in a way that reflects travel time.
For example, with the following infrastructure, using the track graph:
Exploring the solution graph can give the following result:
When a new graph edge is visited, a simulation is run to evaluate its speed. But it is not possible to see beyond the current edge. This makes it difficult to compute braking curves, because they can span over several edges.
This example illustrates the problem: by default the first edge is explored by going at maximum speed. The destination is only visible once the second edge is visited, which doesn’t leave enough distance to stop.
To solve this problem, when an edge is generated with a discontinuity in the speed envelopes, the algorithm goes back over the previous edges to create new ones that include the decelerations.
To give a simplified example, on a path of 4 edges where the train can accelerate or decelerate by 10km/h per edge:
For the train to stop at the end of route 4, it must be at most at 10km/h at the end of edge 3. A new edge is then created on edge 3, which ends at 10km/h. A deceleration is computed backwards from the end of the edge back to the start, until the original curve is met (or the start of the edge).
In this example, the discontinuity has only been moved to the transition between edges 2 and 3. The process is then repeated on edge 2, which gives the following result:
Old edges are still present in the graph as they can lead to other solutions.
While exploring the graph, it is possible to end up in locations that would generate conflicts. They can be avoided by adding delay.
The departure time is defined as an interval in the module parameters:
the train can leave at a given time, or up to x seconds later.
Whenever possible, delay should be added by shifting the departure time.
for example : a train can leave between 10:00 et 11:00. Leaving at 10:00 would cause a conflict, the train actually needs to enter the destination station 15 minutes later. Making the train leave at 10:15 solves the problem.
In OSRD, this feature is handled by keeping track, for every edge, of the maximum duration by which we can delay the departure time. As long as this value is enough, conflicts are avoided this way.
This time shift is a value stored in every edge of the path. Once a path is found, the value is summed over the whole path. This is added to the departure time.
For example :
- a train leaves between 10:00 and 11:00. The initial maximum time shift is 1:00.
- At some point, an edge becomes unavailable 20 minutes after the train passage. The value is now at 20 for any edge accessed from here.
- The departure time is then delayed by 5 minutes to avoid a conflict. The maximum time shift value is now at 15 minutes.
- This process is applied until the destination is found, or until no more delay can be added this way.
Once the maximum delay is at 0, the delay needs to be added between two points of the path.
The idea is the same as the one used to fix speed discontinuities: new edges are created, replacing the previous ones. The new edges have an engineering allowance, to add the delay where it is possible.
computing an engineering allowance is a feature of the running-time calculation module. It adds a given delay between two points of a path, without affecting the speeds on the rest of the path.
We used to compute the engineering allowances during the graph exploration, but that process was far too expensive. We used to run binary searches on full simulations, which would sometimes go back for a long distance in the path.
What we actually need is to know whether an engineering allowance is possible without causing any conflict. We can use heuristics here, as long as we’re on the conservative side: we can’t say that it’s possible if it isn’t, but missing solutions with extremely tight allowances isn’t a bad thing in our use cases.
But this change means that, once the solution is found, we can’t simply concatenate the simulation results. We need to run a full simulation, with actual engineering allowances, that avoid any conflict. This step has been merged with the one described on the standard allowance page, which is now run even when no standard allowance have been set.
The STDCM module must be usable with standard allowances. The user can set an allowance value, expressed either as a function of the running time or the travelled distance. This time must be added to the running time, so that it arrives later compared to its fastest possible running time.
For example: the user can set a margin of 5 minutes per 100km. On a 42km long path that would take 10 minutes at best, the train should arrive 12 minutes and 6 seconds after leaving.
This can cause problems to detect conflicts, as an allowance would move the end of the train slot to a later time. The allowance must be considered when we compute conflicts as the graph is explored.
The allowance must also follow the MARECO model: the extra time isn’t added evenly over the whole path, it is computed in a way that requires knowing the whole path. This is done to optimize the energy used by the train.
The main implication of the standard allowance is during the graph exploration, when we identify conflicts. It means that we need to scale down the speeds. We still need to compute the maximum speed simulations (as they define the extra time), but when identifying at which time we see a given signal, all speeds and times are scaled.
This process is not exact. It doesn’t properly account for the way the allowance is applied (especially for MARECO). But at this point we don’t need exact times, we just need to identify whether a solution would exist at this approximate time.
The process to find the actual train simulation is as follows:
This page is about implementation details. It isn’t necessary to understand general principles, but it helps before reading the code.
This refers to this class in the project.
This class is used to make it easier to create instances of
STDCMEdge, the graph edges. Those contain many attributes,
most of which can be determined from the context (e.g. the
previous node).
The STDCMEdgeBuilder class makes some parameters optional
and automatically computes others.
Once instantiated and parametrized, an STDCMEdgeBuilder has two methods:
makeAllEdges(): Collection<STDCMEdge> can be used to create all
the possible edges in the given context for a given route.
If there are several “openings” between occupancy blocks, one edge
is instantiated for each opening. Every conflict, their avoidance,
and their related attributes are handled here.
findEdgeSameNextOccupancy(double timeNextOccupancy): STDCMEdge?:
This method is used to get the specific edges that uses a certain
opening (when it exists), identified here with the time of the next
occupancy block. It is called whenever a new edge must be re-created
to replace an old one. It calls the previous method.
The methods mentioned here are defined in this class.
The function used to define pathfinding cost sets which path is used over another. The result is always the one that minimizes this cost (as long as the heuristic is admissible).
Here, two parameters are used: total run time and departure time. The latter has a very small weight compared to the former, so that the fastest path is found. More details are explained in the documentation of those methods.
The algorithm used to find a path is an A*, with a heuristic based on geographical coordinates.
However, the coordinates of generated infrastructures are arbitrary and don’t reflect the track distance. It means that, for the generated infrastructures, the path may not always be the shortest one.
It would be possible to use this heuristic to determine whether the current node can lead to a path that doesn’t take longer than the maximum allowed total run time. But for the same reason, adding this feature would break any STDCM test on generated infras. More details in this issue.