臺灣博碩士論文加值系統

本研究改進群組無人機的路徑規劃演算法，將無人機機群的涵蓋範圍與存在多個禁航區的情況納入禁航區避讓之考量，並於演算法中加入D*Lite演算法 (Dynamic ????∗ Algorithm)，使無人機執行任務中若遭遇障礙物能即時對障礙物進行避讓。同時本研究改變以往透過地面導控站對群組無人機進行控制的任務模式，使群組無人機可以自行分配欲飛行之路徑且自主前往各個目標點。
群組無人機的任務規劃，將先透過兩階段式禁忌搜尋法(Tabu Search)搭配2-Opt交換法和????∗搜尋法(????∗ Search Algorithm)，以距離作為成本函數(Cost Function)進行路徑規劃，接著根據無人機機群範圍增加禁航區避讓轉折點，使僚機於任務中不會誤入禁航區，亦將複數禁航區加入任務規劃考量，使無人機在執行範圍更遠的任務時避開所有可能跨越的禁航區；在無人機循規畫路徑飛行的同時，反覆更新地圖信息，透過D* Lite演算法(Dynamic ????∗ Algorithm)，使無人機在任務執行中遇到未知障礙物時透過逆向搜索達，即時重規劃出由目標至無人機當前位置的最佳路線。
為了提升無人機在執行任務上的自主性、降低通訊距離所帶來的任務距離限制，藉由整合嵌入式運算系統將以往需藉地面導控站來執行群組無人機任務的集中式運算架構改為透過邊緣運算使群組無人機自主完成任務的分散式運算架構，完成路徑規劃後，群組無人機能自主前往最合適的路線完成任務。

To improve the path planning algorithm for UAV swarm by adding the coverage area of multi-UAVs’ flight formation and take a multitude of no-fly zones into consideration. In addition, apply D* Lite algorithm for dynamic obstacle avoidance when drone is flying a mission. Furthermore, the study discard using UAVs’ ground control system, in the past, we control UAV swarm to execute various task through ground control system, but now the drones will assign the task route autonomously and make each drone finish a mission by itself.
The dynamic path programming problem for UAV swarm mission use the 2-phase Tabu search with 2-Opt exchange method and ????∗ search as the path programming algorithm, let distance as a cost function for path programming, then increase and expand the turning-points of no-fly zones base on drone fleet coverage, to keep wing drone from barge in prohibited area. Besides, I take plural no-fly zones into account, it’s different from usual that we consider only one no-fly zone on the map. So, now we can make UAV swarm expand task area and avoid all of no-fly zones which probably be crossed by. If drone found an obstacle while flying along with the route which planning by algorithm, it will update the map information immediately and re-planning the optimal path in time from the goal to the current position of drone as reverse search by D* Lite algorithm.
To improve the autonomous drone while execute the mission, we lower the distance restriction from wireless communication. We make the drone integrate with the embedded computation system to change centralized computing architecture into distributed computing architecture, this make each drone can not only fly a mission without ground control system but also can autonomously plan the mission route on the drone. Finally, the drones will assign the best mission routes and fly along with it autonomously.

摘要......i
Abstract......ii
誌謝......iii
目錄......iv
表目錄......vi
圖目錄......vii
符號說明......ix
第一章
緒論......1
1.1 研究背景......2
1.2 研究動機......2
1.3 研究目的......5
1.4 論文架構......5
第二章
文獻探討......7
2.1 路徑規劃演算法......7
2.2 無人機之自主任務執行與即時任務路徑重劃......9
2.3 無人機導控系統開發......11
第三章
研究內容與方法......12
3.1 群組無人機系統架構......12
3.2 硬體介紹與整合......13
3.2.1 DJI F450機架......13
3.2.2 Pixhawk 4飛行控制器......14
3.2.3 Jetson Xavier NX邊緣計算系統......17
3.2.4 XBee無線通訊模組......18
3.2.5 無線控制系統......18
3.2.6 全球定位系統......19
3.2.7 電源系統......20
3.2.8 動力系統......21
3.3 開發環境介紹......22
3.4 地面監視系統......23
3.5 群組無人機路徑規劃......24
3.5.1 禁忌搜尋法原理......24
3.5.2 禁忌搜尋法流程......25
3.6 禁航區避讓......27
3.6.1 A*搜尋演算法原理......28
3.6.2 禁航區避讓流程......29
3.7 群組無人機自主任務派遣......30
3.7.1 DroneKit無人機控制函式庫......30
3.7.2 MAVProxy命令式地面站......31
3.7.3 演算法轉譯......31
3.7.4 D*Lite動態規劃演算法......33
3.7.5 任務發送與接收......35
第四章
實驗規劃與結果......36
4.1 實驗規劃......36
4.2 演算法效益......38
4.2.1 路徑規劃演算法效益測試......38
4.2.2 長僚機群避讓禁航區效果測試......41
4.2.3 多禁航區避讓演算結果測試......43
4.3 單台無人機......44
4.3.1 自主飛行模擬與實驗......44
4.3.2 動態避讓效果模擬......45
4.4 三台無人機......46
4.4.1 自主飛行任務模擬......46
4.4.2 自主飛行任務(含動態避讓)模擬與實驗......47
4.4.3 模擬與實驗比較......50
第五章
結論與建議......52
5.1 結論......52
5.2 建議......53
參考文獻......54
Extended Abstract......56

