CaBooSe (Conflict-Based Search), a library implementing the Continuous Conflict-Based Search123 algorithm (CCBS) for the Multi-Agent Path Finding problem (MAPF), but generic, parallel and in Rust.
CCBS uses the Safe Interval Path Planning4 algorithm (SIPP) algorithm under the hood to plan individual paths while avoiding already processed collisions. Furthermore, SIPP itself uses the Reverse Resumable A*5 algorithm (RRA*) to compute heuristics for each task to solve.
The library is tested on maps and scenarios from the benchmarks provided by the Moving AI Lab.
The original C++ implementation of CCBS is available at PathPlanning/Continuous-CBS.
Some improvements described in this paper2 have been implemented.
- Disjoint splitting
- Prioritizing conflicts
- High-level heuristics
The conflict avoidance table mechanism described in A Conflict Avoidance Table for Continuous Conflict-Based Search could further speed up the search for environments in which many paths with equal costs exist.
- Conflict avoidance table
Other interesting features include:
- Parallel implementation
- Lifelong wrapper of the algorithm
- Handling additional resources (e.g. lifts)
This library uses the Rust programming language. To install it, read the Installation section of The Rust Programming Language online book.
Building the library should then be as easy as writing:
cargo build --release
And running the demo:
cargo run --release --example simple
Footnotes
-
Multi-Agent Pathfinding with Continuous Time by Anton Andreychuk, Konstantin Yakovlev, Dor Atzmon and Roni Stern. ↩
-
Improving Continuous-time Conflict Based Search by Anton Andreychuk, Konstantin Yakovlev, Eli Boyarski and Roni Stern. ↩ ↩2
-
Multi-Agent Pathfinding with Continuous Time by Anton Andreychuk, Konstantin Yakovlev, Pavel Surynek and Roni Stern. ↩
-
SIPP: Safe interval path planning for dynamic environments by Mike Phillips and Maxim Likhachev. ↩
-
Cooperative pathfinding by David Silver. ↩