梁曉輝 慕永輝 吳北華 江宇

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

Abstract： 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 characteristics， 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， improvement. Finally the future development trend of the path planning algorithm is forecasted.

關(guān)鍵詞：路徑規(guī)劃;進(jìn)化型算法;非進(jìn)化型算法;未來(lái)展望

Key words： path planning;evolutionary algorithm;non-evolutionary algorithm;future development

中圖分類(lèi)號(hào)：TP242? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2020）03-0295-05

0? 引言

路徑規(guī)劃（Path Planning）[1]是智能技術(shù)中的熱點(diǎn)研究問(wèn)題，已在多領(lǐng)域有所突破并成功得以應(yīng)用。

在軍事領(lǐng)域涉及到的有無(wú)人機(jī)飛行路徑自動(dòng)規(guī)劃[2]，導(dǎo)彈回避威脅[3]，智能機(jī)器人控制[4]，水下無(wú)人航行器（Unmanned underwater vehicle UUV）的自主航行[5]以及美國(guó)國(guó)防高級(jí)研究計(jì)劃局“小精靈”項(xiàng)目[6]等;在日常方面涉及的有基于地理信息系統(tǒng)（Geographic Information System，GIS）的路徑規(guī)劃[7]，城市智能交通動(dòng)態(tài)路徑規(guī)劃[8]，物流或外賣(mài)配送[9]以及自動(dòng)導(dǎo)引裝置（Automated Guided Vehicle，AGV）的路徑規(guī)劃與調(diào)度[10]等。[11]

路徑規(guī)劃的實(shí)現(xiàn)主要依靠高級(jí)語(yǔ)言編制出的算法，其主要包含：模擬退火法，A*算法，Dijkstra算法，遺傳算法，粒子束算法，人工勢(shì)場(chǎng)法，Voronoi法等。少部分路徑規(guī)劃也可通過(guò)硬件加以改善，例如可以使用微電子器件或光學(xué)器件解決路徑規(guī)劃在實(shí)時(shí)系統(tǒng)中速度慢的缺陷[12]。

1? 路徑規(guī)劃算法

依據(jù)算法實(shí)現(xiàn)原理，可將路徑規(guī)劃算法歸類(lèi)為非進(jìn)化型與進(jìn)化型兩種。

1.1 非進(jìn)化型算法

非進(jìn)化型算法具有簡(jiǎn)潔的設(shè)計(jì)思想流程和較高效率的處理能力。但在“機(jī)械式”解決路徑規(guī)劃問(wèn)題時(shí)，不易產(chǎn)生最優(yōu)路徑，且無(wú)法在過(guò)程中實(shí)現(xiàn)自我學(xué)習(xí)和自我完善，不具備記憶能力。在處理高維空間形式下的路徑規(guī)劃問(wèn)題時(shí)，結(jié)果與期望有較大偏差。

依據(jù)算法數(shù)學(xué)特征，可將非進(jìn)化型算法分成經(jīng)典數(shù)學(xué)與幾何圖論兩類(lèi)型。

1.1.1 經(jīng)典數(shù)學(xué)

①圖搜索概率法。

20世紀(jì)90年代初期，M.H.Overmars提出PRM（Probabilistic? Roadmaps? Method）圖搜索概率法[13-14]。PRM主要包含離線學(xué)習(xí)階段和在線學(xué)習(xí)階段，依據(jù)搜索算法在終始點(diǎn)之間的優(yōu)化規(guī)則形成路標(biāo)圖，并在一定條件的約束下有效的解決在多維空間和復(fù)雜環(huán)境中的路徑規(guī)劃問(wèn)題。

PRM圖搜索概率法的尋徑方式簡(jiǎn)便，整個(gè)規(guī)劃場(chǎng)景的大小與構(gòu)形空間的多維性沒(méi)有特別強(qiáng)烈的關(guān)系，因此復(fù)雜度較低，不需要精確建模。但由于所采集樣點(diǎn)隨機(jī)分布，無(wú)法覆蓋自由空間中的全部路徑，易出現(xiàn)搜索路徑不是所需的最優(yōu)路徑，同時(shí)在規(guī)劃路徑時(shí)遇到狹窄通路或是復(fù)雜度較高的障礙集合時(shí)，算法效率就會(huì)顯得十分低下。

在對(duì)PRM的改進(jìn)中，夏炎等人通過(guò)節(jié)點(diǎn)增強(qiáng)法將原路徑上的節(jié)點(diǎn)代替，利用圓弧替代路徑上的折線，達(dá)到減小節(jié)點(diǎn)拐點(diǎn)個(gè)數(shù)，縮短規(guī)劃路徑長(zhǎng)度，并實(shí)現(xiàn)搜索路徑有較高的平滑度[15]。G.Sanchez等人在PRM的基礎(chǔ)上提出了SBL-PRM算法，即通過(guò)從兩個(gè)基本位姿點(diǎn)出發(fā)，找到路徑后再經(jīng)過(guò)碰撞檢測(cè)等手段使得計(jì)算更加實(shí)時(shí)高效[16-17]。

②模擬退火算法。

1953年， N. Metropolis等人將模擬退火算法SA的思想提出。它通過(guò)模擬熱力學(xué)中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性并結(jié)合概率突跳特性，使得局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)的模式。

模擬退火法在算法實(shí)行中需要一個(gè)輸入作為初始解，在求解的過(guò)程中對(duì)于壞解具有包容性，不會(huì)局限于初始解所在的收斂域內(nèi)。模擬退火在計(jì)算中可跳出局部極小值點(diǎn)，造成了所獲得的解不一定是最優(yōu)解，卻一定是全局的次優(yōu)解，不可避免地使算法整體受參數(shù)影響，導(dǎo)致全局搜索能力變差[18]。

1985年，多目標(biāo)模擬退火算法MOSA被Ulungu提出，解決傳統(tǒng)的SA算法只針對(duì)單個(gè)目標(biāo)求解并表現(xiàn)出了良好的性能[19]。2011年，SankaraoB等人提出了一種具有魯棒性的多目標(biāo)退火算法rMOSA，能夠在較少的模擬次數(shù)下熟練到Pareto解集，使得在MOSA算法的基礎(chǔ)上實(shí)施擾動(dòng)選擇新解，從而具有魯棒性[20]。2005年，田東平等人將適合全局搜索的遺傳算法（GA）和適合局部搜索的模擬退火算法（SA）相結(jié)合，提出了混合GA-SA計(jì)算方法，有效提高了收斂速度，并有效防止種群早熟現(xiàn)象，且驗(yàn)證了該算法的可行性和有效性[21]。

③人工勢(shì)場(chǎng)法。

1986年，人工勢(shì)場(chǎng)法由Khatib博士[22]提出。它是一種虛擬力法，通過(guò)在目標(biāo)位置與障礙物周?chē)鷺?gòu)造出起共同作用的引力場(chǎng)與斥力場(chǎng)，再通過(guò)搜索勢(shì)函數(shù)的下降方向來(lái)規(guī)劃出無(wú)碰的最優(yōu)路徑，整個(gè)勢(shì)場(chǎng)力正是由引力部分和斥力部分組成[23]。

由于人工勢(shì)場(chǎng)法高效的實(shí)時(shí)控制性，可以實(shí)現(xiàn)實(shí)時(shí)路徑規(guī)劃和平滑軌跡處理，因而也得到了廣泛應(yīng)用。但是當(dāng)在勢(shì)場(chǎng)空間中同時(shí)出現(xiàn)多個(gè)障礙物時(shí)，易出現(xiàn)零勢(shì)能點(diǎn)，使勢(shì)能法陷入局部最小點(diǎn)，造成混亂，無(wú)法完成勢(shì)場(chǎng)空間中的路徑規(guī)劃任務(wù)[24]。

很多學(xué)者針對(duì)勢(shì)場(chǎng)原理的幾個(gè)缺點(diǎn)進(jìn)行了改進(jìn)，使其具備學(xué)習(xí)能力，從而可以適應(yīng)未知復(fù)雜環(huán)境或者能在多障礙物情況下消除零勢(shì)能 [25]。日本的Ya-Chun chang等人結(jié)合人工勢(shì)場(chǎng)法和Voronoi圖表法提出了一種混合的路徑規(guī)劃算法，在此計(jì)算中分別利用了兩種方法的優(yōu)點(diǎn)同時(shí)解決勢(shì)場(chǎng)信息構(gòu)造最優(yōu)路徑的選擇[26]。喬莎莎等人對(duì)于遺傳算法與人工勢(shì)場(chǎng)法進(jìn)行結(jié)合仿真，有效避免基于行為的盲目性，增加了路徑節(jié)點(diǎn)和平滑度，但對(duì)于全局規(guī)劃帶來(lái)的問(wèn)題把握不夠[27]。

④A*算法。

1968年，A*算法由Stanford研究院的Peter Hart等人共同發(fā)表，是一種常用的路徑查找和圖形遍歷算法。它通過(guò)尋找最小路徑來(lái)估算節(jié)點(diǎn)的代價(jià)評(píng)估函數(shù)并作為節(jié)點(diǎn)的綜合優(yōu)先級(jí)，當(dāng)選擇下一個(gè)需要遍歷的節(jié)點(diǎn)時(shí)，再選取綜合優(yōu)先級(jí)最高的節(jié)點(diǎn)一步步地找到最優(yōu)路徑。A* 算法的一般過(guò)程可在文獻(xiàn)中查到[28]。

A*算法可以方便的找到開(kāi)銷(xiāo)最小，路程最短的路徑，但是隨著數(shù)據(jù)量的增大，無(wú)用節(jié)點(diǎn)會(huì)導(dǎo)致A*算法搜索時(shí)間增長(zhǎng)，同時(shí)也可以通過(guò)調(diào)節(jié)啟發(fā)函數(shù)來(lái)控制算法的速度和精確度。

Szczerba等人提出了稀疏A*搜索算法（SAS），通過(guò)將約束條件與搜索算法結(jié)合起來(lái)，可有效剪裁搜索空間 [29]。高蝦蝦等人通過(guò)搜索節(jié)點(diǎn)進(jìn)行優(yōu)化，解決了二維航線中存在的局限性問(wèn)題，減少運(yùn)行時(shí)間和消耗內(nèi)存[30]。占偉偉等人也提出一種改進(jìn)的A*算法解決大范圍三維戰(zhàn)場(chǎng)環(huán)境的無(wú)人機(jī)航跡規(guī)劃問(wèn)題，但是由于戰(zhàn)場(chǎng)環(huán)境動(dòng)態(tài)變化，無(wú)法達(dá)到實(shí)時(shí)航跡規(guī)劃。

⑤Dijkstra算法。

1959年，Dijkstra算法由荷蘭科學(xué)家Edsger W.Dijkstra提出[31]。該算法是單源路徑算法，用來(lái)求解一個(gè)頂點(diǎn)到其余各項(xiàng)頂點(diǎn)的最短路徑問(wèn)題，它通過(guò)起始點(diǎn)為中心向外層層擴(kuò)展，直至擴(kuò)展到終點(diǎn)為止得到最短路徑。

Dijkstra算法十分簡(jiǎn)潔，能夠有效的找到最優(yōu)解，不足之處在數(shù)據(jù)節(jié)點(diǎn)龐大時(shí)所需的節(jié)點(diǎn)繁多，效率隨著數(shù)據(jù)節(jié)點(diǎn)的增加而下降，耗費(fèi)大量?jī)?nèi)存空間與計(jì)算時(shí)間。

侯莉莉等人以鄰接鏈表和最小二叉堆的數(shù)據(jù)結(jié)構(gòu)優(yōu)化了Dijkstra算法，改進(jìn)后的算法運(yùn)行時(shí)間有所減少，效率有所提高[32];何少佳等利用Dijkstra算法的優(yōu)點(diǎn)與蟻群算法進(jìn)行改進(jìn)，有效提高了搜索效率，縮短路徑長(zhǎng)度，改善搜索路徑質(zhì)量[33-34]。

⑥Floyd算法。

1978 年，F(xiàn)loyd 算法由圖靈獎(jiǎng)獲得者教授Robert W. Floyd命名，通過(guò)分析有權(quán)圖的帶權(quán)鄰接矩陣，而后在矩陣中求任意兩點(diǎn)的最短路徑[11]。Floyd 算法適用于任意兩點(diǎn)間的最短路徑，同時(shí)也被經(jīng)常用于計(jì)算有向圖的傳遞閉包，規(guī)劃效率要高于Dijkstra算法，但其復(fù)雜度達(dá)到了三次方的級(jí)別，不能直觀反映出各個(gè)頂點(diǎn)之間最短路徑序列的先后關(guān)系。

為了提高查找效率，減少頂點(diǎn)之間長(zhǎng)度比較，代修宇等人對(duì)傳統(tǒng)的Floyd 算法進(jìn)行了優(yōu)化改進(jìn)[35];王靖東通過(guò)對(duì)頂點(diǎn)過(guò)濾，頂點(diǎn)計(jì)算優(yōu)化和反比例優(yōu)化來(lái)提高路徑規(guī)劃成功率和效率[36]。程曉蓉等結(jié)合 Dijkstra 算法和 Floyd 算法的優(yōu)點(diǎn)，提出了一種新的求最短路徑的優(yōu)化算法——F.D 算法，并將這種更高效、快捷的方法應(yīng)用于求解基于 GIS 的電力通信路線最短路徑問(wèn)題上。

1.1.2 幾何圖論

①Voronoi圖算法。

1908年，俄國(guó)數(shù)學(xué)家 Georgy Fedoseevich提出Voronoi圖算法。這種空間分割算法的靈感來(lái)源于笛卡爾的凸域分割空間的思想，是計(jì)算幾何中的一個(gè)重要分支，對(duì)于路徑規(guī)劃的輔助性意義很大。Voronoi圖目前的生成算法主要有兩大類(lèi)：矢量法和柵格法[37]。

2007 年，Bhattacharya P 等人提出了一種基于 Voronoi 圖解障礙是簡(jiǎn)單多邊形的最短路徑問(wèn)題提供了詳細(xì)算法的描述，及 Voronoi 圖算法的維護(hù)和動(dòng)態(tài)的更新，該方法性能優(yōu)于其他有關(guān)路徑規(guī)劃算法[38]; 2010 年，徐鵬飛等人利用半平面與 Voronoi 頂點(diǎn)的位置關(guān)系，提出了簡(jiǎn)單增量構(gòu)造 Voronoi 圖的算法，此算法在處理 Voronoi 邊與節(jié)點(diǎn)的特殊情況，并且該算法的平均時(shí)間復(fù)雜度接近線性[39]。

1.2.4 遺傳算法

1962年，遺傳算法被John Holland[66]提出。它是模擬生物進(jìn)化論中的自然選擇和遺傳變異為基礎(chǔ)理論而形成的一種搜索算法。遺傳算法具有自組織，自適應(yīng)和自學(xué)習(xí)性，能夠同時(shí)處理多個(gè)群體中的多個(gè)個(gè)體，從串集進(jìn)行搜索，覆蓋面大，有利于全局搜索。但是其屬于隨機(jī)類(lèi)算法，結(jié)果的可靠性較差，不能穩(wěn)定的得到最優(yōu)解。

王璇通過(guò)將遺傳算法與粒子群算法和人工免疫算法相結(jié)合形成混合遺傳算法，有效提高收斂速度，且使算法不易陷入局部最優(yōu)值，并使用測(cè)試函數(shù)驗(yàn)證了算法收斂的有效性[67]。在文獻(xiàn)[68]中提出了量子遺傳算法，它是對(duì)量子計(jì)算和遺傳算法相結(jié)合的產(chǎn)物，使得算法的適應(yīng)性更強(qiáng)，效率更高;2016年，田欣提出新的自適應(yīng)調(diào)整方式，提高了遺傳算法的尋優(yōu)效率，并通過(guò)引入模擬退火算法克服遺傳算法有容易陷入局部最優(yōu)的缺點(diǎn)[69]。

1.2.5 粒子群算法

1995 年， Eberhart 等人提出 PSO 算法[70]。它是通過(guò)模擬鳥(niǎo)群的生存行為提出的一種新型群智能優(yōu)化算法，兼有進(jìn)化計(jì)算和群智能的特點(diǎn)來(lái)實(shí)現(xiàn)復(fù)雜空間中最優(yōu)解的搜索。PSO算法在初始時(shí)并非十分完善，在實(shí)際的應(yīng)用時(shí)往往出現(xiàn)早熟收斂和全局收斂性能差等缺點(diǎn)。

PSO在離散域問(wèn)題特別是組合優(yōu)化問(wèn)題的求解研究還比較少，這方面領(lǐng)域的研究被稱為離散PSO。1997年，J.Kennedy等人[71]提出了粒子群算法的離散二進(jìn)制版本，將經(jīng)過(guò)簡(jiǎn)單的修改，使其應(yīng)用于搜索二進(jìn)制的空間。Xiao-Feng Xie等人提出的自組織耗散PSO算法，從熱力學(xué)的角度指出PSO的社會(huì)模型具有自組織耗散結(jié)構(gòu)的特點(diǎn)，進(jìn)而引入了混亂算子，避免了群體過(guò)早的進(jìn)入穩(wěn)定狀態(tài)[72]。

2? 未來(lái)展望

路徑規(guī)劃算法目前多處于理論研究，試驗(yàn)或試運(yùn)行階段，應(yīng)用到實(shí)際層面仍需要一段時(shí)間。

同其它技術(shù)理論一樣，路徑規(guī)劃算法的產(chǎn)生與發(fā)展主要來(lái)自社會(huì)進(jìn)步和軍事需求，同時(shí)也受已有技術(shù)的限制。針對(duì)軍事領(lǐng)域或智能控制領(lǐng)域出現(xiàn)的復(fù)雜問(wèn)題，單一算法顯然無(wú)法高效解決。這就需要多學(xué)科知識(shí)的交叉融合，將具有不同優(yōu)勢(shì)的算法有效結(jié)合成更加高效的復(fù)合型路徑規(guī)劃算法，這也是目前主流的研究方向。

由于非進(jìn)化類(lèi)算法具有運(yùn)算量小、可實(shí)現(xiàn)性較強(qiáng)的優(yōu)勢(shì)，依舊占據(jù)著一定的生存空間。但隨硬件成本的降低，運(yùn)算能力水平不斷提升，具備人工智能的進(jìn)化類(lèi)算法必將成為該領(lǐng)域的核心。

未來(lái)很大概率會(huì)有更高效、實(shí)時(shí)、精確處理路徑規(guī)劃問(wèn)題的新算法誕生，使得軍事武器和生產(chǎn)生活智能化的前景更加廣闊。

參考文獻(xiàn)：

[1]謝娟.路徑規(guī)劃算法的研究及應(yīng)用[D].電子科技大學(xué)，2015，03.

[2]馬傳焱.多無(wú)人機(jī)飛行路徑自動(dòng)規(guī)劃算法研究[J].無(wú)線電工程，2015，45（2）：5-7，33.

[3]馬云紅，周德云.一種簡(jiǎn)單快速的導(dǎo)彈路徑規(guī)劃方法[J].導(dǎo)彈與制導(dǎo)學(xué)報(bào)，2005，25（3）：23-26.

[4]張佳，陳杰，竇麗華.基于路徑規(guī)劃的智能機(jī)器人控制實(shí)驗(yàn)[J].實(shí)驗(yàn)技術(shù)與管理，2010，27（12）：44-47.

[5]溫志文，蔡衛(wèi)軍，楊春武.UUV自主航行路徑規(guī)劃方法[J].制造業(yè)自動(dòng)化，2016，38（11）：1-5.

[6]袁成.美國(guó)國(guó)防高級(jí)研究計(jì)劃局“小精靈”項(xiàng)目[J].兵器知識(shí)，2016，9：37-39.

[7]孫蘭會(huì)，成鋒，陸愈實(shí).基于GIS的路徑規(guī)劃算法研究與實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2016，39（5）：101-109.

[8]李軍.城市智能交通中的動(dòng)態(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ì)[J].吉首大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，28（6）：74-76.

