移動機器人環(huán)境地圖實時構(gòu)建算法系統(tǒng)(最新)13頁

1、西北工業(yè)大學(xué)2010年大學(xué)生創(chuàng)新性實驗計劃項目申 請 書項目名稱 移動機器人環(huán)境地圖實時構(gòu)建算法系統(tǒng) 所在學(xué)院/基地 舞蹈機器人基地 申 請 人 嚴家祺 羅國佳 秦博奇 詹東昀 導(dǎo)師姓名 黃英亮 聯(lián)系電話E-mail: luogj8904 填表日期 2010年9月13日 西北工業(yè)大學(xué)教務(wù)處制表項目名稱移動機器人環(huán)境地圖實時構(gòu)建算法系統(tǒng)起止時間2010年9月至2011年9月申請經(jīng)費20000申請人或申請團隊學(xué) 號姓 名年級所在學(xué)院、專業(yè)聯(lián)系電話E-mail2007301716嚴家祺07級電子信息學(xué)院電子信息工程137599426572292885032008302577

2、羅國佳08級計算機學(xué)院計算機科學(xué)與技uogj89042008302578秦博奇08級計算機學(xué)院計算機科學(xué)與技inboqi01162008302604詹東昀08級計算機學(xué)院計算機科學(xué)與技han89616導(dǎo)師姓 名黃英亮學(xué)院機電學(xué)院職務(wù)/職稱高級講師E-mailhuangyl電 、申請立項依據(jù)（包括項目背景、項目來源、技術(shù)依據(jù)、前期已有的研究基礎(chǔ)，自身具備的知識條件、自己的興趣愛好、特長等）項目背景、來源： 現(xiàn)代社會當(dāng)中，火災(zāi)、爆炸、坍塌等事故多發(fā)，在救援過程中因災(zāi)難現(xiàn)場情況不清，意外坍塌事故等

3、導(dǎo)致救援人員遇難的慘劇時有發(fā)生。為避免此類事故，應(yīng)用救援機器人首先進入現(xiàn)場及時探知險情和受困人員的位置和狀況，有著極大的應(yīng)用意義。因此，在每年的Robocup國際機器人賽事中，Robocup救援組是最熱門項目之一，其主要目的就是促進大規(guī)模災(zāi)難情況下使用機器人進行人員搜救任務(wù)的研究。災(zāi)難現(xiàn)場實時環(huán)境地圖的創(chuàng)建是移動救援機器人領(lǐng)域中的一個基本而重要的問題。環(huán)境地圖被廣泛地應(yīng)用在移動機器人的導(dǎo)航系統(tǒng)中，在移動機器人導(dǎo)航定位和全局路徑規(guī)劃中起到重要作用。要實現(xiàn)移動機器人的自主導(dǎo)航，最重要的是通過定位來獲知機器人在環(huán)境中的準確位姿。根據(jù)先驗地圖進行的移動機器人定位和自主導(dǎo)航技術(shù)得到了廣泛的研究，并取得很

4、好的應(yīng)用效果。但是實際環(huán)境往往是未知的，不能提供諸如環(huán)境中障礙物大小、形狀、位置等先驗信息，而且實際突發(fā)災(zāi)難事件環(huán)境中也不存在路徑、燈塔等人為設(shè)定的標志物，這給移動機器人的自主導(dǎo)航帶來了很大的問題。因此，移動機器人在未知環(huán)境中同時精確定位和地圖創(chuàng)建（SLAM simultaneous localization and mapping）成為移動機器人研究領(lǐng)域的一個亟待解決的問題。自然而然，地圖的構(gòu)建質(zhì)量也就成為每年Robocup救援組比賽項目的一個重要評分依據(jù)。技術(shù)依據(jù)：本項目采用幾何特征地圖來反映機器人所處外部環(huán)境，如災(zāi)難現(xiàn)場中的墻壁、較大的家具等。幾何特征地圖是一種緊湊的地圖表示方法，通過傳

5、感器感知環(huán)境數(shù)據(jù)，從中提取抽象幾何特征如線段、圓、弧線等來表示環(huán)境信息。對于大多數(shù)環(huán)境特別是室內(nèi)環(huán)境利用幾何特征描述的地圖都能精確的反映環(huán)境信息，而且?guī)缀翁卣鞯貓D存儲信息量小，方便應(yīng)用于位姿估計和目標識別。前期已有的研究基礎(chǔ)：本項目擬通過激光測距儀掃描采集外部環(huán)境數(shù)據(jù)，并設(shè)一套高效的算法處理所得數(shù)據(jù)來實時創(chuàng)建并更新現(xiàn)場環(huán)境地圖。舞蹈機器人基地目前已具備救援機器人的機械和電子部件，曾經(jīng)采取過的構(gòu)建地圖的方法主要是依靠超聲波傳感器、電子羅盤、加速度傳感器等多傳感器的信息融合，來構(gòu)建幾何特征地圖。但由于這個方法結(jié)構(gòu)復(fù)雜，受多個傳感器的影響，系統(tǒng)的精度一般不高，而且系統(tǒng)抗電磁干擾能力太差，往往得不出理

