臺灣博碩士論文加值系統

隨著科技發展，無人機應用領域（UAVs）的研究和設計也越來越成熟。由於具備不受地形阻礙、輕鬆涉入險峻地勢等優勢，無人機已被廣泛應用於各類領域。然而，如何找到最佳路徑仍然是一個未解決的問題；舊有的演算法中，找尋到的路徑通常是部分最佳解，或是因障礙物位置關係，使得飛行器困在某個區域，而規劃不出到達目標的路徑。本論文提出了一種基於斜面最低點搜索法（Ramp Lowest Point Search Method）的新型最優劃路徑規劃，以尋找從空間中任意點到目標的路徑。透過斜面最低點搜索法，無人機將自動規劃從起點至終點的路徑，而無需進行複雜的計算。所提出的方法避免了飛行器受困於特定陷阱區的問題，並且可以實現自我校正功能，提供最短、最佳化的飛行路徑。
透過Matlab進行演算法路徑模擬，計算飛行路徑，同時與其他演算法比較之間差異優劣，所提出的方法確實能完成最佳路徑的規劃。最後實際套用至無人機，實際驗證演算法，執行由斜面最低點搜索法所規劃之飛行路徑。

With the ever-changing nature of technology, the research of unmanned aerial vehicles (UAVs) is more popular recently. The unmanned aerial vehicles are generally applied in all kinds of area because they are not easily obstructed by the terrain and easy to move into steep terrain. However, how to find the optimal path is still an unsolved issue. In the existing algorithms, the UAVs tend of find local optimal solution, or the aircraft is trapped in a certain area make route planning failed because the position of the obstacle. In this paper, a novel optimal route planning based on ramp lowest point search method (RLPS) is proposed to find the route from any point in the space to the target. By applying the RLPS method, the path from the starting point to the end point will be planned automatically without complicated calculations. The proposed method will not only achieve self-correct function but also provide the shortest and optimal path.

摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究方法 4
1.4 論文架構簡介 6
第二章 無人機基本介紹與應用 7
2.1 無人機之簡介與應用 7
2.2 多軸機之介紹與特性及應用 8
2.3 路徑規劃演算法之原理與探討 9
2.3.1 路徑規劃演算法分類 9
2.3.2 A*演算法(A Star algorithm) 10
2.3.3 人工勢場法(Artificial Potential Field method) 11
2.3.4 梯度下降法Gradient descent 12
2.4 路徑優劣分析 13
第三章 斜面最低點搜索法之理論與實施比較 14
3.1 斜面最低點搜索法之理論 14


3.1.1 斜面部分之地圖建置 15
3.1.2 機體路徑規劃部分 19
3.1.3 路徑除錯與路徑優化部分 21
3.2 斜面最低點搜索法之模擬實施 24
3.2.1地圖模型建置 24
3.2.2斜面地圖與障礙物模型建置 26
3.2.3路徑搜索 31
3.2.4除錯機制與自動優化 31
3.3 斜面最低點搜索法與現今演算法比較 33
3.3.1人工勢場法所規劃之路徑 34
3.3.2 A*演算法所規劃之路徑 35
3.3.3斜面最低點搜索法所規劃之路徑 36
3.3.4綜合比較 37
3.4 斜面最低點搜索法實際用於無人機之表現 39
3.4.1無人機硬體規格 39
3.4.2地圖建置與障礙物標記 44
3.4.3套用演算法計算規劃路徑 47
3.4.4將路徑匯入APM飛控板並執行路徑 48
3.4.5與其他方法所規劃之路徑比較 50
第四章 結論 53
參考文獻 54
附錄 59

