引入方向變量的群機器人啟發(fā)式區(qū)域覆蓋算法

李慧勇，張國有，郭銀章

（1.太原科技大學(xué)計算機學(xué)院，太原 030024；2.山西工程職業(yè)技術(shù)學(xué)院計算機工程系，太原 030009）

機器人全區(qū)域覆蓋問題是指攜帶有一定探測范圍的傳感器（如激光、聲納等）的機器人覆蓋整個環(huán)境并創(chuàng)建環(huán)境地圖的過程。該問題的本質(zhì)是機器人或機器人團隊利用其移動性將其感知范圍逐步覆蓋整個環(huán)境。群機器人學(xué)［1］是機器人學(xué)與群體智能交叉形成的一個新的學(xué)科和研究方向，利用群體機器人進行區(qū)域覆蓋與傳統(tǒng)的單機器人區(qū)域覆蓋相比，可以加快覆蓋速度，提高覆蓋效率，節(jié)約成本，在軍事、科研以及生產(chǎn)生活中有廣泛的應(yīng)用，例如:未知區(qū)域的地形測繪、未知水域的排雷、搶險救災(zāi)中的廢墟探測、汽車輪船的檢修或噴漆、室內(nèi)外清潔等。

研究群機器人全區(qū)域覆蓋問題，首先要建立環(huán)境地圖的模型。目前環(huán)境地圖的建模方法有:柵格法［2］、單元分解法［3］、拓撲邏輯圖法［4］和 voronoi圖法［5］等。在環(huán)境地圖的模型建立后，群機器人的覆蓋路徑規(guī)劃算法是區(qū)域覆蓋問題的核心。目前已有的算法可以分為兩類:離線規(guī)劃算法和在線規(guī)劃算法。Diana和Wesley等［6］用擬態(tài)物理的方法實現(xiàn)了群機器人的全區(qū)域覆蓋，機器人之間采用顯式通信方式。這種群機器人區(qū)域覆蓋算法的一個局限是機器人群體在區(qū)域覆蓋過程中，機器人之間的距離有一定限制。I.Wagner［7］和 S.Koenig 等［8］受螞蟻等群體性昆蟲運動時在路上留下信息素的啟發(fā)，提出了群機器人啟發(fā)式全區(qū)域覆蓋算法:群體機器人通過在覆蓋區(qū)域留下的信息素進行隱式通信從而完成對目標(biāo)區(qū)域的覆蓋。這類算法對群機器人中機器人之間的距離沒有限制。在基于T.Balch等［9］提出的NC（Node Counting）算法的群機器人啟發(fā)式全區(qū)域覆蓋算法中，機器人每次完成更新當(dāng)前柵格的值和移動到下一個柵格兩個動作。其中，機器人每次移動到一個柵格后，給這個柵格的值加1，然后移動到與其相鄰且值最小的那個柵格中，最后完成全區(qū)域覆蓋。后來，I.Wagner等［7］改進了其中的更新柵格值策略，提出了WVU（Wagner's Value-Update Rule）算法，該算法較原算法全區(qū)域覆蓋時間明顯降低。S.Koenig等［8］將人工智能領(lǐng)域的LRTA（Learning Real-Time A）算法借鑒到更新柵格值的策略中，還有 S.Thrun［9］提出的 TVU（Thrun's Value-Update Rule）算法，都在一定程度上減少了機器人的區(qū)域覆蓋時間。

由于群機器人啟發(fā)式全區(qū)域覆蓋算法的并行性，會產(chǎn)生多個機器人相遇，并且同時占據(jù)某個柵格的情況，因此增加了完成區(qū)域覆蓋的時間。如果能夠減少機器人的相遇次數(shù)，可以在一定程度上減少機器人群體的重復(fù)移動次數(shù)，從而提高算法的覆蓋效率。

