機器人路徑規劃中的算法研究綜述

關鍵詞：機器人；路徑規劃；研究綜述

中圖分類號：ＴＰ１８；ＴＰ２４２ 文獻標志碼：Ａ 開放科學（資源服務）標識碼（ＯＳＩＤ）：

文章編號：１００３－３１０６（２０２４）１１－２６６４－０８

０引言

隨著機器人技術的不斷發展，機器人已經滲透到人們生活的各個領域。路徑規劃問題成為機器人領域的一個重要研究方向。路徑優化可以幫助機器人避開障礙物，優化移動距離和時間，并確保機器人的安全性。有很多路徑優化算法可以應用于機器人的路徑規劃，其中最常用的是Ａ-算法［１］、Ｄｉｊｋｓｔｒａ 算法［２］和隨機搜索樹（Ｒａｐｉｄｌｙ-ｅｘｐｌｏｒｉｎｇ Ｒａｎｄｏｍ Ｔｒｅｅ，ＲＲＴ）算法［３］等。這些算法根據機器人的環境、目標位置和轉彎半徑等［４］信息計算出最優的路徑。在實際應用中，還需要考慮環境的動態變化。總的來說，機器人路徑優化是一個復雜而關鍵的任務，涉及算法、模型和環境感知等多個方面。

本文系統地對各種算法在機器人路徑優化中的應用進行總結，根據移動機器人路徑規劃的特點，將其劃分為基于搜索的路徑規劃算法、基于采樣的路徑規劃算法、基于學習的路徑規劃算法和基于智能仿生的路徑規劃算法。隨后對機器人路徑規劃算法進行細分，并對各種優化算法進行介紹，同時總結其優缺點，對機器人路徑優化進行了總結和展望。

１基于搜索的路徑規劃算法

機器人路徑規劃算法的具體分類如圖１ 所示。

１．１Ａ*搜索算法

Ａ*搜索算法的核心思想是通過評估函數ｆ（ｎ）＝ ｇ（ｎ）＋ｈ（ｎ）來決定下一個要擴展的節點，通常選擇曼哈頓距離或者歐幾里得距離作為ｈ（ｎ）。相比于其他盲目搜索算法，Ａ-搜索算法通過使用啟發式信息，減少了不必要的搜索，提高了搜索效率［５］。

針對傳統Ａ*算法存在規劃路徑與障礙物相交、拐角過大和時間長等方面存在的問題，李炯逸等［６］提出了改進的雙向Ａ*二次路徑規劃算法。不僅對地圖進行了膨脹處理，而且引入了新的啟發函數和雙向擴展等方法，引入轉彎代價函數和自適應權重，通過仿真試驗驗證了算法的實用性和平滑性，在搜索時間、路徑長度、拐點和拐角上都有大幅減小。

孫軍艷等［７］針對多自動導引運輸車路徑規劃與避障問題，設計改進Ａ*算法，即對２組數量不同的多自動引導車（Ａｕｔｏｍａｔｅｄ Ｇｕｉｄｅｄ Ｖｅｈｉｃｌｅ，ＡＧＶ）進行路徑規劃與避障仿真，結果表明改進Ａ* 算法的避障總時間、總路徑長度都有明顯的優化。

Ｘｕ等［８］為了減少冗余節點的數量，提出了一種改進的Ａ 算法，將八邊形鄰域替換為無障礙物的矩形邊界，分別從起始點和目標點２ 個方向對地圖進行探索，探索產生了更少的節點。采用自適應代價函數來提高道路安全判別能力，仿真結果表明所提算法能夠有效縮短路徑長度和搜索時間，減少轉彎次數、總轉彎角度和搜索節點數。

１．2Ｄ*搜索算法

Ｄ*搜索算法是一種基于動態啟發式搜索的路徑規劃算法［９］，能夠在環境發生變化時，實時更新路徑，從而有效解決動態環境下的路徑規劃問題。

