一種基于高效邊界探索的機(jī)器人自主建圖方法

劉瑞雪，曾 碧，汪明慧，盧智亮

（廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006）

隨著機(jī)器人技術(shù)的快速發(fā)展和社會(huì)需求的變革，自主移動(dòng)機(jī)器人越來(lái)越受到工程界和學(xué)術(shù)界的關(guān)注[1]。為使移動(dòng)機(jī)器人能夠在非結(jié)構(gòu)化、非確定的環(huán)境中自主幫助人們完成日常生活任務(wù)，首要實(shí)現(xiàn)的關(guān)鍵技術(shù)是當(dāng)機(jī)器人處于未知環(huán)境時(shí)，可自主探索移動(dòng)路徑，并同時(shí)利用基于激光傳感器的同步定位與建圖(Simultaneous Localization and Mapping，SLAM)[2-3]技術(shù)建立外界環(huán)境在機(jī)器人內(nèi)部表示的地圖，用于后續(xù)導(dǎo)航[4-5]。但是傳統(tǒng)機(jī)器人建圖的方式是人工手動(dòng)或使用鍵盤、游戲桿控制機(jī)器人移動(dòng)，在面對(duì)大而復(fù)雜的室內(nèi)環(huán)境時(shí)會(huì)浪費(fèi)時(shí)間、人力、物力[6]。因此使機(jī)器人脫離人為控制，實(shí)現(xiàn)自主探索建圖路徑具有重要意義[7-8]。

機(jī)器人自主探索建圖是一種基于SLAM算法和路徑規(guī)劃算法，自主尋找有建圖路徑的目標(biāo)點(diǎn)以探索環(huán)境未知區(qū)域，實(shí)現(xiàn)環(huán)境完整構(gòu)圖的方法，涉及機(jī)器人定位、構(gòu)圖與路徑規(guī)劃等多方面技術(shù)。

在自主探索領(lǐng)域，Yamauchi[9]提出Frontierbased邊界探索方法是目前大多數(shù)探測(cè)算法的基礎(chǔ)。Yamauchi定義地圖上空閑區(qū)域和未知區(qū)域之間為地圖邊界，并不斷將機(jī)器人移動(dòng)探索的目標(biāo)設(shè)定為距離機(jī)器人最近的邊界，該方法可以使機(jī)器人完整遍歷未知的室內(nèi)環(huán)境。但該方法沒(méi)有考慮路徑最優(yōu)，因此在未知環(huán)境面積比較大的時(shí)候，機(jī)器人探索會(huì)耗費(fèi)大量時(shí)間。為了縮短機(jī)器人探索路徑，Dirk Holz等[10]提出通過(guò)Dijkstra算法更新和存儲(chǔ)柵格地圖中機(jī)器人與所有邊界柵格的路徑長(zhǎng)度，縮短了自主建圖的探索路徑。但是該方法僅僅考慮了機(jī)器人與邊界的路徑信息，忽略了地圖自身攜帶的有效信息，所以建圖時(shí)間優(yōu)化效果一般。為了可以融合地圖信息來(lái)提高建圖效率，文獻(xiàn)[11-12]提出了基于地圖和路徑估計(jì)的信息增益的解決方案，該方案將建圖路徑和地圖信息增益最大化作為決策依據(jù)，降低了探索建圖的執(zhí)行時(shí)間。但是計(jì)算信息增益需要大量?jī)?nèi)存和計(jì)算量?？紤]到計(jì)算量的問(wèn)題，高環(huán)宇等[13]采用一種動(dòng)態(tài)建立待探索邊界的探索樹(shù)以降低地圖探索重復(fù)率的方式，有效縮短了探索建圖時(shí)間，但建圖過(guò)程中探索樹(shù)的建立不斷增加了程序的內(nèi)存量。類似地，李秀智等[14]將柵格地圖和拓?fù)涞貓D融合，通過(guò)標(biāo)記拓?fù)涔?jié)點(diǎn)的狀態(tài)來(lái)減少機(jī)器人對(duì)環(huán)境的重復(fù)探索。該方法雖然降低了邊界探索算法的重復(fù)率，但是對(duì)候選邊界的評(píng)估有所欠缺，容易產(chǎn)生無(wú)效不可達(dá)邊界。

