王 旭，朱其新，朱永紅

1.蘇州科技大學 電子與信息工程學院，江蘇 蘇州 215009

2.蘇州科技大學 機械工程學院，江蘇 蘇州 215009

3.江蘇省建筑智慧節能重點實驗室，江蘇 蘇州 215009

4.蘇州市共融機器人技術重點實驗室，江蘇 蘇州 215009

5.景德鎮陶瓷大學 機電工程學院，江西 景德鎮 333001

機器人起源于20 世紀，由Fryer[1]和Carrera[2]在Vaucanson 和Jaquet 構造的類人機器人基礎上做的研究。在工業革命結束時，機器人技術的進步促進了不同科學領域的發展，并創造了大批新設備以應用于不同領域之中，如建筑、軍事、航空、運輸等。機器人是由圖1中的幾個系統組成的，本文主要研究其控制系統中的路徑規劃技術。

圖1 機器人的六大系統Fig.1 Six systems of robot

移動機器人通常應用于各種復雜的環境中，圖2展示了四種場景下的移動機器人。在各個領域都有特定功能的機器人來為人類服務[3-4]，以完成各種任務[5]，包括探索未知的環境、搜索被困的受害者和攜帶重要材料等。在緊急和危險的場景中，移動機器人甚至可能是不可替代的[6]。然而，自主移動機器人的路徑規劃問題是當前難以解決的問題之一[3]。路徑規劃的目的是以最優的方式生成從起點到目標點可行的安全路徑，避免自主移動機器人運動過程中可能發生的所有碰撞[7-8]。路徑規劃在靜態地圖環境中，一般在機器人進行移動之前就需要找到整個解決方案。與之不同的是，對于動態以及局部已知的環境，通常需要實時規劃，并且需要更多的計劃更新時間。移動機器人路徑規劃的主要問題一般是計算的復雜性、路徑最優值的存在和整體適應性[4]。在二維移動機器人路徑規劃算法領域，大部分研究的目的在于找到最優解，但是隨著生產技術的發展，最優路徑已經不能滿足需求。所以，在最優路徑、收斂速度、平滑性、搜索速度等條件中進行統籌兼顧的改進是此領域內的最大任務和難點，也是研究的大勢所趨的方向。

圖2 各個領域的移動機器人Fig.2 Mobile robots in various fields

1 路徑規劃研究現狀

路徑規劃是機器人學的基本問題之一[9-10]，也是研究最多的問題。目前，移動機器人路徑規劃領域的研究者們已經開發了許多技術，是當今研究的熱點[11]。早期開發的確定性規劃技術表明，即使對于簡單的系統，它的計算要求也很高[12]。確切的路線圖方法是早期路徑規劃的主要方法，如可見性圖[13]、Voronoi圖[14]、Delaunay三角圖[15]和自適應路線圖[16]，這些方法試圖捕捉機器人搜索空間的連接性。而諸如Dijkstra 和A*等搜索算法被用來在連通性圖中尋找最優解，D*則是針對動態圖的。圖搜索方法的使用涉及到工作空間的離散化，其性能在高維度上有所下降。有效的離散化可以以犧牲完整性為代價，而高分辨率的離散化在計算上是昂貴的。新型計算方法的出現激發了它們在路徑規劃中的應用。模糊邏輯控制[17-18]、神經網絡[19]、遺傳算法[20-21]、蟻群優化[22]和模擬退火[13]等方法都被應用于機器人路徑規劃。

二十一世紀以來，隨著人工智能、傳感器、網絡和通信技術的快速發展，研究者們開始重視機器人的智能化[23]。在執行任務時，機器人需要使用路徑規劃技術對環境進行建模并定位其位置，控制運動，檢測障礙物并避開障礙物。從起點到目標點的安全路徑規劃（通過檢測和避開障礙物）是移動機器人的最基本的功能。因此，作為移動機器人研究的重要組成部分，路徑規劃技術將直接影響移動機器人完成任務的效率。

本文通過將路徑規劃算法劃分為全局和局部兩部分，注重對啟發式路徑規劃算法進行梳理歸納和全面評述。對Dijkstra 算法、A*算法、RRT 算法、遺傳算法、人工勢場法、模擬退火算法、D*算法、蟻群算法、模糊推理法、強化學習法進行了深入分析。引用了領域內最新的文章，結合對各個算法的改進策略，對改進后的算法，在優勢、局限性和適用場景三個方面進行比較。

2 基于先驗信息的全局路徑規劃

