路徑規(guī)劃的主要算法與展望

1、路徑規(guī)劃的主要算法與展望摘要：路徑規(guī)劃算法是智能領(lǐng)域中一項新興的關(guān)鍵支撐技術(shù)；依據(jù)路徑規(guī)劃算法的實現(xiàn)原理，將其分為進(jìn)化型算法與非進(jìn)化型算法；再依據(jù)數(shù)學(xué)特征將非進(jìn)化型算法細(xì)分為經(jīng)典數(shù)學(xué)與幾何圖論兩類；針對每類算法，分別從發(fā)展背景、設(shè)計思想、優(yōu)缺點、改進(jìn)與發(fā)展等方面簡要?dú)w納分析；最后對路徑規(guī)劃算法的未來發(fā)展趨勢進(jìn)行展望。關(guān)鍵詞：路徑規(guī)劃; 進(jìn)化型算法; 非進(jìn)化型算法; 未來展望;Summary of Path Planning AlgorithmsLIANG Xiao-hui MU Yong-hui WU Bei-hua JIANG YuShijiazhuang Campus of Army En

2、gineering UniversityAbstract：Path planning algorithm is an emerging key supporting technology in the field of intelligence; According to the implementation principle of path planning algorithm, it is divided into evolutionary algorithm and non-evolutionary algorithm; Then based on the mathematical c

3、haracteristics, the non-evolutionary algorithm can be divided into two types: classical mathematics and geometric graph theory; For each type of algorithm, the paper will give a brief summary and analysis from some aspects: the background of development,design ideas, advantages and disadvantages, im

4、provement. Finally the future development trend of the path planning algorithm is forecasted.0 引言路徑規(guī)劃（Path Planning)1是智能技術(shù)中的熱點研究問題，已在多領(lǐng)域有所突破并成功得以應(yīng)用。在軍事領(lǐng)域涉及到的有無人機(jī)飛行路徑自動規(guī)劃2，導(dǎo)彈回避威脅3，智能機(jī)器人控制4，水下無人航行器（Unmanned underwater vehicle UUV）的自主航行5以及美國國防高級研究計劃局小精靈;項目6等；在日常方面涉及的有基于地理信息系統(tǒng)（Geographic Information Sys

5、tem,GIS）的路徑規(guī)劃7，城市智能交通動態(tài)路徑規(guī)劃8，物流或外賣配送9以及自動導(dǎo)引裝置（Automated Guided Vehicle,AGV）的路徑規(guī)劃與調(diào)度10等。11路徑規(guī)劃的實現(xiàn)主要依靠高級語言編制出的算法，其主要包含：模擬退火法，A*算法，Dijkstra算法，遺傳算法，粒子束算法，人工勢場法，Voronoi法等。少部分路徑規(guī)劃也可通過硬件加以改善，例如可以使用微電子器件或光學(xué)器件解決路徑規(guī)劃在實時系統(tǒng)中速度慢的缺陷12。1 路徑規(guī)劃算法依據(jù)算法實現(xiàn)原理，可將路徑規(guī)劃算法歸類為非進(jìn)化型與進(jìn)化型兩種。1.1 非進(jìn)化型算法非進(jìn)化型算法具有簡潔的設(shè)計思想流程和較高效率的處理能力。但在

6、機(jī)械式;解決路徑規(guī)劃問題時，不易產(chǎn)生最優(yōu)路徑，且無法在過程中實現(xiàn)自我學(xué)習(xí)和自我完善，不具備記憶能力。在處理高維空間形式下的路徑規(guī)劃問題時，結(jié)果與期望有較大偏差。依據(jù)算法數(shù)學(xué)特征，可將非進(jìn)化型算法分成經(jīng)典數(shù)學(xué)與幾何圖論兩類型。1.1.1 經(jīng)典數(shù)學(xué)(1)圖搜索概率法。20世紀(jì)90年代初期，M.H.Overmars提出PRM(Probabilistic Roadmaps Method）圖搜索概率法13,14。PRM主要包含離線學(xué)習(xí)階段和在線學(xué)習(xí)階段，依據(jù)搜索算法在終始點之間的優(yōu)化規(guī)則形成路標(biāo)圖，并在一定條件的約束下有效的解決在多維空間和復(fù)雜環(huán)境中的路徑規(guī)劃問題。PRM圖搜索概率法的尋徑方式簡便，整個

7、規(guī)劃場景的大小與構(gòu)形空間的多維性沒有特別強(qiáng)烈的關(guān)系，因此復(fù)雜度較低，不需要精確建模。但由于所采集樣點隨機(jī)分布，無法覆蓋自由空間中的全部路徑，易出現(xiàn)搜索路徑不是所需的最優(yōu)路徑，同時在規(guī)劃路徑時遇到狹窄通路或是復(fù)雜度較高的障礙集合時，算法效率就會顯得十分低下。在對PRM的改進(jìn)中，夏炎等人通過節(jié)點增強(qiáng)法將原路徑上的節(jié)點代替，利用圓弧替代路徑上的折線，達(dá)到減小節(jié)點拐點個數(shù)，縮短規(guī)劃路徑長度，并實現(xiàn)搜索路徑有較高的平滑度15。G.Sanchez等人在PRM的基礎(chǔ)上提出了SBL-PRM算法，即通過從兩個基本位姿點出發(fā)，找到路徑后再經(jīng)過碰撞檢測等手段使得計算更加實時高效16,17。(2)模擬退火算法。195

8、3年，N.Metropolis等人將模擬退火算法SA的思想提出。它通過模擬熱力學(xué)中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性并結(jié)合概率突跳特性，使得局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)的模式。模擬退火法在算法實行中需要一個輸入作為初始解，在求解的過程中對于壞解具有包容性，不會局限于初始解所在的收斂域內(nèi)。模擬退火在計算中可跳出局部極小值點，造成了所獲得的解不一定是最優(yōu)解，卻一定是全局的次優(yōu)解，不可避免地使算法整體受參數(shù)影響，導(dǎo)致全局搜索能力變差18。1985年，多目標(biāo)模擬退火算法MOSA被Ulungu提出，解決傳統(tǒng)的SA算法只針對單個目標(biāo)求解并表現(xiàn)出了良好的性能19。2011年，Sa

9、nkaraoB等人提出了一種具有魯棒性的多目標(biāo)退火算法r MOSA，能夠在較少的模擬次數(shù)下熟練到Pareto解集，使得在MOSA算法的基礎(chǔ)上實施擾動選擇新解，從而具有魯棒性20。2005年，田東平等人將適合全局搜索的遺傳算法（GA）和適合局部搜索的模擬退火算法（SA）相結(jié)合，提出了混合GA-SA計算方法，有效提高了收斂速度，并有效防止種群早熟現(xiàn)象，且驗證了該算法的可行性和有效性21。(3)人工勢場法。1986年，人工勢場法由Khatib博士22提出。它是一種虛擬力法，通過在目標(biāo)位置與障礙物周圍構(gòu)造出起共同作用的引力場與斥力場，再通過搜索勢函數(shù)的下降方向來規(guī)劃出無碰的最優(yōu)路徑，整個勢場力正是由引

10、力部分和斥力部分組成23。由于人工勢場法高效的實時控制性，可以實現(xiàn)實時路徑規(guī)劃和平滑軌跡處理，因而也得到了廣泛應(yīng)用。但是當(dāng)在勢場空間中同時出現(xiàn)多個障礙物時，易出現(xiàn)零勢能點，使勢能法陷入局部最小點，造成混亂，無法完成勢場空間中的路徑規(guī)劃任務(wù)24。很多學(xué)者針對勢場原理的幾個缺點進(jìn)行了改進(jìn)，使其具備學(xué)習(xí)能力，從而可以適應(yīng)未知復(fù)雜環(huán)境或者能在多障礙物情況下消除零勢能25。日本的Ya-Chun chang等人結(jié)合人工勢場法和Voronoi圖表法提出了一種混合的路徑規(guī)劃算法，在此計算中分別利用了兩種方法的優(yōu)點同時解決勢場信息構(gòu)造最優(yōu)路徑的選擇26。喬莎莎等人對于遺傳算法與人工勢場法進(jìn)行結(jié)合仿真，有效避免基

11、于行為的盲目性，增加了路徑節(jié)點和平滑度，但對于全局規(guī)劃帶來的問題把握不夠27。(4)A*算法。1968年，A*算法由Stanford研究院的Peter Hart等人共同發(fā)表，是一種常用的路徑查找和圖形遍歷算法。它通過尋找最小路徑來估算節(jié)點的代價評估函數(shù)并作為節(jié)點的綜合優(yōu)先級，當(dāng)選擇下一個需要遍歷的節(jié)點時，再選取綜合優(yōu)先級最高的節(jié)點一步步地找到最優(yōu)路徑。A*算法的一般過程可在文獻(xiàn)中查到28。A*算法可以方便的找到開銷最小，路程最短的路徑，但是隨著數(shù)據(jù)量的增大，無用節(jié)點會導(dǎo)致A*算法搜索時間增長，同時也可以通過調(diào)節(jié)啟發(fā)函數(shù)來控制算法的速度和精確度。Szczerba等人提出了稀疏A*搜索算法（SAS

