移動(dòng)機(jī)器人的自主導(dǎo)航

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