進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-1308201512234400
論文名稱(中文) 以混合基因演算法與動態規劃法解算無人載具多目標路徑規劃
論文名稱(英文) Hybrid Solution for UAV Multiple Target Path planning using Genetic Algorithm with Dynamic Programming
校院名稱 成功大學
系所名稱(中) 航空太空工程學系
系所名稱(英) Department of Aeronautics & Astronautics
學年度 103
學期 2
出版年 104
研究生(中文) 許育銘
研究生(英文) Yu-Ming Syu
學號 P46024257
學位類別 碩士
語文別 英文
論文頁數 68頁
口試委員 口試委員-陳杏圓
口試委員-葉泳蘭
指導教授-林清一
中文關鍵字 無人飛行載具  基因演算法  動態規劃  路徑規劃 
英文關鍵字 UAV  Genetic Algorithm  Dynamic Programming  Path Planning 
學科別分類
中文摘要 本篇論文主旨在於建立無人飛機多目標路徑規劃系統並建置與執行無人飛機系統驗證其可行性。首先求解兩目標之飛行路徑,必需考量滿足條件限制,如飛行安全、飛機性能等,以確保安全性及可行性的無人飛機任務路徑。應用基因演算法於路徑規劃,可調整適應性函式求解兩目標點之間的最佳路徑。接下來,以動態規劃擴展到多目標的飛行計畫,動態規劃可藉由以知的兩兩目標點之間的距離求解如何決定目標點通過的順序並在最後回到起始目標點,此航行的順序是最短路程解。最後整合無人載具自動導航系統執行。
英文摘要 The major objective of this thesis is to present a hybrid method by integrating, Genetic Algorithm with Dynamic Programming, for solving multiple target path planning in implementation into UAV system. In order to guarantee the safety requirement and feasibility for path planning, the flight path planning system (FPPS) necessarily consider the path security, UAV’s capability and so on. The Virtual Flight Map is built at first and the path planning would program in the map by algorithms. Between two target locations, Genetic Algorithm finds the optimal path with suitable fitness function. Then, with the distances matrix between every pair of multiple targets, Dynamic Programming (DP) expands the two targets path planning to multiple targets. The DP decide what is the visiting sequence of multiple targets which visits all targets just once and returns to the starting location. It must be the shortest distance of tour sequence. Finally, UAV system is sat up and performs flight path tracking to verify the flight path planning system.
論文目次 ABSTRACT.......................I
摘要...........................II
誌謝...........................III
CONTENTS.......................IV
LIST OF FIGURES................VI
LIST OF TABLE..................IX
Chapter 1 Introduction.........1
1.1 Motivation.............1
1.2 Literature Survey......2
1.3 Main Idea..............4
1.4 Thesis Outline.........5
Chapter 2 Flight Path Planning.6
2.1 Virtual Flight Map.....7
2.2 Path Planning Algorithm..15
2.2.1 Genetic Algorithm........15
2.2.2 Encoding and Initialization...................17
2.2.3 Evaluation and Selection......................20
2.2.4 Genetic Operators: Crossover and Mutation.....25
2.2.5 Replacement and Iteration.....................27
2.3 Dynamic Programming...........................27
2.4 Remarks ......................................33
Chapter 3 Result and Flight Verification..............34
3.1 GA Result.....................................34
3.1.1 Flatland with Forbid Zone.....................34
3.1.2 Fluctuant terrain.............................38
3.1.3 Terrain with forbidden zone...................42
3.2 DP Result.....................................49
3.3 UAV Flight Control System Set Up..............51
3.4 Flight Experiment.............................55
3.4.1 Flight Experiment for Autopilot Test..........55
3.4.2 Flight Experiment with GA Path Planning.......60
3.5 Remark........................................63
Chapter 4 Conclusion and Future work..................64
4.1 Conclusion....................................64
4.2 Future works..................................65
References............................................66
參考文獻 [1] Ioannis K. Nikolos, K.P. Valavanis, N. C. Tsourveloudis, A.N. Kostaras, “Evolutionary Algorithm Based Offline/Online Path Planner for UAV Navigation”, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 33, NO. 6, Dec. 2003, pp.898-912
[2]Masato Noto, Hiroaki Sato, “A method for the shortest path search by extended Dijkstra algorithm”, 2000 IEEE International Conference on Systems, Man, and Cybernetics, Vol. 3, 2000, pp.2310-2320
[3] Amit Patel, “Introduction to A*”, available in April 2015 from website:
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
[4] Chin E. Lin, Chun-Ying Chen, “UAV Autopilot Path Planning for Terrain Avoidance using Theta-Star Algorithm on Modified Virtual Map”, Journal of Aeronautics, Astronautics and Aviation, Series A, Vol. 46 No. 1, March 2014, pp. 67-77.
[5] Y. K. Hwang, Narendra Ahuja, “A Potential Field Approach to Path Planning”, IEEE Robotics and Automation Society, Vol. 8, NO. 1, 1992, pp.23-32.
[6] David E. Goldberg, Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, 1989, ISBN 0201157675
[7] K. F. Man, K. S. Tang, and S. Kwong, “Genetic algorithms: concepts and applications,” IEEE Transactions on Industrial Electronics, 43.5 (1996), pp.519-534.
[8] J. Tu, and S. X. Yang, “Genetic algorithm based path planning for a mobile robot,” IEEE International Conference on Robotics and Automation, ICRA'03, Vol. 1. 2003.
[9]K. Sugihara, and J. Smith, “Genetic algorithms for adaptive motion planning of an autonomous mobile robot,” IEEE International Symposium on Computational Intelligence in Robotics and Automation, CIRA'97, 1997, pp. 138-143.
[10] H. Mahjoubi, F. Bahrami, and C. Lucas, “Path planning in an environment with static and dynamic obstacles using genetic algorithm: a simplified search space approach,” IEEE Congress on Evolutionary Computation, CEC 2006, pp. 2483-2489.
[11]Sheng-Kai Yang, “Genetic Algorithm Path Planning with Camera Gimbal Tracking for UAV Flight Control”, Master Thesis, Department of Aeronautics and Astronautics, National Cheng Kung University, Taiwan, July 2014.
[12] Edwaed W. Large, “Dynamic programming for the analysis of serial behaviors”, Behavior Research Methods, Instruments, & Computers, June 1993, Vol. 25, NO.2, pp. 238-241.
[13] Dynamic programming, available in April 2015 from website:
http://en.wikipedia.org/wiki/Dynamic_programming
[14] R. E. Bellman, “Dynamic Programming,” Dover Publications, Dover edition, 2003. ISBN 0486428095.
[15] Michael Held and Richard M. Karp, “A dynamic programming approach to sequencing problems”, ACM '61 Proceedings of the 1961 16th ACM national meeting, 1961, pp. 71.201-71.204
[16] W. Y. Chang, F. B. Hsiao, and D. L. Sheu, “Two-Point Flight Path Planning Using a Fast Graph-Search Algorithm,” AIAA Journal of Aerospace Computing, Information, and Communication, vol. 3, Sep. 2006, pp. 453-470.
[17] W. Y. Chang, “The Study of Flight Path Planning for Multiple Target Visitations,” Ph.D. Dissertation, Department of Aeronautics and Astronautics, National Cheng Kung University, Taiwan, June 2007.
[18] U.S. Geological Survey, available in April 2015 from website:
http://www.usgs.gov/
[19] ASTER Global DEM, available in April 2015 from website: http://gdem.ersdac.jspacesystems.or.jp/search.jsp
[20] MICRODEM, available in April 2015 from website: http://www.usna.edu/Users/oceano/pguth/website/microdem/microdem.htm
[21] Mitchell Melanie, “An Introduction to Genetic Algorithms”, 1996, Cambridge, MA: MIT Press, ISBN 9780585030944.
[22] Holland, J. H., “Adaptation in Natural and Artificial Systems”, 1975
[23] Teo Lian Seng, Bin Khalid M. and Yusof R., “Tuning of a neuro-fuzzy controller by genetic algorithm”, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 29, Apr 1999, pp.226-236
[24] K. F. Man, K. S. Tang, and S. Kwong, “Genetic algorithms: concepts and applications,” IEEE Transactions on Industrial Electronics, 43.5 (1996), pp.
519-534.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2020-08-20起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw