Caboose

CaBooSe (Conflict-Based Search), a library implementing the Continuous Conflict-Based Search[^1][^2][^3] algorithm (CCBS) for the Multi-Agent Path Finding problem (MAPF), but generic, parallel and in Rust.

CCBS uses the Safe Interval Path Planning[^4] 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.

[^1]: Multi-Agent Pathfinding with Continuous Time by Anton Andreychuk, Konstantin Yakovlev, Dor Atzmon and Roni Stern. [^2]: Improving Continuous-time Conflict Based Search by Anton Andreychuk, Konstantin Yakovlev, Eli Boyarski and Roni Stern. [^3]: Multi-Agent Pathfinding with Continuous Time by Anton Andreychuk, Konstantin Yakovlev, Pavel Surynek and Roni Stern. [^4]: SIPP: Safe interval path planning for dynamic environments by Mike Phillips and Maxim Likhachev. [^5]: Cooperative pathfinding by David Silver.

Features

Some improvements described in this paper[^2] 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)

Installation

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