馬健，俞揚(yáng)

(南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，江蘇南京 210023)

由于自主移動(dòng)機(jī)器人在日常生活服務(wù)[1]、危險(xiǎn)環(huán)境作業(yè)[2]、太空探索[3]等領(lǐng)域有廣泛的應(yīng)用，對(duì)機(jī)器人的自主行走和環(huán)境感知的研究吸引了越來越多的研究者關(guān)注。路標(biāo)的發(fā)現(xiàn)及其位置的精確估計(jì)自主移動(dòng)機(jī)器人在環(huán)境中的定位起到關(guān)鍵作用。當(dāng)路標(biāo)的位置信息已知時(shí)，通過對(duì)視線范圍內(nèi)路標(biāo)的鑒別和距離的估計(jì)，機(jī)器人即可計(jì)算出自己的所在位置。因此如何有效地在未知環(huán)境中探索和估計(jì)路標(biāo)的位置是自主移動(dòng)機(jī)器人研究的重要問題。

在完全未知環(huán)境中自主探索和估計(jì)路標(biāo)的方法主要基于同時(shí)定位與地圖構(gòu)建(simultaneous localization and mapping，SLAM)技術(shù)。SLAM最先由Self和Cheeseman[4]提出，它迭代的通過路標(biāo)信息修正自身位置，同時(shí)通過自身位置的估計(jì)來修正路標(biāo)信息，使得在機(jī)器人的移動(dòng)過程中能夠逐漸提高其自身位置和路標(biāo)的估計(jì)精度。由于其重要的理論與應(yīng)用價(jià)值，同時(shí)定位與地圖構(gòu)建(SLAM)被認(rèn)為是自主移動(dòng)機(jī)器人實(shí)現(xiàn)真正自主運(yùn)動(dòng)的關(guān)鍵，是智能移動(dòng)機(jī)器人進(jìn)入人類日常生活的必要基礎(chǔ)，也成為近年來機(jī)器人和人工智能領(lǐng)域中一個(gè)非常活躍的研究熱點(diǎn)[5-7]。

在以往的研究中，移動(dòng)機(jī)器人在未知環(huán)境中游走，并在移動(dòng)過程中使用SLAM技術(shù)對(duì)路標(biāo)進(jìn)行估計(jì)[8]。常用的游走方式包括隨機(jī)游走或啟發(fā)式的探索策略，目標(biāo)是最大限度地、盡快地引導(dǎo)機(jī)器人向未探測區(qū)域運(yùn)動(dòng)，盡量避免在已探測區(qū)域內(nèi)運(yùn)動(dòng)，從而盡快減少未探測的區(qū)域。然而，基于SLAM的路標(biāo)估計(jì)方法需要機(jī)器人重復(fù)探測已探測過的環(huán)境來提高對(duì)自身位置和路標(biāo)位置的估計(jì)精度[9]，過快移向未探測區(qū)域?qū)⑹沟靡烟綔y路標(biāo)的精度過低，導(dǎo)致較大的定位誤差。

本文提出一種以全局定位誤差最小化為指導(dǎo)的探索策略，進(jìn)一步提高路標(biāo)位置的估計(jì)精度。本文中還將全局定位信息引入SLAM的位置估計(jì)中，有效地校正當(dāng)移動(dòng)變化過大時(shí)(例如速度發(fā)生變化或轉(zhuǎn)彎時(shí))SLAM估計(jì)的誤差。在模擬環(huán)境中的初步實(shí)驗(yàn)驗(yàn)證了本文方法的有效性。

1 路徑規(guī)劃相關(guān)工作

1.1 同時(shí)定位與地圖構(gòu)建相關(guān)算法

