路徑規劃算法的研究綜述

林梓健 劉凱 林群煦

摘? 要：路徑規劃算法廣泛應用于機器人、無人駕駛設備、自動導航等領域，是推動自動化和智能化發展的技術支撐。文章對幾何搜索算法、智能搜索算法、人工智能算法、混合算法和局部規劃算法等路徑規劃算法進行了簡要介紹，內容包括若干典型算法以及由不同算法相互模仿混合而成的混合算法的特點、優缺點和重要改進。對路徑規劃算法的發展趨勢進行總結，對路徑規劃算法的發展前景進行展望，以期為相關的研究提供參考。

關鍵詞：路徑規劃；算法綜述；自動導航

中圖分類號：TP242? 文獻標識碼：A? 文章編號：2096-4706（2023）04-0075-06

Research Review of the Path Planning Algorithms

LIN Zijian， LIU Kai， LIN Qunxu

（School of Rail Transportation， Wuyi University， Jiangmen? 529020， China）

Abstract： The path planning algorithms are widely used in robots， driverless equipments， automatic navigation and other fields， and they are the technical support for promoting the development of automation and intelligence. This paper briefly introduces path planning algorithms such as geometric search algorithm， intelligent search algorithm， artificial intelligence algorithm， hybrid algorithm and local planning algorithm， including the characteristics， advantages and disadvantages and important improvements of several typical algorithms as well as hybrid algorithms formed by mutual imitation and mixing of different algorithms. Summarize the development trend of path planning algorithms， and prospect the development prospect of path planning algorithms， in order to provide reference for relevant research.

Keywords： path planning; algorithm review; automatic navigation

0? 引? 言

路徑規劃是機器人、自動駕駛等領域里的一個重要部分，包括移動設備的路徑規劃、機械臂的軌跡規劃等內容。規劃良好的路徑對設備的工作能力和工作效率，乃至工作場所的安全等要素有至關重要的影響。本文將介紹其中一些典型的算法，如圖1所示，分為幾何搜索算法、智能搜索算法、人工智能算法、混合算法和局部規劃算法5個部分進行介紹。

1? 幾何搜索算法

1.1? A*算法

A*算法是一種經典的尋路算法，該算法的核心公式是每一步的代價G加估算代價H得到總代價F，常用的H是“曼哈頓距離”，此外也有歐氏距離、對角線距離等可以選擇，系統選擇F最小的路線作為結果。該算法計算快，應用廣泛，但考慮的信息較少，得到的路徑會不夠平順或出現多余的段落。

Zhang[1]等人通過加進類似人工勢場法的目標引力和障礙物斥力，把合力作為一個要素加進A*算法的代價函數里，使得改進后的算法更充分考慮地圖信息，并用B樣條曲線進行平滑處理，得到比傳統A*算法更平順更合理的路徑，在實驗中同樣直線距離的情況下算法會選擇更平直、更少轉彎的路線。Tang[2]等人通過設置函數對傳統A*算法的路徑進行過濾修整，去除交叉或鋸齒形等不合理的路徑，并用B樣條曲線平滑處理，得到更合理、更適合設備執行的路徑。Hong[3]等人通過優化數據結構，并且讓算法在距離目標點只剩一段距離之前不執行傳統A*算法中搜索終點是否在列表中的步驟，因為在大部分時間里這一步都是沒什么意義的，尤其是在尺寸比較大的地圖上，因而大大提升了計算速度和適用范圍。

1.2? Dijkstra算法

Dijkstra算法是一種經典的路徑搜索算法，該算法基于貪婪策略，從起始點開始，一層層地向外搜索直到到達目標。不過傳統的Dijkstra算法有不考慮平滑度等局部情況、某些情況下計算量大和計算復雜、搜索速度慢等不足。

Sun[4]等通過改進讓Dijkstra算法在8個方向上進行搜索，得到比4個方向進行搜索的傳統Dijkstra算法更平順、更優化的路徑。Dijkstra算法的不足也可以通過與其他算法混合使用以彌補，比如Zhao[5]等使用Dijkstra算法搜索初始的路徑后，再使用蟻群算法進行進一步優化。

1.3 Voronoi圖算法

Voronoi圖是一種基于幾何圖形的路徑規劃算法，該算法先按移動設備的尺寸等條件給障礙物“膨脹”處理確保安全距離，并且提取特征點，然后按邊界與兩特征點保持相同距離的方式把區域劃分成若干單元，得到Voronoi圖路徑，邊界線就是可行路徑。