綜上可見(jiàn)，國(guó)內(nèi)外學(xué)者對(duì)自主探索建圖算法已有一定的優(yōu)化效果。但仍存在兩個(gè)主要問(wèn)題：第一，自主建圖路徑探索點(diǎn)選取條件欠缺。探索區(qū)選取算法未考慮探索點(diǎn)的可達(dá)性和防機(jī)器人碰撞的安全性。第二，探索建圖時(shí)間長(zhǎng)，當(dāng)出現(xiàn)機(jī)器人不能導(dǎo)航到探索目標(biāo)點(diǎn)時(shí)，缺乏有效的實(shí)時(shí)解決方案，往往會(huì)增加建圖時(shí)間。

因此本文提出一種基于曲線擬合和滑動(dòng)窗口規(guī)劃的自主邊界探索建圖方法CS-frontier。以Frontierbased算法為基礎(chǔ)，該方法在確定目標(biāo)探索邊界之前，對(duì)地圖候選邊界曲線擬合建模，使機(jī)器人自主建圖時(shí)可不斷優(yōu)選可容納機(jī)器人訪問(wèn)的安全的建圖目標(biāo)探索點(diǎn)，并以最短路徑導(dǎo)航到每一個(gè)可達(dá)目標(biāo)探索點(diǎn)，同時(shí)借助SLAM技術(shù)完成構(gòu)圖；同時(shí)當(dāng)出現(xiàn)機(jī)器人導(dǎo)航不可達(dá)路徑的目標(biāo)探索點(diǎn)時(shí)，使用基于滑動(dòng)窗口邊界鄰域規(guī)劃方法及時(shí)生成最優(yōu)可達(dá)目標(biāo)替代點(diǎn)來(lái)引導(dǎo)導(dǎo)航和完成最終建圖。該方法減少了機(jī)器人自主建圖的時(shí)間，增強(qiáng)了機(jī)器人自主建圖的魯棒性和安全性。

1 背景知識(shí)

1.1 Frontier-based邊界探索算法

Frontier-based邊界探索算法[9]思想為：根據(jù)已構(gòu)建的地圖環(huán)境信息，檢測(cè)已知地圖與未知地圖之間的邊界，選取與機(jī)器人距離最近的邊界作為探索目標(biāo)點(diǎn)；機(jī)器人探索完該目標(biāo)點(diǎn)后，再根據(jù)更新的地圖確定下一個(gè)探索目標(biāo)點(diǎn)，以此不斷迭代，直到完成對(duì)所有未知環(huán)境的探索。

1.1.1 地圖表示

Frontier-based算法采用的地圖表示是證據(jù)網(wǎng)格(Evidence Grids)[15]，如圖1所示。證據(jù)網(wǎng)格通過(guò)傳感器的距離數(shù)據(jù)得到環(huán)境的占用狀態(tài)，提供詳細(xì)的環(huán)境特征數(shù)據(jù)，是機(jī)器人導(dǎo)航和路徑規(guī)劃的重要基礎(chǔ)。證據(jù)網(wǎng)格中單元格有3種區(qū)域：空閑區(qū)域，表示單元格處沒(méi)有障礙物；占用區(qū)域，表示單元格處有障礙物；未知區(qū)域，表示單元格還未被機(jī)器人感知到，屬于未知的區(qū)域。分別由白色、黑色、灰色表示。

圖1 證據(jù)網(wǎng)格Fig.1 Evidence grids

1.1.2 邊界探索

Frontier-based算法定義：在證據(jù)網(wǎng)格中，如圖1所示，有 f標(biāo)識(shí)的單元格為邊界單元格，相鄰的邊界單元格組成一條邊界。在檢測(cè)到邊界后，將邊界長(zhǎng)度大于閾值的邊界添加到可訪問(wèn)的邊界列表中，機(jī)器人嘗試以最短路徑導(dǎo)航到最近邊界的質(zhì)心進(jìn)行下一步探索。具體探索流程如圖2所示。

1.2 最小二乘法曲線擬合原理

曲線擬合是根據(jù)兩個(gè)具有函數(shù)關(guān)系變量的多組實(shí)際值來(lái)確定兩個(gè)變量函數(shù)曲線的方法。最小二乘法曲線擬合是使得變量實(shí)際值與擬合曲線的因變量的殘差平方和最小為優(yōu)化目標(biāo)的方法。以下為利用最小二乘法擬合多項(xiàng)式曲線的數(shù)學(xué)原理。