全局路徑規劃一般屬于離線（靜態）的規劃，移動機器人需要事先掌握地圖所有的環境信息，綜合先驗完全信息來進行路徑規劃。在這種問題中，障礙物的位置一般是固定的。應用于此類問題的算法有：Dijkstra算法、A*算法、RRT算法、遺傳算法等。

2.1 Dijkstra算法

1956 年，由Dijkstra 首次發現迪杰斯特拉算法[24]。Dijkstra 算法作為典型的求解最短路徑的算法，經常被用于計算移動機器人在運動過程中單個節點到目標節點的最短路徑[25]。其主要特點是以源節點為中心向外，通過迭代來選擇下一個節點進行層層擴展，為了確保每一次迭代行進的路程是最短，該算法每次迭代時選擇當前節點最近的子節點作為下一個節點[26]。同時在每一次迭代過程中，都要對源節點到所有遍歷經過的節點之間的最短路徑進行更新，最終得到最短路徑。

在幾十年的發展中，Dijkstra 算法顯示出強悍的競爭力。因為實用性較高，該算法已經被多數研究者應用于實際程序中，例如谷歌地圖[27]將此算法應用于自動駕駛導航之中。張瑜等[28]將Dijkstra的算法結合到一個動態窗口中，并對DWA中速度采樣空間進行約束優化，用作未知環境中的路徑規劃，解決了清洗機器人加速過大導致的偏移量誤差大的問題。韋榮杰等[29]深入研究了一種基于控制的移動機器人避障路徑規劃設計系統，并且做到了不需要繁重的計算量和不用占用較高的內存。Alshammrei 等[30]對Dijkstra 算法進行了改進，有效地解決包括障礙物在內的環境中的最優路徑規劃，但是路線的平滑度和連續性較一般。Durakli 等在文獻[31]中的研究，結構更加簡單，不需要添加任何中間節點，通過引入貝塞爾曲線修剪路徑，使得路徑更加平滑。此外，這種改進算法可以在動態環境中運行并檢測到移動的障礙物，實時地更新路徑。

為了進一步提高Dijkstra算法的性能，文獻[32]采用Dijkstra 算法和蟻群算法混合并引入隨機節點選擇機制，文獻[33]采用遺傳算法優化Dijkstra算法的最短路徑和投遞順序。這兩種方法分別可以使其具有更好的全局搜索能力和更短的路徑長度，但同時也增加了算法的復雜度和路徑的復雜度。姜辰凱等[34]針對智能倉儲中的路徑規劃問題將Dijkstra算法優化，進行時間窗排布，提出了一種路徑長度更短，轉彎角度更小的改進算法。此外，該算法還被廣泛用于疏散線路規劃[35]、鐵路線路及船舶航線規劃、物流調度等領域。改進Dijkstra 算法的文獻對比如表1所示。

表1 Dijkstra算法改進分析Table 1 Improvement analysis of Dijkstra algorithm

總的來說，Dijkstra 由于其算法結構簡單，收斂性好，所以在最優路徑問題和疏散問題中的應用較廣。從所引用的文獻中可以發現，因為需要遍歷更多的節點，導致計算量龐大，算法復雜度高，還會占用更大的內存，所以效率不高。

2.2 A*算法

A*搜索算法最早由斯坦福教授Nilsson 等[36]所發明。此算法基于Dijkstra 算法進行了深入研究，針對單個目標做了優化，算法的宗旨在于優先考慮似乎更接近目標的路徑。A*算法與其他路徑規劃算法的最大區別在于啟發式函數的組成[37]。啟發式函數引導A*算法搜索最短路徑，傳統A*算法的啟發式函數一般使用曼哈頓距離[38]、歐幾里德距離[39]和切比雪夫[40（]對角線距離）。

Wang 等[41]提出了一種改進A*算法的路徑規劃方法，通過對啟發式函數進行加權來提高計算效率，縮短處理時間，有效地解決了旅行商問題中的道路成本，但還存在著路徑過長等局限性。Erke 等[42]提出了一種通過全局規劃生成的準則，以開發啟發式函數和變步長A*算法。與現有技術相比，所提的改進算法具有更好的魯棒性和穩定性。熊旭等[43]應用了基于A*算法生成路徑并使用貝塞爾曲線進行平滑處理，通過解決A*算法沒有考慮車輛輪廓和缺乏速度規劃的問題，保證了車輛的穩定性，同時也提高了A*算法在自動駕駛車輛規劃中的適用性。鄭濤等[44]在A*算法的代價函數中加入了角度評價代價函數，并利用跳點搜索的特性來提高搜索速度。