Huang[6]等在傳統的Voronoi圖算法的基礎上，通過在兩個機器人相遇時在低優先權的機器人上添加Voronoi特征點使低優先權的機器人使用的Voronoi圖和路徑發生改變并繞開高優先級機器人的方式，進行多機器人的路徑規劃。AL-Dahhan[7]等通過在傳統的Voronoi圖得到的初步結果上，刪除一些不必要的點，增加一些新的引導點，使路徑得到進一步優化。Chi[8]等通過1個特征矩陣“過濾”傳統的Voronoi圖得到的特征點，刪除不必要的特征點，得到更優化的路徑。

2? 智能搜索算法

2.1? 蟻群算法

蟻群算法由Dorigo[9]提出，源于對螞蟻尋找食物的研究，螞蟻釋放信息素也受已有信息素的影響 ，在一定的時間后螞蟻們會由于信息素而集中在比較理想的路線上。隨后出現了精英蟻群算法、極大極小值蟻群算法、等級蟻群算法等改進[10]。該算法被廣泛使用，是效率和適用性很高的一種算法。但是蟻群算法有陷入局部最優解、過度依賴信息素、初始時盲目搜索等不足。

Abolhosein[11]等人通過讓蟻群算法的每一次更新都按一定的權重考慮前面已經獲得結果，設計了一種“帶有記憶”的動態蟻群算法，每次更新都在考慮已有結果的基礎上進行而不是地圖稍有改變就從頭開始搜索，大大減少了動態環境下所需的計算時間。Pohan[12]等人通過讓啟發函數不只是考慮當前節點到下一節點的距離，也考慮節點到目標點的距離來設定啟發因子，使得螞蟻不必搜索所有節點，也不必每次都搜索最接近的下一個節點，減少了搜索的盲目性，提高了效率。Zhang[13]等人通過在更新信息素時考慮當下迭代得到的最優解和目前最流行的解，額外增強兩者共同包括的節點的信息素，并且讓信息素能輻射出去影響周邊的其他節點，增加了螞蟻之間的協作性，比傳統的蟻群算法能獲得更快更優化的路徑。Li[14]等人通過引入適應策略，根據信息素的濃度動態調整各點信息素的揮發系數，不讓系統過早收斂而陷入局部最優解，增加了系統的全局搜索能力。Song[15]等在已有的精英蟻群算法基礎上引入序列，找出一群精英螞蟻并排序，同時在信息素更新環節加入模糊邏輯，不僅提升了蟻群算法的計算速度和動態環境搜索能力，還能同時考慮多種其他條件的約束而不只是最短路徑。

2.2? 遺傳算法

遺傳算法由約翰·H·霍蘭[16]等人提出，模仿遺傳物質在適應環境的過程中優勝劣汰，使遺傳物質得到優化。該算法讓各個解進行交換、突變、繁殖復制，淘汰不能適應的解，由“適應度”決定繁殖和淘汰。在著作中約翰·H·霍蘭解釋道，突變的作用是以免過早收斂陷入局部最優解，比如一個早先因某些原因恰好被刪掉的信息，是有可能在遇到其他信息后組合出更好的解的，還能增加多樣性；而交換則能在大程度保持眾多優秀小片段的同時，打亂由這些小片段組成的大片段來增加多樣性，實現眾多小片段逐漸優化，同時由這些小片段組合出多樣的大片段以供選擇，并且這兩個操作都能擴大搜索空間，使搜索不局限于初始條件。遺傳算法不斷改進以提高搜索能力，緩解該算法計算量大、計算時間長等不足。

Wang[17]等人在傳統的遺傳算法的基礎上，增加了直接保留適應度高的個體，刪除和替換掉效果不太好的基因段的步驟，提高了遺傳算法的計算速度和求解性能。Xing[18]等人通過引入精英直接復制到下一代和分組進行適應不同的目標，然后混合并在下一代再分組適應不同目標的策略，提高計算速度的同時使得改進后的遺傳算法能求解多目標的優化問題。Li[19]等在傳統的單一種群進行求解的遺傳算法的基礎上，設置若干個種群同時求解，并通過“遷徙”讓種群之間互相流通，改進基因交叉的算法，并且也設置讓較優的個體直接保留下來，提高了算法的性能和求解速度，如圖2所示。

Li[20]等為適應度判別引入了獎懲因素提高搜索能力，并且每輪搜索直接保留第一維基因里的優秀個體，和由這些優秀個體產生二維基因，使得遺傳算法能求解多維度的問題。遺傳算法的突變和交叉概率是一個重要的改進方向，比如袁夢飛[21]等讓群體在早期擴大突變和交叉的概率以擴大搜索空間，后期則減少突變和交叉的概率以加速收斂，提高了算法的搜索性能和計算速度；王吉岱[22]等通過模糊推理設置動態的突變概率和交叉概率，在種群適應度方差過低或進化速度過慢時增大概率，擴大搜索空間和避免系統早熟或陷入局部最優解，反之則減小概率，加速算法的收斂。

2.3? 人工勢場法

人工勢場法來自對物理學的力場的模仿，讓目標發出“吸引力”，障礙物則發出“排斥力”，形成一個組合力場。該算法簡單而高效，廣泛應用在局部路徑優化、避障等。但是該算法也有一些明顯的不足，例如陷入力平衡而鎖死，由于排斥力的作用要和障礙物保持一端距離導致路線有時候達不到最短、在目標周圍或前往目標的途中的障礙物的排斥力使得機器人無法前往目標點等問題。

針對陷入力平衡的死鎖問題，以往有通過增加虛擬障礙物或虛擬目標打破死鎖的做法，主要是隨機添加的，但該方法被認為不穩定，甚至導致偏離目標。Yuan[23]等通過在陷入死鎖時，計算一個相鄰范圍內的障礙物數量和整個空間的障礙物數量，并由此數量關系產生額外的斥力使得路線因此發生膨脹繞開死鎖地點。Yang[24]等人通過在目標點附近添加一些虛擬目標點供路線陷入死鎖時切換目標為這些虛擬目標點以脫離死點，并且在距離目標點小于某設定值后，使吸引力保持為常數或增大，確保路線能到達目標點，如圖3所示。

Wang[25]等通過在判斷有陷入死鎖的危險時，在行進物體與臨近的某選定障礙物的連線方向上添加額外的“逃脫力”以脫離死鎖狀態。Yao[26]等人在傳統的人工勢場上，在目標點附近施加極大的吸引力，而全局的吸引力則緩慢變化，使得每個目標點成為一個“黑洞”，緩解了傳統人工勢場法中可能由于多個目標的吸引力達成平衡而死鎖的問題，提高了算法解決多目標問題的能力。He[27]等人讓目標物的吸引力不是按傳統方式那樣與距離成正比，而是會變化的，以免過大的吸引力導致撞上障礙物。Wang[28]等人讓人工勢場法搜索陷入死鎖時，沿著障礙物的外表進行“沿墻壁搜索”以脫離死鎖，并讓人工力場外部引導前往目標，內部用于保持間距，應用于多機器人路徑規劃。

2.4? RRT算法

快速搜索隨機樹算法簡稱RRT算法，該算法模仿1棵樹隨機地生長，直到“發芽點”與終點連接上，雙向版本的RRT則模擬2棵樹隨機生長直到兩棵樹的樹枝連接上。該算法原理簡單但是計算量大，而且在一些狹窄通道處難以搜索。

傳統的RRT算法要遍歷整個空間里的所有節點去尋路，導致大量的時間消耗和計算量，Zhou[29]等人提出一種“Cell method”方法，把搜索空間分成若干個尺寸相同的單元，每次搜索優先在節點所屬的單元內搜索，大大減少了計算量。Kang[30]等人提出一種“三角形重連接”的方法，如圖4所示，在已有的RRT算法得到的結果的基礎上進行檢查，如果3個節點之間的連線長度（q1q2和q2q3長度之和）大于首尾兩節點的距離（q1q3的長度），則刪除原來的連線（q1q2和q2q3），重新連接為直接連接收尾的2個節點q1和q3，大幅度優化了路線。

Chen[31]等人在起點和終點之間設置中點為第三點，然后讓4棵搜集樹從這3個點之間相向地同時開始搜索，并且通過公式修正隨機采樣點，讓隨機樹的每一次生長都有意地傾向于終點所在的方向，極大地提高了計算速度。

2.5? PRM算法

概率路線圖算法簡稱PRM算法，該算法的原理是在地圖上撒播一些隨機采樣點，然后刪除不合理的點，再把剩下的點互相連接成線，從這些連線里選取組成最短路徑的若干線段作為輸出結果。該方法最大的特點是采樣點越多結果越好，但同時采樣點越多計算量就越大。

