基于搜索的多机器人路径规划

基于搜索方法的多机器人路径规划

1 冲突基搜索（Conflict-Based Search）

为了解决多机器人通过各自规划出来的轨迹存在冲突的问题，使用中心化的约束树（Constraint Tree）去解决这些冲突的问题。
约束树的节点包括以下几个部分：

• constraints：约束（agent, position, time）代表某个智能体在某个时间不能去到这个位置
• solutions：所有智能体在约束条件下规划的轨迹
• cost：所有智能体轨迹的代价总和

而约束由母节点的 solutions 获得的第一个冲突（conflict） $(a_i,a_j,v,t)$，表示智能体 $a_i$ 和 $a_j$ 在时间 $t$，同时到达点 $v$ 的冲突。子节点的约束就可以分成两个 $(a_i,v,t)$ 和 $(a_j,v,t)$。如果母节点已经有约束，那么子节点除了冲突分出来的约束，还要继承母节点的约束。

这样从母节点开始，在获得冲突，分支，计算在约束下的解以及代价，并在下次选择还未分支的节点（这些节点可以是不同层级的）中代价最小的一个节点不断循环。直到有节点代价最小且没有冲突。

例子：

约束树

伪代码

• OPEN：相当于一个以代价为优先级的优先队列（相当于 Constraints Tree）