曹翔，俞阿龍

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

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

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

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

最近，Yan[17]等在文獻[15-16]的基礎上，進一步將生物啟發(fā)神經(jīng)網(wǎng)絡應用到水下機器人全覆蓋路徑規(guī)劃中。該算法根據(jù)聲吶傳感器獲取的信息，利用信息融合技術(shù)構(gòu)建動態(tài)水下環(huán)境地圖，根據(jù)水下感知的環(huán)境地圖性質(zhì)確定生物啟發(fā)神經(jīng)網(wǎng)絡中神經(jīng)元的活性值，水下機器人通過比較鄰近神經(jīng)元活性值進行路徑規(guī)劃，完成對工作區(qū)域的全覆蓋，該方法將水下環(huán)境的地圖構(gòu)建與全覆蓋路徑規(guī)劃有機結(jié)合，得到一套完整的水下機器人感知環(huán)境與全覆蓋搜救方法。

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

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

1 基于柵格信度函數(shù)的全覆蓋路徑規(guī)劃算法

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

1.1 柵格位置性質(zhì)函數(shù)

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

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

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

1.2 方向信度函數(shù)

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

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

圖2 未陷入死區(qū)方向信度函數(shù)Fig. 2 The direction belief function in the free zone

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

圖3 陷入死區(qū)方向信度函數(shù)Fig. 3 The direction belief function in the dead zone

1.3 路徑選擇策略

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

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

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

進一步分析機器人未陷入死區(qū)時每一步路徑選擇，表1列出了圖5(a)中前6步機器人鄰近位置的柵格信度函數(shù)值。如表所示，機器人初始位置是(1,1)，由于靠近邊界只有3個鄰近柵格可以作為下一步的位置，根據(jù)式(1)、(2)、(5)計算出其鄰近柵格信度函數(shù)值分別為1.375、1.250和1.500，根據(jù)路徑選擇策略選擇最大值1.500對應的作為下一步的位置，即取(1,2)為機器人的下一步移動位置。隨即(1,2)作為機器人的當前位置繼續(xù)選擇路徑。按照上述過程，(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步的柵格信度函數(shù)值Table 1 The grid belief function of robot for the first seven steps

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

2.1 動態(tài)障礙物環(huán)境中全覆蓋路徑規(guī)劃

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

圖6 動態(tài)障礙物環(huán)境中的機器人全覆蓋路徑規(guī)劃Fig. 6 Complete-coverage path planning of robot in the dynamic obstacle environment

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

2.2 不同算法的比較

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

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

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

3 結(jié)束語

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

[1]簡毅, 張月. 移動機器人全局覆蓋路徑規(guī)劃算法研究進展與展望[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]莫宏偉, 馬靖雯. 一種生物地理學移動機器人路徑規(guī)劃算法[J]. 智能系統(tǒng)學報, 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]蒲興成, 趙紅全, 張毅. 細菌趨化行為的移動機器人路徑規(guī)劃[J]. 智能系統(tǒng)學報, 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]杜鵬楨, 唐振民, 陸建峰, 等. 不確定環(huán)境下基于改進螢火蟲算法的地面自主車輛全局路徑規(guī)劃方法[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]邱雪娜, 劉士榮, 宋加濤, 等. 不確定動態(tài)環(huán)境下移動機器人的完全遍歷路徑規(guī)劃[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]朱大奇, 顏明重. 移動機器人路徑規(guī)劃技術(shù)綜述[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]歐陽鑫玉, 楊曙光. 基于勢場柵格法的移動機器人避障路徑規(guī)劃[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]郝宗波, 洪炳镕, 黃慶成. 基于柵格地圖的機器人覆蓋路徑規(guī)劃研究[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.