臺灣博碩士論文加值系統

台灣多山少寬廣地的特性，加上平原區人口稠密的聚集，使得小型飛行器可飛行之區域極為分散與零碎且多數區域不乏涵蓋山脈等危險地形。為了因應低空環境航路規劃之需求，本論文探討二維平面航路規劃方法，利用幾何Voronoi多邊形圖合適的分割特性與Dijkstra搜索法得到全域最佳路徑結果，並擴展航路演算法以解決低空環境規劃常遇到的問題，例如針對於禁限建之飛航空域產生虛擬邊界威脅點來使規劃路徑保持在許可空域；同時使用等高線地形數據作為規劃之依據，產生適合在山區安全飛行的路徑；並簡化龐大的輸入資料，使演算法得以在嵌入式系統上順利運行。

Taiwan island has mountainous terrains and narrow plains with popularity urban area which makes the flyable airspace for light aircraft dispersible and fractional with some danger regions of high mountains. This research aims to develop flight route planning algorithms to generate feasible and optimal flight route by combining Voronoi diagram and Dijkstra’s algorithm. Then the extended algorithm is also proposed to solve the problems of flight route generation at low altitude environment. The virtual boundary technique is proposed to avoid the prohibited airspace for planning. Furthermore, this technique can extended to give approximate terrain contours to avoid in the airspace. The proposed algorithms have been validated by simulation, and performance has been verified by the implementation of algorithms over the ARM-based embedded system.

中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . i
英文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
誌謝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
表目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
圖目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
符號說明 . . . . . . . . . . . . . . . . . . . . . . . . . . . x
第一章 緒論 . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 研究動機與目的 . . . . . . . . . . . . . . . . . . 1 1.2
文獻回顧 . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 動態規劃 . . . . . . . . . . . . . . . . . . 3
1.2.2 A*演算法 . . . . . . . . . . . . . . . . . . 4
1.2.3 基因演算法 . . . . . . . . . . . . . . . . 4
1.2.4 快速隨機樹演算法 . . . . . . . . . . . . 5
1.2.5 人工勢場法 . . . . . . . . . . . . . . . . 6
1.2.6 粒子群最佳化算法 . . . . . . . . . . . . 7
1.2.7 圖論法 . . . . . . . . . . . . . . . . . . . 7
1.3 常見航路規劃方法 . . . . . . . . . . . . . . . . . 9
1.4 論文架構 . . . . . . . . . . . . . . . . . . . . . . 11
第二章 Voronoi結合Dijkstra之航路規劃方法 . . . . . . . 12
2.1 Voronoi圖 . . . . . . . . . . . . . . . . . . . . . . 12
2.1.1 特性 . . . . . . . . . . . . . . . . . . . . 13
2.1.2 Voronoi圖生成演算法 . . . . . . . . . . . 13
2.2 Dijkstra搜索演算法 . . . . . . . . . . . . . . . . 18
2.2.1 簡介 . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Dijkstra演算方法 . . . . . . . . . . . . . . 18
2.3 航路代價與威脅點 . . . . . . . . . . . . . . . . . 23
第三章 低空環境航路規劃 . . . . . . . . . . . . . . . . . 28
3.1 虛擬邊界 . . . . . . . . . . . . . . . . . . . . . . 30
3.2 圓柱法 . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 地形等高線 . . . . . . . . . . . . . . . . . . . . . 41
3.4 低空環境航路規劃總結 . . . . . . . . . . . . . . 52
第四章 航路規劃實作 . . . . . . . . . . . . . . . . . . . . 54
4.1 硬體規格 . . . . . . . . . . . . . . . . . . . . . . 54
4.2 系統架構 . . . . . . . . . . . . . . . . . . . . . . 56
4.3 建構發展環境 . . . . . . . . . . . . . . . . . . . 58
4.3.1 虛擬機 . . . . . . . . . . . . . . . . . . . 58
4.3.2 交叉編譯器 . . . . . . . . . . . . . . . . 59
4.3.3 Bootloader . . . . . . . . . . . . . . . . . 60
4.3.4 開源電腦視覺函式庫 . . . . . . . . . . . 61
4.4 框緩衝 . . . . . . . . . . . . . . . . . . . . . . . 65
4.4.1 框緩衝相關數據結構 . . . . . . . . . . . 66
4.4.2 框緩衝操作流程 . . . . . . . . . . . . . . 67
4.5 系統實作 . . . . . . . . . . . . . . . . . . . . . . 69
4.5.1 控制顯示單元 . . . . . . . . . . . . . . . 69
4.5.2 航路規劃頁面 . . . . . . . . . . . . . . . 71
4.5.3 導航顯示器 . . . . . . . . . . . . . . . . 73
第五章 結論與未來展望 . . . . . . . . . . . . . . . . . . 75
5.1 結論 . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 未來展望 . . . . . . . . . . . . . . . . . . . . . . 76
參考文獻 . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
英文論文大綱 . . . . . . . . . . . . . . . . . . . . . . . . 83
簡歷(CV) . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

