引言：易發(fā)表網(wǎng)憑借豐富的文秘實(shí)踐，為您精心挑選了九篇路徑規(guī)劃范例。如需獲取更多原創(chuàng)內(nèi)容，可隨時(shí)聯(lián)系我們的客服老師。

第1篇

關(guān)鍵詞 自動(dòng)泊車；最佳泊車路徑

中圖分類號(hào)：TP182 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671—7597（2013）041-184-01

經(jīng)過(guò)一百二十多年的發(fā)展，汽車逐漸向小型化、智能化和安全化的方向發(fā)展。而隨著我國(guó)經(jīng)濟(jì)的發(fā)展，汽車的需求量逐年遞增。于此同時(shí)帶來(lái)的問(wèn)題是停車位需求量越來(lái)越大。而在國(guó)內(nèi)，城市占道停車不但能有效的滿足停車位的需求，而且能有效緩解交通堵塞。但是，對(duì)于許多駕駛員而言，順式駐車通常是駕駛員考試中最令人擔(dān)心的一項(xiàng)，而且?guī)缀趺總€(gè)人都會(huì)在某些地點(diǎn)碰到這樣的事情。大城市停車空間有限，將汽車駛?cè)氇M小的空間已成為一項(xiàng)必備技能。 很少有不費(fèi)一番周折就停好車的情況，特別是城市占道停車可能導(dǎo)致交通阻塞、神經(jīng)疲憊和保險(xiǎn)杠被撞彎，占道停車成為了一種痛苦的經(jīng)歷。

在實(shí)際泊車中駕駛員的視野狹隘，僅通過(guò)后視鏡來(lái)觀察車身后面和車周圍的情況，即使如此，也很難準(zhǔn)確的把握車尾的情況。不僅如此，駕駛員還要兼顧控制方向盤(pán)、油門、剎車和換擋等，易造成操作失誤。如果停車時(shí)間過(guò)長(zhǎng)，又容易造成交通堵塞，特別是駕車新手，在缺乏經(jīng)驗(yàn)的情況下，很難準(zhǔn)確停入車位。

基于以上問(wèn)題，尋找到了最佳泊車路徑，以解決廣大駕駛員泊車難的問(wèn)題。

1 自動(dòng)泊車最佳路徑規(guī)劃

最佳路徑雖然可以通過(guò)數(shù)學(xué)建模和泊車經(jīng)驗(yàn)等方法得出，但可靠性低，運(yùn)算復(fù)雜，而且變量較多，如果通過(guò)CAD與Pro/e等繪圖軟件模擬其幾何路徑，則可節(jié)省多處計(jì)算而且能簡(jiǎn)潔直觀的表達(dá)。使用CAD繪圖軟件尋找最佳路徑，主要是通過(guò)一些相關(guān)約束條件和泊車要求繪制最佳幾何路徑。

1.1 泊車危險(xiǎn)點(diǎn)與安全圓

倒車最難在于兼顧控制車輛的時(shí)候，難以觀察自己車輛是否與其它車輛相撞，經(jīng)過(guò)分析可知，倒車時(shí)，最容易觸碰的地方是尾部的后對(duì)角點(diǎn)和前部的前對(duì)角點(diǎn)。根據(jù)避免碰撞要求，可以在停車前方的最佳停車位上的對(duì)角點(diǎn)繪制一個(gè)以汽車前輪軸中點(diǎn)與對(duì)角的距離為半徑的圓R1，圓R1稱為安全圓。

汽車行駛的軌跡為一個(gè)個(gè)圓弧構(gòu)成的圓，由此可知，只需要其自動(dòng)泊車軌跡與安全圓相離或者相切就不會(huì)與前方車輛相撞，而后對(duì)角點(diǎn)只需控制其倒車行程即可避免碰撞。

1.2 泊車關(guān)鍵圓的確定

自動(dòng)泊車進(jìn)入車位是關(guān)鍵階段，把倒入車位的大圓稱為關(guān)鍵圓。首先可以認(rèn)為軸距是其軌跡圓的一根弦，經(jīng)分析可知，此圓越大，倒入車位后此弦與水平線所成的夾角a也就越小，泊車就越準(zhǔn)確，泊車后需要調(diào)整的角度就越小，因此假設(shè)關(guān)鍵圓R2與R1相切，且與車位中線相切時(shí)可取最大圓，由于與R1安全圓相切，所以能保證兩個(gè)對(duì)角點(diǎn)不與其他車輛發(fā)生碰撞，并且有足夠的空間可以進(jìn)行泊車后的角度調(diào)整。

由CAD模擬可以直接測(cè)量得出R2=5702 mm，又由汽車參數(shù)可知模擬車輛最小轉(zhuǎn)彎半徑為r=5500 mm，有R2>r，所以其關(guān)鍵圓R2符合汽車的行駛要求。

1.3 泊車輔助圓的確定

輔助圓是為了幫助車輛倒入關(guān)鍵圓的一段圓弧，使得車輛最終在倒車時(shí)能夠按照R1的軌跡進(jìn)入車位。經(jīng)過(guò)分析可知，輔助圓R3越大，越是難以矯正車輛進(jìn)入關(guān)鍵圓R2，故以最小轉(zhuǎn)向半徑5500 mm計(jì)算，經(jīng)過(guò)測(cè)試調(diào)查可知，駕駛員使車輛行駛在車道中間較容易控制，所以把初始位置定在車道中線上，故輔助圓需與行駛車道中線和關(guān)鍵圓R2相切，這樣便可以確定輔助圓R3。

另外，考慮到變換軌跡時(shí)，車輛是以車身前后軸中心的連線即軸距所構(gòu)成的弦進(jìn)入R2軌道，所以，需使R3向左平移，使得R3與R2相割所構(gòu)成的弦與車身前后軸中心的連線即軸距長(zhǎng)度相等。經(jīng)過(guò)CAD模擬和測(cè)量可知需使R3向左平移452.3 mm，即可獲得R3的最終位置。

1.4 泊車路徑總結(jié)

如上分析和建?？芍?，找到了安全圓、關(guān)鍵圓和輔助圓，將其合并在一起，即可得到最佳泊車路徑如圖1所示。

如上所示，駕駛員需要先將車輛行駛至道路中間，當(dāng)找到停車位時(shí)，駕駛員需要尋找一定的參照，使得車量后輪與車位前方車輛的前輪稍后的地方確定初始位置。首先把方向盤(pán)右轉(zhuǎn)至打死，開(kāi)始倒車，車輛進(jìn)入輔助圓，當(dāng)車輛與水平方向夾角大致成50度時(shí)，再把方向盤(pán)左轉(zhuǎn)打死，直到車輛進(jìn)入車位，再調(diào)整車輛與水平線所成的角度，即可進(jìn)入最佳車位。

如上所述可得到泊車的完整路徑，不容易與其他車輛發(fā)生碰撞，并且容易確定泊車的初始位置，所以安全可靠，具有較高的可行性。但是，即使最佳路徑也不可能一次性倒入車位。第一次倒入車位后需要細(xì)微的調(diào)整，由于調(diào)整路徑比較復(fù)雜，其規(guī)律性需要從汽車試驗(yàn)中尋找規(guī)律，所以調(diào)整路徑暫不使用模擬CAD得出。

2 泊車最佳路徑的驗(yàn)證

選擇模擬小車對(duì)最佳路徑進(jìn)行驗(yàn)證，模擬小車的實(shí)際尺寸與研究對(duì)象車輛的實(shí)際尺寸比為1：10.47，由最佳路徑分析中的CAD模擬路徑可知，輔助圓半徑為5500 mm，而關(guān)鍵圓半徑為：5702 mm。驗(yàn)證過(guò)程選擇PWM波來(lái)控制模擬小車轉(zhuǎn)向，查閱資料可得以上輔助圓應(yīng)當(dāng)采用PWM波比值約為900/200，而關(guān)鍵圓應(yīng)當(dāng)采用PWM波值為：1100/200，再使用單片機(jī)控制PWM波的輸出進(jìn)行實(shí)驗(yàn)。最終，順利驗(yàn)證了最佳泊車路徑的可行性和實(shí)用性。

參考文獻(xiàn)

[1]王芳成.自動(dòng)平行泊車系統(tǒng)的研究[J].中國(guó)科技大學(xué)，2010.

[2]周健.嵌入式模糊自動(dòng)泊車系統(tǒng)的研究[J].廣東工業(yè)大學(xué)，2011.

第2篇

關(guān)鍵詞：分層路網(wǎng)；拓?fù)浣Y(jié)構(gòu)提?。宦窂揭?guī)劃；A算法；二叉堆

0引言

路徑規(guī)劃是車載導(dǎo)航系統(tǒng)最重要的功能之一[1]。根據(jù)圖論中最短路徑理論，不管是最短路徑規(guī)劃、最短時(shí)間規(guī)劃還是最低消費(fèi)規(guī)劃，都可以通過(guò)賦予圖中的邊以相應(yīng)的權(quán)值來(lái)滿足用戶的不同需求。

通常情況下，路徑搜索可以分為平面搜索和分層搜索兩大類。平面搜索算法中最經(jīng)典的是20世紀(jì)60年代初期由Dijkstra提出的Dijkstra算法，非常適合在帶權(quán)有向圖中解決最短路徑問(wèn)題。但是該算法的時(shí)間復(fù)雜度為O（n2），效率比較低，因此在實(shí)際應(yīng)用時(shí)受到了很大的限制。后來(lái)許多學(xué)者在存儲(chǔ)結(jié)構(gòu)和排序算法上對(duì)Dijkstra算法進(jìn)行了改進(jìn)[2-3]，通常改進(jìn)算法的時(shí)間復(fù)雜度與節(jié)點(diǎn)數(shù)成正比，如O（mlbn）或O（m+nlbn）[4]。也有學(xué)者通過(guò)引入啟發(fā)函數(shù)的方式進(jìn)行改進(jìn)，啟發(fā)式搜索以1968年Hart等提出的A*算法為代表，現(xiàn)在仍被廣泛應(yīng)用，但這些改進(jìn)算法的效率會(huì)隨節(jié)點(diǎn)數(shù)的增加而急劇下降。此外，平面搜索算法計(jì)算出的“最短”路徑并不一定是“最優(yōu)”路徑，最短路徑中可能存在大量的窄小擁擠的小巷，而最優(yōu)路徑要盡可能多地包括主干道等快速路段[5]，這就有了分層思想。文獻(xiàn)[6]首先提出了層次空間的推理過(guò)程，文獻(xiàn)[7]又將層次空間推理法則引入到行車最優(yōu)路徑搜索中，但這兩篇文獻(xiàn)均沒(méi)有給出具體的路網(wǎng)層次拓?fù)浣Y(jié)構(gòu)的表達(dá)方法[8]。有代表性的分層算法有最近E節(jié)點(diǎn)法[9]和最佳E節(jié)點(diǎn)法[10]，其中最近E節(jié)點(diǎn)法簡(jiǎn)單但準(zhǔn)確率不高，最佳E節(jié)點(diǎn)法能夠得到最優(yōu)解，但效率低[11]。

本文試圖設(shè)計(jì)一種實(shí)用的分層路徑規(guī)劃算法。首先建立分層路網(wǎng)的拓?fù)浣Y(jié)構(gòu)，然后從搜索空間、搜索策略和數(shù)據(jù)結(jié)構(gòu)三個(gè)方面進(jìn)行研究，采用啟發(fā)式的A*算法作為主搜索方式，引入優(yōu)先隊(duì)列二叉堆作為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，最后通過(guò)實(shí)驗(yàn)驗(yàn)證每項(xiàng)措施的改善效果。

1分層路網(wǎng)拓?fù)浣Y(jié)構(gòu)提取

第3篇

關(guān)鍵詞：移動(dòng)機(jī)器人；路徑規(guī)劃技術(shù)；綜述

DOI：10.16640/ki.37-1222/t.2016.21.135

0 前言

移動(dòng)機(jī)器人的實(shí)現(xiàn)涉及自動(dòng)控制、智能、機(jī)械等多種學(xué)科。它通常被應(yīng)用在醫(yī)療領(lǐng)域、工業(yè)領(lǐng)域等方面。從整體角度來(lái)講，移動(dòng)機(jī)器人的應(yīng)用促進(jìn)了生產(chǎn)效率的顯著提升。路徑規(guī)劃技術(shù)是移動(dòng)機(jī)器人的關(guān)鍵技術(shù)之一，研究該技術(shù)具有一定的現(xiàn)實(shí)意義。

1 路徑規(guī)劃技術(shù)的作用

將路徑規(guī)劃技術(shù)應(yīng)用在移動(dòng)機(jī)器人中，能夠產(chǎn)生的作用主要包含以下幾種：

（1）運(yùn)動(dòng)方面。路徑規(guī)劃技術(shù)的主要作用是其能夠保證移動(dòng)機(jī)器人完成從起點(diǎn)到終點(diǎn)的運(yùn)動(dòng)。（2）障礙物方面。設(shè)計(jì)移動(dòng)機(jī)器人的最終目的是將其應(yīng)用在實(shí)際環(huán)境中，在實(shí)際環(huán)境下，移動(dòng)機(jī)器人的運(yùn)行路線中可能存在一定數(shù)量的障礙物，為了保證最終目的地的順利達(dá)到，需要利用路徑規(guī)劃技術(shù)實(shí)現(xiàn)對(duì)障礙物的有效避開(kāi)[1]。（3）運(yùn)行軌跡方面。對(duì)于移動(dòng)機(jī)器人而言，除了實(shí)現(xiàn)障礙物躲避、達(dá)到最終目的地這兩種作用之外，應(yīng)用路徑規(guī)劃技術(shù)還可以產(chǎn)生一定的優(yōu)化運(yùn)行軌跡作用。在移動(dòng)機(jī)器人的使用過(guò)程中，在路徑規(guī)劃技術(shù)的作用下，機(jī)器人可以完成對(duì)最佳運(yùn)行路線的判斷，進(jìn)而更好地完成相應(yīng)任務(wù)。

2 移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述

移動(dòng)機(jī)器人的路徑規(guī)劃技術(shù)主要包含以下幾種：

2.1 局部路徑規(guī)劃方面

在局部路徑規(guī)劃方面，能夠被應(yīng)用在移動(dòng)機(jī)器人中的技術(shù)主要包含以下幾種：

（1）神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃技術(shù)。從本質(zhì)上講，可以將移動(dòng)機(jī)器人的路徑規(guī)劃看成是空間到行為空間感知過(guò)程的一種映射，因此，可以利用神經(jīng)網(wǎng)絡(luò)的方式將其表現(xiàn)出來(lái)。就神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃技術(shù)而言，首先需要將相關(guān)傳感器數(shù)據(jù)當(dāng)成網(wǎng)絡(luò)輸入，并將網(wǎng)絡(luò)輸出看成是某固定場(chǎng)合中期望運(yùn)動(dòng)方向角增量。在這種情況下，原始樣本集則可以用不同選定位置對(duì)應(yīng)的數(shù)據(jù)代替。為了保證樣本集數(shù)據(jù)的有效性，需要將原始樣本集中的沖突樣本數(shù)據(jù)以及重復(fù)樣本數(shù)據(jù)剔除掉。對(duì)最終樣本集應(yīng)用模糊規(guī)則，實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)的有效訓(xùn)練。當(dāng)?shù)湫蜆颖緦W(xué)習(xí)完成之后，移動(dòng)機(jī)器人對(duì)規(guī)則的掌握水平發(fā)生了顯著提升，進(jìn)而使得移動(dòng)機(jī)器人在產(chǎn)生智能性能的基礎(chǔ)上，順利完成相應(yīng)運(yùn)動(dòng)[2]。