針對傳統的Ｄ*算法在第一次規劃路徑時遍歷節點和路徑的拐點較多的問題，王飛鵬等［１０］提出了改進雙向Ｄ*算法，通過元胞自動機中的擴展Ｍｏｏｒｅ型鄰居結構降低角度變化的最小增量，融合雙向搜索規則來減少算法的搜索時間，利用二階貝塞爾曲線方程優化路徑，使得路徑無明顯拐點。仿真結果表明，改進后的Ｄ*算法在規劃時間上縮短了３０％左右，搜索的元胞數量減少量近５０％ 。

王帥軍等［１１］針對Ｄ*算法本身存在的缺陷，對算法進行改進。基于沃羅諾伊路線圖法，將目標環境分解為多個局部環境，以局部環境關鍵節點為主，將無用節點舍棄。仿真結果表明，改進后的算法在轉角度數、轉彎次數和規劃時間上均有優化，在目標點變更后，利用沃羅諾伊路徑路線圖，機器人以更小的計算量抵達新的目標點。

１．３Ｄｉｊｋｓｔｒａ算法

Ｄｉｊｋｓｔｒａ 算法是一種經典的最短路徑算法，廣泛應用于路徑規劃領域，以荷蘭計算機科學家艾茲格·迪科斯徹的名字命名［１２］。Ｄｉｊｋｓｔｒａ 算法的基本思想是從起點開始，逐步擴展到其他節點，每次選擇當前未確定最短路徑且距離最小的節點進行擴展。

針對移動機器人在復雜環境下由Ｄｉｊｋｓｔｒａ 算法所規劃的路徑存在較多轉折點等問題，鞏慧等［１３］結合實際場景利用幾何拓撲學方法對Ｄｉｊｋｓｔｒａ 算法進行平滑處理，將連續化地圖離散化，隨機生成離散點陣，將多個點連接并生成離散圖，利用Ｄｉｊｋｓｔｒａ 算法搜索最優路徑作為引導路徑。實驗結果表明，所提算法能夠有效減少累計轉彎角度，提高所規劃路徑的平滑度，有效提升機器人的工作效率。

針對水下機器人的作業要求，車建濤等［１４］將路徑規劃問題分為定深度二維最優路徑和不定深度三維最優路徑兩部分，分別采用多邊形擬合和分層多面體擬合的方法建立水下機器人障礙物模型，利用Ｄｉｊｋｓｔｒａ 算法規劃最優路徑。實驗證明了該方法的正確性和有效性，為進一步實際應用奠定了理論基礎。

１．４深度優先搜索算法

深度優先搜索（Ｄｅｐｔｈ Ｆｉｒｓｔ Ｓｅａｒｃｈ，ＤＦＳ）是一種常用的圖遍歷算法，基本思想是從初始節點開始，沿著一條路徑盡可能深地搜索，直到找到目標節點或無法繼續前進為止，然后回溯到上一個節點，嘗試其他可能的路徑［１５］。這個過程會一直持續到所有可能的路徑都被探索過或者找到目標節點為止。但是，它的缺點也很明顯：不能保證找到的是最短路徑。

王瑞超等［１６］為提高電弧增材制造的成形效率，將ＤＦＳ算法與蟻群（Ａｎt"Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）算法相結合，采用多種不同掃描傾角的路徑算法對多孔洞截面輪廓進行填充，采用ＡＣＯ 算法搜索路徑規劃順序和起弧熄弧點的優化組合，使填充路徑的總空行程長度最小。仿真結果表明，混合算法對不同掃描傾角的路徑規劃皆能起到良好連接作用。

王新彥等［１７］針對割草機器人大面積作業時遍歷路徑規劃覆蓋率低、重復率高的問題，提出一種改進Ａ*算法與ＤＦＳ 算法相結合的遍歷路徑規劃算法。通過牛耕式分解法將目標區域劃分成多個不含障礙物的子區域，根據子區域的鄰接關系構建無向圖，使用ＤＦＳ算法規劃子區域的遍歷順序，然后采用改進Ａ*算法進行跨區域路徑轉移。仿真試驗結果表明了改進算法的有效性。

２基于采樣的路徑規劃算法

２．１ ＲＲＴ算法

ＲＲＴ 算法是一種用于解決最優化問題的啟發式搜索算法，基本思想是通過構建一棵包含所有可能解的樹，并以某種方式對這棵樹進行隨機搜索，從而找到最優解。

鞏浩等［１８］提出一種改進的ＲＲＴ 路徑規劃算法，將概率目標偏置與人工勢場結合以引導隨機樹的擴展，采用基于安全距離的碰撞檢測以及動態變步長擴展策略提高避障能力，將剪枝優化和三次Ｂ樣條曲線對初始路徑進行擬合優化，使規劃的路徑更平滑。仿真結果表明改進后的算法優化了路徑的平滑性、搜索時間、迭代次數等。Ｗａｎｇ 等［１９］提出了一種基于自適應目標偏差和啟發式循環采樣的改進ＲＲＴ算法，所提出的遍歷算法具有覆蓋率高、重復率低、普適性強的特點，為割草機器人遍歷路徑規劃提供了理論參考。

Ｌｅｉ等［２０］提出了改進的運動學約束雙向快速探索隨機樹算法。設計了一種改進的人工勢場法，節點為受運動學約束。引入運動控制參數采樣方法控制隨機擴展樹生成滿足移動機器人約束的路徑節點和軌跡，模擬結果表明改進后的算法在路徑長度和規劃時間上都有大幅減小。Ｋａｎｇ等［２１］提出了一種根據場景信息調整擴展方向和動態步長的雙向路徑規劃方法以提高多自由度機器人在構型空間中的規劃效率。

２．２概率路線圖算法

概率路線圖（Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｒｏａｄｍａｐ，ＰＲＭ）算法是一種隨機采樣方法，通過在環境空間中隨機采樣生成一系列路點，然后連接這些路點形成一個路線圖，在這個路線圖上，可以找到從起始點到目標點的最短路徑，即為目標最優路徑。

針對ＰＲＭ 算法在狹長封閉的巷道中難以保障采樣的節點分布均勻導致路徑規劃失敗或無效等問題，薛光輝等［２２］提出了一種改進ＰＲＭ 算法。引入了人工勢場法，將落在障礙物中的節點沿與其距離最近自由空間中的節點連線方向推至自由空間，實現節點的均勻分布，在障礙物的邊緣建立斥力場，使其與障礙物有一定距離。仿真結果表明，改進的ＰＲＭ 算法提高了路徑規劃的安全性，規劃的路徑更平滑，長度更短。

為保持雙機械手焊接龍門系統的效率，Ｚｈｏｕ等［２３］提出了一種基于規則的帶斥力場的惰性ＰＲＭ算法，結合了人工規則和斥力場，還考慮了機械手、焊槍和龍門架之間的協調運動在笛卡爾空間中規劃路徑。仿真結果證明了其在解決弧焊龍門系統無碰撞在線路徑規劃問題中的有效性。

徐大也等［２４］提出一種結合萊維飛行和ＰＲＭ 算法的路徑規劃算法。應用萊維飛行方法提升狹窄區域的采樣質量與效率，采用分段貝塞爾曲線對路徑軌跡進行優化使其符合運動學約束，提高移動機器人的機動性。仿真結果表明，改進后的算法規劃成功率顯著提高，路徑更優，能提高整體工作效率。

３基于學習的路徑規劃算法

３．１人工勢場法

人工勢場法的基本思想是將環境模型化為一個勢場，其中每個位置都對應一個勢能值。目標點具有負勢能，障礙物具有正勢能。移動設備通過計算當前位置與目標點和障礙物之間的勢能差，選擇勢能下降最快的方向進行移動，從而避開障礙物并最終到達目標點。

受新冠疫情的影響，醫療配送機器人開始逐步出現在各大醫療機構中，針對人工場勢法局部最優解問題，劉澳霄等［２５］提出了設計虛擬目標點的方法將機器人從局部最優狀態解救出來；引入了目標距離函數對障礙物斥力進行限制，從而解決目標不可達問題。實驗結果表明，提出的改進算法能夠有效運用于實際場景。

針對自由飛行空間機器人的無碰撞路徑規劃問題，Ｇｕ等［２６］提出了一種自適應人工勢場，即能量最優的避碰策略。通過在斥力勢場中引入平滑衰減函數，對吸引勢場的時變整形參數進行優化，當系統陷入局部極小值時，基于優化理論設計了一個逃逸力來代替人工勢力源，方向向量引導其以最小的能量跳出局部極小值。通過仿真結果驗證了所提方法的有效性。

針對傳統人工勢場法存在目標不可達和局部極小值問題，倪建云等［２７］提出一種改進的人工勢場法。對斥力場函數改進以解決目標不可達問題，提出一種橢圓形目標策略和跟蹤策略逃離局部極小值，采用Ｂ樣條曲線對規劃出的路徑進行擬合處理，結果表明經樣條曲線處理后的路徑比原路徑平滑。

３．２動態窗口算法

動態窗口算法（Ｄｙｎａｍｉｃ Ｗｉｎｄｏｗ Ａｐｐｒｏａｃｈ，ＤＷＡ）是一種基于模型預測控制的方法，核心思想是在機器人的當前狀態附近建立一個“窗口”，在這個“窗口”內搜索最優的控制策略，使得機器人能夠盡快到達目標位置。

馬宗方等［２８］提出一種改進的ＡＣＯ 算法與ＤＷＡ 相結合的混合算法。引入自適應調整信息素揮發系數，融合角度參數建立車庫方向信息素矩陣，在局部規劃中設計基于橢圓方程的障礙物距離評價子函數的改進ＤＷＡ。仿真結果表明，改進算法更符合ＡＧＶ 實際作業過程中在多重環境因素的影響下的動態規劃要求。

Ｙａｏ等［２９］提出了一種模糊邏輯改進的ＤＷＡ。建立驅動電機的能耗模型用于擴展ＤＷＡ 的評價函數，分別基于方向規則、安全規則和融合規則設計了３ 個模糊邏輯控制器，實時輸出權重參數，提高了魯棒性。仿真結果表明，改進后的算法生成路徑更短，驅動電機能耗更低。

Ｌｉｕ等［３０］提出了一種將Ａ*算法與ＤＷＡ 相結合的融合算法，改進了Ａ*算法的節點擴展方法和啟發函數模型，提高了搜索效率，減少了路徑彎曲次數，優化了ＤＷＡ 的軌跡評價函數，使得ＤＷＡ 規劃的局部路徑更加平滑連貫，更易于機器人運動執行。通過仿真驗證了本文提出的融合算法的有效性。

３．３強化學習算法

強化學習（Ｒｅｉｎｆｏｒｃｅｍｅｎｔ Ｌｅａｒｎｉｎｇ，ＲＬ）算法是一種數據驅動的方法，不需要預先知道環境的具體信息，只需要通過不斷的嘗試和學習，就可以逐漸找到最優的路徑。ＲＬ 能夠處理復雜的環境和動態變化的情況，這對于實際應用中常見的不確定性和變化性有著很好的適應能力。

針對移動機器人的長距離避障導航問題，康振興［３１］提出結合深度ＲＬ 和路徑規劃的避障導航算法。根據生成的路徑節點，將長距離路徑劃分為若干短距離，再利用深度ＲＬ 的算法訓練一個具有環境感知和智能決策能力的端到端避障導航模型。仿真實驗表明，該方法解決了深度強化學習（Ｄｅｅｐ Ｒｅ-ｉｎｆｏｒｃｅｍｅｎｔ Ｌｅａｒｎｉｎｇ，ＤＲＬ）在長距離避障導航任務上的局限性問題。

馬天等［３２］提出一種基于ＤＲＬ 的移動機器人路徑規劃方法。在有限空間下采用深度圖信息作為智能體的輸入，模擬復雜的三維空間環境，設計了兩階段離散動作空間下的動作選擇策略，添加門控循環單元結合歷史狀態信息，以提升未知環境中搜索策略的穩定性，進而提高規劃路徑準確度和平滑度。

