作者：K.Fire ?| 來(lái)源：

1 前言

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

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

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

機(jī)器人必須通過(guò)目標(biāo)區(qū)域內(nèi)除障礙物外的所有點(diǎn)，完全覆蓋目標(biāo)區(qū)域；

機(jī)器人在覆蓋過(guò)程中應(yīng)盡量避免路徑重復(fù)；

為了控制方便，應(yīng)盡量使用簡(jiǎn)單的運(yùn)動(dòng)軌跡(例如，直線(xiàn)或圓)；

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

2 隨機(jī)碰撞法

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

在實(shí)際使用過(guò)程中，掃地機(jī)器人常常會(huì)因?yàn)閯?dòng)態(tài)的障礙物等信息陷入困局，調(diào)用隨機(jī)路徑覆蓋掙脫此困局也是一種常見(jiàn)的手段。

3 單元分解法

單元分解法是將整個(gè)空間中的自由區(qū)域通過(guò)某種方法分割為簡(jiǎn)單且無(wú)重疊區(qū)域的子區(qū)域，每一部分子區(qū)域稱(chēng)為細(xì)胞，這些細(xì)胞的并集剛好填滿(mǎn)整個(gè)自由空間，機(jī)器人使用簡(jiǎn)單的覆蓋方式(比如往復(fù)運(yùn)動(dòng)或螺旋運(yùn)動(dòng))對(duì)每個(gè)子區(qū)域進(jìn)行覆蓋，當(dāng)完成每個(gè)子區(qū)域的覆蓋后，就實(shí)現(xiàn)了整個(gè)區(qū)域的全覆蓋。

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

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

4 生物激勵(lì)法

Yang和Luo將生物激勵(lì)的神經(jīng)網(wǎng)絡(luò)模型應(yīng)用在清潔機(jī)器人的全覆蓋路徑規(guī)劃工作上。他們首先對(duì)環(huán)境進(jìn)行建模，利用柵格地圖對(duì)環(huán)境進(jìn)行表示，每一個(gè)柵格點(diǎn)對(duì)應(yīng)一個(gè)神經(jīng)元細(xì)胞，并提出了分流方程用來(lái)計(jì)算周?chē)窠?jīng)元對(duì)當(dāng)前神經(jīng)元的激勵(lì)或抑制程度，分流方程如下式所示。

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

機(jī)器人處于某一柵格時(shí)，會(huì)計(jì)算周?chē)窠?jīng)元的活性值，選擇其中活性值最大的柵格作為下一步位置。生物激勵(lì)法的優(yōu)點(diǎn)是適用性好，且在避障和實(shí)時(shí)性方面表現(xiàn)較好，缺點(diǎn)是可能會(huì)導(dǎo)致路徑重復(fù)率較高。

5 模板法

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

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

6 智能算法

Wang[5]將遺傳算法與牛耕單元分解法結(jié)合，當(dāng)使用分割線(xiàn)將整個(gè)自由空間劃分為子區(qū)域后，通過(guò)遺傳算法對(duì)各子區(qū)域進(jìn)行編碼，簡(jiǎn)歷子區(qū)域與子區(qū)域之間的基點(diǎn)信息，并通過(guò)遺傳算法得到最優(yōu)覆蓋序列，在每個(gè)子區(qū)域內(nèi)以往復(fù)運(yùn)動(dòng)的形式實(shí)現(xiàn)覆蓋，將CCPP問(wèn)題轉(zhuǎn)化為旅行商問(wèn)題(TSP)。

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

編輯：黃飛

?

?