傳統的PRM算法在障礙物比較多的地方效率下降，因為很多落入障礙物的采樣點被直接刪除掉了，為此Chen[32]等人引進了一個“虛擬力”的作用，把落在障礙物范圍內的采樣點，按最快離開障礙物范圍的方向施加一個力的作用，把這些采樣點送回可行空間內的邊界位置上，提高了采樣點的使用率，提高了算法的搜索能力。Xu[33]等人為PRM算法引入一種動態的策略，完成一段路徑后在新的環境里撒播采樣點連接已有的采樣點網絡，充分利用已有的信息，并且只允許互相保持了一定間距的采樣點為有效采樣點，大大提升了計算效率和面對動態環境的能力。Ravankar[34]等人把地圖分成若干區域，區域再細分為網格，然后根據區域和網格里障礙物的情況設置一個“斥力值”，障礙物越多該數值越大，搜索時只在斥力值低于所在區域的平均斥力值的網格里撒播采樣點，并且每個區域的總采樣點數固定，使得采樣點集中在可通行區域里，提高了計算速度和效率。

3? 人工智能算法

3.1? Q-Learning

Q-Learning（Q學習）是強化學習的一種，其原理是模仿生物的學習行為，獲得獎勵的行為更傾向于再次去做，受到懲罰的行為則傾向于去避開。在學習過程中，系統讓agent去嘗試和學習，探索外界環境，尋找更優的行事方式。Q學習的學習過程中每處于一個狀態，agent就會選擇當下已知的Q值最高的行為去執行，并由環境的反饋不斷更新Q值表。Q學習如今在機器人等領域已獲得廣泛應用，在一些領域甚至表現得比人工表現更好。而Q學習在起始階段隨機、盲目地搜索，有些易損壞環境下不適宜讓系統盲目試錯、計算量大和耗費時間長等不足，也在實踐的過程中逐漸獲得改善。此外Q學習可以與神經網絡結合組成DQN算法。

傳統的Q學習在初始的時候Q值表全部內容置為0，然后agent開始盲目隨機地探索，浪費了計算時間和資源，Low[35]等人在初始時通過FPA算法給Q值表賦予初始值，實驗結果表明合理地賦予Q值表初始值能大程度提高系統的學習效率和速度。同樣為了減少盲目搜索的浪費，Sun[36]等給Q學習加入了對比類似情況的環節，在新環境中對比位置、能耗等因素，從已有經驗中獲得幫助加速學習，提高了Q學習面對動態和新環境的性能。Li[37]等人使用基于與Q值相關的概率選擇策略取代傳統Q學習的選擇最大Q值的策略，減少噪音影響和陷入局部最優解的幾率，并通過引入來自相關任務領域的先驗知識和設定先驗規則加速系統訓練。

3.2? 深度學習

深度學習是近年來人工智能領域里的一個新興技術，如圖5所示，該技術模仿人的大腦和神經系統，在提供充足的數據時能輸出良好的結果，目前已經廣泛應用在數據分析、機器視覺、信號處理等領域。深度學習技術也可以用在路徑規劃領域，并且可以和其他算法結合獲得很好的實驗結果。比如混合算法段落將介紹的Hamdia[38]等人結合深度學習和遺傳算法。Abdi[39]等人結合Q-Learning和深度學習，讓前者負責學習機械臂的軌跡規劃和避障，后者則負責學習機械臂的末端執行器的各關節角度，根據這兩類任務的特點，分別發揮兩種算法的優勢，節省了大量的計算時間和計算量。

4? 局部規劃算法

4.1? DWA算法

動態窗口算法簡稱DWA算法，該算法不需要完整的地圖環境信息，而是在指定環境空間內，通過移動機器人自身傳感器不斷獲取周圍的最新信息和環境變化，對每一時刻的速度空間的線速度vt和角速度wt進行多組采樣，如圖6所示，再結合當前移動機器人的狀態對未來可能運動的軌跡進行預測，通過算法對每條路徑進行打分，判斷出分數最高，即距離目標最短以及最快到達的路徑，獲取可下達的對應最佳速度，最后選取并發布至下位機實現導航。

