1.3　國內外路徑規劃技術的研究現狀

1.3.1　環境建模技術研究進展

水下鈷結殼機器人屬于自主式機器人的一種。近年來，有關自主車輛導航研究越來越多，多數集中在室內或者結構化的環境中，環境建模相對簡單。國內外有關室外的環境建模研究主要集中在無人駕駛車輛和星球車輛（月球車、火星車等）上。

利用外部環境的三維地形信息，評估地形的可通行性，判別不可通行區域是自主車導航的核心問題之一，也是機器人環境建模的核心內容。因此，通過對運用于Rocky7上的路徑規劃方法進行總結，S.L.Laubach[38]提到：地形的通行性問題是未來路徑規劃的關鍵，即規劃車體的運動路徑應該更好地結合地形信息。

目前地形通行性方面的研究主要集中在運用人工智能的統計學和模糊方法分析地形物理信息，國際上卡耐基梅隆大學（CMU）與美國噴氣動力試驗室（JPL）的研究者分別提出了環境建模的兩種解決方案。

CMU的方法是沿著候選路徑計算地形通行性，候選路徑根據車體舵輪的轉向角度生成。通行性指數通過路徑上單個柵格的相關權值的累加而得到。R.Simmons[39]、S.Singh[40]使用的相關參數是橫滾角（roll）、俯仰角（pitch）和粗糙度（roughness）。首先將地形分成小塊區域，然后利用最小二乘法將區域擬合到一個平面上，俯仰角和橫滾角的計算是通過此平面的兩種角度來表示該區域的俯仰角和橫滾角，擬合平面和實際區域表面的殘差表示粗糙度。

JPL中比較有代表性的方法是基于語言描述和模糊邏輯的方法。H.Seraji[41，42]將地形柔軟度、坡度、地形粗糙度等地表信息通過語言描述進行模糊分類，之后計算地形通行性指數，最后通過地形的通行性指數（代表不同地形中機器人的通行能力）指導機器人路徑規劃。通行性指數依據傳感器測量范圍的不同分為區域、局部和全局指數。區域通行性指數是通過地形粗糙度和坡度（slope）進行模糊分類而得到；局部通行性指數是由對地形表面柔軟度（surface softness）和局部障礙物進行模糊分類而得到。如圖1-5是H.Seraji獲得的火星環境通行性地圖，圖中不同顏色代表區域的不同通行性。

此外，還有一些基于地形參數的通行性計算方法，如A.Shirkhodaie[43]通過紋理設計，神經網絡分類器、規則分類器和模糊分類器分辨地形的種類并確定其可通行性。D.Gennery[44]使用平滑插值方法計算高度、坡度（smoothed and interpolated height），得到地形的通行性指數。

在國內，徐璐[45]提出一種基于障礙物分類的通行性計算方法，首先計算出障礙物的高度變化，面積等信息，然后對障礙物進行二次分類，分離出可以克服的障礙（可越過的溝和可攀越的土丘等），得到著色障礙分類圖。在以上過程的同時將地形柵格化，計算每一柵格的平均坡度等參數，得到通行性指數，作為機器人三維路徑規劃的評價函數。

史美萍[46]提出了一種新的多約束環境建模方法——MCWM方法，它綜合考慮了運動的平穩性、系統的不確定性、人機協同性和月面地形的可通行性等四個因素，最后產生支持路徑規劃的綜合代價地圖——MCWM模型（圖1-6），達到了地表通行性的合理和魯棒性建模。

劉華軍[47]提出了越野高程地形的相對不變性概念，并利用越野地形的這種性質，提取出了在地形具有的相對不變特征，如地形粗糙度等，利用基于模糊規則的方法，評估各特征對地形的可通行性。最后通過自主車越野導航實驗表明算法能滿足自主車越野導航的需要，穩定有效。

但總的來說，以上通過通行性研究確立環境建模的方法，適合于在環境中尋找通行性最優的行走路徑，而機器人則需要對全礦區的遍歷式采集；而且以上方法并沒有針對性的考慮環境中不同底質對地形通行性的影響，對于采礦區這種含有三種不同類型底質的特殊環境，不能直接應用。因此，本書提出了針對水下不同底質進行環境建模的方法。

1.3.2　遍歷路徑規劃技術的研究進展

