Caboose

CaBooSe (Conflict-Based Search), a library implementing the Continuous Conflict-Based Search¹²³ algorithm (CCBS) for the Multi-Agent Path Finding problem (MAPF), but generic, parallel and in Rust.

CCBS uses the Safe Interval Path Planning⁴ algorithm (SIPP) algorithm under the hood to plan individual paths while avoiding already processed collisions. Furthermore, SIPP itself uses the Reverse Resumable A*⁵ 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.

Features

Some improvements described in this paper² 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