Winning Solution of the AIcrowd SBB Flatland Challenge 2019-2020
This addresses a domain-specific railway scheduling problem for competition participants, with incremental improvements in path regeneration and malfunction handling.
The paper presents the winning solution for the AIcrowd SBB Flatland Challenge 2019-2020, which tackled the problem of routing agents in a railway simulation by achieving a score of 99% in routing agents to destinations within allotted time steps.
This report describes the main ideas of the solution which won the AIcrowd SBB Flatland Challenge 2019-2020, with a score of 99% (meaning that, on average, 99% of the agents were routed to their destinations within the allotted time steps). The details of the task can be found on the competition's website. The solution consists of 2 major components: 1) A component which (re-)generates paths over a time-expanded graph for each agent 2) A component which updates the agent paths after a malfunction occurs, in order to try to preserve the same agent ordering of entering each cell as before the malfunction. The goal of this component is twofold: a) to (try to) avoid deadlocks b) to bring the system back to a consistent state (where each agent has a feasible path over the time-expanded graph). I am discussing both of these components, as well as a series of potentially promising, but unexplored ideas, below.