【文章內(nèi)容簡介】 tein等[15,16]分析指出通常的人工勢場法具有幾個(gè)明顯的缺點(diǎn)：1) APF方法有可能存在非期望的局部吸引點(diǎn)（當(dāng)目標(biāo)處為最小勢場值時(shí)，非期望的局部吸引點(diǎn)是非期望的最小值處；當(dāng)目標(biāo)處為最大勢場值時(shí)，非期望的局部吸引點(diǎn)是非期望的最大值處），使得機(jī)器人陷入到某個(gè)局部環(huán)境中，而不能到達(dá)目標(biāo)點(diǎn)。即APF方法不能保證路徑規(guī)劃的完整性。2) 在密集障礙物環(huán)境下，通常的APF方法容易會(huì)裁減掉比較狹窄的通道，破壞了路徑規(guī)劃的完整性。3) 在某些局部環(huán)境中探測到新障礙物后勢場可能發(fā)生振蕩。4) 狹窄通道中由于機(jī)器人傳感器探測范圍有限性，也會(huì)發(fā)生路徑振蕩。 調(diào)和函數(shù)勢場法在環(huán)境上用Laplace方程建模時(shí)，選擇合適的邊界條件可以保證方程的解，即調(diào)和函數(shù)(Harmoinc函數(shù)) [17]，所形成的勢場中所有非期望的局部吸引點(diǎn)約束在障礙物內(nèi)部，而自由位姿空間中只有目標(biāo)節(jié)點(diǎn)是唯一的局部吸引點(diǎn)。這樣，用調(diào)和函數(shù)解形成的勢場也可以進(jìn)行路徑規(guī)劃。相比普通的人工勢場法，調(diào)和函數(shù)法的最大優(yōu)點(diǎn)在于合適的邊界條件可以避免非期望局部吸引點(diǎn)的出現(xiàn)，保證了路徑規(guī)劃的完整性。調(diào)和函數(shù)路徑規(guī)劃方法便于進(jìn)行理論分析，但Koditschek[18]指出調(diào)和函數(shù)路徑規(guī)劃存在一個(gè)嚴(yán)重的缺點(diǎn)：通常任意形狀環(huán)境上的調(diào)和函數(shù)方程不存在代數(shù)解析解。這約束了必須通過數(shù)值方法對(duì)調(diào)和函數(shù)進(jìn)行數(shù)值求解。Zelek[19]則指出了調(diào)和函數(shù)路徑規(guī)劃中數(shù)值求解時(shí)存在地一個(gè)嚴(yán)重缺點(diǎn)：有效數(shù)字的快速衰減性，不能高解析度地表示大環(huán)境。因此已有的調(diào)和函數(shù)路徑規(guī)劃方法雖然在理論上有其完整性，但在實(shí)際應(yīng)用中是有限的。 回歸神經(jīng)網(wǎng)絡(luò)法（RNN）RNN（Recurrent Neural Network）是Hopfield神經(jīng)網(wǎng)絡(luò)的推廣，具有高度并行性和更豐富的動(dòng)力學(xué)性質(zhì)。RNN路徑規(guī)劃中每個(gè)神經(jīng)元和離散化環(huán)境節(jié)點(diǎn)相對(duì)應(yīng)，并且神經(jīng)元之間的局部連通關(guān)系表示環(huán)境的連通性，通過施加合適的外部激勵(lì)使RNN形成最速上升勢場[20,21,22]。由于研究者對(duì)RNN路徑規(guī)劃的出發(fā)點(diǎn)差異，目前對(duì)RNN路徑規(guī)劃尚且缺乏統(tǒng)一的名稱，這些名稱包括波前擴(kuò)散法的細(xì)胞自動(dòng)機(jī)路徑規(guī)劃[22]、波動(dòng)擴(kuò)散神經(jīng)網(wǎng)絡(luò)[21]（Wave Expansion networks,WENN）、Shunting Model神經(jīng)網(wǎng)絡(luò)[20]（SMNN）等。雖然方法名稱各有差異，但這些方法中每個(gè)處理單元都可看作一個(gè)動(dòng)態(tài)回歸神經(jīng)元，而每個(gè)神經(jīng)元都對(duì)周圍相鄰神經(jīng)元采樣并向傳播勢場。因此可統(tǒng)一稱為RNN路徑規(guī)劃。波前擴(kuò)散法用柵格將環(huán)境離散化表示后，采用細(xì)胞自動(dòng)機(jī)來表示柵格空間，通過波前擴(kuò)散法來建立勢場。波前擴(kuò)散法中從目標(biāo)節(jié)點(diǎn)出發(fā)的一束波沿著非障礙物細(xì)胞節(jié)點(diǎn)進(jìn)行運(yùn)動(dòng)，按每個(gè)細(xì)胞節(jié)點(diǎn)被擴(kuò)散到的先后順序進(jìn)行編號(hào)。當(dāng)機(jī)器人當(dāng)前位置對(duì)應(yīng)的細(xì)胞節(jié)點(diǎn)被波前擴(kuò)展到后，通過回溯獲得一條最短路徑。Kassim[21]的WENN路徑規(guī)劃神經(jīng)元模型比較接近于波前擴(kuò)散法的細(xì)胞模型，同樣采用波前擴(kuò)散機(jī)理來構(gòu)建勢場。Kassim提出采用WENN來構(gòu)建環(huán)境的Voronoi骨架圖來降低路徑規(guī)劃搜索空間。Kassim提出對(duì)環(huán)境中的障礙物進(jìn)行分割，然后每個(gè)障礙物分別傳出自己的波，進(jìn)行同步擴(kuò)散，當(dāng)多束波在某個(gè)柵格相遇時(shí)，表明該柵格一定在Voronoi圖上。但該方法僅適用于環(huán)境中障礙物都為凸型的情況。Glasius[23]構(gòu)建了一種連續(xù)狀態(tài)的RNN模型，由于該RNN中每個(gè)神經(jīng)元都具有波動(dòng)擴(kuò)散衰減性質(zhì)，因此也能形成最快上升路徑。但其模型是根據(jù)微分方程和差分方程近似變換關(guān)系求得的，每個(gè)神經(jīng)元的負(fù)反饋系數(shù)較小，故神經(jīng)元收斂速度慢，動(dòng)態(tài)特性較差。為此在Glasius模型基礎(chǔ)上，Yang[20]等受生物神經(jīng)元細(xì)胞模型出發(fā)，給出一種擴(kuò)展的RNN模型――SMNN來進(jìn)行路徑規(guī)劃，SMNN的神經(jīng)元模型具有更好的生物化學(xué)解釋機(jī)理，同時(shí)神經(jīng)元的負(fù)反饋系數(shù)可以調(diào)整，具有較快的收斂速度。第三章 基于線段關(guān)系的掃描匹配定位移動(dòng)機(jī)器人的自定位能力是實(shí)現(xiàn)自主導(dǎo)航的關(guān)鍵。在結(jié)構(gòu)化或半結(jié)構(gòu)化的環(huán)境里，如走廊、辦公室等，如果環(huán)境地圖已知，自定位主要采用基于掃描匹配[31,32,33,34,35,36,38]和基于概率論[35,37]兩類方法。根據(jù)對(duì)傳感器數(shù)據(jù)的再加工與否，掃描匹配又可以分為特征匹配[31,32,33,34,35,36]和原始數(shù)據(jù)匹配[38]?；趲缀翁卣鞯钠ヅ鋵ふ矣^測地圖和參考地圖的特征的對(duì)應(yīng)關(guān)系，能夠?qū)崿F(xiàn)迅速、高效、可靠的定位。APR [31]尋找的是兩個(gè)地圖中的定位點(diǎn)的對(duì)應(yīng)關(guān)系，它不受初始估計(jì)的影響； [32] and Xu Zezhong [33]根據(jù)拐角間的不變量對(duì)他們進(jìn)行匹配；Cox [34] and J. Gutmann [35] 將掃描數(shù)據(jù)直接跟地圖中的線段進(jìn)行匹配。如果不能探測到足夠的定位點(diǎn)，APR [31]很容易發(fā)生混淆。匹配拐角[32,33]對(duì)特征提取的要求很高，一旦有遮擋很容易丟失位置。原始數(shù)據(jù)匹配[34,35]因?yàn)樾枰?jīng)過多次迭代，計(jì)算量很大。本章提出了一種以線段關(guān)系（LSR，Line Segment Relationship）為特征的匹配方法。同APR[31]方法類似，也需要建立一個(gè)對(duì)應(yīng)關(guān)系矩陣來記錄地圖的對(duì)應(yīng)關(guān)系，有所不同的是，增加了更多的關(guān)系，比如角度、點(diǎn)到直線的距離等，而不僅僅是點(diǎn)到點(diǎn)的距離。這些被匹配的關(guān)系有不同的優(yōu)先級(jí)，只有在高優(yōu)先級(jí)的關(guān)系一致的情況下，才去比較低優(yōu)先級(jí)的關(guān)系。通過計(jì)算兩條線段的對(duì)應(yīng)程度，得出對(duì)應(yīng)性矩陣，從中搜索最佳匹配，估計(jì)機(jī)器人的位姿。對(duì)應(yīng)關(guān)系的最大值，即我們要找的最佳匹配用來計(jì)算機(jī)器人的位姿。因?yàn)殛P(guān)系產(chǎn)生于同一個(gè)地圖中，匹配的過程無需用到坐標(biāo)變換，將不受估計(jì)位姿的影響。它能夠在有遮擋的情況下成功地匹配，且計(jì)算量較小。下文介紹了作為特征的線段的定義，以及通過激光雷達(dá)獲取直線的方法，在此基礎(chǔ)上提出了以線段為特征的地圖掃描匹配方法，并根據(jù)匹配的結(jié)果定位，最后的實(shí)驗(yàn)對(duì)該方法進(jìn)行了檢驗(yàn)。 環(huán)境描述如前文所述，對(duì)環(huán)境的描述主要有兩種方法，幾何地圖和拓?fù)涞貓D。為了實(shí)圖31 地圖示例Fig. 31 Example of a metric map現(xiàn)機(jī)器人的自主定位，詳細(xì)表述了環(huán)境的幾何地圖要優(yōu)于拓?fù)涞貓D，而考慮到定位的精確度以及傳感器對(duì)信息的獲取，定位中多采用特征地圖，它以坐標(biāo)的方式記錄了環(huán)境中物體的信息，直觀而且很容易通過外部傳感器獲取。這里采用直線段來表示環(huán)境，直線段是墻壁、門等物體邊緣最普遍而且也最能反應(yīng)其形態(tài)的特征，能夠充分地顯示環(huán)境中物體的分布。為了唯一的表示地圖中的某一條線段，必須固定線段的起點(diǎn)和終點(diǎn)，這里定義線段為有向線段，形如，其中，為線段起點(diǎn)坐標(biāo)，為線段終點(diǎn)坐標(biāo)，線段的其它信息如斜率、傾角等可以根據(jù)起點(diǎn)終點(diǎn)計(jì)算得出。線段起點(diǎn)和終點(diǎn)的選取遵循端點(diǎn)分配規(guī)則：在機(jī)器人移動(dòng)的自由空間內(nèi)，以逆時(shí)針方向查找，所遇線段的首個(gè)端點(diǎn)即為線段的起點(diǎn)，另一個(gè)端點(diǎn)為線段終點(diǎn)。如在圖31中所示，機(jī)器人在走廊里行走，此時(shí)走廊是機(jī)器人移動(dòng)的自由空間，走廊的各段墻壁以線段的形式表示，則各條線段均定義為有向線段，依照端點(diǎn)選取規(guī)則設(shè)置起始點(diǎn)，如圖中所示。雖然可以很好地定義地圖的形式，但地圖獲取并不是一件容易的事。獲取地圖最簡單的方式是人工測量，然后通過AutoCAD或是文本文件的形式保存，在應(yīng)用時(shí)轉(zhuǎn)化為相應(yīng)的地圖表示。更為高級(jí)也更智能的方法是讓機(jī)器人自己探測地圖，而探測并生成地圖的過程也依賴精確的機(jī)器人自定位能力，這成為了一個(gè)矛盾。因此采用探測地圖的方法創(chuàng)建地圖較多地利用內(nèi)部傳感器如里程計(jì)等，前后地圖的觀測信息可以用來做一些校正。然而，內(nèi)部傳感器由于本身的構(gòu)造以及機(jī)器人移動(dòng)情況的復(fù)雜性，不可避免地存在誤差，雖然可以通過外部傳感器作一些修正，但仍然存在，且這種誤差會(huì)不斷積累，無法去除或減少，經(jīng)過較長的距離，誤差將會(huì)變得相當(dāng)大，嚴(yán)重影響了地圖的構(gòu)造，與真實(shí)情形不符。既然通過機(jī)器人自身創(chuàng)建的地圖存在較大誤差，不能用來準(zhǔn)確定位機(jī)器人，我們?nèi)圆捎檬止だL制地圖的方式，雖然比較費(fèi)事，但是能更好地適用于移動(dòng)機(jī)器人的定位與導(dǎo)航。更方便而且精確的地圖創(chuàng)建方式還有待進(jìn)一步研究。在我們的研究中，以文本的方式保存地圖，地圖中包含了在機(jī)器人所用傳感器探測平面上所有物體的邊緣信息，均轉(zhuǎn)化為直線段形式，用端點(diǎn)坐標(biāo)表示，坐標(biāo)成對(duì)出現(xiàn)，前一坐標(biāo)是線段在全局坐標(biāo)系中起點(diǎn)坐標(biāo)，后一坐標(biāo)是終點(diǎn)坐標(biāo)。 定位傳感器機(jī)器人技術(shù)的發(fā)展，越來越多的傳感器應(yīng)用在機(jī)器人上，使得機(jī)器人的功能不斷強(qiáng)大。應(yīng)用于定位的傳感器多種多樣，以里程計(jì)為代表的內(nèi)部傳感器，提供機(jī)器人的移動(dòng)變化量，雖然在長距離應(yīng)用中有很大的累積誤差，但是在其它很多定位方法中有很大的輔助作用，是絕大數(shù)機(jī)器人必備的傳感器之一。外部傳感器中，用得較多的一類是視覺傳感器，包括單目視覺、雙目視覺、全景視覺等，視覺的使用，可以方便地識(shí)別路標(biāo)以及跟蹤物體，但視覺最大的缺陷是不易獲取物體的深度信息，在單目視覺和全景視覺中用得較多的標(biāo)定方法和基于路標(biāo)的三角定位方法，其中三角定位的精度較高，雙目視覺雖然能夠通過圖像的匹配及之間的差異獲得深度信息，但是它的實(shí)現(xiàn)相當(dāng)困難；另一類常見的是距離傳感器，有紅外、聲納、激光等，它們的最大的優(yōu)點(diǎn)是易于獲得障礙的深度信息，但是在物體識(shí)別及跟蹤上難度較大，其中紅外、聲納因?yàn)榫容^差且方向性單一，在研究和應(yīng)用中越來越少，取而代之的是激光雷達(dá)，它有寬廣的視野和較高的精度，只是目前其成本較高、體積較大。在結(jié)構(gòu)化的環(huán)境中，最方便獲取而且能提供精確定位的信息就是深度信息，因此距離傳感器是我們的首選，為了使定位更加準(zhǔn)確，我們使用激光雷達(dá)。圖32 LRF工作原理圖Fig. 32 Principle of the working of LRF激光雷達(dá)或稱激光測距儀（Laser Range Finder, LRF），是一種通過測量激光傳播時(shí)間（TimeofFlight）的方法測量障礙物距離的設(shè)備。圖32是激光雷達(dá)的工作原理圖，激光束在固定時(shí)間從LRF中發(fā)射，經(jīng)過物體表面反射，由原路徑返回，被接收器接收。在激光束發(fā)射的同時(shí)，設(shè)置一個(gè)計(jì)數(shù)器并開始計(jì)數(shù)，當(dāng)激光束返回的時(shí)候，終止計(jì)數(shù)器計(jì)數(shù)，計(jì)數(shù)器數(shù)值的大小反映了激光傳播的距離。LRF內(nèi)部通過一個(gè)高速旋轉(zhuǎn)的鏡子改變激光束的方向，可以測量不同角度上障礙物的距離，因?yàn)榧す馐怨馑賯鞑ィハ嘀g不會(huì)有影響。LRF的數(shù)據(jù)因?yàn)槟Ｊ皆O(shè)置的不同有所差別，但基本類型相似，均為一系列的距離信息，所代表的實(shí)際距離根據(jù)所選測量范圍作相應(yīng)地變換，數(shù)據(jù)的數(shù)目(Sum)由角度視野和角度分辨率共同決定，Sum = Field / Resolution + 1。在LRF工作的每一個(gè)周期，LRF的數(shù)據(jù)均是由0o開始，以逆時(shí)針方向按角度分辨率增量給出，單一距離相應(yīng)的角度可以根據(jù)該數(shù)據(jù)在所有數(shù)據(jù)中所處的位置計(jì)算，因此，LRF無需傳輸每個(gè)距離的角度信息。以Range = 8m，F(xiàn)ield = 180o，Resolution = 1o為例，測量精度為1mm，障礙物的距離即由LRF數(shù)據(jù)1mm決定，每一個(gè)周期有181(180o/1o + 1)個(gè)距離數(shù)據(jù),其中第90個(gè)數(shù)據(jù)所在的角度為89o((901)1o)。 直線段提取LRF以逆時(shí)針方向進(jìn)行掃描，每間隔一個(gè)固定角度給出該角度上障礙物的距離，在某個(gè)角度上的距離可以轉(zhuǎn)化為以機(jī)器人為原點(diǎn)的坐標(biāo)系中的一個(gè)點(diǎn)。這樣，物體的表面將被表示成一系列連續(xù)的點(diǎn)，直線提取的任務(wù)就是將這些點(diǎn)還原成連續(xù)的表示物體邊緣的線段。 LRF數(shù)據(jù)點(diǎn)分段在提取線段之前，為了去除LRF本身或者光線干擾等對(duì)LRF數(shù)據(jù)的影響，也為了保證提取出來的線段來源于同一個(gè)物體，需要首先將LRF的數(shù)據(jù)進(jìn)行分段。做法：設(shè)定一個(gè)閾值（可根據(jù)半徑作修改），依次比較相鄰點(diǎn)的距離，如果兩點(diǎn)間距離小于該閾值，則認(rèn)為此兩點(diǎn)源于同一物體，將它們放置于同一段中；否則，這兩點(diǎn)不是來自于同一物體，由LRF探測以及數(shù)據(jù)發(fā)送的連續(xù)性可知，前一段在這兩點(diǎn)中前一點(diǎn)處終止，后一點(diǎn)為下一段的起點(diǎn)，另起一段。經(jīng)過分段處理后，數(shù)據(jù)點(diǎn)被分成以段為單位的好多組，但不是所有的段都能用來提取線段。一些段中數(shù)據(jù)點(diǎn)很少，可能只有一個(gè)或者兩個(gè)，一些段中數(shù)據(jù)點(diǎn)很密集，在幾厘米的范圍內(nèi)有十多個(gè)點(diǎn)，這些都是不合格的段，很可能是一些干擾，也可能來自于細(xì)小的物體，不能作為提供有效信息的線段，在提取線段之前需要剔除。線段提取只在各自段中進(jìn)行，與外段中點(diǎn)無關(guān)，即使處于同一條直線上也不會(huì)影響。圖33 序貫計(jì)算的示例[39]Fig. 33 Example of sequence detecting 直線擬合考慮LRF數(shù)據(jù)點(diǎn)的連續(xù)性，選用一種序貫判定的線段提取的方法[39]：從第一個(gè)點(diǎn)開始，依次檢查每一個(gè)點(diǎn)，根據(jù)已有的點(diǎn)構(gòu)造一些參數(shù)，作為后繼點(diǎn)的判定條件；若當(dāng)前點(diǎn)滿足判定準(zhǔn)則，則用此點(diǎn)修正參數(shù)，再作為后繼的判定依據(jù)；依此類推，直到找出連結(jié)直線上所有的點(diǎn)。如圖33，具體的算法如下：算法1 直線段擬合算法a. 設(shè)擬合精度。b. 初始點(diǎn)為，置參數(shù)值。c. 依次對(duì)每個(gè)后繼點(diǎn)，計(jì)算：，并執(zhí)行以下操作。d. 若或，此線段結(jié)束，退出。e. 計(jì)算參數(shù)：。f. 修正參數(shù)：。g. 轉(zhuǎn)到b，考察后繼點(diǎn)。此為一條線段的擬合方法，當(dāng)該條線段結(jié)束退出后，以后續(xù)點(diǎn)為新的起始點(diǎn)重新擬合下一條線段，直到所有的數(shù)據(jù)點(diǎn)都處理完畢。 直線斜率計(jì)算提取后的有向線段表示為：，其中，、分別為線段起點(diǎn)和終點(diǎn)，可以看到因?yàn)長RF數(shù)據(jù)點(diǎn)是以逆時(shí)針方向給出，其起始點(diǎn)的確定與規(guī)則一致。稍有不同的是，線段的斜率和傾角不再由起點(diǎn)和終點(diǎn)簡單計(jì)算決定，起點(diǎn)和終點(diǎn)的確定存在誤差，甚至要大于線段內(nèi)部的數(shù)據(jù)點(diǎn)。分段最佳斜率平均值法[40]是在實(shí)驗(yàn)數(shù)據(jù)處理中用得較多的一種直線斜率計(jì)算方法，在與其它一些方法的比較中，被證明具有更高的精度。分段最佳斜率平均值法最初用于實(shí)驗(yàn)數(shù)據(jù)處理，基于點(diǎn)間某一坐標(biāo)方向上等距的原則，從整體上看LRF數(shù)據(jù)達(dá)不到這樣的要求，但是任意相鄰兩個(gè)距離可以近似認(rèn)為是相等的，分段最佳斜率平均值法仍然適用。圖34 最佳三角擬合狀態(tài)Fig. 34 State of optimum triangle imitating圖35分段最佳斜率平均法原理圖 Principle of segment optimum slope average method