為了解決傳統算法所存在的節點冗余問題，張燕等[45]介紹了路徑二次規劃的關鍵點選擇策略，該策略刪除了冗余的轉彎節點和無效節點。付麗霞等[46]研究了不同障礙物尺度下網格路徑規劃的A*算法。同時，引入了改進的A*算法來優化關鍵點并簡化關鍵點的路徑。宋芮等[47]提出了一種改進算法，以解決傳統A*算法受地圖分辨率約束的問題。Wang等[48]使用開始目標代價函數對目標序列進行排序，并將改進的A*算法和動態窗口法相結合應用于多目標點規劃。表2 是近幾年部分改進策略的對比分析。

表2 A*算法改進分析Table 2 Improvement analysis of A* algorithm

可以看到A*算法作為經典的啟發式算法，其計算效率較高，被廣泛用于函數優化問題和設計優化問題。同時由于其啟發式函數的魯棒性較好，在最新的研究中通常被用于和其他算法的融合，進一步提高了算法性能。

2.3 快速隨機搜索樹算法（RRT）

快速隨機搜索樹（RRT）算法[49]是可以通過搜索可行路徑步驟在所有引用的應用范圍上應用于路徑規劃的幾種技術之一。RRT 算法允許通過有效探索具有凸和非凸障礙的多維搜索空間來規劃完整和非完整系統的路徑。其操作包括從待規劃路徑的初始位置（根節點）擴展樹形數據結構[50]，直到其一個樹枝到達目標位置（最后一個葉節點）。

目前，基于RRT的算法已經被廣泛地用于機器人路徑規劃[51]中。其中，對采樣方式的改進是研究的熱門。李柄輝等[52]提出了一種自適應雙向搜索改進算法，可以很好地處理狹窄通道環境，同時保留RRT算法在其他環境中規劃路徑的能力。所提出的規劃器被證明能夠適應各種環境，并且可以在短時間內完成路徑規劃。康金谷等[53]提出了一種基于三角不等式的RRT-Connect 算法，利用三角不等式原理解決了RRT-Connect算法的尋優問題。所提出的算法在相似的樣本數量和計劃時間中顯示出比RRT-Connect 算法更短的路徑。Jeong 等[54]和廖兵等[55]同樣引用了三角重新布線的思想，前者擴大了可能的父頂點集，并且使算法具有更好的初始解和收斂性，后者在加快收斂速度的同時顯著降低了算法的成本。

Wang 等[56]將采樣點進行聚類，隨后在每個中心生成一棵樹，最后使用強化學習來擴展這些樹。Lai等[57-58]通過多個本地樹來調整全局搜索狀態。文獻[58]還提出了使用貝葉斯估計來調整采樣方向，來增強算法在復雜困難環境中的處理能力。這些改進算法通常根據空間信息計算并選擇合適的樹擴展方向并且具有很高的計算復雜度。此外，RRT 算法在自動泊車，自動駕駛以及物體跟蹤行業有著廣泛的應用。

從表3 中不難發現，最近的研究已經基本解決了RRT算法在狹窄通道中找不到解的問題，但是面對復雜環境時，其計算數據量大的局限性是有待克服的。

表3 RRT算法改進分析Table 3 Improvement analysis of RRT algorithm

2.4 遺傳算法（GA）

遺傳算法是由John H.Holland教授在著作《自然與人工系統中的適應》中提出的一種相對完整的理論和方法。此算法向達爾文的進化論學習，通過模擬自然進化的過程來構建人工系統的模型。GA利用計算機科學和自然生物遺傳學來解決復雜的問題，主要涉及編碼、初始化種群、適應度函數及值的計算、選擇操作、交叉操作、突變操作。圖3是遺傳算法的簡單流程。

圖3 遺傳算法流程圖Fig.3 Genetic algorithm flow chart

遺傳算法具有簡單、通用性強、魯棒性強，適合并行處理的特點。作為啟發式優化算法的典型代表，GA 的搜索策略和優化不依賴于問題的梯度信息。GA易于通過編程實現，并且該算法對優化問題的約束很少，可以輕松地使用它來修改現有的元啟發式優化算法，以實現更好的性能。因此，GA 因其強大的全局優化能力和高效的并行性而在路徑規劃中得到廣泛的應用[59]。

