移動機器人全覆蓋信度函數路徑規劃算法

曹翔，俞阿龍

移動機器人全覆蓋路徑規劃是地形探測、地面資源勘探、地面清潔、戰地偵查等任務的重要組成部分[1-3]。作為移動機器人領域核心研究問題之一，全覆蓋路徑規劃一直受到廣泛關注。移動機器人完成全覆蓋路徑規劃需要解決3個問題[4-7]：1)需遍歷工作區域內除障礙物以外的全部區域；2)在遍歷過程中有效避開所有障礙物；3)在遍歷過程中要盡量避免路徑重復，縮短移動距離。迄今為止，關于全覆蓋路徑規劃的方法多種多樣，各有優劣，主要的方法可以分為：行為覆蓋法[8-9]、區域分割法[10-12]、神經網絡法[13-16]等。

2000年Balch等[8]提出一種移動機器人行為覆蓋路徑規劃方法，機器人根據簡單的移動行為，嘗試性地覆蓋工作區域，如果遇到障礙物，則執行對應的轉向命令。這種方法是一種以時間換空間的低成本策略，如不計時間可以達到全覆蓋。該算法無需了解整個作業區全貌，也不用依賴過多的傳感器，處理器運算量也很小，是一種性價比很高的方案。但是，行為全覆蓋算法工作效率低，路徑規劃策略過于簡單，面對復雜地形機器人經常無法逃離死區[9]。

為了使機器人能夠逃離死區，同時減少算法的計算量，Jin等[10]提出一種基于時空信息的全局導航與局部導航組合的算法。該算法一方面能夠通過局部計算代替不必要的全局計算，減少了實時決策時局部最優導航的計算量；另一方面通過分層的方式使機器人能夠逃離死區。但是在局部與全局的轉換過程中，當周圍沒有未覆蓋的區域時，機器人需要擴大鄰近區域的面積來尋找未覆蓋區域，這將導致覆蓋效率的降低，尤其是當未覆蓋區域距離機器人較遠時[11-12]。

近年來，神經網絡算法被應用到全覆蓋路徑規劃中[13-14]。利用神經網絡的自學習、并行性等特性，增強機器人的“智能”，提高覆蓋效率。受神經網絡結構與柵格地圖單元類似的啟發，加拿大學者S. X.Yang[15-16]等提出一種基于生物啟發神經網絡的移動機器人全覆蓋路徑規劃算法，將需要全覆蓋的二維柵格地圖單元與生物啟發神經網絡的神經元一一對應起來，機器人實現全覆蓋的實時路徑規劃是由神經元的活性值和機器人的上一位置產生的。該算法完全根據柵格地圖單元的性質(未搜索單元、已搜索單元還是障礙物)，決定神經元的輸入，直接計算神經元的活性值，不存在神經網絡學習過程，算法實時性好，同時可以自動避障與逃離死區。

最近，Yan[17]等在文獻[15-16]的基礎上，進一步將生物啟發神經網絡應用到水下機器人全覆蓋路徑規劃中。該算法根據聲吶傳感器獲取的信息，利用信息融合技術構建動態水下環境地圖，根據水下感知的環境地圖性質確定生物啟發神經網絡中神經元的活性值，水下機器人通過比較鄰近神經元活性值進行路徑規劃，完成對工作區域的全覆蓋，該方法將水下環境的地圖構建與全覆蓋路徑規劃有機結合，得到一套完整的水下機器人感知環境與全覆蓋搜救方法。

但是基于生物啟發神經網絡的全覆蓋算法計算量大，同時此種方法中神經網絡模型的衰減率等參數沒有最優值，在實現算法時只能通過反復實驗確定，參數的設定存在人為不確定因素，從而影響其在線應用[18]。

對此，本文在柵格地圖的基礎上，引入方向信度函數的概念，提出一種移動機器人全覆蓋信度函數路徑規劃策略。該策略計算量小、路徑重復率低，使得機器人不僅能夠完成工作區域全覆蓋任務，而且能夠快速逃離死區。算法包括3個部分：1)根據地面環境的狀態對柵格地圖進行賦值，使用不同的函數值表示障礙物、已覆蓋柵格和未覆蓋柵格；2)引入方向信度函數對柵格信度函數值進行優化；3)機器人根據柵格信度函數進行覆蓋路徑規劃。本文提出的基于柵格信度函數的移動機器人全覆蓋路徑規劃算法能夠實現動態工作區域的全覆蓋，與生物啟發神經網絡算法相比有更短的覆蓋路徑。

