ECBS多机器人路径规划-Toy模板网

这篇具有很好参考价值的文章主要介绍了ECBS多机器人路径规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

多机器人路径规划

多智能体路径规划 (Multi-Agent Path Finding, MAPF) 研究多智能体的路径规划算法，为多机系统规划无冲突的最优路径。

ECBS 算法由 CBS(Conflict-Based Search) 算法改进而来, 对 CBS算法的介绍可以参考笔者的这篇文章CBS多机器人路径规划(Conflict-Based Search)。CBS 算法给出 MAPF 问题的全局最优结果，ECBS 算法给出 MAPF 问题的有界次优结果。ECBS 之于 CBS，正如 $A^*_{\epsilon}$ 之于 $A^*$ ，获得有限损失的次优结果，换来极大的速度提升。

参考文献：

Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem

ECBS(Enhanced CBS)

ECBS 基于 CBS 和 $A^*_{\epsilon}$ ，如果对 $A^*_{\epsilon}$ 不熟悉可以参考笔者的这篇文章 A*算法及其变种。

ECBS 沿用 CBS 框架，主要对 CBS 的顶层和底层搜索算法作出改进，论文由浅入深，依次介绍了次优的 GCBS(Greedy-CBS)、有界次优的 BCBS(Bounded Suboptimal CBS)，以及对 BCBS 作出更灵活改进的 ECBS(Enhanced CBS)，本文将依次介绍这些算法。

GCBS(Greedy-CBS)

在 CBS 中，顶层和底层都是最优搜索，GCBS 通过松弛(relax)顶层和底层的搜索条件提升算法效率。

GCBS 不是最优的，但是完备的。完备性的证明可以参考原论文，和 CBS 证明完备性的思想一样。

顶层松弛

CBS 的顶层搜索启发函数规则为全局 $cos t$ 最小，GCBS 的顶层启发函数的规则设计为基于 $so l u t i o n$ 中的冲突( $co n f l i c t s$ )数量，用 $h_c$ 表示，作者给出了以下几个启发函数示例：

$h_1$ ：全局冲突数量：计算当前分支节点中 $so l u t i o n$ 的冲突数量
$h_2$ ：发生冲突的机器人数量：计算前分支节点中路径里存在冲突的机器人数量
$h_3$ ：发生冲突的机器人对(pairs)：计算前分支节点中路径里存在冲突的机器人对的数量
$h_4$ ：顶点覆盖(Vertex cover)：定义一个图 graph：其中机器人为顶点(nodes)，路径之间有冲突的机器人之间有边(edges)相连。事实上， $h_2$ 描述了顶点， $h_3$ 描述了边， $h_4$ 计算顶点覆盖数。
$h_5$ ：可变启发式：在特定的条件下用特定的启发函数，更有鲁棒性，但编程比较麻烦。

作者声称，实测中 $h_5$ 的效果最好。但由于 $h_3$ 兼顾优秀性能和简洁性，介绍算法时选择 $h_3$ 作为实际的启发函数。在下文，所有的 $h_c$ 都代表 $h_3$ 。

底层松弛

松弛底层，最简单的方法就是把寻路算法改成次优的，例如 WA*。作者提到，这样看起来单机器人搜索变快了，但次优算法会得出更长的路径结果，增加了未来顶层需要解决的潜在冲突数(单条路径越长，这些路径之间产生冲突的可能性就越大)。

作者提出，在每次进行当前机器人的路径规划前，考虑之前其他机器人的路径，尽量提前躲避。也就是把之前其他机器人的路径当成障碍物，然后进行时空 A*(space-time A*) 搜索。这样就能直接在底层尽量的减小路径之间的冲突数量。

这种思想其实与基于优先级的搜索(Prioritized-Based Search, PBS)有点像：按顺序对多台机器人进行规划，先进行规划的机器人的路径作为障碍物信息附加在后进行规划的机器人的约束条件中。PBS 的底层可以用任意一种单机规划算法。

为什么说 GCBS 的底层和 PBS 有点像 而不是一样呢，因为为了快速计算出结果， GCBS 的底层只是尽量（倾向于）提前躲避障碍物，并不是完全躲避，未能躲避而产生的冲突交给顶层解决。

BCBS(Bounded Suboptimal CBS)

CBS 的顶层和底层搜索都使用 A* ，BCBS 的顶层和底层搜索都使用 $\space Search(A^*_{\epsilon})$ ，对 $A^*_{\epsilon}$ 不熟悉可以参考笔者的这篇文章 A*算法及其变种。

