Establishes NP-hardness of MAPF on trees for labeled and 2-colored variants across three objectives by proving hardness of stack rearrangement, which reduces to motion on subdivided stars.
Flatland-RL : Multi-Agent Reinforcement Learning on Trains
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
Efficient automated scheduling of trains remains a major challenge for modern railway systems. The underlying vehicle rescheduling problem (VRSP) has been a major focus of Operations Research (OR) since decades. Traditional approaches use complex simulators to study VRSP, where experimenting with a broad range of novel ideas is time consuming and has a huge computational overhead. In this paper, we introduce a two-dimensional simplified grid environment called "Flatland" that allows for faster experimentation. Flatland does not only reduce the complexity of the full physical simulation, but also provides an easy-to-use interface to test novel approaches for the VRSP, such as Reinforcement Learning (RL) and Imitation Learning (IL). In order to probe the potential of Machine Learning (ML) research on Flatland, we (1) ran a first series of RL and IL experiments and (2) design and executed a public Benchmark at NeurIPS 2020 to engage a large community of researchers to work on this problem. Our own experimental results, on the one hand, demonstrate that ML has potential in solving the VRSP on Flatland. On the other hand, we identify key topics that need further research. Overall, the Flatland environment has proven to be a robust and valuable framework to investigate the VRSP for railway networks. Our experiments provide a good starting point for further research and for the participants of the NeurIPS 2020 Flatland Benchmark. All of these efforts together have the potential to have a substantial impact on shaping the mobility of the future.
representative citing papers
An entity-graph MARL framework (RACHE) using R-GCN message passing and attention pooling over train-service nodes outperforms baseline algorithms in railway pricing revenue across two simulated market scenarios.
SMART is a physics-engine-based, scalable testbed for realistic evaluation of multi-agent path finding algorithms with an Action Dependency Graph integration framework.
Presents MAEnvs4VRP, a modular PyTorch library providing unified multi-agent environments for multiple variants of vehicle routing problems following the AEC model.
citing papers explorer
-
On the Hardness of Optimal Motion on Trees
Establishes NP-hardness of MAPF on trees for labeled and 2-colored variants across three objectives by proving hardness of stack rearrangement, which reduces to motion on subdivided stars.
-
Relational Multi-Agent Reinforcement Learning for Dynamic Pricing in High-Speed Railway Markets
An entity-graph MARL framework (RACHE) using R-GCN message passing and attention pooling over train-service nodes outperforms baseline algorithms in railway pricing revenue across two simulated market scenarios.
-
Advancing MAPF Toward the Real World: A Scalable Multi-Agent Realistic Testbed (SMART)
SMART is a physics-engine-based, scalable testbed for realistic evaluation of multi-agent path finding algorithms with an Action Dependency Graph integration framework.
-
Multi-Agent Environments for Vehicle Routing Problems
Presents MAEnvs4VRP, a modular PyTorch library providing unified multi-agent environments for multiple variants of vehicle routing problems following the AEC model.