基于路徑規劃技術的改進算法研究綜述

陸緣緣 崔衍

摘要：路徑規劃技術已經成為各大領域研究的話題，在生活中被廣泛使用，具有很高的研究價值。而路徑規劃技術的主要核心在于路徑規劃算法。首先，對路徑規劃技術進行概述。其次，對常用的路徑規劃相關算法進行分析和總結，提出其所存在的缺點及問題。再著重對目前各種改進算法、混合算法的使用等方面進行分析，對其改進方向、使用場景等方面進行總結。最后，對路徑規劃算法所存在的問題進行提出，對下一步的改進與研究趨勢進行展望。

關鍵詞：路徑規劃技術; 算法; 混合算法

Abstract： Path planning technology has become a research topic in various fields， is widely used in life， and has high research value. The main core of the path planning technology is the path planning algorithm. First， an overview of path planning technology. Secondly， it analyzes and summarizes the commonly used path planning related algorithms， and puts forward their shortcomings and problems. Then focus on the analysis of the current various improved algorithms and the use of hybrid algorithms， and summarize their improvement directions and usage scenarios. Finally， the problems of the path planning algorithm are put forward， and the next improvement and research trends are prospected.

Key words： path planning technology; algorithm; hybrid algorithm

路徑規劃技術[1]目前在很多領域均有著廣泛的應用，其主要內容是根據路徑規劃算法[2]來實現最優路徑的搜索，所得路線即起始點到目標點之間的無障礙安全通路。路徑規劃算法包括傳統算法和智能仿生算法，從傳統的算法到之后的智能仿生算法根據路徑規劃算法各自的特點選擇適合場景應用都已經取得了很大的進展。

文章主要從常見的路徑規劃算法進行分析其優缺點;再通過對相關文獻的學習，總結出A*算法、Dijkstra算法、蟻群算法、粒子群算法等改進;最后對路徑規劃算法改進方向做出一些總結與展望。

1 路徑規劃算法綜述

路徑規劃技術是一種應用于智能領域的新型支撐技術，其中的路徑規劃算法依據其實現原理的不同分為傳統型路徑規劃算法和智能仿生學算法。近年來，路徑規劃已經是國內外學者研究的熱點問題，目前在眾多科技領域中已有很大的成就及突破。

路徑規劃技術在眾多領域中都有著廣泛的應用，在高科技領域中的具體應用場景有：自動引導車、智能搜救機器人、機場巡檢機器人等;在軍事領域中的具體場景有：無人水面艇避障、碰撞預測、海上應急物流;在日常生活中的具體應用場景有：GPS導航、旅行商問題（TSP）、車輛路徑規劃問題（VRP）等;在網絡通信中的具體應用場景有：路由選擇問題等;在物流管理領域中的具體應用場景有：包裹分揀、快遞配送路徑選擇等。

路徑規劃算法的實現主要是通過高級語言編寫而完成的，主要分為傳統算法和智能仿生算法，其常用的人為算法包括：A*算法、Dijkstra算法、Floyd算法;智能仿生算法包括：遺傳算法、蟻群算法、模擬退火算法等。從傳統算法、智能仿生算法發展到傳統算法與仿生算法結合的算法都體現出路徑規劃技術的發展。

2 常見人工算法及其優缺點

Dijkstra算法[3]：該算法從起點遍歷到其他各節點計算其距離直到目標節點的最短路徑。該算法的主要特點是確保每一次的迭代路徑均是最短的。該算法魯棒性好但其搜索效率低。

A*算法[4]：該算法從起點開始，檢查其從起點開始，遍歷起點周圍鄰近的點，然后再遍歷已經遍歷過的點鄰近的點，逐步的向外擴散，直到找到終點。該算法準確性高、性能好，但可能出現目標不可達而浪費性能的現象。

Floyd算法[5]：該算法引用的是動態規劃思想，在兩頂點間插入一個或以上的中轉點，比較經過和未經過中轉點的距離哪個更短。其主要用于求一條帶權值有向圖的任意兩點間的最短路徑。該算法實現簡單，但實現復雜度高。

3 常用智能仿生算法及其優缺點

蟻群算法[6]：該算法思想來自對蟻群覓食行為的探索，每個螞蟻覓食時都會在走過的道路上留下一定濃度的信息素，相同時間內最短的路徑上由于螞蟻遍歷的次數多而信息素濃度高，加上后來的螞蟻在選擇路徑時會以信息素濃度為依據，起到正反饋作用，因此信息素濃度高的最短路徑很快就會被發現，進而找到蟻群從蟻巢開始經過若干個覓食地所尋找出一條近距離且無障礙的可行路徑。該算法魯棒性強、信息正反饋性、自適應性、有并行性和可擴展性，但可能出現前期搜索效率低、易收斂、易陷入局部最優解等問題。

遺傳算法[7]：該算法是一種模擬達爾文遺傳選擇和自然淘汰的生物進化過程中的計算模型。它的思想源于生物遺傳學和適者生存的自然規律，是按照基因遺傳學原理而實現的一種迭代過程的搜索算法。其中采用隨機方式搜索，利用交叉變異的操作提供多樣性來適應不同情形。該算法全局搜索力強并可以有效處理復雜的最優解問題，但所占空間大、運行效率低、運算周期較長。