This is the repo for the team Pikachu's solution in the League of Robot Competition 2023. We come from the ARCS Lab at Robotics Institute, CMU. Our solution won the Overall Best and Fast Mover tracks and ranked second in the Line Honours track.
- We have a related paper, Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities, accepted by SoCS 2024, which discusses our solution and important challenges in the Lifelong MAPF.
- [To Update] We use an automatic algorithm to generate guidance graphs (edge weights that encode moving costs) in the competition for the random map with 800 agents. This algorithm is not included in this repo. If you are interested, please refer to this work by one of our teammates, Yulun.
- The League of Robot Runner Competition also open source solutions from all teams with the benchmark data used in the competition. This repo adds slightly more functionalities but most of the code remains the same as the one used in the competition. We may clean the code further in the future if we have time.
- Note that our code includes RHCR code but doesn't use it eventually. Our code doesn't directly use the code from PIBT repo but uses a part of the LaCAM2 code to execute the PIBT algorithm. Our code doesn't directly use the code from LNS but uses a part of the LNS2 to execute LNS algorithm.
- The team Shadocks, which achieves a close score to us, also has a report describing the solution.
We call our algorithm Windowed Parallel PIBT-LNS (WPPL). Essentially, it is a combination of PIBT, LNS and RHCR. We also parallelize LNS to exploit multi-CPUs. Further, to address the problem of congestion, we apply a guidance graph, which encourages agents to execute certain actions at certain locations and disable some agents in a way that their goals are set to the current locations and their priorities to the lowest. For more details, please to our paper.
Before reading the following, you may want to take a look at the official documents of the competition in the official_docs folder.
To compile and run codes in this repo:
- You may need to install boost, openmp and spdlog, e.g. by
sudo apt install libboost-all-dev libomp-dev libspdlog-dev. If anything is still missing, you can checkapt.txt. - Use
./compile.shto compile - Use
run.shto run all the experiments. - Official json-format logs will be generated at the output path specified by
-o. - If compiled with
set(DEV on), the program will output more statistics in the command line and also output an analysis file in the path specified by the filedanalysis_outputin the configuration file introduced below.
The command line options are the general settings for io and simulation. The configuration files describe the map-specific algorithm settings. The environment variables are some extra advanced settings.
All the command line options are defined in the src/driver.cpp. The following are the most important ones:
--inputFileThe description file path of a problem instance.-oThe output file path.--planTimeLimitThe planning time limit for each execution step in seconds. In the competition, it is 1.--simulationTimeThe total execution steps to simulate.
The problem will automatically load the default configuration files in the configs folder, according to the map name. Please refer to configs/random-32-32-20_annotated.json for the explanation of each field.
OMP_NUM_THREADS=<the number of threads>How many threads to use to precompute heuristics.LNS_NUM_THREADS=<the number of threads>How many parallel Large Neighborhood Search (LNS) threads are used to refine plans.CONFIG_PATH=<the path to a configuration file>The path to a configuration file to replace the default one.MAP_WEIGHT_PATH=<the path to a map weight file>The path to a map weight file (map weights = guidance graph). It will replace the one specified in the configuration file.
If you have any questions, you can send me an email.