基于隨機行走的群機器人二維地圖構建

陸國慶，孫 昊

（河北工業大學人工智能與數據科學學院，天津 300130）

0 引言

群機器人系統是由數量眾多、具有簡單結構和功能一致的機器人組成的，群體機器人是研究通過使用局部規則協調大量相對簡單機器人的群體［1］。它不同于單機器人或者多機器人系統，群機器人系統自身具有高度靈活性和較強的容錯性，能適應各種未知環境和高效率執行單個及多個任務。因此，群機器人廣泛應用于大規模偵察搜救、探索等領域。

目前移動機器人地圖所用到的傳感器主要有激光雷達和視覺傳感器。視覺傳感器主要有單目攝像頭和雙目攝像頭，所采集的圖像信息量大，但同時造成了很大的計算量；激光雷達的測量精確，雖然價格較昂貴，但應用場景十分廣泛，例如可以在黑暗環境下進行測量。由于傳感器的差異和環境中噪聲的影響，地圖構建技術主要存在的問題是測量誤差和信息的不完整［1］。單個機器人在構建環境地圖時，由于其自身的搜索范圍局限和自身發生故障等情況，對未知環境的地圖構建效率較低。群機器人的數量優勢以及較強的魯棒性，比單個機器人地圖構建的效率更高。

地圖構建作為同步定位與建圖（Simultaneous Localization and Mapping，SLAM）技術的一部分，目前大部分研究多集中于單個機器人，對于多個機器人構建未知環境地圖的研究較少。文獻［2］中利用多個搭載單目攝像頭的微型飛行器進行未知環境的地圖構建，設置地面固定站估計機器人位姿，然后構建每個機器人的地圖，最后再融合所有地圖，但是該方法采用視覺進行地圖構建，相較于激光雷達應用場景較為有限。文獻［3］中將粒子群算法應用到多機器人SLAM 中，計算兩個“相撞”機器人的相對位姿，將兩個機器人的先前和接下來的地圖信息融合成一個共同地圖；但是該算法兩個機器人之間的位姿計算相較于隨機行走算法較為復雜。文獻［4］中利用粒子群優化算法進行局部地圖間的配準，然后融合成全局地圖。文獻［5］中將未知環境劃分成4 個區域來避免多移動機器人陷入障礙物區域，對障礙物區域的地圖構建不夠準確，有一定的局限性。

隨機行走算法在群機器人中實現簡單，自由度和容錯性較高，與其他復雜的SLAM 算法相比，機器人之間不需要太多的交流以及機器人實時的定位，大大減少了算法計算的復雜度和時間。群機器人地圖構建中用到的隨機行走算法主要有布朗運動、相關隨機游走、Lévy flight、彈道運動等，這些隨機運動算法可以概述為：機器人隨機選擇一個運動方向，然后朝著該方向運動直到新的運動方向產生［6］。文獻［6］中對群機器人隨機行走構建地圖，對比了多種隨機行走算法進行小范圍的地圖構建，其中機器人運動采用彈道運動時效果較好；但機器人重復在小范圍內的隨機運動必然導致過多的重復搜索，降低了構建地圖的精確度，并且采用彈道運動的方法構建完整的小范圍地圖中殘留了過多的機器人的軌跡，影響了地圖構建的準確性。Pang等［7］提出了一種基于布朗運動和Lévy flight 的改進隨機行走方法，該方法將機器人分散在不同的區域并通過控制群機器人的搜索區域和搜索步長來減小搜索的重復區域，提高了搜索效率。該方法雖然能夠提高搜索效率，但需要根據環境的變化去頻繁調整機器人的搜索區域面積和步長，并且在未知的大環境中并不能很好地調整合適每個機器人的搜索面積的大小以及解決如何分散放置的問題，設置過大的搜索步長容易錯失較多的區域地圖信息。Ramachandran 等［8］提出了一種只需依賴局部機器人間交流的分布式構建地圖方法，每個機器人都裝備激光雷達傳感器，通過自身的距離測量和相鄰機器人傳遞的地圖信息來構建地圖，機器人的運動采用基于機器人間相互信息影響的Lévy flight，該算法中傳遞地圖信息需要機器人之間良好的溝通，機器人隨機行走可能會出現接收其他機器人信息不完全的情況。本文中所有機器人產生的局部地圖由固定節點的地圖融合算法進行融合，避免了機器人間傳遞地圖信息導致的誤差和復雜度。在利用隨機行走及其相關改進算法進行多機器人建圖的相關研究中，雖然都可以進行一定范圍的未知環境地圖構建，但是由于隨機行走的隨機性，難以避免多個機器人重復搜索某個區域的問題，降低了多個機器人的地圖構建效率，機器人搜索過程中頻繁的大范圍的角度旋轉也會增大地圖構建的準確性。對于未知環境，如何簡單高效地構建出更大范圍的環境地圖仍是一個研究熱點。

本文對布朗運動進行改進，提出了一種適合群機器人快速搜索和精確構建環境地圖的改進布朗運動隨機行走算法，通過改進的布朗運動，使機器人在不進行局部溝通的情況下也能搜索到更多的區域，并且通過限制機器人隨機行走的旋轉角度使機器人相同時間內可以搜索到更多的區域，機器人隨機行走中旋轉次數的減少也提高了構建地圖的精度。本文算法計算簡單，降低了復雜度。該算法中個體機器人的移動是隨機向前運動隨機距離，然后旋轉隨機角度來模擬分子的布朗運動，對機器人旋轉角度進行了限制，使群體中的單個機器人能夠在初始運動方向的具體范圍內隨機向前運動，降低搜索區域的重復度，避免了因為運動方向突變導致機器人構建地圖的面積和準確度的下降。機器人在搜索過程中利用激光雷達傳感器構建環境地圖。在仿真實驗中，搭載激光雷達的多個移動機器人依靠改進布朗運動隨機行走算法自主地進行搜索和搜索區域建圖，并且在仿真環境中加入一些障礙物，在單個機器人隨機行走算法中加入避障算法。地圖構建算法和地圖融合算法分別采用了GMapping 算法和Multirobot_map_merge算法。

1 隨機行走算法

隨機行走又稱為隨機漫步、隨機游走等，這類運動的特征是無法根據前一步的運動去預測下一步的運動方向，“隨機游走”一詞最早由卡爾·皮爾森于1905 年提出。隨機游走可應用于許多科學領域，包括生態學、心理學、計算機科學、物理學、化學、生物學以及經濟學。

布朗運動{B(t)，t≥0}是一個非負實域連續的隨機過程，它滿足B(0)=0，并且{B(t)-B(s)}～N(0，t-s)。應用在機器人隨機行走中，機器人向前移動由正態分布函數隨機產生的給定步長，然后轉向從搜索空間隨機選擇的方向，依次重復這個過程。

本文提出了一種基于改進布朗運動的隨機行走算法。在該算法中，群機器人初始位置固定，機器人群數量為N，機器人步長α為標準正態分布中的任意正數取值，保證機器人始終向前運動，因此每一步的步長任意變化，單個機器人初始速度為V，單個機器人的初始位置已知。假定地圖中心點為全局坐標系原點，可以得到第n個機器人初始坐標和初始運動方向，則單個機器人初始位姿可以用（xn0，yn0，θn0）表示。單個機器人的隨機行走算法如圖1 所示。初始時，機器人在初始位置在某個范圍內隨機選擇轉角增量，前進一個步長，然后重復此過程，運動過程中機器人的速度恒定。改進布朗運動隨機行走算法的數學模型如下：

圖1 單個機器人模擬布朗運動示意圖Fig.1 Schematic diagram of single robot simulating Brownian motion

其中：Sn表示第n個機器人在M步長里運動的總里程，αi表示機器人第i步的步長，P為標準正態分布函數的值域；（xn，yn）表示機器人第n個機器人在第i步長的坐標，θni表示第n個機器人在第i步長的運動方向，l為[-1，1]區間的隨機數，β表示單位轉角增量。

為了使群機器人在最短時間內提取到更多環境特征，本文提出的隨機行走算法與其他隨機行走不同之處在于機器人隨機行走時角度變化被限定在固定范圍內，每前進一個步長都要進行運動方向的角度調整，角度調整的可變范圍是一定的，這樣就保證了每個機器人能夠依照初始運動方向在某個梯形區域內運動，避免了因為大幅度旋轉角度變化造成的某個區域的缺失，運動過程中依靠機器人里程計可以實時得到機器人位置。環境范圍越大，機器人個體的數量越多，機器人可掃描到的區域越大，構建的地圖越精確。

本文使用Matlab分別對布朗運動和本文提出的改進布朗運動隨機行走進行了簡單的無障礙物群機器人的運動軌跡仿真，初始坐標點為（0，0），機器人數量為10，二者的運動步數均設置為100，單位轉角增量β設置為30°。布朗運動的仿真結果如圖2（a）所示，本文提出的算法的仿真結果如圖2（b）所示。從機器人運動軌跡仿真結果可以看出，相同步數下，機器人布朗運動搜索到的區域重復性很高，相較于本文提出的改進布朗運動隨機行走算法小得多；本文提出的改進布朗運動隨機行走算法覆蓋的區域較大，而且減小了搜索區域的重復度，提高了群機器人地圖構建的效率。

在實際實驗過程中，由于在實驗環境中添加了障礙物，所以為了避免與障礙物相撞使機器人無法運動，本文采用了簡單的避障算法，如圖3 所示。該算法通過激光雷達采集到的數據判斷與障礙物的距離，設置最小距離D，當機器人激光雷達采集到的距離數據最小值小于D時，停止隨機行走，機器人的旋轉γ設置為60°。

圖3 避障過程Fig.3 Obstacle avoidance process

2 群機器人地圖構建

2.1 GMapping算法

機器人構建的地圖一般分為柵格地圖、拓撲地圖、特征地圖，本次介紹的GMapping 算法［9］，所構建的是二維柵格地圖。在本文中，搭載激光雷達傳感器的單個機器人對環境進行地圖構建采用了GMapping 算法。GMapping 為2007 年在機器人操作系統（Robot Operating System，ROS）中開源的SLAM 軟件包，是目前使用最廣泛的軟件包。它可用于室內和室外，應用改進的自適應Rao-Blackwellized 粒子濾波算法來進行定位與建圖。GMapping 可以實時構建室內地圖，在構建小場景地圖時所需的計算量較小且精度較高，并有效利用了車輪里程計信息，相較于Hector 和Cartographer 算法，對激光雷達頻率要求低、魯棒性高，不需要太多的粒子且沒有回環檢測，因此計算量小于Cartographer而精度相差不大。該算法基于RBPF粒子濾波算法，即將定位和建圖過程分離，先進行定位再進行建圖。GMapping 在RBPF 算法上做了兩個主要的改進：改進提議分布和選擇性重采樣。ROS中GMapping框架如圖4所示。

圖4 ROS中GMapping框架Fig.4 GMapping framework in ROS

2.2 Multirobot_map_merge算法

Multirobot_map_merge 算法的實現基于ROS 框架，主要解決了運動的機器人識別、初始位姿估計和地圖合成問題［10］。借助ROS 的通信機制，機器人的內部交流只需要依賴ROS 的話題機制和服務機制。該算法可以合成任意數量機器人的地圖，并且可以在實驗環境下改變機器人的數量，因此特別適合大規模數量的機器人地圖合成。ROS 中Multirobot_map_merge 框架圖如圖5 所示。本文的群機器人中的每個機器人在運動過程中通過話題機制向Multirobot_map_merge 節點發布話題，通過訂閱每個機器人的話題將局部地圖合成為全局地圖。

圖5 ROS中multirobot_map_merge框架圖Fig.5 multirobot_map_merge framework in ROS

機器人的局部地圖融合成全局地圖過程中，首先需要計算機器人和全局坐標系之間的坐標變換，假定機器人的坐標系相對于全局坐標系的變換需要分別在X軸和Y軸平移a、b個單位，然后旋轉φ，則機器人坐標系在全局坐標系下的變換關系可以表示為：

在對局部地圖進行平移旋轉變換后，再對局部地圖中的關鍵特征（黑色所表示的障礙物部分）進行檢測，對局部地圖中相互重合的部分進行特征匹配，保留每個局部地圖重疊部分的特征，最后在地圖重合部分對關鍵特征進行校準，校準中需要對重疊區域黑色柵格所占據的部分進行統一化校對，即采取“求同去異”原則。只處理每個機器人的局部地圖重合區域的關鍵特征一定程度降低了計算的復雜度。

3 仿真實驗

3.1 實驗環境

本次實驗在Linux 系統下基于ROS 通信框架進行，Stage是ROS 中的一個實現物理仿真的工具包，可以模擬機器人以及環境中的很多物理特性。通過Stage搭建了一個20 m×20 m的環境，在環境中添加障礙物，如圖6 所示。仿真實驗所用的機器人為TurtleBot，TurtleBot 配備了一個激光雷達用于地圖構建，可以很好地采集周圍環境特征用于更精確的建圖。實驗中采用Rviz 顯示機器人的運動狀態和地圖信息，Rviz 是一款顯示多種數據的三維可視化工具，能夠實時顯示機器人傳感器的信息、機器人的運動狀態、周圍環境的變化等。圖7 是群機器人在仿真中的通信結構，包括各節點發布及訂閱的話題和消息。圖8是各個機器人坐標之間的關系。

圖6 Stage中的仿真環境Fig.6 Simulation environment created in Stage

圖7 ROS下機器人的節點和話題Fig.7 Nodes and topics of robots under ROS

圖8 ROS下機器人坐標之間的關系Fig.8 Coordinates relationship of robots under ROS

3.2 實驗過程和結果

群機器人隨機行走進行建圖，不同機器人數量、最大轉角增量的大小、隨機行走的步數都是影響地圖構建的重要因素，為了探究本文提出的改進布朗運動隨機行走算法的優越性，分別從機器人數量、最大轉角增量、行走步數等方面與布朗運動進行對比驗證。實驗仿真環境的完整地圖如圖9所示。

圖9 仿真環境完整地圖Fig.9 Complete map of simulation environment

3.2.1 不同最大轉角增量

實驗開始時將機器人組成的群體放置于地圖固定區域，初始運動方向隨機設置，機器人激光雷達的掃描角度為120°，機器人的最大轉角增量分別設置為β=30°，β=90°，β=180°。機器人數量設置為3，初始位姿分別為（0，0，0）、（0，1，0）、(0，-1，0)，運動步數設置為100。不同最大轉角增量重復進行10 次實驗，選取最優地圖進行對比，實驗結果如圖10所示。

3.2.2 不同機器人數量

實驗開始時將機器人組成的群體放置于地圖固定區域，初始運動方向隨機設置，機器人激光雷達的掃描角度為120°，群機器人初始最大轉角增量為30°，運動步數設置為100。機器人數量分別設置為3和5，如圖6所示，初始位姿分別設置為（0，0，0）、（0，1，0）、(0，-1，0)和（0，0，0）、（0，1，0）、(0，-1，0)、（2，0，0）、(-2，0，0)。不同機器人數量重復進行10 次實驗，選取最優地圖進行對比，實驗結果如圖11所示。

3.2.3 不同運動步數

實驗開始時將機器人組成的群體放置于地圖固定區域，初始運動方向固定，機器人激光雷達的掃描角度為120°，群機器人初始最大轉角增量為30°，機器人數量設置為3，初始位姿分別為（0，0，0）、（0，1，0）、(0，-1，0)，運動步數設置分別為50、100、200。不同運動步數重復進行10 次實驗，選取最優地圖進行對比，實驗結果如圖12所示。

圖12 群機器人不同運動步數地圖構建Fig.12 Mapping of swarm robots with different movement steps

3.2.4 不同方法

本文提出的改進布朗運動與文獻［6］中提出的彈道運動方法進行了相同運動步數下建圖效果的對比，包括最后建圖的實際仿真效果圖以及機器人的運動軌跡圖的對比。機器人搜索時間設置為60 s，改進布朗運動的最大轉角增量設置為30°，機器人數量設置為3，初始位姿分別為（0，0，0）、（0，1，0）、（0，-1，0）。最終實驗結果如圖13和表4所示。

表4 不同機器人運動方法覆蓋率對比Tab.4 Comparison of coverage ratio with different robot movement methods

圖13 群機器人不同方法地圖構建Fig.13 Mapping of swarm robots with different methods

3.2.5 實驗結果分析

移動機器人激光雷達采用GMapping 算法所構建的是二維柵格地圖，地圖的灰色區域代表未知區域，白色區域代表已搜索區域，黑色線條表示障礙物。對群機器人隨機行走構建的地圖結果與仿真環境地圖比較，從搜索區域大小和準確度兩方面進行定性分析。

如圖10 所示，在機器人數量、運動步數相同，不同最大轉角增量情況下，最大轉角增量越大，機器人隨機運動方向的選擇范圍越大，機器人搜索區域的重復面積也越大，機器人運動可旋轉的角度越大，導致運動方向大幅度的隨機變化，使得激光雷達構建的地圖的準確性下降，群機器人采取布朗運動構建地圖面積最小，地圖準確度也最差。

圖10 群機器人不同最大轉角增量地圖構建Fig.10 Mapping of swarm robots under different maximum rotation angle increments

如圖11 所示，在最大轉角增量、運動步數相同，機器人數量不同的情況下，機器人數量由3 個增加到5 個時，相同運動步數下，群機器人的搜索區域面積明顯增加，相較布朗運動，改進布朗運動所構建地圖的精度更高；但是受限于激光雷達的仿真精確性，理論上機器人數量越多，所需要的計算能力越高，所以在準確性上會出現構建地圖的準確度略微下降的情況。在本次仿真實驗中，受限于自身實驗電腦的配置，只進行了3個和5個機器人的仿真實驗，但是從仿真中也可以明顯看出本文提出的改進布朗運動隨機行走的優越性。

圖12 展示本文提出的改進布朗運動隨機行走和布朗運動在不同運動步數下機器人構建地圖的面積和準確性。與布朗運動相比，隨著運動步數的增加，群機器人構建地圖的面積也在增加，本文改進布朗運動隨機行走能夠搜索到更大區域，構建的地圖面積和地圖精確性更高。布朗運動構建的地圖發生整體歪斜的情況，這是由于在大范圍旋轉時過多重復搜索區域導致地圖準確度下降。

表1～4 分別從機器人構建的地圖覆蓋率的平均值、標準差、建圖效率定量分析了最大轉角增量、機器人數量和運動步數對地圖構建的影響。地圖覆蓋率是指已構建的地圖面積與總的環境地圖面積的比值，地圖覆蓋率的平均值反映了地圖構建的區域的面積；標準差反映了建圖的準確度，標準差的衡量主要通過真實地圖與所構建地圖重合度的計算，標準差越大，地圖的準確度越高。為了從時間和空間角度定量評價建圖的可靠性，通過計算所構建地圖的覆蓋面積與搜索時間的比值以及標準差的關系來綜合評價建圖效率，建圖效率的值越大，建圖效率越高。

表1 不同最大轉角增量覆蓋率對比Tab.1 Comparison of coverage ratio with different maximum rotation angle increments

表2 不同數量機器人覆蓋率對比Tab.2 Comparison of coverage ratio with different numbers of robots

表3 不同運動步數覆蓋率對比Tab.3 Comparison of coverage ratio with different movement steps

在改進布朗運動與采用彈道運動進行建圖的對比中，通過圖13 的相同時間下最終建圖結果與機器人的運動軌跡中可以看出，改進后的布朗運動能夠搜索到更多的區域，在表4的定量分析中，改進布朗運動在地圖覆蓋率以及地圖構建準確度方面都要優于彈道運動。

從仿真實驗的結果中可以看出，本文提出的改進布朗運動隨機行走算法通過限制機器人隨機運動時的旋轉角度范圍減少了重復區域的搜索，提高了未知環境下地圖構建效率。在相同環境下，機器人數量和運動步數都會對所構建地圖產生影響，通過對機器人旋轉角度的限制可以很好地避免由于大范圍旋轉造成的偏差，提高群機器人構建的地圖的精度。

4 結語

未知環境的地圖構建作為機器人領域的重要部分，對機器人發展有著深遠的影響，本文針對機器人在未知環境快速和準確地構建環境地圖進行了研究，提出了一種基于布朗運動的群機器人改進布朗運動隨機行走算法，該算法在群機器人地圖構建中的應用使機器人能在不進行復雜溝通情況下快速構建未知環境地圖，提高了地圖構建效率。受限于激光雷達和里程計的準確性，機器人構建地圖時不可避免存在一定的誤差，導致構建的地圖準確度略有下降，未來會通過相關算法對誤差進行補償和構建地圖的校正。另外，群機器人在未知環境探索領域的應用相較復雜結構的單個機器人具有更大的優勢，以后的研究工作應該致力于實現復雜未知場景下精確地圖的構建等相關工作。