未知環(huán)境中自主機器人環(huán)境探索與地圖構(gòu)建

王東署， 王海濤

(鄭州大學(xué)電氣工程學(xué)院 河南鄭州450001)

0 引言

自主移動機器人是機器人技術(shù)的一個重要研究領(lǐng)域，已廣泛應(yīng)用于工農(nóng)業(yè)生產(chǎn)、交通、服務(wù)、醫(yī)療和軍事等領(lǐng)域.隨著應(yīng)用環(huán)境的復(fù)雜化，人類對移動機器人的自主性和智能性提出了更高的要求，特別是在大規(guī)模未知極限或復(fù)雜環(huán)境下，如深海探索、太空探索及核事故處理等領(lǐng)域，人類期望機器人能自主完成環(huán)境的探索，并創(chuàng)建環(huán)境地圖.因此，在未知環(huán)境中進行環(huán)境探索，并根據(jù)任務(wù)的不同同時構(gòu)建相應(yīng)的環(huán)境地圖是自主移動機器人應(yīng)具備的基本能力.

機器人對環(huán)境的探索通?？醋魇荖BV(next best view)問題［1］，即在已探測的環(huán)境中選取一個最好的觀測點作為目標點，并駛向該觀測點，然后通過多次迭代，直到完成對整個工作環(huán)境的遍歷.在探索過程中，機器人必須解決如下3個關(guān)鍵問題:如何根據(jù)傳感器提供的信息來產(chǎn)生一系列候選觀測點;如何從機器人當前位置運動到下一最優(yōu)觀測點;如何對獲得的傳感器信息進行相應(yīng)處理以構(gòu)建出機器人能理解的環(huán)境地圖.其中前兩步可歸為環(huán)境探索，第三步可歸為地圖構(gòu)建，環(huán)境探索又可進一步細分為候選觀測點的選取和評估.

早期候選觀測點的選取主要采用隨機算法［2］，該方法具有很大的隨機性，研究人員必須考慮對隨機點的過濾和環(huán)境遍歷等問題.為了提高機器人環(huán)境探索的效率，Yamauchi［1］提出了前沿探測理論，其基本思想是將已知區(qū)域與未知區(qū)域的交界定義為前沿，探索過程中使機器人盡可能地駛向未知區(qū)域，并使期望的信息增益最大，同時能快速降低地圖信息中的不確定性因素，該探索策略具有一定的趨向性，是目前探索策略的核心思想，被廣泛采用［3-6］.除此之外，F(xiàn)reda等［7］提出了利用前沿理論隨機生成觀測位置，并使候選位置趨向于未探測區(qū)域的混合算法.該算法的核心思想是創(chuàng)建一個結(jié)構(gòu)樹，為樹中的節(jié)點生成隨機探測方向，在該探測方向上選擇候選觀測點.這種方法可以使候選觀測點分布于信息增益較大的邊界上，提高了探測效率.

候選觀測點的評估則主要通過建立一個效用函數(shù)［3-6，8-11］來衡量候選觀測點的效用值，效用函數(shù)中一般包括機器人的轉(zhuǎn)向角度、機器人與目標點間的運動距離、探測未知區(qū)域面積(信息增益)、機器人運動損耗等信息.早期的效用函數(shù)采用單一指標，如文獻［1］采用最小運行距離作為評價候選觀測點的參考指標.現(xiàn)在更多的效用函數(shù)采用兩個或多個指標的組合，如最小運行距離與信息增益的線性組合［8］及非線性組合［9］，最小運行距離、信息增益和重疊率的加權(quán)平均［10］等.