[1] R. E. Larson and J. L. Casti, Principles of Dynamic Programming: Advanced Theory and Applications. Marcel Dekker, Inc. New York, 1982.
[2] K. S. Kwok and B. J. Driessen, “Path planning for complex terrain navigation via dynamic programming,” Proc. of American Control Conference, pp. 2941–2944, 1999.
[3] R. Holdsworth, J. Lambert, and N. Harle, “Harle, inflight path planning replacing pure collision avoidance, using ads-b,” Aerospace and Electronic Systems Magazine, pp. 27–32, 2001.
[4] 曹雲峰, “基於動態規劃的無人機航路優化問題研究,” 計 算機測量與控制, vol. 16(8), 2008.
[5] P. E. Hart, N. J. Nilsson, and B. Raphael, “Correction to a formal basis for the heuristic determination of minimum cost paths,” SIGART Newsletter, vol. 37, pp. 28–29, 1972.
[6] D. M. Bourg and G. Seemann, AI for Game Developers. O’Reilly, 2004.
[7] E. Rippel, A. B. Gill, and N. Shimkin, “Fast graph-search algorithms for general-aviation flight trajectory generation,” Journal of Guidance, Control, and Dynamics, vol. 28, no. 4, pp. 801–811, 2005.
[8] 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, pp. 435–470, 2006.
[9] A. S. Kumar, “Intelligent Transport Route Planning Using Genetic Algorithms in Path Computation Algorithms,” European Journal of Scientific Research, vol. 25(3), pp. 463–468, 2009.
[10] 柳長安, “無人機的偵察航路規劃,” 西北工業大學學報, vol. 21(4), pp. 490–493, Aug., 2003.
[11] E. Feron, “Robust Hybrid Control for Autonomous Vehicle Motion Planning,” Decision and Control, 2000. Proceedings of the 39th IEEE Conference on, vol. 1, pp. 821–826, 2000.
[12] J. Redding, J. N. Amin, and J. D. Boˇskovic, “A real-time obstacle detection and reactive path planning system for autonomous small-scale helicopters,” Proceedings of AIAA Guidance, Navigation and Control Conference, 2007.
[13] S. A. Bortoff, “Path Planning for UAVs,” Proceedings of the American Control Conference Chicago, pp. 364–368, June, 2000.
[14] Y. Kitamura, T. Tanaka, F. Kishino, and M. Yachida, “3-d path planning in a dynamic environment using an octree and an artificial potential field,” Proceedings of 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 474–481, Aug 5-9 1995.
[15] D. H. Shim, H. J. Kim, and S. Sastry, “Decentralized nonlinear model predictive control of multiple flying robots,” Proceedings of 42nd IEEE Conference on Decision and Control, pp. 3621–3626, Dec 9-12 2003.
[16] K. Y. and B. J., “Potential field methods and their inherent limitations for mobile robot navigation,” Proceedings of the IEEE Conference on Robotics and Automation, pp. 1398– 1404, April 7-12 1991.
[17] Y. X. Shibo Li, Xiuxia Sun, “Particle Swarm Optimization for Route Planning of Unmanned Aerial Vehicles,” Proceedings of the 2006 IEEE International Conference on Information Acquisition, Aug., 2006.
[18] 朱 凡, “採 用 粒 子 群 優 化 算 法 的 無 人 機 實 時 航 跡 規 劃,” Electronics Optics and Control, vol. 15(1), pp. 35–38, Jan., 2008.
[19] S. R. P. Chandler and M. Pachter, “UAV Cooperative Path Planning,” Proceedings of the Guidance, Navigation, and Control Conference, AIAA, 2000.
[20] 楊憲東, “多機會合最佳飛行軌跡規劃研究,” 行政院國家 科學委員會專題研究計畫, Feb., 2004.
[21] M. d. Berg, O. Cheong, M. v. Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications. Santa Clara, CA, USA: Springer-Verlag TELOS, 3rd ed. ed., 2008.
[22] J. Corbet, A. Rubini, and G. Kroah-Hartman, Linux 驅動程 式 (Linux Device Drivers, 3/e). O’REILLY, 2006.