同時(shí)定位與地圖構(gòu)建的一個(gè)重要支撐技術(shù)是概率統(tǒng)計(jì)學(xué)。以貝葉斯濾波器為基本原理，研究人員先后提出了擴(kuò)展卡爾曼濾波的SLAM算法(EKFSLAM)[7]期望值最大化的SLAM算法(EMEKF)[8]粒子濾波和擴(kuò)展卡爾曼濾波的SLAM算法(FastSLAM)[9]等。EKF-SLAM 算法是用高斯分布表示后驗(yàn)概率的貝葉斯濾波[10]。該算法作了3個(gè)近似。首先，運(yùn)動(dòng)模型近似為線性的，在環(huán)境為靜態(tài)的條件下，地圖特征狀態(tài)不變，僅有機(jī)器人狀態(tài)發(fā)生變化。根據(jù)擴(kuò)展卡爾曼濾波狀態(tài)方程線性的要求，機(jī)器人的非線性運(yùn)動(dòng)模型近似為一個(gè)帶有高斯噪聲的線性函數(shù);其次，觀測模型近似為線性的。最后，初始的不確定量近似為高斯分布。EKF-SLAM方法已被廣泛地研究和應(yīng)用。Dissanayake等[11]通過在路邊架設(shè)雷達(dá)點(diǎn)路標(biāo)并人工駕駛室外移動(dòng)汽車，驗(yàn)證了卡爾曼濾波在同時(shí)定位與地圖構(gòu)建方面的有效性。Castellanos等[12]利用擴(kuò)展卡爾曼濾波研究室內(nèi)環(huán)境的同時(shí)定位與地圖構(gòu)建。悉尼大學(xué)的Williams等[13]將它應(yīng)用于水下環(huán)境。

EM-SLAM算法是一種由最大似然估計(jì)法發(fā)展而來的統(tǒng)計(jì)算法，由Thrun等[14]提出。應(yīng)用EM算法進(jìn)行地圖構(gòu)建的主要觀點(diǎn)是當(dāng)機(jī)器人路徑已知時(shí)，確定地圖是相對(duì)簡單的;同樣，對(duì)于一張給定的地圖，確定機(jī)器人位姿的概率估計(jì)也相對(duì)簡單。求解時(shí)交替執(zhí)行2個(gè)步驟，分別稱為期望步驟(expectation step，E步驟)和最大值化步驟(maximization step，M步驟).在E步驟中，根據(jù)當(dāng)前最大可能性地圖估計(jì)各個(gè)時(shí)間點(diǎn)機(jī)器人位置的概率估計(jì)，在M步驟中，根據(jù)在E步驟所計(jì)算得到的位置估計(jì)最大可能性地圖。通過不斷重復(fù)，機(jī)器人位置估計(jì)和地圖估計(jì)的精確性不斷提高。

針對(duì)EKF-SLAM方法在單峰高斯假設(shè)下難以解決數(shù)據(jù)對(duì)應(yīng)問題、無法構(gòu)建環(huán)行環(huán)境地圖的缺陷，以及EM-SLAM方法需要多次遍歷數(shù)據(jù)集、難以遞增地構(gòu)建環(huán)境地圖的缺陷，Hahnel等[15]提出了基于粒子濾波和卡爾曼濾波的混合SLAM方法，也稱為FastSLAM。FastSLAM算法的基本思想是通過樣本集合表示概率密度。每一個(gè)樣本是關(guān)于狀態(tài)真值的一個(gè)離散猜測，一組樣本描述出概率分布的代表性特性。這種基于樣本的表示方法使得粒子濾波可以表示各種概率密度，適用于在線的、非線性、非高斯分布的實(shí)時(shí)估計(jì)。FastSLAM面向路標(biāo)特征地圖，將機(jī)器人位姿估計(jì)和地圖特征估計(jì)相分離，用粒子樣本描述機(jī)器人路徑的概率分布，每一個(gè)粒子對(duì)應(yīng)于一個(gè)可能的機(jī)器人路徑，每個(gè)粒子中維護(hù)著一張地圖，以該粒子所對(duì)應(yīng)的機(jī)器人路徑為條件，利用擴(kuò)展卡爾曼濾波估計(jì)地圖中各個(gè)特征的高斯分布。通過將粒子濾波和擴(kuò)展卡爾曼濾波的有機(jī)結(jié)合，F(xiàn)astSLAM極大地減少了粒子需求數(shù)[10]。