機器人在對環(huán)境進行探索的過程中需要將對外界環(huán)境的感知以地圖的形式存儲起來.目前常用的地圖表示方法分為三類:度量地圖、拓撲地圖和混合地圖［12］.自主機器人未知環(huán)境探索與地圖創(chuàng)建是兩個相輔相成的研究內(nèi)容，應(yīng)該是在同一過程中同時進行的.但很多研究將二者分開進行，在設(shè)計環(huán)境探索策略時很少考慮地圖構(gòu)建算法的實現(xiàn).作者將自主環(huán)境探索與地圖構(gòu)建的研究相結(jié)合，提出了可同時實現(xiàn)環(huán)境探索與地圖創(chuàng)建的方法.在環(huán)境探索階段，基于前沿探測理論，提出了具有避障功能的環(huán)境探索策略;在地圖構(gòu)建階段，提出了基于增長的神經(jīng)氣網(wǎng)絡(luò)的地圖構(gòu)建方法，該方法以神經(jīng)氣網(wǎng)絡(luò)的節(jié)點作為拓撲網(wǎng)絡(luò)的網(wǎng)絡(luò)節(jié)點，以少量的神經(jīng)氣網(wǎng)絡(luò)節(jié)點分布來描述具有大量特征信息的未知環(huán)境，建立了能準確描述環(huán)境的且易于機器人理解、規(guī)劃與決策的拓撲網(wǎng)絡(luò)地圖.

1 未知環(huán)境中的探索

移動機器人在完全未知的環(huán)境中，必須通過自身配帶的傳感器對當前所處的環(huán)境進行掃描而獲取環(huán)境信息，并且根據(jù)所獲得的環(huán)境信息選取合適的位置點作為探索的目標點，進而指導(dǎo)機器人在未知環(huán)境中不斷探索，直到對整個未知環(huán)境進行完全遍歷.

1.1 坐標轉(zhuǎn)換

移動機器人環(huán)境探索的目的是為了建立環(huán)境地圖，環(huán)境探索也是未知環(huán)境中構(gòu)建環(huán)境地圖的必要手段，因此，將移動機器人探索的信息轉(zhuǎn)換成環(huán)境地圖的坐標信息，對于環(huán)境認知研究是一個必不可少的步驟.圖1所示為機器人探索點的坐標與環(huán)境地圖絕對坐標之間的轉(zhuǎn)換示意圖.公式如下:

式中，(X，Y)表示探索目標點在環(huán)境地圖中的坐標，(Xr，Yr)表示移動機器人在環(huán)境地圖中的位置坐標，DL表示目標點與移動機器人的距離，α表示移動機器人的航向角，β表示目標點的激光束與激光雷達的夾角．

1.2 探索策略

根據(jù)前沿探測理論，假設(shè)激光傳感器探測的邊緣均分為19個探測點.從中篩選出合適的候選觀測點，從而得到最佳的觀測點作為該步驟目標點，并且駛向該目標點.該方法簡單實用，可以快速有效地對未知環(huán)境進行探索，并且具有避障功能.具體的探索策略步驟如下:

(1)初始化移動機器人位置與航向角.

(2)移動機器人利用傳感器掃描獲取環(huán)境信息，篩選符合以下條件的點為候選觀測點:①該點必須是探測的前沿點，不被障礙物遮擋;②該點處于未探索環(huán)境中.

(3)若篩選出來的候選觀測點被障礙物分為M組，則按以下準則選出最優(yōu)觀測點:①從M組中選取包含候選觀測點最多的一組，若同時有兩組或兩組以上含有最多候選觀測點，則選取與機器人航向角偏向角度最小的一組;②選擇該組N個候選觀測點中處于中間位置的點作為最優(yōu)觀測點.

被選擇的候選組中所有候選探測點標記為已知，未被選中組的候選觀測點標記為未知，當下次被探測到時才標記為已知.

圖2中用小圓圈表示移動機器人當前位置，方塊表示障礙物，星號點表示激光傳感器19個探測點，其中被障礙物占據(jù)了6個.探測點被分成兩組，第一組包含9個探測點，第二組包含4個探測點.首先選擇具有9個探測點這組，然后選擇9個探測點處于中間位置的探測點為最優(yōu)觀測點.同時，第一組的9個探測點標記為已知點，第二組的4個探測點標記為未知點.

(4)移動機器人在駛向目標節(jié)點的過程中，移動設(shè)定步長后要對環(huán)境信息進行更新，具體更新過程詳見環(huán)境地圖的構(gòu)建部分.

(5)移動機器人到達目標節(jié)點后，如果有符合候選觀測點的條件則重復(fù)步驟(2)、(3)、(4);否則，機器人自轉(zhuǎn)設(shè)定的角度后再次查看.

(6)檢測已探測環(huán)境中所有候選探測點的標記值，如果有未知候選觀測點，則驅(qū)動機器人行駛到該點進行探測.

圖1 探索點的坐標與環(huán)境地圖絕對坐標的轉(zhuǎn)換Fig．1 Transition between coordinate of exploration pointand absolute coordinate of environment map

圖2 候選觀測點的選取Fig．2 Choices of candidate observation point

(7)當所有的候選觀測點標記值都為已知，則認為移動機器人完成了整個環(huán)境空間遍歷，停止工作.該過程的流程圖如圖3所示.

圖3 環(huán)境探索流程圖Fig．3 Flowchart of environment exploration

2 基于GNG網(wǎng)絡(luò)的拓撲環(huán)境地圖的構(gòu)建

GNG(growing neural gas)是由Fritzke［13］提出的一種生長的神經(jīng)氣網(wǎng)絡(luò)，是一種非監(jiān)督的、生長型的聚類算法，其神經(jīng)網(wǎng)絡(luò)的規(guī)模具有可增減特性.GNG算法不必預(yù)先知道輸入空間的分布特點，但是在實際系統(tǒng)當中，需要預(yù)先估計輸入空間的大小等情況來估計網(wǎng)絡(luò)大小、生成速度及其他參數(shù).GNG網(wǎng)絡(luò)是由網(wǎng)絡(luò)節(jié)點(node)和網(wǎng)絡(luò)節(jié)點之間的連接線(edge)兩部分構(gòu)成.

機器人對環(huán)境的探索是個動態(tài)遞增的過程，該探索過程可通過GNG網(wǎng)絡(luò)在動態(tài)的輸入空間中不斷地學(xué)習(xí)生成拓撲網(wǎng)絡(luò)節(jié)點來實現(xiàn).GNG網(wǎng)絡(luò)的可增長性體現(xiàn)在規(guī)?？稍鲩L和結(jié)構(gòu)可增長，即隨著輸入空間的不斷增長，用來表示輸入空間的網(wǎng)絡(luò)映射圖不斷增長.隨著網(wǎng)絡(luò)節(jié)點不斷自我學(xué)習(xí)，自組織地發(fā)現(xiàn)輸入空間中數(shù)據(jù)的分布特性，并將這種特性反映在映射輸出空間中.輸入空間中數(shù)據(jù)密集的地方在映射空間中占據(jù)較多的網(wǎng)絡(luò)節(jié)點，能準確地實現(xiàn)輸入空間的模式聚類和模式分類［14］.

基于GNG網(wǎng)絡(luò)的拓撲地圖構(gòu)建算法步驟如下:

(1)初始化節(jié)點空間N，具有兩個已知節(jié)點N1，N2，對應(yīng)的向量為

(2)初始化信號輸入空間S，隨機生成一個輸入信號s，且s的概率為1/S，對應(yīng)的向量為

(3)分別計算輸入信號s與節(jié)點N1和N2的距離，以區(qū)分最近點和次近點，假設(shè)N1為最近點．

(4)若N1和N2之間沒有連接邊，則連接兩點，且設(shè)置該連接邊的老化度為0．

(6)更新最近點N1以及與之有連接的節(jié)點的位置:

(7)最近節(jié)點N1的連接邊老化度加1，如果老化度＞Agemax，則刪除該連接邊，同時刪除沒有連接邊的節(jié)點．

(8)返回步驟(2)，如果信號點個數(shù)為λ的整數(shù)倍且當前網(wǎng)絡(luò)節(jié)點未達到最大網(wǎng)絡(luò)節(jié)點數(shù)，則插入新節(jié)點N．新節(jié)點N產(chǎn)生步驟如下:①找到具有最大累計誤差的節(jié)點A;②找到與節(jié)點A連接的節(jié)點中具有最大累計誤差的節(jié)點B;③新節(jié)點向量④刪除節(jié)點A與節(jié)點B的連接邊，分別連接節(jié)點A與N，B與N;⑤ 更新節(jié)點空間N內(nèi)所有節(jié)點的累計誤差eN=eN-β×eN．

(9)網(wǎng)絡(luò)節(jié)點數(shù)達到設(shè)定數(shù)目，移動機器人駛向新目標點，返回步驟(2).

3 仿真實驗

3.1 探索路徑的生成

仿真實驗是在Matlab環(huán)境下進行的.工作環(huán)境選取10 m×10 m的未知環(huán)境，其中設(shè)有若干規(guī)則障礙物.移動機器人裝配有激光測距儀和里程計，激光傳感器探測距離為2 m，掃描角度為180°.仿真圖中用小圓圈表示移動機器人，半圓區(qū)域為激光測距儀掃描區(qū)域，其余圖形表示障礙物.

該仿真實驗中設(shè)定機器人步長為0.5 m，掃描分辨角度為10°，自轉(zhuǎn)角度為90°.機器人從初始位置開始，按照1.2節(jié)敘述的探索策略在未知環(huán)境中進行探索，其探索路徑如圖4所示.

圖4 探索過程Fig．4 Exploration procedure

3.2 環(huán)境地圖的構(gòu)建

在機器人探索環(huán)境過程中，按照第2節(jié)介紹的地圖構(gòu)建規(guī)則創(chuàng)建如圖5所示的環(huán)境地圖.該仿真實驗中，五角星表示GNG網(wǎng)絡(luò)的節(jié)點，每個節(jié)點表示一個以該節(jié)點為中心的可行區(qū)域，黑色連線表示各節(jié)點的連接邊.各參數(shù)取值如下:λ =200，ew=0．5，en=0．000 5，β =0．000 5，Agemax=108，最大網(wǎng)絡(luò)節(jié)點數(shù)設(shè)置為500.

圖5中的三幅圖依次與圖4中的三幅圖相對應(yīng)，通過仿真可以看到，移動機器人較為圓滿地完成了環(huán)境探索和地圖創(chuàng)建的任務(wù).在該環(huán)境中，機器人成功地躲避了障礙物，順利地完成環(huán)境的探索，基本上沒有出現(xiàn)陷入死區(qū)和環(huán)境信息的重復(fù)探測.在該探索過程中，路程損耗31.8 m，旋轉(zhuǎn)角度為389°，環(huán)境遍歷程度(覆蓋性)為92%.

圖5 地圖生成過程Fig．5 Map building procedure

由圖5中的三幅圖可知:①隨著機器人對環(huán)境探索的不斷深入，通過不斷地增加網(wǎng)絡(luò)節(jié)點來實時更新環(huán)境地圖，認識新的環(huán)境.因此，所提方法實現(xiàn)了自主機器人在環(huán)境探索的同時，同步進行地圖構(gòu)建的功能.②由最后獲得的環(huán)境地圖可以看出，用少量的GNG網(wǎng)絡(luò)節(jié)點就可以獲得大量的地圖信息，且機器人在環(huán)境中探索的時間越長，獲得可行區(qū)域的信息越多，對環(huán)境的認知就越充分.③驗證了所提出的拓撲地圖模型能很好地表示可行空間地圖的連通性，其具有的增長特性表示了機器人對環(huán)境的學(xué)習(xí)過程.

從仿真結(jié)果可以看出，利用GNG網(wǎng)絡(luò)生成的混合地圖有如下優(yōu)點:①GNG網(wǎng)絡(luò)通過對網(wǎng)絡(luò)節(jié)點累計誤差的計算來調(diào)整網(wǎng)絡(luò)節(jié)點的位置，從而保證生成的地圖網(wǎng)絡(luò)節(jié)點分布均勻.②GNG網(wǎng)絡(luò)可以動態(tài)地刪除、增加網(wǎng)絡(luò)節(jié)點以及連接邊，因此可以通過機器人的不斷巡游，把局部的環(huán)境信息連接起來形成全局環(huán)境地圖.③傳統(tǒng)的環(huán)境建模方法需要對傳感器采集的信息進行識別，確定墻壁或者障礙物，作者所提算法不需要對采集的信息進行識別，可減少計算的復(fù)雜度，尤其針對不規(guī)則障礙物的識別具有很好的處理效果.