（2）人工勢(shì)場(chǎng)路徑規(guī)劃技術(shù)。這種規(guī)劃技術(shù)是指，將移動(dòng)機(jī)器人在實(shí)際環(huán)境中的運(yùn)動(dòng)過(guò)程當(dāng)成其在虛擬人工受力場(chǎng)中的一種運(yùn)動(dòng)。在虛擬人工受力場(chǎng)中，目標(biāo)終點(diǎn)會(huì)對(duì)移動(dòng)機(jī)器人產(chǎn)生一定的引力，而該受力場(chǎng)中的障礙物則會(huì)對(duì)其產(chǎn)生一定的斥力。在某固定算法的作用下，這兩種不同的作用力會(huì)產(chǎn)生相應(yīng)的勢(shì)，進(jìn)而形成勢(shì)場(chǎng)。當(dāng)移動(dòng)機(jī)器人在該場(chǎng)中運(yùn)動(dòng)時(shí)，勢(shì)場(chǎng)中的抽象力會(huì)作用在移動(dòng)機(jī)器人上，使得其完成對(duì)障礙物的有效避開(kāi)。在人工勢(shì)場(chǎng)路徑規(guī)劃技術(shù)的實(shí)際應(yīng)用過(guò)程中，由于結(jié)構(gòu)簡(jiǎn)單等因素的影響，移動(dòng)機(jī)器人在到達(dá)終點(diǎn)之前可能會(huì)停留在局部最優(yōu)點(diǎn)位置上。對(duì)此，需要從數(shù)學(xué)的角度出發(fā)，對(duì)勢(shì)場(chǎng)方程進(jìn)行重新定義，通過(guò)這種方式排除勢(shì)場(chǎng)中的局部極值，繼而保證移動(dòng)機(jī)器人運(yùn)動(dòng)的順利進(jìn)行[3]。

（3）遺傳路徑規(guī)劃技術(shù)。這種路徑規(guī)劃技術(shù)建立在自然遺傳機(jī)制等理論的基礎(chǔ)上。這種技術(shù)通過(guò)變異、選擇以及交叉對(duì)控制機(jī)構(gòu)的正確計(jì)算程序進(jìn)行合理編制，進(jìn)而實(shí)現(xiàn)數(shù)學(xué)方式基礎(chǔ)上生物進(jìn)化過(guò)程的合理模擬。當(dāng)移動(dòng)機(jī)器人的適應(yīng)度函數(shù)為正數(shù)時(shí)，允許適應(yīng)度函數(shù)具有不連續(xù)或不可導(dǎo)特點(diǎn)。由于這種路徑規(guī)劃技術(shù)不涉及梯度信息，因此其能夠更好地解決移動(dòng)機(jī)器人在實(shí)際運(yùn)動(dòng)過(guò)程中遇到的問(wèn)題。遺傳路徑規(guī)劃技術(shù)的應(yīng)用優(yōu)勢(shì)在于，它能夠?qū)崿F(xiàn)跟蹤與規(guī)劃的同時(shí)進(jìn)行，因此，遺傳路徑規(guī)劃技術(shù)通常被應(yīng)用在具有時(shí)變特點(diǎn)的未知環(huán)境中。

2.2 全局路徑規(guī)劃方面

在該方面，可以被應(yīng)用在移動(dòng)機(jī)器人中的技術(shù)主要包含以下幾種：

（1）柵格路徑規(guī)劃技術(shù)。這種技術(shù)是指，在將實(shí)際工作環(huán)境分成許多包含二值信息的網(wǎng)格單元的基礎(chǔ)上，應(yīng)用優(yōu)化算法完成最佳路徑的規(guī)劃搜索。在這種規(guī)劃技術(shù)中，其網(wǎng)格單元通常是由八叉樹(shù)或者四叉樹(shù)的方式表示出來(lái)。在該技術(shù)的應(yīng)用中，柵格的作用是完成相關(guān)環(huán)境信息的記錄。如果柵格中某位置的累計(jì)值相對(duì)較低，代表移動(dòng)機(jī)器人可以從該位置通過(guò)；如果柵格中某個(gè)位置的累計(jì)值相對(duì)較高，則表示該位置存在障礙物，此時(shí)，移動(dòng)機(jī)器人需要利用優(yōu)化算法將該障礙物避開(kāi)[4]。

（2）可視圖路徑規(guī)劃技術(shù)。這種路徑規(guī)劃技術(shù)是指，將整個(gè)移動(dòng)機(jī)器人看成一個(gè)點(diǎn)，然后分別將其與障礙物以及目標(biāo)終點(diǎn)連接起來(lái)，上述連線要求為保證所連直線不會(huì)碰觸障礙物。當(dāng)所有連線都連完之后，即完成了一整張可視圖。在該可視圖中，由于起點(diǎn)到目標(biāo)終點(diǎn)之間的連線都不涉及障礙物，因此上述所有連線都屬于有效直線。在這種情況下，需要解決的問(wèn)題主要是從這些連線中找出一條距離最短的連線。對(duì)此，需要應(yīng)用優(yōu)化算法將可視圖中距離較長(zhǎng)的連線刪除，這種處理方式能夠有效提升移動(dòng)機(jī)器人的搜索時(shí)間。

（3）拓?fù)渎窂揭?guī)劃技術(shù)。這種規(guī)劃技術(shù)是指，將移動(dòng)機(jī)器人的移動(dòng)范圍，即規(guī)劃區(qū)域分成多個(gè)具有拓?fù)涮卣鞯淖涌臻g，然后利用不同子空間之間的連通性完成拓?fù)渚W(wǎng)絡(luò)的構(gòu)建。當(dāng)該網(wǎng)絡(luò)構(gòu)建完成后，直接從網(wǎng)絡(luò)中找出能夠使得機(jī)器人順利從起點(diǎn)移動(dòng)到終點(diǎn)的拓?fù)渎窂?，將所得的拓?fù)渎窂阶鳛閰⒖家罁?jù)完成幾何路徑的計(jì)算。這種規(guī)劃技術(shù)的劣勢(shì)主要表現(xiàn)為其拓?fù)渚W(wǎng)絡(luò)的構(gòu)建過(guò)程較為復(fù)雜。但這種規(guī)劃技術(shù)可以實(shí)現(xiàn)移動(dòng)機(jī)器人搜索空間的有效縮小[5]。

3 結(jié)論

路徑規(guī)劃技術(shù)主要分為局部規(guī)劃和全局規(guī)劃兩方面。這兩方面分別包含人工勢(shì)場(chǎng)路徑規(guī)劃技術(shù)以及神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃技術(shù)等。應(yīng)用這些規(guī)劃技術(shù)之后，移動(dòng)機(jī)器人可以在避開(kāi)障礙物的基礎(chǔ)上，順利完成起點(diǎn)到終點(diǎn)最優(yōu)運(yùn)行軌跡的運(yùn)動(dòng)。

參考文獻(xiàn)：

[1]朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010（07）：961-967.

[2]張捍東，鄭睿，岑豫皖.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望[J].系統(tǒng)仿真學(xué)報(bào)，2005（02）：439-443.

[3]鮑慶勇，李舜酩，沈`，門秀花.自主移動(dòng)機(jī)器人局部路徑規(guī)劃綜述[J].傳感器與微系統(tǒng)，2009（09）：1-4+11.

[4]孔峰，陶金，謝超平.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)研究[J].廣西工學(xué)院學(xué)報(bào)，2009（04）：70-74.

第4篇

摘 要：在查閱大量文獻(xiàn)的基礎(chǔ)上對(duì)多機(jī)器人路徑規(guī)劃的主要研究?jī)?nèi)容和研究現(xiàn)狀進(jìn)行了分析和總結(jié)，討論了多機(jī)器人路徑規(guī)劃方法的評(píng)判標(biāo)準(zhǔn)，并闡述了研究遇到的瓶頸問(wèn)題，展望了多機(jī)器人路徑規(guī)劃方法的發(fā)展趨勢(shì)。

關(guān)鍵詞：多機(jī)器人；路徑規(guī)劃；強(qiáng)化學(xué)習(xí)；評(píng)判準(zhǔn)則

Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multirobot.Then discussed the criterion of path planning research for multirobot based large of literature.Meanwhile，it expounded the bottleneck of the path planning research for multirobot，forecasted the future development of multirobot path planning.

Key words:multirobot；path planning;reinforcement learning;evaluating criteria 

近年來(lái)，分布式人工智能(DAI)成為人工智能研究的一個(gè)重要分支。DAI研究大致可以分為DPS（distributed problem solving）和MAS（multiagent system）兩個(gè)方面。一些從事機(jī)器人學(xué)的研究人員受多智能體系統(tǒng)研究的啟發(fā)，將智能體概念應(yīng)用于多機(jī)器人系統(tǒng)的研究中，將單個(gè)機(jī)器人視做一個(gè)能獨(dú)立執(zhí)行特定任務(wù)的智能體，并把這種多機(jī)器人系統(tǒng)稱為多智能體機(jī)器人系統(tǒng)（MARS）。因此，本文中多機(jī)器人系統(tǒng)等同于多智能體機(jī)器人系統(tǒng)。目前，多機(jī)器人系統(tǒng)已經(jīng)成為學(xué)術(shù)界研究的熱點(diǎn)，而路徑規(guī)劃研究又是其核心部分。

機(jī)器人路徑規(guī)劃問(wèn)題可以建模為一個(gè)帶約束的優(yōu)化問(wèn)題，其包括地理環(huán)境信息建模、路徑規(guī)劃、定位和避障等任務(wù)，它是移動(dòng)機(jī)器人導(dǎo)航與控制的基礎(chǔ)。單個(gè)移動(dòng)機(jī)器人路徑規(guī)劃研究一直是機(jī)器人研究的重點(diǎn)，且已經(jīng)有許多成果[1~3]，例如在靜態(tài)環(huán)境中常見(jiàn)的有連接圖法、可視圖法、切線圖法、Voronoi圖法、自由空間法、柵格法、拓?fù)浞?、鏈接圖法、DempsterShafer證據(jù)理論建圖等；動(dòng)態(tài)環(huán)境中常見(jiàn)的有粒子群算法、免疫算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)、蟻群算法、模擬退火算法、人工勢(shì)場(chǎng)法等。然而，多機(jī)器人路徑規(guī)劃研究比單個(gè)機(jī)器人路徑規(guī)劃要復(fù)雜得多，必須考慮多機(jī)器人系統(tǒng)中機(jī)器人之間的避碰機(jī)制、機(jī)器人之間的相互協(xié)作機(jī)制、通信機(jī)制等問(wèn)題。

1 多機(jī)器人路徑規(guī)劃方法

單個(gè)機(jī)器人的路徑規(guī)劃是找出從起始點(diǎn)至終點(diǎn)的一條最短無(wú)碰路徑。多個(gè)機(jī)器人的路徑規(guī)劃側(cè)重考慮整個(gè)系統(tǒng)的最優(yōu)路徑，如系統(tǒng)的總耗時(shí)間最少路徑或是系統(tǒng)總路徑最短等。從目前國(guó)內(nèi)外的研究來(lái)看，在規(guī)劃多機(jī)器人路徑時(shí)，更多考慮的是多機(jī)器人之間的協(xié)調(diào)和合作式的路徑規(guī)劃。

目前國(guó)內(nèi)外多機(jī)器人路徑規(guī)劃研究方法分為傳統(tǒng)方法、智能優(yōu)化方法和其他方法三大類。其中傳統(tǒng)方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢(shì)場(chǎng)方法等）；智能優(yōu)化方法主要有遺傳算法、蟻群算法、免疫算法、神經(jīng)網(wǎng)絡(luò)、強(qiáng)化學(xué)習(xí)等；其他方法主要有動(dòng)態(tài)規(guī)劃、最優(yōu)控制算法、模糊控制等。它們中的大部分都是從單個(gè)機(jī)器人路徑規(guī)劃方法擴(kuò)展而來(lái)的。

1）傳統(tǒng)方法 多機(jī)器人路徑規(guī)劃傳統(tǒng)方法的特點(diǎn)主要體現(xiàn)在基于圖論的基礎(chǔ)上。方法一般都是先將環(huán)境構(gòu)建成一個(gè)圖，然后再?gòu)膱D中尋找最優(yōu)的路徑。其優(yōu)點(diǎn)是比較簡(jiǎn)單，比較容易實(shí)現(xiàn)；缺點(diǎn)是得到的路徑有可能不是最優(yōu)路徑，而是次優(yōu)路徑。薄喜柱等人[4]提出的一種新路徑規(guī)劃方法的基本思想就是基于柵格類的環(huán)境表示和障礙地圖的。而人工勢(shì)場(chǎng)方法的基本思想是將移動(dòng)機(jī)器人在環(huán)境中的運(yùn)動(dòng)視為一種虛擬人工受力場(chǎng)中的運(yùn)動(dòng)。障礙物對(duì)移動(dòng)機(jī)器人產(chǎn)生斥力，目標(biāo)點(diǎn)產(chǎn)生引力，引力和斥力周圍由一定的算法產(chǎn)生相應(yīng)的勢(shì)，機(jī)器人在勢(shì)場(chǎng)中受到抽象力作用，抽象力使得機(jī)器人繞過(guò)障礙物。其優(yōu)點(diǎn)是適合未知環(huán)境下的規(guī)劃，不會(huì)出現(xiàn)維數(shù)爆炸問(wèn)題；但是人工勢(shì)場(chǎng)法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國(guó)昌等人[5]提出了引用總體勢(shì)減小的動(dòng)態(tài)調(diào)度技術(shù)的多機(jī)器人路徑規(guī)劃，較好地解決了這個(gè)問(wèn)題。

2）智能優(yōu)化方法 多機(jī)器人路徑規(guī)劃的智能優(yōu)化方（算）法是隨著近年來(lái)智能計(jì)算發(fā)展而產(chǎn)生的一些新方法。其相對(duì)于傳統(tǒng)方法更加智能化，且日益成為國(guó)內(nèi)外研究的重點(diǎn)。

遺傳算法是近年來(lái)計(jì)算智能研究的熱點(diǎn)，作為一種基于群體進(jìn)化的概率優(yōu)化方法，適用于處理傳統(tǒng)搜索算法難以解決的復(fù)雜和非線性問(wèn)題，如多機(jī)器的路徑規(guī)劃問(wèn)題。在路徑規(guī)劃中，其基本思想是先用鏈接圖法把環(huán)境地圖構(gòu)建成一個(gè)路徑節(jié)點(diǎn)鏈接網(wǎng)，將路徑個(gè)體表達(dá)為路徑中一系列中途節(jié)點(diǎn)，并轉(zhuǎn)換為二進(jìn)制串；然后進(jìn)行遺傳操作（如選擇、交叉、復(fù)制、變異），經(jīng)過(guò)N次進(jìn)化，輸出當(dāng)前的最優(yōu)個(gè)體即機(jī)器人的最優(yōu)路徑。遺傳算法的缺點(diǎn)是運(yùn)算速度不快，進(jìn)化眾多的規(guī)劃要占據(jù)很大的存儲(chǔ)空間和運(yùn)算時(shí)間；優(yōu)點(diǎn)是有效避免了局部極小值問(wèn)題，且計(jì)算量較小。 

孫樹(shù)棟等人[6，7]在這方面較早地展開(kāi)了研究，提出的基于集中協(xié)調(diào)思想的一種混合遺傳算法來(lái)規(guī)劃多機(jī)器人路徑方法較好地解決了避障問(wèn)題。但不足的是該方法必須建立環(huán)境地圖，在環(huán)境未知情況下的規(guī)劃沒(méi)有得到很好的解決；且規(guī)劃只能保證找到一個(gè)比較滿意的解，在求解全局最優(yōu)解時(shí)仍有局限。

文獻(xiàn)[8]中提出的一種基于定長(zhǎng)十進(jìn)編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長(zhǎng)編碼機(jī)制及定長(zhǎng)二進(jìn)制編碼機(jī)制需特殊遺傳操作算子和特殊解碼的缺陷， 使得算法更加簡(jiǎn)單有效。

智能計(jì)算的另一種常見(jiàn)的方法——蟻群算法屬于隨機(jī)搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運(yùn)動(dòng)過(guò)程來(lái)實(shí)現(xiàn)尋優(yōu)，通過(guò)螞蟻群體中各個(gè)體之間的相互作用，分布、并行地解決組合優(yōu)化問(wèn)題。該算法同樣比較適合解決多機(jī)器人的路徑規(guī)劃問(wèn)題。

朱慶保[9]提出了在全局未知環(huán)境下多機(jī)器人運(yùn)動(dòng)螞蟻導(dǎo)航算法。該方法將全局目標(biāo)點(diǎn)映射到機(jī)器人視野域邊界附近作為局部導(dǎo)航子目標(biāo)，再由兩組螞蟻相互協(xié)作完成機(jī)器人視野域內(nèi)局部最優(yōu)路徑的搜索，然后在此基礎(chǔ)上進(jìn)行與其他機(jī)器人的碰撞預(yù)測(cè)與避碰規(guī)劃。因此，機(jī)器人的前進(jìn)路徑不斷被動(dòng)態(tài)修改，從而在每條局部?jī)?yōu)化路徑引導(dǎo)下，使機(jī)器人沿一條全局優(yōu)化的路徑到達(dá)目標(biāo)點(diǎn)。但其不足是在動(dòng)態(tài)不確定的環(huán)境中路徑規(guī)劃時(shí)間開(kāi)銷劇增，而且機(jī)器人缺乏必要的學(xué)習(xí)，以至于整個(gè)機(jī)器人系統(tǒng)路徑難以是最優(yōu)路徑。

強(qiáng)化學(xué)習(xí)[10，11] (又稱再激勵(lì)學(xué)習(xí))是一種重要的機(jī)器學(xué)習(xí)方法。它是一種智能體從環(huán)境狀態(tài)到行為映射的學(xué)習(xí)，使得行為從環(huán)境中獲得積累獎(jiǎng)賞值最大。其原理如圖1所示。

強(qiáng)化學(xué)習(xí)算法一般包含了兩個(gè)步驟：a）從當(dāng)前學(xué)習(xí)循環(huán)的值函數(shù)確定新的行為策略；b）在新的行為策略指導(dǎo)下，通過(guò)所獲得的瞬時(shí)獎(jiǎng)懲值對(duì)該策略進(jìn)行評(píng)估。學(xué)習(xí)循環(huán)過(guò)程如下所示，直到值函數(shù)和策略收斂:

v0π1v1π2…v*π*v*

目前比較常見(jiàn)的強(qiáng)化學(xué)習(xí)方法有：Monte Carlo方法、動(dòng)態(tài)規(guī)劃方法、TD（時(shí)間差分）方法。其中TD算法包含Sarsa算法、Q學(xué)習(xí)算法以及Dyna-Q算法等。其Q值函數(shù)迭代公式分別為

TD（0）策略： V(si)V(si)+α[γi+1+γV(si+1)-V(si)]

Sarsa算法： Q(st，at)Q(st，at)+α[γt+1+γQ(st+1，at.+1)-Q(st，at)]Qs′學(xué)習(xí)算法： Qπ(s，a)=∑Pαss′[Rass′+γVπ(s′)]

近年來(lái)，基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃日益成為國(guó)內(nèi)外學(xué)者研究的熱點(diǎn)。M. J. Mataric[12]首次把強(qiáng)化學(xué)習(xí)引入到多機(jī)器人環(huán)境中。而基于強(qiáng)化學(xué)習(xí)的多機(jī)器人路徑規(guī)劃的優(yōu)點(diǎn)主要體現(xiàn)在：無(wú)須建立精確的環(huán)境模型，簡(jiǎn)化了智能體的編程；無(wú)須構(gòu)建環(huán)境地圖；強(qiáng)化學(xué)習(xí)可以把路徑規(guī)劃、避碰、避障、協(xié)作等問(wèn)題統(tǒng)一解決。

張芳等人[13]提出了基于再激勵(lì)協(xié)調(diào)避障路徑規(guī)劃方法，把再勵(lì)函數(shù)設(shè)計(jì)為基于行為分解的無(wú)模型非均勻結(jié)構(gòu)，新的再勵(lì)函數(shù)結(jié)構(gòu)使得學(xué)習(xí)速度得以提高且有較好的魯棒性。同時(shí)，證明了在路徑規(guī)劃中，機(jī)器人的趨向目標(biāo)和避障行為密切相關(guān)，對(duì)反映各基本行為的再勵(lì)函數(shù)取加權(quán)和來(lái)表示總的再勵(lì)函數(shù)要優(yōu)于取直接和的表示方式，也反映了再勵(lì)函數(shù)設(shè)計(jì)得合理與否及其確切程度將影響再勵(lì)學(xué)習(xí)的收斂速度。王醒策等人[14]在動(dòng)態(tài)編隊(duì)的強(qiáng)化學(xué)習(xí)算法方面展開(kāi)了研究。宋一然[15]則提出了分段再勵(lì)函數(shù)的強(qiáng)化學(xué)習(xí)方法進(jìn)行路徑規(guī)劃。其缺點(diǎn)是學(xué)習(xí)次數(shù)較多、效率不高，當(dāng)機(jī)器人數(shù)目增加時(shí)，它有可能面臨維數(shù)災(zāi)難的困難。所以，基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃在多機(jī)器人環(huán)境下的學(xué)習(xí)將變得比較困難，需要對(duì)傳統(tǒng)的強(qiáng)化學(xué)習(xí)加以優(yōu)化，如基于人工神經(jīng)網(wǎng)絡(luò)的強(qiáng)化學(xué)習(xí)[16]等。

3)其他方法 除了以上國(guó)內(nèi)外幾種比較常見(jiàn)且研究較多的方法外，還有唐振民等人[17]提出的基于動(dòng)態(tài)規(guī)劃思想的多機(jī)器人路徑規(guī)劃，把運(yùn)籌學(xué)中的動(dòng)態(tài)規(guī)劃思想與Dijkstra算法引入到多機(jī)器人的路徑規(guī)劃中，用動(dòng)態(tài)規(guī)劃的基本思想來(lái)解決圖論中的費(fèi)用流問(wèn)題和路徑規(guī)劃中的層級(jí)動(dòng)態(tài)聯(lián)盟問(wèn)題。其選擇距離鄰近法作為聯(lián)盟參考依據(jù)。一個(gè)機(jī)器人的鄰居是指在地理位置上分布在這個(gè)機(jī)器人周圍的其他機(jī)器人；與該機(jī)器人最近鄰的機(jī)器人為第一層鄰居，第一層鄰居的鄰居為該機(jī)器人的第二層鄰居， 依此類推。那么層級(jí)越高（即越近)的鄰居，它滿足協(xié)作要求的可能性越大。動(dòng)態(tài)規(guī)劃算法實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過(guò)程中，必須存儲(chǔ)產(chǎn)生過(guò)程中的各種狀態(tài)，其空間復(fù)雜度要大于其他算法，故動(dòng)態(tài)規(guī)劃方法比較適合多機(jī)器人的全局路徑規(guī)劃。

孫茂相等人[18]提出了最優(yōu)控制與智能決策相結(jié)合的多移動(dòng)機(jī)器人路徑規(guī)劃方法。其首先構(gòu)造一個(gè)以各機(jī)器人最優(yōu)運(yùn)動(dòng)狀態(tài)數(shù)據(jù)庫(kù)為核心的實(shí)時(shí)專家系統(tǒng)， 在離線狀態(tài)下完成; 然后各機(jī)器人在此專家系統(tǒng)的支持下， 以最優(yōu)規(guī)劃策略為基礎(chǔ)， 采用速度遷移算法， 自主決定其控制。該方法擁有較好的穩(wěn)定性與復(fù)雜度。焦立男等人[19]提出的基于局部傳感和通信的多機(jī)器人運(yùn)動(dòng)規(guī)劃框架較好地解決了多機(jī)器人路徑規(guī)劃在局部在線規(guī)劃的系統(tǒng)框架問(wèn)題。沈捷等人[20]提出了保持隊(duì)形的多移動(dòng)機(jī)器人路徑規(guī)劃。以基于行為的導(dǎo)航算法為基礎(chǔ)，把機(jī)器人隊(duì)列的運(yùn)動(dòng)過(guò)程劃分為正常運(yùn)動(dòng)、避障和恢復(fù)隊(duì)形三個(gè)階段。在避障階段，引入虛擬機(jī)器人使隊(duì)形保持部分完整;當(dāng)隊(duì)形被嚴(yán)重打亂時(shí)，規(guī)劃?rùn)C(jī)器人的局部目標(biāo)位姿使隊(duì)列快速恢復(fù)隊(duì)形。其算法重點(diǎn)為避障機(jī)器人進(jìn)入避障狀態(tài)，暫時(shí)脫離隊(duì)列，并以虛擬機(jī)器人代替避障機(jī)器人。

2 多機(jī)器人避碰和避障

避障和避碰是多機(jī)器人路徑規(guī)劃研究中需要考慮的重點(diǎn)問(wèn)題之一。避障和避碰主要討論的內(nèi)容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規(guī)劃中常見(jiàn)的多機(jī)器人避障方法[21]有主從控制法、動(dòng)態(tài)優(yōu)先法（建立在機(jī)器人之間的通信協(xié)商上）、交通規(guī)則法、速率調(diào)整法，以及障礙物膨脹法、基于人工勢(shì)場(chǎng)的方法等。

目前國(guó)內(nèi)外對(duì)于多機(jī)器人避障展開(kāi)的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎(chǔ)，擴(kuò)充并完善了路徑/速度分解方案來(lái)協(xié)調(diào)多機(jī)器人，設(shè)立集中管理agent進(jìn)行整體規(guī)劃，為每個(gè)機(jī)器人規(guī)劃路徑；并根據(jù)優(yōu)先級(jí)規(guī)則對(duì)運(yùn)動(dòng)特征進(jìn)行分布式規(guī)劃以避免機(jī)器人間的沖突。周明等人[23]提出分布式智能避撞規(guī)劃系統(tǒng)，將原來(lái)比較復(fù)雜的大系統(tǒng)轉(zhuǎn)換為相對(duì)簡(jiǎn)單的子系統(tǒng)問(wèn)題，由各智能機(jī)器人依據(jù)任務(wù)要求和環(huán)境變化， 獨(dú)立調(diào)整自身運(yùn)動(dòng)狀態(tài)，完成任務(wù)的分布式智能決策體系結(jié)構(gòu)。任炏等人[24]提出了基于過(guò)程獎(jiǎng)賞和優(yōu)先掃除的強(qiáng)化學(xué)習(xí)多機(jī)器人系統(tǒng)的沖突消解方法。該算法能夠顯著減少?zèng)_突，避免死鎖，提高了系統(tǒng)整體性能。歐錦軍等人[25]提出了通過(guò)調(diào)整機(jī)器人的運(yùn)動(dòng)速度實(shí)現(xiàn)多機(jī)器人避碰，將避碰問(wèn)題轉(zhuǎn)換為高維線性空間的優(yōu)化問(wèn)題， 并進(jìn)一步將其轉(zhuǎn)換為線性方程的求解。該方法的缺點(diǎn)是系統(tǒng)的復(fù)雜度較高、計(jì)算量太大。

人工勢(shì)場(chǎng)方法的特點(diǎn)是計(jì)算簡(jiǎn)潔、實(shí)時(shí)性強(qiáng)、便于數(shù)學(xué)描述，且適合于多自由度機(jī)器人環(huán)境，但容易產(chǎn)生抖動(dòng)和陷入局部極小。為了克服其缺點(diǎn)，景興建等人[26]提出了人工協(xié)調(diào)場(chǎng)的方法，在傳統(tǒng)排斥力場(chǎng)中增加一個(gè)協(xié)調(diào)力，并將吸引力、排斥力和協(xié)調(diào)力與局部環(huán)境下機(jī)器人的運(yùn)動(dòng)狀態(tài)和運(yùn)動(dòng)要求結(jié)合起來(lái)，有效地保證機(jī)器人的安全性，提高機(jī)器人在復(fù)雜動(dòng)態(tài)環(huán)境下行為決策的準(zhǔn)確性和魯棒性。

3 多機(jī)器人協(xié)作和協(xié)調(diào)機(jī)制

多機(jī)器人間的運(yùn)動(dòng)協(xié)調(diào)[27~31]是多機(jī)器人路徑規(guī)劃的關(guān)鍵，也是多機(jī)器人與單機(jī)器人路徑規(guī)劃相區(qū)別的根本所在。多機(jī)器人系統(tǒng)在復(fù)雜動(dòng)態(tài)實(shí)時(shí)環(huán)境下，由于受到時(shí)間、資源及任務(wù)要求的約束，需要在有限時(shí)間、資源的情況下進(jìn)行資源分配、任務(wù)調(diào)配、沖突解決等協(xié)調(diào)合作問(wèn)題，而機(jī)器人間的協(xié)調(diào)與協(xié)作，能夠大大地提高整個(gè)系統(tǒng)的效率和魯棒性，成為系統(tǒng)完成控制或解決任務(wù)的關(guān)鍵。

目前已有的協(xié)調(diào)方式分為集中式、分布式和混合式三種。在集中式協(xié)調(diào)中，集中規(guī)劃器詳細(xì)地規(guī)劃出每個(gè)機(jī)器人的動(dòng)作，通常的做法是將多個(gè)機(jī)器人看做一個(gè)多自由度的機(jī)器人進(jìn)行規(guī)劃；而分布式協(xié)調(diào)規(guī)劃中，機(jī)器人之間進(jìn)行合作，將一個(gè)任務(wù)分成多個(gè)子任務(wù)，根據(jù)各自的特點(diǎn)完成不同的子任務(wù)，從而共同完成總?cè)蝿?wù)；混合式協(xié)調(diào)是集中式和分布式混合在一起的形式。

多機(jī)器人間典型的協(xié)調(diào)方法[32]有合同網(wǎng)協(xié)議[33]、黑板模型、結(jié)果共享的協(xié)同方法、市場(chǎng)機(jī)制。近年來(lái)強(qiáng)化學(xué)習(xí)在多機(jī)器人協(xié)作方面也得到很好的應(yīng)用，陳雪江[32]在基于強(qiáng)化學(xué)習(xí)的多機(jī)器人協(xié)作方面展開(kāi)了研究，提出了多智能體協(xié)作的兩層強(qiáng)化學(xué)習(xí)方法來(lái)求解在多智能體完全協(xié)作、有通信情況下的協(xié)作問(wèn)題。其主要通過(guò)在單個(gè)智能體中構(gòu)筑兩層強(qiáng)化學(xué)習(xí)單元來(lái)實(shí)現(xiàn)：第一層強(qiáng)化學(xué)習(xí)單元負(fù)責(zé)學(xué)習(xí)智能體的聯(lián)合任務(wù)協(xié)作策略；第二層強(qiáng)化學(xué)習(xí)單元負(fù)責(zé)學(xué)習(xí)在本智能體看來(lái)是最有效的行動(dòng)策略。陳偉等人[34]提出基于多目標(biāo)決策理論的多機(jī)器人協(xié)調(diào)方法；通過(guò)對(duì)環(huán)境的拓?fù)浣?，從基于行為的機(jī)器人學(xué)角度出發(fā)，對(duì)任務(wù)進(jìn)行分解并設(shè)計(jì)目標(biāo)行為，以多目標(biāo)行為決策理論作為決策支持，從而達(dá)到多機(jī)器人運(yùn)動(dòng)協(xié)調(diào)的目的。

4 多機(jī)器人路徑規(guī)劃方(算)法的判優(yōu)準(zhǔn)則

通常評(píng)價(jià)機(jī)器人路徑規(guī)劃方(算)法的標(biāo)準(zhǔn)文獻(xiàn)[35]有正確性、時(shí)間/空間復(fù)雜度、并行性、可靠性、擴(kuò)展性、魯棒性和學(xué)習(xí)。而多機(jī)器人的路徑規(guī)劃除了以上一些衡量標(biāo)準(zhǔn)之外，還需要考慮整個(gè)系統(tǒng)的最優(yōu)化以及機(jī)器人間的協(xié)調(diào)性。

1)正確性 是分析算法的最基本的原則之一。一般來(lái)說(shuō)算法的正確性是指:在給定有效的輸入數(shù)據(jù)后，算法經(jīng)過(guò)有窮時(shí)間的計(jì)算能給出正確的答案。但在多機(jī)器人路徑規(guī)劃算法中，正確性主要指:路徑規(guī)劃算法要生成多個(gè)機(jī)器人協(xié)調(diào)運(yùn)動(dòng)的無(wú)碰安全路徑;這條路徑是優(yōu)化的。

2)安全性 一般指多機(jī)器人所生成的各路徑中節(jié)點(diǎn)與障礙物有一定的距離。但在實(shí)際的應(yīng)用背景下，有人認(rèn)為安全性可以從兩個(gè)方面來(lái)理解：a）狹義地講，它就是機(jī)器人在行走過(guò)程中所做的功。在一定的條件下，它與路徑長(zhǎng)度準(zhǔn)則是一致的。b）廣義地講，它是各種優(yōu)化條件加權(quán)綜合而得到的結(jié)果。

3)復(fù)雜度 一個(gè)算法的復(fù)雜性高低體現(xiàn)在該算法所需要的計(jì)算機(jī)資源的多少上面。所需要的資源越多，該算法的復(fù)雜性越高；反之，所需要的資源越少，該算法的復(fù)雜性就越低。算法的復(fù)雜性包括時(shí)間復(fù)雜度和空間復(fù)雜度。

在多機(jī)器人的路徑規(guī)劃算法中，算法的復(fù)雜度分析顯得尤為重要。一般地，單機(jī)器人路徑規(guī)劃算法的時(shí)空復(fù)雜度已經(jīng)頗高，它們的數(shù)量級(jí)至少是O(n2)；多機(jī)器人的路徑規(guī)劃算法不僅是m-O(n2)(即m個(gè)機(jī)器人路徑規(guī)劃簡(jiǎn)單地疊加)，它們之間還存在著對(duì)運(yùn)動(dòng)空間競(jìng)爭(zhēng)的沖突，面對(duì)不斷變化的沖突的協(xié)調(diào)需要花費(fèi)大量的時(shí)間和空間。通常多機(jī)器人的路徑規(guī)劃算法與機(jī)器人的個(gè)數(shù)呈指數(shù)關(guān)系O(km×n2)（k為常數(shù)）。這對(duì)多機(jī)器人路徑規(guī)劃算法的時(shí)間/空間復(fù)雜度控制是一個(gè)很嚴(yán)峻的考驗(yàn)。

4)并行性 算法的并行性從算法設(shè)計(jì)、編寫(xiě)程序、編譯和運(yùn)行等多個(gè)不同的層次來(lái)體現(xiàn)。路徑規(guī)劃過(guò)程需要大量的計(jì)算，當(dāng)處理的環(huán)境比較復(fù)雜，機(jī)器人工作的環(huán)境過(guò)于緊湊，尤其是機(jī)器人數(shù)量很多時(shí)，算法的時(shí)間/空間復(fù)雜度勢(shì)必會(huì)成為算法效率的關(guān)鍵。因此，在算法設(shè)計(jì)和運(yùn)行上的并行性是通常考慮的方法。對(duì)多個(gè)機(jī)器人的路徑規(guī)劃盡量采用分布式多進(jìn)程的規(guī)劃?rùn)C(jī)制，以實(shí)現(xiàn)每個(gè)機(jī)器人路徑規(guī)劃的并行性。

5)可靠性 把多個(gè)機(jī)器人及其工作環(huán)境看成是一個(gè)系統(tǒng)，多機(jī)器人處于它們各自的起始點(diǎn)時(shí)，稱該系統(tǒng)處于初始狀態(tài)；當(dāng)它們處于各自的目標(biāo)點(diǎn)時(shí)，稱該系統(tǒng)處于目標(biāo)狀態(tài)。多機(jī)器人的路徑規(guī)劃就是在該系統(tǒng)的這兩個(gè)狀態(tài)間建立一串合理的狀態(tài)變遷。這一狀態(tài)變遷過(guò)程可能會(huì)歷經(jīng)許多狀態(tài)，如果在狀態(tài)變遷過(guò)程中，路徑規(guī)劃算法控制不好各狀態(tài)間的轉(zhuǎn)移關(guān)系，就會(huì)導(dǎo)致系統(tǒng)紊亂，出現(xiàn)機(jī)器人間的碰撞、找不到路徑等惡性后果，使任務(wù)失敗。所以這就對(duì)算法的可靠性和完備性提出了挑戰(zhàn)。為了很好地克服這一困難，需要對(duì)系統(tǒng)的各種可能狀態(tài)建模，分析它們相互間的關(guān)系，建立有限狀態(tài)自動(dòng)機(jī)模型或Petri網(wǎng)模型，并以此為指導(dǎo)，按照軟件工程的思想，構(gòu)造恰當(dāng)?shù)乃惴ㄝ斎雭?lái)對(duì)算法的可靠性進(jìn)行檢驗(yàn)。

6)可擴(kuò)展性 在多機(jī)器人的路徑規(guī)劃算法中，可擴(kuò)展性主要是指一種路徑規(guī)劃算法在邏輯上，或者說(shuō)在實(shí)現(xiàn)上能否容易地從2D空間擴(kuò)展到3D空間，從低自由度擴(kuò)展到高自由度，從較少的機(jī)器人數(shù)到更多的機(jī)器人數(shù)。可擴(kuò)展性在各種路徑規(guī)劃算法之間沒(méi)有一種量的比較標(biāo)準(zhǔn)，只能從實(shí)際的具體情況出發(fā)、從對(duì)環(huán)境描述的適宜程度出發(fā)、從算法解決這一問(wèn)題的復(fù)雜度出發(fā)、從算法本身的自適應(yīng)出發(fā)等來(lái)考慮。

7)魯棒性和學(xué)習(xí) 魯棒性對(duì)于多機(jī)器人系統(tǒng)非常重要。因?yàn)樵S多應(yīng)用，如路徑規(guī)劃要求連續(xù)的作業(yè)、系統(tǒng)中的單個(gè)機(jī)器人出現(xiàn)故障或被破壞，要求機(jī)器人利用剩余的資源仍然能夠完成任務(wù)。學(xué)習(xí)是在線適應(yīng)特定的任務(wù)。雖然通用的系統(tǒng)非常有用，但將它用于特定應(yīng)用上時(shí)，通常需要調(diào)整一些參數(shù)。具有在線調(diào)整相關(guān)參數(shù)的能力是非常吸引人的，這在將體系結(jié)構(gòu)轉(zhuǎn)移到其他應(yīng)用時(shí)可以節(jié)省許多工作。尤其是多機(jī)器人系統(tǒng)中機(jī)器人的自身學(xué)習(xí)和相互間的學(xué)習(xí)能夠大大提高整個(gè)系統(tǒng)的效率和系統(tǒng)的穩(wěn)定性。

8）最優(yōu)化 對(duì)動(dòng)態(tài)環(huán)境有優(yōu)化反應(yīng)。由于有些應(yīng)用領(lǐng)域涉及的是動(dòng)態(tài)的環(huán)境條件，具有根據(jù)條件優(yōu)化系統(tǒng)的反應(yīng)能力成為能否成功的關(guān)鍵。

5 結(jié)束語(yǔ)

綜上所述，國(guó)內(nèi)外研究者在多機(jī)器人路徑規(guī)劃取得了一些成果，但是在協(xié)作、學(xué)習(xí)、通信機(jī)制等方面仍面臨很大的困難和不足。如何進(jìn)一步提高機(jī)器人間的協(xié)調(diào)性，增強(qiáng)機(jī)器人自身以及相互間的學(xué)習(xí)以提高多機(jī)器人系統(tǒng)的效率和魯棒性都有待深入研究。近年來(lái)無(wú)線通信技術(shù)得到長(zhǎng)足發(fā)展，但在目前的技術(shù)條件下，在多機(jī)器人系統(tǒng)中實(shí)現(xiàn)所有機(jī)器人之間的點(diǎn)對(duì)點(diǎn)實(shí)時(shí)通信還有較大困難，這也是大多數(shù)多機(jī)器人系統(tǒng)仍然采用集中通信方式的主要原因。因此，如何降低多機(jī)器人系統(tǒng)對(duì)通信速度的依賴程度也是一個(gè)非常重要的問(wèn)題。

總之，多機(jī)器人路徑規(guī)劃設(shè)計(jì)和實(shí)現(xiàn)是一項(xiàng)極其復(fù)雜的系統(tǒng)工程，展望其能在結(jié)合計(jì)算智能方法，如差分進(jìn)化、遺傳算法、粒子群算法、免疫算法、模糊邏輯算法、BP網(wǎng)絡(luò)、人工勢(shì)場(chǎng)的改進(jìn)、模擬退火和環(huán)境建模方法等方面取得新的突破。

參考文獻(xiàn)：

［1］WEISS G.Multiagent systems:a modern approach to distributed modern approach to artificial intelligence[M].Cambridge， Massachusetts：MIT Press，1999：121-161.

[2]蔡自興，徐光祐.人工智能及其應(yīng)用:研究生用書(shū)[M].3版.北京：清華大學(xué)出版社，2004：124-198.

[3]譚民，王碩，曹志強(qiáng).多機(jī)器人系統(tǒng)[M].北京：清華大學(xué)出版社，2005：6-81.

[4]薄喜柱，洪炳熔.動(dòng)態(tài)環(huán)境下多移動(dòng)機(jī)器人路徑規(guī)劃的一種新方法[J].機(jī)器人，2001，23（5）：407-410.

[5]顧國(guó)昌，李亞波.基于總體勢(shì)減小的動(dòng)態(tài)調(diào)度技術(shù)解決多機(jī)器人的路徑規(guī)劃[J].機(jī)器人，2001，23（2）：171-174.

[6]孫樹(shù)棟，林茂.基于遺傳算法的多移動(dòng)機(jī)器人協(xié)調(diào)路徑規(guī)劃[J].自動(dòng)化學(xué)報(bào)，2000，26（5）：672-676.

[7]周明，孫樹(shù)棟，彭炎午.基于遺傳算法的多機(jī)器人系統(tǒng)集中協(xié)調(diào)式路徑規(guī)劃[J].航空學(xué)報(bào)，2000，21（2）：146-149.

[8]CAI Zixing，PENG Zhihong.Cooperative coevolutionary adaptive genetic algorithm in path planning of cooperative multimobile robot systems[J].Journal of Intelligent and Robotic Systems:Theory and Applications，2002，33(1):61-71.

[9]朱慶保.全局未知環(huán)境下多機(jī)器人運(yùn)動(dòng)螞蟻導(dǎo)航算法[J].軟件學(xué)報(bào)，2006，17（9）：1890-1898.

[10]SANDHOLM T W，CRITES R H.Multiagent reinforcement learning in the iterated prisoner’s dilemma[J].BioSystems，1996，37(1):147-166.

[11]高陽(yáng)，陳世福，陸鑫.強(qiáng)化學(xué)習(xí)研究綜述[J].自動(dòng)化學(xué)報(bào)，2004，30（1）：

86-100.

[12]MATARIC M J.Interaction and intelligent behavior[D].Massachusetls:Department of Electrical Engineering and Computer Science，MIT，1994.

[13]張芳，顏國(guó)正，林良明.基于再勵(lì)學(xué)習(xí)的多移動(dòng)機(jī)器人協(xié)調(diào)避障路徑規(guī)劃方法[J].計(jì)算機(jī)工程與應(yīng)用，2003，39（3）：80-83.

[14]王醒策，張汝波，顧國(guó)昌.多機(jī)器人動(dòng)態(tài)編隊(duì)的強(qiáng)化學(xué)習(xí)算法研究[J].計(jì)算機(jī)研究與發(fā)展，2003，40（10）：1444-1450.

[15]宋一然.基于強(qiáng)化學(xué)習(xí)的多機(jī)器人路徑規(guī)劃方法[J].莆田學(xué)院學(xué)報(bào)，2006，13（2）：38-41.

[16]韓學(xué)東，洪炳熔.基于人工神經(jīng)網(wǎng)絡(luò)的多機(jī)器人協(xié)作學(xué)習(xí)研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2002，23（6）：1-3.

[17]唐振民，趙春霞，楊靜宇，等.基于動(dòng)態(tài)規(guī)劃思想的多機(jī)器人路徑規(guī)劃[J].南京理工大學(xué)學(xué)報(bào)，2003，27（5）：610-615.

[18]孫茂相，周明，王艷紅，等.多移動(dòng)機(jī)器人實(shí)時(shí)最優(yōu)運(yùn)動(dòng)規(guī)劃[J].控制與決策，1998，

13（2）：125-130.

[19]焦立男，唐振民.基于局部傳感和通訊的多機(jī)器人運(yùn)動(dòng)規(guī)劃框架[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(17)：89-93.

[20]沈捷，費(fèi)樹(shù)岷，鄭波.多移動(dòng)機(jī)器人保持隊(duì)形路徑規(guī)劃[J].東南大學(xué)學(xué)報(bào)，2005，35(3):391-395.

[21]MANSOR M A，MORRIS A S.Path planning in unknown environment with obstacles using virtual window[J].Journal of Intelligent and Robotic Systems，1999，24(3):235-251.

[22]徐潼，唐振民.多機(jī)器人系統(tǒng)中的動(dòng)態(tài)避碰規(guī)劃[J].計(jì)算機(jī)工程，2003，29(17):

79-81，104.

[23]周明，孫茂相，尹朝萬(wàn)，等.多移動(dòng)機(jī)器人分布式智能避撞規(guī)劃系統(tǒng)[J].機(jī)器人，1999，21（2）：139-143.

[24]任炏，陳宗海.基于強(qiáng)化學(xué)習(xí)算法的多機(jī)器人系統(tǒng)的沖突消解的方法[J].控制與決策，2006，21(4):430-434，439.

[25]歐錦軍，朱楓.一種多移動(dòng)機(jī)器人避碰規(guī)劃方法[J].機(jī)器人，2000，22(6):474-481.

[26]景興建，王越超，談大龍.基于人工協(xié)調(diào)場(chǎng)的多移動(dòng)機(jī)器人實(shí)時(shí)協(xié)調(diào)避碰規(guī)劃[J].控制理論與應(yīng)用，2004，21(5):757-764.

[27]PANAIT L，LUKE S.Cooperative multiagent learning:the state of the art[J].Autonomous Agents and MultiAgent Systems，2005，11(3):387-434.

[28]TZAFESTAS C S，PROKOPIOU P A，TZAFESTAS S G.Path planning and control of a cooperative three robot system manipulating large objects[J].Journal of Intelligent and Robotic Systems，1998，22(2):99-116.

[29]薛宏濤，葉媛媛，沈林成，等.多智能體系統(tǒng)體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制研究綜述[J].機(jī)器人，2001，23（1）：85-90.

[30]周風(fēng)余，李貽斌，宋銳，等.基于混合式多智能體系統(tǒng)的協(xié)作多機(jī)器人系統(tǒng)研究[J].山東大學(xué)學(xué)報(bào):工學(xué)版，2005，35(1):82-87.

[31]夏冰，張佐，張毅，等.基于多智能體系統(tǒng)的動(dòng)態(tài)路徑選擇算法研究[J].公路交通科技，2003，20（1）：93-96.

[32]陳雪江.基于強(qiáng)化學(xué)習(xí)的多機(jī)器人協(xié)作機(jī)制研究[D].杭州：浙江工業(yè)大學(xué)，2004.

[33]SMITH R.The contract net protocol:highlevel communication and control in a distributed problem solver[J].IEEE Trans on Computer，1980，C-29(12):1104-1113.

第5篇

關(guān)鍵詞：企業(yè)物資；配送；車輛路徑問(wèn)題；路徑規(guī)劃；里程節(jié)約法

一、前言

隨著信息技術(shù)在現(xiàn)代企業(yè)中的廣泛應(yīng)用和高速發(fā)展，企業(yè)信息化程度大幅提高，企業(yè)的許多革命性的創(chuàng)新成果得益于此。在激烈的市場(chǎng)競(jìng)爭(zhēng)中，倉(cāng)儲(chǔ)配送和信息技術(shù)的有機(jī)結(jié)合為企業(yè)帶來(lái)了新的機(jī)遇，建設(shè)智慧倉(cāng)儲(chǔ)網(wǎng)絡(luò)的理念應(yīng)運(yùn)而生。而配送作為銜接各個(gè)物流節(jié)點(diǎn)的關(guān)鍵流程，使倉(cāng)儲(chǔ)網(wǎng)絡(luò)形成為一個(gè)系統(tǒng)性的整體，保證了物資的正常供應(yīng)。優(yōu)化配送車輛路徑能提高配送效率，降低配送成本，并提升配送準(zhǔn)確性。

物資公司作為公司的專業(yè)分公司，負(fù)責(zé)管理在上海區(qū)域所有工程及運(yùn)維檢修物資的供應(yīng)。工程項(xiàng)目物資的供應(yīng)分為供應(yīng)商直送現(xiàn)場(chǎng)和倉(cāng)庫(kù)供應(yīng)現(xiàn)場(chǎng)兩種類型。其中，供應(yīng)商直送現(xiàn)場(chǎng)為一次配送，關(guān)鍵點(diǎn)在于供應(yīng)計(jì)劃與供應(yīng)商的有效銜接與調(diào)度協(xié)同；而利用公司倉(cāng)儲(chǔ)配送網(wǎng)絡(luò)，通過(guò)中心庫(kù)向各周轉(zhuǎn)庫(kù)配送以供應(yīng)現(xiàn)場(chǎng)物資需求的過(guò)程為二次配送。合理二次配送車輛路徑規(guī)劃與實(shí)施，能提高后續(xù)工程建設(shè)、運(yùn)維檢修及應(yīng)急搶修的需求響應(yīng)速度，增強(qiáng)物資供應(yīng)的計(jì)劃性和準(zhǔn)確性，可有效提升物資供應(yīng)管理水平。

二、車輛路徑問(wèn)題定義

車輛路徑問(wèn)題是指存在幾個(gè)物資需求方，各有一定數(shù)量的物資需求，由一個(gè)配送中心提供物資，并安排一個(gè)車隊(duì)配送物資。為此需要規(guī)劃合理的行車路線以使他們的物資需求得到滿足，且能在一定的約束條件下，達(dá)到路程最短或耗時(shí)最少的目標(biāo)。

公司有十二個(gè)周轉(zhuǎn)庫(kù)，當(dāng)周轉(zhuǎn)庫(kù)內(nèi)某種物資數(shù)量低于安全庫(kù)存時(shí)，由中心庫(kù)提供物資進(jìn)行補(bǔ)庫(kù)。由于工程項(xiàng)目對(duì)響應(yīng)速度要求較高，當(dāng)需要對(duì)多個(gè)周轉(zhuǎn)庫(kù)進(jìn)行補(bǔ)庫(kù)時(shí)，必須綜合周轉(zhuǎn)庫(kù)的地理位置、物資需求量、車輛的運(yùn)載量、配送次數(shù)等，設(shè)計(jì)出合理的車輛配送路徑。

三、配送路徑規(guī)劃意義

1.避免交叉運(yùn)輸

中心庫(kù)車輛配送路徑規(guī)劃，將原先零散配送的物資進(jìn)行整合后，以合理的配送路徑集中配送，避免了交叉運(yùn)輸?shù)那闆r，縮短了總配送距離，降低了運(yùn)輸成本。

2.推進(jìn)節(jié)能環(huán)保

車輛配送路徑優(yōu)化在滿足各周轉(zhuǎn)庫(kù)的物資需求的前提下，以縮短配送車輛的總行駛距離為目標(biāo)，能提高能源利用效率，推動(dòng)公司更積極地承擔(dān)節(jié)能環(huán)保的社會(huì)責(zé)任。

四、配送路徑規(guī)劃過(guò)程

1.組織結(jié)構(gòu)

物資公司倉(cāng)儲(chǔ)配送網(wǎng)絡(luò)包括了集中的物資調(diào)配中心、一個(gè)中心庫(kù)以及十二個(gè)周轉(zhuǎn)庫(kù)。

（1）物資調(diào)配中心作為信息匯集、指令的中心，實(shí)時(shí)獲取中心庫(kù)和周轉(zhuǎn)庫(kù)內(nèi)庫(kù)存物資數(shù)量、物資需求數(shù)量等信息，并根據(jù)這些信息判斷是否需要補(bǔ)庫(kù)。

（2）如果周轉(zhuǎn)庫(kù)需要補(bǔ)庫(kù)，物資調(diào)配中心發(fā)送補(bǔ)庫(kù)指令給中心庫(kù)。

（3）中心庫(kù)綜合需補(bǔ)庫(kù)的周轉(zhuǎn)庫(kù)數(shù)量、地理位置及物資需求量等，規(guī)劃所需的車輛數(shù)、配送路徑等信息，將物資配送至周轉(zhuǎn)庫(kù)。

2.車輛路徑問(wèn)題描述

對(duì)于物資倉(cāng)儲(chǔ)配送網(wǎng)絡(luò)，配送車輛路徑問(wèn)題可以描述為，十二個(gè)周轉(zhuǎn)庫(kù)的位置固定且各有一定的需求量，中心庫(kù)用多輛載重量固定的汽車進(jìn)行配送，要求合理安排汽車路線以使總距離最短，并能滿足以下條件：

（1）每個(gè)周轉(zhuǎn)庫(kù)的物資需求到能滿足；

（2）每個(gè)周轉(zhuǎn)庫(kù)的物資必須由盡可能少的車輛配送，例如在周轉(zhuǎn)庫(kù)的需求能由一輛汽車滿足的情況下，必須只由一輛汽車配送；

（3）每條配送路徑上各周轉(zhuǎn)庫(kù)的需求量總和不能超過(guò)汽車載重量。

3.車輛路徑規(guī)劃

將中心庫(kù)及十二個(gè)周轉(zhuǎn)庫(kù)構(gòu)成的13個(gè)的節(jié)點(diǎn)兩兩連線，共有C132=78種組合，即這13個(gè)倉(cāng)庫(kù)中任意兩個(gè)倉(cāng)庫(kù)間的路徑共計(jì)78條。利用Google、百度等電子地圖軟件，將兩個(gè)倉(cāng)庫(kù)分別作為起點(diǎn)和終點(diǎn)，搜索出這78條路線以及之間的行駛距離。以字母O表示中心庫(kù)，字母A至L表示十二個(gè)周轉(zhuǎn)庫(kù)。當(dāng)有多個(gè)周轉(zhuǎn)庫(kù)需要補(bǔ)庫(kù)時(shí)，配送路徑確定步驟如下：

（1）確定各個(gè)周轉(zhuǎn)庫(kù)需要的物資數(shù)量；

（2）與汽車載重量進(jìn)行比較，確定需要的汽車數(shù)量；

（3）根據(jù)各周轉(zhuǎn)庫(kù)的需求量，運(yùn)用里程節(jié)約法，就近的倉(cāng)庫(kù)由同一汽車配送，同時(shí)避免交叉運(yùn)輸?shù)那闆r，形成配送路徑；

（4）根據(jù)實(shí)時(shí)路況，對(duì)配送路徑進(jìn)行一定調(diào)整，避免高峰期路段擁堵導(dǎo)致無(wú)法及時(shí)配送。

由于從實(shí)際情況考慮，為減少最后配送到的幾個(gè)倉(cāng)庫(kù)的等待時(shí)間，在12個(gè)周轉(zhuǎn)庫(kù)中按地理位置分為兩塊區(qū)域，在郊環(huán)附近的7個(gè)倉(cāng)庫(kù)為一個(gè)配送區(qū)域，郊環(huán)線以內(nèi)的4個(gè)倉(cāng)庫(kù)和崇明區(qū)域?yàn)橐粋€(gè)配送區(qū)域。

以郊環(huán)線附近7個(gè)倉(cāng)庫(kù)的配送為例，如下圖所示，每汽車載重量為5噸，A至G共7個(gè)周轉(zhuǎn)庫(kù)需中心庫(kù)O配送物資，直線上的數(shù)字為距離，括號(hào)內(nèi)的為對(duì)應(yīng)的周轉(zhuǎn)庫(kù)的物資需求量。

4.路徑信息

配送路徑規(guī)劃完畢后，將行車路線信息給對(duì)應(yīng)的汽車司機(jī)。車輛出發(fā)后，利用短信在途跟蹤獲取車輛實(shí)時(shí)的位置信息，并將實(shí)時(shí)路況信息傳遞給司機(jī)，減少因交通擁堵造成的配送延誤。

五、結(jié)語(yǔ)

本文綜合各周轉(zhuǎn)庫(kù)地理位置、需求數(shù)量、汽車運(yùn)載量等方面，運(yùn)用里程節(jié)約法規(guī)劃出車輛配送路徑。車輛配送路徑規(guī)劃將對(duì)原先粗放式的配送方式進(jìn)行優(yōu)化，積極配合政府及上級(jí)公司對(duì)節(jié)能環(huán)保提出的要求，在滿足各倉(cāng)庫(kù)需求的前提下縮短總配送距離，提高物資配送效率，降低配送成本。物資公司后續(xù)將逐步加強(qiáng)自動(dòng)化和信息化建設(shè)，推進(jìn)倉(cāng)儲(chǔ)網(wǎng)絡(luò)各類信息的實(shí)時(shí)共享、獲取、分析和處理，運(yùn)用先進(jìn)信息技術(shù)提高配送準(zhǔn)確性和效率效益，確保智慧倉(cāng)儲(chǔ)網(wǎng)絡(luò)的配送脈絡(luò)高效穩(wěn)定，構(gòu)建一個(gè)現(xiàn)代化、智慧化、特色化的倉(cāng)儲(chǔ)配送體系。

參考文獻(xiàn)：

[1]張玲，王朝霞.物流配送路徑優(yōu)化的模型與求解[J].商場(chǎng)現(xiàn)代化，2006.11.

第6篇

關(guān)鍵詞:路徑規(guī)劃; 地標(biāo); 預(yù)處理; 層次縮減算法; 三角啟發(fā)算法

中圖分類號(hào): TP312.8文獻(xiàn)標(biāo)志碼:A

Landmark.oriented heuristic routing algorithm in traffic network

MENG Ke*, ZHANG Chun.yan

School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221008, China

Abstract:

To improve the query efficiency of road routing algorithm in large-scale traffic network, a landmark-oriented algorithm based on A* algorithm was proposed. Select the most important vertexes and edges as landmarks during preprocessing, choose appropriate landmarks as the reference parameters and calculate in sections in point-to-point routing. Experiment results indicate that it has higher query efficiency and more reasonable results in long-distance road routing.

To improve the query efficiency of road routing algorithm in large.scale traffic network, a landmark.oriented algorithm based on A* algorithm was proposed. Select the most important vertexes and edges as landmarks during preprocessing, choose appropriate landmarks as the reference parameters and calculate in sections in point.to.point routing. The experimental results indicate that it has higher query efficiency and more reasonable results in long.distance road routing.

Key words:

path.planning; landmark; preprocessing; Contraction Hierarchies (CH) algorithm; A* Landmarks Triangle (ALT) algorithm

0 引言

對(duì)于大規(guī)模交通網(wǎng)絡(luò)，Dijkstra算法［1］需要花費(fèi)長(zhǎng)時(shí)間進(jìn)行計(jì)算，不符合實(shí)時(shí)性的要求。目前相關(guān)的優(yōu)化算法有啟發(fā)式算法和預(yù)處理算法兩種。啟發(fā)式算法(A*)［2］使用合適的啟發(fā)函數(shù)減少搜索空間以獲得較高的查詢效率，啟發(fā)函數(shù)會(huì)直接影響最后的計(jì)算結(jié)果；預(yù)處理算法使用點(diǎn)或邊標(biāo)記法、快捷路徑法、區(qū)塊分割法等對(duì)網(wǎng)絡(luò)中的邊進(jìn)行合并和標(biāo)記以迅速求出最短路徑，但需要大量的輔助存儲(chǔ)空間。

根據(jù)實(shí)際交通網(wǎng)絡(luò)的特點(diǎn)：在主干道上通過(guò)的最短路徑最多，存在重要的邊和點(diǎn)；對(duì)于長(zhǎng)距離的路徑規(guī)劃，出發(fā)點(diǎn)和目標(biāo)點(diǎn)的中間節(jié)點(diǎn)有可能成為最短路徑上的點(diǎn)。本文以A*算法為基礎(chǔ)，將地圖中關(guān)鍵的節(jié)點(diǎn)選為地標(biāo)，并將地標(biāo)作為啟發(fā)函數(shù)的啟發(fā)參數(shù)來(lái)求得路徑規(guī)劃的合理解。為提高長(zhǎng)距離路徑規(guī)劃的查詢效率，使用分段處理的思想將查詢分割為若干子查詢，并給出相關(guān)的優(yōu)化方法。

1 相關(guān)研究

對(duì)于靜態(tài)網(wǎng)絡(luò)圖G=(V,E)，大多數(shù)優(yōu)化算法需要經(jīng)過(guò)充分的預(yù)處理。三角啟發(fā)算法（A* Landmarks Triangle，ATL）［3］39算法將圖G按中心點(diǎn)劃分為若干區(qū)域，每個(gè)區(qū)域選取一個(gè)標(biāo)志點(diǎn)(LandMark)，根據(jù)三角不等式使搜索路徑趨向于目標(biāo)節(jié)點(diǎn)，大幅度減少搜索空間，從而提高查詢效率。

文獻(xiàn)［4］提出一種分層合并的預(yù)處理算法CH，對(duì)原始圖G的邊進(jìn)行迭代合并，產(chǎn)生一組生成圖{G1,G2,…,Gh}，生成圖和原始圖的邊使用標(biāo)號(hào)對(duì)應(yīng)，以便求解后還原原始路徑。這種預(yù)處理算法非常消耗存儲(chǔ)空間，不適合于大規(guī)模網(wǎng)絡(luò)，但是可以快速求出最短路徑。經(jīng)過(guò)預(yù)處理的CH算法時(shí)間復(fù)雜度可以達(dá)到O（N log H），N為合并圖的平均邊數(shù)，H為合并圖的層數(shù)。

Arc.Flags［5］基于區(qū)域劃分的思想對(duì)圖進(jìn)行預(yù)處理。將圖劃分為K個(gè)區(qū)域，每一條邊(v,w)存儲(chǔ)一個(gè)K比特的參數(shù)，第i位代表從點(diǎn)v到區(qū)域i的最短路徑中包含此邊。ARC.Flags可以精確求出最短路徑，但預(yù)處理時(shí)間較長(zhǎng)。Chase算法［6］綜合CH和ARC.Flags的特點(diǎn)，對(duì)ARC.Flags劃分的區(qū)域使用CH算法進(jìn)行合并處理，加快預(yù)處理時(shí)間。

Bauer等［7］提出一種混合算法SHARC，對(duì)CH和ARC.Flags進(jìn)行了多項(xiàng)改進(jìn)，提出分層標(biāo)記的思想，可以縮短預(yù)處理時(shí)間和減少額外空間。分層的ARC.Flags提供搜索方向，CH加速區(qū)域內(nèi)的路徑搜索，在單向搜索環(huán)境中SHARC可以提供非常高效的精確最短路徑。經(jīng)過(guò)修改的SHARC可以進(jìn)行時(shí)變最短路徑問(wèn)題的搜索，文獻(xiàn)［8］對(duì)此有詳細(xì)描述。

2 地標(biāo)導(dǎo)向的啟發(fā)式算法

2.1 地標(biāo)的選取

交通網(wǎng)絡(luò)圖一般擁有層次關(guān)系，鄉(xiāng)鎮(zhèn)與城市之間有干道相連，城市與城市之間有高速相連，在路徑規(guī)劃中這些連接線路被通過(guò)的次數(shù)最多。對(duì)于具有這一特點(diǎn)的圖G，地標(biāo)集的定義如下：

設(shè)r為一個(gè)搜索半徑，點(diǎn)u為中心，2r為半徑的G的子圖記為Bu,2r，選取滿足以下條件的最短路徑P，PBu,2r并且Len(P)>r（Len(P)為P的歐拉長(zhǎng)度）；如果存在點(diǎn)集Cu對(duì)于所有的P滿足Cu P，則Cu為Bu,2r的地標(biāo)集，并且設(shè)h=max(|Cu|)為G的地標(biāo)度數(shù)（|Cu|為Cu的節(jié)點(diǎn)個(gè)數(shù)）。顯然h越大地標(biāo)對(duì)最短路徑的貢獻(xiàn)越大，在路徑規(guī)劃時(shí)可利用的地標(biāo)節(jié)點(diǎn)越多。

計(jì)算大規(guī)模交通網(wǎng)絡(luò)的地標(biāo)集，采用以下幾個(gè)步驟。

1)選擇節(jié)點(diǎn)密集型的區(qū)域，將圖分割為搜索半徑為r的不同區(qū)域。在實(shí)驗(yàn)中會(huì)討論r在不同取值時(shí)地標(biāo)集獲取情況以及啟發(fā)式算法的查詢速度。

2)對(duì)于區(qū)域Bu,2r，使用CH算法進(jìn)行預(yù)處理以便于快速計(jì)算最短路徑。

3)為Bu,4r中的每一個(gè)點(diǎn)對(duì)計(jì)算最短路徑，獲取最短路徑集合P={Pv,w|v,w ∈Bu,4r ,|Pv,w|>r}。

4)對(duì)P中所有的路徑取交集獲得地標(biāo)集Cu。

2.2 啟發(fā)式算法設(shè)計(jì)

本文將地標(biāo)節(jié)點(diǎn)作為啟發(fā)式搜索的啟發(fā)節(jié)點(diǎn)，求解思想如下。

對(duì)于點(diǎn)對(duì)（s,t）如果屬于同一分割區(qū)域，由于使用了CH算法進(jìn)行預(yù)處理，可以快速求得精確的最短路徑。如果（s,t）屬于不同區(qū)域則使用以下啟發(fā)式規(guī)則。

1)從s所在區(qū)域的地標(biāo)集中選取距離t最近的地標(biāo)c作為下一跳的啟發(fā)節(jié)點(diǎn)，s到c的最短路徑使用CH求得。如果s所在區(qū)域沒(méi)有地標(biāo)集，則設(shè)c=s，轉(zhuǎn)向第2）步。

2)從鄰近區(qū)域的地標(biāo)集中選取距離t最近的地標(biāo)c′作為啟發(fā)點(diǎn)，使用ALT算法求出（c,c′）的最短路徑。

3)重復(fù)以上步驟直到c′與t在同一分割區(qū)域，使用CH算法計(jì)算（c′,t）最短路徑。

4)對(duì)最短路徑進(jìn)行合并輸出。

CH算法在區(qū)域內(nèi)進(jìn)行快速搜索，同時(shí)對(duì)于不同區(qū)域采用ALT算法控制搜索方向，使搜索始終沿著目標(biāo)進(jìn)行，這是一種分段搜索的思想，對(duì)于長(zhǎng)距離的最短路徑求解由于有地標(biāo)集提供搜索參考，搜索線路比ALT更加精確，耗時(shí)更短。

2.3 算法分析與優(yōu)化

CHALT算法的地標(biāo)集預(yù)處理比較耗時(shí)，但可以在多項(xiàng)式時(shí)間之內(nèi)完成計(jì)算。對(duì)于G的一個(gè)稠密子圖，從空集開(kāi)始， 使用CH算法從所有待處理的路徑中選取一個(gè)覆蓋所有路徑的點(diǎn)，然后將此點(diǎn)從圖中移除，對(duì)剩余路徑迭代計(jì)算，直到不存在滿足條件的點(diǎn)為止，在有限次迭代后算法會(huì)終止。對(duì)子圖預(yù)處理的時(shí)間復(fù)雜度為O(n log nO(CH))，其中n為子圖的節(jié)點(diǎn)個(gè)數(shù)，O（CH）為CH算法的時(shí)間復(fù)雜度。

對(duì)于ALT算法，雙向搜索的收斂速度一般比單向搜索快［9］，因此使用雙向CHALT查詢可以獲得更好的時(shí)間效率，具體執(zhí)行步驟如下：

1)使用前向搜索計(jì)算(s,t)的最短路徑獲取一個(gè)啟發(fā)點(diǎn)cf;

2)使用后向搜索計(jì)算(t,s)的最短路徑獲取一個(gè)啟發(fā)點(diǎn)cb;

3)設(shè)s=cf , t=cb 重復(fù)1)，2)兩步，最終搜索會(huì)在同一個(gè)節(jié)點(diǎn)相遇;

4)合并前向搜索和后向搜索的最短路徑后輸出。

對(duì)于地標(biāo)集，可以使用TNR［10］的思想進(jìn)行最短路徑索引，TNR計(jì)算并存儲(chǔ)所有地標(biāo)之間的最短路徑并存儲(chǔ)在一張|C| × |C|的表格中，其中|C|為圖G中地標(biāo)節(jié)點(diǎn)的個(gè)數(shù)。如果s和t分別在不同的分割區(qū)域，并且存在地標(biāo)，則根據(jù)索引表查詢地標(biāo)之間的最短路徑，否則執(zhí)行啟發(fā)式搜索。對(duì)地標(biāo)的查詢可以在常數(shù)時(shí)間之內(nèi)完成。大規(guī)模網(wǎng)絡(luò)圖使用CHALT+TNR算法可以在犧牲少量存儲(chǔ)空間的前提下提供最優(yōu)的性能。

3 實(shí)驗(yàn)

使用Intel Pentium CPU 2.5GHz、2GB RAM完成本算法和其他算法的比較實(shí)驗(yàn)，算法采用C++編寫(xiě)。實(shí)驗(yàn)數(shù)據(jù)選用北京市交通路網(wǎng)（包含81534個(gè)路段和34219個(gè)節(jié)點(diǎn)）。最短路徑的度量標(biāo)準(zhǔn)為距離最短，在實(shí)驗(yàn)中使用歐拉距離完成路徑計(jì)算。

表1為不同的最短路徑算法在1000組隨機(jī)查詢中的平均時(shí)間比較。預(yù)處理的時(shí)間使用分鐘計(jì)算，預(yù)處理每節(jié)點(diǎn)所占用的額外空間單位為字節(jié)，額外空間為負(fù)說(shuō)明預(yù)處理后的搜索圖比原圖規(guī)模小。從表1中可以看出ARC.Flags和SHARC雖然執(zhí)行效率比較高，但需要長(zhǎng)時(shí)間的預(yù)處理，并且節(jié)點(diǎn)變更對(duì)算法的影響大，不適用于大規(guī)模網(wǎng)絡(luò)；CHALT算法執(zhí)行時(shí)間屬于中上等，但預(yù)處理時(shí)間短，在經(jīng)過(guò)TNR優(yōu)化后的執(zhí)行時(shí)間接近SHARC算法的查詢時(shí)間；雙向CHALT算法在時(shí)間上比單向快一些。由于CHALT使用地標(biāo)節(jié)點(diǎn)作為啟發(fā)參數(shù)，地標(biāo)節(jié)點(diǎn)僅占所有節(jié)點(diǎn)的小部分，不容易受到節(jié)點(diǎn)變更的影響。

在CHALT算法中，劃分區(qū)域的大小將影響地標(biāo)集的選取和路徑規(guī)劃結(jié)果。表2表示不同搜索半徑r對(duì)查詢速度的影響，r的單位為km。從表2中可以看出在r=3km和r=4km時(shí)候在預(yù)處理時(shí)間少的情況下依然可以獲得不錯(cuò)的查詢效率，極端情況下r=0時(shí)算法變?yōu)锳LT算法；r=∞時(shí)算法將僅使用CH算法，地標(biāo)節(jié)點(diǎn)個(gè)數(shù)接近于0，啟發(fā)函數(shù)不可用，也就失去了地標(biāo)的參考價(jià)值。在實(shí)際應(yīng)用中需要根據(jù)實(shí)驗(yàn)來(lái)確定合適的搜索半徑，來(lái)達(dá)到效率與合理性的權(quán)衡。CHALT算法獲取的解為近似解，但接近最優(yōu)解，如圖1(圖1中黑色路徑為CHALT算法，白色路徑為Dijkstra算法)。CHALT算法優(yōu)先選擇重要的節(jié)點(diǎn)和邊，在地圖上表現(xiàn)為主要的街道和路口；Dijkstra算法對(duì)所有與(s,t)相關(guān)的路徑計(jì)算以獲得最優(yōu)解，而不會(huì)考慮節(jié)點(diǎn)的重要性，在實(shí)際應(yīng)用中存在不合理性。CHALT算法獲取的路徑比Dijkstra更平滑并且更合理。

4 結(jié)語(yǔ)

為解決大規(guī)模長(zhǎng)距離的最短路徑規(guī)劃問(wèn)題，本文根據(jù)分

段計(jì)算的思想，使用地標(biāo)集將啟發(fā)式搜索限制在靠近最短路徑的方向。實(shí)驗(yàn)證明CHALT算法在保證預(yù)處理和查詢效率的基礎(chǔ)上，得出更合理的計(jì)算結(jié)果，優(yōu)化后的算法查詢效率更高，可以應(yīng)用在大型交通網(wǎng)絡(luò)中。下一步研究方向?yàn)橐缘貥?biāo)為導(dǎo)向的啟發(fā)式算法在離散變權(quán)網(wǎng)絡(luò)中的應(yīng)用。

參考文獻(xiàn):

［1］

DIJKSTRA E W. A note on two problems in connexion with graphs ［J］. Numerische Mathematik, 1959(1):269-271.

［2］

GOLDBERG A V, KAPLAN H, WERNECK R F. Reach for A*: Efficient point.to.point shortest path algorithms ［C］// Proceedings of 7th International Workshop on Algorithm Engineering and Experiments. Miami: SIAM, 2006:129-143.

［3］

GOLDBERG A V, KAPLAN H, WERNECK R F. Better landmarks within reach［C］// WEA07: Proceedings of the 6th International Conference on Experimental Algorithms. Berlin: Springer.Verlag,2007:38-51.

［4］

GEISBERGER R, SANDERS P, SCHULTES D, et al. Contraction hierarchies: faster and simpler hierarchical routing in road networks［C］// WEA08: Proceedings of the 7th International Conference on Experimental Algorithms. Berlin: Springer.Verlag,2008:319-333.

［5］

KHLER E, MHRING R H, SCHILLING H. Fast point.to.point shortest path computations with arc.flags［C］// The Shortest Path Problem: Ninth DIMACS Implementation Challenge. Piscataway: IEEE, 2009:41-72.

［6］

LAUTHER U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background［EB/OL］.[2011-07-02].gi.days.de/archive/2004/downloads/gitage2004/vortraege/lauther.pdf.

［7］

BAUER R, DELLING D. SHARC: Fast and robust unidirectional routing ［J］. ACM Journal of Experimental Algorithmics, 2009, 14(12):12-26.

［8］

DELLING D. Time.dependent SHARC.routing ［J］. Algorithmica, 2009, 60(7): 60-94.

［9］

GOLDBERG A V, HARRELSON C. Computing the shortest path: A* search meets graph theory, #MSR.TR.2004.24 ［R］.USA: Microsoft Research, 2004.

［10］

BAST H, FUNKE S, SANDERS P, et al. Fast routing in road networks with transit nodes ［J］. Science, 2007,316(5824):566-593.

［11］

HILGER M. Accelerating point.to.point shortest path computations in large scale networks［R］. Berlin: Technische University, 2007.

第7篇

關(guān)鍵詞： 增維啟發(fā)式搜索； 智能車； 路徑規(guī)劃； 高效率； 平衡

中圖分類號(hào)： TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）36-0188-04

Increment-dimensional Heuristic Search Motion Planning Algorithm

WU Hong

（Department of Computer Science and Technology， Tongji University， Shanghai 201804， China）

Abstract： For intelligent vehicle motion planning， effective enough is always an important issue. The huge statue-space， high time complexity of the high dimensional search approach is always the bottle-neck of the algorithm. To solve this problem， this paper proposes a new method， increment-dimensional heuristic search algorithm. This method is a stepped-up heuristic search to reduce the searching status and improve the search algorithm execution efficiency. In experiment， the result shows that this algorithm reduces 87% of searching status and executes time is nearly 1/10 of that of the traditional heuristic search method. It is a very good trade-off between execution efficiency and trajectory quality.

Key words： increment-dimensional heuristic search； intelligent vehicle； motion planning； effective； trade-off

1 引言

在智能無(wú)人車領(lǐng)域，智能車無(wú)人車的行駛安全以及駕駛舒適度一直是一個(gè)非常重要的研究問(wèn)題。而智能無(wú)人車的路徑規(guī)劃是這一問(wèn)題的核心。智能無(wú)人車路徑規(guī)劃算法需要在有限的時(shí)間內(nèi)，輸出高質(zhì)量高精度的路徑，傳輸給智能無(wú)人車的控制模塊、執(zhí)行模塊加以執(zhí)行。一般的移動(dòng)機(jī)器人路勁規(guī)劃算法研究的是在高維度的空間里探索出一條路徑，相比之下，智能無(wú)人車的路徑規(guī)劃則需要考慮車輛動(dòng)力學(xué)模型約束，通常我們需要考慮四維狀態(tài)。二維狀態(tài)（x， y），表示車輛的地理坐標(biāo)，車輛的航向角θ，以及行駛速度v。在四維狀態(tài)空間里搜素出一條可行路徑，是一個(gè)計(jì)算密集型的任務(wù)。與此同時(shí)，智能無(wú)人車的行駛速度可能很高，因此要求規(guī)劃算法能夠在一個(gè)非常有限的時(shí)間里給出搜索的結(jié)果。

為了解決這一問(wèn)題，本文給出一種增維啟發(fā)式路徑規(guī)劃搜索算法。該算法采取一種分階段，逐步增加搜索維度的方法來(lái)生成路徑。在每一個(gè)階段，增維搜索算算法選擇離車輛當(dāng)前位置附近的一個(gè)區(qū)域，增加狀態(tài)空間維度，進(jìn)行啟發(fā)式搜索。因此該算法的輸出軌跡是多精度的軌跡。在車輛附近位置，輸出軌跡為高維度高精度，充分考慮車輛動(dòng)力學(xué)模型，駕駛舒適度，能耗以及可靠性。而在遠(yuǎn)處，低維度低精度的軌跡依然可以引導(dǎo)智能無(wú)人車的行駛方向正確，充分考慮的地圖信息，障礙物信息。從人類正常的駕駛習(xí)慣上來(lái)說(shuō)，駕駛員總是對(duì)近處的駕駛精度較高，而遠(yuǎn)處相對(duì)較低。該算法充分利用了這一點(diǎn)原理，犧牲了遠(yuǎn)處的軌跡精度，極大地提高了算法的運(yùn)行效率。在頻繁聯(lián)系的反復(fù)規(guī)劃中，車輛會(huì)一直執(zhí)行高精度部分軌跡。因此，該算法在運(yùn)行效率以及輸出軌跡質(zhì)量方面，取得一個(gè)非常好的均衡。

為了展示該算法的性能，本文進(jìn)行了仿真實(shí)驗(yàn)。在實(shí)驗(yàn)中，智能無(wú)人車剛剛進(jìn)入一個(gè)停車場(chǎng)，需要在目標(biāo)停車位泊車。實(shí)驗(yàn)結(jié)果表明，相比傳統(tǒng)的高維度啟發(fā)式搜索算法，該算法減少了超過(guò)87%的搜索狀態(tài)，運(yùn)行性能提高了近10倍。

2 研究現(xiàn)狀及文獻(xiàn)綜述

從20世紀(jì)70年代開(kāi)始，歐美的西方國(guó)家開(kāi)始無(wú)人駕駛汽車方面的研究工作，并在智能無(wú)人車的控制和商用化方面取得一定進(jìn)展。在汽車工業(yè)非常發(fā)達(dá)的德國(guó)，各大汽車公司都資助或者聯(lián)合高等院校以開(kāi)發(fā)可在普通道路上行駛的智能無(wú)人車。目前，歐盟已啟動(dòng)一個(gè)名叫CyberCars的智能無(wú)人車項(xiàng)目，以推動(dòng)智能無(wú)人車的研究和各國(guó)間智能無(wú)人車技術(shù)的信息共享。

在20世紀(jì)的80年代，我國(guó)部分大學(xué)開(kāi)始智能無(wú)人車的研究工作，雖然起步較晚也取得一定成果。目前，從事這方面研究工作的 主要是國(guó)防科技大學(xué)、軍事交通學(xué)院及清華大學(xué)等科研機(jī)構(gòu)。[1-6]

在智能無(wú)人車決策模塊的相關(guān)研究中，最核心的部分是路徑規(guī)劃算法的研究。文獻(xiàn)[7]提出一種快速擴(kuò)展隨機(jī)樹(shù)生成算法―RRT （Rapid-Exploring Random Tree）算法。RRT是一種多維空間中有效的路徑規(guī)劃算法。它以一個(gè)初始點(diǎn)作為根節(jié)點(diǎn)，通過(guò)隨機(jī)采樣增加葉子節(jié)點(diǎn)的方式，生成一個(gè)隨機(jī)擴(kuò)展樹(shù)，當(dāng)隨機(jī)樹(shù)中的葉子節(jié)點(diǎn)包含了目標(biāo)點(diǎn)或者進(jìn)入目標(biāo)區(qū)域，便可以在當(dāng)前隨機(jī)樹(shù)中找到一條從初始點(diǎn)到目標(biāo)點(diǎn)的路徑。文獻(xiàn)[8]在RRT算法在自動(dòng)駕駛汽車以及宇宙空間探測(cè)器路徑規(guī)劃上的應(yīng)用。文I[9]對(duì)RRT算法提出優(yōu)化方法并通過(guò)實(shí)驗(yàn)，解決了基本RRT算法存在的動(dòng)態(tài)環(huán)境中規(guī)劃路徑不穩(wěn)定的問(wèn)題，同時(shí)提出雙向RRT生成算法以及動(dòng)態(tài)步長(zhǎng)等優(yōu)化方法，提高了RRT算法生成初始點(diǎn)到目標(biāo)點(diǎn)路徑生成的速度。然而RRT算法在規(guī)劃路徑的過(guò)程中產(chǎn)生的是可行解，而非最優(yōu)解。文獻(xiàn)[10]提出了RRT*算法，RRT算法進(jìn)行了改進(jìn)，保證了RRT算法生成解是漸進(jìn)最優(yōu)解。然而RRT*算法在時(shí)間復(fù)雜度上遠(yuǎn)高于樸素的RRT算法。文獻(xiàn)[11]提出了一種RRT*算法加速的方法，通過(guò)使用預(yù)生成RRT隨機(jī)樹(shù)，在使用RRT*_S算法優(yōu)化當(dāng)前隨機(jī)樹(shù)，構(gòu)造出與RRT*算法生成隨機(jī)樹(shù)本質(zhì)相同的RRT*_S隨機(jī)樹(shù)，從而實(shí)現(xiàn)RRT*算法的加速。文獻(xiàn)[12]為麻省理工學(xué)院將RRT*算法運(yùn)用于叉車移動(dòng)路徑規(guī)劃的一次應(yīng)用實(shí)踐，并對(duì)RRT算法與RRT*算法在實(shí)際應(yīng)用中的結(jié)果給出對(duì)比分析。

文獻(xiàn)[13][14][15][16]給出了2007年美國(guó)DARPA智能無(wú)人車比賽麻省理工學(xué)院（MIT）參賽智能無(wú)人車的整體架構(gòu)，MIT智能無(wú)人車的軌跡生成算法，主要是用RRT算法生成可行路徑，并對(duì)該路徑進(jìn)行平滑，以此為基礎(chǔ)生成智能無(wú)人車運(yùn)動(dòng)軌跡。

文獻(xiàn)[17][18][19][20][21][22]主要闡述了狀態(tài)空間搜索算法，通過(guò)估價(jià)函數(shù)進(jìn)行啟發(fā)式搜索以及狀態(tài)空間搜索剪枝。文獻(xiàn)[23]提出了ARA*（Anytime A*）算法，對(duì)短時(shí)間間隔內(nèi)連續(xù)反復(fù)用A*搜素算法進(jìn)行空間狀態(tài)搜索這一類狀態(tài)空間搜索應(yīng)用場(chǎng)景進(jìn)行優(yōu)化。

3 增維啟發(fā)式搜索算法

增維啟發(fā)式搜索是一種兩階段的啟發(fā)式搜索算法。在算法的第一階段，搜索出一條從車輛當(dāng)前位置到目標(biāo)位置的幾何最短路的軌跡。在第一階段的搜索，我們只考慮二維的搜索狀態(tài)空間（x， y），即車輛的地理坐標(biāo)。第二階段，選取第一階段的路徑中的一個(gè)點(diǎn)作為本階段目標(biāo)點(diǎn)，搜索狀態(tài)加入車輛的航向角θ，以及行駛速度v，總體狀態(tài)空間提升到四維，并且考慮車輛動(dòng)力學(xué)模型，在此狀態(tài)空間下，搜索出一條高精度可執(zhí)行的車輛行駛軌跡。

3.1 第一階段搜索

在這一階段，因?yàn)槲覀冎豢紤]二維狀態(tài)空間（x， y），即車輛的地理坐標(biāo)。如果將狀態(tài)空間離散化，這一搜索問(wèn)題會(huì)退化成一個(gè)圖論的最短路問(wèn)題。雖然圖論的最短路問(wèn)題有很多經(jīng)典成熟的算法。但是在這里還是有一些值得討論的問(wèn)題。

3.1.1 柵格隨機(jī)化

一般地，在執(zhí)行最短路算法之前，會(huì)把狀態(tài)空間離散化成柵格，然后對(duì)柵格做4聯(lián)通或者8聯(lián)通處理，但是這種離散化方法會(huì)使最短路失去最優(yōu)解，如圖1a、1c所示。

圖1 a. 離散化使得幾何最短路失解；b. 隨機(jī)化18聯(lián)通柵格法；c. 8聯(lián)通柵格法幾何最短路（黑），隨機(jī)化18聯(lián)通柵格法幾何最短路（紅）。

a b c

為了解決這一問(wèn)題。如圖1b所示，算法使用一種隨機(jī)化18聯(lián)通的柵格法來(lái)離散化空間。即在柵格之間連邊的時(shí)候，每個(gè)柵格除了相鄰向相鄰8個(gè)柵格聯(lián)通，同時(shí)隨機(jī)向其他10個(gè)柵格聯(lián)通。選取的10個(gè)柵格滿足與該柵格曼哈頓距離小于7，滿足條件的格子約為100個(gè)，足以隨機(jī)化，同時(shí)連邊長(zhǎng)度小于兩個(gè)柵格長(zhǎng)度，也方便計(jì)算是否與障礙物碰撞。

3.1.2 最短路算法

在離散化為柵格之后，采用單源最短路算法來(lái)計(jì)算車輛當(dāng)前位置到其他位置的幾何最短路，雖然單源最短路算法非常的經(jīng)典成熟，但依舊有值得討論的地方。

最短路的經(jīng)典算法是堆優(yōu)化的Dijkstra算法，該算法時(shí)間復(fù)雜度為 [O（eloge）]，其中[e]代表離散化后邊的數(shù)量，然而在稀疏圖中，SPFA算法的實(shí)際時(shí)間復(fù)雜度約為[O（e）]，在18隨機(jī)聯(lián)通結(jié)構(gòu)的圖中效率比價(jià)高，因而在本階段中，我們采用SPFA算法計(jì)算單源最短路。

3.2 第二階段搜索

在第二階段的搜索中，我們選取第一階段結(jié)果，幾何最短路上的一個(gè)點(diǎn)來(lái)作為目標(biāo)點(diǎn)，在搜索狀態(tài)加入車輛的航向角θ，以及行駛速度v，在搜索中充分考慮車輛動(dòng)力學(xué)模型，搜索出一條高精度可執(zhí)行的車輛行駛軌跡。

3.2.1 啟發(fā)函數(shù)

在啟發(fā)式搜索過(guò)程中，一個(gè)強(qiáng)力有效的啟發(fā)式函數(shù)對(duì)搜索效率來(lái)說(shuō)至關(guān)重要。啟發(fā)式函數(shù)不僅為搜索的實(shí)際代價(jià)提供了一個(gè)下界，同時(shí)也是實(shí)際代價(jià)的一個(gè)良好估算，可以引導(dǎo)搜索往正確的方向擴(kuò)展，并且實(shí)現(xiàn)搜索剪枝，在第二階段的搜索中，使用以下啟發(fā)式函數(shù)。

動(dòng)力學(xué)約束無(wú)障礙啟發(fā)函數(shù)，[hnh（x，y，θ，v）]，該函數(shù)忽略障礙物信息，考慮車輛動(dòng)力學(xué)模型，在此條件下求出最優(yōu)的路徑。這一啟發(fā)式函數(shù)因?yàn)楹雎粤苏系K物信息，只考慮動(dòng)力學(xué)模型，所以可以離線計(jì)算、存儲(chǔ)，在真實(shí)路徑規(guī)劃的過(guò)程中查詢，計(jì)算速度極快。該函數(shù)極大的消除接近目標(biāo)點(diǎn)航向角錯(cuò)誤的搜索分支。

地圖信息非動(dòng)力學(xué)模型啟發(fā)函數(shù)，[hh（x，y）]，該啟發(fā)函數(shù)是上一啟發(fā)函數(shù)的對(duì)偶函數(shù)，忽略車輛動(dòng)力學(xué)模型，以幾何最短路作為啟發(fā)函數(shù)。該啟發(fā)函數(shù)充分考慮的地理信息，消除了錯(cuò)誤行駛方向的搜索分支。

結(jié)合二者，選取啟發(fā)函數(shù)[h（x， y，θ，v）] = max（[hnhx，y，θ，v， hh（x，y））]，

fxyv） = g（x， y， ，v） + h（x， y， ，v） （1）

fxyv） Fxyv） （2）

f 為狀態(tài)[（x， y， θ， v）]的估價(jià)函數(shù)， g為當(dāng)前搜索狀態(tài)[（x， y， θ， v）]的實(shí)際代價(jià)， [F]為實(shí)際搜索代價(jià)。

在該啟發(fā)函數(shù)的引導(dǎo)下，第二階段啟發(fā)式搜索可以高效地計(jì)算出四維高精度路徑。

4 仿真實(shí)驗(yàn)以及實(shí)驗(yàn)結(jié)果

為了展示該算法的性能，本文進(jìn)行了仿真實(shí)驗(yàn)。在實(shí)驗(yàn)中，智能無(wú)人車剛剛進(jìn)入一停車場(chǎng)，需要在目標(biāo)停車位泊車。實(shí)驗(yàn)環(huán)境為Ubuntu 12.04 Linux系統(tǒng)，Intel i5處理器， 8GB內(nèi)存。停車場(chǎng)大小為長(zhǎng)80米寬50米，柵格離散化精度為10厘米，車輛采用72個(gè)不同的航向角，同時(shí)采用兩個(gè)速度，最大的前向速度以及最大的后向速度。

圖2 a樸素四維啟發(fā)式搜索；b增維啟發(fā)式搜索；c樸素四維啟發(fā)式搜索輸出路徑；d增維啟發(fā)式搜索輸出路徑

a

b

c

d

表1 算法性能比^

[ 階段 樸素四維啟發(fā)式搜索 增維啟發(fā)式搜索 搜索狀態(tài)數(shù)量 第一階段 400000 第二階段 10808634 408773 共計(jì) 10808634 808773 算法運(yùn)行時(shí)間

（毫秒） 第一階段 142 第二階段 2844 141 共計(jì) 2844 283 ]

如圖1b，對(duì)于每一次路徑規(guī)劃，增維啟發(fā)式搜索算法可以有效地減少搜索狀態(tài)的數(shù)量，因?yàn)楦呔S度高精度部分的搜索集中在離車輛較近的區(qū)域，而從全局的角度，二維的幾何最短路依舊引導(dǎo)著軌跡往正確的方向。相比之下樸素的四維啟發(fā)式搜索搜索量極大（圖2b）。從輸出軌跡上看，兩者的輸出軌跡質(zhì)量幾乎相同（圖2c、2d）。

5 結(jié)論

本文展示了增維啟發(fā)式搜索路徑規(guī)劃算法。該算法分為兩階段。第一階段在全局考慮二維的搜索狀態(tài)空間，得出起始點(diǎn)到目標(biāo)位置的幾何最短路。在第一階段幾何最短路基礎(chǔ)上選取一個(gè)目標(biāo)點(diǎn)作為第二階段目標(biāo)狀態(tài)空間，進(jìn)而得到考慮了車輛動(dòng)力學(xué)模型、四維的高精度可執(zhí)行軌跡。仿真實(shí)驗(yàn)結(jié)果表明，在現(xiàn)實(shí)場(chǎng)景下，該算法極大地減少了搜索狀態(tài)數(shù)量，提高了算法執(zhí)行效率，同時(shí)輸出高質(zhì)量的智能無(wú)人車行駛軌跡。

參考文獻(xiàn)：

[1] 楊明.無(wú)人駕駛車輛研究綜述與展望[J]..哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2006，38（增刊）：1259-1262.

[2] 孫振平.自主駕駛汽車智能控制系統(tǒng)[D].國(guó)防科技大學(xué)，2004.

[3] 楊森森.基于GPS/INS/激光雷達(dá)的無(wú)人車組合導(dǎo)航[D].上海交通大學(xué)碩士學(xué)位論文，2013.

[4] 錢鈞，楊汝清，王晨，等，基于路標(biāo)的智能車輛定位[J].上海交通大學(xué)學(xué)報(bào)，2007，41（6）：894-898.

[5] 王曦鳴.軍用無(wú)人車的路徑規(guī)劃與仿真研究[D].北京交通大學(xué)碩士學(xué)位論文，2010.

[6] 曹玉芬，張國(guó)斌.美國(guó)無(wú)人地面車輛計(jì)劃[J].國(guó)外坦克，2004（5）：25-27.

[7] Rapidly-exploring random trees： A new tool for path planning. S. M. LaValle. TR 98-11， Computer Science Dept.， Iowa State University， October 1998

[8] RRT-based trajectory design for autonomous automobiles and spacecraft. P. Cheng， Z. Shen， and S. M. LaValle. Archives of Control Sciences， 11（3-4）：167--194， 2001.

[9] Rapidly-exploring random trees： Progress and prospects. S. M. LaValle and J. J. Kuffner. In Proceedings Workshop on the Algorithmic Foundations of Robotics， 2000.

[10] S. Karaman and E. Frazzoli， Sampling-based algorithms for optimal motion planning，I. Robotic Res.， vol. 30， no. 7， pp. 846C894， 2011.

[11] Yun-xiao Shan Bi-jun Li Jian-Zhou Yue-Zhang，An Approach to Speed Up RRT* ，2014 IEEE Inteligent Vehicles Symposium （IV） June 8-11

[12] Karaman S， Walter M R， Perez A， et al. Anytime motion planning using the RRT*[C]//Robotics and Automation （ICRA）， 2011 IEEE International Conference on. IEEE， 2011： 1478-1483.

[13] Leonard J， How J， Teller S， et al. A perception-driven autonomous urban vehicle[J]. Journal of Field Robotics， 2008， 25（10）： 727-774.

[14] Kuwata Y， Fiore G， Teo J， et al. Motion planning for urban driving using RRT[C]//Intelligent Robots and Systems， 2008. IROS 2008. IEEE/RSJ International Conference on. IEEE， 2008： 1681-1686.

[15] Leonard J， Barrett D， How J， et al. Team MIT urban challenge technical report[J]. 2007.

[16] Kuwata Y， Karaman S， Teo J， et al. Real-time motion planning with applications to autonomous urban driving[J]. Control Systems Technology， IEEE Transactions on， 2009， 17（5）： 1105-1118.

[17] Barbehenn， M. and Hutchinson， S. （1995）. Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest path trees. IEEE Transactions on Robotics and Automation， 11（2）： 198C214.

[18] Gaschnig， J. G. （1979）. Performance measurement and analsis of certain search algorithms. Ph.D. Dissertation， Carnegie Mellon University.

[19] Stentz， A. （1995）. The Focussed D* Algorithm for real-time replanning. Proceedings of the International Joint Conference on Artificial Intelligence （IJCAI）， pp. 1652C1659.

[20] Pearl， J. （1984）. Heuristics： Intelligent Search Strategies for Computer Problem Solving. Boston， MA： Addison-Wesley

第8篇

【關(guān)鍵詞】虛擬場(chǎng)景；路經(jīng)規(guī)劃；八叉樹(shù)；A*算法

中圖分類號(hào)：TP39文獻(xiàn)標(biāo)識(shí)碼A文章編號(hào)1006-0278（2013）06-172-01

一、引言

隨著虛擬現(xiàn)實(shí)技術(shù)的日益成熟，只有景色、建筑物等一般視景信息的虛擬場(chǎng)景已不能滿足人們的視覺(jué)需求，迫切需求一個(gè)有生命的對(duì)象引入到虛擬場(chǎng)景中，增加瀏覽者的沉浸感。虛擬場(chǎng)景中虛擬人的路徑規(guī)劃是虛擬現(xiàn)實(shí)研究中的一項(xiàng)關(guān)鍵技術(shù)。目前，研究者們已經(jīng)把研究的重心放在如何為虛擬人規(guī)劃出一條行走的最優(yōu)路徑，使虛擬人的路徑導(dǎo)航更具有真實(shí)感和可信度。

由于虛擬環(huán)境中的模型多由三角面網(wǎng)格組成，通過(guò)使用基于空間多層次劃分的八叉樹(shù)方法，充分發(fā)揮了其空間劃分的優(yōu)勢(shì)，加快了場(chǎng)景的渲染速度，減少了確定對(duì)象的處理時(shí)間以及存儲(chǔ)空間①。

文章采用八叉樹(shù)和A*算法相結(jié)合的方法，對(duì)路徑進(jìn)行規(guī)劃，并對(duì)A*算法做了改進(jìn)，以適應(yīng)八叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。

二、密集型區(qū)域八叉樹(shù)劃分算法

八叉樹(shù)是由四叉樹(shù)推廣到三維空間而形成的一種三維柵格數(shù)據(jù)結(jié)構(gòu)，它作為一種場(chǎng)景組織方法，廣泛應(yīng)用于虛擬現(xiàn)實(shí)系統(tǒng)，可顯著減少對(duì)場(chǎng)景中多邊形進(jìn)行排序的時(shí)間。

由于傳統(tǒng)八叉樹(shù)對(duì)空間的劃分是均勻的，導(dǎo)致了最終生成一個(gè)結(jié)構(gòu)不平衡的八叉樹(shù)，從而增加整個(gè)八叉樹(shù)的存儲(chǔ)空間以及各結(jié)點(diǎn)的遍歷時(shí)間。文章采用了對(duì)傳統(tǒng)八叉樹(shù)算法進(jìn)行改進(jìn)，采用基于密集型區(qū)域八叉樹(shù)劃分方法。密集型區(qū)域八叉樹(shù)的網(wǎng)格劃分算法是對(duì)每一子空間重新建立最小包圍盒，這樣避免了在建立頂點(diǎn)樹(shù)時(shí)，由于該部分頂點(diǎn)在空間上分布不均勻而導(dǎo)致樹(shù)的深度的增加，進(jìn)而減少了存儲(chǔ)空間，加快了網(wǎng)格模型數(shù)據(jù)的讀取速度。另外，由于建立了頂點(diǎn)的最小包圍盒，在誤差較小時(shí)，只有空間距離比較近的頂點(diǎn)才會(huì)聚合在一起；而相距較遠(yuǎn)的頂點(diǎn)只有在深層次簡(jiǎn)化時(shí)才會(huì)聚合，這些特點(diǎn)在一定程度上保證了簡(jiǎn)化時(shí)網(wǎng)格模型的逼真度。

密集型區(qū)域八叉樹(shù)劃分方法的算法描述如下：

步驟1使用OBB包圍盒方法建立模型的最小包圍盒。

步驟2以包圍盒的X軸、Y軸、Z軸方向的中分面作為分割基準(zhǔn)，將包圍盒平均劃分為八個(gè)子包圍盒。

步驟3如果每個(gè)子空間內(nèi)存在物體的屬性不相同或未達(dá)到規(guī)定的限差，則重新從步驟1開(kāi)始進(jìn)行劃分。否則，劃分結(jié)束，并對(duì)劃分后的每一個(gè)結(jié)點(diǎn)記錄下結(jié)點(diǎn)編號(hào)、劃分標(biāo)志、結(jié)點(diǎn)在頂點(diǎn)樹(shù)中的深度以及它所含的景物面片表的入口指針。

三、A*算法

A*算法是建立在典型的Dijkstra算法上的，是由Hart，Nilsson，Raphael等人首先提出的。該算法的創(chuàng)新之處在于選擇下一個(gè)被檢查的節(jié)點(diǎn)時(shí)引入了已知的全局信息，對(duì)當(dāng)前節(jié)點(diǎn)距終點(diǎn)的距離做出估計(jì)，作為評(píng)價(jià)該節(jié)點(diǎn)處于最優(yōu)路線上的可能性的量度，這樣就可以首先搜索可能性較大的節(jié)點(diǎn)，從而提高了搜索過(guò)程的效率。

下面是對(duì)A*算法的介紹，我們首先來(lái)介紹一下啟發(fā)式搜索中的估計(jì)函數(shù)。因?yàn)樵趩l(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。估價(jià)函數(shù)的表示如下：

其中是節(jié)點(diǎn)的估價(jià)函數(shù)，是已知的，指在狀態(tài)空間中從初始節(jié)點(diǎn)到節(jié)點(diǎn)的實(shí)際代價(jià)；是從結(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)，它體現(xiàn)了搜索的啟發(fā)信息，啟發(fā)信息決定著算法的啟發(fā)能力。啟發(fā)信息越多，估價(jià)函數(shù)就越好，即約束條件越多，則排除的節(jié)點(diǎn)就越多，說(shuō)明這個(gè)算法越好。這種做法存在一個(gè)平衡的問(wèn)題，也會(huì)使算法的準(zhǔn)確性下降。具體的說(shuō)，代表了搜索的廣度優(yōu)先趨勢(shì)，當(dāng)時(shí)，可以省略，這樣就提高了搜索效率。

A*算法是一個(gè)可采納的最好優(yōu)先算法。A*算法的估價(jià)函數(shù)可表示為：

這里，是估價(jià)函數(shù)，是起點(diǎn)到終點(diǎn)的最短路徑值，是到目標(biāo)的最短路經(jīng)啟發(fā)值。由于這個(gè)其實(shí)是無(wú)法預(yù)先知道的，所以我們用前面的估價(jià)函數(shù)做近似。代替，但需要滿足（在大多數(shù)情況下都滿足時(shí)，可以不用考慮）。代替，并滿足?？梢宰C明應(yīng)用這樣的估價(jià)函數(shù)是可以找到最短路徑的。

四、基于密集型區(qū)域八叉樹(shù)的A*算法改進(jìn)

由于使用八叉樹(shù)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的環(huán)境地圖擴(kuò)展步長(zhǎng)不一致，采用傳統(tǒng)的A*算法效率較低，因此對(duì)A*算法做了改進(jìn)，以適應(yīng)八叉樹(shù)結(jié)構(gòu)的搜索。改進(jìn)的辦法是從葉節(jié)點(diǎn)開(kāi)始搜索并為Open表設(shè)置兩個(gè)優(yōu)先隊(duì)列，命名為隊(duì)列1和隊(duì)列2（隊(duì)列1中存放的節(jié)點(diǎn)總是高于隊(duì)列2），在兩個(gè)隊(duì)列中分別存放相鄰層次的全部節(jié)點(diǎn)，層次越高的優(yōu)先級(jí)越高。通過(guò)這種分層次的搜索，也大大縮小了搜索的空間并縮短了搜索時(shí)間，這樣一來(lái)大大提高了搜索效率。

五、結(jié)束語(yǔ)

針對(duì)于復(fù)雜的3D環(huán)境，文章根據(jù)八叉樹(shù)適合虛擬場(chǎng)景劃分的特點(diǎn)，采用了一種適合密集型區(qū)域的八叉樹(shù)劃分方法，進(jìn)行場(chǎng)景劃分。為適合八叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，對(duì)A*算法做了改進(jìn)，引入優(yōu)先級(jí)隊(duì)列并采用了分層結(jié)構(gòu)，采用了從葉節(jié)點(diǎn)到根節(jié)點(diǎn)的搜索方法，規(guī)劃出了虛擬人行走的最優(yōu)路徑。

第9篇

關(guān)鍵詞：滾轉(zhuǎn)角控制 區(qū)域規(guī)避 路徑約束

中圖分類號(hào)：V279 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）04（b）-0057-02

當(dāng)前實(shí)時(shí)實(shí)現(xiàn)路徑規(guī)劃優(yōu)化設(shè)計(jì)的算法比較復(fù)雜而且要求具有很好的精確性，同時(shí)各個(gè)優(yōu)化方法也趨向混合，采用兩種或兩種以上的方法來(lái)研究，這樣結(jié)合了各個(gè)方法的優(yōu)點(diǎn)。由于高速飛行器通過(guò)改變航向角的方式來(lái)進(jìn)行轉(zhuǎn)彎，轉(zhuǎn)彎半徑比較大，影響飛行器機(jī)動(dòng)性，對(duì)行器變軌、避障和改變打擊角度，都有很大的影響。所以本文采用基于滾轉(zhuǎn)角控制轉(zhuǎn)彎的方法，保證了轉(zhuǎn)彎半徑盡可能的小，增加了飛行器的機(jī)動(dòng)性能。同時(shí)也要考慮飛行器的動(dòng)力學(xué)模型、氣動(dòng)、過(guò)載等物理參數(shù)的約束影響。

1 動(dòng)力學(xué)方程

本文直接選取某一飛行器，其三自由度質(zhì)點(diǎn)運(yùn)動(dòng)方程組：

（1）

（2）

（3）

（4）

（5）

（6）

再入軌道約束包括熱耗率、垂直加速度或者過(guò)載系數(shù)和動(dòng)壓。

≤ （7）

≤ （8）

≤ （9）

所有上面的約束都被認(rèn)為是硬性約束。對(duì)于有中等或者很大的升阻比的飛行器，平衡滑翔條件是另一個(gè)路徑約束。

≤0 （10）

其中是一個(gè)確定的滾轉(zhuǎn)角，該約束可以減少高度隨返回軌道的長(zhǎng)周期變化，考慮到軌跡發(fā)散，同時(shí)保證了充分的滾轉(zhuǎn)角裕度，這是個(gè)軟約束。

對(duì)于再入飛行器從再入段終點(diǎn)開(kāi)始，通過(guò)機(jī)動(dòng)飛行消耗能量，降低速度、高度，調(diào)整航向到自動(dòng)著陸起點(diǎn)為止的飛行段。要實(shí)施最終的能量管理（TAEM，terminal area energy management），此時(shí)由能量管理系統(tǒng)控制。在TAEM的接口處，軌跡必須有正確的條件以保證TAEM和進(jìn)場(chǎng)航線順利實(shí)施。典型的再入條件為：

（11）

在TAEM處的相對(duì)速度有靠近航向?qū)?zhǔn)錐（HAC，heading alignment cone）的切點(diǎn)決定，以保證獲得HAC在TAEM階段的切線。引入定義

（12）

其中是當(dāng)前飛行器在大圓中的位置與HAC的方位角。對(duì)于最終航向角的一個(gè)約束為：

≤ （13）

是提前設(shè)定的值。最終飛行器在TAEM接口處變?yōu)槠斤w姿態(tài)。在TAEM處過(guò)大的|σ|會(huì)導(dǎo)致TAEM控制有很長(zhǎng)的過(guò)度響應(yīng)。所以對(duì)于水平著陸的飛行器而言，最終在TAEM處的滾轉(zhuǎn)角約束為

≤ （14）

其中是一個(gè)確定的值，一般取在5～15 °范圍內(nèi)。

2 滾轉(zhuǎn)角約束設(shè)計(jì)

如果要基于滾轉(zhuǎn)角控制，就要把原來(lái)基于速度、高度的限制條件，轉(zhuǎn)化為基于滾轉(zhuǎn)角的限制條件。下面分兩部分解決這個(gè)問(wèn)題。

（1）初始下降最大可行滾轉(zhuǎn)角

根據(jù)入口界面給定的條件，取滾轉(zhuǎn)角為常值（符號(hào)由水平制導(dǎo)決定），對(duì)再入飛行器三自由度質(zhì)點(diǎn)運(yùn)動(dòng)方程組數(shù)值積分。當(dāng)在速度為Vpt時(shí)滿足下式，則停止積分。

≤ （15）

是一個(gè)很小的預(yù)置正數(shù)，其中

（16）

當(dāng)滾轉(zhuǎn)角為0時(shí)，準(zhǔn)平衡滑翔條件為：

（17）

（2）QEGC限制跟隨速度變化的滾轉(zhuǎn)角

在知道均衡滑翔條件后，微分方程可簡(jiǎn)化為代數(shù)方程。但是實(shí)際的航跡角是隨時(shí)間變化的，在大多數(shù)的情況下都是小振幅長(zhǎng)周期的振動(dòng)。我們可以得到

（18）

根據(jù)三個(gè)路徑約束在給定速度下共同確定的約束邊界，大氣密度ρ隨著高度被表示為v的函數(shù)，攻角α也可以表示為速度的函數(shù)。應(yīng)用可以確定出升力隨速度的變化關(guān)系。設(shè)定方程（5.24）中的r≈1，因?yàn)?。用替代掉L，可以求得最大的可行滾轉(zhuǎn)角。

（19）

QEGC給出了在保證其他約束條件下確定滾轉(zhuǎn)角的方法。滾轉(zhuǎn)角的范圍有如下形式：

≤≤ （20）

這樣對(duì)于復(fù)雜的約束條件只需簡(jiǎn)單的選擇滾轉(zhuǎn)角，就能夠保證所有的條件成立。綜合上面的內(nèi)容，可以得出滾轉(zhuǎn)角的在整個(gè)返回飛行中的取值如下：

（21）

在上式中Vpt是初始下降階段的末速度。在整個(gè)包絡(luò)可容許的滾轉(zhuǎn)角范圍為

≤≤ （22）

3 仿真實(shí)現(xiàn)

飛行器仿真對(duì)象選擇某類飛行器。其仿真參數(shù)如表1所示。

攻角α變化范圍為[0°，45°]；馬赫數(shù)Ma變化范圍為[3，25]；高度變化范圍為[0km，120km]。初始條件表2。

攻角α的規(guī)律如下，

（23）

當(dāng)時(shí)，當(dāng)時(shí)，。

大氣密度與高度的關(guān)系式：

（24）

其中，，，可以求得任意海拔高度的大氣密度值。

氣動(dòng)參數(shù)的確定：

記 如果，升力系數(shù)和阻力系數(shù)由下式求得：

（25）

滾轉(zhuǎn)角的選取：

我們綜合上面所講約束條件，可以設(shè)定的值為常值，這是符號(hào)隨時(shí)間變化，達(dá)到規(guī)避威脅的目的。這個(gè)也是整個(gè)算法的關(guān)鍵。

避障算法仿真，最終的位置是自由的，沒(méi)有約束。避開(kāi)障礙是最主要的目的。在選擇滾轉(zhuǎn)角時(shí)，要考慮到最小轉(zhuǎn)彎半徑的約束。實(shí)驗(yàn)中我們采用手動(dòng)的方式來(lái)生成避障軌跡，對(duì)于滾轉(zhuǎn)角取為±60°。具體的變化時(shí)刻，輸入的時(shí)間序列得到。滾轉(zhuǎn)角變化曲線。結(jié)果如圖1、2、3、4。

再入飛行器規(guī)劃路徑仿真結(jié)果表明基于滾轉(zhuǎn)角控制軌跡優(yōu)化方法保證了飛行器的快速性和機(jī)動(dòng)性，減小了轉(zhuǎn)彎半徑，提高了轉(zhuǎn)彎效率，可以快速、方便的達(dá)到規(guī)避障礙的目的。