實例講解

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

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

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

圖3 CBS搜索過程

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

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

待改進的地方

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

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

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

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