跳點搜索融合雙向并行蟻群算法的AGV路徑規劃研究

摘要 在靜態柵格地圖中，針對傳統蟻群算法進行AGV（ Automated Guided Vehicle，自動引導車）路徑規劃收斂慢且搜索結果容易陷入局部最優的問題，提出一種融合跳點搜索（Jump Point Search，JPS）和雙向并行蟻群搜索的改進算法.首先，對實際研究環境進行柵格化建模，使用改進的跳點搜索算法生成雙向搜索的初始次優路徑，為雙向蟻群搜索提供初始搜索方向參考.其次，在雙向并行蟻群搜索過程中采用改進的轉移概率啟發函數，該函數在確定下一個轉移節點時考慮了避免AGV與障礙物碰撞的因素，同時通過設計信息素共享機制并結合改進的信息素增量及濃度兩種融合模型，共享和更新全局信息素濃度，以更好地探索和優化路徑，保證雙向路徑連結.最后，與傳統蟻群算法進行實驗結果對比，驗證了改進算法的全局搜索能力、效率和安全性.

關鍵詞 跳點搜索算法；蟻群算法；自動引導車；路徑規劃；雙向并行

中圖分類號TP18;TP242.6

文獻標志碼A

0引言

AGV路徑規劃（AGVPP，AGV Path Planning）是指為每臺AGV（Automated Guided Vehicle，自動引導車）設備規劃一條自起點至終點且規避與障礙物碰撞的最優路徑[1].AGV路徑規劃目前主要有三類方法：1）基于人工智能的算法，如蟻群算法[2]、粒子群優化算法[3]等；2）基于局部避障的算法，如勢場法[4]、動態窗口法[5]等；3）基于圖論的算法，如Dijkstra算法[6]、A*算法[7]等.基于人工智能的算法可根據環境變化自適應地調整路徑規劃策略，適用于不同的場景和任務，同時可能伴隨大量的計算和模擬，需要較高的計算資源和時間成本.基于局部避障的算法只考慮AGV周圍的局部環境，而不需要知道全局地圖信息，具有實時性強、精度高和適應性強的特點，但可能會導致生成的路徑僅為局部最優解，而非全局最優解.基于圖論的算法能夠基于全局環境信息進行搜索和規劃，即使在復雜的環境中也能夠規劃一條連接起點和終點的路徑，但有可能存在較大的計算量，需通過優化策略來提升規劃路徑的質量和效率.

A*算法是靜態場景下進行AGV路徑規劃的常見啟發式算法，但在搜索路徑的時候，需要頻繁查詢 OpenList和 CloseList 中的節點，導致節點排序和查詢節點消耗大量時間資源，隨著柵格地圖的增大，AGV的導航實時性將明顯降低.Harabor 等[8]提出了跳點搜索（Jump Point Search，JPS）算法，只將所謂的跳躍點作為搜索的節點，不僅顯著提升了搜索效率，也在一定程度上解決了因對稱性路徑造成的搜索空間過大的問題.趙曉等[9]將JPS算法應用于移動機器人的導航中，體現了JPS 算法較傳統 A*算法的優勢.但隨著地圖規模和障礙物復雜度的增加，JPS算法的路徑規劃過程仍可能導致計算資源的大量消耗，同時考慮到障礙物的實物體積，算法生成的規劃路徑無法有效避免AGV與障礙物碰撞，可能存在緊貼障礙物、軌跡不平滑[10]等問題，將直接影響實際工作場景下AGV設備的安全運行.

傳統蟻群算法是一種基于正反饋的單向搜索算法，其前期搜索的盲目性有可能導致收斂速度慢且容易陷入局部最優[11]，但其搜索速度快、精度高、尋址能力強，同時易與其他算法結合，因此具有較高的優化靈活性.馬軍等[12]嘗試將蟻群算法和A*算法進行結合，改進了啟發式函數和信息素更新方式，但并沒有顯著解決蟻群算法搜索初期盲目性大的問題.Zhu等[13]融合了人工勢場法與蟻群算法，通過動態調整算法的狀態轉移規則以提升全局搜索能力和收斂進度，但算法復雜度對AGV配置有一定要求，且存在AGV碰撞障礙物邊緣的可能性.李二超等[14]提出一種基于貝塞爾曲線融合雙向蟻群的算法，規劃出的路徑可避免AGV與障礙物的碰撞且兼顧了平滑度的要求，但是對搜索初期如何優化雙向蟻群搜索的方向性未做探討，且算法的復雜性和計算量較大，對AGV的性能配置存在一定要求.

