Loosely Synchronized Rule-Based Planning (LSRP) for Multi-Agent Path Finding with Asynchronous Actions

This repository provides an implementation of the Loosely Synchronized Rule-Based Planning (LSRP) algorithm for solving Multi-Agent Path Finding with asynchronous actions problems (MAPF-AA). LSRP is designed to handle a large number of agents by trading off solution quality for scalability. More technical details can be found in [1].

The code is distributed for academic and non-commercial use. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

(Fig 1: A 100 agent MAPF-AA instances.)

Requirements

• C++ compiler supporting C++11 or later
• CMake (version 2.8.3 or later)
• Make

Project Structure

• demo/ - Contains a few input files for the command example cases
• include/ - Contains all header files.
• source/ - Contains all source files corresponding to the headers.
• test/ - Contains toy example file that shows how to use the code.

Installation and Usage

1. Clone this repository.
2. mkdir build/
3. cmake -DCMAKE_BUILD_TYPE=Release -B build
4. cd build/
5. make
6. Run the program with the following command:

   ./lsrp <map_path> <scen_path> <duration_path> <runtime> [swap]

   To run the program with 10 agents on the specified map and scenario files, and save the results to result.xml with a maximum runtime of 30 seconds and the swap feature enabled, use the following command:

   ./lsrp ../demo/warehouse-10-20-10-2-1.map ../demo/warehouse-10-20-10-2-1-random-1.scen ../demo/duration.txt 30 swap

Note: A pseudo random generator is used in the algorithm on the main branch. If you prefer a deterministic solver, please checkout the feature/no-rng branch.

Command Line Arguments

• <map_path>: The path to the map file.
• <scen_path>: The path to the scenario file.
• <duration_path>: The path to the duration file where the durations for each agent is written.
• <runtime>: The maximum runtime for the algorithm in seconds.
• [swap] (optional): If provided, enables the swap feature.

Example

To run the toy example, use the following command:

./test_toyexample

To run a toy example

Visualization

For visualization of the results, you can use the Visualizer.

This Qt framework-based visualizer allows you to load and display the output files generated by this project.

References

• [1] Zhou, S., Zhao, S., & Ren, Z. (2025). Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions. Proceedings of the AAAI Conference on Artificial Intelligence, 39(14), 14763-14770.
  [Bibtex][Paper]

License

This code is distributed under the MIT License. See the LICENSE file for details.