首先，定义 $f oc a l$ - $search(f_1,f_2)$ 表示使用启发函数 $f_1,f_2$ 的 $\space Search$ ，其中， $f_1$ 用于选择哪些节点被选入 $FOC A L$ 表， $f_2$ 用于选择从 $FOC A L$ 表中选择哪一个节点作为下一步扩展。

顶层搜索

对约束树进行 $f oc a l$ - $search(g,h_c)$ ，其中, $g (n)$ 表示当前节点的 $cos t$ ， $h_c(n)$ 表示 $h_3(n)$ (发生冲突的机器人对的数量)。

底层搜索

在底层应用 $f oc a l$ - $search(f,h_c)$ ，其中 $f (n) = g (n) + h (n)$ 与 A* 中的 $f (n)$ 一致， $h_c(n)$ 表示 $h_3(n)$ (考虑在节点 n 的路径冲突)

定义 $BCBS(w_H,w_L)$ 表示在顶层的 $\space search$ 使用 $w_H$ 参数，在底层的 $\space search$ 使用 $w_L$ 参数 ( $w=1+\epsilon$ )。

根据定义， $BCBS(w_H,w_L)$ 有如下特例：

$w_L = 1$ ，即 $BCBS(w_H,1)$ ：表示仅在顶层使用 $\space search$
$w_H = 1$ ，即 $BCBS(1,w_L)$ ：表示仅在底层使用 $\space search$
$w_H = w_L = 1$ ，即 $BCBS (1, 1)$ ：BCBS 退化为 CBS
$w_H = w_L = \infty$ ，即 $BCBS(\infty,\infty)$ ：BCBS 退化为 GCBS，此时， $FOC A L$ 表与 $Op e n$ 表一致。

$BCBS(w_H,w_L)$ 能保证最终的全局 $\le w_H \cdot w_L \cdot C^*$ ，其中， $C^*$ 为最优 $cos t$ (也就是 CBS 的结果)。

ECBS(Enhanced CBS)

提出新方法的第一步是抨击旧方法。刚介绍完 BCBS，作者马上提到，BCBS 中关于 $w_L$ 和 $w_H$ 的调参是非常有讲究的，需要大量的调试经验，并且在整个搜索过程中 $w_L$ 和 $w_H$ 完全固定，会影响算法性能。

为了解决这个问题，ECBS 应运而生。

ECBS 的底层搜索算法与 $BCBS (1, w)$ 一致。以下介绍 ECBS 的顶层搜索算法。

设在 CBS 底层搜索中，为机器人 $a_i$ 搜索路径时使用的 $OPEN$ 表为 $OPEN_i$ ，则 $OPEN_i$ 中的最小 $f$ 值 $f_{min}(i)$ 为机器人 $a_i$ 最优路径代价 $cos t$ 的下界(Lower Bound)。对一个约束树节点(CT node) $n$ ，设 $\sum^k_{i=1}f_{min}(i)$ ，根据定义有 $\le n.cost \le LB(n) \cdot w$ 。

在 ECBS 中，每一个 CT node 传递两个值给顶层算法：

$n . cos t$
$L B (n)$

设 $\in OPEN)$ ，其中 $OPEN$ 为顶层搜索中的 $OPEN$ 表，则 $L B$ 显然是全局最优代价 $C^*$ 的下界。ECBS 顶层算法的 $FOC A L$ 表定义如下：

$\{n | n \in OPEN,n.cost \le LB \cdot w\}$

由于 $L B$ 是全局最优代价 $C^*$ 的下界，那么 $FOC A L$ 里的所有节点的代价 $cos t$ 都小于等于 $w$ 倍最优代价，因此，全局代价也小于等于 $\cdot C^*$ 。

至此，ECBS 在顶层和底层的次优界限完成了统一。ECBS 既有 $BCBS (1, w)$ 底层算法的灵活性，顶层也不局限于 $BCBS(w_H,1)$ 的固定参数的 $FOC A L$ 表，而是随着底层算法的搜索情况而改变。

总结

本文所述的三个算法都是完备的。ECBS 为推进 MAPF 算法发展做出了重大贡献。顺带一提，这个研究组居然在学术论文里使用文学笔法，这是非常罕见的。贴一下作者的结尾句：Time will tell how these new methods compare in general to traditional search approaches.文章来源地址https://www.toymoban.com/news/detail-745857.html

到了这里，关于ECBS多机器人路径规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！