設(shè)兩個(gè)變量的一組數(shù)據(jù)x=(x1,x2,···,xn) ，y=(y1,y2,···,yn)，兩個(gè)變量的擬合曲線多項(xiàng)式 p(x)為

其中a,b,c為多項(xiàng)式未知常量系數(shù)，為了求得a,b,c的值，推算過(guò)程如式(2)所示。

圖2 Frontier-based算法流程圖Fig.2 Flow chart of the Frontier-based algorithm

運(yùn)用最小二乘法曲線擬合原理[16]，計(jì)算 x,y所有數(shù)據(jù)到擬合曲線的偏差平方和L。

根據(jù) W 得到常量系數(shù)a,b,c的值，因而得到根據(jù)最小二乘法求得的多項(xiàng)式曲線函數(shù)p(x)。

2 Frontier-based算法改進(jìn)

2.1 基于邊界曲線擬合的邊界篩選

Frontier-based算法探索建圖時(shí)將長(zhǎng)度大于設(shè)定閾值的邊界添加入候選邊界組，從中選取距離機(jī)器人最近的邊界作為下一個(gè)探索目標(biāo)區(qū)。然而，候選邊界組中往往存在邊界長(zhǎng)度已達(dá)到閾值，但是形狀曲折細(xì)長(zhǎng)、周圍空間狹窄的邊界，如圖3所示。當(dāng)這類邊界被選作探索區(qū)時(shí)，機(jī)器人會(huì)進(jìn)入狹窄區(qū)域發(fā)生碰撞，進(jìn)而影響構(gòu)圖質(zhì)量?；蛘唛L(zhǎng)時(shí)間停留原地，無(wú)路徑到達(dá)目標(biāo)探索點(diǎn)，增加了自主建圖時(shí)間。

為了提高目標(biāo)探索點(diǎn)的有效性和可達(dá)性，本文算法以Frontier-based算法為基礎(chǔ)，以與證據(jù)網(wǎng)格表示一致的柵格地圖[17]為地圖模型，將曲線擬合建模方法應(yīng)用到候選邊界組的篩選方法中，去除不安全邊界，篩選安全邊界。

2.1.1 局部邊界坐標(biāo)系與全局坐標(biāo)系的轉(zhuǎn)換

圖3 不安全邊界示意圖Fig.3 Schematic of the insecure boundary

在機(jī)器人已建地圖中，候選邊界組中的邊界由多組基于地圖全局坐標(biāo)系的邊界點(diǎn)組成，不包含邊界的方向信息，所以對(duì)邊界進(jìn)行曲線建模時(shí)需要針對(duì)候選邊界組中的邊界創(chuàng)建局部邊界坐標(biāo)系。如圖4所示，創(chuàng)建局部邊界坐標(biāo)系步驟如下：(1) 坐標(biāo)系原點(diǎn)：邊界質(zhì)心 O。(2) 坐標(biāo)系Y 軸：連接邊界兩端邊界點(diǎn)P，Q為一條直線，找到距離該直線最遠(yuǎn)的邊界點(diǎn) N作為頂點(diǎn)，連接質(zhì)心與頂點(diǎn)的直線為Y 軸，正方向?yàn)橘|(zhì)心到頂點(diǎn)的方向。(3) 坐標(biāo)系 X 軸：坐標(biāo)系Y軸正向順時(shí)針旋轉(zhuǎn)90°方向?yàn)?X 軸正向。

圖4 局部邊界坐標(biāo)系Fig.4 Local boundary coordinate system

構(gòu)建局部邊界坐標(biāo)系后，將邊界數(shù)值從地圖全局坐標(biāo)系轉(zhuǎn)換到局部邊界坐標(biāo)系下。兩坐標(biāo)系的位置關(guān)系如圖5所示，O-XgYg表示地圖全局坐標(biāo)系，O′是邊界質(zhì)心，O′-XlYl表示局部邊界坐標(biāo)系， N是邊界頂點(diǎn)， S為一條邊界中的邊界點(diǎn)。

圖5 兩坐標(biāo)系轉(zhuǎn)換示意圖Fig.5 Schematic of two coordinate systems transformation

最后，由式(8)可以將邊界候選組中的所有邊界的邊界點(diǎn)從全局坐標(biāo)系轉(zhuǎn)換到局部邊界坐標(biāo)系下，得到局部邊界坐標(biāo)系下的邊界候選組。

2.1.2 邊界曲線建模