張昭君等[60]為了解決傳統遺傳算法隨機初始化所導致可行個體的概率低和過早收斂問題，對初始化種群進行了改進，提出了一種具有混合初始化方法的新型遺傳算法。該方法可以生成更好的初始種群同時通過刪除和反向操作來提高算法的性能。同樣在針對初始化種群的改進中，Lee 等[61]提出一種基于有向無環圖的方法來提高算法性能；郝坤等[62]提出了基于多種群遷移的方法，將初始種群進行了連接，使離散路徑連接到連續路徑；李凱榮等[63]提出了隨機搜索法和升序法相結合產生初始種群的方法來提升路徑規劃效率。而在適應度函數的改進方面，張錚等[64]提出一個改進的適應度函數，優化了自適應交叉變異操作，通過平衡閾值優化其性能來應用于動態環境規劃；Lamin 等[65]提出了一種適合于遺傳算法的適應度函數，通過減少其路徑中的轉彎次數以達到目標。遺傳算子優化也是遺傳算法的一個改進方向。張瓊冰等[66]設計了一種新的交叉機制，該機制帶有可變長度的交叉算子，成功提高了遺傳算法的收斂速度；為了處理運動目標的問題，Patle 等[67]在此基礎上提出了基于矩陣二進制編碼的遺傳算法（MGA），用于單機器人和多機器人系統的復雜環境中。在這種方法中，機器人可以很容易地跟蹤移動障礙物和移動目標，并在短時間內到達目的地；Doostie 等[68]提出一種新的自適應遺傳算法，采用A*算法尋找中間節點來擬合可行曲線，最后再引入鄰域遺傳算子。對于染色體長度的改進，倪建軍等[69]提出了另一種新型遺傳算法。在他們的方法中，染色體的長度被修改以獲得最佳輸出。GA方法對環境（已知和未知）做出了有效的反應；因此，它被用于水下機器人[70]和空中機器人[71]的三維路徑規劃問題，以及仿人機器人[72]的二維路徑規劃。表4 是遺傳算法部分改進策略的對比分析。

表4 遺傳算法改進分析Table 4 Improvement analysis of genetic algorithm

遺傳算法雖然具有較強的路徑搜索能力和較高的效率，在函數優化問題中展現出較強的競爭力，但其需要具體的經驗，所以在面對未知環境時效果一般。

3 基于傳感器信息的局部路徑規劃

局部路徑規劃一般屬于在線（動態）的規劃，移動機器人的內部傳感器必須實時收集環境地圖信息，確定地圖和障礙的分布情況，從而選擇從當前節點到目標節點的最佳路徑。應用于此類問題的算法有：人工勢場法、模擬退火算法、D*算法、蟻群算法、模糊推理法、強化學習法等。

3.1 人工勢場法（APF）

1985 年，Khatib[73]提出了用于移動機器人導航的APF方法。根據他的觀點，目標和障礙物就像帶電的表面，總電勢在機器人上產生了假想力。如圖4所示，這個假想力將機器人吸引向目標，并使其遠離障礙物。在這里，機器人沿著負的梯度，避開障礙物，到達目標點。人工勢場算法結構簡單，能夠滿足實時控制的要求。因此，該算法在處理動態避障路徑規劃方面還具有顯著優勢[74]。

圖4 人工勢場法原理Fig.4 Principle of artificial potential field method

朱其丹等[75]在2006 年提出了一種無局部極小值的勢場函數構造，能夠針對特定環境而合理地逃逸局部極小值，從根本上解決了局部極小值問題。為了改進對環境的高要求，2017年，Abdalla等[76]提出了一種將人工勢場法與模糊控制邏輯相結合的思想，放棄了具有局部最小問題的初始路徑，直到傳感器確認不存在碰撞風險為止。張成[77]將改進的人工勢場方法與混沌優化算法相結合，解決了移動機器人在未知復雜環境中的擺動問題。王宏等[78]采用模型預測控制算法進行路徑規劃，將障礙物和潛在碰撞嚴重程度的人工電位場添加到控制目標中。王鵬偉等[79]提出了一種基于改進人工勢場算法的避障設計。對人工勢場方法進行了改進，重建了障礙物的排斥場范圍，最后生成無碰撞路徑。姚慶峰等[80]將人工勢場方法改進為一種黑洞勢場和強化學習相結合的方法，解決了局部穩定點的問題。林澤南等[81]基于APF方法提出了一種新的排斥場。將全局路徑的長度和平滑度作為粒子群優化（PSO）的適應度函數，以獲得APF中的障礙物影響范圍、引力系數和排斥系數。Duhe等[82]提出了排斥場的四種替代公式：校正多項式、切向和徑向分量、泊松勢和偽分數勢，有效地減少了移動機器人靠近障礙物時出現的振蕩。