傳統的DWA算法在復雜環境下生成的路徑不平滑，Xiang[40]等針對原DWA的評價函數權系數不變的情況，采用模糊控制器算法，加入航向角的變化，并與模糊控制器結合獲取較低的航向角變化率，使路徑更平穩，避免角度變化過大。Chang[41]等基于強化學習動態調整DWA參數，提高了規劃成功率。在人類相似性方面，傳統DWA結果較差，因此Ballesteros[42]等提出BDWA，BDWA定義一種新的獎勵功能，這種獎勵功能通過聚類從志愿者在醫院環境中使用被動滾輪的真實導航軌跡中提取的，以產生與需要滾動器的人類非常接近的軌跡，使DWA能模仿真實行人軌跡，平衡了人類相似性和安全約束。

4.2? 局部優化算法

使用軌跡規劃算法得到的路線往往不夠合理，帶有銳角或直角的轉角、不必要的曲折、走回頭路等不合理因素使得不便于馬上讓機器人執行。因此可以使用一些局部優化算法進行優化，得到更合理的路線。常用的局部優化算法有平滑處理、考慮速度和加速度變化的五次多項式、貝塞爾曲線、B樣條曲線等。

Wang[43]等把軌跡分為3個部分，分別設置開始時加速度為0、結束時加速度為0以及運行中軌跡的三階導數連續，3個約束條件，獲得比傳統B樣條曲線更平穩和精確的改進B樣條曲線。古勁[44]等人通過曲線首末端切矢條件反求曲線上的點進行插補計算，提出了一種比傳統B樣條曲線更平滑、更光順的改進三次B樣條曲線軌跡，實現G2級連續。Luan[45]等人結合A*算法和貝塞爾曲線，在A*算法得到的點的基礎上應用分段三次貝塞爾曲線，并考慮機器人的起始和終止運動時刻，得到C2級連續光順的曲線。

5? 混合算法

各種路徑規劃算法各有特點各有優劣，因此在單個算法進行改進之外，人們也嘗試把不同的算法混合起來，取長補短優勢互補，有時能取得單一算法難以得到的效果。

Yuan[23]等結合RRT算法和人工勢場法，在相對空曠的地方采用人工勢場法快速求解，在遇到障礙物時用RRT算法避障，該混合算法一方面緩解了RRT算法計算慢的不足，另一方面避開了傳統人工勢場法當障礙物在目標點旁邊時會導致到達不了目標點的缺陷。Zeng[46]等人結合RRT算法與迪杰斯特拉算法，先用RRT算法連接起始點和目標點，然后再用迪杰斯特拉算法在前者得到的結果的基礎上搜索最優路徑。Hamdia[38]等結合神經網絡深度學習和遺傳算法，讓遺傳算法優化神經網絡的一些參數，比如網絡的層數、每層的神經元數等，比傳統的神經網絡深度學習提高了很高的效率。Chen[47]等人結合人工勢場法和PRM算法，讓障礙物發出排斥力，迫使采樣點必須遠離障礙物直到可以認定排斥力為0的距離或位于兩個障礙物之間的“力平衡點”，從而省略了傳統的PRM算法的碰撞檢查部分，提高了算法的計算速度。如圖7所示。

Li[48]等人結合遺傳算法和A*算法，使用A*算法的成本函數作為啟發信息，加速遺傳算法的計算收斂和獲得最優結果。Wang[28]等人結合人工勢場法和Q學習，讓人工勢場法在外部條件約束下規劃路徑同時讓Q學習在實際經驗中學習進行具體調整和優化路徑。Chen[49]等人結合蟻群算法和人工勢場法，使用蟻群算法規劃全局的路徑，然后使用人工勢場法進行局部避障，并根據周圍障礙物的情況動態調整步幅，以在未知的環境下進行路徑規劃。He[27]等在人工勢場法陷入死鎖時，啟動模擬退火算法以脫離死鎖點。

6? 結? 論

本文介紹了一些常用的路徑規劃算法以及它們的特點、優缺點和改進。以下對路徑規劃算法的發展趨勢和前景做一展望：

（1）混合算法把不同特點的算法結合起來使用，取長補短優勢互補，這些混合算法展現了強大的搜索能力，能彌補原來的單一算法的不足，甚至青出于藍而勝于藍，達到比原來的單一算法更好的效果。

（2）有一些算法會經歷一個盲目、隨機搜索的階段，比如傳統的蟻群算法，或者收斂的過程可能陷入振蕩或死鎖，比如傳統的人工勢場法，這些缺陷制約了計算效率和計算速度，因此縮減甚至消除這些缺陷是重要的改進方向。

