研究生: |
羅聖傑 Sheng-Jie Luo |
---|---|
論文名稱: |
利用改造的非支配排序基因多目標優化演算法實行複數無人飛行載具在複雜環境下之路徑規劃 Multi-UAVs Path Planning in a Complicated Environment with the Use of Improved NSGA-II Multi-Objective Optimization Approaches |
指導教授: |
蘇順豐
Shun-Feng Su |
口試委員: |
郭重顯
Chung-Hsien Kuo 陶金旺 Chin-Wang Tao 莊鎮嘉 Chen-Chia Chuang |
學位類別: |
碩士 Master |
系所名稱: |
電資學院 - 電機工程系 Department of Electrical Engineering |
論文出版年: | 2013 |
畢業學年度: | 101 |
語文別: | 英文 |
論文頁數: | 93 |
中文關鍵詞: | 路徑規劃 、多目標基因遺傳演算法 、無人飛行載具 |
外文關鍵詞: | path planning, multi-objectives genetic algorithms, unmanned aerial vehicles |
相關次數: | 點閱:374 下載:6 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本研究針對複數台無人飛行載在三維的路徑規劃問題,提出一個改進的非支配排序基因遺傳演算法(Improved NSGA-II)。此路徑規劃問題在三為空間真實環境下須考慮多個目標優化。除引入真實地圖做飛行環境,也加入了許多限制以及因防護機制所帶來的毀滅及偵查可能性。為了搜尋較好可行解,除了使用原始環境天擇的方法,本文也採取了人擇方式,由人為的偏好決定基因演化的方向。且此方法可同時考慮多個待優化目標之權重分配,減少因適應度函數選擇的不當所增加的收斂時間成本。藉由固定三維座標裡的水平座標,使算法不會將路徑點收斂至同一座標,以達路徑的可行性。此外,加入新設計的遺傳操作子:平滑及取才算子,以增加路徑的合理性及多元化。實驗結果指出,本文所提之改進算法可考將多個目標列入計算且有效找到根據人為偏好所近似的 Pareto 較優可行解集。
In this study, an improved non-dominated sorting genetic algorithm (improved NSGA-II) is proposed for multi-UAVs three-dimensional path planning. It can be found that the problem for such a path planning problem is a multiple objectives optimization problem in a 3-D real environment. In addition to the use of real maps as the flight environment, several restrictions and the possibility of destruction and detection caused by protective mechanisms (ADUs) are also considered in the problem. In order to have better search performance, in addition to using the original environment of natural selection methods, humankind selection manner is taken into account to determine the direction of genetic evolution by human preference. This approach simultaneously considers the weight assignments of multiple objectives and reduces the costs of convergence time, which may increase if the fitness functions chosen are improper. Also, with a fixed horizontal coordinate in the three-dimensional coordinates, the algorithm does not converge to the same point so that it can reach feasibility of the paths. Besides, new designed genetic operators, and , are proposed to increase the rationality and diversity of paths. Experimental results indicate that the proposed algorithm can take several objectives into account and effectively find feasible solutions of the approximate Pareto optimum set based on the human preferences.
[1] L. R. Newecome, Unmanned aviation: a brief history of unmanned aerial vehicles, Aiaa, 2004.
[2] Wikipedia, "Multi-objective optimization," Wikipedia, [Online]. Available:
http://en.wikipedia.org/wiki/Multi-objective_optimization. [Accessed Jul. 2013].
[3] B. Suman and K. Prabhat, "A survey of simulated annealing as a tool for single and multiobjective optimization," Journal of the operational research society 57.10, vol. 57, no. 10, pp. 1143-1160, 2006.
[4] N. Srinivas and D. Kalyanmoy, "Muiltiobjective optimization using nondominated sorting in genetic algorithms," Evolutionary computation 2.3, pp. 221-248, 1994.
[5] D. Kalyanmoy, A. Samir, A. Pratap and T. Meyarivan, "A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II," Lecture notes in computer science , pp. 849-858, 2000.
[6] E. Besada-Portas, L. de la Torre, J. de la Cruz and B. de Andres-Toro, "Evolutionary trajectory planner for multiple UAVs in realistic scenarios," Robotics, IEEE Transactions, vol. 26, no. 4, pp. 619-634, 2010.
[7] S. Mittal and D. Kalyanmoy, "Three-dimensional offline path planning for UAVs using multiobjective evolutionary algorithms," Proceedings of the Congress on Evolutionary Computation, 2007.
[8] I. Nikolos, K. Valavanis, N. Tsourveloudis and A. Kostaras, "Evolutionary algorithm based offline/online path planner for UAV navigation," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions , vol. 33, no. 6, pp. 898-912, 2003.
[9] I. K. Nikolos, N. C. Tsourveloudis and K. P. Valavanis, "Evolutionary algorithm based path planning for multiple UAV cooperation," Advances in Unmanned Aerial Vehicles. Springer Netherlands, p. 309340, 2007.
[10] I. Hasircioglu, H. R. Topcuoglu and M. Ermis, "3-D path planning for the navigation of unmanned aerial vehicles by using evolutionary algorithms," Proceedings of the 10th annual conference on Genetic and evolutionary computation, 2008.
[11] Y. Pehlivanoglu and A. Hacioglu, "Vibrational genetic algorithm based path planner for autonomous UAV in spatial data based environments," Recent Advances in Space Technologies, 2007. RAST'07. 3rd International Conference, pp. 573-578, 2007.
[12] I. K. Nikolos and N. Tsourvelouds, "Path planning for cooperating unmanned vehicles over 3-d terrain," Informatics in Control, Automation and Robotics. Springer Berlin Heidelberg, pp. 153-168, 2009.
[13] Z. Changwen, L. Lei, X. FanJiang, S. Fuchun and D. Mingyue, "Evolutionary route planner for unmanned air vehicles," Robotics, IEEE Transactions, vol. 21, no. 4, pp. 609-620, 2005.
[14] Z. Ruoding, Z. Changwen and Y. Ping, "Route planning for unmanned air vehicles with multiple missions using an evolutionary algorithm.," Natural Computation, vol. 3, pp. 23-28, 2007.
[15] J. M. de la Cruz, E. Besada-Portas, L. Torre-Cubillo, B. Andres-Toro and J. A. Lopez-Orozco, "Evolutionary path planner for UAVs in realistic environments," Proceedings of the 10th annual conference on Genetic and evolutionary computation, pp. 1477-1484, 2008.
[16] J. M. de la Cruz, E. Besada Portas, L. de la Torre and B. Andr’es Toro, "Multiobjective path planner for unmanned air vehicles (UAVs) based on genetic algorithms," in the 8th Int. FLINS Conf., Madrid, Spain, 2008.
[17] J. A. Bondy and U. S. R. Murty, "North Holland," in Graph Theory with Applications, London, 1976, pp. 12-21.
[18] R. Diestel, Graph Theory, Springer-Verlag, 2005.
[19] A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
[20] B. Korte, L. Lovasz, H. Promel and A. Schrijver, PATHS, FLOWS, AND VLSI-LAYOUT, Springer-Verlag, 1990.
[21] D. Goldberg and K. Deb, "A comparative analysis of selection schemes used in genetic algorithms," in Foundations of Genetic Algorithms, Morgan Kaufmann Publishers, Inc, 1991, pp. 69-93.
[22] B. L. Miller and D. E. Goldberg, "Genetic Algorithms, Tournament Selection, and the Effects of Noise," IlliGAL Report, 1995.
[23] M. V. Butz, K. Sastry and D. E. Goldberg, "Tournament Selection in XCS," IlliGAL Report, 2002.
[24] Wikipedia, "Crossover (genetic algorithm)," Wikipedia, [Online]. Available: http://en.wikipedia.org/wiki/Crossover_(genetic_algorithm). [Accessed Jul. 2013].
[25] P. K. Chawdhry, R. Roy and R. K. Pant, Soft computing in engineering design and manufacturing, Springer, 1998.
[26] "Crossover and Mutation," [Online]. Available:
http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php. [Accessed Jul. 2013].
[27] J. Chen, S. Xiong and W. Lin, "Improved strategies and researches of NSGA-II algorithm," Computer Engineering and Applications, pp. 42-45, 2011.
[28] K. Deb, C. Shamik and M. Kaisa, "Towards estimating nadir objective vector using evolutionary approaches," Proceedings of the Genetic and Evolutionary Computation Conference, pp. 643-650, 2006.
[29] K. Deb, J. Sundar, N. Udaya Bhaskara Rao and S. Chaudhuri, "Reference point based multi-objective optimization using evolutionary algorithms," International Journal of Computational Intelligence Research, vol. 2, no. 3, pp. 273-286, 2006.
[30] Wikipedia, "Parallel processing," Wikipedia, [Online]. Available:
http://en.wikipedia.org/wiki/Parallel_processing. [Accessed Jul. 2013].