針對上述問題，本文提出一種利用跳點搜索算法加速雙向并行蟻群搜索的改進算法，兩組蟻群自地圖起點和終點并行相向搜索，利用跳點搜索算法規劃的次優路徑為兩組蟻群提供初始路徑參考，以加速搜索和算法收斂，并通過在并行搜索的蟻群間共享信息素增量和信息素濃度，以進一步優化搜索效果.

1環境建模

柵格法建模具有簡單直觀、易于計算和適用性廣等優點，是路徑規劃中常見的建模方法[15].本文采用柵格法對實際工作環境展開建模研究.模型環境中每個柵格為一個節點，黑色節點表示障礙物，白色節點表示AGV可通過的空曠區域，地圖信息即可表示為一個二維矩陣C=（cij），其中：

為驗證算法的通用性和可用性，本文采用柵格法構建如下20 m×20 m和30 m×30 m兩個不同規模的模型地圖，如圖1所示.

上述模型地圖起點和終點分別使用S、E表示，本文算法研究的目的可歸納為尋找S和E間的最短平滑安全路徑問題.根據算法驗證需要，模型地圖中的部分障礙物為“凹”形并由多個障礙物節點組成，其他障礙物在實際生產環境中表現為隨機形狀和隨機分布.

2跳點搜索算法及其不足

2.1跳點搜索算法

算法搜索過程中當前節點的鄰節點，可分為自然鄰居和強迫鄰居[16]兩類.自然鄰居節點是當前節點在水平、垂直和對角線方向上的直接鄰節點，用于進一步擴展路徑搜索.在上述研究假設的AGV運動方向上，若當前節點c的鄰節點中有障礙物，相較其他鄰節點，鄰節點f到節點c的父節點p的代價距離最短，則節點f為節點c的強迫鄰居節點.若節點c滿足下列條件之一，則可認定為跳點：

1）節點c是起點或終點；

2）節點c至少有一個強迫鄰居；

3）在斜向搜索時，斜向搜索分解的水平或垂直方向上，有滿足上述1）或2）條件的節點.

在搜索過程中算法通過跳點剔除搜索過程中大量無用節點，并反復通過代價估計函數值確定下一步需拓展的節點.跳點搜索算法的代價估計函數與A*算法相同，定義為

2.2跳點搜索算法的不足

跳點搜索算法基于A*算法進行改良，在路徑搜索中舍棄了大量可能會產生冗余計算的無用節點，僅識別和存儲“跳點”，相較于A*算法顯著減少了算法運行期間需要計算的節點數量和探索路徑數量.但跳點搜索算法在路徑規劃時并不考慮AGV及障礙物的形狀和大小，只關注節點間的跳躍關系，因此規劃出來的路徑有可能存在AGV緊貼障礙物或與之碰撞的問題[20].當障礙物形狀呈現對稱圖形時，若雙向搜索均使用跳點算法，則可能生成從障礙物對稱側經過障礙物的兩條長度和收斂速度類似的路徑；若雙向搜索未進行信息共享，則一向路徑進行跳點擴展時，有可能越過另一向路徑正在擴展的跳點，進而產生冗余路徑.在障礙物位置分布隨機的情況下，若障礙物數量較多，路徑規劃過程中有可能生成大量跳點，造成搜索方向和路徑長度存在較大的不確定性，且雙向兩條搜索路徑的重疊節點有可能距離起點和終點連線的中心較遠，造成路徑規劃資源浪費.

3融合跳點搜索的雙向并行蟻群算法

考慮到傳統蟻群算法前期搜索的盲目性和單向搜索效率，本文提出一種雙向并行搜索的蟻群算法，即位于起點和終點的兩組螞蟻同時進行并行搜索.在搜索的起始階段，將改進的跳點搜索算法的啟發式規則和路徑作為蟻群算法的啟發式信息和初始次優路徑.在搜索過程中，雙向蟻群通過共享和同步更新信息素增量和信息素濃度，達到優化搜索的方向性的目的.當兩組蟻群搜索路徑相接并重疊時，重疊節點的信息素濃度將會顯著升高，即重疊節點可以幫助確定搜索方向的正確性，并提供路徑繼續搜索的方向性參考.兩組蟻群分別到達目標點后，通過比較兩個方向上的路徑質量評價指標來選擇最優路徑.

