利用改造的非支配排序基因多目標優化演算法實行複數無人飛行載具在複雜環境下之路徑規劃

簡易檢索 / 詳目顯示

回結果列表

研究生：	羅聖傑 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
相關次數：	點閱：235 下載：6
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

本研究針對複數台無人飛行載在三維的路徑規劃問題，提出一個改進的非支配排序基因遺傳演算法(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.

中文摘要	I
Abstract	II
誌謝	III
Contents	IV
List of Figures	VIII
List of Tables	X
Chapter 1	Introduction	1
1	Research Motivation and Objective	1
2	Multiple Objectives Optimum Problem	2
3	Related Research for UAVs Path Planning	5
4	New Designs and Improved Way Cited	6
5	Thesis Organization	7
Chapter 2	Environment and System Description	8
1	Original Mathematical Models	8
1.1	Objective One---minimum turning radius	8
1.2	Objective Two--- Limited UAV Slope	9
1.3	Objective Three--- Fuel	10
1.4	Objective Four---Terrain	13
1.5	Objective Five--- Map Limits	13
1.6	Objective Six--- Flight Prohibited Zones	14
1.7	Objective Seven--- Minimum Path Length	15
1.8	Objective Eight--- Minimum Probability of Kill	15
1.9	Objective Nine---Minimum Probability of Radar Detection	17
1.10	Objective Ten---Minimum Flight Altitude	19
1.11	Objective Eleven--- Avoiding UAVs Collisions	19
2	Improved Mathematical Models	20
2.1	Reform of Objective Four---Terrain	22
2.2	Reform of Objective Six--- Flight Prohibited Zones	23
2.3	Reform of Objective Eight--- Minimum Probability of Kill	24
2.4	Reform of Objective Nine--- Probability of Radar Detection	25
3	Initial Condition Set for Simulation	26
3.1	Some Simple Setting Parameters	26
3.2	Real Map Used in Simulation	27
3.3	Position and Range of ADUs Model	28
Chapter 3	Methods of Path Planning	33
1	The Development of NSGA-II	33
1.1	Pareto Sorting Tactic	34
1.2	Crowding Distance Tactic	34
1.3	Selection and Truncation Tactic (elitist strategy)	35
2	The Architecture of NSGA-II	36
2.1	Selection	38
2.2	Crossover	39
2.3	Mutation	42
2.4	Evaluation	44
2.5	Combination of Population	44
2.6	Sorting	44
2.7	Extraction of Population	45
3	The Improvement of NSGA-II Dedicated for Path	45
3.1	Reform of Pareto Sorting Tactic	46
3.2	Reform of Arithmetic Operator	47
3.2.1	The Crossover Way Used in This Thesis	48
3.2.2	The Mutation Way Used in This Thesis	48
3.3	Reference Point Used in NSGA-II	49
3.4	New operator we designed for path planning--Smooth	51
3.5	New operator we designed for path planning--DifferentSolution	52
4	The Definition of Path in Improved NSGA-II	53
4.1	Initial Population	53
4.2	The Representation of Path in Improved NSGA-II Operators	54
5	The Parallel Processing of NSGA-II in Simulation	57
Chapter 4	Experiment Result	59
1	The GUI Interface of Improved NSGA-II in Simulation	60
2	The Result of Experiment---Single UAV	61
2.1	Experiment Results with Simple Initialization	62
2.1.1	Experiment-1 Using Original NSGA-II	63
2.1.2	Experiment-2 Using Improved NSGA-II	66
2.1.3	Experiment-3 Comparison with Using Improved NSGA-II	69
2.2	Experiment Results with Random Initialization	72
2.2.1	Experiment-4 Using Original NSGA-II and Random Initialization	72
2.2.2	Experiment-5 Using Improved NSGA-II and Half-Random Initialization	75
3	The Result of Experiment--Multiple UAV	79
3.1.1	Experiment-6 Using Original NSGA-II	80
3.1.2	Experiment-7 Using Improved NSGA-II	84
Chapter 5	Conclusion and Future Work	87
1	Conclusions	87
2	Future Work	88
REFERENCES	90

                                

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

簡易檢索 / 詳目顯示

相關論文