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