關于機器人遍歷（覆蓋）路徑規劃問題，Sylvia[48]認為，覆蓋是機器人必須遍訪工作環境中的可達表面。Zheng[49]定義已知環境信息情況下機器人覆蓋問題為：遍訪已知環境的所有位置，同時完成某項任務。Enrique等[50]認為，覆蓋路徑必須盡可能短，重復路徑盡可能避免；覆蓋問題轉化為兩個子問題：首先是尋找能遍歷簡單區域的運動方式，其次是尋找一條連接區域的可靠途徑，用來保證全區域覆蓋。

在國外，關于覆蓋算法，Howie[51]首先研究基于生成樹的機器人覆蓋算法，文獻[52]對算法本身作了較詳細的總結。而覆蓋算法在水下機器人上的應用方面，文獻[53]采用水下機器人覆蓋技術對水下進行地形測繪。但現有的覆蓋技術大部分局限于二維環境中，僅Ercan等在文獻[54]中提到簡單三維物件表面的覆蓋問題，絕大多數覆蓋問題尚未涉及三維地形的覆蓋。

Grossberg[55]根據生物學家Huxley和Hodgkin提出的描述細胞膜的動力學模型（H-H模型）和神經細胞膜的電路模型[56]，提出了神經動力學網絡模型。Yang和Meng又將這種基于生物激勵的神經網絡應用到機器人的環境建模和遍歷路徑規劃[57]。將區域劃分成的柵格作為一個神經元，通過生物激勵神經網絡模型中的動力學激勵公式確定柵格的激勵值大小。這種方法考慮轉彎最少，遍歷最短的路徑，能避開障礙物和跳出死角，達到了完全遍歷，不足是重復率較高。通過啟發式模板和生物激勵結合的方法能夠得到較好的改善性能指標。

Carvalho[58]等人在已知環境地圖的前提下，在真實機器人平臺上進行了基于行為模板的遍歷路徑規劃研究，把機器人行為劃分成多種固定的模板，依據實際位置選擇適合模板，最后實現規劃路徑的遍歷。該方法需要預先獲知環境地圖，通過讓機器人首先沿著區域邊界行走完成對環境地圖的總體構建，然后再根據實時環境信息依靠合適模板進行啟發式行走，缺點是此法的實現較困難。

Quine和McCluskey提出Q-M法，該方法開始是用于電路上尋找最大素蘊含的方法。該方法通過提取給定環境中所有基本矩形自由區域，并用這些自由區域作為節點構造連通圖，完成對區域的覆蓋。

在國內研究中，Qiu等[59]提出了利用生物激勵神經網絡對環境進行建模，計算環境信息，并采用滾動規劃技術和啟發式搜索算法進行路徑規劃。

蔡自興[60]認為，機器人覆蓋就是利用移動機器人，遍歷目標環境區，盡可能地滿足重復路徑少、時間短和未遍歷區域小的優化目標。

李開生[61]首先提出遍歷規劃的數學描述和概念，包括全遍歷規劃的設計方法，設計了常用的幾個性能評價函數；并且在此基礎上，給出了基本遍歷運動序列的全遍歷規劃器，該規劃器是基于綜合性能評價指標的。

張赤斌[62]采用全局運動規劃和局部區域遍歷相結合的方法。該方法首先定義了遍歷空間中子區域間的綜合連通距離，再由一個完全賦權連通矩陣表示整個遍歷空間中的連通關系。采用群智能算法優化子空間遍歷距離，得到最短全局遍歷順序，證明了算法的有效性。

謝斌[63]提出了基于改進的Node Counting在線圖搜索方法。算法通過擴大遍歷時的局部搜索空間，使移動機器人工作空間的搜索加快。設計仿真系統主要模塊，并編制相應的仿真程序。該算法具有良好的遍歷性能，同時在機器人被“綁架”或信息素被破壞的情況下，算法仍具有較好的魯棒性。

邱雪娜[64，65]提出了改進的生物激勵神經網絡法（圖1-7）。該方法集成了模板模型，啟發式搜索和障礙物逼近算法；移動機器人的工作環境建模使用“分流合作—競爭反饋”網絡的生物激勵神經網絡；能夠實現不規則形狀障礙物周邊區域的遍歷。

