本篇論文主旨在於建立無人飛機多目標路徑規劃系統並建置與執行無人飛機系統驗證其可行性。首先求解兩目標之飛行路徑，必需考量滿足條件限制，如飛行安全、飛機性能等，以確保安全性及可行性的無人飛機任務路徑。應用基因演算法於路徑規劃，可調整適應性函式求解兩目標點之間的最佳路徑。接下來，以動態規劃擴展到多目標的飛行計畫，動態規劃可藉由以知的兩兩目標點之間的距離求解如何決定目標點通過的順序並在最後回到起始目標點，此航行的順序是最短路程解。最後整合無人載具自動導航系統執行。

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.

[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.