（3）在路徑規劃的同時，也要考慮到相關設備的特殊要求，比如動作或線路是否平穩流暢、路徑是否足夠安全、考慮設備的慣性和受力狀況等。在多機器人協同、多移動設備等領域，還要考慮多設備之間的協調、防撞、隊形等要求。此外，應急能力也是一個重要的研究內容，比如設備突然被障礙物干擾或阻擋、多個設備的路徑發生沖突等。

（4）為了讓算法更廣泛適用，如何讓設備一邊探索未知的環境一邊進行路徑規劃、如何減少算法的計算量和提高計算效率以降低算法對設備條件的要求等改進，也是重要的研究內容。

盡管有些情況下可能為了綜合性能，而需要付出一些計算時間或精度的代價，但路徑規劃算法領域已獲得的進步是令人矚目的。此外，隨著如今相關領域積累的日益豐富的經驗，性能發展迅速的軟硬件設備，以及機器學習、傳感器、物聯網、激光雷達、機器視覺等高新技術的結合下，路徑規劃算法將走向更強大的未來，發揮更大的作用。

參考文獻：

[1] ZHANG J，WU J，SHEN X，et al. Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star [J/OL].International Journal of Advanced Robotic Systems，2021，18（5）：[2022-08-20].https：//doi.org/10.1177/17298814211042730.

[2] TANG G，TANG C，CLARAMUNT C，et al. Geometric A-Star Algorithm：An Improved A-Star Algorithm for AGV Path Planning in a Port Environment [J].IEEE Access，2021，9：59196-59210.

[3] HONG Z H，SUN P F，TONG X H，et al. Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map [J/OL].ISPRS International Journal of Geo-Information，2021，10（11）：[2022-08-20].https：//doi.org/10.3390/ijgi10110785.

[4] SUN Y H，FANG M，SU Y X. AGV Path Planning based on Improved Dijkstra Algorithm [C]//Journal of Physics：Conference Series.Bijing：IOP，2021，1746（1）：1-7.

[5] ZHAO H L，NIE Z，ZHOU F B，et al. A Compound Path Planning Algorithm for Mobile Robots [C]//2021 IEEE International Conference on Power Electronics，Computer Applications（ICPECA）.Shenyang：IEEE，2021：1-5.

[6] HUANG S K，WANG W J，SUN C H. A Path Planning Strategy for Multi-Robot Moving with Path-Priority Order Based on a Generalized Voronoi Diagram [J/OL].Applied Sciences，2021，11（20）：[2022-08-20].https：//doi.org/10.3390/app11209650.

[7] AL-DAHHAN M R H，SCHMIDT K W. Voronoi Boundary Visibility for Efficient Path Planning [J].IEEE Access，2020，8：134764-134781.

[8] CHI W Z，DING Z Y，WANG J K，et al. A Generalized Voronoi Diagram-Based Efficient Heuristic Path Planning Method for RRTs in Mobile Robots [J].IEEE Transactions on Industrial Electronics，2022，69（5）：4926-4937.

[9] DORIGO M，GAMBARDELLA L M. Ant colony system：a cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on evolutionary computation，1997，1（1）：53-66.

[10] KASHEF S，ELSHAER R. A Review of Implementing Ant System Algorithms on Scheduling Problems [J].The Egyptian Journal for Engineering Sciences and Technology，2021，36（2）：43-52.

[11] ABOLHOSEINI S，ALESHEIKH A A. Dynamic routing with ant system and memory-based decision-making process [J].Environment Systems and Decisions，2021，41（2）：198-211.

[12] POHAN M A R，TRILAKSONO B R，SANTOSA S P，et al. Path Planning Algorithm Using the Hybridization of the Rapidly-Exploring Random Tree and Ant Colony Systems [J].IEEE Access，2021，9：153599-153615.

[13] ZHANG S C，PU J X，SI Y N. An adaptive improved ant colony system based on population information entropy for path planning of mobile robot [J].IEEE Access，2021，9：24933-24945.

[14] LI C Q，XIAO J，LIU Y，et al. An Adaptive Immune Ant Colony Optimization for Reducing Energy Consumption of Automatic Inspection Path Planning in Industrial Wireless Sensor Networks [J/OL].Journal of Sensors，2021，2021：1-11[2022-08-16].https：//doi.org/10.1155/2021/9960043.

[15] SONG Q，ZHAO Q L，Dynamic Path Planning for Unmanned Vehicles Based on Fuzzy Logic and Improved Ant Colony Optimization [J].IEEE Access，2020，8：62107-62115.