圍繞紡織機械臂的自動路徑規劃，Ｚｈａｏ 等［３３］提出了一種融合深度ＲＬ 的端到端規劃與控制模型。引入了級聯模糊獎勵制度，將其融入到端到端模型中，增強學習效率，減少無效探索，從而加快模型的收斂。在模擬環境中進行的一系列實驗證明了該模型在紗線－線軸－裝配任務中的出色表現。

為了避免算法陷入次優解，Ｚｈａｏ等［３４］使用了一個無模型的、由逆運動學經驗指導的深度ＲＬ框架，將環境增強策略與基于多信息熵的幾何優化相結合，顯著提高了智能紡織機械臂的操作效率和安全性，為實際智能針織應用中的路徑規劃提供了開創性和實用性的解決方案。

４基于智能仿生的路徑算法

４．１粒子群優化算法

在粒子群優化（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）算法中，每個個體（粒子）都含有自身屬性，包括位置和速度，這些粒子在搜索空間中移動，以找到最優解。ＰＳＯ 算法具有較強的魯棒性，能夠處理各種復雜的路徑規劃問題。

Ｃｈｅｎ 等［３５］針對一種核電站巡邏機器人路徑規劃問題，考慮到最短長度和最小風險度的沖突，采用區間多目標ＰＳＯ方法，根據每個風險度區間的擁擠距離對粒子的全局最優位置和局部最優位置進行巧妙的區間更新，以增加種群的多樣性，通過仿真實驗驗證了所提方法的有效性。羅陽陽等［３６］利用突變算子增加粒子種群多樣性，并小范圍對粒子的位置采用突變策略進行更新，以防止ＰＳＯ算法易陷入局部最優的問題，并且應用機器人運動學原理跟蹤所有規劃的路徑點。

Ｆｅｒｎａｎｄｅｓ 等［３７］針對移動機器人在靜態和動態環境下的軌跡規劃任務，提出了增強多樣性的ＰＳＯ算法，該算法的主要特點是其種群可以使自身有效地逃離局部極小值，避免粒子停滯，所提出的算法參數使用基準測試函數，隨后對改進的算法在４ 種復雜的環境中進行模擬，驗證了算法的有效性。

為了增強ＰＳＯ群體尋找最優機器人路徑的全局搜索能力，并保持ＰＳＯ 群體的開發和探索之間的平衡，Ｐａｎｄｅｙ等［３８］研究了移動機器人的軌跡規劃和導航控制問題。為了實現研究目標，使用基于懲罰的方法開發了自適應ＰＳＯ 運動算法，為了向機器人提供最佳或無碰撞的位置，在目標搜索動作期間同時比較全部隨機定位的粒子的適應度值，通過比較適應度值，使機器人在搜索空間中占據最佳位置，直至到達目標。將所提的自適應ＰＳＯ 結果與現有導航技術的結果進行了比較，改進幅度為１１．３０％ 。

４．２ＡＣＯ算法

ＡＣＯ 算法是一種模擬自然界中螞蟻尋找食物路徑的優化算法，它在路徑規劃、網絡路由和組合優化等領域有著廣泛的應用。

針對ＡＣＯ 算法易陷入局部最優、路徑轉折點多等問題，潘玉恒等［３９］提出一種基于動態擴展鄰域ＡＣＯ 算法并定義新的信息素計算方式和增量規則，引入自適應調整因子改進啟發函數提高算法的全局搜索能力，并設定迭代閾值，提升算法的收斂速度。仿真實驗表明，改進的算法具有更高的可行性和適用性。王豐等［４０］提出了基于動態更新狀態轉移規則的ＡＣＯ 算法。通過人工勢場法改進啟發函數，利用偽隨機狀態策略改進狀態轉移規則，引入動態信息素更新方式，通過仿真驗證證明改進算法有效提升了機器人全局路徑的平滑性和安全性。

Ｃｕｉ等［４１］提出了一種多策略自適應ＡＣＯ算法，提出了一種方向引導機制來提高節點選擇的性能，引入自適應啟發函數來減少最優路徑解的長度和轉彎次數。采用確定性狀態轉移概率規則來提高ＡＣＯ的收斂速度。隨后，利用非均勻信息素初始化增強ＡＣＯ對優勢區域的選擇能力。對策略的主要參數進行了優化，并驗證了其有效性。

