基于均勻掃描和專注引導(dǎo)策略的自主探索算法

摘 要：為解決機(jī)器人難以快速探索含有狹窄入口的未知環(huán)境，以及在探索收益接近的目標(biāo)之間徘徊探索而導(dǎo)致探索效率降低的問(wèn)題，提出一種包含均勻掃描和專注引導(dǎo)策略的自主探索算法USAGE。USAGE采用均勻掃描的方式檢測(cè)地圖的邊界點(diǎn)，并對(duì)邊界點(diǎn)進(jìn)行聚類得到待探索點(diǎn)。最后通過(guò)專注引導(dǎo)策略確定最優(yōu)探索目標(biāo)，在含有信息增益和路徑代價(jià)的傳統(tǒng)評(píng)價(jià)函數(shù)中引入轉(zhuǎn)向代價(jià)評(píng)估指標(biāo)，并根據(jù)機(jī)器人的狀態(tài)約束探索任務(wù)執(zhí)行，引導(dǎo)機(jī)器人專注探索。通過(guò)在機(jī)器人操作系統(tǒng)搭建仿真環(huán)境進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，與基于快速探索隨機(jī)樹(shù)（rapidly-exploring random tree，RRT）的探索算法相比，USAGE占用系統(tǒng)內(nèi)存減少了11.34%以上，在探索耗時(shí)和探索距離方面分別減小了26.90%和31.94%，提升了自主探索效率。

關(guān)鍵詞：機(jī)器人； 自主探索； 邊界點(diǎn)； 評(píng)價(jià)函數(shù)； 機(jī)器人操作系統(tǒng)

中圖分類號(hào)：TP242.6 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）11-031-3415-05

doi：10.19734/j.issn.1001-3695.2024.02.0074

Autonomous exploration algorithm based on uniform scanning and attentive guidance explorer

Shen Weilin^a， Chen Huihui^b?， Guan Boliang^b， Wang Aiguo^b， Yang Jianmao^b

（a. School of Electromechanical Engineering amp; Automation， b. School of Electronic amp; Information Engineering，" Foshan" University，" Foshan" Guangdong 528225，" China）

Abstract：To solve the problem of difficulty for robots to quickly explore unknown environments with narrow entrances， as well as the decrease in exploration efficiency caused by wandering between targets with close exploration benefits， this paper proposed a self-exploration algorithm USAGE （uniformly scanning and attentive guidance explorer） ， which included uniform scanning and attentive guidance strategy. USAGE used the uniform scanning method to detect boundary points， and clustered the boundary points to obtain the points to be explored， and finally determined the optimal exploration target through an attentive guidance strategy. This strategy introduced the steering cost evaluation index into the traditional evaluation function containing information gain and path cost， and constrained the execution of the exploration task according to the robot’s state， and guided the robot to focus on exploration. Through building a simulation environment in the robot operating system for verification， the experimental results show that compared with the exploration algorithm based on rapidly-exploring random tree （RRT） ， USAGE occupies less system memory by more than 11.34%， reduces the exploration time and exploration path level by 26.90% and 31.94% respectively， which improves autonomous exploration efficiency.

Key words：robot; autonomous exploration; boundary point; evaluation function; robot operating system

0 引言

機(jī)器人自主探索是機(jī)器人領(lǐng)域的重要研究方向。具備自主探索能力的機(jī)器人能夠在無(wú)人干預(yù)的情況下主動(dòng)探索未知環(huán)境并繪制地圖，廣泛應(yīng)用在警用反恐^[1]、災(zāi)難救援^[2]、采礦任務(wù)^[3]以及日常生活中^[4]。

機(jī)器人通過(guò)即時(shí)定位與地圖構(gòu)建（simultaneous localization and mapping，SLAM）技術(shù)實(shí)現(xiàn)在運(yùn)動(dòng)的同時(shí)繪制地圖。機(jī)器人在自主探索程序的引導(dǎo)下，在未知環(huán)境中自主規(guī)劃路徑和探索，從而繪制出整個(gè)未知環(huán)境的地圖。自主探索的過(guò)程可以看作是機(jī)器人不斷尋找探索目標(biāo)并朝目標(biāo)行進(jìn)的過(guò)程，因此如何尋找探索目標(biāo)以及選擇怎樣的探索目標(biāo)去探索，進(jìn)而實(shí)現(xiàn)機(jī)器人在陌生環(huán)境中快速、精準(zhǔn)地構(gòu)建完整的全局地圖是自主探索算法的主要優(yōu)化目標(biāo)。

在機(jī)器人自主探索的研究中，Yamauchi^[5]首次提出了基于邊界的自主探索算法，將地圖中空閑空間與未知空間的交界定義為邊界，該算法通過(guò)邊緣檢測(cè)技術(shù)提取地圖邊界并在距離機(jī)器人最近的邊界中得到探索目標(biāo)。文獻(xiàn)[6，7]改進(jìn)了邊界提取模塊，只處理最新獲取的激光掃描數(shù)據(jù)，而不是處理整個(gè)地圖，通過(guò)減少源數(shù)據(jù)的方式降低了處理時(shí)間。Umari等人^[8]提出了應(yīng)用快速探索隨機(jī)樹(shù)（rapidly-exploring random tree， RRT）檢測(cè)邊界點(diǎn)，并設(shè)計(jì)全局RRT邊界點(diǎn)檢測(cè)器和局部RRT邊界點(diǎn)檢測(cè)器共同檢測(cè)地圖中的邊界點(diǎn)。

RRT是一種樹(shù)型數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)和算法，結(jié)構(gòu)簡(jiǎn)單，具有概率完備的特性，但RRT容易在已探索過(guò)的空間重復(fù)探索，造成邊界點(diǎn)檢測(cè)性能降低。針對(duì)RRT檢測(cè)邊界點(diǎn)存在效率低的問(wèn)題，文獻(xiàn)[9，10]改進(jìn)了傳統(tǒng)RRT的生長(zhǎng)速率，利用可變生長(zhǎng)率的全局RRT加速擴(kuò)展，從而提高邊界點(diǎn)檢測(cè)的效率。Sumer等人^[11]提出了利用三種RRT共同檢測(cè)邊界點(diǎn)，在文獻(xiàn)[8]的基礎(chǔ)上優(yōu)化了局部RRT的重置條件，當(dāng)局部RRT檢測(cè)到邊界點(diǎn)或生長(zhǎng)次數(shù)到達(dá)預(yù)先定義次數(shù)時(shí)重置，解決傳統(tǒng)RRT在已探索區(qū)域重復(fù)探索導(dǎo)致生長(zhǎng)被困的問(wèn)題。此外，在最新刪除的邊界點(diǎn)處構(gòu)造臨時(shí)RRT，用于加快檢測(cè)地圖更新區(qū)域附近的邊界點(diǎn)，提高了邊界點(diǎn)檢測(cè)性能。這些基于RRT的邊界點(diǎn)檢測(cè)算法的改進(jìn)在一定程度上提高了算法性能，但是RRT的生長(zhǎng)方式具有隨機(jī)性，難以快速檢測(cè)轉(zhuǎn)角、長(zhǎng)廊等復(fù)雜空間的邊界點(diǎn)，導(dǎo)致機(jī)器人不能及時(shí)發(fā)現(xiàn)其附近的邊界點(diǎn)，在未探索完全的情況下離開(kāi)原地而前往其他地方探索或由于無(wú)探索目標(biāo)而停在原地，造成自主探索的效率降低。

在自主探索的過(guò)程中，選擇優(yōu)質(zhì)的邊界點(diǎn)作為探索目標(biāo)是實(shí)現(xiàn)機(jī)器人高效探索的關(guān)鍵，直接影響探索任務(wù)的執(zhí)行效果。探索目標(biāo)選擇方法包括基于機(jī)器人移動(dòng)方向^[12]、基于距離^[5]和基于評(píng)價(jià)函數(shù)^[13～17]等，傳統(tǒng)的評(píng)價(jià)函數(shù)綜合考慮邊界點(diǎn)的信息增益和路徑代價(jià)并計(jì)算探索收益，探索收益最大的邊界點(diǎn)被定為探索目標(biāo)。傳統(tǒng)的探索目標(biāo)選擇方法存在以下兩個(gè)方面的不足：a）傳統(tǒng)的評(píng)價(jià)函數(shù)只有路徑代價(jià)和信息增益兩個(gè)評(píng)價(jià)指標(biāo)，距離遠(yuǎn)但信息增益大的邊界點(diǎn)可能被選為探索目標(biāo)；b）是直接將探索收益最大的邊界點(diǎn)作為探索目標(biāo)，忽略了探索收益大的程度，當(dāng)存在多個(gè)邊界點(diǎn)且它們之間的探索收益差值較小時(shí)，機(jī)器人可能會(huì)頻繁改變探索目標(biāo)，造成徘徊式探索，降低了探索效率。

針對(duì)機(jī)器人快速探索存在狹窄入口的未知環(huán)境和減少徘徊式探索的需求，本文提出包含均勻掃描和專注引導(dǎo)策略的自主探索算法（uniformly scanning and attentive guidance explorer，USAGE）。USAGE采用均勻采樣的邊界點(diǎn)檢測(cè)算法和專注引導(dǎo)策略分別解決邊界點(diǎn)檢測(cè)問(wèn)題和探索目標(biāo)優(yōu)選問(wèn)題，實(shí)現(xiàn)快速、全面檢測(cè)地圖中的邊界點(diǎn)，以及根據(jù)機(jī)器人的狀態(tài)加入約束條件，優(yōu)選得到探索目標(biāo)，引導(dǎo)機(jī)器人探索未知環(huán)境，減少機(jī)器人徘徊，提高機(jī)器人探索效率和精確率。

