1 前言

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

作者：K.Fire ?| 來(lái)源：計(jì)算機(jī)視覺(jué)工坊

添加微信：dddvisiona，備注：自動(dòng)駕駛，拉你入群。文末附行業(yè)細(xì)分群。

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

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

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

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

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

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

2 隨機(jī)碰撞法

隨機(jī)碰撞法本質(zhì)上是一種用時(shí)間換取空間的算法，它的思路是是機(jī)器人選擇任意一個(gè)初始方向，驅(qū)動(dòng)機(jī)器人在環(huá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ū)域稱為細(xì)胞，這些細(xì)胞的并集剛好填滿整個(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ū)域地圖，然后用一條豎直的切割線從左至右掃描過(guò)整個(gè)區(qū)域，黨切割線與多邊形障礙物的頂點(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]、線掃分割法等。這里不過(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ì)算周圍神經(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ì)算周圍神經(jīng)元的活性值，選擇其中活性值最大的柵格作為下一步位置。生物激勵(lì)法的優(yōu)點(diǎn)是適用性好，且在避障和實(shí)時(shí)性方面表現(xiàn)較好，缺點(diǎn)是可能會(huì)導(dǎo)致路徑重復(fù)率較高。

5 模板法

模板法由Neumann de Carvalho R等人提出，依賴于二維環(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)域的車載傳感器空間同步（標(biāo)定）》。

6 智能算法

Wang[5]將遺傳算法與牛耕單元分解法結(jié)合，當(dāng)使用分割線將整個(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ū)域。

7 參考文獻(xiàn)

[1] Choset, H. Coverage of Known Spaces: The Boustrophedon Cellular Decomposition[J].?Autonomous Robots?9, 247–253 (2000). https://doi.org/10.1023/A:1008958800904

[2] Rekleitis, I., New, A.P., Rankin, E.S.?et al.?Efficient Boustrophedon Multi-Robot Coverage: an algorithmic approach[J].?Ann Math Artif Intell?52, 109–142 (2008). https://doi.org/10.1007/s10472-009-9120-2

[3] Acar EU, Choset H, Rizzi AA, Atkar PN, Hull D. Morse Decompositions for Coverage Tasks[J].?The International Journal of Robotics Research. 2002;21(4):331-344. doi:10.1177/027836402320556359

[4] Acar EU, Choset H. Sensor-based Coverage of Unknown Environments: Incremental Construction of Morse Decompositions[J].?The International Journal of Robotics Research. 2002;21(4):345-366. doi:10.1177/027836402320556368

[5] Z. Chibin, W. Xingsong and D. Yong, Complete Coverage Path Planning Based on Ant Colony Algorithm[C], 2008 15th International Conference on Mechatronics and Machine Vision in Practice, Auckland, New Zealand, 2008, pp. 357-361, doi: 10.1109/MMVIP.2008.4749559.

[6] Gabriely, Y., Rimon, E. Online Scan Coverage of Grid Environments by a Mobile Robot[J]. In: Boissonnat, JD., Burdick, J., Goldberg, K., Hutchinson, S. (eds) Algorithmic Foundations of Robotics V. 2004. Springer Tracts in Advanced Robotics, vol 7. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45058-0_25

目前工坊已經(jīng)建立了3D視覺(jué)方向多個(gè)社群，包括SLAM、工業(yè)3D視覺(jué)、自動(dòng)駕駛方向，細(xì)分群包括：[工業(yè)方向]三維點(diǎn)云、結(jié)構(gòu)光、機(jī)械臂、缺陷檢測(cè)、三維測(cè)量、TOF、相機(jī)標(biāo)定、綜合群；[SLAM方向]多傳感器融合、ORB-SLAM、激光SLAM、機(jī)器人導(dǎo)航、RTK|GPS|UWB等傳感器交流群、SLAM綜合討論群；[自動(dòng)駕駛方向]深度估計(jì)、Transformer、毫米波|激光雷達(dá)|視覺(jué)攝像頭傳感器討論群、多傳感器標(biāo)定、自動(dòng)駕駛綜合群等。[三維重建方向]NeRF、colmap、OpenMVS等。除了這些，還有求職、硬件選型、視覺(jué)產(chǎn)品落地等交流群。大家可以添加小助理微信: dddvisiona，備注：加群+方向+學(xué)校|公司, 小助理會(huì)拉你入群。