移動機器人路徑規劃算法綜述*

張晶 蔡志全 韓永成 牛彩霞

（唐山工業職業技術學院）

在智能化時代環境下，人工智能技術開始得到關注，而且在移動機器人這一領域也展開深入研究，將不同學科技術加以整合，應用在各個行業領域。機器人本質上屬于新工具，不僅為行業發展提供了動力，還極大地增加了人們生活的便捷性，減輕工作與勞動壓力。因為移動機器人關系到不同技術，整體質量也直接決定了智能化程度，所以在路徑規劃階段，一般會通過2種路徑加強機器人科技科水平，為我國科技行業的進步添磚加瓦。這里提到移動機器人路徑規劃，需要運用到不同形式的傳感器影響機器人，并且按照環境感知，在評判標準作用下規劃出安全性最佳的運行路線。路徑規劃期間按照機器人功能，可使用不同的算法，得出機器人繞過一些障礙物的時間、效率。常見的路徑規劃算法有全局、局部和人工智能三種類型，在移動機器人路徑規劃中分別有不同的作用。下文圍繞移動機器人路徑規劃算法分別展開討論。

一、移動機器人路徑規劃概述

移動機器人路徑規劃屬于技術研發領域，常見的機器人路徑規劃技術是以任意參數指標為對象，從任務區域挑選出從起點到終點連接的最佳避障路徑，換言之，也可以理解為在若干個約束條件下所獲得的可行解。分析移動機器人的路徑規劃效果，通常會對機器人運行、任務完成實時結果帶來直接的影響[1]。

最初關注機器人路徑規劃的分析，可以追溯到20世紀，迄今為止世界上所有的機器人研發依然在持續進行，并且從技術上獲得了顯著成效。按照環境信息特征，將路徑規劃劃分為離散域范圍、連續域范圍兩種類型；按照路徑規劃算法被發現的順序，則有傳統算法和現代智能算法兩種類型。結合移動機器人理解的工作區域信息層次，路徑規劃主要有兩類，即全局路徑規劃、局部路徑規劃。其一，全局路徑規劃。按照掌握的全局環境信息可創建抽象全區域環境地圖模型，該模型中可以通過尋優搜索算法，得出機器人運行的全局最優、次優路徑，對移動機器人朝目標點進行安全移動加以引導。該路徑規劃算法首先需要理解環境信息并構建地圖模型，其次則涉及到全局路徑搜索、機器人引導。其二，局部路徑規劃。機器人完成任務期間，按照所攜帶傳感器獲取的局部環境信息，便可以展開實時動態路徑規劃，這一類型路徑規劃算法的靈活性、實時性非常強。但是在局部環境特點影響下，所得到的路徑有可能僅為局部最優，并非是全局最優，還有可能無法達到目標[2]。實際上對于移動機器人路徑規劃而言，可以將全局與局部兩種路徑規劃算法加以組合，通過前者獲得機器人的全局優化路徑，再利用后者達到實時避障的效果。

二、移動機器人路徑規劃的常見算法

（一）全局路徑規劃算法

1.圖搜索算法

圖搜索算法涵蓋了諸多不同類型的算法，如A*算法，針對移動機器人確定目標關鍵點，一般是機器人與障礙物，機器人環繞障礙物之后遵循“以點成線，以線成面”的原則直接構圖即為可視圖。可視圖目標點可見，點與點之間的頂點需要保證清晰度。圖搜索算法在運用中，可以得出最短路線，即起點和目標點之間的最短距離[3]。利用這種優化算法，刪除一些多余的連線，可視圖得到簡化處理之后搜索時間也就隨之縮短。

2.快速隨機搜索樹

快速隨機搜索樹（Rapidexploration Random Tree，RRT）作為全局路徑規劃算法，是在采樣基礎上延伸而來的搜索算法，在高維非歐空間搜索中適用性極高。利用快速隨機搜索樹算法，針對多維度空間中不完整性約束問題能夠快速做出處理。路徑規劃起點作為搜索樹根節點，按照規定準則可以設定搜索樹的節點，再結合路徑規劃已知約束條件，已經確定的節點再擴展之后可得出新節點，在搜索樹中儲存，隨之不斷重復上述流程，直至找到終點。通過此算法一方面可以展開隨機采樣，使機器人探索并未探查的空間，另一方面在探索期間也會優化搜索樹[4]。

快速隨機搜索樹算法屬于快速搜索算法，具有探索速度快、搜索力強、地圖預處理操作便捷等優勢，但是在搜索過程中比較盲目，特別是高維、動態環境下，可能增加探索的時間與計算復雜性，還有可能陷入死區中，導致局部最小值。面對此算法計算復雜的問題，建議將RRT算法和滾動路徑規劃算法結合，起到移動機器人在線避障的引導作用，可以降低RRT算法復雜程度，還加強了實時性。以此為基礎引入選擇性參數，優化傳統算法統一概率，可以提高RRT算法收斂效率，加強算法路徑規劃指向性。經過改進之后的RRT算法，可以運用在滾動窗口改進路徑規劃算法中，既保證了原有RRT算法在隨機搜索方面的優勢，又對估價收斂標準函數引導搜索樹生長進行了引導，縮短算法運算所花費的時間。面對局部最小問題，建議采用回歸分析法，篩選出新節點，保證算法智能趨近終點優勢的基礎上，還可以對未知空間展開探索[5]。另外，快速隨機搜索樹基礎上還提出了高自由度關節移動機器人的方法，在高維空間中具有極高的適應性，按照路徑復雜性確定機器人主體，并且篩選出機器人關節，也就是所謂的配置空間、采樣自適應維度路徑規劃。該路徑規劃與自適應快速隨機搜索樹算法結合之后，利用自適應選擇主體，可在自適應三維空間范圍內循序漸進的增加RRT。因為傳統形式的快速搜索隨機樹算法在運用中收斂速度不高，建議與多約束條件改進算法加以融合，此算法同時涉及到環境約束、運動學約束，通過啟發方法采樣節點，極大地保證了路徑規劃速度[6]。

3.智能仿生算法

智能仿生算法的核心是對自然界所有動物進化的過程、昆蟲覓食捕獵行為等進行模擬，以此來規劃移動機器人運行路徑，常見的有蟻群算法、粒子群算法等。其一，蟻群算法。此算法是在螞蟻覓食行為基礎上延伸而來，一般螞蟻覓食期間會分泌出信息素，在已經走過道路遺留痕跡，后續再有覓食的螞蟻便會根據遺留的信息素明確路線，搜索得出信息素濃度，一般濃度高即為最短路徑[7]。基于此，蟻群算法領域的全局路徑規劃，可以按照蟻群數量、啟發因子、信息素數量等確定移動機器人規劃路徑，經過信息素改進后可以進一步提高算法收斂速度和搜索效率。

4.遺傳算法

遺傳算法（Genetic Algorithm，GA）屬于全局優化搜索算法范疇，其是在達爾文進化思想基礎上延伸而來，以自然選擇與遺傳產生的交叉、變異、遺傳等現象，展開仿真模擬，遵循優勝劣汰原則，并且結合結果獲得候選解，在所有候選解當中可以發現最優解。遺傳算法具有迭代優勢，并且組合其他算法，展現出自組織性、自學習性的特點，移動機器人路徑規劃最優路徑的搜索性也非常強。遺傳算法的操作比較簡單，很少會受外部環境影響，但是實時運算和搜索效率不高，極易于陷入到局部最優解。算法運行階段，不重要的種群存在則會增加計算難度，降低算法運行效率，在線路徑規劃的適用性不高。

（二）局部路徑規劃算法

1.模擬退火算法

模擬退火算法是目前移動機器人路徑規劃中，組合優化問題最為有效地解決算法，處理算法期間金屬熱在算法有效退火，初期控制金屬環溫度，即使遇到突發性事件，也可以隨機搜索，快速地收集數據。結合路徑規劃現狀，使用模擬退火算法，具有操作簡單、有效性強、控制數據少以及彈性等諸多優勢，但是也會出現一定概率，導致速度緩慢[8]。運用模擬退火算法進行移動機器人局部路徑規劃，使路徑擺脫原始路徑，探索出新目標點，找到最佳移動路徑。

2.人工勢場算法

人工勢場算法在移動機器人路徑規劃中運用，針對機器人所在環境展開規劃，在人工場范圍內運動，其本質上屬于抽象意義的人造受力場，利用目標點對輸出機器人形成引力與障礙物斥力，基于不同環境所形成的合力也可以明確機器人輸出。此算法的結構比較簡單，在底層實時控制方面具有明顯的優勢，最終規劃路徑也十分平滑，保證了移動機器人運行的安全性。但是人工勢場算法依然存在局部最優、狹窄通道動蕩等問題[9]。如果環境要求過于嚴格，其虛擬合力即為零，此時會影響到移動機器人的運行，無法繼續執行任務。通過人工勢場啟發函數，便可達到全局最優，并規避局部最優帶來的影響。面對人工勢場算法潛在問題，可以結合斥力模型，路徑規劃階段移動機器人規避局部極小點，使得路徑規劃面臨問題得到解決。

（三）基于人工智能算法的路徑規劃技術

基于人工智能算法的路徑規劃表現最為突出的就是深度強化學習算法（Deep Reinforcement Learning,DQN)，所謂深度強化學習，是深度學習感知能力、強化學習決策能力的融合，按照輸入圖像展開精準控制，其本質上與人類的思維方式更為接近，是人工智能領域也得到了極大的關注。深度學習感知力較強，但決策力不高，強化學習本身有一定的決策力，面對感知問題卻無法得出有效的結論。將兩種算法結合后的深度強化學習具有自監督學習能力，可在復雜的環境中可自主與周圍環境進行交互。同時其在決策與狀態分析也有很好的表現能力。深度強化學習在路徑規劃方面最主要的優勢在于其不依賴人工標記軌跡，只需設置規劃原則如運行路徑最短、無障礙物碰撞和目標點等，然后在虛擬實驗平臺或者現實環境中訓練神經網絡即可。但是深度強化學習在路徑規劃上仍也存在很多不足之處，如路徑規劃時效性差、遇障礙多次轉向等問題，需要從改進神經網絡模型、獎勵函數和多算法融合方面進行探索改進，為移動機器人路徑規劃這種比較復雜的系統感知決策問題梳理思路。

