Please use this identifier to cite or link to this item:
標題: 基於凡諾圖之3D無人飛機路徑規劃
3D Unmanned Aerial Vehicle Path Planning Based on Voronoi Diagram
作者: 陳建旭
Chen, Chien Hsu
關鍵字: 無人飛行載具;Unmanned Aerial Vehicles(UAVs);群蟻最佳化;凡諾圖;太空梭雷達地形任務;數值地形高程;Ant Colony Optimization;Voronoi Diagram;Shuttle Radar Topography Mission (SRTM);Digital Elevation Models (DEM)
出版社: 資訊科學與工程學系所
引用: 中文文獻 [1]史宗鵬, 杜萍, 畢義明. “基於A*演算法的即時航跡規劃方法研究,” 海軍工程大學學報, 18 (5), pp. 79-82, 2006. [2]張棋, “基於改進啟發演算法的無人機航路規劃,” 碩士論文, 電子科技大學, pp. 31-38, 2010. [3]劉金義, 劉爽, “Voronoi Diagram應用綜述,” 工程圖學學報, 第二期, pp. 125-131, 2004. 英文文獻 [4]Bullnheimer B., Hartl R. F., and Strauss C., “A New Rank-based Version of the Ant System,” A Computational Study, Technical Report POM-03/97, Institute of Management Science, University of Vienna, 1997. [5]Chang W. Y., “The Study of Flight Path Planning for Multiple Target Visitations,” PHD Dissertation, National Cheng-Kung University, 2007. [6]Cheng Z., Sun Y., and Liu Y. L., “Path planning based on immune genetic algorithm for UAV,” International Conference on ICEICE, pp.590-593, 2011. [7]Dorigo M., “Optimization, Learning and Natural Algorithms,” Ph.D. Thesis, Politecnico di Milano, Italy, 1992. [8]Dorigo M. and Caro G. Di, “The Ant Colony Optimization Meta-heuristic, New Ideas in Optimization,” McGraw-Hill, pp. 11-32, 1999. [9]Dorigo M., and Gambardella L. M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, pp. 53-66, 1997. [10]Fu X. W., Gao X. G. “Multiple UCAVs cooperative path planning in dynamic environments,” Industrial Electronics and Applications (ICIEA), pp. 1708-1711, 2009. [11]Huo C. L., “Multiple Target Path Planning for Intelligent UAV,” Master Degree Thesis, National Dong-Hwa University, 2009. [12]Liu L. F. and Zhang S. Q., “Voronoi diagram and GIS-based 3D path planning,” International Geoinformatics Conference, pp. 1-5, 2009. [13]Ma X. L., Ye W., and Fan H. D., “Low altitude penetration route planning algorithm simulation study,”Journal of System Simulation, vol. 16, pp. 458–464, 2004. [14]Malaek S. M., Kosari A. R., and Jokar S., “Dynamic Based Cost Functions for TF/TA Flights,” IEEE Aerospace Conference, pp. 1869-1876, 2005. [15]Nikolos I. K., Valavanis K. P., Tsourveloudis N. C., and Kostaras A. N., “Evolutionary algorithm based offline/online path planner for UAV navigation,” IEEE Transactions On Systems, Man, and Cybernetics—Part B: Cybernetics vol.33, pp. 898-912, 2003. [16]Rathbun, D., Kragelund S., Pongpunwattana A., and Capozzi, B. “An evolution based path planning algorithm for autonomous motion of a UAV through uncertain environments,”Digital Avionics Systems Conference, vol 2, pp. 8D2-1 - 8D2-12 ,2002. [17]Shen C. L. and Xu K. H., “Low altitude penetration of a number of key technologies,” Journal of Nanjing University of Aeronautics and Astronautics, vol. 32, pp. 335–342, 2000. [18]Wang G. S., Li Q., and Guo L. J., “Multiple UAVs Routes Planning Based on Particle Swarm Optimization Algorithm,” Information Engineering and Electronic Commerce (IEEC), pp. 1-5, 2010. [19]Zhang C., Zhen Z. Y., Wang D. B., and Li M.,“UAV path planning method based on ant colony optimization,”Control and Decision Conference (CCDC), pp. 3790-3792, 2010. [20]Zhao L., Zheng Z., Liu W., Cai K. Y., and Lin S,“Real-time path planning for multi-UAVs with share of threats information,”Industrial Electronics and Applications (ICIEA), pp. 1359-1364, 2011.
無人飛行載具(Unmanned Aerial Vehicles, UAVs)已廣泛運用於民生及軍事用途,為提高任務執行之效能及安全性,有關自主性飛行控制之路徑規劃,已是各國重要發展關鍵技術,然而無人飛行載具飛行航路需滿足諸多飛行限制,以利任務遂行。現階段較為熟悉之最佳化演算法計有:基因演算法、粒子演算法及類神經網路等,本文則以模擬螞蟻覓食行為之群蟻最佳化演算法(Ant Colony Optimization, ACO)作為基礎,並建置地形模型、威脅源模型及考量載具飛行性能,評估航程距離、威脅程度及飛行高低累計代價,規劃三維飛行路徑,以供決策者參考。
本文首先介紹蟻群演算法基本原理和數學模型,利用其機率式分佈計算、正反饋機制及貪婪搜索的演算法,完成路徑搜索外,威脅源強度及飛行高度亦納入適性函數進行成本評估,進而選出最佳化之飛行路徑;為降低龐大計算空間,路徑以凡諾圖(Voronoi Diagram)生成初始航跡,並將透過已知的地方雷達或威脅源進行分段航跡成本預先處理;另考量其無人飛行載具飛行性能限制,數位地形高度、坡度亦進行調整,避免於航路路徑上撞山或墜毀地面。
經由群蟻演算最佳化路徑產生後,本文再對於生成航跡進行區域最佳解分析,調整最佳路徑,增加飛行航路效益。為驗證本文所提方法之可用性,最後章節以美國太空梭雷達地形任務(Shuttle Radar Topography Mission, SRTM)數值地型高程資料(Digital Terrain Elevation Models, DTEM)模擬飛行路徑,藉由通過MATLAB對其程式模擬,說明本論文研究方法之可行性。