通過對NC、WVU、LRTA、TVU四種群機器人啟發(fā)式全區(qū)域覆蓋算法的分析，在原有算法基礎(chǔ)上引入了方向變量。引入方向變量的新算法中，方向變量存放上一步機器人移動的方向，機器人每次移動盡量按照原來的方向前進，減少轉(zhuǎn)向次數(shù)，從而減少了機器人相遇的幾率，因此在一定程度上減少了機器人重復(fù)移動次數(shù)。同時由于減少了機器人轉(zhuǎn)向次數(shù)，從而在一定程度上減少了機器人在實際應(yīng)用中因為轉(zhuǎn)向而造成的能量損耗。

圖1 機器人和柵格地圖Fig.1 Robot and grid map

1 群機器人啟發(fā)式全區(qū)域覆蓋算法

在柵格地圖環(huán)境中，群體機器人中的個體機器人只有局部感知能力，個體機器人的感知范圍如圖1（a）中白色區(qū)域所示。設(shè)未被覆蓋的柵格值為0，覆蓋過的區(qū)域柵格值為一個正整數(shù)，如圖1（b）所示；機器人每次只能判斷與其相鄰的A、B、C、D四個方向柵格的值；群體機器人中每個機器人的移動能力有限，每次只能移動至與其相鄰的 A、B、C、D四個柵格之一；機器人可以同時占據(jù)一個柵格；群機器人在開始區(qū)域覆蓋前的位置隨機分布在柵格地圖中。

最基本的NC算法［10］（Node Counting）如下:

Step 1 求出A、B、C、D四個柵格中值中的最小值；

Step 2 機器人將當(dāng)前占據(jù)的柵格值加1；

Step 3 機器人移動到值最小的柵格中，如果有若干柵格值都等于最小值則隨機移動到其中一個柵格中，轉(zhuǎn)到Step 1.

該算法簡單明了。由于機器人每次到過一個柵格后就把該柵格的值加1，因此柵格的值越小，說明柵格被訪問的次數(shù)越少。機器人每次都向沒有被訪問過或者比較少訪問過的柵格移動，因此最后可以完成整個柵格地圖的覆蓋。后來提出來的改進算法主要是針對NC算法的Step 2進行修改。設(shè)當(dāng)前柵格值為u，下一步要移動到的那個柵格值為u_next，則NC算法的Step 2可以用等式u=u+1表示。WVU算法［7］中更新策略是:if（u＜=u_next）then u=u+1.LRTA 算法［8］的更新策略是:u=u_next+1.TVU 算法［10］的更新策略是:u=max（u+1，u_next+1）.這些算法都是通過修改原有NC算法中的柵格值的更新策略，在一定程度上減少了機器人完成區(qū)域覆蓋所需時間。

但是，在上述四種算法的改進中，沒有考慮到多個機器人相遇，同時占據(jù)某個柵格，從而產(chǎn)生對柵格的重復(fù)覆蓋的問題。如何能夠盡量減少機器人的相遇次數(shù)呢?下面比較一下同一柵格地圖環(huán)境下，相同數(shù)量機器人執(zhí)行同一覆蓋算法，從相同位置出發(fā)，走不同路徑，移動相同次數(shù)后，所形成的不同覆蓋區(qū)域。