1.2 室內(nèi)未知環(huán)境的路徑規(guī)劃

室內(nèi)未知環(huán)境的路徑規(guī)劃算法可分為3類:1)隨機(jī)遍歷策略，如迂回往復(fù)式、內(nèi)外螺旋式[18];2)沿邊學(xué)習(xí)加局部路徑規(guī)劃方法，主要應(yīng)用算法為細(xì)胞分解法，應(yīng)用的局部路徑規(guī)劃方法有人工勢場法、完全應(yīng)激式算法、模糊邏輯算法[17];3)漫步式探測路徑規(guī)劃[19]，機(jī)器人根據(jù)自身傳感器探測周圍環(huán)境信息，并在可視區(qū)域根據(jù)一定的算法生成局部運(yùn)動(dòng)的規(guī)劃目標(biāo)，將機(jī)器人的路徑規(guī)劃歸結(jié)為逐步尋找下一步最佳視點(diǎn)的遞歸。采用此種策略的完全遍歷規(guī)劃方法有強(qiáng)化學(xué)習(xí)方法、基于隨機(jī)樹結(jié)構(gòu)的方法、生物激勵(lì)的神經(jīng)網(wǎng)絡(luò)方法、探測路徑規(guī)劃[13]。

隨機(jī)遍歷策略有迂回往復(fù)式、內(nèi)外螺旋式、隨機(jī)轉(zhuǎn)向式、時(shí)間轉(zhuǎn)向式、模板模型法、隨機(jī)局部遍歷的方法。這些方法的共同點(diǎn)是:1)不采用現(xiàn)在通用的效益函數(shù);2)規(guī)劃算法簡單，方便低成本軟硬件設(shè)計(jì)實(shí)現(xiàn)?？偟膩碚f，在不采用效益評(píng)價(jià)函數(shù)，如工作時(shí)間、能量損耗、重復(fù)覆蓋率等的前提下，可以達(dá)到長時(shí)間上的大范圍覆蓋未知環(huán)境。簡單的隨機(jī)遍歷策略廣泛應(yīng)用于清潔機(jī)器人，如科沃斯地寶系列機(jī)器人。迂回往復(fù)法也經(jīng)常作為其他算法的底層策略，或算法判斷后所采取的方法[16]。

沿邊學(xué)習(xí)加局部路徑規(guī)劃方法中機(jī)器人在沿邊學(xué)習(xí)的過程中可以獲取室內(nèi)未知環(huán)境的全局信息進(jìn)行建模，而后采用全局視角和局部路徑規(guī)劃相結(jié)合的方法，遍歷整個(gè)室內(nèi)的未知環(huán)境。其思想是機(jī)器人首先沿著未知室內(nèi)環(huán)境邊沿行走一周，然后選擇某個(gè)位置向四周觀察，確定合適的探測區(qū)域前進(jìn)，并以此循環(huán)下去，典型的算法有MTCP[17]算法。進(jìn)行局部路徑規(guī)劃時(shí)，機(jī)器人可以建立虛擬子目標(biāo)，主要應(yīng)用算法為細(xì)胞分解法，該方法在機(jī)器人進(jìn)行沿邊學(xué)習(xí)之后，算法將環(huán)境分解為多個(gè)細(xì)胞，每個(gè)細(xì)胞設(shè)置一個(gè)基點(diǎn)，機(jī)器人走遍了基點(diǎn)則完成了遍歷。人工勢場法、完全應(yīng)激式算法、模糊邏輯算法以及啟發(fā)式函數(shù)也可以作為路徑評(píng)價(jià)的判斷標(biāo)準(zhǔn)。

雖然沿邊學(xué)習(xí)方法可以獲得部分環(huán)境信息，但是由于一方面此方法需要對(duì)環(huán)境進(jìn)行建模，另一方面?zhèn)鞲衅餍畔⒉煌耆虼嗽摲椒ㄓ芯窒扌浴６绞铰窂揭?guī)劃算法則可以避免這些缺點(diǎn)，其方法有強(qiáng)化學(xué)習(xí)法、基于隨機(jī)樹結(jié)構(gòu)的方法、基于生物激勵(lì)的神經(jīng)網(wǎng)絡(luò)方法和探測路徑規(guī)劃方法。

對(duì)于探測路徑規(guī)劃方法，其規(guī)劃序列為首先選擇一組下一步觀測視點(diǎn)的候選位置，然后通過效用函數(shù)評(píng)估這些候選位置，選擇使效用函數(shù)最大化的位置作為下一個(gè)觀測視點(diǎn)。探測路徑規(guī)劃主要包括2個(gè)方面:候選視點(diǎn)的生成和評(píng)價(jià)。在機(jī)器人進(jìn)行探測時(shí)，首先應(yīng)當(dāng)考慮的是信息收益和路徑成本。

候選點(diǎn)的生成算法一般為前沿(Frontier)理論、隨機(jī)生成候選點(diǎn)理論以及這2種方法的混合算法。前沿理論基本思想是將下一步探測視點(diǎn)放置在已探測環(huán)境與未探測環(huán)境的交界線上，從而期望獲得最大化信息收益。隨機(jī)生成的方法是在傳感器掃描區(qū)域的圓或者圓環(huán)上以隨機(jī)的方式生成一定數(shù)量的候選視點(diǎn)。對(duì)候選視點(diǎn)的評(píng)價(jià)中，信息收益是一項(xiàng)重要指標(biāo)，一般有2種方法進(jìn)行衡量:一種是直接衡量傳感器探測空間的未知區(qū)域的幾何信息法;另一種是采用熵的概率信息法[16]。此外，路徑成本也是效益評(píng)價(jià)函數(shù)里的常見參數(shù)，如何衡量定位不確定性，成為了目前研究的熱點(diǎn)。

2 本文方法

2.1 基于路標(biāo)的全局位置估計(jì)探索策略

本文提出的室內(nèi)未知環(huán)境機(jī)器人路徑規(guī)劃方法屬于漫步式探測路徑規(guī)劃，其目的是最小化全局定位誤差。機(jī)器人從室內(nèi)某一初始位置出發(fā)后先隨機(jī)游走直至發(fā)現(xiàn)一定數(shù)量的路標(biāo)，而后選擇下一步的探測路徑。本文的思想是首先選擇一組下一步觀測視點(diǎn)的候選位置，然后通過效益評(píng)價(jià)函數(shù)評(píng)估這些候選位置，選擇使效益評(píng)價(jià)函數(shù)最大化的位置作為下一個(gè)觀測位置。由于在整個(gè)可達(dá)空間中搜索下一個(gè)最佳探測規(guī)劃位置意味著巨大的計(jì)算量，為減少計(jì)算量，一般對(duì)候選探測位置作一定的約束以提高計(jì)算效率。因此，探測規(guī)劃研究的討論主要集中在2個(gè)方面，一個(gè)是候選位置的生成，另一個(gè)是候選位置的評(píng)估。

本文方法將以當(dāng)前自主移動(dòng)機(jī)器人所在位置為圓心、r為半徑的圓上隨機(jī)生成的N個(gè)可達(dá)空間內(nèi)的位置作為候選視點(diǎn)，而后分別預(yù)估自主移動(dòng)機(jī)器人在這N個(gè)候選位置對(duì)應(yīng)的N條路徑上可能觀測到的新路標(biāo)的個(gè)數(shù)及位置、新路標(biāo)的個(gè)數(shù)與該條路徑預(yù)估新探測的環(huán)境面積的比例、已經(jīng)探測的路標(biāo)個(gè)數(shù)、已經(jīng)探測的環(huán)境面積的比例。新探測的路標(biāo)的位置則用隨機(jī)的方法進(jìn)行估計(jì)。候選位置的評(píng)價(jià)采用效用函數(shù)對(duì)候選視點(diǎn)進(jìn)行量化評(píng)估，該方法考慮了全局定位誤差最小化，并對(duì)較大轉(zhuǎn)彎角度進(jìn)行懲罰，以使機(jī)器人能夠在降低全局定位誤差的同時(shí)較為平滑地游走。該效用函數(shù)為