在我國鈷結殼調查區內主要分布的是相對平坦地形，機器人的遍歷路徑設計，是在滿足最大覆蓋率、最小重復率和最小消耗的前提下，一種綜合的優化設計。在采礦遍歷路徑規劃中，針對平坦地形環境，設計綜合評價準則，并以此指導遍歷路徑規劃，是本書研究的特點。

1.3.3　全局靜態規劃技術的研究進展

靜態路徑規劃是在全局環境信息已知的情況下，機器人按照某種優化準則，在環境中從一點行走到的另一點的可行通路。

在國外研究方面，S.M.LaValle提出快速隨機搜索樹算法[66]（RRT）算法，該算法是一種增量式前向搜索算法。搜索樹構造階段，從初始位姿點出發構造搜索樹，在位姿空間中隨機選擇一個位姿點，遍歷搜索樹，找到距離最近的節點，后在控制輸入集里選擇一個控制輸入作用在該節點上，機器人沿著節點間連線，依照狀態轉換方程產生滿足約束的候選路徑集，到達一個新狀態集，依據節點間距離，選擇距離最近的控制輸入作為最佳控制輸入。并且依次產生新狀態，直到到達目標狀態，完成搜索樹構造。算法從目標狀態點出發，找尋父節點，直至到達狀態起始點，就規劃出滿足全局約束的路徑。

Barraquand和Latombe設計了隨機路徑規劃算法[67]（RPP）。該算法以人工勢場法為基礎，通過執行隨機步驟使其脫離局部極值。RPP定義啟發式勢函數和三種模式：DESCEND，ESCAPE和BACKTRACK。初始時刻，規劃器在DESCEND模式下，從起始節點開始依照梯度下降的原則產生新的節點。在該節點鄰域內，且使得勢函數最小方向上產生一個新節點。如果陷入局部極值，規劃器轉入ESCAPE模式，執行一個隨機步驟創建新節點。如果在ESCAPE模式中，隨機產生新節點失敗，規劃器轉入BACKTRACK模式。在此模式下，從上次產生的新節點起始節點間隨機選擇一個節點，從而完成完整路徑規劃。

Orlin.J[68]應用經典最短路徑搜索算法Dijkstra算法解決靜態路徑規劃問題。該算法可在顯式圖中找到從目標節點到圖中任意節點的最短路徑，或從起始節點到任意節點的最短路徑。若該算法在到達目標節點時結束，那么一定可以找到一條從起始節點到目標節點的最短路徑。算法復雜度是O（n2）。

Papadatos.A[69]解決靜態路徑規劃問題時使用A*算法，該算法是一種隱式圖啟發式搜索算法，其距離函數的定義具有啟發性。其距離函數的定義為f（c）=g（c）+h（c），即某個節點c處的距離f（c）定義為從起點至c的距離g（c），與從c到目標點距離的估計h（c）之和。啟發式估計是真實路徑費用的下界，只要h（c）存在，A*算法一定可以得到一條最優路徑。

Stentz發展了D*算法[70]，D*算法還可在動態圖上搜索到最短路徑。該算法能夠在搜索動態圖目標節點的過程中處理變弧的代價，假設弧的代價在遇到障礙時可能會發生變化。D*在靜態圖中的搜索情況將轉化為Dijkstra算法，時間復雜度為O（n2）。D*算法代價參數可以隨搜索過程改變的情況下，它可以處理任意的路徑優化問題；當參數的變更發生在起始點附近時，算法效率最高。

而在國內，張鈸[71]提出用狀態空間的連通性分析解決路徑規劃問題，它根據環境和機器人的幾何特點，將空間劃分成若干拓撲一致的子區域，根據彼此的連通性建立拓撲網，在圖中搜索一條拓撲路徑。這種方法的優點是利用拓撲特征縮小了搜索空間，算法復雜性僅依賴于障礙物數目，理論上是完備的。

吳峰光[72]采用移動線和掃描線相結合的方法構造切線圖。采用移動線算法檢測障礙物頂點之間的公切線，然后利用掃描線算法測試公切線與障礙物之間交叉點的存在性，如果存在，則濾除這些公切線，那么剩下的公切線構成的圖被稱為切線圖。構造切線圖在的時間復雜度為O（[M+R]N+M2lgM），式中N為障礙物頂點數，M是N點構成的凸曲線的條數，R為開凸曲線的滾動數。最終，搜索最優路徑問題轉化為從起點到終點，經過障礙物切線的最短距離問題。

