【正文】 進(jìn)步為多傳感器數(shù)據(jù)的分析和處理提供了理論基礎(chǔ)。 柵格地圖即將整個(gè)工作環(huán)境分為若干相同大小的柵格，對(duì)于每個(gè)柵格指出其中存在障礙物的可能性。柵格地圖很容易創(chuàng)建和維 護(hù)，機(jī)器人所了解的每個(gè)柵格的信息直接與環(huán)境中某區(qū)域?qū)?yīng)，使用聲納這樣的廉價(jià)傳感器即可獲得創(chuàng)建地圖的信息并加入地圖中，借助于該地圖，可以方便地進(jìn)行自定位和路徑規(guī)劃。 幾何特征地圖是指機(jī)器人收集環(huán)境的感知數(shù)據(jù)，從中提取更為抽象的幾何特征來描述環(huán)境，例如線段或曲線，這種表示方法更為緊湊，且方便于位置估計(jì)和目標(biāo)識(shí)別。 Chatila 和 Laumond 最早提出在全局坐標(biāo)系中使用多邊形 6 來表示物體。 1996 年AAAI 移動(dòng)機(jī)器人競(jìng)賽冠軍“ Jeeves”則從機(jī)器人聲納的測(cè)量數(shù)據(jù)序列中尋找室內(nèi)環(huán)境中的墻 (用線段表示 )來逐步構(gòu)建地圖。 拓?fù)涞貓D是另一種緊湊地圖表示方法。在這方面最早成功的方法是由Kuipers 和 Byun 提出的，拓?fù)漤旤c(diǎn)被定義為擁有最多等距障礙物的點(diǎn)， Choset的方法與此類似，這種點(diǎn)被稱為匯合點(diǎn) (meet points)，頂點(diǎn)間由弧連接，弧中包含了一點(diǎn)向另一點(diǎn)移動(dòng)的度量信息，在仿真中發(fā)現(xiàn)這種方法能夠可靠地在大規(guī)模的室內(nèi)環(huán)境中實(shí)現(xiàn)。 Shatkay 和 Kaelbling 通過觀測(cè)路標(biāo)來建立 環(huán)境的拓?fù)涞貓D，并通過路標(biāo)匹配和 BaumWelsh 算法實(shí)現(xiàn)機(jī)器人的定位。拓?fù)涞貓D占用空間較 少 (決定于環(huán)境的復(fù)雜度 )，可以實(shí)現(xiàn)快速的路徑規(guī)劃，不需要機(jī)器人準(zhǔn)確的位置信息，也為人機(jī)交互下達(dá)指令提供了一種更為自然的接口 ； 但難以創(chuàng)建和維護(hù)，特別是傳感器誤差較大時(shí)，如果環(huán)境中存在兩個(gè)很相似的地方，將很難確定這是否為同一節(jié)點(diǎn)。感知信息的不確定性，必然導(dǎo)致模型的不確定；因此，當(dāng)依據(jù)模型和感知進(jìn)行決策時(shí)決策也帶有不確定性，圖 22 給出了不確定信息在地圖創(chuàng)建中的傳遞過程。 7 2)如何依據(jù)對(duì)信息的不確定性描述創(chuàng)建地圖。 目前存在 多種用來描述和處理不確定性的方法，如概率方法、模糊邏輯、信任度量、證據(jù)理論、神經(jīng)網(wǎng)絡(luò)、灰色系統(tǒng)理論等等，這些方法都有自己的特點(diǎn)和適當(dāng)?shù)膽?yīng)用場(chǎng)合。 Elfes 和 Moravec 最早提出了用概率值來表示柵格地圖中每個(gè)柵格為障礙物占有的可能性。 Olson 基于最大似然估計(jì)提出了移動(dòng)機(jī)器人的概率自定位技術(shù) [16]，基本思想是比較在當(dāng)前位置上產(chǎn)生的地圖和以前的地圖并進(jìn)行概率意義上的最大匹配， Olson 的方法在火星探索車上進(jìn)行了實(shí)驗(yàn)。 卡爾曼濾波是 1960 年由 提出的著名算法，蔡鶴皋 [17]等人闡述了卡爾曼濾波在多傳感器數(shù)據(jù)融合技術(shù)領(lǐng)域的應(yīng)用。 8 第 3 章 概率定位方法簡(jiǎn)介 概述 定位是根據(jù)先驗(yàn)環(huán)境地圖信息，結(jié)合當(dāng)前位置以及傳感器輸入信息，準(zhǔn)確確定機(jī)器人位姿的 過程。 移動(dòng) 機(jī)器人定位 有三種類型：最簡(jiǎn)單的定位問題、也是迄今為止研究最多的問題 — 位置跟蹤 [1]，機(jī)器人初始位置已知，通過里程計(jì) 碼盤反饋信息實(shí)現(xiàn)位姿估計(jì)，但 必須補(bǔ)償里程計(jì)累積誤差； 更具有挑戰(zhàn)性的是全局定位問題 [2]，初始位置未知， 全局位置通過多峰值概率分布函數(shù)表示，機(jī)器人必須能夠處理 多種不同的位置假設(shè)，因此，全局定位問題較為困難；但最為困難的是誘拐機(jī)器人問題 [3]，即對(duì)一個(gè)已經(jīng)定位好的，在不告知被移動(dòng)的情況下，將其轉(zhuǎn)移到其他地方，重新定位 ，該方法常用來測(cè)試定位方法的魯棒性。由于這些不確定性因素的存在，使定位變的更加困難，因此， 近年來，越來越多的研究者把概率理論應(yīng)用到移動(dòng)機(jī)器人定位中。 移動(dòng)機(jī)器人定位的 系統(tǒng)狀態(tài)是機(jī)器人位姿（ yx, ,? ） ,其中（ yx, ）是機(jī)器人在二維 環(huán)境坐標(biāo)系中的坐標(biāo)， ? 是正對(duì)方向。定位的目標(biāo)是使位置概率分布盡可能的接近實(shí)際分布，實(shí)際分布是一個(gè)以 實(shí)際位置為平均值的單峰高斯分布，如果實(shí)現(xiàn)了該目標(biāo)， 就實(shí)現(xiàn)了準(zhǔn)確定位。這兩類數(shù)據(jù)分別用符號(hào)標(biāo)記為? 和 a 。 為了實(shí)現(xiàn)上述公式，必須知道兩個(gè)條件概率密度：概率 P? ?axxttt 1,1 ??表示系統(tǒng)的動(dòng)態(tài)性，即輸入相應(yīng)控制信息，系統(tǒng)狀態(tài)怎樣變化，稱 為 運(yùn)動(dòng)模型；概率 P? ?xtt?表示當(dāng)前狀態(tài) xt能感知數(shù)據(jù) ?t的可能性，稱為感知模型。 為了實(shí)現(xiàn) BF，還需要詳細(xì)定義感知模型 P? ?xtt?和 P? ?axxttt 1,1 ??，以及合理表示置信度 ? ?xtBel。 KF 不管獲得的 數(shù)據(jù)是否準(zhǔn)確，盡可能的處理所有 數(shù)據(jù) 獲得一個(gè)全局最優(yōu)估計(jì) ，因此 KF 是最優(yōu)化的。 KF 假設(shè) wt1?和 vt是條件獨(dú)立的 0均值高斯分布，系統(tǒng)初始 狀態(tài) x0是條件獨(dú)立的單峰高斯分布。在預(yù)測(cè)階段，先驗(yàn)狀態(tài)估 計(jì) ^xt? 和先驗(yàn)誤差協(xié)方矩陣 pt?組成先驗(yàn)置信度 ???????xtBel,可以按照高斯分布表示 [6]，其式為： ???????xtBel =N( ^xt? ,pt? ) ^xt? =AE? ?zzxtt 111 , ?? ?+E? ?wt 1? pt?=E??????????????????? ? ???????? ?? ^^ xxxxttTtt(6) 在 修 正 階段 ， KF 跟 據(jù) 測(cè)量 數(shù) 據(jù)對(duì) 預(yù) 測(cè)階 段 的先 驗(yàn) 狀態(tài) 估 計(jì)證信度進(jìn)行修正，形成了后驗(yàn)x t ： ???????xtBel=N( pxtt??,^ ) ? ?vPHHpKPKPPxzKxxttHTttttttttttt?? ?????????????????1^^^)((7) 盡管有許多限制條件，但 KF 已經(jīng)取得了 很大的成功。 KF 的一個(gè)關(guān)鍵優(yōu)點(diǎn)就是它的有效性，它的復(fù)雜度 是狀態(tài)空間和感知數(shù)據(jù) 維數(shù)的多項(xiàng)式函數(shù)。 然而，許多動(dòng)態(tài)系統(tǒng)和傳感器模型是非線性的，例如 全局定位的多峰值概率密度估計(jì)，線性 KF 是不能處理的。相應(yīng)的方法有 PKF、 EKF 等。其中馬爾可夫 定位能夠表示復(fù)雜的多峰值概率分布，實(shí)現(xiàn)全局定位。 POMDP 概念來自運(yùn)籌學(xué)領(lǐng)域，主要用于解決感知和動(dòng)作都具有不確定性的最優(yōu)決策問題。效用函數(shù)可以事先定義，例如可用機(jī)器人離目標(biāo)點(diǎn)的距離描述。因此 POPDP 中一個(gè)重要內(nèi)容是狀態(tài)估計(jì)，它負(fù)責(zé)根據(jù)傳感器輸入數(shù)據(jù)和機(jī)器人所采 取的動(dòng)作估計(jì)位于環(huán)境中的狀態(tài)。 馬爾可夫定位中，環(huán)境狀態(tài) 是機(jī)器人在環(huán)境中的位置；通常環(huán)境狀態(tài)用離散變量表示，如拓?fù)涔?jié)點(diǎn)或位置柵格。設(shè) Rk為機(jī)器人在 k 時(shí)刻的位置，是一隨機(jī)變量。此方法中用可信度概念而不直接用概率表示的目的是為了強(qiáng)調(diào)這是對(duì)機(jī)器人狀態(tài)的評(píng)估。當(dāng)機(jī)器人運(yùn)動(dòng)或接收到新的傳感器輸入數(shù)據(jù)時(shí)，狀態(tài) Rk 將被更新。馬爾可夫定位的任務(wù)是隨著機(jī)器人的運(yùn)動(dòng)，不斷地更新機(jī)器人位于位置 Rk 的可信度 12 ? ?RKBel ,并以可信度最大的位置作為對(duì)機(jī)器人實(shí)際的估計(jì)。m1,… .,mk1? 。這種條件概率的計(jì)算復(fù)雜度與條件變量個(gè)數(shù)成指數(shù)增長(zhǎng)關(guān)系。在介紹 Markov 定位算法之前，論文將詳細(xì)描述這兩個(gè)重要的 Markov 獨(dú)立性條件假設(shè)。 馬爾可夫獨(dú)立性假設(shè) 馬爾可夫定位的關(guān)鍵是過程的無后效性假設(shè)，即馬爾可夫假設(shè)。 1 動(dòng)作的獨(dú)立性 動(dòng) 作的獨(dú)立性是指機(jī)器人當(dāng)前時(shí)刻的狀態(tài) Rk僅與前一時(shí)刻的狀態(tài) Rk1?，以及動(dòng)作 ak1?有關(guān)，即一旦 Rk1?狀態(tài)已知時(shí) k1 時(shí)刻以前的所有動(dòng)作和狀態(tài)對(duì) k 時(shí)刻的狀態(tài)無影響。m1 ,? ,mk1? 。這一假設(shè)也是合理的，因?yàn)?k1時(shí)刻之前的動(dòng)作和位姿狀態(tài)并沒有為 k時(shí)刻的機(jī)器人位姿提供任何附加的信息。這樣一旦知道機(jī)器人在 k時(shí)刻的位置，其它的所有測(cè)量，即以前的狀態(tài)和動(dòng)作都對(duì) mk 條件概率的預(yù)測(cè)無影響。m1 ,… .,mk1? 。例如，當(dāng)給定機(jī)器人的位置時(shí)，由距離傳感器測(cè)得的距離數(shù)據(jù)只與機(jī)器人到障礙物的距離有關(guān)，而與另一傳感器測(cè)得的距離無關(guān)。 根據(jù)動(dòng)作和感知獨(dú)立性假設(shè)，與定位相關(guān)的各個(gè)問題方面都可用狀態(tài)變量Rk 、條件概率 ? ( aRR KKK 11, ?? )和 ? ( Rm Kk )進(jìn)行建模。 ? ?RKBel越大，機(jī)器人實(shí)際位于 Rk處的可能性越大。 ? ?RKBel =? ( amR kkK .~~,1.~~,1 , ) =)。()。 式 43對(duì)機(jī)器人狀態(tài)可信度的估計(jì)是遞推進(jìn)行的，系統(tǒng)初始狀態(tài)的可信度知識(shí)體現(xiàn)了定位的特點(diǎn)。如果初始時(shí)刻 機(jī)器人對(duì)其所處位置一無所知，那么初始狀態(tài)的概率分布函數(shù)可用均勻分布表示，此時(shí)相應(yīng)于全局定位問題。為了簡(jiǎn)化書寫，此常數(shù)常用 ? 表示。 ??? ) 式中， l =? ??,yx T 為環(huán)境狀態(tài)空間中的任意位置。 ??? ??表示在 k時(shí)刻已知機(jī)器人位于 Rk 處的可信度及前面的所有感知數(shù)據(jù)時(shí)，機(jī)器人觀察到特征 mk 的概率，通常也稱為感知模型。感知數(shù)據(jù) mk 是可由距離傳感器或視覺圖象處理等在環(huán)境中提取的距離數(shù)據(jù)或一個(gè)抽象特征，如門、走廊等。 1,11,1 , ?? ?? )(45) 感知模型用于更新機(jī)器人位姿狀態(tài)的可信度。 ?? ??)表示當(dāng)動(dòng)作 ak1? 立即執(zhí)行后，以及 在 k時(shí)刻的環(huán)境測(cè)量數(shù)據(jù)到來之前機(jī)器人位于位置 Rk 的概率。這是由從前面 k1 時(shí)刻的所有可能狀態(tài) Rk1? =l 轉(zhuǎn)移到當(dāng)前狀態(tài) Rk 的概率之和決定的。 ?? ?? ) =???? ?l kkkK amRR lP ),( 1,11,11 ??? ( amR kkK l 1,11,11 , ??? ? ?? )(46) =??? ?l KkK aRR lP ),( 11? ( amR kkK l 1,11,11 , ??? ? ?? ) 如果 為連續(xù)狀態(tài)變量，那么 46 式也可表示為 ? ( amR kkK 1,11,1 。 ?? ??。為了 描述 里程計(jì)測(cè)量的不確定性，其條件概率一般用均值為機(jī)器人預(yù)測(cè)位置的有界高斯分布表示。 通過上面的推導(dǎo)，可得到重要的遞推公式 ? ?RKBel = ? ? ? ?? ?amm aRRRmKKKKKKKkP PP1,11,111, ,?????? = ? ? ? ? ? ?lBellPP RaRRRmKR KKKKK ?? ???? 111 ,?(410) 對(duì)于連續(xù)狀態(tài)變量，式 410 變?yōu)? ? ?RKBel= ? ?RmKKP? ? ???? ? aRR KKK lP 11 ,? ?lBe RK ??1 dl(411) 式 410 及式 411 是 Markov 定位的理論基礎(chǔ)。根據(jù) 410 式， k 時(shí)刻機(jī)器人位于Rk 的狀態(tài)可信度的估計(jì)地計(jì)算可分為兩步：首先應(yīng)用動(dòng)作模型更新其可信度，然后再應(yīng)用傳感器模型進(jìn)行更新。 第二步 運(yùn)動(dòng)后的更新 當(dāng) k1 時(shí)刻機(jī)器人執(zhí)行動(dòng)作 a 時(shí)，應(yīng)用運(yùn)動(dòng)模型，得到 k時(shí)刻機(jī)器人位于Rk 的可信度為： ? ?RKBel =P( aRR KKK 11, ?? )= ? ?? ?? ?K KKK aRR lP 11 ,? ?lBel RK ??1 (413) 或 ? ?RKBel =P( aRR KKK 11, ?? )= ? ?? ?? ? aRR KKK lP 11 ,? ?lBe RK ??1 dl (414) 第三步 感知后的更新 當(dāng) k 時(shí)刻得到新的感知數(shù)據(jù)后，應(yīng)用感知模型，有 ? ?RKBel = ? ?Rm KKP? ? ?RKBel 1? (415) 在上述算法中， ? ?RBel0反映了有關(guān)其初始位置的信息。如果十分確信其初始位置，那么 ? ?RBel0