式(1)的目標(biāo)函數(shù)表示全局定位誤差，其中i表示需要估計(jì)位置的路標(biāo)，m表示環(huán)境中需要估計(jì)位置的路標(biāo)的個(gè)數(shù)，α表示機(jī)器人一步轉(zhuǎn)彎的角度，est_again_location(i)表示結(jié)合全局位置估計(jì)和卡爾曼濾波的SLAM算法得到的第i個(gè)路標(biāo)的估計(jì)坐標(biāo)，est_location(i)表示上次得到的第i個(gè)路標(biāo)的估計(jì)坐標(biāo)，這2個(gè)函數(shù)的具體估計(jì)方法見3.2小節(jié)。punish(α)表示轉(zhuǎn)彎角度的懲罰項(xiàng)，本文簡單地用機(jī)器人轉(zhuǎn)彎時(shí)的角度的弧度制大小表示。

機(jī)器人一步優(yōu)化路徑規(guī)劃的算法流程如下:

1)以預(yù)測的機(jī)器人所在位置為圓心、R為半徑的圓上隨機(jī)找N個(gè)在面板范圍內(nèi)的點(diǎn);

2)分別預(yù)估機(jī)器人在這N條路徑上會(huì)觀測到的新路標(biāo)的個(gè)數(shù)及位置;

3)通過模擬機(jī)器人在這N條路徑上游走，分別計(jì)算每條路徑對(duì)應(yīng)的效用函數(shù)值;

4)選取效用函數(shù)值最小路徑為下一步探測路徑。

2.2 全局位置估計(jì)和卡爾曼濾波的SLAM算法

在傳統(tǒng)的SLAM問題的相關(guān)的算法中，SLAM是一個(gè)濾波問題，是根據(jù)系統(tǒng)的初始狀態(tài)和從0到t時(shí)刻的觀測信息與控制信息估計(jì)系統(tǒng)的當(dāng)前狀態(tài)?？柭鼮V波算法就屬于這種思想，卡爾曼濾波器已經(jīng)被廣泛認(rèn)為是實(shí)現(xiàn)SLAM的一種基本方法。然而，在實(shí)際情況中，當(dāng)移動(dòng)機(jī)器人移動(dòng)變化過大時(shí)(例如速度發(fā)生變化或轉(zhuǎn)彎時(shí))，使用傳統(tǒng)的SLAM相關(guān)算法，機(jī)器人的位置和真實(shí)的位置的誤差會(huì)比較大，機(jī)器人轉(zhuǎn)彎越急誤差可能越大。基于此本文提出結(jié)合全局位置估計(jì)和卡爾曼濾波的SLAM算法，由于全局定位信息更少地依賴歷史運(yùn)動(dòng)軌跡，與卡爾曼濾波等傳統(tǒng)結(jié)合使用不僅可以減小機(jī)器人游走時(shí)的估計(jì)誤差，而且可以有效降低機(jī)器人在轉(zhuǎn)彎時(shí)估計(jì)的誤差。

不失一般性，本文假設(shè)機(jī)器人所在的真實(shí)物理位置為 (xi，yi)，i∈ {1，2，...，n}，選取的已觀測到的路標(biāo)的真實(shí)位置為(xti，yti)，路標(biāo)的估計(jì)位置為(xsi，ysi)，假設(shè)需要估計(jì)的機(jī)器人的位置為(xs，ys)，優(yōu)化的目標(biāo)函數(shù)為

記機(jī)器人與第i個(gè)路標(biāo)的真實(shí)距離為

這樣，本文有n個(gè)這樣的式子，分別將第i個(gè)式子減去第n個(gè)式子得到n－1個(gè)如下的等式:

這是一個(gè)最小二乘問題，記A為n－1個(gè)式(3)的右邊部分，即n－1個(gè)[2(xsi－xsn)2(ysi－ysn)]，則A為(n－1)×2的矩陣。記x為所求的[xsys]T，B為n－1個(gè)式(4)的左邊部分，即B為(n－1)×1的矩陣。需要估計(jì)的機(jī)器人的位置的最小二乘的最后結(jié)果 x'= [xs'，ys']T=(ATA)－1ATB 。在機(jī)器人每一步行走過程中，本文用上述方法得出的估計(jì)位置和卡爾曼濾波得出的估計(jì)位置的平均值作為機(jī)器人最終的估計(jì)位置。

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

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

本文對(duì)2種規(guī)劃方法做了對(duì)比仿真，實(shí)驗(yàn)隨機(jī)選擇候選點(diǎn)運(yùn)動(dòng)和一步最優(yōu)規(guī)劃算法。機(jī)器人運(yùn)動(dòng)模型為本實(shí)驗(yàn)室全方位移動(dòng)機(jī)器人模型，假設(shè)其可以感知半徑10 m范圍內(nèi)的路標(biāo).環(huán)境大小為80 m×80 m的正方形，其中隨機(jī)分布了30個(gè)路標(biāo)，游走前機(jī)器人位于坐標(biāo)(30 m，20 m)處，與x軸正方向成45o夾角，2種游走策略下自主移動(dòng)機(jī)器人運(yùn)行步數(shù)都是1 000步。對(duì)于本文的方法，在環(huán)境中均勻選取100個(gè)點(diǎn)，以估計(jì)全局誤差。

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

圖1給出了不同探索策略的機(jī)器人從相同位置和角度出發(fā)在相等的運(yùn)行步數(shù)下生成的運(yùn)動(dòng)路徑。

圖1 運(yùn)動(dòng)軌跡與探索的路標(biāo)結(jié)果對(duì)比Fig.1 The comparison of trajectory and road signs

其中，略大的點(diǎn)表示環(huán)境中的路標(biāo)，虛線表示自主移動(dòng)機(jī)器人真實(shí)的游走路線，實(shí)線表示自主移動(dòng)機(jī)器人分別使用隨機(jī)游走策略和本文的方法的游走路線，略小的點(diǎn)表示估計(jì)的路標(biāo)的位置，圓圈表示算法預(yù)計(jì)的路標(biāo)的估計(jì)誤差。實(shí)驗(yàn)結(jié)果表明:1)使用本文的游走策略探測到的路標(biāo)更多，本文的游走策略未探測的路標(biāo)有6個(gè)，而使用隨機(jī)游走后未探測到的路標(biāo)有13個(gè);2)在觀測到的路標(biāo)上，使用隨機(jī)游走策略的最大誤差更大;3)使用本文策略后自主移動(dòng)機(jī)器人游走的路線更平滑，在機(jī)器人位置的估計(jì)問題上，本文采用新算法后位置估計(jì)的誤差有較為顯著的減小。

3.2.1 全局路標(biāo)定位誤差比較

圖2給出了自主移動(dòng)機(jī)器人2種游走策略下的全局位置估計(jì)誤差的比較結(jié)果。其中橫坐標(biāo)表示的是機(jī)器人游走的步數(shù)，縱坐標(biāo)表示2種游走策略對(duì)應(yīng)的在每一步的全局位置估計(jì)誤差。由于機(jī)器人游走開始時(shí)會(huì)隨機(jī)游走一段至發(fā)現(xiàn)一定數(shù)量的路標(biāo)，所以橫坐標(biāo)不是從0開始，而是從發(fā)現(xiàn)一定數(shù)量的路標(biāo)的時(shí)刻180開始的。機(jī)器人隨機(jī)選擇候選點(diǎn)的全局誤差的均值和方差分別是1.821 2和1.062 4，而機(jī)器人采用基于路標(biāo)的全局位置估計(jì)探索策略后的全局誤差的均值和方差分別是 1.532 0和0.943 2。