以下研究將起點S至終點E的路徑搜索方向定為正向搜索方向，將終點E至起點S的路徑搜索方向定為反向搜索方向.

3.1跳點搜索算法改進

傳統蟻群算法要求單向蟻群自起點到目標點進行搜索，所有螞蟻在搜索過程中均會持續釋放信息素，并同時伴隨信息素的揮發效應.單向蟻群大致相同的起始路徑將無法保證算法有效規劃全局最優路徑，且均勻分配的信息素濃度雖然保證了所有路徑被選擇的概率，但也隨之產生了蟻群初期盲目搜索及引發的算法搜索效率降低的問題.

為提升路徑規劃效率、降低計算量，本研究擬在搜索初期使用改進的跳點搜索算法生成初始次優路徑，將路徑方向作為蟻群算法中的路徑選擇策略.同時，本文將采用曼哈頓距離作為跳點搜索的啟發函數.

考慮到跳點搜索算法規劃的路徑有可能造成AGV與障礙物碰撞，對跳點篩選規則做如下改進：

1）直線搜索方向篩選規則改進

直線搜索包括水平和垂直兩個方向，兩個方向的改進原理相同.以水平方向搜索為例，改進的直線搜索路徑如圖2a中的實線路徑所示.p（c）為節點c的父節點，節點f為節點c的強制鄰居，當節點c的鄰節點存在障礙物時（圖中為節點c的正上方黑色節點），為避免碰撞，本研究不允許通過虛線對角線到達強制鄰居，即在圖中不以節點c作為跳點，而以其自然鄰居節點d作為跳點.

2）斜線搜索方向篩選規則改進

改進的對角線搜索路徑規則如圖2b中的實線路徑所示，節點c的左側為障礙物.與改進的直線搜索類似，為避免碰撞則不以虛線路徑行進，同理將節點b和節點d作為跳點處理.

3.2轉移概率啟發函數改進

傳統蟻群算法在t時刻的轉移概率啟發函數一般表示為ηij（t）=1dij，啟發函數僅考慮節點i和j之間的歐式距離dij，即i節點附近節點的局部信息.但某些情況下，節點i和j之間的歐式距離與節點j到目標點的距離未必成正比.

改進后的轉移概率啟發函數綜合考慮了局部及全局信息，同時結合了上述對跳點篩選規則的優化思路，使用曼哈頓距離作為轉移概率啟發函數，符合上述改進跳點篩選規則避免AGV與障礙物碰撞的思路.改進后的啟發函數為

3.3信息素共享機制設計及更新公式改進

3.3.1傳統蟻群算法信息素更新機制

傳統蟻群算法的信息素濃度更新公式表示為

3.3.2信息素共享機制設計

式（5）和（6）主要應用于蟻群的單向搜索過程，傳統蟻群算法在選擇路徑時，可能會面臨大量的盲路徑，經過一定數量路徑的迭代后生成的可能為非最優路徑，導致計算資源浪費.本文在雙向并行蟻群搜索過程中，擬讓雙向蟻群共享對方蟻群全局信息素信息，即當一方的螞蟻發現了一條可行的路徑時釋放信息素，另一方的螞蟻可以通過感知到的全局信息素來引導搜索方向，使兩個方向的搜索路徑逐漸靠近，確保路徑連結，提升搜索效率.全局信息素信息共享可以增進蟻群間的信息交流和合作，有助于更好地探索和優化路徑.

本研究中的全局信息素信息共享分為信息素增量共享和信息素濃度共享.對以下研究作假設如下：當前時刻t正向最近完成的搜索路徑為從節點i至節點j，反向為節點l至節點k.需要注意的是，為保證雙向蟻群并行搜索效率，若當前此輪正向搜索結束但此時反向搜索仍在進行，則增量融合公式中將使用反向搜索上一時刻生成的最新增量，即雙向搜索過程共享最新的增量矩陣信息，反向搜索同理.

