CBS多機(jī)器人路徑規(guī)劃實(shí)例講解

實(shí)例講解

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

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

CBS的搜索過程如圖3所示。

圖3 CBS搜索過程

CBS開始時(shí)沒有沖突約束，每個(gè)機(jī)器人按照各自的路徑規(guī)劃，得到節(jié)點(diǎn)1所示的路徑結(jié)果，由于路徑產(chǎn)生沖突，需要生成新的分支（節(jié)點(diǎn)2和節(jié)點(diǎn)3），節(jié)點(diǎn)2添加沖突為：1號在1時(shí)刻（從0時(shí)刻開始）不進(jìn)入位置3，節(jié)點(diǎn)3添加沖突為：2號在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）開始生成新的分支：節(jié)點(diǎn)4和節(jié)點(diǎn)5，然后對節(jié)點(diǎn)4和節(jié)點(diǎn)5進(jìn)行低層次的搜索得到路徑，最終節(jié)點(diǎn)5得到有效路徑，搜索過程可以結(jié)束。

待改進(jìn)的地方

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

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

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

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