路徑規劃一直以來是相當重要的議題，從最早的汽車平面導航再到近年來興起的無人機導航。常見的演算法有可視圖法(Visibility Graph) 、A*演算法(A* Algorithm)、凡諾圖(Voronoi Diagram) 、蟻群演算法(Ant Colony Optimization, ACO)及粒子演算法(Particle Swarm Optimization, PSO)，這些演算法應用在2D搜索上足以應付，但是當遇到3D場景時這些演算法都有各自的缺點，像是搜索時間過長或是容易陷入局部最佳，灰狼優化演算法(Gray Wolf Optimization )被應用來解決這個問題。

因此本文基於灰狼優化演算法，通過模擬灰狼群體捕食策略及等級制度，並加入差分進化演算法(Differential Evolution, DE)及貪婪策略的概念。針對全域靜態地圖下，其他算法規劃無人機路徑時未考慮到信號覆蓋範圍以及整體航線不夠平滑，使用灰狼優化演算法來解決這些問題，最後與其他演算法比較有不錯的結果。

Path planning has always been a very important issue, from the earliest car plane navigation to the drone navigation of recent years. Common algorithms include Visibility Graph, A* Algorithm, Voronoi Diagram, Ant Colony Optimization (ACO), and Particle Swarm Optimization (PSO), these algorithms are sufficient for 2D search, but when it comes to 3D scenes these algorithms have their own shortcomings, such as too long search time or easily fall into the local best, Gray Wolf Optimization (GWO) is applied to solve this problem.

Therefore, in this paper, based on the Grey Wolf Optimization algorithm, we simulate the predation strategy and hierarchy of grey wolves and add the concept of Differential Evolution (DE) and Greedy Algorithm. For the global static map, other algorithms do not consider the signal coverage and smoothness of the overall route, we use the gray wolf optimization algorithm to solve these problems and compare it with other algorithms and have good performance.

[1] P. Aero, "How to Use Drones to Measure Stockpiles and Track Volumes More Accurately," 20 7 2021. [Online]. Available: https://www.propelleraero.com/blog/how-stockpile-volume-measurement-works-in-drone-surveying-with-propeller/.
[2] "DRONE INSPECTIONS: A COMPREHENSIVE GUIDE TO HOW DRONES ARE BEING USED FOR VISUAL INSPECTIONS THROUGHOUT THE WORLD," flyability, [Online]. Available: https://www.flyability.com/drone-inspections.
[3] “SURVEYING WITH A DRONESsurveying & GIS,” wingtra, [線上]. Available: https://wingtra.com/drone-mapping-applications/surveying-gis/.
[4] “Drones Assisting Emergency Response,” IAI, 21 12 2020. [線上]. Available: https://www.iai.co.il/news-media/features/drones-assisting-emergency-response.
[5] L. R. o. T. S. Problem, “Literature Review on Travelling Salesman Problem,” International Journal of Research , 6 2018.
[6] M. Dorigo, V. Maniezzo 且 A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) , 2 1996.
[7] Seyedali Mirjalili, Seyed Mohammad Mirjalili,Andrew Lewis, “Grey Wolf Optimizer,” Advances in Engineering Software , p. 69:46–61, 3 2014.
[8] Paramvir Bahl and Venkata N. Padmanabhan, “RADAR: An In-Building RF-based User Location and Tracking System,” Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), 3 2000.
[9] Ram Kishan Dewangan1 · Anupam Shukla1 · W. Wilfred Godfrey1, “Three dimensional path planning using Grey wolf optimizer for UAVs,” Springer Science+Business Media, LLC, part of Springer Nature 2019, 7 1 2019.
[10] Wataru Mayeda; Wai-Kai Chen, “Graph Theory,” IEEE Transactions on Systems, Man, and Cybernetics, 5 1973.
[11] Han-Pang Huang* and Shu-Yun Chung, “Dynamic Visibility Graph for Path Planning,” Proceedings of 2004 IEEElRSl International Conference onIntelligent Robots and Systems, 28 9 2004.
[12] Ellips Masehian* and M. R. Amin-Naseri, “A Voronoi Diagram–Visibility Graph–Potential Field Compound Algorithm for Robot Path Planning,” 14 4 2003.
[13] František DuchoĖ*a, Andrej Babineca, Martin Kajana, Peter BeĖoa, Martin Floreka, Tomáš Ficoa, Ladislav Jurišicaa, “Path planning with modified A star algorithm for a mobile robot,” Modelling of Mechanical and Mechatronic Systems MMaMS 2014, 2014.
[14] HaibinDuan , YaxiangYu , Xiangyin Zhang , ShanShao, “Three-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm,” HaibinDuanYaxiangYuXiangyinZhangShanShao, pp. 1104-1115, 9 2010.
[15] Hsu-Chih Huang; Ching-Chih Tsai, “Global path planning for autonomous robot navigation using hybrid metaheuristic GA-PSO algorithm,” SICE Annual Conference 2011, 27 10 2011.