圖2 2種游走策略下的全局位置估計(jì)誤差比較結(jié)果Fig.2 The global position estimation error under two kinds of migration strategy

3.2.2 自主移動(dòng)機(jī)器人自身定位誤差比較

圖3給出了卡爾曼濾波的SLAM算法和結(jié)合全局位置估計(jì)、卡爾曼濾波的SLAM算法在機(jī)器人使用本文的游走策略時(shí)每一步的機(jī)器人定位誤差的比較結(jié)果。其中橫坐標(biāo)表示的是機(jī)器人游走的步數(shù)，縱坐標(biāo)表示每種算法在每一步對(duì)機(jī)器人自身位置估計(jì)誤差的平均值。從圖中可以看出在機(jī)器人游走初期，機(jī)器人探測到的路標(biāo)不多，基于卡爾曼濾波的SLAM算法產(chǎn)生的誤差和本文的方法的位置估計(jì)誤差差別不大。同時(shí)，全局位置估計(jì)的誤差變化較大，從圖中可以看出，自主移動(dòng)機(jī)器人在180～500步之間位置估計(jì)誤差抖動(dòng)較大。但隨著機(jī)器人游走步數(shù)的增大，機(jī)器人探測到的路標(biāo)增多，本文方法產(chǎn)生的誤差明顯減小。圖中誤差圖有峰值出現(xiàn)，出現(xiàn)的原因是由于機(jī)器人轉(zhuǎn)彎時(shí)的誤差比平時(shí)大，從圖中可以看出本文方法在機(jī)器人轉(zhuǎn)彎時(shí)的誤差比卡爾曼濾波的SLAM算法產(chǎn)生的誤差明顯小?？柭鼮V波的SLAM算法產(chǎn)生的誤差的均值和方差分別為1.046 7和0.842 7，結(jié)合全局位置估計(jì)和卡爾曼濾波的SLAM算法產(chǎn)生的誤差的均值和方差分別為0.791 0 和0.409 1。

圖3 2種SLAM算法的機(jī)器人定位誤差比較Fig.3 The robot positioning error under two kinds of SLAM algorithm

3.2.3 2種游走策略下移動(dòng)機(jī)器人耗時(shí)的比較

由于移動(dòng)機(jī)器人采用基于路標(biāo)的全局位置估計(jì)探索策略后，每次轉(zhuǎn)彎等動(dòng)作時(shí)需要較多的時(shí)間規(guī)劃下一步的游走路徑，所以相對(duì)于隨機(jī)游走，移動(dòng)機(jī)器人游走的耗時(shí)增加。實(shí)驗(yàn)表明移動(dòng)機(jī)器人采用路標(biāo)的全局位置估計(jì)探索策略時(shí)耗時(shí)為237.588 2 s，而移動(dòng)機(jī)器人隨機(jī)游走時(shí)耗時(shí)為81.959 9 s。

實(shí)驗(yàn)結(jié)果表明，相對(duì)于卡爾曼濾波的SLAM算法，采用結(jié)合全局位置估計(jì)和卡爾曼濾波的SLAM算法后機(jī)器人自身位置估計(jì)的精度有明顯提高，但耗時(shí)相對(duì)增加。改變初始條件，多次實(shí)驗(yàn)，每次的誤差數(shù)據(jù)不盡相同，但得到的結(jié)論相同。

4 結(jié)束語

采用基于路標(biāo)的全局位置估計(jì)探索策略后，相對(duì)于機(jī)器人隨機(jī)游走，機(jī)器人的全局定位誤差有了較為明顯的減小。結(jié)合全局位置估計(jì)和卡爾曼濾波的SLAM算法相對(duì)于基于卡爾曼濾波的SLAM算法，可以有效地減小機(jī)器人位置的估計(jì)誤差。更多的實(shí)驗(yàn)分析以及機(jī)器人多步優(yōu)化路徑規(guī)劃問題等，值得進(jìn)一步研究。

[1]DURRANT-WHYTE H F.An autonomous guided vehicle for cargo handling applications[J].International Journal of Robotics Research，1996，15(5):407-440.

