引言：易發表網憑借豐富的文秘實踐，為您精心挑選了九篇路徑規劃范例。如需獲取更多原創內容，可隨時聯系我們的客服老師。

第1篇

關鍵詞 自動泊車；最佳泊車路徑

中圖分類號：TP182 文獻標識碼：A 文章編號：1671—7597（2013）041-184-01

經過一百二十多年的發展，汽車逐漸向小型化、智能化和安全化的方向發展。而隨著我國經濟的發展，汽車的需求量逐年遞增。于此同時帶來的問題是停車位需求量越來越大。而在國內，城市占道停車不但能有效的滿足停車位的需求，而且能有效緩解交通堵塞。但是，對于許多駕駛員而言，順式駐車通常是駕駛員考試中最令人擔心的一項，而且幾乎每個人都會在某些地點碰到這樣的事情。大城市停車空間有限，將汽車駛入狹小的空間已成為一項必備技能。 很少有不費一番周折就停好車的情況，特別是城市占道停車可能導致交通阻塞、神經疲憊和保險杠被撞彎，占道停車成為了一種痛苦的經歷。

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

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

1 自動泊車最佳路徑規劃

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

1.1 泊車危險點與安全圓

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

汽車行駛的軌跡為一個個圓弧構成的圓，由此可知，只需要其自動泊車軌跡與安全圓相離或者相切就不會與前方車輛相撞，而后對角點只需控制其倒車行程即可避免碰撞。

1.2 泊車關鍵圓的確定

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

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

1.3 泊車輔助圓的確定

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

另外，考慮到變換軌跡時，車輛是以車身前后軸中心的連線即軸距所構成的弦進入R2軌道，所以，需使R3向左平移，使得R3與R2相割所構成的弦與車身前后軸中心的連線即軸距長度相等。經過CAD模擬和測量可知需使R3向左平移452.3 mm，即可獲得R3的最終位置。

1.4 泊車路徑總結

如上分析和建模可知，找到了安全圓、關鍵圓和輔助圓，將其合并在一起，即可得到最佳泊車路徑如圖1所示。

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

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

2 泊車最佳路徑的驗證

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

參考文獻

[1]王芳成.自動平行泊車系統的研究[J].中國科技大學，2010.

[2]周健.嵌入式模糊自動泊車系統的研究[J].廣東工業大學，2011.

第2篇

關鍵詞：分層路網；拓撲結構提取；路徑規劃；A算法；二叉堆

0引言

路徑規劃是車載導航系統最重要的功能之一[1]。根據圖論中最短路徑理論，不管是最短路徑規劃、最短時間規劃還是最低消費規劃，都可以通過賦予圖中的邊以相應的權值來滿足用戶的不同需求。

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

本文試圖設計一種實用的分層路徑規劃算法。首先建立分層路網的拓撲結構，然后從搜索空間、搜索策略和數據結構三個方面進行研究，采用啟發式的A*算法作為主搜索方式，引入優先隊列二叉堆作為數據存儲結構，最后通過實驗驗證每項措施的改善效果。

1分層路網拓撲結構提取

第3篇

關鍵詞：移動機器人；路徑規劃技術；綜述

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

0 前言

移動機器人的實現涉及自動控制、智能、機械等多種學科。它通常被應用在醫療領域、工業領域等方面。從整體角度來講，移動機器人的應用促進了生產效率的顯著提升。路徑規劃技術是移動機器人的關鍵技術之一，研究該技術具有一定的現實意義。

1 路徑規劃技術的作用

將路徑規劃技術應用在移動機器人中，能夠產生的作用主要包含以下幾種：

（1）運動方面。路徑規劃技術的主要作用是其能夠保證移動機器人完成從起點到終點的運動。（2）障礙物方面。設計移動機器人的最終目的是將其應用在實際環境中，在實際環境下，移動機器人的運行路線中可能存在一定數量的障礙物，為了保證最終目的地的順利達到，需要利用路徑規劃技術實現對障礙物的有效避開[1]。（3）運行軌跡方面。對于移動機器人而言，除了實現障礙物躲避、達到最終目的地這兩種作用之外，應用路徑規劃技術還可以產生一定的優化運行軌跡作用。在移動機器人的使用過程中，在路徑規劃技術的作用下，機器人可以完成對最佳運行路線的判斷，進而更好地完成相應任務。

2 移動機器人路徑規劃技術綜述

移動機器人的路徑規劃技術主要包含以下幾種：

2.1 局部路徑規劃方面

在局部路徑規劃方面，能夠被應用在移動機器人中的技術主要包含以下幾種：

（1）神經網絡路徑規劃技術。從本質上講，可以將移動機器人的路徑規劃看成是空間到行為空間感知過程的一種映射，因此，可以利用神經網絡的方式將其表現出來。就神經網絡路徑規劃技術而言，首先需要將相關傳感器數據當成網絡輸入，并將網絡輸出看成是某固定場合中期望運動方向角增量。在這種情況下，原始樣本集則可以用不同選定位置對應的數據代替。為了保證樣本集數據的有效性，需要將原始樣本集中的沖突樣本數據以及重復樣本數據剔除掉。對最終樣本集應用模糊規則，實現神經網絡的有效訓練。當典型樣本學習完成之后，移動機器人對規則的掌握水平發生了顯著提升，進而使得移動機器人在產生智能性能的基礎上，順利完成相應運動[2]。

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

（3）遺傳路徑規劃技術。這種路徑規劃技術建立在自然遺傳機制等理論的基礎上。這種技術通過變異、選擇以及交叉對控制機構的正確計算程序進行合理編制，進而實現數學方式基礎上生物進化過程的合理模擬。當移動機器人的適應度函數為正數時，允許適應度函數具有不連續或不可導特點。由于這種路徑規劃技術不涉及梯度信息，因此其能夠更好地解決移動機器人在實際運動過程中遇到的問題。遺傳路徑規劃技術的應用優勢在于，它能夠實現跟蹤與規劃的同時進行，因此，遺傳路徑規劃技術通常被應用在具有時變特點的未知環境中。

2.2 全局路徑規劃方面

在該方面，可以被應用在移動機器人中的技術主要包含以下幾種：

（1）柵格路徑規劃技術。這種技術是指，在將實際工作環境分成許多包含二值信息的網格單元的基礎上，應用優化算法完成最佳路徑的規劃搜索。在這種規劃技術中，其網格單元通常是由八叉樹或者四叉樹的方式表示出來。在該技術的應用中，柵格的作用是完成相關環境信息的記錄。如果柵格中某位置的累計值相對較低，代表移動機器人可以從該位置通過；如果柵格中某個位置的累計值相對較高，則表示該位置存在障礙物，此時，移動機器人需要利用優化算法將該障礙物避開[4]。

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