[1] G. Wild and G. Baxter, "Tech issues cause most drone accidents: research," RMIT University Research, Melbourne, 2016.
[2] P. Li and H. Duan, Path planning of unmanned aerial vehicle based on improved gravitational search algorithm, vol. 55, SP Science China Press, May 2012.
[3] J. Lerner, D. Wagner and K. Zweig, Algorithmics of Large and Complex Networks, 1 ed., Berlin Heidelberg: Springer-Verlag, 2009, pp. 7-139.
[4] 逍遙文, "逍遙文工作室-A興搜尋演算法(A* Search Algorithm)," 逍遙文工作室, December 2001. [Online]. Available: https://cg2010studio.com/2011/12/20/a%E6%98%9F%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95-a-search-algorithm/.
[5] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Section 24.3: Dijkstra's algorithm, MIT Press and McGraw–Hill, January 2001, pp. 595-601.
[6] O. Khatib,, "Real-Time Obstacle Avoidance for Manipulators," IEEE International Conference on Robotics and Automation, vol. 5, pp. 500-505, March 1985.
[7] X. G. Wu, S. P. Gong and P. Xie, "Local Path Planning Based on Improved Artificial Potential Field Using Fuzzy Repulsion Force for Robot," Journal of Electrical Engineering, vol. 2, pp. 48-60, September 2014.
[8] Y. Zhang, Z. Liu and L. Chang, "A New Adaptive Artificial Potential Field and Rolling Window Method for Mobile Robot Path Planning," in 2017 29th Chinese Control And Decision Conference (CCDC), Chongqing, China, May 2017.
[9] A. Group, "UAVによる次世代測量技術とは," Andoh Group, March 2014. [Online]. Available: http://www.kkandoh.co.jp/service/newsurveytechnology.html.
[10] M. C. D. Simone , Z. B. Rivera and D. Guida, "Obstacle Avoidance System for Unmanned Ground Vehicles by Using Ultrasonic Sensors," Machines 2018, pp. 2-13, April 2018.
[11] M. Naruse, K. Yamamoto, K. Sekiguchi, and K. Nonaka, "Verification of Coverage Control for Multi-Copter with Local Optimal Solution Avoidance and Collision Avoidance Using Random-walk and Artificial Potential Method," pp. 440-445, September 2017.
[12] 人機與認知實驗室, "雷鋒網-掃地機器人是怎麼做路徑規劃的," June 2016. [Online]. Available: https://www.leiphone.com/news/201606/p4rtD88yiYVQT6F9.html.
[13] 江任捷, "演算法筆記-Path," 2003. [Online]. Available: http://www.csie.ntnu.edu.tw/~u91029/Path.html.
[14] P. Yao, H. Wang and Z. Su, "UAV feasible path planning based on disturbed fluid and trajectory propagation," Chinese Journal of Aeronautics, vol. 28, pp. 1163-1177, August 2015.
[15] M. F. Othman, M. Samadi, and M. H. Asl, "Simulation of Dynamic Path Planningfor Real-Time Vision-Base Robots," Springer, vol. 376, pp. 1-10, August 2013.
[16] "dijkstra algorithm-A* algorithm gif," [Online]. Available: https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95.
[17] H. Robbins and S. Monro, "A Stochastic Approximation Method," The Annals of Mathematical Statistics, vol. 22, p. 400, 1951.
[18] J. Barzilai and J. M. Borwein, "Two-Point Step Size Gradient Methods," IMA Journal of Numerical Analysis, vol. 8, pp. 14-148, January 1988.
[19] "Gradient descent," [Online]. Available: https://upload.wikimedia.org/wikipedia/commons/7/79/Gradient_descent.png.
[20] C. Anderson, "DIY DRONES," January 2008. [Online]. Available: https://diydrones.com/profiles/blogs/hackhawk-hacking-the-altair-aerial-blackhawk-with-your-own-flight.
[21] 迅雷創新, "迅雷創新," 迅雷創新, 2008. [Online]. Available: http://doc.cuav.net/tutorial/copter/first-setup/connect/mission-planner/flight-plan.html.
[22] 李威宏, "空拍機原理及法規," 2018.
[23] I. Hobby, "Infinity-Hobby 你也能看見台灣-無人機空拍入門," March 2008. [Online]. Available: http://infinityhobby.blogspot.com/?view=flipcard.
[24] RadioLink, "R9DS," 2014. [Online]. Available: https://www.robotshop.com/media/files/pdf/radiolink-r9ds-10-ch-24ghz-dsss-fhss-receiver-datasheet.pdf.
[25] RadioLink Eletornic Limted, "RadioLink AT9 Instruction Manual," October 2014. [Online]. Available: http://www.radiolink.com.cn/doce/UploadFile/ProductFile/2014101549866685.pdf.
[26] RadioLink, "One of the fastest remote control as so far," [Online]. Available: http://radiolink.com.cn/doce/product-detail-89.html.
[27] RadioLink, "RadioLink航模遙控器與航模軟硬件方案提供商," [Online]. Available: http://www.radiolink.com.cn/docc/product-detail-128.html.
[28] BP Hobbies LLC, "Cheetah HW30A Brushless ESC Data sheet," BP Hobbies LLC, [Online]. Available: https://www.bphobbies.com/pdf/bp/esc_2015/bp-hw30a-esc-2015.pdf.
[29] u-blox, "NEO-7 u-blox 7 GNSS modules Data Sheet," November 2014. [Online]. Available: https://www.u-blox.com/sites/default/files/products/documents/NEO-7_DataSheet_%28UBX-13003830%29.pdf.
[30] Robu.in, "Robu.in Demystifying Robotics," 2018. [Online]. Available: https://robu.in/product/ublox-neo-7m-gps-compass/.