6、想的地圖構(gòu)建效果。而本項目采取的方法只需要一個激光傳感器采取數(shù)據(jù)，通過算法處理優(yōu)化，完全可以替代以上多傳感器的融合，大大簡化了系統(tǒng)的復(fù)雜性，提高了系統(tǒng)的可靠性與穩(wěn)定性，減小了系統(tǒng)誤差。自身具備的知識條件：本項目的項目組人員都是西北工業(yè)大學(xué)舞蹈機器人基地的成員，在過去的實踐中，對傳感器的操作與傳感器的應(yīng)用都有一定的了解。本項目的人員由電子信息專業(yè)和計算機專業(yè)的學(xué)生組成，首先可以解決底層硬件通信的問題，而上層數(shù)據(jù)處理算法則由計算機專業(yè)的成員完成，我們在計算方法、計算機圖形學(xué)、算法設(shè)計與分析、信號處理等學(xué)科上有扎實的基礎(chǔ)，因此可以勝任信息采取與算法設(shè)計的工作。自己的興趣愛好、特長： 本項目組的人員都

7、是舞蹈機器人基地里的核心人員，動手能力強，善于思考，對MFC繪圖、算法的設(shè)計、傳感器網(wǎng)絡(luò)通信等都有過經(jīng)驗。二、立項研究的目的和意義環(huán)境地圖是移動機器人自主完成任務(wù)的首要條件，未知環(huán)境中移動機器人同時定位和地圖創(chuàng)建對于智能機器人技術(shù)的發(fā)展有著重要的意義。本項目預(yù)設(shè)計并實現(xiàn)一個簡單而有效的系統(tǒng)，該系統(tǒng)能快速、準確地構(gòu)建出現(xiàn)場環(huán)境的幾何特征地圖。由于只采用激光測距儀采集數(shù)據(jù)，相比多傳感器融合系統(tǒng)而言，大大降低了多傳感器導(dǎo)致的系統(tǒng)誤差，且激光測距儀采集數(shù)據(jù)精度高，抗外部干擾能力強，更適合于災(zāi)難現(xiàn)場的復(fù)雜環(huán)境。后期數(shù)據(jù)處理及地圖生成采用軟件實現(xiàn)，相對硬件實現(xiàn)更易于改進和優(yōu)化。幾何特征地圖意義重大：第一：

8、對災(zāi)難現(xiàn)場實現(xiàn)地圖重現(xiàn)，可以有助于救援人員開展救援工作，提前預(yù)知現(xiàn)場環(huán)境，避免再次意外對救援人員的傷害。也有利于及時調(diào)度救援人員，最大限度的救出受困人員，具有很大的社會意義； 第二：環(huán)境地圖是智能移動機器人自主行走、自動避障、自主識別救援目標的技術(shù)基礎(chǔ)和重要保障，促進了智能移動機器人的發(fā)展。三、項目計劃實施研究內(nèi)容第一：對激光傳感器的特性以及參數(shù)的研究，保證采集到的環(huán)境數(shù)據(jù)的精確度和數(shù)據(jù)傳輸?shù)臏蚀_性，深入了解激光傳感器的原理，還可以利用其特性簡化日后數(shù)據(jù)處理的工作。第二：對算法中涉及到的激光掃描頻率、掃描范圍、動態(tài)閾值等一些參數(shù)的設(shè)計作預(yù)估，建立數(shù)學(xué)模型分析，得出一個精度較高的模型。第三：結(jié)合

9、傳感器的實際數(shù)據(jù)，進一步驗證模型的精確程序，根據(jù)實際數(shù)據(jù)對模型進行優(yōu)化，選擇最適合的算法參數(shù)。第四：搭建災(zāi)難現(xiàn)場摸擬環(huán)境，對系統(tǒng)進行大量的試驗，不斷改進和優(yōu)化算法方案。第五：編寫高效的作畫程序，能快速、精確繪出現(xiàn)場的幾何特征地圖。四、國內(nèi)外研究概況掃描匹配方法是環(huán)境地圖創(chuàng)建的一種有效的方法，可分為迭代匹配算法和非迭代匹配算法。迭代最近點（ICP）算法是一種典型的迭代匹配算法。ICP算法通過在迭代過程中不斷降低配準誤差，獲得兩組點集間相對位姿變化。該算法的缺點是匹配收斂速度慢而且容易陷入局部最優(yōu)解。此后，出現(xiàn)了許多基于ICP算法的改進算法。直方圖匹配算法是典型的非迭代匹配算法，該算法的最大優(yōu)點是