（3）拓撲路徑規劃技術。這種規劃技術是指，將移動機器人的移動范圍，即規劃區域分成多個具有拓撲特征的子空間，然后利用不同子空間之間的連通性完成拓撲網絡的構建。當該網絡構建完成后，直接從網絡中找出能夠使得機器人順利從起點移動到終點的拓撲路徑，將所得的拓撲路徑作為參考依據完成幾何路徑的計算。這種規劃技術的劣勢主要表現為其拓撲網絡的構建過程較為復雜。但這種規劃技術可以實現移動機器人搜索空間的有效縮小[5]。

3 結論

路徑規劃技術主要分為局部規劃和全局規劃兩方面。這兩方面分別包含人工勢場路徑規劃技術以及神經網絡路徑規劃技術等。應用這些規劃技術之后，移動機器人可以在避開障礙物的基礎上，順利完成起點到終點最優運行軌跡的運動。

參考文獻：

[1]朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010（07）：961-967.

[2]張捍東，鄭睿，岑豫皖.移動機器人路徑規劃技術的現狀與展望[J].系統仿真學報，2005（02）：439-443.

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

[4]孔峰，陶金，謝超平.移動機器人路徑規劃技術研究[J].廣西工學院學報，2009（04）：70-74.

第4篇

摘 要：在查閱大量文獻的基礎上對多機器人路徑規劃的主要研究內容和研究現狀進行了分析和總結，討論了多機器人路徑規劃方法的評判標準，并闡述了研究遇到的瓶頸問題，展望了多機器人路徑規劃方法的發展趨勢。

關鍵詞：多機器人；路徑規劃；強化學習；評判準則

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 

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

機器人路徑規劃問題可以建模為一個帶約束的優化問題，其包括地理環境信息建模、路徑規劃、定位和避障等任務，它是移動機器人導航與控制的基礎。單個移動機器人路徑規劃研究一直是機器人研究的重點，且已經有許多成果[1~3]，例如在靜態環境中常見的有連接圖法、可視圖法、切線圖法、Voronoi圖法、自由空間法、柵格法、拓撲法、鏈接圖法、DempsterShafer證據理論建圖等；動態環境中常見的有粒子群算法、免疫算法、遺傳算法、神經網絡、蟻群算法、模擬退火算法、人工勢場法等。然而，多機器人路徑規劃研究比單個機器人路徑規劃要復雜得多，必須考慮多機器人系統中機器人之間的避碰機制、機器人之間的相互協作機制、通信機制等問題。

1 多機器人路徑規劃方法

單個機器人的路徑規劃是找出從起始點至終點的一條最短無碰路徑。多個機器人的路徑規劃側重考慮整個系統的最優路徑，如系統的總耗時間最少路徑或是系統總路徑最短等。從目前國內外的研究來看，在規劃多機器人路徑時，更多考慮的是多機器人之間的協調和合作式的路徑規劃。

目前國內外多機器人路徑規劃研究方法分為傳統方法、智能優化方法和其他方法三大類。其中傳統方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優化方法主要有遺傳算法、蟻群算法、免疫算法、神經網絡、強化學習等；其他方法主要有動態規劃、最優控制算法、模糊控制等。它們中的大部分都是從單個機器人路徑規劃方法擴展而來的。

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

2）智能優化方法 多機器人路徑規劃的智能優化方（算）法是隨著近年來智能計算發展而產生的一些新方法。其相對于傳統方法更加智能化，且日益成為國內外研究的重點。

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

孫樹棟等人[6，7]在這方面較早地展開了研究，提出的基于集中協調思想的一種混合遺傳算法來規劃多機器人路徑方法較好地解決了避障問題。但不足的是該方法必須建立環境地圖，在環境未知情況下的規劃沒有得到很好的解決；且規劃只能保證找到一個比較滿意的解，在求解全局最優解時仍有局限。

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

智能計算的另一種常見的方法——蟻群算法屬于隨機搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運動過程來實現尋優，通過螞蟻群體中各個體之間的相互作用，分布、并行地解決組合優化問題。該算法同樣比較適合解決多機器人的路徑規劃問題。

朱慶保[9]提出了在全局未知環境下多機器人運動螞蟻導航算法。該方法將全局目標點映射到機器人視野域邊界附近作為局部導航子目標，再由兩組螞蟻相互協作完成機器人視野域內局部最優路徑的搜索，然后在此基礎上進行與其他機器人的碰撞預測與避碰規劃。因此，機器人的前進路徑不斷被動態修改，從而在每條局部優化路徑引導下，使機器人沿一條全局優化的路徑到達目標點。但其不足是在動態不確定的環境中路徑規劃時間開銷劇增，而且機器人缺乏必要的學習，以至于整個機器人系統路徑難以是最優路徑。

強化學習[10，11] (又稱再激勵學習)是一種重要的機器學習方法。它是一種智能體從環境狀態到行為映射的學習，使得行為從環境中獲得積累獎賞值最大。其原理如圖1所示。

強化學習算法一般包含了兩個步驟：a）從當前學習循環的值函數確定新的行為策略；b）在新的行為策略指導下，通過所獲得的瞬時獎懲值對該策略進行評估。學習循環過程如下所示，直到值函數和策略收斂:

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

目前比較常見的強化學習方法有：Monte Carlo方法、動態規劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學習算法以及Dyna-Q算法等。其Q值函數迭代公式分別為

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′學習算法： Qπ(s，a)=∑Pαss′[Rass′+γVπ(s′)]

近年來，基于強化學習的路徑規劃日益成為國內外學者研究的熱點。M. J. Mataric[12]首次把強化學習引入到多機器人環境中。而基于強化學習的多機器人路徑規劃的優點主要體現在：無須建立精確的環境模型，簡化了智能體的編程；無須構建環境地圖；強化學習可以把路徑規劃、避碰、避障、協作等問題統一解決。

張芳等人[13]提出了基于再激勵協調避障路徑規劃方法，把再勵函數設計為基于行為分解的無模型非均勻結構，新的再勵函數結構使得學習速度得以提高且有較好的魯棒性。同時，證明了在路徑規劃中，機器人的趨向目標和避障行為密切相關，對反映各基本行為的再勵函數取加權和來表示總的再勵函數要優于取直接和的表示方式，也反映了再勵函數設計得合理與否及其確切程度將影響再勵學習的收斂速度。王醒策等人[14]在動態編隊的強化學習算法方面展開了研究。宋一然[15]則提出了分段再勵函數的強化學習方法進行路徑規劃。其缺點是學習次數較多、效率不高，當機器人數目增加時，它有可能面臨維數災難的困難。所以，基于強化學習的路徑規劃在多機器人環境下的學習將變得比較困難，需要對傳統的強化學習加以優化，如基于人工神經網絡的強化學習[16]等。

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