1 USAGE算法

1.1 自主探索系統(tǒng)框架

如圖1所示，USAGE自主探索系統(tǒng)由SLAM模塊、USAGE模塊和運(yùn)動(dòng)控制模塊三部分組成。USAGE算法的執(zhí)行流程如圖2所示，USAGE檢測(cè)柵格地圖的邊界點(diǎn)，并聚類得到待探索點(diǎn)，通過(guò)構(gòu)建評(píng)價(jià)函數(shù)和約束條件從若干個(gè)待探索點(diǎn)中優(yōu)選出一個(gè)最優(yōu)探索目標(biāo)，引導(dǎo)機(jī)器人探索。

柵格地圖將真實(shí)地圖分為大小相同的正方形柵格，多個(gè)柵格組成一個(gè)區(qū)域。將柵格地圖表示為柵格集合G={g₁，g₂，…，g_i，…}，第i個(gè)柵格表示為三元組g_i=（x_i，y_i，s_i），其中（x_i，y_i）表示柵格位置坐標(biāo)，s_i表示柵格狀態(tài)屬性，s_i∈{－1，0，1}分別表示柵格位置的地圖為未知、空閑和占用三種狀態(tài)。未探索的柵格為未知狀態(tài)，已探索且有障礙物的柵格為占用狀態(tài)，已探索且無(wú)障礙物的柵格為空閑狀態(tài)。自主探索機(jī)器人冷啟動(dòng)時(shí)，G的大小為人工預(yù)設(shè)估算值，所有柵格的狀態(tài)均為未知。機(jī)器人啟動(dòng)后，激光雷達(dá)開(kāi)始掃描并通過(guò)SLAM算法建圖，被掃描到的柵格的狀態(tài)改為占用或空閑。

如圖1所示，在t時(shí)刻，z_t表示激光雷達(dá)檢測(cè)數(shù)據(jù)，G^（t）表示地圖，" p^（t）^表示機(jī)器人在t時(shí)刻的前進(jìn)目標(biāo)，p_t表示機(jī)器人在t時(shí)刻的實(shí)時(shí)位置，p^（t）∈G^（t）。假設(shè)t時(shí)刻機(jī)器人到達(dá)位置p^（t），SLAM模塊使用Gmapping算法^[18]處理激光雷達(dá)檢測(cè)數(shù)據(jù)z_t構(gòu)建和更新地圖，得到地圖G^（t）。USAGE檢測(cè)G^（t）中的邊界點(diǎn)并確定機(jī)器人的最優(yōu)探索目標(biāo)p^（t）^。運(yùn)動(dòng)控制模塊負(fù)責(zé)規(guī)劃到達(dá)最優(yōu)探索目標(biāo)p^（t）^的安全路徑并引導(dǎo)機(jī)器人探索。

1.2 基于均勻掃描的邊界點(diǎn)檢測(cè)

根據(jù)柵格的狀態(tài)，集合G被劃分為未知柵格集合（記為U）、空閑柵格集合（記為F）和占用柵格集合（記為O）。集合F和O中的柵格表示地圖的已知區(qū)域。邊界點(diǎn)是集合F與U中的柵格鄰接的柵格，且邊界點(diǎn)不屬于O，如圖3所示。

初始階段，地圖中所有柵格的狀態(tài)初始化為未知，機(jī)器人的初始位置視作二維地圖坐標(biāo)系的原點(diǎn)。SLAM模塊在t時(shí)刻根據(jù)激光雷達(dá)掃描數(shù)據(jù)更新地圖，得到G^（t）。USAGE使用雙路并行隔行掃描的方式檢測(cè)地圖中的邊界點(diǎn)。以機(jī)器人的初始位置為起點(diǎn)，兩個(gè)檢測(cè)器分別向上和向下移動(dòng)，隔行掃描柵格后，更新邊界點(diǎn)隊(duì)列V^（t）。

假設(shè)S={g_i，g_i+1，…，g_i+n}為同一行的n+1個(gè)柵格，SG^（t），USAGE使用式（1）篩選出子集S中的邊界點(diǎn)，其中g(shù)_j∈S，g_j+1∈S。

V^（t）←V^（t）+g_j

if g_j∈F∧g_j+1∈UV^（t）←V^（t）+g_j+1 if g_j∈U∧g_j+1∈F（1）

由于識(shí)別邊界點(diǎn)至少需要對(duì)比兩個(gè)柵格，為加快檢測(cè)速度，USAGE在掃描柵格時(shí)，采用隔點(diǎn)對(duì)比檢測(cè)。假設(shè)隔點(diǎn)對(duì)比的間隔步長(zhǎng)為p，待對(duì)比的柵格集{g₀，g₂，…，g_n}減少為{g₀，g_p，g_2p，…，g_ip，…}，數(shù)量從n降低為n/p，本文設(shè)置隔點(diǎn)對(duì)比的間隔步長(zhǎng)p為機(jī)器人模型的外接圓半徑。每次對(duì)比柵格g_ip的狀態(tài)和g_（i+1）p及g_（i+1）p上鄰域柵格的狀態(tài)，當(dāng)兩個(gè)柵格（g_ip和g_（i+1）p或者g_ip和g_（i+1）p上鄰域柵格）的關(guān)系滿足式（2）時(shí)，截取柵格子集S，并使用式（1）檢測(cè)邊界點(diǎn)。