Unmanned Aerial Vehicles have been widely operated in civil and military domain. Intelligent path planning of autonomous flight control has been considered to be a pivotal technology for flight path planning, so as to promote mission effectiveness and safety. However, there are still essential constraints, which UAV path planning issues are supposed to comply with. For the time being, there are well-known algorithms such as Genetic Algorithm, Particle Swarm Optimization, and Neutral Network, which are prevailing. The method proposed in this thesis is based on the Ant Colony Optimization (ACO); in addition, it utilizes the digital terrain model, the threat model, and the aerodynamics performance constraints and tries to minimize the cost of the flight path. Finally, the results obtained are intended to present to a commander for decision making.
Ant Colony Optimization model consists of probability distribution, positive feedback, and greedy algorithm. On account of accumulation of path pheromone, which are stemmed from threat intensity, terrain elevation, and path distance, near optimal path may be found. To reduce the huge computation time, the Voronoi Diagram is applied to produce flight path firstly, and the cost of the path is preprocessed by considering the threat positions and intensity which were known in advance; moreover, UAV performance constraints have to be taken into account. That is, the digital terrain elevation and the slope have to be adjusted for the avoidance of aircraft crash.
Finally, the proposed method tries to carry out a local optimization method to improve the flight path by trajectory adjustment. To verify the feasibility of the proposed method, NASA SRTM (Shuttle Radar Topography Mission) DEM (Digital Elevation Models) was adopted for the flight path finding. The results reveal to effectiveness of the proposed method.
其他識別: U0005-2008201214293900
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.