孫茂相等人[18]提出了最優控制與智能決策相結合的多移動機器人路徑規劃方法。其首先構造一個以各機器人最優運動狀態數據庫為核心的實時專家系統， 在離線狀態下完成; 然后各機器人在此專家系統的支持下， 以最優規劃策略為基礎， 采用速度遷移算法， 自主決定其控制。該方法擁有較好的穩定性與復雜度。焦立男等人[19]提出的基于局部傳感和通信的多機器人運動規劃框架較好地解決了多機器人路徑規劃在局部在線規劃的系統框架問題。沈捷等人[20]提出了保持隊形的多移動機器人路徑規劃。以基于行為的導航算法為基礎，把機器人隊列的運動過程劃分為正常運動、避障和恢復隊形三個階段。在避障階段，引入虛擬機器人使隊形保持部分完整;當隊形被嚴重打亂時，規劃機器人的局部目標位姿使隊列快速恢復隊形。其算法重點為避障機器人進入避障狀態，暫時脫離隊列，并以虛擬機器人代替避障機器人。

2 多機器人避碰和避障

避障和避碰是多機器人路徑規劃研究中需要考慮的重點問題之一。避障和避碰主要討論的內容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規劃中常見的多機器人避障方法[21]有主從控制法、動態優先法（建立在機器人之間的通信協商上）、交通規則法、速率調整法，以及障礙物膨脹法、基于人工勢場的方法等。

目前國內外對于多機器人避障展開的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎，擴充并完善了路徑/速度分解方案來協調多機器人，設立集中管理agent進行整體規劃，為每個機器人規劃路徑；并根據優先級規則對運動特征進行分布式規劃以避免機器人間的沖突。周明等人[23]提出分布式智能避撞規劃系統，將原來比較復雜的大系統轉換為相對簡單的子系統問題，由各智能機器人依據任務要求和環境變化， 獨立調整自身運動狀態，完成任務的分布式智能決策體系結構。任炏等人[24]提出了基于過程獎賞和優先掃除的強化學習多機器人系統的沖突消解方法。該算法能夠顯著減少沖突，避免死鎖，提高了系統整體性能。歐錦軍等人[25]提出了通過調整機器人的運動速度實現多機器人避碰，將避碰問題轉換為高維線性空間的優化問題， 并進一步將其轉換為線性方程的求解。該方法的缺點是系統的復雜度較高、計算量太大。

人工勢場方法的特點是計算簡潔、實時性強、便于數學描述，且適合于多自由度機器人環境，但容易產生抖動和陷入局部極小。為了克服其缺點，景興建等人[26]提出了人工協調場的方法，在傳統排斥力場中增加一個協調力，并將吸引力、排斥力和協調力與局部環境下機器人的運動狀態和運動要求結合起來，有效地保證機器人的安全性，提高機器人在復雜動態環境下行為決策的準確性和魯棒性。

3 多機器人協作和協調機制

多機器人間的運動協調[27~31]是多機器人路徑規劃的關鍵，也是多機器人與單機器人路徑規劃相區別的根本所在。多機器人系統在復雜動態實時環境下，由于受到時間、資源及任務要求的約束，需要在有限時間、資源的情況下進行資源分配、任務調配、沖突解決等協調合作問題，而機器人間的協調與協作，能夠大大地提高整個系統的效率和魯棒性，成為系統完成控制或解決任務的關鍵。

目前已有的協調方式分為集中式、分布式和混合式三種。在集中式協調中，集中規劃器詳細地規劃出每個機器人的動作，通常的做法是將多個機器人看做一個多自由度的機器人進行規劃；而分布式協調規劃中，機器人之間進行合作，將一個任務分成多個子任務，根據各自的特點完成不同的子任務，從而共同完成總任務；混合式協調是集中式和分布式混合在一起的形式。

多機器人間典型的協調方法[32]有合同網協議[33]、黑板模型、結果共享的協同方法、市場機制。近年來強化學習在多機器人協作方面也得到很好的應用，陳雪江[32]在基于強化學習的多機器人協作方面展開了研究，提出了多智能體協作的兩層強化學習方法來求解在多智能體完全協作、有通信情況下的協作問題。其主要通過在單個智能體中構筑兩層強化學習單元來實現：第一層強化學習單元負責學習智能體的聯合任務協作策略；第二層強化學習單元負責學習在本智能體看來是最有效的行動策略。陳偉等人[34]提出基于多目標決策理論的多機器人協調方法；通過對環境的拓撲建模，從基于行為的機器人學角度出發，對任務進行分解并設計目標行為，以多目標行為決策理論作為決策支持，從而達到多機器人運動協調的目的。

4 多機器人路徑規劃方(算)法的判優準則

通常評價機器人路徑規劃方(算)法的標準文獻[35]有正確性、時間/空間復雜度、并行性、可靠性、擴展性、魯棒性和學習。而多機器人的路徑規劃除了以上一些衡量標準之外，還需要考慮整個系統的最優化以及機器人間的協調性。

1)正確性 是分析算法的最基本的原則之一。一般來說算法的正確性是指:在給定有效的輸入數據后，算法經過有窮時間的計算能給出正確的答案。但在多機器人路徑規劃算法中，正確性主要指:路徑規劃算法要生成多個機器人協調運動的無碰安全路徑;這條路徑是優化的。

2)安全性 一般指多機器人所生成的各路徑中節點與障礙物有一定的距離。但在實際的應用背景下，有人認為安全性可以從兩個方面來理解：a）狹義地講，它就是機器人在行走過程中所做的功。在一定的條件下，它與路徑長度準則是一致的。b）廣義地講，它是各種優化條件加權綜合而得到的結果。

3)復雜度 一個算法的復雜性高低體現在該算法所需要的計算機資源的多少上面。所需要的資源越多，該算法的復雜性越高；反之，所需要的資源越少，該算法的復雜性就越低。算法的復雜性包括時間復雜度和空間復雜度。