從表5中可以發現，人工勢場法是局部路徑規劃中實用性較高的算法，在未知的環境中具有較強的避障能力。最近的研究通常是將人工勢場算法和其他算法進行融合改進，在解決運動規劃和避障問題中具有較好的魯棒性。但是在規劃時間和路徑的最優問題方面，還需要進一步的研究改進。

表5 人工勢場法改進分析Table 5 Improvement analysis of artificial potential field method

3.2 D＊算法

D*算法是基于A*算法的動態化改進，也是一種探路算法。它對路徑的未被探索的部分進行假設，并基于這些假設找到從當前坐標到目標坐標的最短路徑。隨后機器人沿著這條路徑移動，當它注意到新的障礙物信息時，它會把這些信息添加到地圖上。在到達目標坐標之前，或在確定目標坐標無法到達之前，重復這一次過程。在穿越未知的地形時，往往會遇到新的障礙，因此，重新規劃的過程需要更加快速。啟發式搜索算法利用從以往問題中獲得的經驗，加速對現有問題的搜索，從而加快搜索類似問題的序列。

Stentz[83]最早在1995 年提出D*算法以用于火星探測器的動態避障。Drake 等[84]設計一種新的路徑規劃器，旨在追求移動目標。此規劃器使用D*作為其初始路徑查找的基礎，然后從其搜索樹中獲取數據，以便在目標移動時快速重新規劃路徑。通過在搜索樹中存儲部分解路徑，以加快當前搜索速度，而不會失去最優性保證。但是，所有這些算法都優化了一個目標：最小化沿計劃路徑的邊緣成本值之和。但是在復雜未知的動態環境中，大尺寸區域處理始終是弱點，特別是在基于D*的路徑規劃中存在不必要的動態區域[85]。

在最新的研究中，許新寧等[86]通過自動分割聚類地圖的方法，使用障礙物位置的信息來自動計算。俞建華等[87]針對位置環境的路徑規劃問題，將D*進行了改進，引入Dubins 算法進行局部路徑平滑處理。孫兵等[88]在原有成本函數的基礎上增加了障礙物成本項和轉向角成本項作為約束條件，從而保證了導航的安全。任忠強等[89]提出一種在多目標增量搜索算法的基礎上引入了MOPBD*的次優變體的改進策略，實現了比現有的多目標路徑規劃增量方法快一個數量級的優勢。李孟澤等[90]設計了基于分散式邊緣計算的系統架構，做到了可以實時更新地圖信息，改進任務路徑來進行重新規劃。

表6是上述文獻的改進分析對比。總的來說，D*算法雖然計算量大，路徑不平滑，但是在處理動態障礙問題下，具有較強的可靠性，經常被用于未知環境的動態規劃問題。

表6 D*算法改進分析Table 6 Improvement analysis of D* algorithm

3.3 模擬退火算法（SA）

模擬退火算法（simulated annealing，SA）最早是由Metropolis 提出的基于蒙特卡羅（Monte Carlo）思想設計的。1983 年，Kirkpatrick 等[91]將退火思想加入到優化領域，常用于在較大的解空間中搜索近似全局最優解的優化算法。

SA作為一種優化技術，可以處理具有非線性，不連續性和隨機性程度的成本函數。它還可以處理強加給這些成本函數的任意邊界條件和約束。Tavares 等[92]提出了路徑的三種情況：折線、貝塞爾曲線、樣條插值曲線。并且在所提出的SA 算法中，每次迭代時評估每個連續參數的靈敏度，增加接受的解的數量。每個參數的敏感性與它在下一個候選項的定義中的概率分布相關聯。Ganeshmurthy 等[93]提出了一種將基于啟發式的方法組合到基于模擬退火算法的方法中，用于動態機器人路徑規劃，通過組合啟發式方法對運行時和離線路徑規劃進行了改進。孫琦等[94]通過啟發式遺傳算法降低模型在初始搜索路徑中的隨機性，然后結合Beam 搜索方法減少搜索所占用的空間和時間。苗輝等[95]開發了一種增強的SA 方法，該方法將兩個額外的數學運算符和初始路徑選擇啟發式方法集成到標準SA 中，用于移動機器人的動態路徑規劃。它顯著提高了SA 的計算性能，同時提供了最佳的機器人路徑解決方案，從而使其實時和在線應用成為可能。張琦等[96]將模擬退火（SA）和蟻群優化（ACO）算法相結合提出一種新的路徑規劃方法SAACO，用于解決未知環境下的移動機器人路徑規劃問題。翟龍鎮等[97]將模擬退火和遺傳算法結合，并且設計了自適應因子，避免搜索過程陷入局部最優解的同時，維持了種群的多樣性。表7是改進模擬退火算法的分析對比。

