libMultiRobotPlanning

libMultiRobotPlanning provides search algorithms for task and path planning in multi-robot systems. Supported algorithms include:

Single-Robot Algorithms

• A*
• A* epsilon (focal search)
• SIPP (Safe Interval Path Planning)

Multi-Robot Algorithms

• Conflict-Based Search (CBS)
• Enhanced Conflict-Based Search (ECBS)
• Conflict-Based Search with Optimal Task Assignment (CBS-TA)
• Enhanced Conflict-Based Search with Optimal Task Assignment (ECBS-TA)
• Prioritized Planning using SIPP

Assignment Algorithms

• Minimum sum-of-cost (flow-based; integer costs; any number of agents/tasks)
• Best Next Assignment (series of optimal solutions)

To build the library, use CMake to generate build files and then run make. Note that the default make target only builds the examples.

Tested on Ubuntu 16.04.

mkdir build
cd build
cmake ..
make

You can run specific test cases using Python. For example, to run a specific test class/method for the Next Best Assignment algorithm, call the test script with the target test name as an argument.

python3 ../test/test_next_best_assignment.py TestNextBestAssignment.test_1by2

To run an Enhanced Conflict-Based Search (ECBS) instance, use the ecbs executable. You must provide an input map file (-i), an output file (-o), and a weight parameter (-w). After running, you can visualize the results using the visualize.py script.

./ecbs -i ../benchmark/32x32_obst204/map_32by32_obst204_agents10_ex1.yaml -o output.yaml -w 1.3
python3 ../example/visualize.py ../benchmark/32x32_obst204/map_32by32_obst204_agents10_ex1.yaml output.yaml

Conflict-Based Search (CBS) works on generalized graphs. To use roadmaps, you must first annotate the roadmap using annotate_roadmap.py (which assumes a 2D Euclidean embedding and straight-line edges), then run the cbs_roadmap executable, and finally visualize the output.

Workflow:

1. Annotate the roadmap.
2. Run cbs_roadmap with input (-i) and output (-o) flags.
3. Visualize using visualize_roadmap.py.

python3 ../tools/annotate_roadmap.py ../test/mapf_simple1_roadmap_to_annotate.yaml mapf_simple1_roadmap_annotated.yaml
./cbs_roadmap -i mapf_simple1_roadmap_annotated.yaml -o output.yaml
python3 ../example/visualize_roadmap.py mapf_simple1_roadmap_annotated.yaml output.yaml

The library provides the following algorithms for multi-robot coordination:

The following targets are available via make after configuring with CMake:

• make: Builds only the examples.
• make docs: Builds Doxygen documentation.
• make clang-format: Re-formats all source files.
• make clang-tidy: Runs the linter and static code analyzer.
• make run-test: Runs the unit tests.

The library provides the following algorithms for single-robot pathfinding:

The library provides the following algorithms for task assignment: