基于隨機(jī)行走的群機(jī)器人二維地圖構(gòu)建

陸國慶，孫 昊

（河北工業(yè)大學(xué)人工智能與數(shù)據(jù)科學(xué)學(xué)院，天津 300130）

0 引言

群機(jī)器人系統(tǒng)是由數(shù)量眾多、具有簡單結(jié)構(gòu)和功能一致的機(jī)器人組成的，群體機(jī)器人是研究通過使用局部規(guī)則協(xié)調(diào)大量相對(duì)簡單機(jī)器人的群體［1］。它不同于單機(jī)器人或者多機(jī)器人系統(tǒng)，群機(jī)器人系統(tǒng)自身具有高度靈活性和較強(qiáng)的容錯(cuò)性，能適應(yīng)各種未知環(huán)境和高效率執(zhí)行單個(gè)及多個(gè)任務(wù)。因此，群機(jī)器人廣泛應(yīng)用于大規(guī)模偵察搜救、探索等領(lǐng)域。

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

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

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

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

1 隨機(jī)行走算法

隨機(jī)行走又稱為隨機(jī)漫步、隨機(jī)游走等，這類運(yùn)動(dòng)的特征是無法根據(jù)前一步的運(yùn)動(dòng)去預(yù)測(cè)下一步的運(yùn)動(dòng)方向，“隨機(jī)游走”一詞最早由卡爾·皮爾森于1905 年提出。隨機(jī)游走可應(yīng)用于許多科學(xué)領(lǐng)域，包括生態(tài)學(xué)、心理學(xué)、計(jì)算機(jī)科學(xué)、物理學(xué)、化學(xué)、生物學(xué)以及經(jīng)濟(jì)學(xué)。

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

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

圖1 單個(gè)機(jī)器人模擬布朗運(yùn)動(dòng)示意圖Fig.1 Schematic diagram of single robot simulating Brownian motion

其中：Sn表示第n個(gè)機(jī)器人在M步長里運(yùn)動(dòng)的總里程，αi表示機(jī)器人第i步的步長，P為標(biāo)準(zhǔn)正態(tài)分布函數(shù)的值域；（xn，yn）表示機(jī)器人第n個(gè)機(jī)器人在第i步長的坐標(biāo)，θni表示第n個(gè)機(jī)器人在第i步長的運(yùn)動(dòng)方向，l為[-1，1]區(qū)間的隨機(jī)數(shù)，β表示單位轉(zhuǎn)角增量。

為了使群機(jī)器人在最短時(shí)間內(nèi)提取到更多環(huán)境特征，本文提出的隨機(jī)行走算法與其他隨機(jī)行走不同之處在于機(jī)器人隨機(jī)行走時(shí)角度變化被限定在固定范圍內(nèi)，每前進(jìn)一個(gè)步長都要進(jìn)行運(yùn)動(dòng)方向的角度調(diào)整，角度調(diào)整的可變范圍是一定的，這樣就保證了每個(gè)機(jī)器人能夠依照初始運(yùn)動(dòng)方向在某個(gè)梯形區(qū)域內(nèi)運(yùn)動(dòng)，避免了因?yàn)榇蠓刃D(zhuǎn)角度變化造成的某個(gè)區(qū)域的缺失，運(yùn)動(dòng)過程中依靠機(jī)器人里程計(jì)可以實(shí)時(shí)得到機(jī)器人位置。環(huán)境范圍越大，機(jī)器人個(gè)體的數(shù)量越多，機(jī)器人可掃描到的區(qū)域越大，構(gòu)建的地圖越精確。

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

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

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

2 群機(jī)器人地圖構(gòu)建

2.1 GMapping算法

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

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

2.2 Multirobot_map_merge算法

Multirobot_map_merge 算法的實(shí)現(xiàn)基于ROS 框架，主要解決了運(yùn)動(dòng)的機(jī)器人識(shí)別、初始位姿估計(jì)和地圖合成問題［10］。借助ROS 的通信機(jī)制，機(jī)器人的內(nèi)部交流只需要依賴ROS 的話題機(jī)制和服務(wù)機(jī)制。該算法可以合成任意數(shù)量機(jī)器人的地圖，并且可以在實(shí)驗(yàn)環(huán)境下改變機(jī)器人的數(shù)量，因此特別適合大規(guī)模數(shù)量的機(jī)器人地圖合成。ROS 中Multirobot_map_merge 框架圖如圖5 所示。本文的群機(jī)器人中的每個(gè)機(jī)器人在運(yùn)動(dòng)過程中通過話題機(jī)制向Multirobot_map_merge 節(jié)點(diǎn)發(fā)布話題，通過訂閱每個(gè)機(jī)器人的話題將局部地圖合成為全局地圖。

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

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

在對(duì)局部地圖進(jìn)行平移旋轉(zhuǎn)變換后，再對(duì)局部地圖中的關(guān)鍵特征（黑色所表示的障礙物部分）進(jìn)行檢測(cè)，對(duì)局部地圖中相互重合的部分進(jìn)行特征匹配，保留每個(gè)局部地圖重疊部分的特征，最后在地圖重合部分對(duì)關(guān)鍵特征進(jìn)行校準(zhǔn)，校準(zhǔn)中需要對(duì)重疊區(qū)域黑色柵格所占據(jù)的部分進(jìn)行統(tǒng)一化校對(duì)，即采取“求同去異”原則。只處理每個(gè)機(jī)器人的局部地圖重合區(qū)域的關(guān)鍵特征一定程度降低了計(jì)算的復(fù)雜度。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

本次實(shí)驗(yàn)在Linux 系統(tǒng)下基于ROS 通信框架進(jìn)行，Stage是ROS 中的一個(gè)實(shí)現(xiàn)物理仿真的工具包，可以模擬機(jī)器人以及環(huán)境中的很多物理特性。通過Stage搭建了一個(gè)20 m×20 m的環(huán)境，在環(huán)境中添加障礙物，如圖6 所示。仿真實(shí)驗(yàn)所用的機(jī)器人為TurtleBot，TurtleBot 配備了一個(gè)激光雷達(dá)用于地圖構(gòu)建，可以很好地采集周圍環(huán)境特征用于更精確的建圖。實(shí)驗(yàn)中采用Rviz 顯示機(jī)器人的運(yùn)動(dòng)狀態(tài)和地圖信息，Rviz 是一款顯示多種數(shù)據(jù)的三維可視化工具，能夠?qū)崟r(shí)顯示機(jī)器人傳感器的信息、機(jī)器人的運(yùn)動(dòng)狀態(tài)、周圍環(huán)境的變化等。圖7 是群機(jī)器人在仿真中的通信結(jié)構(gòu)，包括各節(jié)點(diǎn)發(fā)布及訂閱的話題和消息。圖8是各個(gè)機(jī)器人坐標(biāo)之間的關(guān)系。

圖6 Stage中的仿真環(huán)境Fig.6 Simulation environment created in Stage

圖7 ROS下機(jī)器人的節(jié)點(diǎn)和話題Fig.7 Nodes and topics of robots under ROS

圖8 ROS下機(jī)器人坐標(biāo)之間的關(guān)系Fig.8 Coordinates relationship of robots under ROS

3.2 實(shí)驗(yàn)過程和結(jié)果

群機(jī)器人隨機(jī)行走進(jìn)行建圖，不同機(jī)器人數(shù)量、最大轉(zhuǎn)角增量的大小、隨機(jī)行走的步數(shù)都是影響地圖構(gòu)建的重要因素，為了探究本文提出的改進(jìn)布朗運(yùn)動(dòng)隨機(jī)行走算法的優(yōu)越性，分別從機(jī)器人數(shù)量、最大轉(zhuǎn)角增量、行走步數(shù)等方面與布朗運(yùn)動(dòng)進(jìn)行對(duì)比驗(yàn)證。實(shí)驗(yàn)仿真環(huán)境的完整地圖如圖9所示。

圖9 仿真環(huán)境完整地圖Fig.9 Complete map of simulation environment

3.2.1 不同最大轉(zhuǎn)角增量

實(shí)驗(yàn)開始時(shí)將機(jī)器人組成的群體放置于地圖固定區(qū)域，初始運(yùn)動(dòng)方向隨機(jī)設(shè)置，機(jī)器人激光雷達(dá)的掃描角度為120°，機(jī)器人的最大轉(zhuǎn)角增量分別設(shè)置為β=30°，β=90°，β=180°。機(jī)器人數(shù)量設(shè)置為3，初始位姿分別為（0，0，0）、（0，1，0）、(0，-1，0)，運(yùn)動(dòng)步數(shù)設(shè)置為100。不同最大轉(zhuǎn)角增量重復(fù)進(jìn)行10 次實(shí)驗(yàn)，選取最優(yōu)地圖進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖10所示。

3.2.2 不同機(jī)器人數(shù)量