在多機器人的路徑規劃算法中，算法的復雜度分析顯得尤為重要。一般地，單機器人路徑規劃算法的時空復雜度已經頗高，它們的數量級至少是O(n2)；多機器人的路徑規劃算法不僅是m-O(n2)(即m個機器人路徑規劃簡單地疊加)，它們之間還存在著對運動空間競爭的沖突，面對不斷變化的沖突的協調需要花費大量的時間和空間。通常多機器人的路徑規劃算法與機器人的個數呈指數關系O(km×n2)（k為常數）。這對多機器人路徑規劃算法的時間/空間復雜度控制是一個很嚴峻的考驗。

4)并行性 算法的并行性從算法設計、編寫程序、編譯和運行等多個不同的層次來體現。路徑規劃過程需要大量的計算，當處理的環境比較復雜，機器人工作的環境過于緊湊，尤其是機器人數量很多時，算法的時間/空間復雜度勢必會成為算法效率的關鍵。因此，在算法設計和運行上的并行性是通常考慮的方法。對多個機器人的路徑規劃盡量采用分布式多進程的規劃機制，以實現每個機器人路徑規劃的并行性。

5)可靠性 把多個機器人及其工作環境看成是一個系統，多機器人處于它們各自的起始點時，稱該系統處于初始狀態；當它們處于各自的目標點時，稱該系統處于目標狀態。多機器人的路徑規劃就是在該系統的這兩個狀態間建立一串合理的狀態變遷。這一狀態變遷過程可能會歷經許多狀態，如果在狀態變遷過程中，路徑規劃算法控制不好各狀態間的轉移關系，就會導致系統紊亂，出現機器人間的碰撞、找不到路徑等惡性后果，使任務失敗。所以這就對算法的可靠性和完備性提出了挑戰。為了很好地克服這一困難，需要對系統的各種可能狀態建模，分析它們相互間的關系，建立有限狀態自動機模型或Petri網模型，并以此為指導，按照軟件工程的思想，構造恰當的算法輸入來對算法的可靠性進行檢驗。

6)可擴展性 在多機器人的路徑規劃算法中，可擴展性主要是指一種路徑規劃算法在邏輯上，或者說在實現上能否容易地從2D空間擴展到3D空間，從低自由度擴展到高自由度，從較少的機器人數到更多的機器人數。可擴展性在各種路徑規劃算法之間沒有一種量的比較標準，只能從實際的具體情況出發、從對環境描述的適宜程度出發、從算法解決這一問題的復雜度出發、從算法本身的自適應出發等來考慮。

7)魯棒性和學習 魯棒性對于多機器人系統非常重要。因為許多應用，如路徑規劃要求連續的作業、系統中的單個機器人出現故障或被破壞，要求機器人利用剩余的資源仍然能夠完成任務。學習是在線適應特定的任務。雖然通用的系統非常有用，但將它用于特定應用上時，通常需要調整一些參數。具有在線調整相關參數的能力是非常吸引人的，這在將體系結構轉移到其他應用時可以節省許多工作。尤其是多機器人系統中機器人的自身學習和相互間的學習能夠大大提高整個系統的效率和系統的穩定性。

8）最優化 對動態環境有優化反應。由于有些應用領域涉及的是動態的環境條件，具有根據條件優化系統的反應能力成為能否成功的關鍵。

5 結束語

綜上所述，國內外研究者在多機器人路徑規劃取得了一些成果，但是在協作、學習、通信機制等方面仍面臨很大的困難和不足。如何進一步提高機器人間的協調性，增強機器人自身以及相互間的學習以提高多機器人系統的效率和魯棒性都有待深入研究。近年來無線通信技術得到長足發展，但在目前的技術條件下，在多機器人系統中實現所有機器人之間的點對點實時通信還有較大困難，這也是大多數多機器人系統仍然采用集中通信方式的主要原因。因此，如何降低多機器人系統對通信速度的依賴程度也是一個非常重要的問題。

總之，多機器人路徑規劃設計和實現是一項極其復雜的系統工程，展望其能在結合計算智能方法，如差分進化、遺傳算法、粒子群算法、免疫算法、模糊邏輯算法、BP網絡、人工勢場的改進、模擬退火和環境建模方法等方面取得新的突破。

參考文獻：

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

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

[3]譚民，王碩，曹志強.多機器人系統[M].北京：清華大學出版社，2005：6-81.

[4]薄喜柱，洪炳熔.動態環境下多移動機器人路徑規劃的一種新方法[J].機器人，2001，23（5）：407-410.

[5]顧國昌，李亞波.基于總體勢減小的動態調度技術解決多機器人的路徑規劃[J].機器人，2001，23（2）：171-174.

[6]孫樹棟，林茂.基于遺傳算法的多移動機器人協調路徑規劃[J].自動化學報，2000，26（5）：672-676.

[7]周明，孫樹棟，彭炎午.基于遺傳算法的多機器人系統集中協調式路徑規劃[J].航空學報，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]朱慶保.全局未知環境下多機器人運動螞蟻導航算法[J].軟件學報，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]高陽，陳世福，陸鑫.強化學習研究綜述[J].自動化學報，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]張芳，顏國正，林良明.基于再勵學習的多移動機器人協調避障路徑規劃方法[J].計算機工程與應用，2003，39（3）：80-83.

[14]王醒策，張汝波，顧國昌.多機器人動態編隊的強化學習算法研究[J].計算機研究與發展，2003，40（10）：1444-1450.

[15]宋一然.基于強化學習的多機器人路徑規劃方法[J].莆田學院學報，2006，13（2）：38-41.

[16]韓學東，洪炳熔.基于人工神經網絡的多機器人協作學習研究[J].計算機工程與設計，2002，23（6）：1-3.

[17]唐振民，趙春霞，楊靜宇，等.基于動態規劃思想的多機器人路徑規劃[J].南京理工大學學報，2003，27（5）：610-615.

[18]孫茂相，周明，王艷紅，等.多移動機器人實時最優運動規劃[J].控制與決策，1998，

13（2）：125-130.

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

[20]沈捷，費樹岷，鄭波.多移動機器人保持隊形路徑規劃[J].東南大學學報，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].計算機工程，2003，29(17):

79-81，104.

[23]周明，孫茂相，尹朝萬，等.多移動機器人分布式智能避撞規劃系統[J].機器人，1999，21（2）：139-143.

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

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

[26]景興建，王越超，談大龍.基于人工協調場的多移動機器人實時協調避碰規劃[J].控制理論與應用，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]薛宏濤，葉媛媛，沈林成，等.多智能體系統體系結構及協調機制研究綜述[J].機器人，2001，23（1）：85-90.

[30]周風余，李貽斌，宋銳，等.基于混合式多智能體系統的協作多機器人系統研究[J].山東大學學報:工學版，2005，35(1):82-87.

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