機(jī)器人構(gòu)建地圖的邊界形狀特征多為一元二次曲線圖像特征，因此本文算法設(shè)邊界f擬合曲線多項(xiàng)式pc(x)為

2.1.3 安全邊界及目標(biāo)探索點(diǎn)的選取

根據(jù)2.1.2中的方法對(duì)候選邊界中所有邊界進(jìn)行邊界曲線建模，獲得所有邊界的曲線擬合函數(shù)。下一步計(jì)算邊界的空間寬度，因?yàn)檫吔琰c(diǎn)分散，不能僅僅通過(guò)邊界兩邊的頂點(diǎn)推算。所以本文算法利用邊界擬合函數(shù)計(jì)算邊界的空間寬度。如圖6所示，曲線A是圖中邊界的擬合函數(shù)pc(x)在坐標(biāo)系O′-XlYl中的圖像, D為邊界的空間寬度。當(dāng)D大于機(jī)器人底盤寬度時(shí)，將該邊界添加入安全邊界列表，確定邊界空間可以容納機(jī)器人；反之，則添加入不安全邊界列表，確定該邊界空間狹窄，機(jī)器人訪問(wèn)該邊界時(shí)會(huì)發(fā)生碰撞。安全邊界和目標(biāo)探索點(diǎn)篩選實(shí)現(xiàn)方案如下。

圖6 安全邊界篩選示意圖Fig.6 Schematic of the security boundary screening

根據(jù)求根公式計(jì)算式(10)的解，即曲線A的零點(diǎn)R1，R2的橫坐標(biāo)分別為 x1， x2。則邊界的空間距離D=|x1- x2|。比較D與機(jī)器人底盤寬度2r。

根據(jù)以上方法篩選候選邊界組中所有邊界，在安全邊界列表選取與機(jī)器人距離最近的邊界為探索區(qū)，并將該邊界的質(zhì)心作為下一個(gè)目標(biāo)探索點(diǎn)。

2.2 不可達(dá)目標(biāo)探索點(diǎn)規(guī)劃

Frontier-based算法在獲取到目標(biāo)探索點(diǎn)后，機(jī)器人嘗試使用路徑規(guī)劃器規(guī)劃一條最短無(wú)障礙路徑。若有路徑，機(jī)器人順利導(dǎo)航至目標(biāo)點(diǎn)探索邊界，反之，由于室內(nèi)環(huán)境地圖復(fù)雜，激光雷達(dá)為360°發(fā)散式掃描，機(jī)器人的目標(biāo)探索邊界出現(xiàn)如圖7和圖8所示的情況：安全邊界 f彎曲方向指向地圖未知區(qū)域，其目標(biāo)探索點(diǎn)即質(zhì)心處于機(jī)器人未感知的區(qū)域。這導(dǎo)致機(jī)器人無(wú)法規(guī)劃出一條到達(dá)質(zhì)心位置的路徑，只能將該目標(biāo)邊界添加入不可訪問(wèn)邊界列表，并原地等待一個(gè)路徑規(guī)劃周期(約2 min)，再重新確定新的目標(biāo)探索點(diǎn)，建圖效率低。

為了優(yōu)化上述問(wèn)題所導(dǎo)致自主探索建圖時(shí)間長(zhǎng)的問(wèn)題，本文算法將基于滑動(dòng)窗口的邊界鄰域規(guī)劃方法引入Frontier-based算法。

圖7 不可達(dá)目標(biāo)探索點(diǎn)Fig.7 Unreachable target exploration point

圖8 不可達(dá)目標(biāo)探索點(diǎn)鄰域規(guī)劃Fig.8 Neighborhood planning for unreachable target exploration points

基于滑動(dòng)窗口的邊界鄰域規(guī)劃的思想是：對(duì)于不可達(dá)邊界如圖8中邊界f，采用90°圓形扇面滑動(dòng)窗口，每次逆時(shí)針旋轉(zhuǎn)90°，旋轉(zhuǎn)4次，掃描質(zhì)心C 的圓形鄰域內(nèi)，尋找可以容納機(jī)器人的可達(dá)新目標(biāo)探索點(diǎn)。從而無(wú)需機(jī)器人原地等待2 min，并避免機(jī)器人放棄對(duì)此類邊界的探索。

如圖8所示，目標(biāo)邊界 f的不可達(dá)探索點(diǎn)C 決策出新目標(biāo)探索點(diǎn)C′。具體算法偽代碼為

2.3 CS-frontier算法