表7 模擬退火算法改進分析Table 7 Improvement analysis of simulated annealing algorithm

3.4 模糊推理法

Zadeh 于1965 年最早提出模糊集的概念。在之后的研究中，Cordón等[98]用模糊邏輯算法表示從狀態空間到控制空間的非線性映射。在路徑規劃中，先由模糊推理處理從傳感器檢測到的地圖和障礙物信息，其次根據定義的模糊規則來進行模糊推理和決策。推理的結果被去模糊化以控制移動機器人的運動。對于采用模糊邏輯算法的避障[99]，通常將機器人與周圍障礙物之間的感覺信息作為模糊控制器的輸入，并為機器人輸出新的移動指令。圖5是模糊推理的流程。

圖5 模糊推理過程Fig.5 Fuzzy reasoning process

為了更好地適應動態環境，宋琦等[100]將改進的蟻群算法與模糊邏輯方法整合到模糊邏輯蟻群優化（FLACO）中，提高了求解精度，節約了運算成本。Mirza[101]將模糊邏輯與神經網絡結合，使它們在動態環境中具有強大的處理和適應能力。王寧等[102]和Lee[103]在解決水中航行器路徑規劃問題時，將人工勢場法和模糊邏輯結合，克服了全局路徑規劃的缺點，有效的避免與障礙物發生碰撞。孫冰等[104]利用粒子群優化算法對模糊邏輯的隸屬函數值進行優化，解決了路徑規劃中模糊邏輯的邊界設計嚴重依賴專家經驗的問題。Gharajeh 等[105]提出了一種基于自適應神經模糊推理系統，使移動機器人能夠進行自主無碰撞，有效地找到不同場景下通過障礙物的無碰撞路徑。王京華等[106]提出一種空間取點的優化方法，結合了Dijkstra 算法的原理。與圖搜索算法相比，該算法大大減少了規劃時間，提供了更靈活的轉彎角度。與采樣算法相比，該算法可以更好地考慮機器人的尺寸以及速度和轉彎角度之間的關系，同時估計每一步的運動狀態。表8是近幾年對模糊算法進行改進的對比。

表8 模糊算法改進分析Table 8 Improvement analysis of fuzzy algorithm

3.5 蟻群算法（ACO）

蟻群算法（ant colony algorithm，ACO）是由意大利學者Dorigo[107]在1992年所提出。該算法是模仿螞蟻尋找食物來源的行為[108]而衍生出的元啟發式算法。蟻群算法因其并行處理、分布式計算和較強的魯棒性，近年來被廣泛應用到移動機器人路徑規劃領域[109]。圖6 是蟻群優化原理的仿生示意圖。

圖6 蟻群尋找食物源Fig.6 Ant colony searching for food source

作為智能優化算法[110]的典型，蟻群算法在路徑規劃領域彰顯了極強的競爭力。Utkarsh等[111]在網格地圖中結合了移動機器人的定向運動和矢量運動，提出了一種快速的蟻群算法。王麗娜等[112]提出了一種改進的蟻群算法。通過引入Floyd 算法來生成引導路徑，并增加引導路徑上的信息素含量。通過初始信息素的差異，引導蟻群快速找到目標節點。其次，應用回退策略，減少因落入陷阱而死亡的螞蟻數量，提高螞蟻找到目標節點的概率。羅強等[113]提出一種改進的蟻群優化算法，構建分配不等的初始信息素和采用偽隨機狀態轉換規則選擇路徑，解決了蟻群算法局部最優、收斂速度慢、搜索效率低的問題。Akka等[114]為了避免蟻群算法容易陷入局部最優解的缺陷，對信息素矩陣更新方法進行了優化。Uriol 等[115]分析并調整了ACO 算法的參數并且證明了ACO 算法在復雜環境下移動機器人路徑規劃的適用性。改進蟻群算法路徑平滑度的方案也是研究的熱門。戴曉林等[116]引入A*算法的求值函數和彎曲抑制算子，提高蟻群算法的啟發式信息，加快收斂速度，增加全局路徑的平滑度。楊輝等[117]提出了一種高效的雙層蟻群優化算法，由兩個獨立連續運行的蟻群算法組成。首先，提出一種并行精英蟻群優化方法[118]，在復雜地圖中生成初始無碰撞路徑，其次應用一種稱為轉折點優化算法的路徑改進算法，在長度、平滑度和安全性方面對初始路徑進行優化。表9是改進蟻群算法的文獻分析。

表9 蟻群算法改進分析Table 9 Improvement analysis of ant colony algorithm algorithm

