臺灣博碩士論文加值系統

本論文探討無人飛機(Unmanned Aerial Vehicle, UAV)自我調整飛行路徑，能夠自動閃避危險防空武器射程範圍，通過危險的路經區域。使得UAV可以用在軍用偵照、戰場電戰干擾、秘密擊殺、環境保護和高空監視等任務需求。
實驗以粒子群最佳化演算法(particle swarm optimization, PSO)調整飛行路徑，能避讓防空武器障礙物的危險範圍，模擬不同類型防空武器佈署於不同地形內，達到閃避結果的飛行路徑規劃。
本論文提出之演算法經由模擬實驗證明，在符合現實防空武器部署情況下，UAV可以依任務需要避讓防空障礙物，搜尋閃避飛行路徑，安全飛抵目標區。

This paper discusses an unmanned aerial vehicle (UAV) flight route by itself to evade and passing through the air-defense weapons engagement zones. Making the UAV can be used in Military reconnaissance at the battlefield, electronic warfare interfere, secret assassination, environmental protection, and aerial surveillance.
By using particle swarm optimization algorithms, an UAV adjusts its flight route to evade weapon engagement zones. In this experimental study, various types of air-defense weapons were simulated, and the optimal path within a multitarget navigation route was determined by adjusting the flight routes in a 3D space by using a particle swarm optimisation algorithm. Through terrain feature simulations, an algorithm that can be used in simulated experiments to verify the actual air-defense weapon deployment of various countries was developed. The UAV is capable of independently assessing the defensive area of air- defense obstacles.
By adjusting flight routes through combinatorial optimization and particle swarm optimization, the UAV achieves a safe landing on the target area without being shot down by the enemy. The focus of this study was to develop an intelligent UAV route-planning algorithm for evading air-defense weapons.

摘要 I
ABSTRACT II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 VIII
符號表 IX
第一章 緒論 1
1-1 研究背景 1
1-2 動機與目的 2
1-3 文獻探討 3
1-3-1 二維探勘演算法 4
1-3-2 三維探勘演算法 10
1-4 研究方法 12
1-5 論文架構 13
第二章 防空識別區飛行路徑規劃設計 15
2-1 飛行環境建立 15
2-2 飛行動態限制 17
2-3 防空識別區與防空武器分類簡介 18
2-3-1 防空識別區 20
2-3-2 防空武器分類 21
2-4 路徑演算法工具應用 22
2-4-1 B-spline 解析函數路徑軌跡演算法 22
2-4-2 道格拉斯-普克(Douglas–Peucker algorithm)演算法 25
2-4-3 PSO演算法 27
第三章 防空武器障礙物路徑探勘與調整 31
3-1 防空識別區防空武器障礙物特徵萃取程序 31
3-1-1 防空武器座標範圍配置 32
3-1-2 防空識別區圖形特徵萃取 37
3-1-3 飛行路徑曲線特徵萃取 41
3-2 飛行候選路徑向量調整 44
3-2-1 飛行路徑向量 45
3-3 適應函數 47
3-3-1 防空障礙物避讓路徑 47
3-3-2 適應函數的設計 49
3-4 避讓演算法整體架構流程 56
第四章 實驗模擬 59
4-1 防空識別區域模擬環境條件建立 59
4-1-1 無人機動態演算法參數設定 60
4-1-2 防空識別區內模擬地形環境 62
4-2 防空武器障礙物特徵模擬 64
4-3 多巡航點最佳候選路徑規劃 68
4-4 防空障礙物佈署不同地形特徵比較 69
4-4-1 防空武器佈署避讓多巡航點路徑規劃實驗 70
4-4-2 飛航路徑規劃討論 77
第五章 研究結論與未來展望 79
5-1 結論 79
5-2 未來展望 80
參考文獻 81
作者簡歷 87

[1]謝德望、黃楓台、李勝義，“巡弋飛彈飛行路徑最佳化之研究”，國防大學理工學院電機工程學系，中正嶺學報出版，第三十六卷，第二期，五月2008年。
[2]何小林，“巡弋飛彈偵測與防禦研析”，海軍學術月刊，第36卷第11期，2002。
[3]胡元傑，“中共之巡弋飛彈發展”，國防譯粹月刊出版，第31卷，第7期，2004。
[4]A. Alvarez, A. Caiti, and R. Onken, “Evolutionary path planning for autonomous underwater vehicles in a variable ocean,” IEEE Journal of Oceanic Engi. , vol. 29, no. 2, pp. 418-429, 2004.
[5]Y. Gu, B. Seanor, G. Campa, M. R. Napolitano, L. Rowe, S. Gururajan, and S. Wan, “Design and flight testing evaluation of formation control laws,” IEEE Trans. on Control Systems Technology, vol. 14, no. 6, pp. 1105-1112, 2006.
[6]T. Shima, S. Rasmussen, and D. Gross, “Assigning micro UAVs to task tours in an urban terrain,” IEEE Trans. on Control Systems Technology, vol.15, no. 4, pp. 601-612, 2007.
[7]火致力，智慧型無人飛行載具多目標巡航路徑規劃，國立東華大學碩士論文，2009。
[8]D. Merkle, M. Middendorf, and H. Schmeck, “Ant colony optimization for resource-constrained project scheduling,” IEEE Trans. on Evolutionary Computation, vol. 6, issue: 4, pp. 333-346, 2002.
[9]張延廷，國防通識教育(上)第三章軍事科技，國防大學出版書籍，2010。
[10]B. Bethke, M. Valenti, and J. P. How, “UAV task assignment,” IEEE Robotics & Automation Magazine, vol. 15, no 1, pp. 39-44, 2008.
[11]李雨林，“共軍巡弋飛彈發展與威脅”，國防雜誌社出版，第18卷第2期，2002。
[12]S. A. Cambone, K. A.Krieg, and U. P. Pace, “Unmanned Aircraft Systems Roadmap,” USA: Office of the Secretary Of Defense, 2005.
[13]J. Y. Hwang, “A fast path planning by path graph optimization,” IEEE Trans. on Systems, Man, and Cybernetics, Part A: Cybernetics, vol. 33, no. 1, pp. 121-128, 2003.
[14]I. Guyon, S. Gunn, M. Nikravesh, L. A. Zadeh, Feature Extraction Foundations and Applications, Springer, New York ,2006.
[15]I. K. Nikolos, N. C. Tsourveloudis and K. P. Valavanis, “Evolutionary algorithm based 3-D path planner for UAV navigation,” Technical Univ. of Crete, Dept. of Prod. Engi. and Mana. pp. 1-6, 2000.
[16]S. Mittal and K. Deb, “Three-dimensional offline path planning for UAVs using multiobjective evolutionary algorithms,” in Proc. of IEEE Congress on Evolutionary Computation, pp. 3195-3202, 2007.
[17]C. E. Thorpe, “Path planning for a mobile robot,” IEEE Trans. on Man and Cybernetics Society, pp. 318-322, Apr. 1992.
[18]S. Quan, Z. Chi, X. Ning, and X. Jing, “Develop feedback robot planning method for 3D surface inspection,” IEEE/RSJ International Conf. on Intelligent Robots and Systems, pp. 4381-4386, 2009.
[19]J. Ren, K. A. McIsaac, R. V. Patel, and T. M. Peters, “A potential field model using generalized sigmoid functions,” IEEE Trans. on Systems, Man and Cybernetics, Part B: Cybernetics, vol. 37, no. 2, pp. 477-484, 2007.
[20]Y. K. Hwang and N. Ahuja, “A potential field approach to path planning,” IEEE Trans. on Robotics and Automation, vol. 8, pp. 23-32, 1992.
[21]D. P. Bertsekas, Dynamic Programming and Optimal Control, Vol. II, 4th Edition, 2012.
[22]L. Huang, G. Wan, and C. Liu, “An improved parallel thinning algorithm,” in Proc. of the 7th International Conf. on Document Analysis and Recognition, pp. 780-783, 2003.
[23]L. Louisa, S. W. Lee, and C. Y. Suen, “Thinning Methodologies-A Comprehensive Survey,” IEEE Trans. on Pattern Analysis and MachineIntelligence, vol. 14, no. 9, sept. 1992.
[24]T. Y. Zhang and C. Y. Suen, “A fast thinning algorithm for thinning digital patterns,” Communications of the ACM, vol. 27, no. 3, pp. 236-239, March 1984.
[25]P. Bhattacharya and M. L. Gavrilova, “Roadmap-based path planning -using the Voronoi diagram for a clearance-based shortest path,” IEEE Robotics & Automation Magazine, vol. 15, no. 2, pp. 58-66, June 2008.
[26]P. Bhattacharya and M. L. Gavrilova, “Voronoi diagram in optimal path planning,” in Proc. of IEEE International Symposium on Voronoi Diagrams in Science and Engineering, pp. 38-47, 2007.
[27]X. Yang, M. Moallem, and R. V. Patel, “A layered goal-oriented fuzzy motion planning strategy for mobile robot navigation,” IEEE Trans. on Systems, Man, and Cybernetics, Part B, vol. 35, issue: 6, pp. 1214-1224, 2005.
[28]L. E. Kavraki, P. Svestka, J. C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. on Robotics and Automation, vol. 12, no. 4, pp. 566-580, 1996.
[29]J. P. van den Berg and M. H. Overmars, “Roadmap-based motion planning in dynamic environments,” IEEE Trans. on Robotics, vol. 21, no. 5, pp. 885-897, 2005.
[30]P. N. Azariadis and N. A. Aspragathos, “Obstacle representation by Bump-surfaces for optimal motion-planning,” Robotics and Autonomous Systems, vol. 51, no. 2-3, pp. 129-150, 2005.
[31]R. Finkel, J. L. Bentley, Quad Trees: A Data Structure for Retrieval on Composite Keys, Acta Informatica. 1974.
[32]M. Saska, “Robot path planning using particle swarm optimization of ferguson splines,” in Proc. of IEEE Conference on Emerging Technologies and Factory Automation, pp. 833-839, Sept. 2006.
[33]V. G. Gudise and G. K. Venayagamoorthy, “Comparison of particle swarm optimization and backpropagation as training algorithms for neural networks,” in Proc. of IEEE Swarm Intelligence Symp. , pp. 110-117, 2003.
[34]J. L. Peng, F. Zhu, X. Sun, and B. Sun, “On route-planning of UAV based on discrete PSO and Voronoi diagram,” in Proc. of IEEE Chinese Control Conference, pp. 804-807, 2007.
[35]S. S. Ge and Y. J. Cui, “New potential functions for mobile robot path planning,” IEEE Trans. on Robotics and Automation, vol. 16, no. 5, pp. 615-620, 2000.
[36]J. W. Horng and J. T. Li, “An automatic and efficient dynamic programming algorithm for polygonal approximation of digital curves,” Pattern Recognition Letters. , vol. 23, no. 1-3, pp. 170-182, 2002.
[37]C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice Hall, 1982.
[38]T. Y. Sun, S. J. Tsai, Y. N. Lee, S. M. Yang, and S. H. Ting, “The study on intelligent advanced fighter air combat decision support system,” in Proc. of IEEE Conf. on Information Reuse and Integration, pp. 39-44, 2006.
[39]A. I. Belkharraz and K. Sobel, “Simple adaptive control for aircraft control surface failures,” IEEE Trans. on Aerospace and Electronic Systems, vol. 43, no. 2, pp. 600-611, 2007.
[40]蘇桓生，作戰區野戰防空武器數量需求模式建構，國防大學資原管理與決策研究所碩士論文，2008。
[41]S. H. Chen, T. Y. Sun, S. J. Tsai, C. H. Tsai, S. H. Ting, and C. M. Wu, “Intelligent control of air combat maneuvering automation based on input-output linearization and particle swarm optimizer,” in Proc. of 8th Symposium on International Advanced Intelligent Systems, pp. 211-216, 2007.
[42]朱奕嵐，絕對性領空主權之論析，私立東吳大學法律系碩士論文，1999。
[43]李石磊、宋祥君、李旭淵與姚志敏，“防空導彈引戰配合效率評估仿真方法與應用”，中文電子期刊火力與指揮控制編輯部出版, 第30卷，第4期，pp. 24-27，2005。
[44]S. M. LaValle, Planning Algorithms, Cambridge University Press, 2006.
[45]I. K. Nikolos, K. P. Valavanis, N. C. Tsourveloudis, and A. N. Kostaras, “Evolutionary algorithm based offline/online path planner for UAV navigation,” IEEE Trans. on Systems, Man and Cybernetics-Part B: Cybernetics, vol. 33, no. 6, pp. 898-912, 2003.
[46]M. Visvalingam and J. D. Whyatt, “The Douglas-Peucker algorithm for line simplification: re-evaluation through visualization,” Computer Graphics Forum, vol. 9, no. 3, pp. 213-255, 1990.
[47]R. C. Gonzalez and R. E. Woods, Digital Image Processing, Addison-Wesley Inc. , 1993.
[48]R. C. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” in Proc. 6th Int. Symp. Micro Mach. Human, pp. 39-43, 1995.
[49]C. Zhang, H. Shao, and Y. Li, “Particle swarm optimization for evolving artificial neural network,” in Proc. of the International Conference on Systems, Man, and Cybernetics, vol. 4, pp. 2487-2490, 2000.
[50]S. T. Hsieh, T. Y. Sun, C. L. Lin, and C. C. Liu, “Effective learning rate adjustment of blind source separation based on an improved particle swarm optimizer,” IEEE Trans. on Evolutionary Computation, vol. 12, no. 2, pp. 242-251, 2008.
[51]S. T. Hsieh, T. Y. Sun, C. C. Liu, and C. W. Lin, “An improved particle swarm optimizer for placement constraints,” Journal of Artificial Evolution and Applications, Open Access Journal, vol. 10, 2008.
[52]C. W. Warren, “Global path planning using artificial potential fields,” in Proc. of IEEE Inter. Conf. on Robotics and Automation, pp. 316-321, vol. 1, 1989.
[53]S. Kanchanavally, R. Ordonez, and C. J. Schumacher, “Path planning in three dimensional environment using feedback linearization,” in Proc. of American Control Conference, pp. 3545-3550, 2006.
[54]B. Hutt and K. Warwick, “Synapsing variable-length crossover: meaningful crossover for variable-length genomes,” IEEE Trans. on Evolutionary Computation, vol. 11, no 1, pp. 118-130, 2007.
[55]B. R. Preiss, Data Structures and algorithms with object-oriented design patterns 94 in c++, John Wiley & Sons, 1999.