實例講解

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

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

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

圖3 CBS搜索過程

CBS開始時沒有沖突約束，每個機器人按照各自的路徑規(guī)劃，得到節(jié)點1所示的路徑結果，由于路徑產生沖突，需要生成新的分支（節(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得到有效路徑，搜索過程可以結束。

待改進的地方

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

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

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

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