DQN算法主要有神經網絡、Q learning兩種，被稱作 Deep Q Network。該算法中包括記憶庫，記載著學習的所有經歷。Q learning屬于off-policy 離線學習法，可以學習目前正在經歷的內容，也可以學習以往經歷的內容，整體范圍比較廣。因此，當DQN更新時便可以隨機抽取已有經歷學習，有利于提高神經網絡更新的效率。此外，Fixed Q-targets 的應用需要打亂相關性，若在移動機器人路徑規劃中應 用 fixed Q-targets，DQN所涉及到的2個結構一致，但是參數存在差異的神經網絡，可以預估神經網絡參數，加強路徑規劃精準性。

三、移動機器人路徑規劃算法應用前景

如今移動機器人技術已經非常先進，在計算機、傳感器、人工智能等各項技術的飛速發展下，路徑規劃也獲得了非常顯著的研究效果，但是路徑規劃算法之間的差異、限制，還需要在基礎理論與技術層面加以優化。立足于移動機器人路徑規劃算法的發展現狀，路徑規劃算法今后的發展前景非常可觀，也為我國人工智能行業的發展夯實了基礎。為此，分析今后移動機器人路徑規劃算法的應用前景，主要表現在以下四方面：

第一，現有的路徑規劃算法將得到不斷改進與優化。路徑規劃算法的應用，其中任意一種算法難免會遇到問題，特別是算法自身存在的局限性。在移動機器人路徑規劃中進行改進，有利于提高算法性能，將移動機器人面臨的問題予以解決。

第二，混合算法將得到廣泛應用。路徑規劃中采用混合算法，是將不同算法進行組合。獨立算法無法解決切實存在的路徑規劃問題，特別是交叉學科面臨的新問題。考慮到研發各種新算法具有很大難度，所以可以通過不同的路徑規劃算法優勢，達到互補效果，為解決路徑規劃問題探索新思路。例如群體智能算法、強化學習算法和神經網絡等，在移動機器人路徑規劃問題均得到了組合應用，通過這種互補混合算法，不僅加快了算法之間的融合，利用取長補短與優勢互補，還會延伸出大量優秀算法。人工智能、數理、仿生算法等經過組合之后，在移動機器人路徑規劃中應用也呈現出可觀的發展前景。

第三，多種機器人協同合作。移動機器人的作業范圍近年來逐漸拓寬，加上作業任務難度增加、復雜程度更高，所以單一機器人無法快速完成規定的任務，此時便要多種機器人協同合作，既可以提高機器人的工作效率，又能夠杜絕因改變作業環境、機器人系統局部故障等原因造成的工作停滯事故。單一機器人處于某種關注環境下，有時并不能很好地達到使用要求，通過多機器人協同合作的方法可以解決該問題。另外，多機器人在運行期間也會出現一些故障，例如路徑規劃更加復雜，障礙物和機器人數量更多，也在路徑規劃階段面臨困難。所以，多種機器人協同運行將成為今后行業領域內研究的重點。

第四，當移動機器人處在比較復雜的且多維環境下，移動機器人路徑規劃將成為關注要點。面對具體對象，移動機器人路徑規劃一般是以陸地作業機器人路徑規劃為對象，此條件下比較常用掃地機器人、反恐防爆機器人。面對空中飛行機器人、水下機器人，對比掃地機器人等生活中使用幾率比較高的設備，總體來說研究不夠深入。目前，空間探測對移動機器人提出的嚴格要求，所以移動機器人研究重點也開始轉移到崎嶇地形、障礙物比較多的復雜環境。立足于路徑規劃環境描述這一角度，二維平面環境下的路徑規劃工作量比較大，三維環境的路徑規劃相對較少。即便如此，仍然有一些移動機器人的工作環境為三維環境空間，例如飛行器。此外，陸地機器人一般是在相對穩定的陸地環境中運行，飛行機器人和仿生魚類機器人的工作環境與之相比，其惡劣程度也有所增加，傳感器的使用也更加嚴格，還存在一些危險因素。為此，飛行器、仿生魚類機器人在研究過程中需要重點分析，全面總結，從現實環境著手展開移動機器人路徑規劃。

四、結束語

綜上所述，移動機器人是在人工智能技術基礎上延伸而來的全新行業領域，融合了互聯網、人工智能等多項先進技術。機器人研究最為重要的是路徑規劃，在此環節需要使用大量算法，只有如此才能夠規劃最優機器人行進路線，提高運行效率與質量，以免因為路徑規劃不合理，導致出現延長行進時間的現象。基于本文的分析，圖搜索算法、快速隨機搜索樹、智能仿生算法、遺傳算法、模擬退火算法、人工勢場算法等均可以在路徑規劃中應用，除了單一算法的使用外，還可以將算法組合應用，進一步優化路徑規劃效果。此外，工作人員對現有算法進行改進，還可以起到良好的優化效果，提高移動機器人行進效率，也為我國移動機器人的研究積累經驗。