[32]陳雪江.基于強化學習的多機器人協作機制研究[D].杭州：浙江工業大學，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篇

關鍵詞：企業物資；配送；車輛路徑問題；路徑規劃；里程節約法

一、前言

隨著信息技術在現代企業中的廣泛應用和高速發展，企業信息化程度大幅提高，企業的許多革命性的創新成果得益于此。在激烈的市場競爭中，倉儲配送和信息技術的有機結合為企業帶來了新的機遇，建設智慧倉儲網絡的理念應運而生。而配送作為銜接各個物流節點的關鍵流程，使倉儲網絡形成為一個系統性的整體，保證了物資的正常供應。優化配送車輛路徑能提高配送效率，降低配送成本，并提升配送準確性。

物資公司作為公司的專業分公司，負責管理在上海區域所有工程及運維檢修物資的供應。工程項目物資的供應分為供應商直送現場和倉庫供應現場兩種類型。其中，供應商直送現場為一次配送，關鍵點在于供應計劃與供應商的有效銜接與調度協同；而利用公司倉儲配送網絡，通過中心庫向各周轉庫配送以供應現場物資需求的過程為二次配送。合理二次配送車輛路徑規劃與實施，能提高后續工程建設、運維檢修及應急搶修的需求響應速度，增強物資供應的計劃性和準確性，可有效提升物資供應管理水平。

二、車輛路徑問題定義

車輛路徑問題是指存在幾個物資需求方，各有一定數量的物資需求，由一個配送中心提供物資，并安排一個車隊配送物資。為此需要規劃合理的行車路線以使他們的物資需求得到滿足，且能在一定的約束條件下，達到路程最短或耗時最少的目標。

公司有十二個周轉庫，當周轉庫內某種物資數量低于安全庫存時，由中心庫提供物資進行補庫。由于工程項目對響應速度要求較高，當需要對多個周轉庫進行補庫時，必須綜合周轉庫的地理位置、物資需求量、車輛的運載量、配送次數等，設計出合理的車輛配送路徑。

三、配送路徑規劃意義

1.避免交叉運輸

中心庫車輛配送路徑規劃，將原先零散配送的物資進行整合后，以合理的配送路徑集中配送，避免了交叉運輸的情況，縮短了總配送距離，降低了運輸成本。

2.推進節能環保

車輛配送路徑優化在滿足各周轉庫的物資需求的前提下，以縮短配送車輛的總行駛距離為目標，能提高能源利用效率，推動公司更積極地承擔節能環保的社會責任。

四、配送路徑規劃過程

1.組織結構

物資公司倉儲配送網絡包括了集中的物資調配中心、一個中心庫以及十二個周轉庫。

（1）物資調配中心作為信息匯集、指令的中心，實時獲取中心庫和周轉庫內庫存物資數量、物資需求數量等信息，并根據這些信息判斷是否需要補庫。

（2）如果周轉庫需要補庫，物資調配中心發送補庫指令給中心庫。

（3）中心庫綜合需補庫的周轉庫數量、地理位置及物資需求量等，規劃所需的車輛數、配送路徑等信息，將物資配送至周轉庫。

2.車輛路徑問題描述

對于物資倉儲配送網絡，配送車輛路徑問題可以描述為，十二個周轉庫的位置固定且各有一定的需求量，中心庫用多輛載重量固定的汽車進行配送，要求合理安排汽車路線以使總距離最短，并能滿足以下條件：

（1）每個周轉庫的物資需求到能滿足；

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

（3）每條配送路徑上各周轉庫的需求量總和不能超過汽車載重量。

3.車輛路徑規劃

將中心庫及十二個周轉庫構成的13個的節點兩兩連線，共有C132=78種組合，即這13個倉庫中任意兩個倉庫間的路徑共計78條。利用Google、百度等電子地圖軟件，將兩個倉庫分別作為起點和終點，搜索出這78條路線以及之間的行駛距離。以字母O表示中心庫，字母A至L表示十二個周轉庫。當有多個周轉庫需要補庫時，配送路徑確定步驟如下：

（1）確定各個周轉庫需要的物資數量；

（2）與汽車載重量進行比較，確定需要的汽車數量；

（3）根據各周轉庫的需求量，運用里程節約法，就近的倉庫由同一汽車配送，同時避免交叉運輸的情況，形成配送路徑；

（4）根據實時路況，對配送路徑進行一定調整，避免高峰期路段擁堵導致無法及時配送。

由于從實際情況考慮，為減少最后配送到的幾個倉庫的等待時間，在12個周轉庫中按地理位置分為兩塊區域，在郊環附近的7個倉庫為一個配送區域，郊環線以內的4個倉庫和崇明區域為一個配送區域。

以郊環線附近7個倉庫的配送為例，如下圖所示，每汽車載重量為5噸，A至G共7個周轉庫需中心庫O配送物資，直線上的數字為距離，括號內的為對應的周轉庫的物資需求量。

4.路徑信息

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

五、結語

本文綜合各周轉庫地理位置、需求數量、汽車運載量等方面，運用里程節約法規劃出車輛配送路徑。車輛配送路徑規劃將對原先粗放式的配送方式進行優化，積極配合政府及上級公司對節能環保提出的要求，在滿足各倉庫需求的前提下縮短總配送距離，提高物資配送效率，降低配送成本。物資公司后續將逐步加強自動化和信息化建設，推進倉儲網絡各類信息的實時共享、獲取、分析和處理，運用先進信息技術提高配送準確性和效率效益，確保智慧倉儲網絡的配送脈絡高效穩定，構建一個現代化、智慧化、特色化的倉儲配送體系。

參考文獻：

[1]張玲，王朝霞.物流配送路徑優化的模型與求解[J].商場現代化，2006.11.

第6篇

關鍵詞:路徑規劃; 地標; 預處理; 層次縮減算法; 三角啟發算法

中圖分類號: TP312.8文獻標志碼: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 引言

對于大規模交通網絡，Dijkstra算法［1］需要花費長時間進行計算，不符合實時性的要求。目前相關的優化算法有啟發式算法和預處理算法兩種。啟發式算法(A*)［2］使用合適的啟發函數減少搜索空間以獲得較高的查詢效率，啟發函數會直接影響最后的計算結果；預處理算法使用點或邊標記法、快捷路徑法、區塊分割法等對網絡中的邊進行合并和標記以迅速求出最短路徑，但需要大量的輔助存儲空間。