圖2為執(zhí)行WVU算法的兩個機器人在10×10柵格地圖環(huán)境下，移動8次后，走不同路徑，可能形成的若干種覆蓋區(qū)域中的三種不同覆蓋區(qū)域。在圖2中，值為0的柵格表示沒有被覆蓋，值為1表示柵格已經(jīng)被覆蓋過一次，值為2表示柵格被覆蓋過2次。為區(qū)別不同的兩個機器人的覆蓋路徑，分別用橫線柵格和斜線柵格來區(qū)分不同機器人覆蓋過的柵格。用（x，y）來表示機器人在柵格地圖中所處的位置（其中x表示行坐標(biāo)，y表示列坐標(biāo)）。圖2中兩個機器人的出發(fā)點分別是（2，4）和（2，6），其中圖2（a）中機器人移動路徑分別是:（2，4）→（3，4）→（4，4）→（5，4）→（6，4）→（7，4）→（8，4）→（9，4）和（2，6）→（3，6）→（4，6）→（5，6）→（6，6）→（7，6）→（8，6）→（9，6）；圖 2（b）中的機器人移動路徑分別是:（2，4）→（3，4）→（4，4）→（5，4）→（5，5）→（5，6）→（5，7）→（5，8）和（2，6）→（3，6）→（4，6）→（5，6）→（6，6）→（7，6）→（8，6）→（9，6）；圖 2（c）中機器人移動路徑分別是:（2，4）→（3，4）→（3，5）→（4，5）→（4，6）→（5，6）→（5，7）→（6，7）和（2，6）→（2，6）→（3，5）→（3，6）→（4，6）→（4，7）→（5，7）→（5，8）。圖2（a）中，機器人沒有重復(fù)覆蓋區(qū)域，共完成覆蓋16個柵格；圖2（b）中，有一個重復(fù)覆蓋柵格，柵格（5，6）被兩個機器人重復(fù)訪問，共完成覆蓋15個柵格；圖2（c）中，有三個重復(fù)覆蓋柵格，機器人共完成覆蓋13個柵格?？梢?，相同的機器人數(shù)量，同樣的移動次數(shù)，同樣的算法下，不同的覆蓋路徑，圖2（a）覆蓋區(qū)域最大，圖2（c）覆蓋區(qū)域最小。從圖2的比較中可以看出，機器人的移動路徑轉(zhuǎn)向次數(shù)越少，相遇幾率就越小。相遇幾率越小，那么相遇并同時覆蓋一個柵格的情況就越少。因此，減少機器人在覆蓋過程中的轉(zhuǎn)向次數(shù)，可以在一定程度上減少柵格的重復(fù)訪問次數(shù)，提高機器人的區(qū)域覆蓋效率。

圖2 兩個機器人執(zhí)行WVU算法的不同覆蓋區(qū)域Fig.2 Different covering terrains of two robots executing WVU algorithm

另一方面，群機器人在進行區(qū)域覆蓋的實際應(yīng)用過程中，如果機器人個體在覆蓋過程中能夠盡量沿直線運動，則其能量消耗是較少的。如果機器人在行進中轉(zhuǎn)向，則其要進行減速，轉(zhuǎn)向，加速三個運動狀態(tài)的轉(zhuǎn)換，根據(jù)牛頓定律，轉(zhuǎn)向過程中是要消耗一定的能量的，轉(zhuǎn)向次數(shù)越多，這種額外能量損耗越大。設(shè)一次轉(zhuǎn)向過程中機器人的能量損耗為e，則圖2（a）中機器人能量損耗為0，圖2（b）中機器人能量損耗為e，圖2（c）中機器人能量損耗為12e.可見，機器人按照相同的區(qū)域覆蓋算法，走不同的路徑，移動相同的次數(shù)，會產(chǎn)生不同的額外能量損耗，而且差別較大。

群機器人執(zhí)行相同的啟發(fā)式全區(qū)域覆蓋算法，之所以轉(zhuǎn)向次數(shù)會產(chǎn)生如此大的差別，是因為在該類算法的Step 3中，當(dāng)機器人相鄰柵格中出現(xiàn)多個等于最小值的柵格時，機器人的移動方向是隨機的。在這種情況下，如何能使機器人盡量按照原來的運動方向移動，從而盡量減少機器人的轉(zhuǎn)向次數(shù)，是修改算法的切入點。

2 引入方向變量的群機器人啟發(fā)式全區(qū)域覆蓋算法

如圖1（a）所示，設(shè)機器人每次移動的四個方向為A、B、C、D，引入機器人方向變量 m，m 的值可以取A、B、C、D之一。移動變量m中存放的是機器人前一次的移動方向，機器人每次移動完成后更新方向變量m的值。引入方向變量后的群機器人啟發(fā)式全區(qū)域覆蓋算法中，機器人首先求出其相鄰四個柵格值中的最小值，然后和m方向柵格的值比較，如果相等，則機器人移動到m方向柵格中，并按照算法規(guī)則更新原占據(jù)柵格的值；如果不等，則機器人移動到柵格值最小的那個柵格中，如果有若干柵格值都等于最小值，再隨機移動到其中之一。

根據(jù)上述思路，引入方向變量后的群機器人啟發(fā)式全區(qū)域覆蓋算法如下:

Step 1 求出A、B、C、D四個柵格值中的最小值；

Step 2 如果方向變量m方向的柵格值等于最小值，則機器人更新當(dāng)前柵格的值，并移動到m方向的那個柵格中，然后轉(zhuǎn)到Step 1；否則轉(zhuǎn)到Step 3.

Step 3 機器人更新當(dāng)前柵格的值并且移動到值最小的柵格中，如果有若干柵格值都等于最小值則隨機移動到其中一個柵格中，并且更新方向變量m的值，然后轉(zhuǎn)到Step 1.

引入方向變量后，原來群機器人啟發(fā)式全區(qū)域覆蓋算法中的NC算法、LRTA算法、WVU算法和TVU算法，分別形成了NC-M算法、LRTA-M算法、WVU-M算法和TVU-M算法。在圖2的實例中，如果機器人執(zhí)行引入方向變量的區(qū)域覆蓋算法，只可能出現(xiàn)圖2（a）中的移動路徑，不會出現(xiàn)圖2（b）和圖2（c）那種移動路徑，從而減少了機器人相遇并同時覆蓋某個柵格的幾率，在一定程度上減小了機器人的重復(fù)覆蓋率，并且由于減少了機器人在行進過程中的轉(zhuǎn)向次數(shù)，在一定程度上減少了機器人因為轉(zhuǎn)向而造成的額外能量損耗。

3 仿真實驗

通過仿真程序來驗證改進算法的有效性。仿真程序由C語言編寫，柵格地圖在仿真程序中由一個二維數(shù)組表示，數(shù)組元素的值代表柵格的值。在柵格地圖中每個柵格的初值為0，邊界柵格的值為一個很大的數(shù)（使邊界柵格在區(qū)域覆蓋過程中不被訪問）；機器人初始位置隨機；機器人從一個柵格移動到相鄰的柵格中為一次移動，機器人移動一次所花的時間為單位時間；機器人每次移動可以更新當(dāng)前柵格的值；當(dāng)所有柵格的值都為非0時，表示全區(qū)域覆蓋結(jié)束；實驗環(huán)境地圖采用40×40柵格地圖。

表1 12個機器人實驗結(jié)果Tab.1 The experimental results of 12 robots

12個機器人分別采用8種不同的群機器人啟發(fā)式全區(qū)域覆蓋算法，對實驗地圖進行區(qū)域覆蓋的結(jié)果如表1所示，其中的覆蓋時間為群機器人完成一次全區(qū)域覆蓋所花的時間，轉(zhuǎn)向數(shù)為完成一次全區(qū)域覆蓋每個機器人的平均轉(zhuǎn)向次數(shù)。由于該類算法是隨機算法，因此每種算法進行20次試驗，并在最后求均值。從數(shù)據(jù)中可以看出，群機器人使用引入方向變量后的四種新算法，完成一次全區(qū)域覆蓋的平均時間僅為相應(yīng)原算法的45%左右，平均轉(zhuǎn)向次數(shù)僅為相應(yīng)原算法的25%左右，將上述算法的實驗均值數(shù)據(jù)用條形圖表示如圖3所示。

從圖3中可以清晰地看出，引入方向變量后的WVU-M、LRTA-M和TVU-M三種算法是所有算法中覆蓋時間最小和轉(zhuǎn)向次數(shù)最少的，并且這三種算法效率相當(dāng)。NC-M算法比NC算法效率也大大提高，但較其他三種算法仍然有很大差距。通過實驗比較機器人數(shù)量對算法效率的影響，得出的數(shù)據(jù)如圖4所示。

圖3 12個機器人均值數(shù)據(jù)Fig.3 The average data of 12 robots

圖4 不同數(shù)量機器人的均值數(shù)據(jù)Fig.4 Average data of different numbers of robots

