移動(dòng)機(jī)器人全覆蓋信度函數(shù)路徑規(guī)劃算法

曹翔，俞阿龍

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 方向信度函數(shù)

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

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

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

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

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

1.3 路徑選擇策略

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

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

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

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

2 仿真實(shí)驗(yàn)分析

圖5 機(jī)器人路徑選擇過(guò)程Fig. 5 The process of robot’s path selection

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

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

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

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

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

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

2.2 不同算法的比較

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

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

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