Abstract
The Flatland competition aimed at finding novel approaches to solve the vehicle re-scheduling problem (VRSP). The VRSP is concerned with scheduling trips in traffic networks and the re-scheduling of vehicles when disruptions occur, for example the breakdown of a vehicle. While solving the VRSP in various settings has been an active area in operations research (OR) for decades, the ever-growing complexity of modern railway networks makes dynamic real-time scheduling of traffic virtually impossible. Recently, multi-agent reinforcement learning (MARL) has successfully tackled challenging tasks where many agents need to be coordinated, such as multiplayer video games. However, the coordination of hundreds of agents in a real-life setting like a railway network remains challenging and the Flatland environment used for the competition models these real-world properties in a simplified manner. Submissions had to bring as many trains (agents) to their target stations in as little time as possible. While the best submissions were in the OR category, participants found many promising MARL approaches. Using both centralized and decentralized learning based approaches, top submissions used graph representations of the environment to construct tree-based observations. Further, different coordination mechanisms were implemented, such as communication and prioritization between agents. This paper presents the competition setup, four outstanding solutions to the competition, and a cross-comparison between them.
Introduction
Modern railway networks, such as those operated by the Swiss Federal Railways (SBB), are incredibly dense. A single train malfunction can trigger a "domino effect" of delays across the entire system. This is the Vehicle Re-scheduling Problem (VRSP): the challenge of dynamically re-routing hundreds of agents in real-time within a constantly changing environment. Solving this problem is NP-complete. To foster innovation, the Flatland simulator was developed—a simplified but representative grid-world environment where the goal is to navigate as many trains as possible to their target stations in minimal time, despite random breakdowns.
The Flatland Environment
The competition utilized a grid-based simulator where agents (trains) move between cells. The environment is composed of various track types, including straight sections, simple switches, and complex crossings.
For the competition, 41 distinct test sets were created, scaling from $25 \times 25$ grids with a single agent to massive $314 \times 314$ grids with over 6,000 agents. Stochasticity was introduced through varying malfunction rates to test the robustness of re-scheduling logic.
Methods and Solutions
Four outstanding solutions were highlighted, representing both Operations Research (OR) and Reinforcement Learning (RL) paradigms:
- Multi-Agent Path Finding (MAPF) - Team An_Old_Driver: The top performer used Prioritized Planning with Safe Interval Path Planning (SIPP). They optimized paths using Large Neighborhood Search (LNS) and a "lazy planning" scheme to mitigate congestion.
- Communicative RL - Team JBR_HSE: This team employed Proximal Policy Optimization (PPO) with a self-attention-based communication layer. They also used a "Departure Schedule" classifier to predict destination reachability before allowing trains onto the grid.
- Graph-Based RL - Team Netcetera: This approach modeled the environment as a graph of switches, utilizing Ape-X DQN and solving conflicts via graph coloring heuristics.
- Traffic Light Coordination - Team MARMot-Lab-NUS: Inspired by urban traffic, they implemented a "Traffic Light" mechanism to manage bottlenecks in dense switch clusters.
Key Insights
- Tree Observations: Successful RL teams moved away from raw grid images, instead using "Tree Observations" that follow tracks from the agent's perspective to capture relevant features like distance to switches and goals.
- Communication and State Masking: Attention mechanisms for inter-agent communication significantly improved arrival rates. Furthermore, by ignoring "non-decision" cells (straight tracks) and only triggering models at switches (highlighted in blue in the environment visualization), teams reduced computational overhead.
- The Caution Trade-off: RL agents often exhibited excessive caution to avoid penalties. Heuristics like departure scheduling were vital to balance safety with throughput.
Results and Discussion
The OR approach by An_Old_Driver was the overall winner, achieving a 98.6% completion rate. The leading RL solution (JBR_HSE) was highly competitive, reaching a 78.5% completion rate. While all methods performed well on small grids, performance diverged at higher densities (around Test 10). OR methods remained robust, whereas RL agents showed higher variance and declining scores, indicating that global search still holds an advantage over local learned policies in highly constrained, large-scale environments.
Conclusion
While RL is rapidly closing the gap, it still struggles with permanent deadlocks. Future work focuses on hybrid approaches—combining RL's local decision speed with OR's global consistency—and developing more sophisticated temporal architectures and learned coordination protocols.
Summary updated