CBS基本操作過程介紹

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

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

CBS基本操作過程

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

高層次的搜索過程

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

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

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

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

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

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

低層次的搜索過程

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

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

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

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

通過高低兩個搜索過程不斷地運行，當問題的復雜程度不高時，能夠及時得到比較好的結果。