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

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

CBS基本操作過(guò)程

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

高層次的搜索過(guò)程

高層次的搜索過(guò)程主要有兩個(gè)作用：

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

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

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

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

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

低層次的搜索過(guò)程

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

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

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

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

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