4 結(jié)論

提出了未知環(huán)境中移動機器人同時環(huán)境探索和地圖構(gòu)建的策略方法.該方法利用隨機探索策略引導(dǎo)移動機器人在未知環(huán)境中進行探索，同時利用GNG網(wǎng)絡(luò)的增長特性，通過不斷增加新的拓撲網(wǎng)絡(luò)節(jié)點來對周圍環(huán)境進行抽象提取，隨著移動機器人的不斷探索，生成易于機器人理解的環(huán)境地圖，并能指示該地圖中的可行區(qū)域、障礙物等信息.采用該方法所建立的環(huán)境地圖，能使機器人在環(huán)境探索過程中，實時地更新地圖、學(xué)習(xí)環(huán)境，體現(xiàn)了聚類、降維、自學(xué)習(xí)及自適應(yīng)的特點.

［1］ Yamauchi B.A frontier-based approach for autonomous exploration［C］//Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation.Monterey，1997:146-151.

［2］ Tovar B，Murrieta-Cid R，Esteves C.Robot motion planning for map building［C］//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.Lausanne，2002:673-680.

［3］ Basilico N，Amigoni F.Exploration strategies based on multicriteria decision making for search and rescue autonomous robots［C］//Proceedings of 10th International Conference on Autonomous Agents and Multiagent Systems.Taipei，2011:99-106.

［4］ Jens W，Karsten B.Ground plan based exploration with a mobile indoor robot［C］//Proceedings of the 7th German Conference on Robotics.Munich，2012:452-457.

［5］ Hirashita S，Yairi T.Information-based exploration strategy for mobile robot in dynamic environment［C］//Proceedings of the 8th IEEE International Symposium on Computational Intelligence in Robotics and Automation.Daejeon，2009:90-95.

［6］ Taillandier P，Stinckwich S.Using the PROMETHEE multi-criteria decision making method to define new exploration strategies for rescue robots［C］//Proceedings of the IEEE International Symposium on Safety，Security，and Rescue Robotics.Kyoto，2011:321-326.

［7］ Freda L，Oriolo G.Frontier-based probabilistic strategies for sensor-based exploration［C］//Proceedings of the IEEE Interna-tional Conference on Robotics and Automation.Barcelona，2005:2892-2898.

［8］ Stachniss C，Burgard W.Exploring unknown environments with mobile robots using coverage maps［C］//Proceedings of the 18th International Joint Conference on Artificial Intelligence.San Francisco，2003:1127-1132.

［9］ González-Ba?os H H，Latombe J.Navigation strategies for exploring indoor environments［J］.International Journal of Robotic Research，2002，21(10/11):829-848.

［10］Dirk H，Nicola B，F(xiàn)rancesco A.A comparative evaluation of exploration strategies and heuristics to improve them［C］//Proceedings of the European Conference on Mobile Robotics.Oerebro，2011:1-6.

［11］張明狀，莊嚴，王偉，等.移動機器人即時環(huán)境探索與地圖庫構(gòu)建［J］.東南大學(xué)學(xué)報:自然科學(xué)版，2009，39(1):111-115.

［12］仲朝亮，劉士榮，楊帆.動態(tài)環(huán)境下基于GNG網(wǎng)絡(luò)的拓撲地圖構(gòu)建［J］.華東理工大學(xué)學(xué)報:自然科學(xué)版，2012，38(1):63-68.

［13］ Fritzke B.A growing neural gas network learns topologies［J］.Advances in Neural Information Processing Systems，1995(7):625-632.

［14］仲朝亮，劉士榮，邱雪娜.未知環(huán)境下基于GNG網(wǎng)絡(luò)的環(huán)境地圖自主認知［C］//第29屆中國控制會議.北京，2010:3768-3772.