10、算法容易實現(xiàn)，匹配速度快，但是受構(gòu)建特征直方圖時分辨率選取的影響，匹配精度很難得到有效的提高?？傮w而言，迭代匹配算法匹配精度高，但匹配收斂速度較慢，很難完成實時條件下環(huán)境地圖的創(chuàng)建；非迭代匹配算法的匹配速度優(yōu)于迭代匹配算法，但是匹配精度不高。五、研究方法、技術(shù)路線及研究中面臨的技術(shù)難點和擬采取的解決辦法 本項目利用激光測距儀測得環(huán)境數(shù)據(jù)，從中提取出特征點對，采用非迭代的方式，在誤差函數(shù)的解空間里采用聚類的方法完成點對的匹配，進而完成環(huán)境地圖的創(chuàng)建。1、 特征點對的提取：激光傳感器在i時刻掃描得到描述環(huán)境信息的點集uki，對uki中的數(shù)據(jù)進行特征點對的提取，特征點對是描述現(xiàn)場環(huán)境的多變形的線段的

11、起點和終點，如圖1所示。 (a)激光數(shù)據(jù)點集 (b)特征點對集 圖1 提取特征信息效果2、 特征點對集的匹配：特征點對集的匹配基于以下兩個假設(shè)：一是環(huán)境中的特征點之間具有拓撲結(jié)構(gòu)穩(wěn)定性，即兩個特征點之間的歐式距離在相鄰兩組數(shù)據(jù)中是相等的，在靜態(tài)環(huán)境中這一假設(shè)一般能夠滿足；二是在二維平面內(nèi)，相鄰兩組特征點集之間的變換可以視為剛體變換，可由兩組特征點對集中的對應(yīng)匹配點對之間的變換來表示，這樣可以提高算法效率，降低計算復(fù)雜度。匹配算法可以概括為匹配、計算、聚類三個步驟。I 匹配是指在兩組特征點對集中選出所有歐式距離相近的對應(yīng)特征點對，構(gòu)成對應(yīng)特征點對集合。II 計算是針對每對對應(yīng)特征點對，求得相應(yīng)的

12、旋轉(zhuǎn)角Ri和位移Ti，加入到三維向量解空間 (,)中。III 一般情況下，對于配對過程中錯誤的特征點對，即相對應(yīng)的特征點不是環(huán)境中的同一個特征點，用這些特征點對求得的變換參數(shù)(,)在空間中是隨機分布的；而對于配對過程中正確的特征點對，求得的變換參數(shù)(,)在理論上是相等的，即對應(yīng)于空間中的同一點。但由于測量誤差和計算誤差的影響，這些變換參數(shù)不會完全相等，即對應(yīng)于空間中的不是某一點，而是由許多點構(gòu)成的密集點簇。顯然，以點簇中點作為最優(yōu)變換參數(shù)是比較合理的。在空間中對所有求得的變換參數(shù)(,)，采用適當(dāng)?shù)拈撝颠M行聚類，選出元素個數(shù)最多的類，將此類的中心作為最優(yōu)變換參數(shù)，從而完成兩組點集的匹配。整個過程

13、主要分為特征點的提取和特征點集的匹配兩個步驟，算法框圖如2所示。特征點對之間兩兩成對匹配，得到解空間特征點對提取點集uki對解空間內(nèi)所有的解元素進行聚類，求得最優(yōu)旋轉(zhuǎn)角R與最優(yōu)位移T特征點對提取點集uki+1uki =uki+1進行點集變換uki+1=R x uki+1+T 圖2 算法流程圖技術(shù)路線：一、特征點對的提取（區(qū)域分割線段端點（特征點對）提?。?、把激光測距儀一個掃描周期內(nèi)采集到的離散點按照連續(xù)兩點間的歐式距離大小是否超過某一閾值分成彼此不連通的區(qū)域。假設(shè)采集到N個點，那么首先認為是一個區(qū)域，即。按照下列公式計算連續(xù)兩個點之間的距離 其中i=1,2,N判斷Di和閾值的關(guān)系，如果Di

14、大于閾值（動態(tài)設(shè)定），則認為（Xi，Yi）是兩個區(qū)域的分割點，以這個點為分割點將區(qū)域分成兩部分，可以得到區(qū)域，。按照同樣的原則對區(qū)域A2進行分割，得到區(qū)域A2,A3。依此類推，最后可以得到相互不連通的區(qū)域（A1,A2,AN）。判斷每個區(qū)域內(nèi)的數(shù)據(jù)點的個數(shù)，如果某個區(qū)域包含數(shù)據(jù)點的個數(shù)小于等于3個，那么該區(qū)域被視為噪聲區(qū)域，舍棄這些噪聲點。在每個區(qū)域Ai中，以區(qū)域Ai的第一個點Ps（Xs，Ys）和最后一個點Pe（Xe，Ye）作一條直線L，計算區(qū)域內(nèi)其余各點到這條直線L的距離，假設(shè)在點Pm（Xm，Ym）處取得距離的最大值Dmax，如果距離最大值大于閾值Dthr，以點Pm為分割點將區(qū)域Ai分成兩部分

