libMultiRobotPlanning

libMultiRobotPlanning 是一个包含搜索算法的库，主要用于多机器人/智能体系统的任务规划和路径规划。该库使用 C++14 编写，广泛采用模板技术以获得优异性能，并附带实用示例。

目前支持以下算法：

• 单机器人算法

  • A*
  • A* epsilon（也称为焦点搜索）
  • SIPP（安全间隔路径规划）

• 多机器人算法

  • 基于冲突的搜索（CBS）
  • 增强型基于冲突的搜索（ECBS）
  • 带最优任务分配的基于冲突的搜索（CBS-TA）
  • 带最优任务分配的增强型基于冲突的搜索（ECBS-TA）
  • 使用 SIPP 的优先级规划（SIPP 示例代码）

• 分配算法

  • 最小总代价法（基于流；整数代价；任意数量的智能体/任务）
  • 下一个最佳分配法（一系列最优解）

构建

已在 Ubuntu 16.04 上测试通过。

mkdir build
cd build
cmake ..
make

目标

• make：仅构建示例
• make docs：构建 Doxygen 文档
• make clang-format：重新格式化所有源文件
• make clang-tidy：运行代码检查工具及静态代码分析器
• make run-test：运行单元测试

运行特定测试

python3 ../test/test_next_best_assignment.py TestNextBestAssignment.test_1by2

运行示例实例

ECBS

./ecbs -i ../benchmark/32x32_obst204/map_32by32_obst204_agents10_ex1.yaml -o output.yaml -w 1.3
python3 ../example/visualize.py ../benchmark/32x32_obst204/map_32by32_obst204_agents10_ex1.yaml output.yaml

广义路网

CBS 可在广义图上运行，尤其侧重于可选的等待动作（例如，也可与运动基元结合使用）。然而，当前的路网标注和可视化步骤假定为二维欧几里得嵌入以及直线边。

python3 ../tools/annotate_roadmap.py ../test/mapf_simple1_roadmap_to_annotate.yaml mapf_simple1_roadmap_annotated.yaml
./cbs_roadmap -i mapf_simple1_roadmap_annotated.yaml -o output.yaml
python3 ../example/visualize_roadmap.py mapf_simple1_roadmap_annotated.yaml output.yaml

libMultiRobotPlanning 快速上手指南

libMultiRobotPlanning 是一个专为多机器人/智能体系统设计的任务与路径规划搜索算法库。该库基于 C++14 编写，采用高度模板化设计以确保高性能，并提供了丰富的示例代码。

环境准备

• 操作系统：推荐 Ubuntu 16.04 或更高版本（Linux 环境）。
• 编译器：支持 C++14 标准的编译器（如 GCC 5.0+ 或 Clang 3.4+）。
• 构建工具：
  • CMake (3.5+)
  • Make
• 运行时依赖（用于运行示例和可视化）：
  • Python 3
  • PyYAML (pip3 install pyyaml)
  • Matplotlib (pip3 install matplotlib)

提示：国内用户可使用清华源或阿里源加速 apt 和 pip 包的安装。

安装步骤

克隆仓库并编译项目：

git clone https://github.com/whoenig/libMultiRobotPlanning.git
cd libMultiRobotPlanning
mkdir build
cd build
cmake ..
make

编译完成后，可执行文件将生成在 build 目录下。

可选构建目标

• make docs：生成 Doxygen 文档。
• make run-test：运行单元测试。
• make clang-format / make clang-tidy：代码格式化与静态分析。

基本使用

以下演示如何运行 ECBS (Enhanced Conflict-Based Search) 算法示例，并进行结果可视化。

1. 运行规划算法

使用提供的基准地图文件运行 ECBS 算法，设置亚最优界权重 -w 1.3：

./ecbs -i ../benchmark/32x32_obst204/map_32by32_obst204_agents10_ex1.yaml -o output.yaml -w 1.3

• -i: 输入配置文件路径。
• -o: 输出规划结果文件路径。
• -w: 权重参数，控制求解速度与最优性的平衡。

2. 可视化结果

使用 Python 脚本加载地图和规划结果进行可视化：

python3 ../example/visualize.py ../benchmark/32x32_obst204/map_32by32_obst204_agents10_ex1.yaml output.yaml

其他场景：通用路线图 (Generalized Roadmaps)

CBS 算法也支持在通用图上运行（包含等待动作）。若需处理自定义路线图，需先标注再运行：

# 1. 标注路线图
python3 ../tools/annotate_roadmap.py ../test/mapf_simple1_roadmap_to_annotate.yaml mapf_simple1_roadmap_annotated.yaml

# 2. 运行 CBS 规划
./cbs_roadmap -i mapf_simple1_roadmap_annotated.yaml -o output.yaml

# 3. 可视化路线图结果
python3 ../example/visualize_roadmap.py mapf_simple1_roadmap_annotated.yaml output.yaml

运行特定测试

如需验证特定算法模块（例如“次优分配”测试）：

python3 ../test/test_next_best_assignment.py TestNextBestAssignment.test_1by2