S←g_ip，…，g_（i+1）p，ifg_ip∈F∧g_（i+1）p∈Ug_ip∈U∧g_（i+1）p∈F（2）

1.3 基于專注引導(dǎo)策略的探索目標(biāo)選擇

被探索的區(qū)域內(nèi)環(huán)境越復(fù)雜，邊界點(diǎn)也越多，找到最優(yōu)探索目標(biāo)也就越困難。傳統(tǒng)的探索目標(biāo)選擇方法是通過(guò)含有信息增益和路徑代價(jià)的評(píng)價(jià)函數(shù)計(jì)算邊界點(diǎn)的探索收益，然后選擇探索收益最大的邊界點(diǎn)作為探索目標(biāo)。為解決傳統(tǒng)的探索目標(biāo)優(yōu)選策略難以在探索收益接近的邊界點(diǎn)中擇優(yōu)，導(dǎo)致探索目標(biāo)頻繁改變的問(wèn)題，USAGE采用專注引導(dǎo)策略約束機(jī)器人執(zhí)行探索任務(wù)。專注引導(dǎo)策略首先對(duì)已檢測(cè)到的邊界點(diǎn)進(jìn)行聚類，得到待探索點(diǎn)，然后在含有信息增益和路徑代價(jià)的傳統(tǒng)評(píng)價(jià)函數(shù)基礎(chǔ)上引入機(jī)器人姿態(tài)評(píng)估待探索點(diǎn)的探索收益，最后增加距離和探索收益差值約束進(jìn)行探索目標(biāo)擇優(yōu)。專注引導(dǎo)策略的執(zhí)行過(guò)程包括邊界點(diǎn)聚類、探索收益評(píng)估和探索目標(biāo)選擇三個(gè)步驟。

1.3.1 邊界點(diǎn)聚類

邊界點(diǎn)檢測(cè)模塊的檢測(cè)速度快，檢測(cè)出大量邊界點(diǎn)，且部分邊界點(diǎn)聚集分布在柵格地圖中。為了減少邊界點(diǎn)數(shù)量，提高計(jì)算效率，USAGE通過(guò)mean shift聚類^[19]算法對(duì)已檢測(cè)到的邊界點(diǎn)進(jìn)行均值聚類處理，使用聚類中心點(diǎn)表征該中心點(diǎn)周圍近距離的邊界點(diǎn)，從而達(dá)到減少邊界點(diǎn)數(shù)量，降低計(jì)算開(kāi)銷的目的。

假設(shè)邊界點(diǎn)檢測(cè)模塊共檢測(cè)到n個(gè)二維邊界點(diǎn)x₁，x₂，…，x_n，則邊界點(diǎn)x的mean shift向量的表示形式為

M_h（x）=1k∑x_i∈S_h（x_i－x）（3）

其中：S_h是以點(diǎn)x為圓點(diǎn)，半徑為h的圓形區(qū)域，k為區(qū)域S_h內(nèi)數(shù)據(jù)點(diǎn)的數(shù)量。上式為聚類算法的一次迭代過(guò)程，求解S_h內(nèi)的k個(gè)向量相對(duì)于向量x的偏移均值，向量M_h（x）的方向指向數(shù)據(jù)點(diǎn)分布密集的區(qū)域，每次迭代后，數(shù)據(jù)點(diǎn)x會(huì)往向量M_h（x）方向移動(dòng)，移動(dòng)距離為‖M_h（x）‖，并把區(qū)域S_h內(nèi)的其他點(diǎn)標(biāo)記為同一類。

USAGE通過(guò)mean shift算法對(duì)大量邊界點(diǎn)進(jìn)行均值聚類，得到多個(gè)類的中心點(diǎn)。聚類后，簇的中心點(diǎn)視為待探索點(diǎn)，探索目標(biāo)會(huì)在待探索點(diǎn)中擇優(yōu)得到。如果待探索點(diǎn)的數(shù)量只有1個(gè)，則直接將該待探索點(diǎn)作為探索目標(biāo)，引導(dǎo)機(jī)器人進(jìn)行探索；如果存在多個(gè)待探索點(diǎn)，則通過(guò)探索收益評(píng)估和探索目標(biāo)約束進(jìn)行擇優(yōu)得到探索目標(biāo)。

1.3.2 探索收益評(píng)估