朱慶保[73]描述了機器人靜態路徑規劃的仿生算法，該算法利用柵格法對環境進行建模，并模擬螞蟻覓食行為，最終由多只螞蟻完成最優路徑搜索。采用了目標導引函數、最近鄰居策略和概率搜索策略，使搜索過程迅速高效。最后通過仿真表明：即使在非常復雜的障礙物環境中，算法也能迅速規劃出最優路徑。

而在水下自主車靜態路徑規劃方面，為了提高機器人的集礦效率，達到最優路徑規劃的目標，王隨平[74]建立了從起始點到終點，自主車耗能最少、耗時最短的多目標優化問題模型；利用對子目標加權將單目標優化問題取代多目標優化；采用了將蟻群算法與遺傳算法相融合算法——GAAA算法，對機器人作業路徑進行了尋優控制；并通過仿真驗證了算法用于機器人路徑尋優是有效的和可行的，并且規劃路徑的效果較螞蟻系統更好（圖1-8，圖1-9）。

機器人進行全局路徑規劃的基礎是水下三維環境模型，在每個已獲知精確環境信息的滾動窗口內，機器人利用在環境模型中規劃出的路徑逐步向目標點方向行走采集。本書采用群智能算法[75～80]規劃滾動窗口內的靜態路徑，并對算法進行改進，提高算法實時性；并按照不同的原則設置算法啟發函數和適應度函數，以滿足機器人運行中存在的采集路徑和連接路徑的不同要求。

1.3.4　動態路徑規劃技術的研究進展

動態路徑規劃的前提是機器人無法獲得先驗的全局環境信息，只能依靠當前獲得的信息，以在線的形式規劃機器人的路徑。

關于動態路徑規劃的方法研究，Gerke M[81]使用遺傳算法（Genetic Algorithms）解決機器人動態路徑規劃問題。遺傳算法利用簡單的繁殖機制和編碼技術來描述復雜的現象，由于作為并行算法其隱性并行性適用于全局搜索，而且算法本身的優化計算和整體搜索策略不依賴于梯度信息，所以解決了其他一些算法難以解決的問題。因此，在移動機器人局部路徑規劃中有著廣泛的應用。遺傳算法是一種多點搜索算法，具備固有的并行性，不必要求導數存在、連續性、單峰等假設，不受搜索空間限制性假設的約束，因此與傳統優化算法相比具備突出的優點。

Nelson H C[82]使用模糊邏輯算法（Fuzzy Logic Algorithm）。模糊邏輯是基于實時傳感信息的一種在線規劃方法，它利用包含模糊概念的參照物的位置和運動信息，動態環境模型構造二維隸屬度函數；采用反射式導航機制，將當前環境障礙信息輸入模糊推理機，把機器人期望轉向角和速度作為推理機輸出；通過模糊評價綜合考察各個方向，獲得搜索結果。該方法運用近似自然語言方式，在包含動態障礙物的局部環境中能有效地實現機器人避碰導航；可以處理數據的非精確性和不確定性，克服誤差和噪聲，實現輸入輸出之間的映射關系。

Jang D[83]采用神經網絡（Artificial Neural Net Work）算法規劃機器人在線路徑。基本原理是將傳感器測得的障礙物信息等作為神經網絡的輸入層信息，經過神經網絡的并行處理；由多個選定位姿下的數據構成原始樣本集，經過剔除沖突或重復樣本等處理，得到最終樣本集；再由輸出層輸出由人給定場合下期望速度和轉向角，引導機器人導航避障，最后到達目的地。作為一個高度并行的分布式系統，神經網絡可以實時解決機器人在線路徑規劃問題。

模擬退火算法（Simulated Annealing）[84]是一種基于蒙特卡羅（Monte Carlo）迭代求解法的一種啟發式隨機搜索算法，Kastella K將其應用到機器人在線規劃領域。算法模擬固體的退火過程，按照Metropolis準則接受新解，并以一定的概率接受惡化解，因而能夠獲得全局最優解。算法將搜尋空間內的每一點想像成空氣內的分子；分子的能量，就是它本身的動能；而搜尋空間內的每一點，也像空氣分子一樣帶有能量，以表示該點對命題的合適程度。算法先以搜尋空間內一個任意點作起始：每一步先選擇一個鄰居，然后再計算從現有位置到達鄰居的概率。

