NeurIPS 2020 Flatland Challenge is a railway scheduling competition which was held in partnership with German, Swiss, and French railway companies. This repository contains the winner solution from the team An_Old_Driver.
The organizers characterized the research challenge, that lasted several months with continuous software submissions, as follows:
This challenge tackles a key problem in the transportation world: How to efficiently manage dense traffic on complex railway networks? This is a real-world problem faced by many transportation and logistics companies around the world such as the Swiss Federal Railways and Deutsche Bahn. Your contribution may shape the way modern traffic management systems are implemented, not only in railway but also in other areas of transportation and logistics.
The software is based on multi-agent path finding (MAPF) technology and has reached the highest score in both rounds of the challenge and outperformed all other entries in both tracks, including all reinforcement learning entries. According to the organizers, there were more than 700 participants from 51 countries making more than 2,000 submissions.
Please check our paper [1] for more details.
[1] Jiaoyang Li, Zhe Chen, Yi Zheng, Shao-Hung Chan, Daniel Harabor, Peter J. Stuckey, Hang Ma and Sven Koenig. Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pages 477-485, 2021.
The software is developed by
- Jiaoyang Li, University of Southern California
- Zhe Chen, Monash University
- Yi Zheng, University of Southern California
- Shao-Hung Chan, University of Southern California
We would like to thank to Han Zhang for initially tried some ideas for the competition. We would like to thank Daniel Harabor, Peter J. Stuckey, Hang Ma and Sven Koenig for their ideas and advice.
Copyright (c) 2020 The University of Southern California. All Rights Reserved.
Copyrights licensed under an Academic/non-profit use license.
See the accompanying LICENSE file for terms.
In addition to the above license, this software is not allowed to be used in 2021 or later flatland challenges or any other challenges.
The software is developed in C++ and uses boost-python to interact with the Python-based Flatland simulator. boost-python requires special versions of boost and python, and therefore, we suggest you follow the following instruction to install boost and boost-python:
-
Downgrade your python to 3.6 and make sure python-dev is also installed.
-
Install boost 1.61.0 (must include libboost-python3) (Other versions of boost may also work. However you need to make sure your boost-python matches the python version and configure CMakeLists.txt to let the compiler find right packages.)
- Follow Section 5 in boost 1.61.0 document to install the library;
- In particular, when you run bootstrap.sh, make sure it finds the correct version of python. If you didn't see "Detecting Python version... 3.6", use bootstrap.sh --help to learn to configure path to your python manually.
- After installation, make sure that libboost-python3 is in you boost library (which is located at /usr/local/lib by defalult). You might find the library with a slightly different name (e.g., libboost-python36 or libboost-python-py36), in which case, you need to replace "python3" with the last part of the name of your library for variable boostPython in both PythonCBS\CMakelists.txt and CBSH-rect-cmake\CMakeLists.txt. For example, change "set(boostPython python3)" to "set(boostPython python36)".
-
If you are using Windows, configure paths of dependencies manually in ./Mapf-solver/CMakeLists.txt.
Compile codes under Mapf-solver using cmake and make sure libPythonCBS.xx is compiled at the folder where your python codes are.
- ./run_example.py is an example pythoin code that we use to test our software on a locally generated flatland problem.
- Below is a template python code with explanations:
# import mapf solver from shared lib
from libPythonCBS import PythonCBS
# Parameter initialization
agent_priority_strategy = 3 # the strategy for sorting agents, choosing a number between 0 and 5
# 0: keep the original ordering
# 1: prefer max speed then max distance
# 2: prefer min speed then max distance
# 3: prefer max speed then min distance
# 4: prefer min speed then min distance
# 5: prefer different start locations then max speed then max distance
neighbor_generation_strategy = 3 # 0: random walk; 1: start; 2: intersection; 3: adaptive; 4: iterative
debug = False
framework = "LNS" # "LNS" for large neighborhood search or "Parallel-LNS" for parallel LNS.
time_limit = 200 #Time limit for computing initial solution.
default_group_size = 5 # max number of agents in a group for LNS
stop_threshold = 30
max_iteration = 1000 # when set to 0, the algorithm only run prioritized planning for initial solution.
agent_percentage = 1.1 # >1 to plan all agents. Otherwise plan only certain percentage of agents.
replan = True # turn on/off partial replanning.
replan_timelimit = 3.0 # Time limit for replanning.
# Initialize local flatland environment
local_env = ......
# Search for solution
solver = PythonCBS(local_env, framework, time_limit, default_group_size, debug, replan,stop_threshold,agent_priority_strategy,neighbor_generation_strategy)
solver.search(agent_percentage, max_iteration)
# Build MCP
solver.buildMCP()
# Then in the main while loop of the Flatland simulator
# Get corresponding action dictionary by:
action = solver.getActions(local_env, steps, replan_timelimit) # steps: current timestep- Other important hard-coded parameters are in ./Mapf-solver/PythonAPI/PythonCBS.h:
int max_replan_times = 50000; // Maximum replanning times.
float max_replan_runtime = 100; // Maximum time spend on replanning.
int strategies[4] = {1,3,5,6}; // agent_priority_strategies for parallel-lns.- Example run.py script is located in folder ./Flatland2020SubmissionKit
- Place Mapf-solver folder under the root of submission repo. Make sure run.sh can find Mapf-solver for compiling source code.
- Dependencies required by docker are described in ./Flatland2020SubmissionKit/apt.txt
- Following the official submission guide to make submissions.
More details of the vairous MAPF technologies mentioned in the talk and other MAPF related material can be found at mapf.info.
Solutions from 2019 Flatland Challenge