[2]MONTEMERLO M，PINEAU J，ROY N，et al.Experiences with a mobile robotic guide for the elderly[C]//Proceedings of the 18th National Conference on Artificial Intelligence.Edmonton，Canada.2002:587-592.

[3]HUNTSBERGER T，AGHAZARIAN H，CHENG Y，et al.Rover autonomy for long range navigation and science data acquisition on planetary surfaces[C]//Proceedings of IEEE International Conference on Roboticsand Automation.Washington，DC，2002:3161-3168.

[4]SMITH R，SELF M，Cheeseman P.Estimating uncertain spatial relationships in robotics[M].Autonomous Robot Vehicles，1990:167-193.

[5]LI C，HUANG Y，KANG Y，et al.Monocular SLAM using verticalstraightlineswith inverse-depth representation[C]//Proceedings of 7th IEEE World Congress on Intelligent Control and Automation.Chongqing，China，2008:3015-3020.

[6]THRUN S，BURGARD W，F(xiàn)OX D.A probabilistic approach to concurrent mapping and localization for mobile robots[J].Autonomous Robots，1998，5(3/4):253-271.

[7]GRISETTI G，STACHNISS C，BURGARD W.Improved techniques for grid mapping with Rao-Blackwellized particle filters[J].IEEE Transactions on Robotics，2007，23(1):34-46.

[8]張恒，樊曉平.移動(dòng)機(jī)器人同步定位與地圖構(gòu)建過程中的軌跡規(guī)劃研究[J].機(jī)器人，2006，28(3):285-290.ZHANG Heng，F(xiàn)AN Xiaoping.Mobile robot trajectory planning in simultaneous localization and mapping problem[J].Robot，2006，28(3):285-290.

[9]NEWMAN P.On the structure and solution of the simultaneous localisation and map building problem[D].Sydney:University of Sydney，1999:1-5.

[10]熊蓉.室內(nèi)未知環(huán)境線段特征地圖構(gòu)建[D].杭州:浙江大學(xué)，2009:10-23.XIONG Rong.Line feature map building for unknown indoor environments[D].Hangzhou:Zhejiang University，2009:10-23.

[11]DISSANAYAKE M W M G，NEWMAN P，CLARK S，et al.A solution to the simultaneous localization and map building(SLAM)problem[J].IEEE Transactions on Robotics and Automation，2001，17(3):229-241.

[12]CASTELLANOS J A，MONTIEL J M M，NEIRA J，et al.The SPmap:A probabilistic framework for simultaneous localization and map building[J].IEEE Transactions on Robotics and Automation，1999，15(5):948-952.

[13]WILLIAMS S，DISSANAYAKE G，DURRANT-WHYTE H F.Towards terrain-aided navigation for underwater robotics[J].Advanced Robotics，2001，15(5):533-549.

[14]THRUN S.Probabilistic algorithms in robotics[J].AI Magazine，2000，21(4):93-109.

[15]HAHNEL D，BURGARD W，F(xiàn)OX D，et al.An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements[C]//Proceedings of 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems.Las Vegas，NV，2003:206-211.

[16]李一波，張慶濤.室內(nèi)未知環(huán)境遍歷路徑規(guī)劃算法綜

述[J].計(jì)算機(jī)科學(xué)，2012，39(11A):334-338.

LI Yibo，ZHANG Qingtao.Review of coverage path planning arithmetic in unknown indoor environment[J].Computer Science，2012，39(11A):334-338.

[17]ULRICH I，MONDADA F，NICOUD J D.Autonomous vacuum cleaner[J].Robotics and Autonomous Systems，1997，19(3):233-245.

[18]OH J S，PARK J B，CHOI Y H.Complete coverage navigation of clean robot based on triangular cell map[J].IEEE Transactions on Industrial Electronics，2004，51(3):718-726.

[19]JEBARI I，BAZEILLE S，F(xiàn)ILLIAT D.Informatics in control，automation and robotics[M].Berlin:Springer，2012:224-237.