根據實際交通網絡的特點：在主干道上通過的最短路徑最多，存在重要的邊和點；對于長距離的路徑規劃，出發點和目標點的中間節點有可能成為最短路徑上的點。本文以A*算法為基礎，將地圖中關鍵的節點選為地標，并將地標作為啟發函數的啟發參數來求得路徑規劃的合理解。為提高長距離路徑規劃的查詢效率，使用分段處理的思想將查詢分割為若干子查詢，并給出相關的優化方法。

1 相關研究

對于靜態網絡圖G=(V,E)，大多數優化算法需要經過充分的預處理。三角啟發算法（A* Landmarks Triangle，ATL）［3］39算法將圖G按中心點劃分為若干區域，每個區域選取一個標志點(LandMark)，根據三角不等式使搜索路徑趨向于目標節點，大幅度減少搜索空間，從而提高查詢效率。

文獻［4］提出一種分層合并的預處理算法CH，對原始圖G的邊進行迭代合并，產生一組生成圖{G1,G2,…,Gh}，生成圖和原始圖的邊使用標號對應，以便求解后還原原始路徑。這種預處理算法非常消耗存儲空間，不適合于大規模網絡，但是可以快速求出最短路徑。經過預處理的CH算法時間復雜度可以達到O（N log H），N為合并圖的平均邊數，H為合并圖的層數。

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

Bauer等［7］提出一種混合算法SHARC，對CH和ARC.Flags進行了多項改進，提出分層標記的思想，可以縮短預處理時間和減少額外空間。分層的ARC.Flags提供搜索方向，CH加速區域內的路徑搜索，在單向搜索環境中SHARC可以提供非常高效的精確最短路徑。經過修改的SHARC可以進行時變最短路徑問題的搜索，文獻［8］對此有詳細描述。

2 地標導向的啟發式算法

2.1 地標的選取

交通網絡圖一般擁有層次關系，鄉鎮與城市之間有干道相連，城市與城市之間有高速相連，在路徑規劃中這些連接線路被通過的次數最多。對于具有這一特點的圖G，地標集的定義如下：

設r為一個搜索半徑，點u為中心，2r為半徑的G的子圖記為Bu,2r，選取滿足以下條件的最短路徑P，PBu,2r并且Len(P)>r（Len(P)為P的歐拉長度）；如果存在點集Cu對于所有的P滿足Cu P，則Cu為Bu,2r的地標集，并且設h=max(|Cu|)為G的地標度數（|Cu|為Cu的節點個數）。顯然h越大地標對最短路徑的貢獻越大，在路徑規劃時可利用的地標節點越多。

計算大規模交通網絡的地標集，采用以下幾個步驟。

1)選擇節點密集型的區域，將圖分割為搜索半徑為r的不同區域。在實驗中會討論r在不同取值時地標集獲取情況以及啟發式算法的查詢速度。

2)對于區域Bu,2r，使用CH算法進行預處理以便于快速計算最短路徑。

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

4)對P中所有的路徑取交集獲得地標集Cu。

2.2 啟發式算法設計

本文將地標節點作為啟發式搜索的啟發節點，求解思想如下。

對于點對（s,t）如果屬于同一分割區域，由于使用了CH算法進行預處理，可以快速求得精確的最短路徑。如果（s,t）屬于不同區域則使用以下啟發式規則。

1)從s所在區域的地標集中選取距離t最近的地標c作為下一跳的啟發節點，s到c的最短路徑使用CH求得。如果s所在區域沒有地標集，則設c=s，轉向第2）步。

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

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

4)對最短路徑進行合并輸出。

CH算法在區域內進行快速搜索，同時對于不同區域采用ALT算法控制搜索方向，使搜索始終沿著目標進行，這是一種分段搜索的思想，對于長距離的最短路徑求解由于有地標集提供搜索參考，搜索線路比ALT更加精確，耗時更短。

2.3 算法分析與優化

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

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

1)使用前向搜索計算(s,t)的最短路徑獲取一個啟發點cf;

2)使用后向搜索計算(t,s)的最短路徑獲取一個啟發點cb;

3)設s=cf , t=cb 重復1)，2)兩步，最終搜索會在同一個節點相遇;

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

對于地標集，可以使用TNR［10］的思想進行最短路徑索引，TNR計算并存儲所有地標之間的最短路徑并存儲在一張|C| × |C|的表格中，其中|C|為圖G中地標節點的個數。如果s和t分別在不同的分割區域，并且存在地標，則根據索引表查詢地標之間的最短路徑，否則執行啟發式搜索。對地標的查詢可以在常數時間之內完成。大規模網絡圖使用CHALT+TNR算法可以在犧牲少量存儲空間的前提下提供最優的性能。

3 實驗

使用Intel Pentium CPU 2.5GHz、2GB RAM完成本算法和其他算法的比較實驗，算法采用C++編寫。實驗數據選用北京市交通路網（包含81534個路段和34219個節點）。最短路徑的度量標準為距離最短，在實驗中使用歐拉距離完成路徑計算。

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

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

4 結語

為解決大規模長距離的最短路徑規劃問題，本文根據分

段計算的思想，使用地標集將啟發式搜索限制在靠近最短路徑的方向。實驗證明CHALT算法在保證預處理和查詢效率的基礎上，得出更合理的計算結果，優化后的算法查詢效率更高，可以應用在大型交通網絡中。下一步研究方向為以地標為導向的啟發式算法在離散變權網絡中的應用。

參考文獻:

［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篇

關鍵詞： 增維啟發式搜索； 智能車； 路徑規劃； 高效率； 平衡

中圖分類號： TP311 文獻標識碼：A 文章編號：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 引言

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

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

為了展示該算法的性能，本文進行了仿真實驗。在實驗中，智能無人車剛剛進入一個停車場，需要在目標停車位泊車。實驗結果表明，相比傳統的高維度啟發式搜索算法，該算法減少了超過87%的搜索狀態，運行性能提高了近10倍。

2 研究現狀及文獻綜述

從20世紀70年代開始，歐美的西方國家開始無人駕駛汽車方面的研究工作，并在智能無人車的控制和商用化方面取得一定進展。在汽車工業非常發達的德國，各大汽車公司都資助或者聯合高等院校以開發可在普通道路上行駛的智能無人車。目前，歐盟已啟動一個名叫CyberCars的智能無人車項目，以推動智能無人車的研究和各國間智能無人車技術的信息共享。

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

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

文獻[13][14][15][16]給出了2007年美國DARPA智能無人車比賽麻省理工學院（MIT）參賽智能無人車的整體架構，MIT智能無人車的軌跡生成算法，主要是用RRT算法生成可行路徑，并對該路徑進行平滑，以此為基礎生成智能無人車運動軌跡。

