基于路徑規(guī)劃技術(shù)的改進(jìn)算法研究綜述

陸緣緣 崔衍

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

關(guān)鍵詞：路徑規(guī)劃技術(shù); 算法; 混合算法

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

路徑規(guī)劃技術(shù)[1]目前在很多領(lǐng)域均有著廣泛的應(yīng)用，其主要內(nèi)容是根據(jù)路徑規(guī)劃算法[2]來實(shí)現(xiàn)最優(yōu)路徑的搜索，所得路線即起始點(diǎn)到目標(biāo)點(diǎn)之間的無障礙安全通路。路徑規(guī)劃算法包括傳統(tǒng)算法和智能仿生算法，從傳統(tǒng)的算法到之后的智能仿生算法根據(jù)路徑規(guī)劃算法各自的特點(diǎn)選擇適合場(chǎng)景應(yīng)用都已經(jīng)取得了很大的進(jìn)展。

文章主要從常見的路徑規(guī)劃算法進(jìn)行分析其優(yōu)缺點(diǎn);再通過對(duì)相關(guān)文獻(xiàn)的學(xué)習(xí)，總結(jié)出A*算法、Dijkstra算法、蟻群算法、粒子群算法等改進(jìn);最后對(duì)路徑規(guī)劃算法改進(jìn)方向做出一些總結(jié)與展望。

1 路徑規(guī)劃算法綜述

路徑規(guī)劃技術(shù)是一種應(yīng)用于智能領(lǐng)域的新型支撐技術(shù)，其中的路徑規(guī)劃算法依據(jù)其實(shí)現(xiàn)原理的不同分為傳統(tǒng)型路徑規(guī)劃算法和智能仿生學(xué)算法。近年來，路徑規(guī)劃已經(jīng)是國(guó)內(nèi)外學(xué)者研究的熱點(diǎn)問題，目前在眾多科技領(lǐng)域中已有很大的成就及突破。

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

路徑規(guī)劃算法的實(shí)現(xiàn)主要是通過高級(jí)語言編寫而完成的，主要分為傳統(tǒng)算法和智能仿生算法，其常用的人為算法包括：A*算法、Dijkstra算法、Floyd算法;智能仿生算法包括：遺傳算法、蟻群算法、模擬退火算法等。從傳統(tǒng)算法、智能仿生算法發(fā)展到傳統(tǒng)算法與仿生算法結(jié)合的算法都體現(xiàn)出路徑規(guī)劃技術(shù)的發(fā)展。

2 常見人工算法及其優(yōu)缺點(diǎn)

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

A*算法[4]：該算法從起點(diǎn)開始，檢查其從起點(diǎn)開始，遍歷起點(diǎn)周圍鄰近的點(diǎn)，然后再遍歷已經(jīng)遍歷過的點(diǎn)鄰近的點(diǎn)，逐步的向外擴(kuò)散，直到找到終點(diǎn)。該算法準(zhǔn)確性高、性能好，但可能出現(xiàn)目標(biāo)不可達(dá)而浪費(fèi)性能的現(xiàn)象。

Floyd算法[5]：該算法引用的是動(dòng)態(tài)規(guī)劃思想，在兩頂點(diǎn)間插入一個(gè)或以上的中轉(zhuǎn)點(diǎn)，比較經(jīng)過和未經(jīng)過中轉(zhuǎn)點(diǎn)的距離哪個(gè)更短。其主要用于求一條帶權(quán)值有向圖的任意兩點(diǎn)間的最短路徑。該算法實(shí)現(xiàn)簡(jiǎn)單，但實(shí)現(xiàn)復(fù)雜度高。

3 常用智能仿生算法及其優(yōu)缺點(diǎn)

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

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