3.6 強化學習法

隨著智能科學的發展和人工智能的蓬勃發展，人工智能路徑規劃技術迅速成為專家學者研究的重點，而現有的一些路徑規劃算法采用許多靜態策略，并且每個策略都與一個獨立的環境實例進行長時間的交互，沒有提出環境建模方法的判斷。強化學習因為其無需建立路徑規劃問題的數學模型和環境圖的特點，逐漸被用于協作解決避障、路徑規劃等問題。圖7是強化學習的基本框架。

圖7 強化學習的基本框架Fig.7 Basic framework of reinforcement learning

在求解路徑規劃問題的強化學習算法中，Q-learning算法是一種比較常用的與環境交互的學習方法。它是一種無模型的典型的強化學習方法[119-120]。這種方法不需要完整的環境知識。使機器人能夠從環境中學習適當的行為，并在機器人路徑規劃中取得了良好的效果。Q-learning通過連續估計狀態值函數和優化Q函數獲得最優策略。Q-learning在一定程度上不同于普通的時差方法（TD）。它采用狀態-動作對的Q(s,a)函數進行迭代計算。在智能體的學習過程中，需要檢查相應行為是否合理，以確保最終結果收斂。

Bae等[121]將Q-learning和卷積神經網絡（CNN）相結合，使移動機器人可以在各種環境中靈活高效地移動。Maw 等[122]提出了一種混合路徑規劃算法，該算法利用深度強化學習進行局部規劃，使目標能夠實時避免碰撞。ZENG等[123]將Q-learning算法應用于動態環境下的移動機器人導航，控制q值表大小，提高導航算法的速度。Low 等[124]引入部分引導Q-learning 的概念，初始化Q 表，加速Q 學習的收斂。Q-learning 算法也可用于求解基于網格圖的路徑規劃問題。2010年，Bonny等[125]提出了一種擴展的Q-learning算法，通過引入標志變量，加快了Q函數的收斂速度，提高了算法的效率。

在近幾年最新的研究中，Abdi 等[126]開發了一種結合計算機視覺、Q 學習和神經網絡的新路徑規劃方法。Sahu等人[127]提出了一種創新的方法來解決移動機器人對在已知靜態和復雜環境下的路徑規劃和同步問題，該問題解決了移動機器人從預定的起始位置到預設的目標位置的混合算法的設計，結合了改進Q-learning 的優點和粒子群優化[128]的特點（PSO）。Kim 等[129]利用Qlearning 對探索策略進行了調整，實現了實時路徑規劃。郭曉偉等[130]提出了一種改進的Q 學習算法來解決數字孿生裝配系統中的移動機器人路徑規劃。

此外，Sarsa 算法是一種基于Q 學習算法的模型無關的強化學習方法。在移動機器人路徑規劃領域，Sarsa算法也可以與其他方法相結合。Asghari[131]等將Sarsa算法與遺傳算法（GA）相結合來進行科學的調度分配。

表10 是強化學習算法改進策略的分析對比，作為智能優化算法的代表，強化學習算法體現了較強的實用性和適應性。對強化學習算法的改進可以在很多方向，總的來說，強化學習具有收斂快、時間短、路徑優等優點，仍存在計算復雜的局限性。表11 是上述所有算法的對比。

表10 強化學習法改進分析Table 10 Improvement analysis of reinforcement learning

表11 所有算法的對比Table 11 Comparison of all algorithms

4 結束語

4.1 總結

本文將路徑規劃算法簡單地分為兩大類——全局和局部，綜述了移動機器人路徑規劃技術的研究進展。此分類沒有明確的界限，很多算法對于兩種路徑規劃都適用。為了獲得最優路徑，針對不同的需求選擇不同的路徑規劃算法尤為重要。文章針對不同算法進行了討論和研究。其中，Dijkstra算法結構簡單，但需要遍歷更多的節點，因此效率不高。A*算法的關鍵是建立一個評估函數，以確保最短路徑搜索始終沿著目標方向，這比Dijkstra算法的效率更高。適用于求解靜態環境下的最短路徑。RRT 算法適用于高維空間和復雜約束條件下的路徑規劃，路徑生成的可行性可以滿足要求。但是由于其隨機采樣的特性，往往規劃時間較長。GA 因其在合適的參數下具有較強的路徑搜索能力和較高的效率而被廣泛應用，但參數的選擇主要取決于經驗，這對求解結果有很大影響。好的路徑規劃技術不僅可以節省大量時間，還可以減少人力和生產資源的投入。人工勢場算法（APF）結構簡單，能夠滿足實時控制的要求。因此，該算法在處理動態避障路徑規劃方面還具有顯著優勢。D*算法與A*相反，A*算法從起點到目標點進行搜索，而D*是從目標點向起點進行搜索進行反向傳播，反向搜索。模擬退火算法（SA）作為一種優化技術，可以處理具有非線性、不連續性和隨機性程度的成本函數。常用于在較大的解空間中搜索近似全局最優解的優化算法。模糊控制算法對于不確定性、隨機性比較強的環境處理能力非常出眾。能夠適應多障礙復雜的環境，且可以安全避障，避障路徑較為平滑。但是其對模糊控制器的專家經驗要求較高。蟻群算法（ACO）具有并行處理、分布式計算和較強的魯棒性，但是容易陷入局部最優，并且收斂速度慢和面對復雜環境搜索效率低。而強化學習算法的優勢在于不需要完整的環境信息，能夠讓機器人從環境中學習適當的行為。但是一般來說，其計算復雜度較高，訓練時間較長。