文獻[17][18][19][20][21][22]主要闡述了狀態空間搜索算法，通過估價函數進行啟發式搜索以及狀態空間搜索剪枝。文獻[23]提出了ARA*（Anytime A*）算法，對短時間間隔內連續反復用A*搜素算法進行空間狀態搜索這一類狀態空間搜索應用場景進行優化。

3 增維啟發式搜索算法

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

3.1 第一階段搜索

在這一階段，因為我們只考慮二維狀態空間（x， y），即車輛的地理坐標。如果將狀態空間離散化，這一搜索問題會退化成一個圖論的最短路問題。雖然圖論的最短路問題有很多經典成熟的算法。但是在這里還是有一些值得討論的問題。

3.1.1 柵格隨機化

一般地，在執行最短路算法之前，會把狀態空間離散化成柵格，然后對柵格做4聯通或者8聯通處理，但是這種離散化方法會使最短路失去最優解，如圖1a、1c所示。

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

a b c

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

3.1.2 最短路算法

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

最短路的經典算法是堆優化的Dijkstra算法，該算法時間復雜度為 [O（eloge）]，其中[e]代表離散化后邊的數量，然而在稀疏圖中，SPFA算法的實際時間復雜度約為[O（e）]，在18隨機聯通結構的圖中效率比價高，因而在本階段中，我們采用SPFA算法計算單源最短路。

3.2 第二階段搜索

在第二階段的搜索中，我們選取第一階段結果，幾何最短路上的一個點來作為目標點，在搜索狀態加入車輛的航向角θ，以及行駛速度v，在搜索中充分考慮車輛動力學模型，搜索出一條高精度可執行的車輛行駛軌跡。

3.2.1 啟發函數

在啟發式搜索過程中，一個強力有效的啟發式函數對搜索效率來說至關重要。啟發式函數不僅為搜索的實際代價提供了一個下界，同時也是實際代價的一個良好估算，可以引導搜索往正確的方向擴展，并且實現搜索剪枝，在第二階段的搜索中，使用以下啟發式函數。

動力學約束無障礙啟發函數，[hnh（x，y，θ，v）]，該函數忽略障礙物信息，考慮車輛動力學模型，在此條件下求出最優的路徑。這一啟發式函數因為忽略了障礙物信息，只考慮動力學模型，所以可以離線計算、存儲，在真實路徑規劃的過程中查詢，計算速度極快。該函數極大的消除接近目標點航向角錯誤的搜索分支。

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