3.3.3信息素增量融合模型設計

首先針對傳統蟻群算法的信息素增量公式進行改進，設計雙向信息素增量融合模型.在每輪搜索迭代結束時，通過共享和融合雙向信息素增量，生成當前搜索方向的信息素增量，并將對向搜索的信息素增量作為生成當前信息素增量的參考，以此作為引導雙向蟻群路徑連結的激勵.

3.3.4信息素濃度融合模型設計

參考基礎增量和融合增量進行雙向信息素濃度融合模型設計.與式（5）類似，利用式（9）中得到的雙向融合增量，分別進行相應方向信息素基礎濃度值更新，更新過程已將對向搜索的信息素增量考慮在內.更新公式可表示為

3.4改進算法流程

改進算法的流程如圖3所示.

在搜索過程開始階段，首先針對實際研究環境進行柵格化建模，存儲起點S、終點E和障礙物的分布坐標信息，同時針對關鍵參數進行初始化.使用改進的跳點搜索算法生成雙向搜索的初始次優路徑，該路徑作為雙向搜索過程開始時更新初始信息素含量的依據，為雙向蟻群搜索提供方向參考.在初始次優路徑的基礎上生成初始信息素濃度，并展開雙向并行搜索.搜索過程將采用改進的轉移概率啟發函數，該函數在確定下一個轉移節點時已考慮了避免AGV與障礙物碰撞的可能性，因此轉移節點可能為信息素濃度最高或次高的節點.通過共享雙向信息素增量和濃度值，使用信息素增量融合模型和濃度融合模型更新全局信息素濃度.當達到最大迭代次數時輸出最優路徑，并與傳統蟻群算法進行實驗結果對比.

4實驗及結果分析

為驗證本文算法的有效性，采用Python 3.7進行實驗.實驗環境為16 GB內存運行Windows 11的PC，CPU 為具備4核8線程的AMD Ryzen 5，工作頻率2.1 GHz.實際工作環境為某電子產品制造企業已普遍采用AGV進行產品及物料搬運的兩個車間，根據障礙物分布柵格化20 m×20 m和30 m×30 m兩組地圖環境，建立直角坐標系進行實驗.出于隱私保護考慮，AGV設備型號和非關鍵參數在不影響實驗研究效果的前提下不作體現.本文開展實驗車間使用4輪額定功率80 W的AGV設備，設備長寬高尺寸為0.8 m×0.6 m×0.4 m，理想巡航速度和最大速度分別為0.5 m/s和1 m/s，加速度和減速度均為1 m/s2.

通過分析表1和表2對比數據，傳統蟻群算法在搜索初期由于搜索的盲目性及其導致的無用信息素積累，有可能在探索過程生成冗余拐點，增加最優路徑長度、拐點數和搜索耗時.改進算法能夠有效減少搜索節點的個數，有助于減少規劃過程對系統資源的占用，提升規劃效率.從收斂曲線可知，雖然改進算法在搜索初期有所波動，但生成其最優路徑的迭代次數顯著減少，收斂速度快，結合相關對比指標的平均值和標準差可知，改進算法的平滑性明顯優于傳統蟻群算法.綜上，改進算法各項指標均優于傳統蟻群算法，具有較好的全局搜索能力，且伴隨著地形擴大和障礙物增加，改進算法與傳統蟻群算法的指標差距在逐步拉大，在實際環境中有助于規劃出更加平滑的路徑，減少AGV工作過程的時間和能耗.同時，將改進算法中的跳點搜索規則融入轉移概率啟發函數，生成的路徑能夠有效地避免與障礙物碰撞，大大提升了規劃路徑的安全性.

此外，本文研究并未對算法適用環境做明確限制，也未固化障礙物的位置，具備實際工作場景下的應用價值.

5結語

針對傳統蟻群搜索算法收斂速度慢、規劃路徑易陷入局部最優且未考慮AGV與障礙物的碰撞的不足，本文提出一種將跳點搜索算法融入雙向并行蟻群搜索過程的改進算法.改進算法設定了兩組相向并行搜索的蟻群，以改進的跳點搜索算法為雙向搜索生成初始次優路徑，以此減少蟻群搜索初期搜索的盲目性.在雙向并行搜索過程中通過改進轉移概率啟發函數、共享信息素增量和濃度優化了全局搜索能力、效率和安全性.通過多次迭代實驗并對比數據，改進算法較傳統蟻群算法在復雜障礙物環境中，具有更快的收斂速度、更短的規劃路徑和耗時以及更少的搜索節點，驗證了本文改進算法的有效性和優越性.