Fukuda T[85]通過免疫算法（Immune algorithm）解決機器人在線規劃問題。免疫算法是一種具有勘測與開采能力，隨機性和確定性選擇相結合的啟發式隨機搜索算法。它通過抗體學習抗原來完成應答，完成自適應免疫中體液免疫的簡單模擬。將免疫概念在保留原算法優良特性的前提下，力圖有選擇、有目的地利用待求問題中的一些特征信息或知識來抑制其優化過程中出現的退化現象。

Mallot H.A[86]把基于行為的方法應用到機器人在線路徑規劃領域。該方法將導航問題分解為相對獨立的行為單元[87]，比如跟蹤、避碰、目標導向等。這些行為單元是完整的運動控制單元，由傳感器和執行器所組成，具有相應的導航功能，單元之間通過相互協調來完成導航任務。

在國內，相關文獻也分別就遺傳算法、模糊邏輯、神經網絡算法、模擬退火算法、免疫算法和基于行為的算法應用到機器人局部路徑規劃領域，并提出了相應的改進算法，取得了不錯的研究成果[88～93]。

而在水下自主車的局部路徑規劃上，張菁[94]探討了基于模糊決策的自主車實時路徑規劃方法。首先，通過測距聲吶水下機器人對其前方180°的范圍實時探測，獲得環境信息，利用模糊決策進行實時路徑規劃，得到避障所需轉動角度及方向，對于特殊情況參照連續轉角記錄儀來修正轉角，實現特殊環境中的運動避障。

劉海瀅[95]研究了水下多金屬結核集礦車作業過程中的局部路徑規劃，旨在解決水下特殊復雜環境下集礦機自適應實時路徑規劃問題；利用了基于強化學習的自調整和自學習算法實現了水下集礦機的實時運動規劃，實現模糊控制規則；設計了集礦機實時運動規劃器操作過程、規劃器結構以及相應的算法的整套實時規劃方案，樣機池試試驗表明該方法的有效性。

王隨平[96]針對水下底履帶機器車復雜、未知的工作環境，提出了一種履帶機器車避障和導航算法（圖1-10）。該算法首先利用聲吶傳感器實時檢測障礙物的位置，然后用D-S理論推算障礙物更精確的位置，最后運用改進人工勢場法決策行走方向，規劃履帶機器車的實時作業路徑，實現了水下履帶機器車的避障和導航。仿真結果表明，該算法適應未知動態復雜環境下水下履帶車的實時避障和導航。

李鵬英[97]結合水下集礦機實際作業環境，建立了基于神經網絡的集礦機實時避障模型。該模型利用多傳感器融合技術，將傳感器采集到的環境信息數據處理后作為BP神經網絡輸入；把車體的速度、轉向角和注視向量作為為網絡輸出；依據集礦機實際運行情況，綜合人行走經驗，設置能實現實時避障網絡導師訓練信號。為克服局部極小值問題，引入遺傳算法對BP避障模型進行改進。仿真實驗表明該算法能夠通過有效訓練達到預期的目標，并很大程度上克服了BP網絡的局部極小問題。

席裕庚、張純剛等[98～102]借鑒預測控制中的滾動優化原理，在全局環境信息未知或不完備的情況下，利用機器人實時探測的局部環境信息提出了基于滾動窗口法的機器人路徑在線規劃方法。該方法以滾動的方式進行在線規劃，實現了優化與反饋的合理結合。建立了環境中存在靜態和動態障礙物情況下，滾動規劃的算法模型，具有良好的適應性，并分析了算法的安全性和可達性。該算法不追求全局情況未知的路徑最優，而是通過滾動的方式獲得局部較優路徑，通過對環境的不斷更新最終得到次優結果。

本書以尋找遍歷路徑上的對應轉向點為目的，建立動態路徑規劃的改進滾動窗口法模型。隨著機器人的不斷行走，滾動窗口內的環境信息也不斷獲得更新，機器人通過在窗口邊界上不斷需找新的子目標點的方式，逐步向轉向點靠近，并最終在滾動窗口內找到轉向點，完成單次動態規劃。機器人重復上述過程，最終達到對全區域的遍歷采集。