結合二者，選取啟發函數[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 為狀態[（x， y， θ， v）]的估價函數， g為當前搜索狀態[（x， y， θ， v）]的實際代價， [F]為實際搜索代價。

在該啟發函數的引導下，第二階段啟發式搜索可以高效地計算出四維高精度路徑。

4 仿真實驗以及實驗結果

為了展示該算法的性能，本文進行了仿真實驗。在實驗中，智能無人車剛剛進入一停車場，需要在目標停車位泊車。實驗環境為Ubuntu 12.04 Linux系統，Intel i5處理器， 8GB內存。停車場大小為長80米寬50米，柵格離散化精度為10厘米，車輛采用72個不同的航向角，同時采用兩個速度，最大的前向速度以及最大的后向速度。

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

a

b

c

d

表1 算法性能比^

[ 階段 樸素四維啟發式搜索 增維啟發式搜索 搜索狀態數量 第一階段 400000 第二階段 10808634 408773 共計 10808634 808773 算法運行時間

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

如圖1b，對于每一次路徑規劃，增維啟發式搜索算法可以有效地減少搜索狀態的數量，因為高維度高精度部分的搜索集中在離車輛較近的區域，而從全局的角度，二維的幾何最短路依舊引導著軌跡往正確的方向。相比之下樸素的四維啟發式搜索搜索量極大（圖2b）。從輸出軌跡上看，兩者的輸出軌跡質量幾乎相同（圖2c、2d）。

5 結論

本文展示了增維啟發式搜索路徑規劃算法。該算法分為兩階段。第一階段在全局考慮二維的搜索狀態空間，得出起始點到目標位置的幾何最短路。在第一階段幾何最短路基礎上選取一個目標點作為第二階段目標狀態空間，進而得到考慮了車輛動力學模型、四維的高精度可執行軌跡。仿真實驗結果表明，在現實場景下，該算法極大地減少了搜索狀態數量，提高了算法執行效率，同時輸出高質量的智能無人車行駛軌跡。

參考文獻：

[1] 楊明.無人駕駛車輛研究綜述與展望[J]..哈爾濱工業大學學報，2006，38（增刊）：1259-1262.

[2] 孫振平.自主駕駛汽車智能控制系統[D].國防科技大學，2004.

[3] 楊森森.基于GPS/INS/激光雷達的無人車組合導航[D].上海交通大學碩士學位論文，2013.

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

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

[6] 曹玉芬，張國斌.美國無人地面車輛計劃[J].國外坦克，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篇

【關鍵詞】虛擬場景；路經規劃；八叉樹；A*算法

中圖分類號：TP39文獻標識碼A文章編號1006-0278（2013）06-172-01

一、引言

隨著虛擬現實技術的日益成熟，只有景色、建筑物等一般視景信息的虛擬場景已不能滿足人們的視覺需求，迫切需求一個有生命的對象引入到虛擬場景中，增加瀏覽者的沉浸感。虛擬場景中虛擬人的路徑規劃是虛擬現實研究中的一項關鍵技術。目前，研究者們已經把研究的重心放在如何為虛擬人規劃出一條行走的最優路徑，使虛擬人的路徑導航更具有真實感和可信度。

由于虛擬環境中的模型多由三角面網格組成，通過使用基于空間多層次劃分的八叉樹方法，充分發揮了其空間劃分的優勢，加快了場景的渲染速度，減少了確定對象的處理時間以及存儲空間①。

文章采用八叉樹和A*算法相結合的方法，對路徑進行規劃，并對A*算法做了改進，以適應八叉樹的存儲結構。

二、密集型區域八叉樹劃分算法

八叉樹是由四叉樹推廣到三維空間而形成的一種三維柵格數據結構，它作為一種場景組織方法，廣泛應用于虛擬現實系統，可顯著減少對場景中多邊形進行排序的時間。

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

密集型區域八叉樹劃分方法的算法描述如下：

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

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

步驟3如果每個子空間內存在物體的屬性不相同或未達到規定的限差，則重新從步驟1開始進行劃分。否則，劃分結束，并對劃分后的每一個結點記錄下結點編號、劃分標志、結點在頂點樹中的深度以及它所含的景物面片表的入口指針。

三、A*算法

A*算法是建立在典型的Dijkstra算法上的，是由Hart，Nilsson，Raphael等人首先提出的。該算法的創新之處在于選擇下一個被檢查的節點時引入了已知的全局信息，對當前節點距終點的距離做出估計，作為評價該節點處于最優路線上的可能性的量度，這樣就可以首先搜索可能性較大的節點，從而提高了搜索過程的效率。

下面是對A*算法的介紹，我們首先來介紹一下啟發式搜索中的估計函數。因為在啟發式搜索中，對位置的估價是十分重要的。估價函數的表示如下：

其中是節點的估價函數，是已知的，指在狀態空間中從初始節點到節點的實際代價；是從結點到目標節點最佳路徑的估計代價，它體現了搜索的啟發信息，啟發信息決定著算法的啟發能力。啟發信息越多，估價函數就越好，即約束條件越多，則排除的節點就越多，說明這個算法越好。這種做法存在一個平衡的問題，也會使算法的準確性下降。具體的說，代表了搜索的廣度優先趨勢，當時，可以省略，這樣就提高了搜索效率。

A*算法是一個可采納的最好優先算法。A*算法的估價函數可表示為：

這里，是估價函數，是起點到終點的最短路徑值，是到目標的最短路經啟發值。由于這個其實是無法預先知道的，所以我們用前面的估價函數做近似。代替，但需要滿足（在大多數情況下都滿足時，可以不用考慮）。代替，并滿足。可以證明應用這樣的估價函數是可以找到最短路徑的。

四、基于密集型區域八叉樹的A*算法改進

由于使用八叉樹存儲結構存儲的環境地圖擴展步長不一致，采用傳統的A*算法效率較低，因此對A*算法做了改進，以適應八叉樹結構的搜索。改進的辦法是從葉節點開始搜索并為Open表設置兩個優先隊列，命名為隊列1和隊列2（隊列1中存放的節點總是高于隊列2），在兩個隊列中分別存放相鄰層次的全部節點，層次越高的優先級越高。通過這種分層次的搜索，也大大縮小了搜索的空間并縮短了搜索時間，這樣一來大大提高了搜索效率。

五、結束語

針對于復雜的3D環境，文章根據八叉樹適合虛擬場景劃分的特點，采用了一種適合密集型區域的八叉樹劃分方法，進行場景劃分。為適合八叉樹的存儲結構，對A*算法做了改進，引入優先級隊列并采用了分層結構，采用了從葉節點到根節點的搜索方法，規劃出了虛擬人行走的最優路徑。

第9篇

關鍵詞：滾轉角控制 區域規避 路徑約束

中圖分類號：V279 文獻標識碼：A 文章編號：1674-098X（2014）04（b）-0057-02

當前實時實現路徑規劃優化設計的算法比較復雜而且要求具有很好的精確性，同時各個優化方法也趨向混合，采用兩種或兩種以上的方法來研究，這樣結合了各個方法的優點。由于高速飛行器通過改變航向角的方式來進行轉彎，轉彎半徑比較大，影響飛行器機動性，對行器變軌、避障和改變打擊角度，都有很大的影響。所以本文采用基于滾轉角控制轉彎的方法，保證了轉彎半徑盡可能的小，增加了飛行器的機動性能。同時也要考慮飛行器的動力學模型、氣動、過載等物理參數的約束影響。

1 動力學方程

本文直接選取某一飛行器，其三自由度質點運動方程組：

（1）

（2）

（3）

（4）

（5）

（6）

再入軌道約束包括熱耗率、垂直加速度或者過載系數和動壓。

≤ （7）

≤ （8）

≤ （9）

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

≤0 （10）

其中是一個確定的滾轉角，該約束可以減少高度隨返回軌道的長周期變化，考慮到軌跡發散，同時保證了充分的滾轉角裕度，這是個軟約束。

對于再入飛行器從再入段終點開始，通過機動飛行消耗能量，降低速度、高度，調整航向到自動著陸起點為止的飛行段。要實施最終的能量管理（TAEM，terminal area energy management），此時由能量管理系統控制。在TAEM的接口處，軌跡必須有正確的條件以保證TAEM和進場航線順利實施。典型的再入條件為：

（11）

在TAEM處的相對速度有靠近航向對準錐（HAC，heading alignment cone）的切點決定，以保證獲得HAC在TAEM階段的切線。引入定義

（12）

其中是當前飛行器在大圓中的位置與HAC的方位角。對于最終航向角的一個約束為：

≤ （13）

是提前設定的值。最終飛行器在TAEM接口處變為平飛姿態。在TAEM處過大的|σ|會導致TAEM控制有很長的過度響應。所以對于水平著陸的飛行器而言，最終在TAEM處的滾轉角約束為

≤ （14）

其中是一個確定的值，一般取在5～15 °范圍內。

2 滾轉角約束設計

如果要基于滾轉角控制，就要把原來基于速度、高度的限制條件，轉化為基于滾轉角的限制條件。下面分兩部分解決這個問題。

（1）初始下降最大可行滾轉角

根據入口界面給定的條件，取滾轉角為常值（符號由水平制導決定），對再入飛行器三自由度質點運動方程組數值積分。當在速度為Vpt時滿足下式，則停止積分。

≤ （15）

是一個很小的預置正數，其中

（16）

當滾轉角為0時，準平衡滑翔條件為：

（17）

（2）QEGC限制跟隨速度變化的滾轉角

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

（18）

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

（19）

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

≤≤ （20）

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

（21）

在上式中Vpt是初始下降階段的末速度。在整個包絡可容許的滾轉角范圍為

≤≤ （22）

3 仿真實現

飛行器仿真對象選擇某類飛行器。其仿真參數如表1所示。

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

攻角α的規律如下，

（23）

當時，當時，。

大氣密度與高度的關系式：

（24）

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

氣動參數的確定：

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

（25）

滾轉角的選取：

我們綜合上面所講約束條件，可以設定的值為常值，這是符號隨時間變化，達到規避威脅的目的。這個也是整個算法的關鍵。

避障算法仿真，最終的位置是自由的，沒有約束。避開障礙是最主要的目的。在選擇滾轉角時，要考慮到最小轉彎半徑的約束。實驗中我們采用手動的方式來生成避障軌跡，對于滾轉角取為±60°。具體的變化時刻，輸入的時間序列得到。滾轉角變化曲線。結果如圖1、2、3、4。

再入飛行器規劃路徑仿真結果表明基于滾轉角控制軌跡優化方法保證了飛行器的快速性和機動性，減小了轉彎半徑，提高了轉彎效率，可以快速、方便的達到規避障礙的目的。