1 基于柵格信度函數的全覆蓋路徑規劃算法

全覆蓋路徑規劃是指移動機器人以盡可能低的路徑重復率遍歷工作區域中的全部可到達點，它包含兩個方面的技術指標，即區域覆蓋率和路徑重復率。本文以弓形路徑移動方式為基礎，引入方向信度函數對機器人移動路徑進行優化，完成對工作區域的全覆蓋的同時降低路徑重復率。

1.1 柵格位置性質函數

為了避免機器人與障礙物發生碰撞，防止機器人對同一柵格單元重復覆蓋，將對柵格地圖進行賦值。依據每個柵格的性質賦不同的信度函數值，表示出每個柵格的狀態信息[19-22]。本節以二維的柵格地圖為例說明怎樣對柵格進行信度賦值。圖1(a)顯示的是一個二維的柵格地圖，工作區域被分成了9個柵格，其中黑色柵格表示被障礙物占領，白色柵格表示自由空間，Pc表示機器人當前所在的位置。根據式(1)對柵格位置性質函數xj賦值，如柵格6表示障礙物，則被賦值為-；柵格 1、2、3、4、5、7、8表示自由未被覆蓋單元，則被賦值為1；柵格Pc表示已被覆蓋單元，則被賦值為0.5。

式中xj表示第j個柵格的位置性質函數值。同時為了避免同一個柵格的反復覆蓋，在此約定柵格被多覆蓋一次，其位置性質函數值就減少0.5。假如柵格Pc被覆蓋過一次，其位置性質函數值為0.5；如果柵格Pc被覆蓋了兩次，其位置性質函數值為0。

圖1 柵格地圖Fig. 1 The grid map

1.2 方向信度函數

為了降低路徑重復率，提高覆蓋效率，對機器人的移動路徑進行優化，引入方向信度函數。定義為

式(2)中方向信度函數的定義分為兩種情況，當機器人未陷入死區時，是機器人當前位置與下一位置移動方向角之差的函數，是關于前一位置、當前位置和可能為下一位置的函數。此時方向信度函數為，機器人移動方向角之差表示為

圖2 未陷入死區方向信度函數Fig. 2 The direction belief function in the free zone

機器人陷入死區是指它的周邊相鄰區域，或者是邊界，或者是障礙物，或者是已覆蓋過的區域。只有從死區逃離出來，才能繼續完成全覆蓋任務，而逃離死區的路徑，直接決定著全覆蓋的路徑重復率。當機器人陷入死區后，為了讓機器人以盡可能短的路徑逃離死區，本文提及的算法不再以當前位置與下一步位置的移動角之差作為方向向導，而是將當前位置與距離最近未覆蓋柵格位置和下一步位置的角度差作為移動的方向向導，引導機器人快速逃離死區。機器人陷入死區后的方向信度函數定義為，其中移動方向角之差為

圖3 陷入死區方向信度函數Fig. 3 The direction belief function in the dead zone

1.3 路徑選擇策略

在柵格地圖中，全覆蓋路徑規劃問題就演變為尋找機器人的下一個移動位置，只有準確找出了該位置，才能使機器人自主規劃出一條切實可行的無碰撞且重復率低的移動路徑。為了避開障礙物并且能夠完成工作區域的全覆蓋，根據柵格位置性質函數和方向信度函數，定義一個綜合柵格信度函數，路徑選擇的原則是機器人始終向著綜合柵格信度函數值最大的方向運動。其定義為

圖4 各個柵格綜合信度函數值Fig. 4 The comprehensive belief function of each grid