參考文獻

References

［1］PatleB K，Babu L G，Pandey A，et al.A review：on path planning strategies for navigation of mobile robot[J].Defence Technology，2019，15（4）：582-606

[2]劉加奇，王泰華，董征.基于改進蟻群算法的移動機器人路徑規劃[J].傳感器與微系統，2022，41（5）：140-143LIU Jiaqi，WANG Taihua，DONG Zheng.Path planning of mobile robot based on improved ant colony algorithm[J].Transducer and Microsystem Technologies，2022，41（5）：140-143

[3]趙迪，何克勤，趙祖高.基于改進粒子群優化算法的移動機器人路徑規劃[J].傳感器與微系統，2023，42（6）：150-153ZHAO Di，HE Keqin，ZHAO Zugao.Path planning for mobile robot based on improved PSO algorithm[J].Transducer and Microsystem Technologies，2023，42（6）：150-153

[4]翟麗，張雪瑩，張閑，等.基于勢場法的無人車局部動態避障路徑規劃算法[J].北京理工大學學報，2022，42（7）：696-705ZHAI Li，ZHANG Xueying，ZHANG Xian，et al.Local dynamic obstacle avoidance path planning algorithm for unmanned vehicles based on potential field method[J].Transactions of Beijing Institute of Technology，2022，42（7）：696-705

[5]陳嬌，徐菱，陳佳，等.改進A*和動態窗口法的移動機器人路徑規劃[J].計算機集成制造系統，2022，28（6）：1650-1658CHEN Jiao，XU Ling，CHEN Jia，et al.Path planning based on improved A*and dynamic window approach for mobile robot[J].Computer Integrated Manufacturing Systems，2022，28（6）：1650-1658

[6]吳立輝，胡文博，周秀，等.面向多搬運任務的柔性制造車間多載具AGV節能路徑規劃[J].計算機應用研究，2023，40（1）：57-62WU Lihui，HU Wenbo，ZHOU Xiu，et al.Energy-efficient path planning for single multi-load AGV executing multiple transport tasks in flexible manufacturing workshop[J].Application Research of Computers，2023，40（1）：57-62

[7]耿宏飛，神健杰.A*算法在AGV路徑規劃上的改進與驗證[J].計算機應用與軟件，2022，39（1）：282-286GENG Hongfei，SHEN Jianjie.Improvement and verification of A* algorithm in AGV path planning[J].Computer Applications and Software，2022，39（1）：282-286

[8]Harabor D，Grastien A.The JPS pathfinding system[J].Proceedings of the International Symposium on Combinatorial Search，2012，3（1）：207-208

[9]趙曉，王錚，黃程侃，等.基于改進A*算法的移動機器人路徑規劃[J].機器人，2018，40（6）：903-910ZHAO Xiao，WANG Zheng，HUANG Chengkan，et al.Mobile robot path planning based on an improved A* algorithm[J].Robot，2018，40（6）：903-910

[10]魏博聞，嚴華.一種面向非結構化環境的改進跳點搜索路徑規劃算法[J].科學技術與工程，2021，21（6）：2363-2370WEI Bowen，YAN Hua.An improved jump point search path-planning algorithm for unstructured environment[J].Science Technology and Engineering，2021，21（6）：2363-2370

[11]劉紫玉，趙麗霞，薛建越，等.面向車輛路徑問題的改進蟻群算法研究[J].河北科技大學學報，2022，43（1）：80-89LIU Ziyu，ZHAO Lixia，XUE Jianyue，et al.Research on vehicle routing problem based on improved ant colony algorithm[J].Journal of Hebei University of Science and Technology，2022，43（1）：80-89

[12]馬軍，宋栓軍，韓軍政，等.融合蟻群-A*算法的移動機器人路徑規劃[J].西安工程大學學報，2020，34（1）：72-77MA Jun，SONG Shuanjun，HAN Junzheng，et al.Mobile robot path planning based on a fusion ant colony-A*algorithm[J].Journal of Xian Polytechnic University，2020，34（1）：72-77