[16] 約翰·H·霍蘭.隱秩序：適應性造就復雜性 [M].周曉牧，譯.上海：上海科技教育出版社，2019.

[17] WANG H J，FU Z J，ZHOU J J，et al. Cooperative collision avoidance for unmanned surface vehicles based on improved genetic algorithm [J/OL].Ocean Engineering，2021，222：[2022-08-16].108612.https：//doi.org/10.1016/j.oceaneng.2021.108612.

[18] XING X G，LIU Y，GARG A，et al. An improved genetic algorithm for determining modified water-retention model for biochar-amended soil [J].CATENA，2021，200：[2022-08-16].https：//doi.org/10.1016/j.catena.2021.105143.

[19] LI J L，LIU Z B，WANG X F. Public charging station location determination for electric ride-hailing vehicles based on an improved genetic algorithm [J/OL].Sustainable Cities and Society，2021，74：[2022-08-16].https：//doi.org/10.1016/j.scs.2021.103181.

[20] LI R H，CHANG Y L，WANG Z C. Study of optimal allocation of water resources in Dujiangyan irrigation district of China based on an improved genetic algorithm [J].Water Supply，2021，21（6）：2989-2999.

[21] 袁夢飛，闞秀，曹樂，等.自適應精英遺傳算法的快遞車路徑規劃 [J].導航定位學報，2021，9（6）：104-111.

[22] 王吉岱，王新棟，田群宏，等．基于改進模糊自適應遺傳算法的移動機器人路徑規劃 [J]．機床與液壓，2021，49（23）：18-23．

[23] YUAN Q N，YI J H，SUN R T，et al. Path Planning of a Mechanical Arm Based on an Improved Artificial Potential Field and a Rapid Expansion Random Tree Hybrid Algorithm [J/OL].Algorithms，2021，14（11）：[2022-08-16].https：//doi.org/10.3390/a14110321.

[24] YANG W L，WU P，ZHOU X Q，et al. Improved Artificial Potential Field and Dynamic Window Method for Amphibious Robot Fish Path Planning [J/OL].Applied Sciences，2021，11（5）：[2022-08-16].https：//doi.org/10.3390/app11052114.

[25] WANG Z，LI G F，REN J. Dynamic path planning for unmanned surface vehicle in complex offshore areas based on hybrid algorithm [J].Computer Communications，2021，166：49-56.

[26] YAO Q F，ZHENG Z Y，QI L，et al. Path planning method with improved artificial potential field—A reinforcement learning perspective [J].IEEE Access，2020，8：135513-135523.

[27] HE N F，SU Y F，GUO J L，et al. Dynamic path planning of mobile robot based on artificial potential field [C]//2020 International Conference on Intelligent Computing and Human-Computer Interaction（ICHCI）.Sanya：IEEE，2020：259-264.

[28] WANG M，ZENG B，WANG Q. Research on Motion Planning Based on Flocking Control and Reinforcement Learning for Multi-Robot Systems [J/OL].Machines，2021，9（4）：[2022-08-12].https：//doi.org/10.3390/machines9040077.

[29] ZHOU Y，ZHANG E D，GUO H L，et al. Lifting path planning of mobile cranes based on an improved RRT algorithm [J/OL].Advanced Engineering Informatics，2021，50：[2022-08-12].https：//doi.org/10.1016/j.aei.2021.101376.

[30] KANG J G，LIM D W，CHOI Y S，et al. Improved RRT-Connect Algorithm Based on Triangular Inequality for Robot Path Planning [J/OL].Sensors，2021，21（2）：[2022-08-12].https：//doi.org/10.3390/s21020333.

[31] CHEN J G，ZHAO Y，XU X. Improved RRT-Connect Based Path Planning Algorithm for Mobile Robots [J].IEEE Access，2021，9：145988-145999.

[32] CHEN G，LUO N，LIU D，et al. Path planning for manipulators based on an improved probabilistic roadmap method [J/OL].Robotics and Computer-Integrated Manufacturing，2021，72：[2022-08-12].https：//doi.org/10.1016/j.rcim.2021.102196.

[33] XU Z F，DENG D，SHIMADA K. Autonomous UAV Exploration of Dynamic Environments Via Incremental Sampling and Probabilistic Roadmap [J].IEEE Robotics and Automation Letters，2021，6（2）：2729-2736.