實(shí)驗(yàn)開始時(shí)將機(jī)器人組成的群體放置于地圖固定區(qū)域，初始運(yùn)動(dòng)方向隨機(jī)設(shè)置，機(jī)器人激光雷達(dá)的掃描角度為120°，群機(jī)器人初始最大轉(zhuǎn)角增量為30°，運(yùn)動(dòng)步數(shù)設(shè)置為100。機(jī)器人數(shù)量分別設(shè)置為3和5，如圖6所示，初始位姿分別設(shè)置為（0，0，0）、（0，1，0）、(0，-1，0)和（0，0，0）、（0，1，0）、(0，-1，0)、（2，0，0）、(-2，0，0)。不同機(jī)器人數(shù)量重復(fù)進(jìn)行10 次實(shí)驗(yàn)，選取最優(yōu)地圖進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖11所示。

3.2.3 不同運(yùn)動(dòng)步數(shù)

實(shí)驗(yàn)開始時(shí)將機(jī)器人組成的群體放置于地圖固定區(qū)域，初始運(yùn)動(dòng)方向固定，機(jī)器人激光雷達(dá)的掃描角度為120°，群機(jī)器人初始最大轉(zhuǎn)角增量為30°，機(jī)器人數(shù)量設(shè)置為3，初始位姿分別為（0，0，0）、（0，1，0）、(0，-1，0)，運(yùn)動(dòng)步數(shù)設(shè)置分別為50、100、200。不同運(yùn)動(dòng)步數(shù)重復(fù)進(jìn)行10 次實(shí)驗(yàn)，選取最優(yōu)地圖進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖12所示。

圖12 群機(jī)器人不同運(yùn)動(dòng)步數(shù)地圖構(gòu)建Fig.12 Mapping of swarm robots with different movement steps

3.2.4 不同方法

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

表4 不同機(jī)器人運(yùn)動(dòng)方法覆蓋率對(duì)比Tab.4 Comparison of coverage ratio with different robot movement methods

圖13 群機(jī)器人不同方法地圖構(gòu)建Fig.13 Mapping of swarm robots with different methods

3.2.5 實(shí)驗(yàn)結(jié)果分析

移動(dòng)機(jī)器人激光雷達(dá)采用GMapping 算法所構(gòu)建的是二維柵格地圖，地圖的灰色區(qū)域代表未知區(qū)域，白色區(qū)域代表已搜索區(qū)域，黑色線條表示障礙物。對(duì)群機(jī)器人隨機(jī)行走構(gòu)建的地圖結(jié)果與仿真環(huán)境地圖比較，從搜索區(qū)域大小和準(zhǔn)確度兩方面進(jìn)行定性分析。

如圖10 所示，在機(jī)器人數(shù)量、運(yùn)動(dòng)步數(shù)相同，不同最大轉(zhuǎn)角增量情況下，最大轉(zhuǎn)角增量越大，機(jī)器人隨機(jī)運(yùn)動(dòng)方向的選擇范圍越大，機(jī)器人搜索區(qū)域的重復(fù)面積也越大，機(jī)器人運(yùn)動(dòng)可旋轉(zhuǎn)的角度越大，導(dǎo)致運(yùn)動(dòng)方向大幅度的隨機(jī)變化，使得激光雷達(dá)構(gòu)建的地圖的準(zhǔn)確性下降，群機(jī)器人采取布朗運(yùn)動(dòng)構(gòu)建地圖面積最小，地圖準(zhǔn)確度也最差。

圖10 群機(jī)器人不同最大轉(zhuǎn)角增量地圖構(gòu)建Fig.10 Mapping of swarm robots under different maximum rotation angle increments

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

圖12 展示本文提出的改進(jìn)布朗運(yùn)動(dòng)隨機(jī)行走和布朗運(yùn)動(dòng)在不同運(yùn)動(dòng)步數(shù)下機(jī)器人構(gòu)建地圖的面積和準(zhǔn)確性。與布朗運(yùn)動(dòng)相比，隨著運(yùn)動(dòng)步數(shù)的增加，群機(jī)器人構(gòu)建地圖的面積也在增加，本文改進(jìn)布朗運(yùn)動(dòng)隨機(jī)行走能夠搜索到更大區(qū)域，構(gòu)建的地圖面積和地圖精確性更高。布朗運(yùn)動(dòng)構(gòu)建的地圖發(fā)生整體歪斜的情況，這是由于在大范圍旋轉(zhuǎn)時(shí)過多重復(fù)搜索區(qū)域?qū)е碌貓D準(zhǔn)確度下降。

