Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World

Florian Laurent, Manuel Schneider, Christian Scheller, Jeremy D. Watson, Jiaoyang Li, Zhe Chen, Yi Zheng, Shao-Hung Chan, Konstantin Makhnev, Oleg Svidchenko, Vladimir Egorov, Dmitry Ivanov, Aleksei Shpilman, Evgenija Spirovska, Oliver Tanevski, Aleksandar Nikov, Ramon Grunder, David Galevski, Jakov Mitrovski, Guillaume Sartoretti, Zhiyao Luo, Mehul Damani, Nilabha Bhattacharya, Shivam Agarwal, Adrian Egli, Erik Nygren, Sharada P. Mohanty

Executive Summary

The Flatland Competition 2020 challenged researchers to solve a massive multi-agent coordination problem: routing thousands of trains across a complex grid world without deadlocks. While traditional Operations Research (OR) methods still dominate at extreme scales, the competition highlighted how Multi-Agent Reinforcement Learning (MARL) is closing the gap through innovative communication protocols and tree-based environment observations.

The Vehicle Re-Scheduling Problem (VRSP)

In real-world railway networks, such as those operated by the Swiss Federal Railways (SBB), thousands of trains must be coordinated simultaneously. When a single train malfunctions, it creates a ripple effect of delays and potential deadlocks. Solving this in real-time is an NP-complete nightmare.

The Flatland environment grid world and its fundamental track cell types.

The paper addresses this through the Flatland environment, which simplifies the VRSP into a 2D grid world. Agents (trains) must move from a starting cell to a target station. The challenge lies in high agent density, limited movement (trains cannot reverse), and random malfunctions that force dynamic re-routing.

Top Performing Methods

The competition evaluated approaches across two distinct tracks: Operations Research (OR) and Reinforcement Learning (RL).

1. Operations Research (OR) - The Winning Approach

The overall winner, team An_Old_Driver, utilized a highly optimized centralized approach:

  • Prioritized Planning (PP): Trains are ranked, and their paths are planned sequentially to avoid conflicts.
  • Safe Interval Path Planning (SIPP): An efficient variant of A* search that plans over "time intervals" to avoid collisions, eliminating the need to check every single timestep.
  • Large Neighborhood Search (LNS): An optimization step that iteratively selects subsets of trains and replans their paths to improve the global solution.
  • Lazy Planning: To handle thousands of agents, the system only planned for a few at a time, dynamically accounting for malfunctions as they occurred.

2. Reinforcement Learning (RL) Innovations

Top RL teams moved away from standard "image-like" grid observations, adopting novel techniques to handle the sparse, graph-like nature of railways:

  • Tree Observations: Instead of a raw grid, agents "look ahead" from their current position, following possible paths at switches to build a tree of features (e.g., distance to target, presence of other agents).
  • Communication Layers: Team JBR_HSE (1st place in the RL track) implemented a communication protocol using self-attention. This allowed agents to share intent and coordinate effectively at bottlenecks.
  • Priority Heuristics: Team Netcetera used a conflict graph and a graph-coloring algorithm to assign priorities to agents centrally, which were then used as inputs for decentralized RL policies.
  • State Masking: Most teams ignored "non-decision" cells (straight tracks where no choice is possible) to simplify the action space and speed up training.

The Flatland Benchmark

The competition utilized a procedurally generated benchmark to test these methods. Participants used an open-source generator to create infinite variations of training grids. The final evaluation relied on a hidden set of 41 tests, each containing 10 environments. Complexity scaled dramatically, from a single agent on a 25x25 grid to 6,256 agents on a 314x314 grid. Furthermore, environments included varying rates of random breakdowns, requiring agents to be reactive rather than just following static, pre-computed paths.

Key Insights

  • The Power of Communication: For RL agents, the ability to "talk" was the single most impactful modification. It significantly increased arrival rates by allowing agents to negotiate right-of-way at switches.
  • Heuristics Prevent Gridlock: Pure RL struggled with gridlock at the start of episodes. The most successful RL teams used a Departure Schedule (a supervised classifier) to stagger train starts, preventing the system from being overwhelmed.
  • Tree vs. Grid: Standard Convolutional Neural Networks (CNNs) are inefficient for sparse railway networks. Tree-based observations that follow the "rails" provide a much higher signal-to-noise ratio.
  • The "Cautious" RL Problem: RL agents often learned to be overly cautious to avoid deadlocks, leading to lower overall throughput compared to the more aggressive, globally-optimized OR paths.

Results and Future Directions

Operations Research remains the state-of-the-art for this domain. The overall OR winner achieved a score of 297.5, solving 363 environments with a 98.6% completion rate. In contrast, the top RL solution achieved a score of 214.1, solving 336 environments with a 78.5% completion rate. Performance for all methods remained high until agent density reached a critical threshold, after which OR maintained much better stability in high-congestion scenarios.

The authors acknowledge that RL is still a considerable distance from OR in solving the VRSP. RL's primary weakness is the lack of a global lookahead; a single local decision can cause a domino effect resulting in a deadlock miles away. Future directions include combining tree observations with local grid views for better spatial reasoning, integrating temporal models (like LSTMs) to predict when malfunctions might clear, and moving toward fully learned end-to-end coordination controllers.

Summary updated

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 o...
BibTeX
@inproceedings{laurent2020flatland,
  author = {Florian Laurent and Manuel Schneider and Christian Scheller and Jeremy D. Watson and Jiaoyang Li and Zhe Chen and Yi Zheng and Shao-Hung Chan and Konstantin Makhnev and Oleg Svidchenko and Vladimir Egorov and Dmitry Ivanov and Aleksei Shpilman and Evgenija Spirovska and Oliver Tanevski and Aleksandar Nikov and Ramon Grunder and David Galevski and Jakov Mitrovski and Guillaume Sartoretti and Zhiyao Luo and Mehul Damani and Nilabha Bhattacharya and Shivam Agarwal and Adrian Egli and Erik Nygren and Sharada P. Mohanty},
  title = {{Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=Ati-ZE1bE9Y},
}
Figure