為了進一步說明機器人的路徑選擇策略，圖5顯示了二維環境中基于柵格信度函數路徑選擇策略的路徑規劃效果(設置參數)。如圖5(a)所示，機器人從起點(1,1)出發，在方向信度函數的約束下，上下迂回來選擇路徑，保證了路徑的規整和方向改變最少的效果。從柵格位置性質函數值來看，機器人覆蓋過一次的地方，函數值變為0.5，而未覆蓋過的地方，函數值為1，維持柵格位置性質函數值最高，“吸引”機器人前往。當機器人運動到(2,20)時，右邊出現障礙物，而根據本文算法的定義障礙物的位置信度函數值為-。由于機器人總是選擇柵格信度函數值最大柵格作為下一步移動位置，因此在路徑規劃過程中將自動規避這些障礙物區域。圖5(b)顯示了當機器人移動到(20,12)時陷入死區。此時方向信度函數調整為，保證機器人向著未覆蓋的區域移動。圖5(c)顯示了機器人逃離死區的過程，圖中黑色線段表示機器人逃離死區的路徑。通過圖5中機器人路徑的選擇過程可知，本文提及的柵格信度函數全覆蓋算法不僅能夠使機器人躲避障礙物，而且可以快速的逃離死區。

進一步分析機器人未陷入死區時每一步路徑選擇，表1列出了圖5(a)中前6步機器人鄰近位置的柵格信度函數值。如表所示，機器人初始位置是(1,1)，由于靠近邊界只有3個鄰近柵格可以作為下一步的位置，根據式(1)、(2)、(5)計算出其鄰近柵格信度函數值分別為1.375、1.250和1.500，根據路徑選擇策略選擇最大值1.500對應的作為下一步的位置，即取(1,2)為機器人的下一步移動位置。隨即(1,2)作為機器人的當前位置繼續選擇路徑。按照上述過程，(1,3)、(1,4)、(1,5)、(1,6)、(1,7)依次作為機器人第3步、第4步、第5步、第6步、第7步的位置。

2 仿真實驗分析

圖5 機器人路徑選擇過程Fig. 5 The process of robot’s path selection

表1 機器人前7步的柵格信度函數值Table 1 The grid belief function of robot for the first seven steps

表2 機器人逃離死區的柵格信度函數值Table 2 The grid belief function of robot escaping from the dead zone

2.1 動態障礙物環境中全覆蓋路徑規劃

工作區域中，動態障礙物對機器人的路徑規劃具有不容忽視的影響，尤其是機器人在執行地面全覆蓋式的地形勘探和數據測量等任務時，動態障礙物的出現不僅威脅機器人安全，還會妨礙其對整個區域的全覆蓋效果。本節針對動態障礙物對區域全覆蓋的影響進行研究。如圖6(a)所示，機器人從(1,1)位置出發執行全覆蓋任務。障礙物3是動態的，起初在地圖上占據著相關區域，機器人無法對該區域進行覆蓋，如圖6(b)所示。

圖6 動態障礙物環境中的機器人全覆蓋路徑規劃Fig. 6 Complete-coverage path planning of robot in the dynamic obstacle environment

隨著機器人任務的繼續執行，當機器人移動至300步時，障礙物3離開(圖6(b)所示)，地圖上相關區域的柵格性質函數值變為1。當機器人移動到(20,4)時，正好執行完障礙物3離開前的地圖覆蓋，如圖6(c)所示。但是此時由于障礙物離開留下的區域需要覆蓋，因此根據快速逃離死區的規則，機器人從(20,4)再度出發，前往最近未覆蓋柵格(14,11)，此時機器人采用方向信度函數策略，以盡量短的路徑到達未覆蓋的區域。圖6(c)中黑色線段為(20,4)到未覆蓋區的移動路徑。當機器人到達未覆蓋柵格(14,11)之后，機器人恢復為的方向信度函數規則，繼續執行區域覆蓋任務直至完成，最終路徑效果見圖6(d)。由此可見，柵格信度函數值能夠跟隨環境地圖信息的變化而變化，從而指導機器人執行新區域覆蓋任務。因此本文提及的算法能夠實現動態障礙物環境中的全覆蓋路徑規劃。

2.2 不同算法的比較