Ｈｕｏ等［４２］提出了一種基于轉角約束的改進ＡＣＯ算法。加入了距離因子和轉向角懲罰因子，減少了路徑搜索的盲目性。此外，改進了信息素更新方法，采用獎勵懲罰機制提高算法的收斂速度和增加全局最優路徑的信息素濃度。實驗結果表明，所提方法為復雜環境下的阿克曼移動機器人提供了一種高效、平滑的路徑規劃解決方案。

４．３其他仿生算法

在機器人路徑規劃問題中，除ＰＳＯ算法和ＡＣＯ算法最常用外，還有很多仿生算法被應用于機器人路徑規劃。

為解決海洋捕食者算法收斂速度慢、收斂精度低、易陷入局部最優的問題，黃訓愛等［４３］提出一種多策略改進海洋捕食者算法。引入混沌映射初始化種群，增加捕食者種群多樣性；設計出自適應移動步長動態調整策略，增強算法逃離局部最優的能力。仿真結果表明，該算法規劃的路徑長度更短，搜索效率更高。

為了同時規劃多個機器人的最優無碰撞路徑，Ｃｕｉ等［４４］提出了一種改進的人工蜂群算法。為了更好地引導搜索方向，在雇傭蜂階段和偵察蜂階段的搜索方程中引入全局最優個體。在觀察蜂階段融入教與學優化算法的學習方法。仿真結果證明了改進后的算法在生成最優無碰撞路徑和運行時間方面優于競爭對手。

５結束語

以上幾種算法各有優勢，但也有各自的缺陷，在具體場景中通常會對其做出改進，不僅可以優化自身的參數，還可以根據具體的應用場景和需求靈活選擇其他算法以提高算法性能。

比如王志特等［４５］針對機器人路徑規劃對于路徑最短、搜索效率以及平滑度的性能要求，提出一種改進Ａ*算法與改進ＤＷＡ相融合的算法。張曉倩等［４６］針對傳統ＡＣＯ算法搜索效率慢及無法實時避障的問題，提出了將改進的ＡＣＯ 算法與ＤＷＡ 融合的動態路徑規劃方法。張振等［４７］基于全向移動機器人提出了一種改進Ａ*算法與ＤＷＡ 相融合的實時路徑規劃方法，將２ 種算法融合規劃出一條基于全局最優的圓滑曲線路徑。時維國等［４８］將ＡＣＯ 算法與人工勢場法相融合，以提高算法在復雜的靜態和動態環境中具有極高的環境適應性和路徑規劃效率。為了解決機器人路徑規劃中傳統Ａ*算法和ＤＷＡ存在的遍歷節點較多、冗余點較多等問題，劉宇庭等［４９］將二者結合。針對智能工廠內部裝修中的工作區分割線、設備布局線勾畫的路徑優化問題，周偉等［５０］提出了一種基于Ａ*算法與改進鯨魚算法相結合的混合算法。為了克服麻雀搜索算法的局限性和移動機器人動態避障的挑戰，Ｈｏｕ等［５１］引入了增強型麻雀搜索算法與ＤＷＡ 相結合的集成方法。針對巡檢機器人需在復雜環境下多任務點遍歷巡檢路徑規劃問題，宋文清等［５２］提出一種多策略差分擾動機制改進的堆優化算法。

通過對機器人路徑規劃方法進行的總結和展望，可以發現未來的研究方向將集中在提高算法的穩定性、適應性，研究新型智能優化算法以及結合其他優化方法等方面。隨著這些研究的不斷深入和應用領域的拓展，算法將在解決機器人路徑規劃問題中發揮更加重要的作用。

作者簡介

郭小瑩 女，（１９９９—），碩士研究生。主要研究方向：生產管理系統工程。

（*通信作者）趙淑蘋 女，（１９７９—），博士，副教授，碩士生導師。主要研究方向：企業人力資源管理。