12、），通過將約束條件與搜索算法結(jié)合起來，可有效剪裁搜索空間29。高蝦蝦等人通過搜索節(jié)點進(jìn)行優(yōu)化，解決了二維航線中存在的局限性問題，減少運(yùn)行時間和消耗內(nèi)存30。占偉偉等人也提出一種改進(jìn)的A*算法解決大范圍三維戰(zhàn)場環(huán)境的無人機(jī)航跡規(guī)劃問題，但是由于戰(zhàn)場環(huán)境動態(tài)變化，無法達(dá)到實時航跡規(guī)劃。(5)Dijkstra算法。1959年，Dijkstra算法由荷蘭科學(xué)家Edsger W.Dijkstra提出31。該算法是單源路徑算法，用來求解一個頂點到其余各項頂點的最短路徑問題，它通過起始點為中心向外層層擴(kuò)展，直至擴(kuò)展到終點為止得到最短路徑。Dijkstra算法十分簡潔，能夠有效的找到最優(yōu)解，不足之處在數(shù)據(jù)節(jié)點

13、龐大時所需的節(jié)點繁多，效率隨著數(shù)據(jù)節(jié)點的增加而下降，耗費(fèi)大量內(nèi)存空間與計算時間。侯莉莉等人以鄰接鏈表和最小二叉堆的數(shù)據(jù)結(jié)構(gòu)優(yōu)化了Dijkstra算法，改進(jìn)后的算法運(yùn)行時間有所減少，效率有所提高32；何少佳等利用Dijkstra算法的優(yōu)點與蟻群算法進(jìn)行改進(jìn)，有效提高了搜索效率，縮短路徑長度，改善搜索路徑質(zhì)量33,34。(6)Floyd算法。1978年，F(xiàn)loyd算法由圖靈獎獲得者教授Robert W.Floyd命名，通過分析有權(quán)圖的帶權(quán)鄰接矩陣，而后在矩陣中求任意兩點的最短路徑11。Floyd算法適用于任意兩點間的最短路徑，同時也被經(jīng)常用于計算有向圖的傳遞閉包，規(guī)劃效率要高于Dijkstra算法

14、，但其復(fù)雜度達(dá)到了三次方的級別，不能直觀反映出各個頂點之間最短路徑序列的先后關(guān)系。為了提高查找效率，減少頂點之間長度比較，代修宇等人對傳統(tǒng)的Floyd算法進(jìn)行了優(yōu)化改進(jìn)35；王靖東通過對頂點過濾，頂點計算優(yōu)化和反比例優(yōu)化來提高路徑規(guī)劃成功率和效率36。程曉蓉等結(jié)合Dijkstra算法和Floyd算法的優(yōu)點，提出了一種新的求最短路徑的優(yōu)化算法F.D算法，并將這種更高效、快捷的方法應(yīng)用于求解基于GIS的電力通信路線最短路徑問題上。1.1.2 幾何圖論(1)Voronoi圖算法。1908年，俄國數(shù)學(xué)家Georgy Fedoseevich提出Voronoi圖算法。這種空間分割算法的靈感來源于笛卡爾的凸

15、域分割空間的思想，是計算幾何中的一個重要分支，對于路徑規(guī)劃的輔助性意義很大。Voronoi圖目前的生成算法主要有兩大類：矢量法和柵格法37。2007年，Bhattacharya P等人提出了一種基于Voronoi圖解障礙是簡單多邊形的最短路徑問題提供了詳細(xì)算法的描述，及Voronoi圖算法的維護(hù)和動態(tài)的更新，該方法性能優(yōu)于其他有關(guān)路徑規(guī)劃算法38;2010年，徐鵬飛等人利用半平面與Voronoi頂點的位置關(guān)系，提出了簡單增量構(gòu)造Voronoi圖的算法，此算法在處理Voronoi邊與節(jié)點的特殊情況，并且該算法的平均時間復(fù)雜度接近線性39。(2)矢量法。矢量法包括以下幾種經(jīng)典型算法：分治法、增量法

