林梓健 劉凱 林群煦

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

關(guān)鍵詞：路徑規(guī)劃；算法綜述；自動導航

中圖分類號：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? 引? 言

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

1? 幾何搜索算法

1.1? A*算法

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

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

1.2? Dijkstra算法

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

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

1.3 Voronoi圖算法

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

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

2? 智能搜索算法

2.1? 蟻群算法

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

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

2.2? 遺傳算法

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

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

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

2.3? 人工勢場法

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

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

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

2.4? RRT算法

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

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

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

2.5? PRM算法

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

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

3? 人工智能算法

3.1? Q-Learning

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

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

3.2? 深度學習

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

4? 局部規(guī)劃算法

4.1? DWA算法

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

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

4.2? 局部優(yōu)化算法

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

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

5? 混合算法

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

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

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

6? 結(jié)? 論

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

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

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

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

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

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

參考文獻：

[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，F(xiàn)ANG 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·霍蘭.隱秩序：適應(yīng)性造就復雜性 [M].周曉牧，譯.上海：上海科技教育出版社，2019.

[17] WANG H J，F(xiàn)U 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] 袁夢飛，闞秀，曹樂，等.自適應(yīng)精英遺傳算法的快遞車路徑規(guī)劃 [J].導航定位學報，2021，9（6）：104-111.

[22] 王吉岱，王新棟，田群宏，等．基于改進模糊自適應(yīng)遺傳算法的移動機器人路徑規(guī)劃 [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].農(nóng)業(yè)機械學報，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