[34] RAVANKAR A A，RAVANKAR A，EMARU T，et al. HPPRM：Hybrid Potential Based Probabilistic Roadmap Algorithm for Improved Dynamic Path Planning of Mobile Robots [J].IEEE Access，2020，8：221743-221766.

[35] LOW E S，ONG P，CHEAH K C. Solving the optimal path planning of a mobile robot using improved Q-learning [J].Robotics and Autonomous Systems，2019，115：143-161.

[36] SUN F J，WANG X C，ZHANG R. Improved Q-Learning Algorithm Based on Approximate State Matching in Agricultural Plant Protection Environment [J/OL].Entropy，2021，23（6）：[2022-08-12].https：//doi.org/10.3390/e23060737.

[37] LI B，LIANG H B. Multi-Robot Path Planning Method Based on Prior Knowledge and Q-learning Algorithms [C]//Proceedings of 2020 2nd International Conference on Computer Modeling，Simulation and Algorithm（CMSA2020）.Beijing：IOP，2020，1624（4）：1-9.

[38] HAMDIA K M，ZHUANG X Y，RABCZUK T. An efficient optimization approach for designing machine learning models based on genetic algorithm [J].Neural Computing and Applications，2021，33（6）：1923-1933.

[39] ABDI A，ADHIKARI D，PARK J H. A Novel Hybrid Path Planning Method Based on Q-Learning and Neural Network for Robot Arm [J/OL].Applied Sciences，2021，11（15）：[2022-08-12].https：//doi.org/10.3390/app11156770.

[40] XIANG L D，LI X M，LIU H，et al. Parameter Fuzzy Self-Adaptive Dynamic Window Approach for Local Path Planning of Wheeled Robot [J].IEEE Open Journal of Intelligent Transportation Systems，2021，3：1-6.

[41] CHANG L，SHAN L，JIANG C，et al. Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment [J].Autonomous Robots，2021，45（1）：51-76.

[42] BALLESTEROS J，URDIALES C，VELASCO A B M，et al. A Biomimetical Dynamic Window Approach to Navigation for Collaborative Control [J].IEEE Transactions on Human-Machine Systems，2017，47（6）：1123-1133.

[43] WANG X Y，WANG A，WANG D Z，et al. Repetitive Control Scheme of Robotic Manipulators Based on Improved B-Spline Function [J/OL].Complexity，2021，2021：[2022-08-12].https：//doi.org/10.1155/2021/6651105.

[44] 古勁，吳泰羽，李傳軍，等. 基于改進三次B樣條的灌木修剪運動軌跡光順算法研究 [J].農業機械學報，2021，52（S1）：89-97.

[45] LUAN P G，THINH N T. C 2 Piecewise Cubic Bezier Curve Based Smoothing Path for Mobile Robot [J/OL].International Journal of Mechanical Engineering and Robotics Research，2021，10（9）：1-7[2022-08-12].http：//www.ijmerr.com/uploadfile/2021/0727/20210727113132943.pdf.

[46] ZENG X Y，LU H C，LYU H F，et al. Robot Path Planning Based on Improved RRT Algorithm [C]//LSMS 2021，ICSEE 2021：Intelligent Equipment，Robots，and Vehicles.Hangzhou：Springer，2021：361-369.

[47] CHEN J B，ZHOU Y L，GONG J，et al. An improved probabilistic roadmap algorithm with potential field function for path planning of quadrotor [C]//2019 Chinese Control Conference（CCC）.Guangzhou：IEEE，2019：3248-3253.

[48] LI Y B，DONG D G，GUO X N. Mobile Robot Path Planning based on Improved Genetic Algorithm With A-star Heuristic Method [C]//2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference（ITAIC）.Chongqing：IEEE，2020：1306-1311.

[49] CHEN Y L，BAI GQ，ZHAN Y，et al. Path Planning and Obstacle Avoiding of the USV Based on Improved ACO-APF Hybrid Algorithm With Adaptive Early-Warning [J].IEEE Access，2021，9：40728- 40742.

作者簡介：林梓健（1997—），男，漢族，廣東江門人，碩士研究生在讀，主要研究方向：智能裝備；通訊作者：林群煦（1983—），男，漢族，廣東江門人，副教授，博士，主要研究方向：智能化物流和移動機器人；劉凱（1999—），男，漢族，廣東廣州人，碩士研究生在讀，主要研究方向：機器視覺、機器人導航。

收稿日期：2022-09-30