本文提出的自主邊界探索建圖方法 CS-frontier，其自主建圖方法流程圖如圖9所示。

圖9 CS-frontier自主建圖算法Fig.9 CS-frontier autonomous mapping algorithm

算法步驟如下：

步驟1：收集傳感器數(shù)據(jù)，使用基于SLAM方法的Gmapping(Grid Mapping)算法[19]更新構(gòu)建環(huán)境地圖。

步驟2：使用計(jì)算機(jī)視覺(jué)方法檢測(cè)地圖邊界。如果存在邊界，則添加入邊界候選組；反之，執(zhí)行步驟8。

步驟3：利用邊界曲線擬合建模方法篩選候選邊界組中邊界，將符合邊界添加入安全邊界列表。

步驟4：選擇安全邊界列表中與機(jī)器人距離最近的邊界的質(zhì)心作為下一步構(gòu)圖的目標(biāo)探索點(diǎn)。

步驟5：如果目標(biāo)探索點(diǎn)在地圖的空閑區(qū)域，則執(zhí)行步驟7；否則執(zhí)行步驟6。

步驟6：針對(duì)不可達(dá)目標(biāo)探索點(diǎn)，使用基于滑動(dòng)窗口的邊界鄰域規(guī)劃方法推算新的替代點(diǎn)。

步驟7：機(jī)器人規(guī)劃最短無(wú)障礙路徑導(dǎo)航至目標(biāo)探索點(diǎn)，然后執(zhí)行步驟1。

步驟8：自主建圖完成。

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

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

本文的實(shí)驗(yàn)分別在兩個(gè)不同室內(nèi)場(chǎng)景進(jìn)行。簡(jiǎn)單實(shí)驗(yàn)場(chǎng)景如圖10所示：面積為8 m×9.6 m，障礙物主要是桌子、紙箱、墻壁；復(fù)雜實(shí)驗(yàn)場(chǎng)景如圖11所示：面積為9.5 m×8.0 m，障礙物主要是辦公桌、凳子和辦公雜物。實(shí)驗(yàn)平臺(tái)如圖12所示，包含一臺(tái)搭載Rplidar A2 360°激光測(cè)距雷達(dá)的Turtlebot 2機(jī)器人和一臺(tái)搭載英特爾i7-8750H CPU的筆記本電腦。

圖10 簡(jiǎn)單實(shí)驗(yàn)環(huán)境Fig.10 Simple experimental environment

圖11 復(fù)雜實(shí)驗(yàn)環(huán)境Fig.11 Complex experimental environment

圖12 Turtlebot 2平臺(tái)Fig.12 Turtlebot 2 platform

3.2 評(píng)價(jià)指標(biāo)

本實(shí)驗(yàn)評(píng)價(jià)指標(biāo)主要為探索次數(shù)：機(jī)器人自主建圖過(guò)程中探索目標(biāo)點(diǎn)總數(shù)；路徑長(zhǎng)度：機(jī)器人自主構(gòu)建完整地圖所移動(dòng)的路徑總長(zhǎng)度；自主建圖時(shí)間：機(jī)器人從初始建圖到完整建圖的時(shí)間；地圖覆蓋率：機(jī)器人實(shí)時(shí)已建地圖面積與環(huán)境完整地圖面積的比例；地圖完整度：自主建圖完成后,所建地圖面積與環(huán)境完整地圖面積的比例。

3.3 實(shí)驗(yàn)數(shù)據(jù)

本文算法的實(shí)驗(yàn)基于機(jī)器人操作系統(tǒng)(Robot Operating System，ROS)框架，使用Gmapping算法構(gòu)建實(shí)時(shí)柵格地圖，使用ROS平臺(tái)move_base路徑規(guī)劃器規(guī)劃?rùn)C(jī)器人導(dǎo)航路徑。相關(guān)實(shí)驗(yàn)設(shè)置參數(shù)如表1所示。

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

本文在圖10、圖11所示的室內(nèi)場(chǎng)景對(duì)所提出的算法進(jìn)行驗(yàn)證。首先機(jī)器人在起點(diǎn)處開(kāi)啟Gmapping建圖算法，不斷以最短路徑方式導(dǎo)航至自主探索建圖算法決策的目標(biāo)探索點(diǎn)，最終遍歷整個(gè)環(huán)境。為驗(yàn)證本文算法的有效性，本文進(jìn)行兩項(xiàng)算法對(duì)比實(shí)驗(yàn)。

表1 實(shí)驗(yàn)參數(shù)設(shè)置Table 1 Experimental parameters setting

3.4.1 對(duì)比實(shí)驗(yàn)一

CS-frontier算法與Frontier-based算法對(duì)比。

(1) 簡(jiǎn)單環(huán)境實(shí)驗(yàn)對(duì)比。兩種探索建圖算法在圖10環(huán)境中進(jìn)行的實(shí)驗(yàn)過(guò)程性能對(duì)比如圖13、圖14和表2所示。圖13中圓點(diǎn)表示自主建圖過(guò)程中機(jī)器人的目標(biāo)探索點(diǎn)，箭頭線段表示機(jī)器人探索建圖路徑和方向。

圖13 簡(jiǎn)單環(huán)境自主探索建圖過(guò)程和完成圖Fig.13 Mapping process independent exploration and completion map in simple environment

圖14 Frontier-based探索中不安全邊界Fig.14 Insecure borders in Frontier-based exploration

Frontier-based算法探索次數(shù)比CS-frontier算法多5次。通過(guò)實(shí)驗(yàn)觀察，圖13(a)中Frontier-based算法探索過(guò)程，如圖14所示，目標(biāo)探索點(diǎn)F3,F7位置處于地圖的未知區(qū)域內(nèi)，機(jī)器人無(wú)路徑到達(dá)，原地旋轉(zhuǎn)規(guī)劃路徑2 min放棄探索；目標(biāo)探索點(diǎn)F8,F9,F14所屬邊界長(zhǎng)度達(dá)到閾值，但是邊界空間距離小，為不安全邊界，導(dǎo)航過(guò)程中機(jī)器人發(fā)生碰撞，且因空間狹窄到達(dá)不了目標(biāo)位置，等待2 min再?zèng)Q策下一個(gè)目標(biāo)點(diǎn)。

表2 各算法性能對(duì)比Table 2 Performance comparison of various algorithms

CS-frontier算法在探索過(guò)程中利用邊界曲線擬合建模方法篩選掉了不安全邊界，并采用滑動(dòng)窗口邊界鄰域規(guī)劃方法對(duì)處于未知區(qū)域的探索點(diǎn)進(jìn)行重規(guī)劃，相對(duì)于Frontier-base算法大大縮短了建圖時(shí)間，自主建圖時(shí)間僅用9.21 min。

(2) 復(fù)雜環(huán)境實(shí)驗(yàn)對(duì)比。兩種探索建圖算法在圖11環(huán)境中的實(shí)驗(yàn)過(guò)程、效果和性能對(duì)比如圖15和表2所示，F(xiàn)rontier-based算法17次探索中，探索點(diǎn) F9處于地圖未知區(qū)域，被放棄探索。還有8個(gè)是無(wú)路徑不安全邊界：F1,F2,F3,F4,F6,F7,F10,F15。其中如圖15(a)中地圖的左上部分，機(jī)器人在 F14處使用路徑規(guī)劃器尋找 F15的路徑時(shí)，由于機(jī)器人不斷地旋轉(zhuǎn)恢復(fù)嘗試尋找路徑，導(dǎo)致地圖角度誤差加大，引起建圖算法不穩(wěn)定性，造成已構(gòu)建的全局地圖與局部地圖進(jìn)行匹配時(shí)發(fā)生偏轉(zhuǎn)，構(gòu)圖發(fā)生錯(cuò)誤，使得已建地圖與實(shí)際場(chǎng)景不符，最終地圖完整度僅90.5%。

CS-frontier相較于Frontier-based而言，探索次數(shù)少且目標(biāo)探索點(diǎn)均安全有效，雖然探索路徑長(zhǎng)度相差不大，但是Frontier-based因?yàn)閷?duì)不安全邊界的多次路徑恢復(fù)嘗試，導(dǎo)致探索時(shí)間增加，也增加了構(gòu)建地圖的不準(zhǔn)確性。CS-frontier算法在探索過(guò)程中，減少機(jī)器人對(duì)不安全探索點(diǎn)的探索和機(jī)器人碰撞、多次旋轉(zhuǎn)等引起定位誤差和地圖誤差的產(chǎn)生，從而增強(qiáng)了自主建圖算法的整體穩(wěn)定性。如圖15(b)所示，CSfrontier算法探索路徑平滑，構(gòu)建的地圖誤差小，更加準(zhǔn)確，地圖完整度更高。

