Skip to content
/ caboose Public

A Rust implementation of Continuous Conflict-Based Search for Multi-Agent Path Finding

License

Notifications You must be signed in to change notification settings

vcoppe/caboose

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Caboose

Crates.io Documentation Rust codecov License:MIT

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.

Features

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)

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

Footnotes

  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. 2

  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.

About

A Rust implementation of Continuous Conflict-Based Search for Multi-Agent Path Finding

Topics

Resources

License

Stars

Watchers

Forks

Languages