表1～4 分別從機(jī)器人構(gòu)建的地圖覆蓋率的平均值、標(biāo)準(zhǔn)差、建圖效率定量分析了最大轉(zhuǎn)角增量、機(jī)器人數(shù)量和運(yùn)動(dòng)步數(shù)對(duì)地圖構(gòu)建的影響。地圖覆蓋率是指已構(gòu)建的地圖面積與總的環(huán)境地圖面積的比值，地圖覆蓋率的平均值反映了地圖構(gòu)建的區(qū)域的面積；標(biāo)準(zhǔn)差反映了建圖的準(zhǔn)確度，標(biāo)準(zhǔn)差的衡量主要通過真實(shí)地圖與所構(gòu)建地圖重合度的計(jì)算，標(biāo)準(zhǔn)差越大，地圖的準(zhǔn)確度越高。為了從時(shí)間和空間角度定量評(píng)價(jià)建圖的可靠性，通過計(jì)算所構(gòu)建地圖的覆蓋面積與搜索時(shí)間的比值以及標(biāo)準(zhǔn)差的關(guān)系來綜合評(píng)價(jià)建圖效率，建圖效率的值越大，建圖效率越高。

表1 不同最大轉(zhuǎn)角增量覆蓋率對(duì)比Tab.1 Comparison of coverage ratio with different maximum rotation angle increments

表2 不同數(shù)量機(jī)器人覆蓋率對(duì)比Tab.2 Comparison of coverage ratio with different numbers of robots

表3 不同運(yùn)動(dòng)步數(shù)覆蓋率對(duì)比Tab.3 Comparison of coverage ratio with different movement steps

在改進(jìn)布朗運(yùn)動(dòng)與采用彈道運(yùn)動(dòng)進(jìn)行建圖的對(duì)比中，通過圖13 的相同時(shí)間下最終建圖結(jié)果與機(jī)器人的運(yùn)動(dòng)軌跡中可以看出，改進(jìn)后的布朗運(yùn)動(dòng)能夠搜索到更多的區(qū)域，在表4的定量分析中，改進(jìn)布朗運(yùn)動(dòng)在地圖覆蓋率以及地圖構(gòu)建準(zhǔn)確度方面都要優(yōu)于彈道運(yùn)動(dòng)。

從仿真實(shí)驗(yàn)的結(jié)果中可以看出，本文提出的改進(jìn)布朗運(yùn)動(dòng)隨機(jī)行走算法通過限制機(jī)器人隨機(jī)運(yùn)動(dòng)時(shí)的旋轉(zhuǎn)角度范圍減少了重復(fù)區(qū)域的搜索，提高了未知環(huán)境下地圖構(gòu)建效率。在相同環(huán)境下，機(jī)器人數(shù)量和運(yùn)動(dòng)步數(shù)都會(huì)對(duì)所構(gòu)建地圖產(chǎn)生影響，通過對(duì)機(jī)器人旋轉(zhuǎn)角度的限制可以很好地避免由于大范圍旋轉(zhuǎn)造成的偏差，提高群機(jī)器人構(gòu)建的地圖的精度。

4 結(jié)語

未知環(huán)境的地圖構(gòu)建作為機(jī)器人領(lǐng)域的重要部分，對(duì)機(jī)器人發(fā)展有著深遠(yuǎn)的影響，本文針對(duì)機(jī)器人在未知環(huán)境快速和準(zhǔn)確地構(gòu)建環(huán)境地圖進(jìn)行了研究，提出了一種基于布朗運(yùn)動(dòng)的群機(jī)器人改進(jìn)布朗運(yùn)動(dòng)隨機(jī)行走算法，該算法在群機(jī)器人地圖構(gòu)建中的應(yīng)用使機(jī)器人能在不進(jìn)行復(fù)雜溝通情況下快速構(gòu)建未知環(huán)境地圖，提高了地圖構(gòu)建效率。受限于激光雷達(dá)和里程計(jì)的準(zhǔn)確性，機(jī)器人構(gòu)建地圖時(shí)不可避免存在一定的誤差，導(dǎo)致構(gòu)建的地圖準(zhǔn)確度略有下降，未來會(huì)通過相關(guān)算法對(duì)誤差進(jìn)行補(bǔ)償和構(gòu)建地圖的校正。另外，群機(jī)器人在未知環(huán)境探索領(lǐng)域的應(yīng)用相較復(fù)雜結(jié)構(gòu)的單個(gè)機(jī)器人具有更大的優(yōu)勢(shì)，以后的研究工作應(yīng)該致力于實(shí)現(xiàn)復(fù)雜未知場(chǎng)景下精確地圖的構(gòu)建等相關(guān)工作。