移動機器人的自主導(dǎo)航

移動機器人的自主導(dǎo)航一、討論的背景二、移動機器人是一個集環(huán)境感知、動態(tài)決策與規(guī)劃、行為掌握與執(zhí)行等多功能于一體的綜合系統(tǒng)。它集中了傳感器技術(shù)、計算機技術(shù)、機械工程、電子工程、自動化掌握工程以及人工智能等多學(xué)科的討論成果，是目前科學(xué)技術(shù)進(jìn)展最活躍的領(lǐng)域之一。隨著機器人性能不斷地完善，移動機器人的應(yīng)用范圍大為擴展，不僅在工業(yè)、農(nóng)業(yè)、國防、醫(yī)療、服務(wù)等行業(yè)中得到廣泛的應(yīng)用，而且在排雷、搜捕、救援、輻射和空間領(lǐng)域等有害與危急場合都得到很好的應(yīng)用。因此，移動機器人技術(shù)已經(jīng)得到世界各國的普遍關(guān)注。三、在自主式移動機器人相關(guān)技術(shù)的討論中，導(dǎo)航技術(shù)是其討論核心，同時也是移動機器人實現(xiàn)智能化及完全自主的關(guān)鍵技術(shù)。導(dǎo)航是指移動機器人通過傳感器感知環(huán)境信息和自身狀態(tài)，實現(xiàn)在有障礙的環(huán)境中面對目標(biāo)的自主運動。導(dǎo)航主要解決以下三方面的問題：(1)通過移動機器人的傳感器系統(tǒng)獵取環(huán)境信息;(2)用肯定的算法對所獲信息進(jìn)行處理并構(gòu)建環(huán)境地圖;(3)依據(jù)地圖實現(xiàn)移動機器人的路徑規(guī)劃及運動掌握。四、相關(guān)技術(shù)五、移動機器人定位是指確定機器人在工作環(huán)境中相對于全局坐標(biāo)的位置是移動機器人導(dǎo)航的基本環(huán)節(jié)。定位方法依據(jù)機器人工作環(huán)境的簡單性、配備傳感器種類和數(shù)量等方面的不同而采納多種方法。主要方法有慣性定位、標(biāo)記定位、GPS定位、基于地圖的定位等，它們都不同程度地適用于各種不同的環(huán)境，括室內(nèi)和室外環(huán)境，結(jié)構(gòu)化環(huán)境與非結(jié)構(gòu)化環(huán)境。度之間達(dá)到一種平衡。相對于其他定位方法，基于采樣表示MCL方法的優(yōu)點如下:①與卡爾曼濾波器方法相比，可以表示多模分布，并可實現(xiàn)機器人的全局定位;②與基于柵格的馬爾可夫定位方法相比，能以相當(dāng)高的頻率集成測量數(shù)據(jù);③與固定尺寸柵格單元的馬爾可夫定位方法相比，具有更高的定位精度，緣由在于采樣中對應(yīng)的狀態(tài)表示沒有被離散化;④易于實施。然而粒子濾波器算法也存在不足，其緣由在于估量的隨機性。例如，假如采樣集的尺寸較小機器人可能僅由于MCL沒能夠生成正確位置的一個采樣而導(dǎo)致失去對其位置的跟蹤。算法也不適用于機器人綁架問題，由于一旦機器人處于綁架狀態(tài)，則可能在機器人新位姿四周沒有合適的采樣。因此，當(dāng)傳感器不足夠精確時，上述基本的MCL算法性能會急速下降。極端狀況下，常規(guī)MCL算法在傳感器信息無噪聲干擾時也會失敗。為避開和削減常規(guī)MCL算法的缺陷，討論人員提出了多種改進(jìn)方案，如混合McL算法、實時粒子濾波器方、幫助粒子濾波器等。三十、(3)路徑規(guī)劃三十一、不論采納何種導(dǎo)航方式，智能移動機器人主要完成路徑規(guī)劃、定位和避障等任務(wù)。路徑規(guī)劃是自主式移動機器人導(dǎo)航的基本環(huán)節(jié)之一。它是依據(jù)某一性能指標(biāo)搜尋一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或近似最優(yōu)的無碰路徑。依據(jù)機器人對環(huán)境信息知道的程度不同，可分為兩種類型:環(huán)境信息完全知道的全局路徑規(guī)劃和環(huán)境信息完全未知或部分未知，通過傳感器在線地對機器人的工作環(huán)境進(jìn)行探測，以獵取障礙物的位置、外形和尺寸等信息的局部路徑規(guī)劃。全局路徑規(guī)劃包括環(huán)境建模和路徑搜尋策略兩個子問題。依據(jù)不同的地圖模型，路徑規(guī)劃可分為兩類:基于圖結(jié)構(gòu)的路徑規(guī)劃、基于波陣面的路徑規(guī)劃。對于圖結(jié)構(gòu)的路徑規(guī)劃，通常依靠于環(huán)境結(jié)構(gòu)的拓?fù)鋱D表示，如可視圖法(v-GraPh)、自由空間法(FreespaeeAPproaeh)和四叉樹法等(Grids)等。在該類以拓?fù)涞貓D表示的路徑規(guī)劃中，通?？芍苯硬杉{基于圖的最優(yōu)路徑計算方法獵取路徑信息，如A*算法、D*算法?？梢晥D法以機器人為一點，將機器人、目標(biāo)點和多邊形障礙物的各頂點進(jìn)行組合連接，要求機器人和障礙物各頂點之間、目標(biāo)點和障礙物各頂點之間以及各障礙物頂點與頂點之間的連線，均不能穿越障礙物，即直線是可視的。搜尋最優(yōu)路徑的問題就轉(zhuǎn)化為從起始點到目標(biāo)點經(jīng)過這些可視直線的最短距離問題。廣義Voronoi圖法和切線圖法對可視圖法進(jìn)行了改進(jìn)，其中Voronni圖的基本思想是產(chǎn)生與全部邊界點等距的線，而這些線的走向是沿著走廊或開口的中間，沿該線運動不會與任何障礙物沖突。切線圖用障礙物的切線表示弧，因此是從起點到目標(biāo)點的最短路徑的圖，即機器人必需幾乎接近障礙物行走。自由空間法應(yīng)用于機器人路徑規(guī)劃，采納預(yù)先定義的如廣義錐形和凸多邊形等基本外形構(gòu)造自由空間，并將自由空間表示為連通圖，通過搜尋連通圖來進(jìn)行路徑規(guī)劃。該法比較敏捷，起始點和目標(biāo)點的轉(zhuǎn)變不會造成連通圖的重構(gòu)，但算法的簡單程度與障礙物的多少成正比，且不是任何狀況下都能獲得最短路徑。四叉樹或八叉樹表示通常是將標(biāo)準(zhǔn)柵格地圖轉(zhuǎn)化為圖的形式，并通過優(yōu)化算法完成路徑搜尋。波陣面?zhèn)鞑バ鸵?guī)劃器(WaVe-frontTransform)很適合柵格類型地圖的規(guī)劃處理。其基本原理是:波陣面把結(jié)構(gòu)空間視為一種導(dǎo)熱物質(zhì)，假如存在一個路徑，熱從起始節(jié)點向目標(biāo)節(jié)點傳導(dǎo)，熱量將最終達(dá)到目標(biāo)節(jié)點，同時全部柵格單元到目標(biāo)的最優(yōu)路徑都可以計算出來，該算法與勢場原理相像，讓路徑自身來表示機器人應(yīng)當(dāng)怎么做。該類算法討論比較豐富，在論文的節(jié)有具體敘述。局部路徑規(guī)劃的主要方法有:人工勢場法(ArtifieialPotentialField)、遺傳算法(GenetieAlgorithm)和模糊規(guī)律算法(FuzzyLogieAlgorithm)等。人工勢場法將機器人在環(huán)境中的運動視為一種虛擬的人工受力場中的運動。障礙物對機器人產(chǎn)生斥力，目標(biāo)點產(chǎn)生引力，引力和斥力的合力作為機器人的加速力，來掌握機器人的運動方向和計算機器人的位置。該法結(jié)構(gòu)簡潔，便于低層的實時掌握，在實時避障和平滑的軌跡掌握方面，得到了廣泛的應(yīng)用，但對存在局部最優(yōu)解的問題，簡潔產(chǎn)生死鎖現(xiàn)象(DeadLock),因而可能使機器人在到達(dá)目標(biāo)點之前就停留在局部最優(yōu)點。多數(shù)優(yōu)化算法都是單點搜尋算法，很簡潔陷入局部最優(yōu)，而遺傳算法卻是一種多點搜尋算法，因而更有可能搜尋到全局最優(yōu)解。由于遺傳算法的整體搜尋策略和優(yōu)化計算不依靠于梯度信息，所以解決了路徑規(guī)劃處理中一些其它優(yōu)化算法無法解決的問題。但遺傳算法運算速度不快，進(jìn)化眾多的規(guī)劃要占據(jù)較大的存儲空間和運算時間?；趯崟r傳感信息的模糊規(guī)律算法參考人的駕駛閱歷，通過查表得到規(guī)劃信息，實現(xiàn)局部路徑規(guī)劃,可克服勢場法易產(chǎn)生的局部微小問題，適用于時變未知環(huán)境下的路徑規(guī)劃，實時性較好。三十二、（4）同步地圖創(chuàng)建與自定位三十三、移動機器人地圖創(chuàng)建需要機器人位姿和基于當(dāng)前位姿的外界環(huán)境信息。因此地圖創(chuàng)建過程就是機器人對所在環(huán)境進(jìn)行遍歷，并將遍歷過程中獵取的環(huán)境信息不斷融合累積的過程。地圖創(chuàng)建最簡潔的方法為增進(jìn)式方案，它包含2個部分:首先采用當(dāng)前地圖估量機器人位置，然后當(dāng)機器人獵取新的信息時對當(dāng)前估量位置四周區(qū)域進(jìn)行局部地圖更新。然而在未知環(huán)境下的實時地圖創(chuàng)建中，增進(jìn)式地圖創(chuàng)建方案明顯不能滿意需要。由于機器人運動存在累積誤差，僅依靠運動掌握信息不能確定機器人位姿，需依據(jù)地圖中的外部環(huán)境信息不斷進(jìn)行校正定位;而地圖構(gòu)建過程又依靠于精確的位姿信息，兩過程相互沖突與依靠，必需同時考慮，即要求實現(xiàn)同步地圖創(chuàng)建和定位。作為移動機器人討論的核心問題，近20年來SLAM討論吸引了全世界范圍內(nèi)大批討論人員的參加，并已經(jīng)取得系列重要討論成果。方法主要可分為:基于Kalman濾波器的跟蹤方法;基于EM算法的全局優(yōu)化方法;基于Partiolefilters的SLAM算法;此外,討論人員也提出了基于上述算法的混合方案,以及基于其他計算智能方法的SLAM方案。上述討論為SLAM問題奠定了基本理論框架和討論基礎(chǔ)，但是仍舊存在很多難題。1六、慣性定位是在移動機器人的車輪上裝有光電編碼器通過對車輪轉(zhuǎn)動的紀(jì)錄來粗略地確定移動機器人位置。該方法雖然簡潔，但是由于車輪與地面存在打滑現(xiàn)象，生的累積誤差隨路徑的增加而增大，導(dǎo)致定位誤差的漸漸累積，從而引起更大的差。七、標(biāo)記定位法是在移動機器人工作的環(huán)境里人為地設(shè)置一些坐標(biāo)已知的標(biāo)記，八、超聲波放射器、激光反射板等,通過機器人的傳感器系統(tǒng)對標(biāo)記的探測來確定機器人在全局地圖中的位置坐標(biāo)。三角測量法是標(biāo)記定位中常用的方法，機器人在同一點探測到三個陸標(biāo)，并通過三角幾何運算，由此可確定機器人在工作環(huán)境中的坐標(biāo)。標(biāo)記定位是移動機器人定位中普遍采納的方法，其可獲得較高的定位精度且計量小，但是在實際應(yīng)用中需要對環(huán)境作一些改造，添加相應(yīng)的標(biāo)記，不太符合真正意義的自主導(dǎo)航。九、GPS定位是采用環(huán)繞地球的24顆衛(wèi)星，精確計算使用者所在位置的浩大衛(wèi)星網(wǎng)定位系統(tǒng)。GPS定位技術(shù)應(yīng)用已經(jīng)特別廣泛，除了最初的軍事領(lǐng)域外，在民用方面也得到了廣泛的應(yīng)用，但是由于在移動導(dǎo)航中，移動GPS接收機定位精度受到衛(wèi)星信號狀況和道路環(huán)境的影響，同時還受到時鐘誤差、傳播誤差、接收機噪聲等諸多因素的影響，因此，單純采用GPS定位精度比較低、牢靠性不高，所以在機器人的導(dǎo)航應(yīng)用中通常還輔以磁羅盤、光碼盤與GPS數(shù)據(jù)進(jìn)行融合，提高導(dǎo)航精度。此外，GPS定位系統(tǒng)也不適用于室內(nèi)或者水下機器人的導(dǎo)航中以及對于位置精度要求較高的機器人系統(tǒng)?；诃h(huán)境地圖模型匹配定位是指移動機器人通過自身的傳感器系統(tǒng)，探測四周環(huán)境，采用感知到的局部環(huán)境信息和肯定的算法進(jìn)行局部地圖構(gòu)建，并將建立的局部地圖與其內(nèi)部事先存儲的全局地圖進(jìn)行匹配，從而實現(xiàn)定位。這種定位方法常用于移動機器人的全局定位。十、2.2移動機器人的地圖構(gòu)建十一、由于路徑規(guī)劃和很多定位方法都是基于環(huán)境地圖，所以構(gòu)建并維護(hù)一個環(huán)境地圖也是自主導(dǎo)航中的一個重要內(nèi)容。機器人采用對環(huán)境的感知信息對現(xiàn)實世界進(jìn)行建模,自動地構(gòu)建一個地圖。典型的地圖表示方法有概率柵格地圖、拓?fù)涞貓D和幾何特征地圖三種。十二、柵格地圖十三、柵格地圖是在機器人系統(tǒng)中得到廣泛應(yīng)用的一種地圖描述方法。首先由Elfes十四、和Moravec依據(jù)"occuPancygridmaPPing''算法提出的，在機器人的路徑規(guī)劃、導(dǎo)航、避障掌握、位姿估量中均得到了廣泛應(yīng)用，并成為一種通用的移動機器人地圖描述方法。柵格地圖是一種表示靜態(tài)環(huán)境的方法，用每一個柵格被占據(jù)的概率值來表示環(huán)境信息，柵格地圖很簡潔創(chuàng)建和維護(hù)，即使使用精確度不高的聲納傳感器也可以創(chuàng)建柵格地圖來表示環(huán)境信息，但是柵格地圖最大的缺點就是精確度不高，信息存儲量高。在環(huán)境規(guī)模比較大或者對環(huán)境劃分比較具體的狀況下，柵格地圖的維護(hù)所占用的內(nèi)存和CPU資源快速增長，使得計算機的實時處理變得很困難。十五、拓?fù)涞貓D十六、拓?fù)涞貓D由Brooks;Mataric等學(xué)者提出110—川。在表示環(huán)境地圖時，它并沒有一個明顯的尺度概念，而是選用一些特定的地點來描述環(huán)境信息。拓?fù)涞貓D通常表示為一個圖表，圖中的節(jié)點表示一個特定地點，連接節(jié)點的弧用來表示特定地點之間的路徑信息。拓?fù)涞貓D對于結(jié)構(gòu)化的環(huán)境是一個很有效的表示方法，這里有更多的特定地點。相反，在非結(jié)構(gòu)化環(huán)境中，地點的識別將變得特別簡單。假如僅僅以拓?fù)湫畔⑦M(jìn)行機器人定位，機器人將很快迷失方向和位置。此外，為了更好地表示環(huán)境模型，消失了混合拓?fù)浜统叨鹊貓D的表示方法，通過加入尺度信息來補償拓?fù)湫畔ⅰ＿@樣的地圖表示方法具有拓?fù)涞貓D的高效性，尺度地圖的全都性和精確性。十七、幾何特征地圖十八、幾何特征地圖由一組環(huán)境特征組成，每一個路標(biāo)特征用一個幾何原型來近似。這種地圖只局限于表示可參數(shù)化的環(huán)境路標(biāo)特征或者可建模的對象，如點、線、面。由于以幾何位置關(guān)系來表示環(huán)境地圖，所以為了保證地圖的全都性，要求各觀測位置是相對精確的。對于結(jié)構(gòu)化的辦公室環(huán)境，用一些幾何模型來表示環(huán)境空間是可行的。用線段來擬合室內(nèi)的墻面，用點來擬合墻角、桌子角等。對于室外道路環(huán)境，可以用點特征來表示道路兩側(cè)的大樹位置。幾何特征地圖中特征的提取需要對感知信息做額外的處理，且需要大量的感知數(shù)據(jù)才能得到結(jié)果。十九、移動機器人路徑規(guī)劃技術(shù)二十、不論采納何種導(dǎo)航方式，智能移動機器人主要完成路徑規(guī)劃、定位和避障等任務(wù)。路徑規(guī)劃是自主式移動機器人導(dǎo)航的基本環(huán)節(jié)之一。它是依據(jù)某一性能指標(biāo)搜尋一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或近似最優(yōu)的無障路徑。依據(jù)機器人對環(huán)境信息把握的程度不同，可分為兩種類型:環(huán)境信息完全可知的全局路徑規(guī)劃和環(huán)境信息完全未知或部分未知，通過傳感器在線地對機器人的工作環(huán)境進(jìn)行探測，以獵取障礙物的位置、外形和尺寸等信息的局部路徑規(guī)劃。二十一、全局路徑規(guī)劃二十二、全局路徑規(guī)劃的主要方法有:可視圖法、柵格法今和拓?fù)浞ǖ?。所謂圖，就是用弧連接節(jié)點的數(shù)據(jù)結(jié)構(gòu)，節(jié)點代表機器人的位置，弧代表移動機器人在兩個位置間的移動線路?？梢晥D法將機器人、目標(biāo)點和多邊形障礙物的各頂點視為節(jié)點。并將機器人、目標(biāo)點和多邊形障礙物的各頂點進(jìn)行組合連接，連接的直線視為弧，機器人和障礙物各頂點之間、目標(biāo)點和障礙物各頂點之間以及各障礙物頂點與頂點之間的連線均不能穿越障礙物,即直線是可視的。因此，可視圖法可將最優(yōu)路徑搜尋問題轉(zhuǎn)化為在這些直線中搜尋從起始點到目標(biāo)點的最短距離問題是全局路徑規(guī)劃中一種經(jīng)典的方法。其常用的有Thngeni圖法和Voronoi圖法。可視圖法雖然給簡單的路徑規(guī)劃問題提出了一種可行的方法，但本身也存在其敏捷性和實時性不高的問題。由于傳統(tǒng)的丁hngeni圖法要求移動物體沿著障礙物的邊緣移動，所以當(dāng)物體可以旋轉(zhuǎn)時，最短路徑特別簡潔受到物體模型的影響而不精確。而voronoi圖法可有效的解決Thngeni圖法在三維空間中的缺陷。幾ngeni圖，二十三、如圖1.1所示，用障礙物的切線表示弧，因此是從起始點到目標(biāo)點的最短路徑的圖。二十四、圖1.2用完可能遠(yuǎn)離障礙物和墻壁的路徑表示弧。因此從起始節(jié)點到目標(biāo)節(jié)點的路徑將會增長，但可以有效的提高機器人移動過程中的平安系數(shù)。此外，假如環(huán)境中障礙物過多，可視圖法的簡單性快速增加，為了提高系統(tǒng)的實時性，可以采納優(yōu)化算法刪除一些不必要的連線，如DynamicVisibihtyGr即h方法和T-Veetors方法等。柵格法是移動機器人以構(gòu)建好的全局柵格地圖做為先驗信息，依據(jù)肯定的約束算法而規(guī)劃出一條從起始點到目標(biāo)點的最優(yōu)路徑。由于該方法是基于柵格地圖的，因此路徑規(guī)劃的實時性和精確性往往受到柵格地圖的制約。若柵格過小，辨別率雖高，但抗干擾性差，由于存儲的信息量大，處理時間長而導(dǎo)致實時性較差;柵格越大，其抗干擾性越強，實時性好，但存在辨別率低，路徑規(guī)劃不精確的缺點。所以如何選擇合適的柵格，保證路徑規(guī)劃的實時性和精確性是其討論的主要問題。拓?fù)浞ㄊ腔谕負(fù)涞貓D實現(xiàn)路徑規(guī)劃的一種方法。拓?fù)浞ɑ舅枷胧墙稻S法，即將在高維幾何空間中求路徑的問題轉(zhuǎn)化為低維拓?fù)淇臻g中判別連通性的問題。優(yōu)點在于采用拓?fù)涮卣鞔蟠罂s小了搜尋空間。算法簡單性僅依靠于障礙物數(shù)目，理論上是完備的。缺點是建立拓?fù)渚W(wǎng)絡(luò)的過程相當(dāng)簡單，特殊在增加障礙物時如何有效地修正己經(jīng)存在的拓?fù)渚W(wǎng)是有待解決的問題。二十五、局部路徑規(guī)劃技術(shù)局部路徑規(guī)劃的主要方法有:人工勢場法、模糊規(guī)律算法、遺傳算法等。人工勢場法是由腸atib提出的一種虛擬力法其基本思想是建立一種虛擬力，將機器人在未知環(huán)境中的運動視為在人工虛擬力場中的運動，即目標(biāo)對被規(guī)劃對象存在吸引力，而障礙物對其有排斥力，引力與斥力的合力作為機器人運動的加速力，從而計算機器人的位置和掌握機器人的運動方向。勢場法結(jié)構(gòu)簡潔，便于低層的實時掌握。但它存在陷阱區(qū)域以及在相近的障礙物群中不能識別路徑等缺點。模糊規(guī)律算法是通過對駕駛員的工作過程觀看討論得出的。駕駛員的避碰動作并不是對環(huán)境信息的精確計算來完成的，而是依據(jù)比較模糊的環(huán)境信息，靠閱歷來決策實行什么樣的操作。模糊規(guī)律算法基于實時傳感器的信息，參考人的駕駛閱歷，通過查表得到規(guī)劃出的信息，完成局部路徑規(guī)劃。該法克服了勢場法易產(chǎn)生局部微小的問題。而且計算量小，易做到邊規(guī)劃邊跟蹤，適用于時變未知環(huán)境下的路徑規(guī)劃，實時性較好。二十六、遺傳算法是Holfand教授于1962年首先提出的。遺傳算法是一種基于自然選二十七、擇和基因遺傳學(xué)原理的搜尋算法。遺傳算法借鑒物種進(jìn)化的思想，將欲求解的問題進(jìn)行編碼，每一個可能解均被表示成字符串的形式，初始化隨機產(chǎn)生一個種群的候選群，種群規(guī)模固定為N,用合理的適應(yīng)度函數(shù)對種群進(jìn)行性能評估，并在此基礎(chǔ)上進(jìn)行繁殖、交叉和變異遺傳操作。適應(yīng)度函數(shù)類似于自然選擇的某種力氣，繁殖、交叉和變異這三個遺傳算子則分別模擬了自然界生物的繁衍、交配和基因突變。多數(shù)優(yōu)化算法都是單點搜尋算法，很簡潔陷入局部最優(yōu)，而遺傳算法卻是一種多點搜尋算法，因而更有可能搜尋到全局最優(yōu)解。在簡單環(huán)境下，遺傳算法也存在導(dǎo)致進(jìn)化緩慢、易產(chǎn)生非法個體及進(jìn)化效率不高的問題。對于移動機器人而言，導(dǎo)航力量是其最重要的功能之一，機器人首先要求避開危急狀況如碰撞等，將機器人停留于平安的操作環(huán)境下;其次需具備完成到環(huán)境中某一特定位置執(zhí)行特定任務(wù)的力量。通常移動機器人導(dǎo)航問題可總結(jié)為"在哪里?"、"去哪里?"、"怎么去?"三個問題。為解決上述三個問題，通常涉及以下三方面討論:①地圖創(chuàng)建和地圖識別解釋，即用有效表示模型，將移動機器人環(huán)境遍歷過程中獵取的環(huán)境信息儲存記憶;②自定位(self-focalization),確定移動機器人在地圖中當(dāng)前位置信息;③路徑規(guī)劃(PathPlanning)，給定當(dāng)前位置和目標(biāo)信息，選擇最優(yōu)運動掌握序列驅(qū)動機器人到達(dá)目標(biāo)位置。地圖表示模型和地圖創(chuàng)建機器人地圖可以分為兩大類:幾何地圖和拓?fù)涞貓D。幾何地圖又可分為柵格地圖和特征地圖。柵格地圖將空間環(huán)境地圖劃分為若干規(guī)章方格，依據(jù)傳感器獵取的環(huán)境信息，采納有效的傳感器幾何模型確定當(dāng)前柵格區(qū)域是否被占用。由于測距傳感器幾何模型不精確問題和環(huán)境的干擾影響，人們先后提出了基于聲納和激光信息融合的柵格概率計算模型、MuRIE柵格模型、基于反饋神經(jīng)網(wǎng)絡(luò)模型的柵格概率計算方法、改進(jìn)型模糊自調(diào)整柵格地圖模型、前向傳感器模型，削減傳感器存在的鏡面反射、測量數(shù)據(jù)冗余、隨機性誤差等影響。Ribo.M等分析了Bayesian概率模型、D—S證據(jù)理論、模糊集三種柵格地圖更新模型的優(yōu)缺點。特征地圖由一系列包含位置信息的特征組成【，刀。特征地圖創(chuàng)建主要包括特征檢測、特征匹配和更新三個方面。特征的選擇特別廣泛，多面體、平面體、直線、角點、目標(biāo)邊緣等均可作為地圖特征，如Ayache等采納三目立體攝像機獵取環(huán)境中的直線段信息，Leonard等提出Ren模型提取固定特征，Ipv.Lip等采納EAFc算法從原始聲納測量數(shù)據(jù)中提取線段特征，Tardos等用Hough變換實現(xiàn)特征的提取。多傳感器融合是提高特征檢測力量的重要手段，Castellanos等對激光和攝像機數(shù)據(jù)在特征級進(jìn)行融合;wijk等用三角融合測量方法TBF提取點目標(biāo)口］,choset等［551提出ATM模型實現(xiàn)點特征的精確提取。特征地圖的匹配和更新模型常見的有kalman模型、粒子濾波器等，詳見論文第六章。二十八、拓?fù)涞貓D由環(huán)境中特征位置或區(qū)域組成的節(jié)點及其連接關(guān)系組成[']。拓?fù)涞囟?、圖節(jié)點的定義和識別是首要問題，它可以由操作人員直接定義或由機器人系統(tǒng)自動生成。第一種定義方法是人為預(yù)定節(jié)點標(biāo)志，通常選擇走廊、門、墻和角點等來完成空間環(huán)境的定義。其次是特定位置法，即依據(jù)特定位置的環(huán)境信息定義節(jié)點。KuiPers等通過采納爬山法查找局部唯一特征點，采用外部傳感器感知的環(huán)境信息定義節(jié)點。Kortenkamp等提出用入口(gateway)作為節(jié)點標(biāo)志等。第三種節(jié)點定義為，傳感器測量值相像的區(qū)域，如Nehmzow等直接依據(jù)柵格直方圖信息進(jìn)行節(jié)點定義f64—66],Ulrich等基于圖像信息進(jìn)行節(jié)點識別和定義。拓?fù)涞貓D中節(jié)點之間的關(guān)系可以分為:①鄰接關(guān)系,即可從一個節(jié)點直接到另一節(jié)點163,67];②相對幾何關(guān)系，即依據(jù)機器人內(nèi)部傳感器如里程計和方向盤信息，確定節(jié)點之間的相對幾何位置。③肯定位置關(guān)系，即每個節(jié)點被指定全局位置坐標(biāo)。④隱含連接，節(jié)點之間的關(guān)系由包含有通用路標(biāo)的節(jié)點推想獲得。依據(jù)連接關(guān)系信息，移動機器人可從一個節(jié)點區(qū)域運動到另一節(jié)點區(qū)域，從而更有利于高級任務(wù)處理如導(dǎo)航和規(guī)劃等。拓?fù)涞貓D的創(chuàng)建有兩種方式，一種是直接依據(jù)傳感器信息和機器人運動模型創(chuàng)建，另一種是從幾何地圖(特殊是柵格地圖)提取節(jié)點和連接關(guān)系，如常見的廣義voronoi圖法和四叉樹法(2)自定位(self-loealization)GPS全球定位系統(tǒng)有效解決了"我在哪里"的問題，然而該定位系統(tǒng)對于室內(nèi)機器人或者微型機器人而言，其定位精度難以達(dá)到要求，而且GPS系統(tǒng)在室內(nèi)或者障礙物密集區(qū)域也受到很大限制，因此需要討論其他的定位方案。定位問題有3種形式:①局部跟蹤:假如機器人的初始姿勢已知，則定位就一個跟蹤問題，跟蹤問題可以通過有界的不確定性加以描述;②全局定位，其中機器人初始位置完全未知，必需在全局不確定條件下進(jìn)行機器人定位;③綁架問題，即機器人在運動操作過程中，被人為搬運至任意位置區(qū)域下的定位問題，該種狀況通常用于測試極端條件下定位方法的魯棒性。目前，常用的定位方法有基于Kalman濾波器的跟蹤定位模型、Markov概率定位模型、基于粒子濾波器的蒙特卡羅定位模型等?？柭鼮V波器是定位定位算法中最主要手段之一，它用高斯分布表示后驗概率。為解打算位過程中測量模型的非線性問題，人們提出了擴展Kalman模型。當(dāng)機器人移動時，位置估量