全覆蓋路徑規(guī)劃算法(CCPP)工作原理解析

作者：K.Fire ?| 來源：

1 前言

全覆蓋路徑規(guī)劃(complete coverage path planning, CCPP)問題的任務是確定一條路徑，該路徑在避開障礙物的情況下通過一個區(qū)域或一定空間范圍內的所有點。

Choset根據環(huán)境地圖是否先驗已知，將全覆蓋路徑規(guī)劃算法分為“在線式”和“離線式”兩類。離線式CCPP算法只依賴于靜態(tài)環(huán)境信息，并且假設環(huán)境是先驗已知的。然而，在許多情況下，假設對環(huán)境有充分的先驗知識可能是不現實的。在線式CCPP算法不假設對要覆蓋的環(huán)境有充分的先驗知識，而是利用傳感器數據實時掃描目標空間。因此，這些后期算法也被稱為基于傳感器的覆蓋算法。這里也推薦「3D視覺工坊」新課程《深度剖析面向自動駕駛領域的車載傳感器空間同步（標定）》。

根據CCPP算法工作原理不同，可以分為隨機碰撞法、單元分解法、生物激勵法、模板法、智能算法等，但CCPP算法都應該滿足覆蓋必須滿足的要求，主要有：

機器人必須通過目標區(qū)域內除障礙物外的所有點，完全覆蓋目標區(qū)域；

機器人在覆蓋過程中應盡量避免路徑重復；

為了控制方便，應盡量使用簡單的運動軌跡(例如，直線或圓)；

在允許條件下，獲得一條“最優(yōu)”路徑(路線總長度最短或能量消耗最少)；

2 隨機碰撞法

隨機碰撞法本質上是一種用時間換取空間的算法，它的思路是是機器人選擇任意一個初始方向，驅動機器人在環(huán)境中直線行走，覆蓋這條直線范圍中的面積，當機器人檢測到障礙物時，使機器人順時針轉過一定角度，并重復上述過程。這種策略的覆蓋面積具有極大的隨機性，從理論上講，給定充足的時間，能夠使機器人覆蓋足夠的空間范圍，但這種方法非常低效。這種方法的優(yōu)點是：不需要復雜的定位傳感器，通常只需要配備紅外傳感器，也不需要耗費巨大的計算資源；這種方法的缺點是：在局部范圍內存在大量的重復路徑，且環(huán)境適用性差，當環(huán)境中有多個子場景時，特別是兩個子場景之間通過狹長的走廊連接，隨機碰撞法可能會耗費大量的無用時間才能夠從一個區(qū)域走到另外一個區(qū)域。

在實際使用過程中，掃地機器人常常會因為動態(tài)的障礙物等信息陷入困局，調用隨機路徑覆蓋掙脫此困局也是一種常見的手段。

3 單元分解法

單元分解法是將整個空間中的自由區(qū)域通過某種方法分割為簡單且無重疊區(qū)域的子區(qū)域，每一部分子區(qū)域稱為細胞，這些細胞的并集剛好填滿整個自由空間，機器人使用簡單的覆蓋方式(比如往復運動或螺旋運動)對每個子區(qū)域進行覆蓋，當完成每個子區(qū)域的覆蓋后，就實現了整個區(qū)域的全覆蓋。

以梯形分解法為例，它是最簡單的精確細胞分解方法。該方法先使機器人沿著空間的邊緣行走一圈，構建整個區(qū)域地圖，然后用一條豎直的切割線從左至右掃描過整個區(qū)域，黨切割線與多邊形障礙物的頂點相遇時，就會分解出一個子區(qū)域，這樣整個自由空間就被分解為諸多子區(qū)域，每個子區(qū)域都是梯形。機器人在每個子區(qū)域中進行往復運動對子區(qū)域進行覆蓋。梯形分解法如圖所示。

其他代表方法有：牛耕單元分解法[1,2]、莫爾斯分解法[3,4]、線掃分割法等。這里不過多敘述，感興趣可以閱讀參考文獻。

4 生物激勵法

Yang和Luo將生物激勵的神經網絡模型應用在清潔機器人的全覆蓋路徑規(guī)劃工作上。他們首先對環(huán)境進行建模，利用柵格地圖對環(huán)境進行表示，每一個柵格點對應一個神經元細胞，并提出了分流方程用來計算周圍神經元對當前神經元的激勵或抑制程度，分流方程如下式所示。

其中xi表示第i個神經元的狀態(tài)；A是非負常數，表示神經元活性的衰減速率；B、D代表神經元狀態(tài)的上下限；Ii代表外部輸入，ωij表示第i個神經元與第j個神經元的連接權值，一般由兩個神經元之間的距離計算得到。第i個神經元的活性值連接圖如圖所示。

機器人處于某一柵格時，會計算周圍神經元的活性值，選擇其中活性值最大的柵格作為下一步位置。生物激勵法的優(yōu)點是適用性好，且在避障和實時性方面表現較好，缺點是可能會導致路徑重復率較高。

5 模板法

模板法由Neumann de Carvalho R等人提出，依賴于二維環(huán)境地圖的先驗知識，并可以處理地圖上沒有表示的意外障礙，他們將機器人的運動行為預先規(guī)定為七種固定的模板，如下圖所示。這些模板包含了機器人在地圖中可能遇到的所有情況，機器人根據模板在地圖中運動，最終實現地圖的全覆蓋。

模板法的優(yōu)點是原理簡單，計算消耗小，可以處理動態(tài)障礙物；缺點是需要地圖的先驗知識，適用性較差，智能度較低。這里也推薦「3D視覺工坊」新課程《深度剖析面向自動駕駛領域的車載傳感器空間同步（標定）》。

6 智能算法

Wang[5]將遺傳算法與牛耕單元分解法結合，當使用分割線將整個自由空間劃分為子區(qū)域后，通過遺傳算法對各子區(qū)域進行編碼，簡歷子區(qū)域與子區(qū)域之間的基點信息，并通過遺傳算法得到最優(yōu)覆蓋序列，在每個子區(qū)域內以往復運動的形式實現覆蓋，將CCPP問題轉化為旅行商問題(TSP)。

Zhang[6]將蟻群算法引入單元分解法，根據兩個子區(qū)域之間的連通性信息定義距離矩陣，并采用蟻群算法根據距離矩陣優(yōu)化覆蓋順序，他們的實驗結果表明，這樣結合的算法不僅能保證覆蓋所有工作空間，而且規(guī)劃路徑更短，路徑重疊率更小，規(guī)劃效率更高，但對于復雜環(huán)境，很難避開障礙物附近的恢復區(qū)域。

編輯：黃飛

?

?