圖15 復(fù)雜環(huán)境自主探索建圖過(guò)程和完成圖Fig.15 Mapping process independent exploration and completion map in complex environments

因此，實(shí)驗(yàn)結(jié)果表明，在簡(jiǎn)單環(huán)境和復(fù)雜環(huán)境的不同驗(yàn)證中，本文CS-frontier算法優(yōu)化了Frontierbased算法中的不安全邊界探索和目標(biāo)探索點(diǎn)無(wú)路徑問(wèn)題，本文算法更適應(yīng)相對(duì)復(fù)雜的生活、辦公環(huán)境，自主建圖效率高，算法魯棒性強(qiáng)，整體性能更好、更高效。

3.4.2 對(duì)比實(shí)驗(yàn)二

CS-frontier算法與以下兩種自主建圖算法在如圖10環(huán)境中進(jìn)行實(shí)驗(yàn)對(duì)比：牛耕式全覆蓋遍歷算法[20]，該算法自主建圖按照左下右上的路徑方式遍歷整個(gè)環(huán)境；基于滾動(dòng)窗口的機(jī)器人自主構(gòu)圖算法[6]，使用滾動(dòng)窗口的方式讓機(jī)器人滾動(dòng)探測(cè)地圖。對(duì)比結(jié)果如表2、圖16所示。

圖16 地圖覆蓋率對(duì)比圖Fig.16 Comparison of the map coverage

從探索次數(shù)看，CS-frontier算法探索次數(shù)最少，牛耕遍歷算法最多，從路徑長(zhǎng)度和建圖時(shí)間來(lái)看，CS-frontier算法的總路徑最短，自主建圖時(shí)間僅用9.21 min，就達(dá)到較高的地圖完整度。從地圖覆蓋率看，如圖16所示，隨著探索次數(shù)增加，牛耕遍歷法上升速度最慢，滑動(dòng)窗口算法因?yàn)榇翱诨瑒?dòng)地圖重復(fù)多，覆蓋率增加較慢，F(xiàn)rontier-based算法在無(wú)效探索點(diǎn)處影響了覆蓋率的增加，CS-frontier算法上升速度最快，地圖重復(fù)率最低。

實(shí)驗(yàn)表明本文提出的CS-frontier算法相比傳統(tǒng)的自主探索建圖算法，可選擇更少的探索點(diǎn)，以更高的探索效率和更平滑的路徑完成自主探索建圖。

4 結(jié)論

為了更好地實(shí)現(xiàn)移動(dòng)機(jī)器人自主構(gòu)建未知環(huán)境的柵格地圖模型，提高機(jī)器人自主性和智能化水平，本文提出 CS-frontier自主邊界探索建圖方法。該方法針對(duì)在未知環(huán)境下，機(jī)器人如何自主探索未知區(qū)域進(jìn)行構(gòu)圖，并克服邊界狹窄探索區(qū)域影響構(gòu)圖完整性的問(wèn)題，一方面，根據(jù)已構(gòu)地圖邊界的曲線特征，采用邊界曲線建模方法，選取安全邊界，再選擇與機(jī)器人最短距離的安全邊界探索點(diǎn)作為下一個(gè)探索區(qū)；另一方面，通過(guò)基于滑動(dòng)窗口的邊界鄰域規(guī)劃算法確定處于未知區(qū)域目標(biāo)點(diǎn)的探索，提高了自主建圖的通用性。通過(guò)在實(shí)際室內(nèi)復(fù)雜場(chǎng)地多次重復(fù)對(duì)比實(shí)驗(yàn)表明，本文方法無(wú)論是與目前經(jīng)典的Frontierbased邊界探索算法，還是傳統(tǒng)牛耕全覆蓋遍歷算法及基于滾動(dòng)窗口的機(jī)器人自主構(gòu)圖算法相比，都有更高的探索效率和通用性。

然而在機(jī)器人建圖過(guò)程中，里程計(jì)、電機(jī)旋轉(zhuǎn)角度等累計(jì)誤差都會(huì)引起建圖算法中局部地圖與全局地圖匹配的誤差，影響機(jī)器人構(gòu)建地圖的準(zhǔn)確性。所以在研究提高機(jī)器人探索未知環(huán)境構(gòu)圖的自主性的同時(shí)，考慮建圖算法的穩(wěn)定性和精確性是下一步研究工作的內(nèi)容。