探索收益評(píng)估指對(duì)每個(gè)待探索點(diǎn)使用評(píng)價(jià)函數(shù)計(jì)算它的探索收益。評(píng)價(jià)函數(shù)包括信息增益、路徑代價(jià)和轉(zhuǎn)向代價(jià)三個(gè)評(píng)價(jià)指標(biāo)。

a）信息增益表示為I（p， r），指待探索點(diǎn)p周圍未知區(qū)域面積的大小，即以p為圓心、用戶定義的信息增益半徑r的圓內(nèi)未知柵格的數(shù)量。

b） 路徑代價(jià)表示為N（p），指機(jī)器人從當(dāng)前位置到待探索點(diǎn)p的歐氏距離。為了消除評(píng)價(jià)函數(shù)中不同評(píng)估指標(biāo)之間的量綱影響，對(duì)N（p）進(jìn)行歸一化處理得到歸一化路徑代價(jià)（p），如式（4）所示。

（p）=N（p）N_max（4）

其中：N_max是N（p）的最大值，即最遠(yuǎn)待探索點(diǎn)的歐氏距離。

c） 轉(zhuǎn)向代價(jià)表示為H（p），指機(jī)器人從當(dāng)前行進(jìn)方向轉(zhuǎn)向待探索點(diǎn)p時(shí)，需要調(diào)整的轉(zhuǎn)向角度。加入轉(zhuǎn)向角度鼓勵(lì)機(jī)器人朝著與當(dāng)前行進(jìn)方向偏差較小的目標(biāo)進(jìn)行探索。為了消除評(píng)價(jià)函數(shù)中不同評(píng)估指標(biāo)之間的量綱影響，對(duì)H（p）進(jìn)行歸一化處理得到歸一化轉(zhuǎn)向代價(jià)（p），如式（5）所示。

H（p）=cos^－1a·b|a||b|（p）=H（p）180（5）

其中：a是機(jī)器人當(dāng)前姿態(tài)的單位向量；b是機(jī)器人當(dāng)前位置指向p的單位向量。

待探索點(diǎn)p的探索收益評(píng)價(jià)函數(shù)R（p）如式（6）所示。

R（p）=λI（p， r）+e^{（－α（p）－β（p））}（6）

其中：α和β分別是路徑代價(jià)和轉(zhuǎn)向代價(jià)的權(quán)重系數(shù)。

為鼓勵(lì)機(jī)器人優(yōu)先對(duì)近距離的目標(biāo)進(jìn)行探索，引入權(quán)重系數(shù)λ。λ的計(jì)算如式（7）（8）所示。

λ=A（N（p）） if N（p）≤D1if N（p）gt;D（7）

A（N（p））=2×DN（p）（8）

其中：D是用戶定義的距離閾值。

1.3.3 探索目標(biāo)選擇

為降低機(jī)器人在探索收益接近的待探索點(diǎn)之間頻繁執(zhí)行探索任務(wù)的可能性，USAGE根據(jù)機(jī)器人的狀態(tài)對(duì)探索目標(biāo)選擇方式進(jìn)行約束，分為如下三個(gè)步驟：

a）計(jì)算所有待探索點(diǎn)p的探索收益R（p），得到探索收益最大的待探索點(diǎn)p^*。

b）獲取機(jī)器人當(dāng)前位置p^（t）_r和機(jī)器人正在探索的目標(biāo)位置p^（t）^，并計(jì)算p^（t）_r與p^（t）^的距離l^（t）_r。當(dāng)l^（t）_r≤D時(shí)，將探索收益最大的待探索點(diǎn)p^*作為新的探索目標(biāo)p^（t+1）^；當(dāng)l^（t）_rgt;D，則執(zhí)行步驟c）。

c）定義探索收益差值閾值R_r，通過(guò)R_r對(duì)比p^*與p^（t）^的探索收益差值，作用是判斷p^*和p^（t）^探索收益的偏差程度，評(píng)估探索目標(biāo)改變的必要性，實(shí)現(xiàn)機(jī)器人專注探索，解決探索收益接近的探索目標(biāo)導(dǎo)致機(jī)器人徘徊探索的問(wèn)題。新的探索目標(biāo)p^（t+1）^選擇方式如式（9）所示。

p^（t+1）^=p^* if （R（p^*）－R（p^（t）^））gt; R_rp^（t）^ other（9）

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證USAGE探索算法的有效性，本文利用仿真器Gazebo搭建室內(nèi)場(chǎng)景仿真環(huán)境1和2進(jìn)行實(shí)驗(yàn)，仿真環(huán)境的面積分別為220 m²和400 m²，如圖4所示。實(shí)驗(yàn)所用的機(jī)器人的物理尺寸為0.28×0.31×0.15（m³），機(jī)器人運(yùn)動(dòng)底盤采用兩輪差速驅(qū)動(dòng)，不允許倒車，機(jī)器人搭載的激光雷達(dá)的最遠(yuǎn)掃描距離為10 m，掃描范圍為-180°～180°。

