多機(jī)器人路徑規(guī)劃

多智能體路徑規(guī)劃 (Multi-Agent Path Finding, MAPF) 研究多智能體的路徑規(guī)劃算法，為多機(jī)系統(tǒng)規(guī)劃無(wú)沖突的最優(yōu)路徑。

ECBS 算法由 CBS(Conflict-Based Search) 算法改進(jìn)而來(lái), 對(duì) CBS算法的介紹可以參考筆者的這篇文章CBS多機(jī)器人路徑規(guī)劃(Conflict-Based Search)。CBS 算法給出 MAPF 問(wèn)題的全局最優(yōu)結(jié)果，ECBS 算法給出 MAPF 問(wèn)題的有界次優(yōu)結(jié)果。ECBS 之于 CBS，正如 $A_{?}^{?}$ 之于 $A^{?}$，獲得有限損失的次優(yōu)結(jié)果，換來(lái)極大的速度提升。

參考文獻(xiàn)：

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

ECBS(Enhanced CBS)

ECBS 基于 CBS 和 $A_{?}^{?}$，如果對(duì) $A_{?}^{?}$ 不熟悉可以參考筆者的這篇文章 A*算法及其變種。

ECBS 沿用 CBS 框架，主要對(duì) CBS 的頂層和底層搜索算法作出改進(jìn)，論文由淺入深，依次介紹了次優(yōu)的 GCBS(Greedy-CBS)、有界次優(yōu)的 BCBS(Bounded Suboptimal CBS)，以及對(duì) BCBS 作出更靈活改進(jìn)的 ECBS(Enhanced CBS)，本文將依次介紹這些算法。

GCBS(Greedy-CBS)

在 CBS 中，頂層和底層都是最優(yōu)搜索，GCBS 通過(guò)松弛(relax)頂層和底層的搜索條件提升算法效率。

GCBS 不是最優(yōu)的，但是完備的。完備性的證明可以參考原論文，和 CBS 證明完備性的思想一樣。

頂層松弛

CBS 的頂層搜索啟發(fā)函數(shù)規(guī)則為全局 $cost$ 最小，GCBS 的頂層啟發(fā)函數(shù)的規(guī)則設(shè)計(jì)為基于 $solution$ 中的沖突($conflicts$)數(shù)量，用 $h_c$ 表示，作者給出了以下幾個(gè)啟發(fā)函數(shù)示例：

• $h_1$：全局沖突數(shù)量：計(jì)算當(dāng)前分支節(jié)點(diǎn)中 $solution$ 的沖突數(shù)量
• $h_2$：發(fā)生沖突的機(jī)器人數(shù)量：計(jì)算前分支節(jié)點(diǎn)中路徑里存在沖突的機(jī)器人數(shù)量
• $h_3$：發(fā)生沖突的機(jī)器人對(duì)(pairs)：計(jì)算前分支節(jié)點(diǎn)中路徑里存在沖突的機(jī)器人對(duì)的數(shù)量
• $h_4$：頂點(diǎn)覆蓋(Vertex cover)：定義一個(gè)圖 graph：其中機(jī)器人為頂點(diǎn)(nodes)，路徑之間有沖突的機(jī)器人之間有邊(edges)相連。事實(shí)上，$h_2$ 描述了頂點(diǎn)，$h_3$ 描述了邊，$h_4$ 計(jì)算頂點(diǎn)覆蓋數(shù)。
• $h_5$：可變啟發(fā)式：在特定的條件下用特定的啟發(fā)函數(shù)，更有魯棒性，但編程比較麻煩。

作者聲稱，實(shí)測(cè)中 $h_5$ 的效果最好。但由于 $h_3$ 兼顧優(yōu)秀性能和簡(jiǎn)潔性，介紹算法時(shí)選擇 $h_3$ 作為實(shí)際的啟發(fā)函數(shù)。在下文，所有的 $h_c$ 都代表 $h_3$。

底層松弛

松弛底層，最簡(jiǎn)單的方法就是把尋路算法改成次優(yōu)的，例如 WA*。作者提到，這樣看起來(lái)單機(jī)器人搜索變快了，但次優(yōu)算法會(huì)得出更長(zhǎng)的路徑結(jié)果，增加了未來(lái)頂層需要解決的潛在沖突數(shù)(單條路徑越長(zhǎng)，這些路徑之間產(chǎn)生沖突的可能性就越大)。

作者提出，在每次進(jìn)行當(dāng)前機(jī)器人的路徑規(guī)劃前，考慮之前其他機(jī)器人的路徑，盡量提前躲避。也就是把之前其他機(jī)器人的路徑當(dāng)成障礙物，然后進(jìn)行時(shí)空 A*(space-time A*) 搜索。這樣就能直接在底層盡量的減小路徑之間的沖突數(shù)量。

這種思想其實(shí)與基于優(yōu)先級(jí)的搜索(Prioritized-Based Search, PBS)有點(diǎn)像：按順序?qū)Χ嗯_(tái)機(jī)器人進(jìn)行規(guī)劃，先進(jìn)行規(guī)劃的機(jī)器人的路徑作為障礙物信息附加在后進(jìn)行規(guī)劃的機(jī)器人的約束條件中。PBS 的底層可以用任意一種單機(jī)規(guī)劃算法。

為什么說(shuō) GCBS 的底層和 PBS 有點(diǎn)像 而不是一樣呢，因?yàn)闉榱?strong>快速計(jì)算出結(jié)果， GCBS 的底層只是盡量（傾向于）提前躲避障礙物，并不是完全躲避，未能躲避而產(chǎn)生的沖突交給頂層解決。

BCBS(Bounded Suboptimal CBS)

