實(shí)例講解

以下將通過(guò)一個(gè)簡(jiǎn)單的實(shí)例講解CBS的基本過(guò)程，實(shí)例如圖2所示。

圖2 初始和目標(biāo)狀態(tài)

CBS的搜索過(guò)程如圖3所示。

圖3 CBS搜索過(guò)程

CBS開(kāi)始時(shí)沒(méi)有沖突約束，每個(gè)機(jī)器人按照各自的路徑規(guī)劃，得到節(jié)點(diǎn)1所示的路徑結(jié)果，由于路徑產(chǎn)生沖突，需要生成新的分支（節(jié)點(diǎn)2和節(jié)點(diǎn)3），節(jié)點(diǎn)2添加沖突為：1號(hào)在1時(shí)刻（從0時(shí)刻開(kāi)始）不進(jìn)入位置3，節(jié)點(diǎn)3添加沖突為：2號(hào)在1時(shí)刻不進(jìn)入位置3。

在約束的作用下進(jìn)行低層次的搜索，節(jié)點(diǎn)2和節(jié)點(diǎn)3都搜索到了路徑，但發(fā)生了新的沖突，由于節(jié)點(diǎn)2和節(jié)點(diǎn)3的代價(jià)值相等，可以從左邊的節(jié)點(diǎn)（節(jié)點(diǎn)2）開(kāi)始生成新的分支：節(jié)點(diǎn)4和節(jié)點(diǎn)5，然后對(duì)節(jié)點(diǎn)4和節(jié)點(diǎn)5進(jìn)行低層次的搜索得到路徑，最終節(jié)點(diǎn)5得到有效路徑，搜索過(guò)程可以結(jié)束。

待改進(jìn)的地方

雖然CBS做為一個(gè)比較優(yōu)秀的多機(jī)器人路徑規(guī)劃器，依然存在一些缺點(diǎn)影響它在實(shí)際中的應(yīng)用。

1.當(dāng)環(huán)境擁擠，機(jī)器人數(shù)目多時(shí)，計(jì)算時(shí)間比較長(zhǎng)，甚至無(wú)解；

2.無(wú)法判斷有些情況是否無(wú)解，導(dǎo)致程序無(wú)法結(jié)束運(yùn)行，且一直消耗系統(tǒng)內(nèi)存；

3.實(shí)際情況下，機(jī)器人需要原地旋轉(zhuǎn)、有加減速度、運(yùn)行存在誤差，需要后續(xù)進(jìn)一步處理才能在實(shí)際中運(yùn)行；