為了進一步考察本文所提算法的性能，本節將與其他算法對區域覆蓋率、路徑重復率、總行程等指標進行比較。圖7顯示了兩種不同算法對20×20且存在不規則障礙物的柵格區域進行全覆蓋路徑規劃的結果。采用文獻[17]的生物啟發神經網絡全覆蓋方式得到的路徑規劃效果如圖7(a)所示。采用本文提及的柵格信度函數算法的路徑規劃結果如圖7(b)所示。兩種路徑規劃方法進行效果對比的評價指標如表3所示。通過圖7和表3的結果可知，雖然兩種方法的區域覆蓋率均達到100%，但是機器人逃離死區的路徑有較大的區別。生物啟發神經網絡算法由于陷入死區的位置離未覆蓋區域較遠，神經元的活性傳遞需要較長時間，使得機器人長期停留在死區，需要更長的路徑才能逃離死區。而柵格信度函數算法在機器人陷入死區后能通過調整方向信度函數的方法快速的逃離死區。圖7中黑色線段顯示了兩種不同算法逃離死區的路徑。雖然兩種算法在未陷入死區前機器人移動路徑相同，但是由于逃離死區的路徑不同，導致兩種算法的重復覆蓋柵格數，路徑重復率、總行程等指標的差異。從表3可見生物啟發神經網絡算法的重復覆蓋的柵格有39塊，而柵格信度函數算法只有23塊；生物啟發神經網絡算法的路徑重復率幾乎是本文算法的2倍；總行程后者比前者少16步。結果表明基于柵格信度函數的算法可以有效降低路徑重復率，縮短行程，對于機器人來說路徑規劃更適合控制，更節省能源。

圖7 不同算法全覆蓋路徑規劃結果Fig. 7 The results of complete-coverage path planning with different algorithms

表3 不同算法全覆蓋路徑規劃性能比較Table 3 Performance comparison of complete-coverage path planning with different algorithms

3 結束語

本文采用柵格信度函數算法解決了移動機器人全覆蓋路徑規劃問題。仿真實驗證明本文所提算法在二維障礙物環境中，不僅能夠實現動態障礙物工作區域的全覆蓋，而且還能夠快速逃離死區，降低了機器人路徑的重復率，提高了覆蓋效率。限于篇幅，本文未討論實際的二維環境柵格地圖的構建以及機器人的形狀、轉向幅度、定位對全覆蓋路徑規劃的影響，后續研究將把柵格地圖構建與全覆蓋路徑規劃結合，研究移動機器人對真實環境的感知與路徑規劃方法。

[1]簡毅, 張月. 移動機器人全局覆蓋路徑規劃算法研究進展與展望[J]. 計算機應用, 2014, 34(10): 2844–2849, 2864.JIAN Yi, ZHANG Yue. Complete coverage path planning algorithm for mobile robot: progress and prospect[J]. Journal of computer applications, 2014, 34(10): 2844–2849,2864.

[2]YAN Mingzhong, ZHU Daqi. An algorithm of complete coverage path planning for autonomous underwater vehicles[J]. Key engineering materials, 2011, 467-469: 1377–1385.

[3]莫宏偉, 馬靖雯. 一種生物地理學移動機器人路徑規劃算法[J]. 智能系統學報, 2015, 10(5): 705–711.MO Hongwei, MA Jingwen. A biogeography-based mobile robot path planning algorithm[J]. CAAI transactions on intelligent systems, 2015, 10(5): 705–711.

[4]LI Yan, CHEN Hai, JOO ER MENG, et al. Coverage path planning for UAVs based on enhanced exact cellular decomposition method[J]. Mechatronics, 2011, 21(5): 876–885.

[5]蒲興成, 趙紅全, 張毅. 細菌趨化行為的移動機器人路徑規劃[J]. 智能系統學報, 2014, 9(1): 69–75.PU Xingcheng, ZHAO Hongquan, ZHANG Yi. Mobile robot path planning research based on bacterial chemotaxis[J].CAAI transactions on intelligent systems, 2014, 9(1):69–75.

[6]KAPANOGLU M, ALIKALFA M, OZKAN M, et al. A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time[J]. Journal of intelligent manufacturing, 2012, 23(4): 1035–1045.