本文設(shè)置了28組共280次實(shí)驗(yàn)，包括10組自我測(cè)評(píng)實(shí)驗(yàn)和18組基準(zhǔn)算法對(duì)比實(shí)驗(yàn)。自我測(cè)評(píng)實(shí)驗(yàn)是根據(jù)USAGE算法中探索目標(biāo)優(yōu)選中評(píng)價(jià)函數(shù)的不同權(quán)重配置（路徑代價(jià)權(quán)重α和轉(zhuǎn)向代價(jià)權(quán)重β）在兩個(gè)仿真環(huán)境中進(jìn)行實(shí)驗(yàn)?；鶞?zhǔn)算法對(duì)比實(shí)驗(yàn)是在相同的實(shí)驗(yàn)條件下對(duì)比RRT探索算法^[8]和文獻(xiàn)[11]探索算法。為避免實(shí)驗(yàn)數(shù)據(jù)的偶然性，每組實(shí)驗(yàn)進(jìn)行10次重復(fù)實(shí)驗(yàn)并記錄相關(guān)數(shù)據(jù)，機(jī)器人的初始位置設(shè)置在環(huán)境中間綠色方框中心點(diǎn)處。相關(guān)實(shí)驗(yàn)參數(shù)設(shè)置如表1所示。

2.2 自我測(cè)評(píng)實(shí)驗(yàn)結(jié)果

為探究USAGE中的評(píng)價(jià)函數(shù)中不同權(quán)重配置（路徑代價(jià)權(quán)重α和轉(zhuǎn)向代價(jià)權(quán)重β）對(duì)探索效率的影響，本文根據(jù)不同的權(quán)重配置設(shè)置了5組探索方案，設(shè)置機(jī)器人的最大線速度為0.5 m/s，分別在仿真環(huán)境1和2中進(jìn)行實(shí)驗(yàn)，記錄機(jī)器人的平均探索耗時(shí)和平均探索距離，實(shí)驗(yàn)數(shù)據(jù)如圖5所示。

實(shí)驗(yàn)數(shù)據(jù)表明：在仿真環(huán)境1中，探索方案（α=2， β=1）的探索效率最高，與只考慮路徑代價(jià)的探索方案（α=1， β=0）相比，平均探索耗時(shí)和距離分別減小了7.28%和7.37%；與只考慮轉(zhuǎn)向代價(jià)的探索方案（α=0， β=1）相比，平均探索耗時(shí)和距離分別減小了9.58%和12.34%。這表明不同的路徑代價(jià)和轉(zhuǎn)向代價(jià)權(quán)重比例對(duì)探索效率有一定的影響，只考慮路徑代價(jià)或轉(zhuǎn)向代價(jià)的探索方案的探索效率低于其他探索方案，綜合考慮路徑代價(jià)和轉(zhuǎn)向代價(jià)可以提高機(jī)器人自主探索的效率。在仿真環(huán)境2中，探索方案（α=2， β=1）的效率最高，與探索效率最低的探索方案（α=1， β=2）相比，平均探索耗時(shí)和距離分別減小了17.64%和9.53%，這表明在大場(chǎng)景地圖中，路徑代價(jià)是影響機(jī)器人自主探索效率的關(guān)鍵因素。

2.3 基準(zhǔn)算法對(duì)比實(shí)驗(yàn)結(jié)果

在基準(zhǔn)算法對(duì)比實(shí)驗(yàn)中，設(shè)置機(jī)器人的最大線速度為0.5 m/s，本文采用探索方案（α=2， β=1）的USAGE算法與RRT探索算法^[8]和文獻(xiàn)[11]進(jìn)行對(duì)比。

本文使用top命令查看系統(tǒng)內(nèi)存占用率，對(duì)比不同探索算法中的邊界點(diǎn)檢測(cè)模塊的物理內(nèi)存使用量（resident set size，RSS），實(shí)驗(yàn)數(shù)據(jù)如表2所示。

表2表明：USAGE與RRT和文獻(xiàn)[11]相比，在仿真環(huán)境1中，RSS分別減小了11.34%和43.09%，在仿真環(huán)境2中，RSS分別減小了24.81%和46.41%。USAGE探索兩種環(huán)境都占用較小的系統(tǒng)內(nèi)存，且不會(huì)大幅度變化，而RRT和文獻(xiàn)[11]會(huì)隨著探索的進(jìn)行占用更大的內(nèi)存，驗(yàn)證了USAGE的邊界點(diǎn)檢測(cè)模塊的有效性。

為驗(yàn)證USAGE的專注引導(dǎo)策略的有效性，本文根據(jù)不同的探索目標(biāo)優(yōu)選策略設(shè)置對(duì)比實(shí)驗(yàn)，對(duì)比算法為融合USAGE的邊界點(diǎn)檢測(cè)模塊與RRT的探索目標(biāo)優(yōu)選策略的算法（簡(jiǎn)稱USAGE-RRT），在相同的實(shí)驗(yàn)條件下重復(fù)10次實(shí)驗(yàn)，對(duì)比平均探索耗時(shí)和距離，實(shí)驗(yàn)數(shù)據(jù)如表3所示。

