Caboose

CaBooSe (基于冲突的搜索)，一个实现 连续基于冲突搜索[^1][^2][^3] 算法 (CCBS) 的库，用于解决 多智能体路径搜索问题 (MAPF)，但它是 通用、并行 且使用 Rust 编写的。

CCBS 在内部使用 安全区间路径规划[^4] 算法 (SIPP) 来规划个别路径，同时避免已经处理过的冲突。此外，SIPP 本身使用 可逆可恢复 A*[^5] 算法 (RRA*) 来计算每个任务的启发式信息以解决问题。

此库在来自移动 AI 实验室提供的基准测试的地图和场景上进行了测试。

CCBS 的原始 C++ 实现在PathPlanning/Continuous-CBS中可用。

[^1]: Anton Andreychuk、Konstantin Yakovlev、Dor Atzmon 和 Roni Stern 的《具有连续时间的多智能体路径搜索》[^2]: Anton Andreychuk、Konstantin Yakovlev、Eli Boyarski 和 Roni Stern 的《改进连续时间基于冲突搜索》[^3]: Anton Andreychuk、Konstantin Yakovlev、Pavel Surynek 和 Roni Stern 的《具有连续时间的多智能体路径搜索》[^4]: Mike Phillips 和 Maxim Likhachev 的《SIPP：动态环境中的安全区间路径规划》[^5]: David Silver 的《合作路径搜索》

功能

本论文[^2]中描述的一些改进已实现。

• 断开分割
• 优先处理冲突
• 高级启发式

在连续基于冲突搜索的冲突避免表中描述的 冲突避免表 机制可以进一步加快在存在许多等价成本的路径的环境中搜索的速度。

• 冲突避免表

其他有趣的功能包括

• 并行实现
• 算法的终身包装器
• 处理额外资源（例如，电梯）

安装

本库使用 Rust 编程语言。要安装它，请阅读在线书籍 安装 部分的内容，该书籍的链接为 《Rust编程语言》。

然后构建该库应该像编写以下内容一样简单

cargo build --release

并运行演示

cargo run --release --example simple