16、、和間接法-Delaunay三角網(wǎng)法。矢量法提高了運(yùn)算的復(fù)雜程度，縮短了運(yùn)算時間，不影響全局空間的分割，具有精度高，效率高的特性，但是也造成生成圖像的精準(zhǔn)度不夠，儲存結(jié)構(gòu)也相對復(fù)雜37。在Voronoi圖的發(fā)展歷程中，矢量法的出現(xiàn)要早于柵格法。1975年，謝姆斯等人提出的采用分治法構(gòu)造平面點集Voronoi圖算法40;1993年，Barry J等人把線狀障礙物的VSP-VD和Delaunay三角網(wǎng)分別定義為有限制的Voronoi圖和有限制的Delaunay三角網(wǎng)41。(3)柵格法。1968年，柵格法由W.E.Howden提出，它將路徑規(guī)劃所占用的環(huán)境分解成具有二值信息的網(wǎng)絡(luò)單元42。這種方法的

17、特點是簡單、易于實現(xiàn)，它同時具有表達(dá)不規(guī)則障礙物的能力。其缺點是表示效率不高，存在著時空開銷與求解精度之間的矛盾。路徑規(guī)劃時柵格法多以環(huán)境建模形式存在，采以柵格（grid）來表示環(huán)境信息，以此避免復(fù)雜的計算。單位柵格越小，障礙物的表示越精確，但也會浪費(fèi)大量的存儲空間，搜索的范圍會以指數(shù)的形式激增。單位柵格過大，由算法規(guī)劃的路徑會變得很不精確。43目前基于對柵格法改進(jìn)方案多是通過與其它算法的復(fù)合。2009年，雷艷敏等提出通過對柵格屬性的設(shè)置來彌補(bǔ)勢場法和柵格法的缺點，仿真結(jié)果表明該方法是可行有效的44;2007年，鄭秀敏等提出將柵格法與模擬退火法進(jìn)行結(jié)合，采用柵格法表示環(huán)境信息，模擬退火法來進(jìn)行

18、局部的路徑規(guī)劃成功提高了路徑規(guī)劃的效率，增強(qiáng)了可靠性45。1.2 進(jìn)化型算法進(jìn)化型算法可以理解成智能算法，是人們受自然（生物界）規(guī)律得到的啟迪而模仿出的算法，具有一定的自我學(xué)習(xí)，自我更新和記憶能力。對問題的解決方式較為復(fù)雜，能夠處理復(fù)雜的路徑規(guī)劃問題，但是在龐大的計算量下易造成效率低下，無法高效的完成實時控制。1.2.1 禁忌搜索法1986年，禁忌搜索算法（Tabu Search,TS）由Glover教授正式提出，是一種亞啟發(fā)式（meta-henristic）的搜索算法46,47,48。TS通過引入一個靈活的存儲結(jié)構(gòu)和與之對應(yīng)的禁忌準(zhǔn)則，并通過藐視準(zhǔn)則赦免一些被禁忌的優(yōu)良狀態(tài)，借此保證多樣化的

19、有效搜索來實現(xiàn)最終的全局優(yōu)化。其最主要的特點就是采用了禁忌技術(shù)和特赦規(guī)則，使得算法可以跳出局部最優(yōu)解，進(jìn)行有效的計算，最終實現(xiàn)全局的優(yōu)化49。禁忌搜索算法易于實現(xiàn)，通用性及局部開發(fā)能力較強(qiáng)，收斂速度快，但全局開發(fā)能力相對較弱，搜索結(jié)果完全依賴于初始解和領(lǐng)域的映射關(guān)系。混合算法的出現(xiàn)，尤其是遺傳算法和模擬退火算法的有效結(jié)合對于算法性能和效率有較大幅度的改善50,51,52,53。2012年，王超利用禁忌搜索算法和遺傳算法的特點將二者結(jié)合，得到較強(qiáng)的全局搜索能力和局部搜索能力的混合算法54;2010年，蘭任55在其論文中利用粒子群PSO算法前期收斂速度快和TS的優(yōu)點對蛋白質(zhì)結(jié)構(gòu)進(jìn)行預(yù)測，通過對結(jié)果