圖4中，橫坐標(biāo)為機器人個數(shù)，圖4（a）中的縱坐標(biāo)為機器人完成一次全區(qū)域覆蓋的平均時間，圖4（b）中的縱坐標(biāo)為完成一次全區(qū)域覆蓋，每個機器人的平均轉(zhuǎn)向次數(shù)。從圖4（a）中可以看出，每種算法中，隨著機器人數(shù)量的增加，群機器人完成一次全區(qū)域覆蓋的時間逐漸減少，其中TVU-M、LRTA-M和WVU-M三種算法效率相當(dāng)，且在所有算法中，這三種算法所用時間最少。在圖4（b）中，NC、WVU、LRTA和TVU四種算法的每個機器人的平均轉(zhuǎn)向次數(shù)隨著機器人數(shù)量的逐漸增加，在上下波動，沒有明顯下降趨勢；而NC-M、WVU-M、LRTA-M和TVUM四種算法，每個機器人的平均轉(zhuǎn)向數(shù)隨著機器人數(shù)量的增加而逐漸下降，其中TVU-M、LRTA-M和WVU-M三種算法轉(zhuǎn)向次數(shù)最少而且效率相當(dāng)。

4 結(jié)論

在原有的群機器人啟發(fā)式全區(qū)域覆蓋算法中，引入方向變量，在方向變量的作用下，機器人在區(qū)域覆蓋過程中盡量不改變原來的運動方向，減少了機器人之間的相遇次數(shù)，從而減少了不同機器人同時訪問相同柵格而導(dǎo)致的重復(fù)覆蓋，提高了算法的效率。

仿真實驗驗證了群機器人在完成一次全區(qū)域覆蓋任務(wù)時，使用引入方向變量后的改進算法比原算法的平均覆蓋時間減少一半左右，而且隨著機器人數(shù)量的不斷增加，平均覆蓋時間不斷減少。在8種比較算法中，TVU-M、LRTA-M和WVU-M三種算法的全區(qū)域覆蓋時間最少，并且三種算法效率相當(dāng)。

同時實驗結(jié)果也表明，完成一次全區(qū)域覆蓋任務(wù)，如果使用原來的算法，隨著機器人數(shù)量的增加，每個機器人的平均轉(zhuǎn)向次數(shù)并沒有明顯的降低而是在上下波動。而如果使用引入方向變量的新算法，每個機器人的平均轉(zhuǎn)向次數(shù)隨著機器人數(shù)量的增加而線性下降，尤其是TVU-M、LRTA-M和WVUM三種算法轉(zhuǎn)向次數(shù)最少而且效率相當(dāng)。

［1］薛頌東，曾建潮.群機器人研究綜述［J］.模式識別與人工智能，2008，21（2）:177-185.

［2］YAMAUCHI B.Decentralized coordination for multi-robot exploration［J］.Robotics and Autonomous Systems，1999，29（2）:111-118.

［3］CHOSET H.Coverage of Known Spaces:The Boustrophedon Cellular Decomposition［J］.Autonomous Robots，2000，9（3）:247-253.

［4］SYLVIA C WONG，BRUCE A MACDONALD.A topological coverage algorithm for mobile robots［C］//Proceedings of the 2003 IEEE/RSJ Intl Conference on Intelligent Robots and Systems，Las Vegas，Nevada.2003:1685-1690.

［5］CHOSET H，BURDICK J.Sensor based planning I，The generalized Voronoi graph［C］//IEEE International Conference on Robotics and Automation，1995:1649-1655.

［6］SPEARS D F，KERR W，SPEARS W F.Physics-Based Robots Swarms For Coverage Problems［J］.Int J on Intelligent Control and Systems，2006，11（3）:11-23.

［7］WAGNER I A，LINDENBAUM M.MAC vs PC:Determinism and randomness as complementary approaches to robotic exploration of continuous unknown domains［J］.Int J of Robotics Research，2000，19（1）:12-31.

［8］KOENING S，SZYMANKI B.Efficient and inefficient ant coverage methods［J］.Annals of Mathematics and Artificial Intelligence，2001，31:41-76.

［9］THRUN S.Efficient exploration in reinforcement learning［R］.Pittsburgh:Carnegie Mellon University，1992.

［10］BALCH T，ARKIN R.Avoiding the past:A simple，but effective strategy for reactive navigation［C］//International Conference on Robotics and Automation，1993:678-685.