[13]L. E. Kavraki， P. Svestka， J. C. Latombe， and M. H. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces [J]. 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? Configuration- Spaces? [J].? IEEE? Transactions? on? Robotics and Automation， 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 Checking [C]. International Symposium on Robotics Research， Lorne， Australia， 2001.

[17]Sanchez G.， Latombe J. C. On Delaying Collision Checking in PRM Planning? Application to Multi-Robot Coordination [C]. 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]楊理云.用模擬退火算法求解旅行商問(wèn)題[J].微電子學(xué)與計(jì)算機(jī)，2007（05）：193-196.

[20]卜文浩.模擬退火算法綜述[D].西安理工大學(xué)，2007，08.

[21]田東平，遲洪欽.混合遺傳算法和模擬退火法[J].計(jì)算機(jī)工程與應(yīng)用，2006（22）：63-65.

[22]Khatib O.Realtime Abstract Avoidance for Manipulators，and Mobile Robots in Proe[J].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)人工勢(shì)場(chǎng)的改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，1005-3751（2006）04-0096-03.

[24]王奇志.基于改進(jìn)人工勢(shì)場(chǎng)法的多障礙機(jī)器人運(yùn)動(dòng)控制[C].北京：2003年中國(guó)智能自動(dòng)化會(huì)議論文論文集（上冊(cè)）.

[25]許亞.基于改進(jìn)的人工勢(shì)能場(chǎng)的移動(dòng)機(jī)器人的路徑規(guī)劃研究[J].科技展望，2016（33）.

[26]Chang? 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ó)慶.基于遺傳算法和人工勢(shì)場(chǎng)法的路徑規(guī)劃[J].現(xiàn)代電子技術(shù)，2012，35：75-78.

[28]熊壬浩，劉羽.A*算法的改進(jìn)及并行化[J].計(jì)算機(jī)應(yīng)用，2015，35（7）：1843-1848.

[29]NILSSON N.Problem-solving methods in artificial intelligence[M].IEEE Transactions on Aerospace and Electronic System，2000，36（3）：869-878.

[30]高蝦蝦，郭國(guó)龍，徐成華，馮蓉.基于改進(jìn)A*算法的三維飛行航線規(guī)劃.第三屆高分辨率對(duì)地觀測(cè)學(xué)術(shù)年會(huì)論文集[C].2014，12.

[31]Dijkstra E. A note on two problems in connexi on with graphs[J].Numerische Mathematik，1951，1（1）：269-271.

[32]趙磊，侯莉莉.一種Dijkstra算法的優(yōu)化實(shí)現(xiàn)算法-學(xué)術(shù)研究，2014.

[33]何少佳，史劍清，王海坤.基于改進(jìn)蟻群粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].桂林理工大學(xué)學(xué)報(bào)，2014，34（4）：765-770.

[34]王輝，朱龍彪，王景良，陳紅艷，邵小江，朱志慧.基于Dijkstra-蟻群算法的泊車(chē)系統(tǒng)路徑規(guī)劃研究[J].工程設(shè)計(jì)學(xué)報(bào)，2016，05.

[35]代修宇，程國(guó)忠.Floyd算法的改進(jìn)與優(yōu)化[J].西昌學(xué)院學(xué)報(bào)·自然科學(xué)版，2012，03：63-65.

[36]王靖東，楊凌.基于優(yōu)化Floyd算法的室內(nèi)機(jī)器人路徑規(guī)劃研究[D].西北農(nóng)林科技大學(xué)，2015.

[37]徐政超.基于voronoi圖算法的航路規(guī)劃方法研究[D].長(zhǎng)安大學(xué)，2015.

[38]BHATTACHARYA， GAVRILOVA M L. Voronoi Diagrami n Optimal Path Planning[C]. The 4th Int-ernational Symposium on Voronoi Diagrams in Science and Engineering， 2007： 38-47.

[39]徐鵬飛，陳志剛.增量構(gòu)造Voronoi區(qū)域的改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（8）：8-10.

[40]SHAMOS M I， HOEY D. Closest Point Problems[C]. In Proceedings of 16th IEEE Symposium on Foundations of Computer Science， 1975： 151-162.