[7]杜鵬楨, 唐振民, 陸建峰, 等. 不確定環境下基于改進螢火蟲算法的地面自主車輛全局路徑規劃方法[J]. 電子學報,2014, 42(3): 616–624.DU Pengzhen, TANG Zhenmin, LU Jianfeng, et al. Global path planning for ALV based on improved glowworm swarm optimization under uncertain environment[J]. Acta electronica sinica, 2014, 42(3): 616–624.

[8]BALCH T. The case for randomized search[C]//Proceedings of Workshop on Sensors and Motion, IEEE International Conference on Robotics and Automation. San Francisco,CA: IEEE Press, 2000: 213–215.

[9]HABIB M A, ALAM M S, SIDDQUE N H. Optimizing coverage performance of multiple random path-planning robots[J]. Paladyn, 2012, 3(1): 11–22.

[10]JIN Xin, GUPTA S, LUFF J M, et al. Multi-resolution navigation of mobile robots with complete coverage of unknown and complex environments[C]//Proceedings of 2012 American Control Conference. Montreal: IEEE Press,2012: 4867–4872.

[11]YAZICI A, KIRLIK G, PARLAKTUNA O, et al. A dynamic path planning approach for multirobot sensor-based coverage considering energy constraints[J]. IEEE transactions on cybernetics, 2014, 44(3): 305–314.

[12]HSU P M, LIN Chunliang, YANG Mengyao. On the complete coverage path planning for mobile robots[J]. Journal of intelligent and robotic systems, 2014, 74(3/4): 945–963.

[13]邱雪娜, 劉士榮, 宋加濤, 等. 不確定動態環境下移動機器人的完全遍歷路徑規劃[J]. 機器人, 2006, 28(6):586–592.QIU Xuena, LIU Shirong, SONG Jiatao, et al. A complete coverage path planning method for mobile robots in uncertain dynamic environments[J]. Robot, 2006, 28(6):586–592.

[14]GUO Yi, BALAKRISHNAN M. Complete coverage control for nonholonomic mobile robots in dynamic environments[C]//Proceedings of 2006 IEEE International Conference on Robotics and Automation. Orlando, FL, USA:IEEE Press, 2006: 1704–1709.

[15]YANG S X, LUO Chaomin. A neural network approach to complete coverage path planning[J]. IEEE transactions on systems, man, and cybernetics, part B: cybernetics, 2004,34(1): 718–724.

[16]LUO Chaomin, YANG S X. A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environments[J]. IEEE transactions on neural networks, 2008, 19(7): 1279–1298.

[17]YAN Mingzhong, ZHU Daqi, YANG S X. Complete coverage path planning in an unknown underwater environment based on D-S data fusion real-time map building[J].International journal of distributed sensor networks, 2012,2012: 567959, doi: 10.1155/2012/567959.

[18]朱大奇, 顏明重. 移動機器人路徑規劃技術綜述[J]. 控制與決策, 2010, 25(7): 961–967.Zhu Daqi, Yan Mingzhong. Survey on technology of mobile robot path planning[J]. Control and decision, 2010,25(7): 961–967.

[19]LEE T K, BAEK S H, CHOI Y H, et al. Smooth coverage path planning and control of mobile robots based on highresolution grid map representation[J]. Robotics and autonomous systems, 2011, 59(10): 801–812.

[20]歐陽鑫玉, 楊曙光. 基于勢場柵格法的移動機器人避障路徑規劃[J]. 控制工程, 2014, 21(1): 134–137.OUYANG Xinyu, YANG Shuguang. Obstacle avoidance path planning of mobile robots based on potential grid method[J]. Control engineering of china, 2014, 21(1):134–137.

[21]郝宗波, 洪炳镕, 黃慶成. 基于柵格地圖的機器人覆蓋路徑規劃研究[J]. 計算機應用研究, 2007, 24(10): 56–58.HAO Zongbo, HONG Bingrong, HUANG Qingcheng.Study of coverage path planning based on grid-map[J]. Application research of computers, 2007, 24(10): 56–58.

[22]SIPAHIOGLU A, KIRLIK G, PARLAKTUNA O, et al.Energy constrained multi-robot sensor-based coverage path planning using capacitated arc routing approach[J]. Robotics and autonomous systems, 2010, 58(5): 529–538.