單個機(jī)器人通過路徑規(guī)劃、運(yùn)動控制，能夠躲避環(huán)境中的障礙物，但會面臨一個嚴(yán)峻的問題。當(dāng)一個場景中存在多輛移動機(jī)器人時，即使每個機(jī)器人都有避障策略，也很容易就會造成道路擁堵、阻塞的情況，而且會隨著機(jī)器人數(shù)量的增加變得更嚴(yán)峻。

就像如果道路沒有交通指揮系統(tǒng)，人們就會將有些道路擠得水瀉不通，形成死鎖的局面。為解決此問題，一種基于沖突的多機(jī)器人路徑搜索方法（Conflict-Base search）應(yīng)運(yùn)而生。

CBS基本操作過程

CBS由2個搜索過程組成，底層次的搜索過程負(fù)責(zé)為每個機(jī)器人搜索出一條有效路徑，高層次的負(fù)責(zé)檢查路徑?jīng)_突，并選擇出其中代價值最小的分支重新進(jìn)行底層次的路徑搜索，直到高層次的搜索過程發(fā)現(xiàn)有效路徑為止。

高層次的搜索過程

高層次的搜索過程主要有兩個作用：

1.檢查路徑之間的沖突，并生成新的分支；

2.選出代價值最小的分支進(jìn)行低層次的搜索；

路徑之間的沖突分為同一時刻占據(jù)同一個節(jié)點(diǎn)和同一時刻調(diào)換位置兩種類型的沖突，如圖（1）所示

當(dāng)兩條路徑在n時刻檢測到存在沖突的情況時，需要生成兩個分支：第一個機(jī)器人在n時刻不能進(jìn)入該節(jié)點(diǎn)和第二個機(jī)器人在n時刻不能進(jìn)入該節(jié)點(diǎn)。

在上述兩個過程完成后，選擇其中代價值最小的節(jié)點(diǎn)進(jìn)行低層次的路徑搜索過程。

低層次的搜索過程

低層次的搜索過程與普通的路徑規(guī)劃方法類似，如Dirkstra、A*等。但其不同之處在于：

1.搜索過程中需要考慮額外的約束，即高層次搜索中添加的沖突；

2.在搜索過程中需要考慮原地等待的情況；

由于在搜索過程中需要考慮到等待的情況，因此將時間也做為一個維度加入到路徑搜索過程中，通常每次擴(kuò)展搜索區(qū)域時，時間增加一個單位長度。

通過高低兩個搜索過程不斷地運(yùn)行，當(dāng)問題的復(fù)雜程度不高時，能夠及時得到比較好的結(jié)果。