表3表明：在仿真環(huán)境1中，USAGE與USAGE-RRT相比，其在平均探索耗時(shí)和距離方面分別減小了8.81%和9.43%。在仿真環(huán)境2中，USAGE與USAGE-RRT相比，其在平均探索耗時(shí)和距離方面分別減小了9.33%和7.35%。采用專注引導(dǎo)策略的探索方案可以提高探索效率，驗(yàn)證了USAGE的專注引導(dǎo)策略的有效性。

為驗(yàn)證USAGE可以實(shí)現(xiàn)機(jī)器人減小在相同路徑中重復(fù)探索的可能性，本文在相同的實(shí)驗(yàn)條件下對(duì)比機(jī)器人探索仿真環(huán)境1和2的運(yùn)動(dòng)軌跡，從圖6和7的實(shí)驗(yàn)結(jié)果可以看出USAGE的運(yùn)動(dòng)軌跡更加平滑，且行駛的路徑長(zhǎng)度更短，這表明USAGE能夠減小機(jī)器人在相同路徑探索的可能性，提高了探索效率。

為進(jìn)一步驗(yàn)證USAGE的有效性，本文設(shè)置三種不同的機(jī)器人最大線速度（0.3 m/s、0.5 m/s和0.7 m/s）對(duì)比實(shí)驗(yàn)，從探索耗時(shí)和探索距離兩個(gè)方面評(píng)估探索算法的優(yōu)劣，實(shí)驗(yàn)結(jié)果如表4所示。表4表明：在仿真環(huán)境1中，USAGE（0.5 m/s）的探索效率最高，相對(duì)RRT（0.5 m/s）在平均探索耗時(shí)和距離方面分別減小了26.25%和26.82%；相對(duì)文獻(xiàn)[11]（0.5 m/s）在平均探索耗時(shí)和距離方面分別減小了15.14%和15.09%。在仿真環(huán)境2中，USAGE（0.7 m/s）的探索效率最高，相對(duì)RRT（0.7 m/s）在平均探索耗時(shí)和距離方面分別減小了26.90%和31.94%；相對(duì)文獻(xiàn)[11]（0.7 m/s）在平均探索耗時(shí)和距離方面分別減小了19.18%和13.98%。

綜上所述，本文提出的USAGE自主探索算法在一定程度上加快了邊界點(diǎn)檢測(cè)速度和減小機(jī)器人探索重復(fù)路徑的可能性，使機(jī)器人探索未知環(huán)境花費(fèi)更少的時(shí)間和行駛更短的距離，提高了機(jī)器人自主探索的效率。此外，USAGE實(shí)現(xiàn)自主探索占用較小的系統(tǒng)內(nèi)存，在嵌入式設(shè)備部署方面具有一定的優(yōu)勢(shì)。

3 結(jié)束語(yǔ)

本文提出了一種高效率的自主探索算法USAGE。與基于快速探索隨機(jī)樹(shù)的探索算法相比，USAGE占用系統(tǒng)內(nèi)存更小，且占用的內(nèi)存不會(huì)隨著探索的進(jìn)行而大幅度增大，使USAGE更適用于資源受限的探索機(jī)器人。此外，USAGE在不同的機(jī)器人探索速度探索不同復(fù)雜程度的環(huán)境都體現(xiàn)出較好的探索性能，實(shí)現(xiàn)自主探索花費(fèi)更少的時(shí)間和行駛更短的距離，提升了自主探索效率。

本文算法采用單個(gè)機(jī)器人進(jìn)行自主探索建圖，未來(lái)將研究多機(jī)器人協(xié)作完成自主探索，提供多機(jī)器人協(xié)作探索構(gòu)建室內(nèi)環(huán)境地圖的解決方案。

參考文獻(xiàn)：

[1]陳曉東. 警用與反恐機(jī)器人的現(xiàn)狀與趨勢(shì) [J]. 機(jī)器人技術(shù)與應(yīng)用， 2015 （6）： 31-33. （Chen Xiaodong. Present situation and trend of police and anti-terrorist robot [J]. Robot Technique and Application， 2015 （6）： 31-33.）

[2]Delmerico J， Mueggler E， Nitsch J， et al.Active autonomous aerial exploration for ground robot path planning [J]. IEEE Robotics and Automation Letters， 2017， 2 （2）： 664-671.

[3]朱華， 由韶澤. 新型煤礦救援機(jī)器人研發(fā)與實(shí)驗(yàn) [J]. 煤炭學(xué)報(bào)， 2020， 45 （6）： 2170-2181. （Zhu Hua， You Shaoze， Research and experience of a new type of coal mine rescue robot [J]. Journal of China Coal Society， 2020， 45 （6）： 2170-2181.）

