Rolling-Horizon Collision Resolution (RHCR) is an efficient algorithm for solving lifelong Multi-Agent Path Finding (MAPF) where we are aksed to plan collision-free paths for a large number of agents that are constanly engaged with new goal locations. RHCR calls a Windowed MAPF solver every h timesteps that resolves collisions only for the next w timesteps (w >= h). More details can be found in our extended abstract at AAMAS 2020 [1] and our full paper at AAAI 2021 [2].
The code requires the external library BOOST (https://www.boost.org/).
Here is an easy way of installing BOOST in Linux:
sudo apt install libboost-all-devAfter you installed BOOST and downloaded the source code, go into the directory of the source code and compile it with CMake:
cmake .
make
Then, you are able to run the code:
./lifelong -m maps/sorting_map.grid -k 800 --scenario=SORTING --simulation_window=5 --planning_window=10 --solver=PBS --seed=0
for running RHCR with PBS on the sorting center map; and
./lifelong -m maps/kiva.map -k 100 --scenario=KIVA --simulation_window=1 --solver=ECBS --suboptimal_bound=1.5 --dummy_path=1 --seed=0
for running ECBS(w=1.5) with dummy paths on the kiva map.
- m: the map file
- k: the number of agents
- scenario: the simulation scenario (each scenario corresponding to a different task assigner). Use KIVA for the fulfillment warehouse scenario and SORTING for the sorting center scenario.
- simulation_window: the replanning period h
- planning_window: the planning window w
- solver: the windowed MAPF solver (WHCA, ECBS, and PBS)
- seed: the random seed
You can find more details and explanations for all parameters with:
./lifelong --help
RHCR is released under USC – Research License. See license.md for further details.
[1] Jiaoyang Li, Andrew Tinka, Scott Kiesel, Joseph W. Durham, T. K. Satish Kumar and Sven Koenig. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses (extended abstract). In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1898-1900, 2020.
[2] Jiaoyang Li, Andrew Tinka, Scott Kiesel, Joseph W. Durham, T. K. Satish Kumar and Sven Koenig. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), (in print), 2021.