20、的分析驗證了混合型算法的優(yōu)越性。1.2.2 神經(jīng)網(wǎng)絡(luò)算法神經(jīng)網(wǎng)絡(luò)算法（Neural Network）是一種以人腦的神經(jīng)網(wǎng)絡(luò)作為啟發(fā)，通過簡化，抽象與模擬人腦存儲和處理信息的過程并用數(shù)學(xué)語言加以描述而衍生出來的智能化信息處理技術(shù)56。根據(jù)學(xué)習(xí)算法與網(wǎng)絡(luò)結(jié)構(gòu)兩個方面相結(jié)合的角度來對神經(jīng)網(wǎng)絡(luò)進(jìn)行分類57，有以下幾個類別，單層前向網(wǎng)絡(luò)，多層前向網(wǎng)絡(luò)，反饋神經(jīng)網(wǎng)絡(luò)，隨機(jī)神經(jīng)網(wǎng)絡(luò)和競爭神經(jīng)網(wǎng)絡(luò)等。神經(jīng)網(wǎng)絡(luò)算法具有自學(xué)習(xí)，聯(lián)想存儲，具備高速尋找最優(yōu)解的能力，但是算法的網(wǎng)絡(luò)參數(shù)較多，屬于黑盒狀態(tài)，不可觀察結(jié)果，學(xué)習(xí)時間較長，容易陷入局部最小值。BP(Back Propagation）算法是人工神經(jīng)網(wǎng)絡(luò)中研究最

21、為成熟，應(yīng)用也是最為廣泛的人工神經(jīng)網(wǎng)絡(luò)模型之一58，它由Rumelhart等人在1986年提出，按照誤差逆向傳播算法訓(xùn)練的多層前饋神經(jīng)網(wǎng)絡(luò)，其結(jié)構(gòu)簡單，可塑性強(qiáng)，具有自我學(xué)習(xí)的特性，但是學(xué)習(xí)速率固定，不儲存學(xué)習(xí)過程中的參數(shù)，因此無記憶能力59。神經(jīng)網(wǎng)絡(luò)算法與其它算法的有機(jī)結(jié)合是目前改進(jìn)劣勢的重要方式。2016年，王和杰提出用遺傳算法來優(yōu)化BP神經(jīng)網(wǎng)絡(luò)，改善初始值和閾值，可充分發(fā)揮BP神經(jīng)網(wǎng)絡(luò)的局部搜索能力，提高算法穩(wěn)定性，避免陷入局部最優(yōu)值60。2017年，劉品提出采用高階神經(jīng)網(wǎng)絡(luò)對BP網(wǎng)絡(luò)模型結(jié)構(gòu)進(jìn)行優(yōu)化，能夠產(chǎn)生更好的擬合，可以解決高度復(fù)雜問題61。1.2.3 蟻群算法二十世紀(jì)九十年代，意

22、大利學(xué)者Dorigo Mden通過模擬螞蟻的行為規(guī)律，以螞蟻在自然界中協(xié)同工作尋找食物為數(shù)學(xué)模型提出了蟻群算法（Ant Colony Optimization），這是一種貪婪啟發(fā)式的搜索算法。傳統(tǒng)蟻群算法具有正反饋機(jī)制，加強(qiáng)了算法的尋優(yōu)能力，個體與個體建立的信息共享，互相合作，促進(jìn)該算法能夠搜索到最優(yōu)解。蟻群算法易于與其他算法結(jié)合使用，擁有更強(qiáng)大的搜索能力。但是無法實現(xiàn)實時在線搜索，尤其是面對空間較大，不易在有限時間內(nèi)找到最優(yōu)解，且其易陷入局部最優(yōu)的局面。Gambardella等人在1995年提出Ant-Q蟻群算法，此算法通過最優(yōu)信息的反饋，以較大的概率選擇信息素強(qiáng)度最大的路徑62;Stutz

23、le and Hoos在1997年改進(jìn)擴(kuò)展了蟻群算法的全局搜索范圍，減小了算法陷入局部最優(yōu)導(dǎo)致早熟現(xiàn)象發(fā)生的幾率63；徐精明等人首次提出了多態(tài)蟻群算法，對人工蟻進(jìn)行合理分工，結(jié)合局部與全局搜索，加快了算法收斂速度64;2013年，李擎等人提出了粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法，通過全局異步和精英策略成功減少粒子群算法調(diào)用蟻群算法的迭代次數(shù)65。1.2.4 遺傳算法1962年，遺傳算法被John Holland66提出。它是模擬生物進(jìn)化論中的自然選擇和遺傳變異為基礎(chǔ)理論而形成的一種搜索算法。遺傳算法具有自組織，自適應(yīng)和自學(xué)習(xí)性，能夠同時處理多個群體中的多個個體，從串集進(jìn)行搜索，覆蓋面大，有利于全局搜

24、索。但是其屬于隨機(jī)類算法，結(jié)果的可靠性較差，不能穩(wěn)定的得到最優(yōu)解。王璇通過將遺傳算法與粒子群算法和人工免疫算法相結(jié)合形成混合遺傳算法，有效提高收斂速度，且使算法不易陷入局部最優(yōu)值，并使用測試函數(shù)驗證了算法收斂的有效性67。在文獻(xiàn)68中提出了量子遺傳算法，它是對量子計算和遺傳算法相結(jié)合的產(chǎn)物，使得算法的適應(yīng)性更強(qiáng)，效率更高；2016年，田欣提出新的自適應(yīng)調(diào)整方式，提高了遺傳算法的尋優(yōu)效率，并通過引入模擬退火算法克服遺傳算法有容易陷入局部最優(yōu)的缺點69。1.2.5 粒子群算法1995年，Eberhart等人提出PSO算法70。它是通過模擬鳥群的生存行為提出的一種新型群智能優(yōu)化算法，兼有進(jìn)化計算和群

25、智能的特點來實現(xiàn)復(fù)雜空間中最優(yōu)解的搜索。PSO算法在初始時并非十分完善，在實際的應(yīng)用時往往出現(xiàn)早熟收斂和全局收斂性能差等缺點。PSO在離散域問題特別是組合優(yōu)化問題的求解研究還比較少，這方面領(lǐng)域的研究被稱為離散PSO。1997年，J.Kennedy等人71提出了粒子群算法的離散二進(jìn)制版本，將經(jīng)過簡單的修改，使其應(yīng)用于搜索二進(jìn)制的空間。XiaoFeng Xie等人提出的自組織耗散PSO算法，從熱力學(xué)的角度指出PSO的社會模型具有自組織耗散結(jié)構(gòu)的特點，進(jìn)而引入了混亂算子，避免了群體過早的進(jìn)入穩(wěn)定狀態(tài)72。2 未來展望路徑規(guī)劃算法目前多處于理論研究，試驗或試運(yùn)行階段，應(yīng)用到實際層面仍需要一段時間。同其

26、它技術(shù)理論一樣，路徑規(guī)劃算法的產(chǎn)生與發(fā)展主要來自社會進(jìn)步和軍事需求，同時也受已有技術(shù)的限制。針對軍事領(lǐng)域或智能控制領(lǐng)域出現(xiàn)的復(fù)雜問題，單一算法顯然無法高效解決。這就需要多學(xué)科知識的交叉融合，將具有不同優(yōu)勢的算法有效結(jié)合成更加高效的復(fù)合型路徑規(guī)劃算法，這也是目前主流的研究方向。由于非進(jìn)化類算法具有運(yùn)算量小、可實現(xiàn)性較強(qiáng)的優(yōu)勢，依舊占據(jù)著一定的生存空間。但隨硬件成本的降低，運(yùn)算能力水平不斷提升，具備人工智能的進(jìn)化類算法必將成為該領(lǐng)域的核心。未來很大概率會有更高效、實時、精確處理路徑規(guī)劃問題的新算法誕生，使得軍事武器和生產(chǎn)生活智能化的前景更加廣闊。參考文獻(xiàn)1謝娟.路徑規(guī)劃算法的研究及應(yīng)用D.電子科技

27、大學(xué)，2015,03.2馬傳焱多無人機(jī)飛行路徑自動規(guī)劃算法研究J無線電工程，2015,45(2):5-7,33.3馬云紅，周德云一種簡單快速的導(dǎo)彈路徑規(guī)劃方法J導(dǎo)彈與制導(dǎo)學(xué)報，2005,25(3):23-26.4張佳，陳杰，竇麗華基于路徑規(guī)劃的智能機(jī)器人控制實驗J實驗技術(shù)與管理，2010,27(12):44-47.5溫志文，蔡衛(wèi)軍，楊春武UUV自主航行路徑規(guī)劃方法J制造業(yè)自動化，2016,38(11):1-5.6袁成美國國防高級研究計劃局小精靈;項目J兵器知識，2016,9:37-39.7孫蘭會，成鋒，陸愈實基于GIS的路徑規(guī)劃算法研究與實現(xiàn)J現(xiàn)代電子技術(shù)，2016,39(5):101-109

28、.8 李軍.城市智能交通中的動態(tài)路徑規(guī)劃研究D.杭州電子科技大學(xué)，2017,04.9 高小芳.物流配送最優(yōu)路徑規(guī)劃D.華僑大學(xué)，2017,02.10 劉維民AGV路徑規(guī)劃與調(diào)度系統(tǒng)研究D.華南理工大學(xué)，2017,02.11張廣林，胡小梅，柴劍飛，趙磊，俞濤路徑規(guī)劃算法及其應(yīng)用綜述J現(xiàn)代機(jī)械，2011,5:85-90.12曾慶立，李麗華，唐圣學(xué)基于神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃的硬件設(shè)計J吉首大學(xué)學(xué)報（自然科學(xué)版），2007,28(6):74-76.13 L. E. Kavraki, P. Svestka, J. C. Latombe, and M. H.Overmars. Probabilistic roa

29、dmaps for path planning in highdimensional configuration spacesJ. IEEE Transactions on Robotics and Automation, 1996,12(4):566-580.14 Kavrak i L, Svestka P, Latombe J C, et al. Probabilistic Road Maps for Path Planning in High-dimensional ConfigurationSpacesJ. IEEE Transactions on Robotics and Autom

30、ation,1996,12(4):566-580.15夏炎，隋巖.PRM路徑規(guī)劃算法優(yōu)化研究J.應(yīng)用科技，2010,37(10):1-5.16 Sanchez G.,Latombe J. C. Single-Query Bi-Directional Motion Planning with lazy Collision CheckingC. International Symposium on Robotics Research, Lorne, Australia, 2001.17 Sanchez G., Latombe J. C. On Delaying Collision Checking

31、 in PRM Planning Application to Multi-Robot CoordinationC.International Journal of Robotics Research, 2002, 21(1):5-26.18 鄭秀敏，顧大鵬，劉相術(shù).基于柵格法-模擬退火算法的機(jī)器人路徑規(guī)劃J.機(jī)器人技術(shù)，1008-0570(2007)02-2-0247-02.19楊理云.用模擬退火算法求解旅行商問題J.微電子學(xué)與計算機(jī)，2007(05):193-196.20 卜文浩.模擬退火算法綜述D.西安理工大學(xué)，2007,08.21田東平，遲洪欽.混合遺傳算法和模擬退火法J.計算機(jī)工程與

32、應(yīng)用，2006(22):63-65.22 Khatib O.Realtime Abstract Avoidance for Manipulators,and Mobile Robots in ProeJ.IEEE Int Conf.On.Robotics and Automation March 25-381985.500-505,also in Int JRobot Res,1986,5(1):90-98.23王肖青，王奇志.傳統(tǒng)人工勢場的改進(jìn)J.計算機(jī)技術(shù)與發(fā)展，1005-3751(2006)04-0096-03.24王奇志.基于改進(jìn)人工勢場法的多障礙機(jī)器人運(yùn)動控制C.北京：2003年中國

33、智能自動化會議論文論文集（上冊）.25許亞.基于改進(jìn)的人工勢能場的移動機(jī)器人的路徑規(guī)劃研究J.科技展望，2016(33).26Chang Y-C,Yamamoto Y.Pathplanning of whelled mobile robot with simultaneous free space locating capability,Intelligent Service Robotics,2009,2(1):19-22.27喬莎莎，吳勇，張建東，史國慶.基于遺傳算法和人工勢場法的路徑規(guī)劃J.現(xiàn)代電子技術(shù)，2012,35:75-78.28熊壬浩，劉羽.A*算法的改進(jìn)及并行化J.計算機(jī)應(yīng)用，

34、2015,35(7):1843-1848.29 NILSSON N.Problem-solving methods in artificial intelligenceM.IEEE Transactions on Aerospace and Electronic System,2000,36(3):869-878.30高蝦蝦，郭國龍，徐成華，馮蓉.基于改進(jìn)A*算法的三維飛行航線規(guī)劃.第三屆高分辨率對地觀測學(xué)術(shù)年會論文集C.2014,12.31Dijkstra E. A note on two problems in connexi on with graphsJ.Numerische Math

35、ematik,1951,1(1):269-271.32趙磊，侯莉莉.一種Dijkstra算法的優(yōu)化實現(xiàn)算法-學(xué)術(shù)研究，2014.33何少佳，史劍清，王海坤.基于改進(jìn)蟻群粒子群算法的移動機(jī)器人路徑規(guī)劃J.桂林理工大學(xué)學(xué)報，2014,34(4):765-770.34王輝，朱龍彪，王景良，陳紅艷，邵小江，朱志慧.基于Dijkstra-蟻群算法的泊車系統(tǒng)路徑規(guī)劃研究J.工程設(shè)計學(xué)報，2016,05.35代修宇，程國忠.Floyd算法的改進(jìn)與優(yōu)化J.西昌學(xué)院學(xué)報·自然科學(xué)版，2012,03:63-65.36王靖東，楊凌.基于優(yōu)化Floyd算法的室內(nèi)機(jī)器人路徑規(guī)劃研究D.西北農(nóng)林科技大學(xué)，2

36、015.37 徐政超.基于voronoi圖算法的航路規(guī)劃方法研究D.長安大學(xué)，2015.38 BHATTACHARYA, GAVRILOVA M L. Voronoi Diagrami n Optimal Path PlanningC. The 4th Int-ernational Symposium on Voronoi Diagrams in Science and Engineering, 2007:38-47.39徐鵬飛，陳志剛.增量構(gòu)造Voronoi區(qū)域的改進(jìn)算法J.計算機(jī)工程與應(yīng)用，2010,46(8):8-10.40 SHAMOS M I, HOEY D. Closest Poi

37、nt ProblemsC. In Proceedings of 16th IEEE Symposium on Foundations of Computer Science, 1975:151-162.41BARRY J, WANG C A. Duality of Constrained Voronoi Diagrams and Delaunay TriangulationsJ. Algorithmica, 1999, 9(2):142-155.42 徐鵬.基于模擬退火算法的機(jī)器人路徑規(guī)劃與研究J.信息與通信，1671-4792-(2011)1-0042-03.43 鄭秀敏，顧大鵬，劉相術(shù).基

38、于柵格法-模擬退火算法的機(jī)器人路徑規(guī)劃J.機(jī)器人技術(shù)，1008-0570(2007)02-2-0247-02.44雷艷敏，馮志彬.改進(jìn)的勢場柵格法在機(jī)器人路徑規(guī)劃中的應(yīng)用J.長春大學(xué)學(xué)報，2009,19(1):38-42.45 鄭秀敏，顧大鵬，劉相術(shù).基于柵格法-模擬退火法的機(jī)器人路徑規(guī)劃J.機(jī)器人技術(shù)，1008-0570(2007)02-2-0247-02.46 Glover F.and M. Tabu Search. Boston, Kluwer Academic Publishers,1997.47邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計算方法M.清華大學(xué)出版社，2005:51-68.48王凌.智能優(yōu)

39、化算法及其應(yīng)用M.清華大學(xué)出版社，2001.49王玉晶.基于禁忌搜索算法的生理信號情感識別研究D.西南大學(xué)，2008,05.50J.A. Hageman et. al.,Hybrid genetic algorithm-tabu search approach for optimising multilayer optical coatings,Analytica Chimica Acta, 490, 2003,211-222.51柯坷，張世英.禁忌一遞階遺傳算法研究J.控制與決策，2001,16(4):480-483.52孫艷豐，鄭加齊.GATS混合算法及其收斂性研究J.鐵道學(xué)報，22(2)

40、:94-98.53李大衛(wèi)，王莉，王夢光.遺傳算法與禁忌搜索算法的混合策略J.系統(tǒng)工程學(xué)報，1998,13(3):28-34.54王超.基于混合遺傳禁忌搜索算法的多目標(biāo)柔性作業(yè)車間調(diào)度問題研究D.重慶大學(xué)，2012.55 蘭任.基于并行混合粒子群算法的蛋白質(zhì)結(jié)構(gòu)預(yù)測D.大連理工大學(xué)，2011.56 袁曾人工神經(jīng)元網(wǎng)絡(luò)及其應(yīng)用M北京：清華大學(xué)出版社，1999,10.57曾顯峰基于人工神經(jīng)網(wǎng)絡(luò)的入侵檢測技術(shù)研究D.廣州市：華南理工大學(xué)，2010.58 張雨濃.人工神經(jīng)網(wǎng)絡(luò)的面向?qū)ο筌浖崿F(xiàn)D.廣州：華南理工大學(xué)，1999.59 劉品.BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化研究及應(yīng)用D.中國地質(zhì)大學(xué)，2017,02.60 王和杰.基于遺傳算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)的汽車油耗計算模