Meet-Passexpert series
This puzzle comes from the field of planning. Meet-Pass planning is a central aspect of scheduling in real railway systems, though of course this toy example is very much simpler that those handled by industrial-strength optimisers today. As always, our point is that the problem can be represented in pure logic and solved by logical modelling, not this this is the best solution method in practice.
Part of a railway system is made up of sections of track connected like this:
Each section (track T1, …, track T5, siding S1) is big enough to hold a train, and safety requirements state that only one train may be in a section at any one time.
At time “start”, there are three trains in the system:
- train A is in section T1
- train B is in section T2
- train C is in section T4
At each time step, a train may move to an adjacent section provided this is empty. We interpret this to mean that no train may move into an occupied section, even if the other train occupying it is about to move on.
Find a sequence of moves at the end of which train A in in track section T5 and the other two trains are back in their starting positions.
This particular example is taken from a standard benchmark in AI planning. For instance, an encoding in PDDL (Planning Domain Definition Language) may be found here.
Solver
Auto Parser Results
No errors found.