[13]ZhuS N，Zhu W Y，Zhang X Q，et al.Path planning of lunar robot based on dynamic adaptive ant colony algorithm and obstacle avoidance[J].International Journal of Advanced Robotic Systems，2020，17（3）：172988141989897

[14]李二超，齊款款.貝塞爾曲線融合雙向蟻群算法的移動機器人路徑規劃[J].陜西師范大學學報（自然科學版），2022，50（3）：79-88LI Erchao，QI Kuankuan.Path planning of mobile robot based on Bessel curve and bidirectional ant colony algorithm[J].Journal of Shaanxi Normal University （Natural Science Edition），2022，50（3）：79-88

[15]付雄，李濤.基于自適應步長策略的A*算法路徑規劃優化[J].南京信息工程大學學報（自然科學版），2024，16（2）：164-172FU Xiong，LI Tao.Path optimization of A* algorithm based on adaptive step size strategy[J].Journal of Nanjing University of Information Science amp; Technology （Natural Science Edition） ，2024，16（2）：164-172

[16]邱磊，劉輝玲，雷建龍.跳點搜索算法的原理解釋及性能分析[J].新疆大學學報（自然科學版），2016，33（1）：80-87QIU Lei，LIU Huiling，LEI Jianlong.Principle explanation and performance analysis of jump point search algorithm[J].Journal of Xinjiang University （Natural Science Edition），2016，33（1）：80-87

[17]張洪海，李翰，劉皞，等.城市區域物流無人機路徑規劃[J].交通運輸系統工程與信息，2020，20（6）：22-29ZHANG Honghai，LI Han，LIU Hao，et al.Path planning for logistics unmanned aerial vehicle in urban area[J].Journal of Transportation Systems Engineering and Information Technology，2020，20（6）：22-29

[18]王秀紅，劉雪豪，王永成.基于改進A*算法的倉儲物流移動機器人任務調度和路徑優化研究[J].工業工程，2019，22（6）：34-39WANG Xiuhong，LIU Xuehao，WANG Yongcheng.A research on task scheduling and path planning of mobile robot in warehouse logistics based on improved A*algorithm[J].Industrial Engineering Journal，2019，22（6）：34-39

[19]張慶，劉旭，彭力，等.融合JPS和改進A*算法的移動機器人路徑規劃[J].計算機科學與探索，2021，15（11）：2233-2240ZHANG Qing，LIU Xu，PENG Li，et al.Path planning for mobile robots based on JPS and improved A*algorithm[J].Journal of Frontiers of Computer Science and Technology，2021，15（11）：2233-2240

[20]黃智榜，胡立坤，張宇，等.基于改進跳點搜索策略的安全路徑研究[J].計算機工程與應用，2021，57（1）：56-61HUANG Zhibang，HU Likun，ZHANG Yu，et al.Research on security path based on improved hop search strategy[J].Computer Engineering and Applications，2021，57（1）：56-61

AGV path planning via integration of jump point search with

bi-directional parallel ant colony algorithm

LIN Xinchuan

1College of Information Engineering，Fujian Business University，Fuzhou 350012，China

AbstractIn this article，an improved algorithm that combines jump point search and bi-directional parallel ant colony search is proposed for static grid maps to address the slow convergence and easy trapping in local optima perplexed traditional ant colony algorithms for Automated Guided Vehicle（AGV） path planning.First，the actual research environment is modeled by gridization，and the improved jump point search algorithm is used to generate the initial suboptimal path for bi-directional search，providing a reference for the initial search direction of bi-directional ant colony search.Second，an improved transition probability heuristic function is used in the bi-directional parallel ant colony search process，which considers the avoidance of collision between AGV and obstacles when determining the next transition node.Meanwhile，by designing an information sharing mechanism and combining two fusion models of improved information increment and concentration，the global information concentration is shared and updated to better explore and optimize the path and ensure the connection of bi-directional paths.Finally，experimental results are compared with those of traditional ant colony algorithms to verify the improved algorithms global search capability，efficiency and security.

Key wordsjump point search algorithm;ant colony algorithm;automated guided vehicle （AGV）;path planning;bi-directional parallel