CBS 的頂層和底層搜索都使用 A* ，BCBS 的頂層和底層搜索都使用 $FOCALSearch(A_{?}^{?})$，對(duì) $A_{?}^{?}$ 不熟悉可以參考筆者的這篇文章 A*算法及其變種。

首先，定義 $focal$-$search(f_1,f_2)$ 表示使用啟發(fā)函數(shù) $f_1,f_2$ 的 $FocalSearch$，其中，$f_1$用于選擇哪些節(jié)點(diǎn)被選入 $FOCAL$表，$f_2$用于選擇從 $FOCAL$表中選擇哪一個(gè)節(jié)點(diǎn)作為下一步擴(kuò)展。

頂層搜索

對(duì)約束樹進(jìn)行 $focal$-$search(g,h_c)$，其中, $g(n)$ 表示當(dāng)前節(jié)點(diǎn)的 $cost$，$h_c(n)$ 表示 $h_3(n)$(發(fā)生沖突的機(jī)器人對(duì)的數(shù)量)。

底層搜索

在底層應(yīng)用 $focal$-$search(f,h_c)$，其中 $f(n)=g(n)+h(n)$ 與 A* 中的 $f(n)$ 一致，$h_c(n)$ 表示 $h_3(n)$ (考慮在節(jié)點(diǎn) n 的路徑?jīng)_突)

定義 $BCBS(w_H,w_L)$ 表示在 頂層的 $focalsearch$ 使用 $w_H$ 參數(shù)，在底層的 $focalsearch$ 使用 $w_L$ 參數(shù) ($w=1+?$)。

根據(jù)定義，$BCBS(w_H,w_L)$有如下特例：

• $w_L=1$，即 $BCBS(w_H,1)$ ：表示僅在頂層使用 $focalsearch$
• $w_H=1$，即 $BCBS(1,w_L)$ ：表示僅在底層使用 $focalsearch$
• $w_H=w_L=1$，即 $BCBS(1,1)$ ：BCBS 退化為 CBS
• $w_H=w_L=\infty$，即 $BCBS(\infty ,\infty )$ ：BCBS 退化為 GCBS，此時(shí)，$FOCAL$ 表與 $Open$ 表一致。

$BCBS(w_H,w_L)$ 能保證最終的全局 $cost\le w_H?w_L?C^{?}$，其中，$C^{?}$ 為最優(yōu) $cost$ (也就是 CBS 的結(jié)果)。

ECBS(Enhanced CBS)

提出新方法的第一步是抨擊舊方法。剛介紹完 BCBS，作者馬上提到，BCBS 中關(guān)于 $w_L$ 和 $w_H$ 的調(diào)參是非常有講究的，需要大量的調(diào)試經(jīng)驗(yàn)，并且在整個(gè)搜索過(guò)程中 $w_L$ 和 $w_H$ 完全固定，會(huì)影響算法性能。

為了解決這個(gè)問(wèn)題，ECBS 應(yīng)運(yùn)而生。

ECBS 的底層搜索算法與 $BCBS(1,w)$ 一致。以下介紹 ECBS 的頂層搜索算法。

設(shè)在 CBS 底層搜索中，為機(jī)器人 $a_i$ 搜索路徑時(shí)使用的 $OPEN$ 表為 $OPE{N}_i$，則 $OPE{N}_i$ 中的最小 $f$ 值 $f_{min}(i)$ 為 機(jī)器人 $a_i$ 最優(yōu)路徑代價(jià) $cost$ 的下界(Lower Bound)。對(duì)一個(gè)約束樹節(jié)點(diǎn)(CT node) $n$，設(shè) $LB(n)={\sum }_{i=1}^k{f}_{min}(i)$，根據(jù)定義有 $LB(n)\le n.cost\le LB(n)?w$。

在 ECBS 中，每一個(gè) CT node 傳遞兩個(gè)值給頂層算法：

• $n.cost$
• $LB(n)$

設(shè) $LB=min(LB(n)|n\in OPEN)$ ，其中 $OPEN$ 為頂層搜索中的 $OPEN$ 表，則 $LB$ 顯然是全局最優(yōu)代價(jià) $C^{?}$ 的下界。ECBS 頂層算法的 $FOCAL$ 表定義如下：

F O C A L = { n ∣ n ∈ O P E N , n . c o s t ≤ L B ? w } FOCAL = \{n | n \in OPEN,n.cost \le LB \cdot w\} FOCAL={n∣n∈OPEN,n.cost≤LB?w}

由于 $LB$ 是全局最優(yōu)代價(jià) $C^{?}$ 的下界，那么 $FOCAL$ 里的所有節(jié)點(diǎn)的代價(jià) $cost$ 都小于等于 $w$ 倍最優(yōu)代價(jià)，因此，全局代價(jià)也小于等于 $w?C^{?}$。

至此，ECBS 在頂層和底層的次優(yōu)界限完成了統(tǒng)一。ECBS 既有 $BCBS(1,w)$ 底層算法的靈活性，頂層也不局限于 $BCBS(w_H,1)$ 的固定參數(shù)的 $FOCAL$ 表，而是隨著底層算法的搜索情況而改變。

總結(jié)

本文所述的三個(gè)算法都是完備的。ECBS 為推進(jìn) MAPF 算法發(fā)展做出了重大貢獻(xiàn)。 順帶一提，這個(gè)研究組居然在學(xué)術(shù)論文里使用文學(xué)筆法，這是非常罕見的。貼一下作者的結(jié)尾句：Time will tell how these new methods compare in general to traditional search approaches.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-745857.html

到了這里，關(guān)于ECBS多機(jī)器人路徑規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！