[41]BARRY J， WANG C A. Duality of Constrained Voronoi Diagrams and Delaunay Triangulations[J]. Algorithmica， 1999， 9（2）： 142-155.

[42]徐鵬.基于模擬退火算法的機(jī)器人路徑規(guī)劃與研究[J].信息與通信，1671-4792-（2011）1-0042-03.

[43]鄭秀敏，顧大鵬，劉相術(shù).基于柵格法-模擬退火算法的機(jī)器人路徑規(guī)劃[J].機(jī)器人技術(shù)，1008-0570（2007）02- 2- 0247- 02.

[44]雷艷敏，馮志彬.改進(jìn)的勢(shì)場(chǎng)柵格法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J].長(zhǎng)春大學(xué)學(xué)報(bào)，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)化計(jì)算方法[M].清華大學(xué)出版社，2005：51-68.

[48]王凌.智能優(yōu)化算法及其應(yīng)用[M].清華大學(xué)出版社，2001.

[49]王玉晶.基于禁忌搜索算法的生理信號(hào)情感識(shí)別研究[D].西南大學(xué)，2008，05.

[50]J.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é)報(bào)，22（2）：94-98.

[53]李大衛(wèi)，王莉，王夢(mèng)光.遺傳算法與禁忌搜索算法的混合策略[J].系統(tǒng)工程學(xué)報(bào)，1998，13（3）：28-34.

[54]王超.基于混合遺傳禁忌搜索算法的多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題研究[D].重慶大學(xué)，2012.

[55]蘭任.基于并行混合粒子群算法的蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)[D].大連理工大學(xué)，2011.

[56]袁曾.人工神經(jīng)元網(wǎng)絡(luò)及其應(yīng)用[M].北京：清華大學(xué)出版社，1999，10.

[57]曾顯峰.基于人工神經(jīng)網(wǎng)絡(luò)的入侵檢測(cè)技術(shù)研究[D].廣州市：華南理工大學(xué)，2010.

[58]張雨濃.人工神經(jīng)網(wǎng)絡(luò)的面向?qū)ο筌浖?shí)現(xiàn)[D].廣州：華南理工大學(xué)，1999.

[59]劉品.BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化研究及應(yīng)用[D].中國(guó)地質(zhì)大學(xué)，2017，02.

[60]王和杰.基于遺傳算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)的汽車(chē)油耗計(jì)算模型[D].江蘇科技大學(xué)，2017.

[61]劉品.BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化研究及應(yīng)用[D].中國(guó)地質(zhì)大學(xué)，2017.

[62]Gambardella L M， Dorigo M.Ant-Q： a reinforcement learning approach to the traveling salesman problem.Proceedings of the 12th International Conference on Machine Learning， 1995： 252-260.

[63]Stutzle T，Hoos H.The MAX-MIN ant system and local search for the traveling salesmanproblem.Proceedings of the IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference，1997：309-314.

[64]徐精明，曹先彬，王煦法.多態(tài)蟻群算法[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào)，2005，35（l）：59-65.

[65]李擎，張超，陳鵬.一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法[J].控制與決策，2013，28（6）：873-878.

[66]Holland J.H. Outline for a logical theory of adaptive systems[J]. Journal of the Association for Computing Machinery，1962，9（3）：297-314.

[67]王璇.遺傳算法的改進(jìn)及其應(yīng)用研究[D].華北電力大學(xué)，2010.

[68]Yang Junan， Zhuang Zhenquan. Research of Quantum Genetic Algorithm and Its Application in Blind Source Separation.

[69]田欣.基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[D].鄭州大學(xué)，2016.

[70]Kenndy J， Eberhart R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks. 1995， 4： 1942-1948.

[71]J.Kennedy and R.C. Eberhart. A Discrete Binary Version of the Particle Swarm Algorithm. In Proceedings of the Conference on Systems， Man，and Cybernetics，1997：4104-4109.

[72]Xiao-Fen Xie， Wen-Jun Zhang， Zhi-Lian Yang. A Dissipative Particle Swarm Optimization.? Congress? on? Evolutionary Computation.2002：1456-1461.