[4]趙雅婷， 趙韓， 梁昌勇， 等. 養(yǎng)老服務(wù)機(jī)器人現(xiàn)狀及其發(fā)展建議 [J]. 機(jī)械工程學(xué)報(bào)， 2019，55 （23）： 13-24. （Zhao Yating， Zhao Han， Liang Changyong， et al.Current situation and development suggestions of old-age service robot [J]. Journal of Mechanical Engineering， 2019， 55 （23）： 13-24.）

[5]Yamauchi B. A frontier-based approach for autonomous exploration [C]// Proc of IEEE International Symposium on Computational Intelligence in Robotics and Automation. Piscataway，NJ： IEEE Press， 1997： 146-151.

[6]Keidar M， Kaminka G A. Robot exploration with fast frontier detection： theory and experiments [C]// Proc of the 11th International Conference on Autonomous Agents and Multiagent Systems. New York： ACM Press， 2012： 113-120.

[7]Senarathne P， Wang Danwei. Incremental algorithms for safe and reachable frontier detection for robot exploration [J]. Robotics and Autonomous Systems， 2015， 72： 189-206.

[8]Umari H， Mukhopadhyay S. Autonomous robotic exploration based on multiple rapidly-exploring randomized trees [C]// Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway，NJ：IEEE Press， 2017： 1396-1402.

[9]楊儻月， 汪秀忠， 陳自豪， 等. 基于改進(jìn)RRT算法的機(jī)器人自主環(huán)境探測(cè) [J]. 信息技術(shù)， 2019， 43 （12）： 20-23， 28. （Yang Tangyue， Wang Xiuzhong， Chen Zihao， et al.Autonomous robotic exploration based on improved rapidly-exploring random tree [J]. Information Technology， 2019， 43 （12）： 20-23， 28.）

[10]齊立哲， 何東東， 陳騫， 等. 基于拓?fù)涞貓D的移動(dòng)機(jī)器人室內(nèi)環(huán)境高效自主探索算法 [J]. 機(jī)器人， 2023， 45 （3）： 313-320. （Qi Lizhe， He Dongdong， Chen Qian， et al.An efcient autonomous exploration algorithm of indoor environment for mobile robots using topological map [J]. Robot， 2023， 45 （3）： 313-320.）

[11]Sumer E，Temeltas H. RRT based frontier point detection for 2D autonomous exploration [C]// Proc of International Conference on Robotics and Automation Engineering. Piscataway，NJ：IEEE Press， 2022： 305-311.

[12]Mei Yongguo， Lu Y H， Lee C S G， et al.Energy-efficient mobile robot exploration [C]// Proc of IEEE International Conference on Robotics and Automation. Piscataway，NJ：IEEE Press， 2006： 505-511.

[13]Wu Chengyan， Lin H Y. Autonomous mobile robot exploration in unknown indoor environments based on rapidly-exploring random tree [C]// Proc of IEEE International Conference on Industrial Technology. Piscataway，NJ：IEEE Press， 2019： 1345-1350.

[14]Fang Baofu， Ding Jianfeng， Wang Zaijun. Autonomous robotic exploration based on frontier point optimization and multistep path planning [J]. IEEE Access， 2019， 7： 46104-46113.

[15]孟祥天. 陌生環(huán)境下機(jī)器人自主建圖的研究與實(shí)現(xiàn) [D]. 成都： 電子科技大學(xué)， 2020. （Meng Xiangtian. Research and implementation of robot autonomous mapping in unfamiliar environment [D]. Chengdu： University of Electronic Science and Technology of China， 2020.）

[16]周建偉. 基于多傳感器的移動(dòng)機(jī)器人自主探索建圖系統(tǒng)的研究與實(shí)現(xiàn) [D]. 南京： 南京郵電大學(xué)， 2020. （Zhou Jianwei. Research and implementation of autonomous exploration and mapping system for mobile robot based on multi-sensor [D]. Nanjing： Nanjing University of Posts and Telecommunications， 2020.）

[17]張淑珍， 馬玉祥， 侯致遠(yuǎn)， 等. 融合波前邊緣檢測(cè)與快速搜索隨機(jī)樹(shù)的自主探索方法 [J]. 中國(guó)慣性技術(shù)學(xué)報(bào)， 2023， 31 （9）： 925-931. （Zhang Shuzhen， Ma Yuxiang， Hou Zhiyuan， et al.Autono-mous exploration method for fusing wavefront frontier detection with rapidly-exploring random trees[J]. Journal of Chinese Inertial Technology， 2023， 31 （9）： 925-931.）

[18]Grisetti G， Stachniss C， Burgard W. Improved techniques for grid mapping with Rao-Blackwellized particle filters [J]. IEEE Trans on Robotics， 2007， 23 （1）： 34-46.

[19]Comaniciu D， Meer P. Mean shift： a robust approach toward feature space analysis [J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2002， 24 （5）： 603-619.