15、，。然后對區(qū)域A和A采用同樣的方法進行迭代處理，直到該區(qū)域內(nèi)所有點到所在區(qū)域起點終點構(gòu)成直線的距離的最大值不大于閾值Dthr，這樣這個區(qū)域就被分為M個可以用一條線段線性表示的點集Li（i=1,2,M）。如圖3所示。 圖3 特征點提取效果圖對A1,A2,AN進行上述操作，使得每個區(qū)域由若干個點集組成，每個點集里的所有點都依附于一條直線。則從每個點集提取第一個點和最后一個點（可優(yōu)化提?。?，形成點對，代表線段的起點和終點。這些點對中的點就是多邊形的端點或角點，即我們想得到的特征點。 二、特征點對匹配已經(jīng)提取出了局部地圖的所有特征點對，即，計算出各點對的歐式距離，即。將與上一次的局部地圖（現(xiàn)已并入全局

16、地圖）的所有特征點對計算出的歐式距離進行匹配。找出閾值范圍內(nèi)歐式距離近似相等的點對。計算出每個相匹配點對之間的變換旋轉(zhuǎn)角Rk和變換位移Tk，（km,n），加入到三維向量解空間 (,)中。三、對解空間進行聚類 以中的第一個元素作為初始類和類的中心，類的個數(shù)采取動態(tài)設(shè)置閾值，動態(tài)設(shè)定的方式如下確定：如果一個元素到任何一個類的中心的距離都大于某一閾值，則將此元素構(gòu)成一個新的類。最后找出所含元素個數(shù)最多的類，該類的中心，即為所求的最優(yōu)變換參數(shù)。 技術(shù)難點：1、 準確提取局部地圖的特征點是正確匹配的關(guān)鍵，但是受原始數(shù)據(jù)精度和閾值參數(shù)選取的影響，一些情況下也會出現(xiàn)線段提取不當(dāng)或者分割太細的情況（如圖4）。

17、 圖4實際可以用三條線段來表示的區(qū)域被錯誤的分成了四條線段。因此可在當(dāng)前基礎(chǔ)上，將線段提取分為兩個步驟完成。選按照原來的方法進行分割，然后利用最小二乘線段擬合算法，得到線段參數(shù)，然后計算任意相鄰兩條線段L1和L2之間的夾角和相鄰兩條線段端點的最小值。如果滿足條件 且那么假設(shè)認為這兩條線段是被錯誤分開的線段，應(yīng)該為同一條線段，直接取前一條線段的起點和后一條線段的終點作為特征點對加入到特征點對集合當(dāng)中。 2、 局部地圖和全局地圖需要比較多的相匹配的特征點對，這樣才能提高匹配精度。然而在實際環(huán)境中，由于激光傳感器掃描范圍有限、離障礙物過近或位姿變化過大等情況，導(dǎo)致局部地圖和全局地圖中符合匹配條件的點

18、對過少。解決辦法是通過大量的實驗，確定一套符合該算法系統(tǒng)的閾值方案以及較合適的激光傳感器的掃描頻率、范圍等。 六、進度安排（選題、自主設(shè)計實驗、實驗研究、數(shù)據(jù)處理、研制開發(fā)、撰寫總結(jié)報告、項目鑒定、成果推廣或論文發(fā)表等）內(nèi)容時間段選 題2010年7月算法系統(tǒng)規(guī)劃與設(shè)計2010年7月至2010年9月結(jié)合傳感器參數(shù)進一步優(yōu)化和完善算法結(jié)構(gòu)2010年9月根據(jù)算法的描述設(shè)計數(shù)據(jù)結(jié)構(gòu)與類2010年9月至2010年10月算法的程序?qū)崿F(xiàn)及各模塊的測試2010年11月至2011年4月對于算法實現(xiàn)上的進行速度優(yōu)化2011年4月至2011年5月開展大量的實驗及現(xiàn)場模擬2011年5月至2011年8月完善細節(jié)，發(fā)表論文2010年8月至2011年9月七、擬利用資源（開展研究工作所需要的實驗室、創(chuàng)新競賽基地、主要儀器設(shè)備、試劑、參考資料及其他工作條件等）實驗室：西北工業(yè)大學(xué)舞蹈機器人基地 傳感器： URG-04LX激光測距儀 測試平臺： 救援機器人八、經(jīng)費使用計劃 經(jīng)費支出項目名稱具體支出內(nèi)容金 額（千元）使用時間URG