[1] 陳柏宇 ，，“群組機器人路徑規劃及失效後之路徑補償研究 國立虎尾
科技大學自動化工程系碩士論文 2017。
[2] 吳盛佑 ，，“群組無人機 4維任務規劃 系統建立 國立虎尾科技大學自動
化工程系碩士論文 2019。
[3] 莊明龍 ，，“4G-LTE 群組無人機系統建立 國立虎尾科技大學自動化工
程系碩士論文 2018。
[4] National Aeronautics and Space Administration (NASA) website What is Unmanned Aircraft System Traffic Management
https://www.nasa.gov/ames/utm [5] United States Air Force, “Small Unmanned Aircraft Systems (SUAS) Flight Plan: 2016–2036”, Defense Technical Information Center, 2016.
[6] Halit Ergezer, Kemal Leblebicioğlu, “Path Planning for Multiple Unmanned Aerial Vehicle”, IEEE, 2012.
[7] Jeong-Won Lee, Bruce Walker, Kelly Cohen “Path Planning of Unmanned Aerial Vehicles in a Dynamic Environment”, Infotech@Aerospace Confer-ence, 2011.
[8] Khalid Al-Mutib, Mansour Alsulaiman, Muhammad Emaduddin, Hedjar Ramdane, Ebrahim Mattar, “D* Lite Based Real-Time Multi-Agent Path Planning in Dynamic Environments”, International Journal of Engineering Research and Applications, Vol. 2, 2012.
[9] Sven Koenig, Maxim Likhachev, David Furcy, “Lifelong Planning A*”, Computer Science Department, University of Southern California, Los Ange-les, 2001.
[10] Anthony Stentz, “Optimal and Efficient Path Planning for Partially-known Environments”, IEEE International Conference on Robotics and Automation, 1994. [11] Sven Koenig, Maxim Likhachev, “D* Lite”, College of Computing, Georgia Institute of Technology, Atlanta, 2002.
[12] Steven M. LaValle, “Rapidly-Exploring Random Trees : A New Tool for Path Planning”, Department of Computer Science, Iowa Stare University, Ames, 1998. [13] Anthony Stentz, “The Focussed D* Algorithm for Real-Time Replanning”, International Joint Conference on Artificial Intelligence, 1995.
[14] Shigeru Tsubakitani, James R. Evans, “Optimizing tabu list size for the trav-eling salesman problem”, Computers & Operations Research, 1998.
[15] Alfonsas Misevicius, “Using iterated tabu search for the traveling salesman problem”, Information Technology and Control, 2004.
[16] 廖彩雲，黃琬淑，以兩階段法求解即時需求物流配送問題之研究，資
訊科技國際期刊， Vol. 2:1 June. 2008 pp. 76-9 [17] 黃玟翔 ，，“群組無人機之多群任務分派及禁航區避讓 國立虎尾科技
大學自動化工程系碩士論文 2020。
[18] Anjan Chakrabarty, Vahram Stepanyan, Kalmanje Krishnakuma, “Real-Time Path Planning for Multi-copters flying in UTM -TCL4”, AIAA, Autonomous Small UAS Urban Flight II , 2019.
[19] Anjan Chakrabarty, Corey A.Ippolito, “Autonomous Flight for Multi-copters flying in UTM –TCL4+ sharing common airspace”, AIAA, 2020.
[20] Quadcopter Garage DJI F450機架圖 片
http://quadcoptergarage.com/dji-flame-wheel-f450-review/
[21] PX4官方 網站 Pixhawk 4飛控制器接口說明 圖 片
https://docs.px4.io/v1.11/zh/flight_controller/pixhawk4.html
[22] Bosch Sensortec官方網站， BMI055六軸姿態感測器 圖片和規格
https://www.bosch-sensortec.com/products/motion-sensors/imus/bmi055/
[23] TE官方網站， MS5611氣壓高度計 圖片
https://www.te.com/usa-en/product-CAT-BLPS0036.html
[24] 意法半導體 LSM303D電子羅盤 圖片
https://www.st.com/en/mems-and-sensors/lsm303d.html
[25] U-blox官方網站， NEO-M8N 全球定位 模組 規格
https://www.u-blox.com/en/product/neo-m8-series
[26] T-motor官方網站， T-motor Air 2216 KV880馬達 規格
https://store.tmotor.com/goods.php?id=727
[27] F. Glover, “Tabu search: Part I,” ORSA Journal of Computing, Vol. 1, No.3, pp. 190-206, 1989.
[28] F. Glover, “Tabu search: Part II,” ORSA Journal of Computing, Vol. 2, No.1, pp. 4-32, 1990.
[29] PyPy官方網站， PyPy優點與功能介紹，
https://www.pypy.org/
[30] Cython官方網站，關於 Cython
https://www.cython.org/