此外，與靜態環境相比，基于動態環境發表的研究論文很少。而在動態環境中，針對移動目標問題的機器人路徑規劃研究較少，針對移動障礙問題的機器人路徑規劃研究較少。到目前為止，大多數論文只展示了模擬分析，關于實時應用的論文要少得多。與單一移動機器人系統相比，關于多個移動機器人系統導航的論文較少。與獨立算法相比，關于混合算法的論文要少得多。

隨著生產力的發展，路徑規劃技術也會逐漸變得高效和智能，在各個領域得到應用，與人們的生活息息相關。

4.2 發展趨勢

隨著計算機、傳感器技術飛速發展，路徑規劃技術日新月異。在具體的路徑規劃算法中，都各自存在著優勢和局限性。在今后的研究中，還需不斷地跟進這些理論和實踐。根據現在的發展狀況，未來還可以在以下幾個方面進行關注：

（1）新的混合方法

應用新開發的混合算法就是將路徑規劃的不同算法取長補短，進行有效結合。將路徑規劃的算法進行合理的結合能做到提高效率。很多方法如強化學習法[132]和模糊推理法[133]已經被應用到路徑規劃問題中。例如人工勢場法和強化學習法的混合[134]可以有效地避免碰撞，使機器人快速、安全地到達目標點。將模糊算法和Dijkstra 算法混合[106]，可以再找到最優且平滑的路徑。類似的這些混合式算法具有很大的發展前景。

（2）基礎算法的改進

在現實場景中，路徑規劃過程都會面對許多挑戰，尤其是例如收斂慢、計算量大的局限性，從而導致路徑質量差、路徑振蕩等問題。而群體優化、蟻群優化、退火算法等受自然啟發的方法可以為路徑規劃注入智能。需要新的仿真方法來集成動態環境中的機器人行為。此外，在機器人系統中，應該研究具有單位負載可達性約束的路徑規劃方法。因此在具體思想上進行改進，可以有效地提升算法的效率，解決路徑規劃中的問題。

（3）復雜環境的路徑規劃

移動機器人路徑規劃大多數解決了地面二維環境下智能機器人的路徑規劃研究，例如掃地機器人、服務機器人、安防巡檢機器人等；而面向水下[135]和空中機器人的三維路徑規劃研究就相對較少。例如在水下機器人領域，許多特定的算法被提出用來解決水下環境的路徑導航規劃[136-137]，相比于二維模型更加復雜，需要考慮的影響因素也隨之增加。

隨著移動機器人技術的發展，路徑規劃的研究也將逐漸深入到復雜高維的地形環境中。此時就需要新的決策模型，機器人將在復雜環境中發揮至關重要的作用，需要新的方法來支持關于如何在復雜地圖系統中規劃和優化路徑的決策。高維和復雜環境中移動機器人的路徑規劃是未來的一條必不可少的研究方向。

（4）多機器人路徑規劃

需要新的方法來進行多機器人路徑規劃，因為移動機器人正在進入新的環境并提供更多的服務。需要包括動態環境的不確定性（如交通、變化的行進路徑和距離、區域內的變化的服務點和不同的服務活動）的方法來確定多機器人的協同。此外，需要找到多機器人的最佳比率的方法。仿真建模結合大數據、機器學習和預測分析可以支持這一點。此外，排隊、流動和交通理論可以幫助分析整體避障，作為評估性能改善或降低的一個因素。在多機器人領域，多無人機編隊路徑規劃[138]也是研究的熱門方向，該研究不僅需要考慮多機器人，更需要考慮三維環境的避障問題。也是今后研究的重難點。