# 臺灣博碩士論文加值系統

(44.221.66.130) 您好！臺灣時間：2024/06/24 05:08

:::

### 詳目顯示

:

• 被引用:2
• 點閱:256
• 評分:
• 下載:0
• 書目收藏:1
 現今無人載具在環境探勘的應用已相當廣泛，人們利用無人載具去勘查幾個指定的危險地點，但單一無人載具往往受到電量限制而無法完成大量的任務，以及失效後無能遞補其任務。因此我們派多載具完成大量的任務，並且試圖規劃其路線，達成短時間、短距離、低燃料消耗等，避免路線上做不必要的浪費，以及失效後之任務能由其餘車輛進行補償並且避開禁行區。對於這種大型的數學模型問題，若需要在合理的時間求得最佳解是一件非常困難的事情，所以一般都以啟發式演算法來求得一個近似解，故本研究將採用A^* 搜尋法及二階段架構之禁忌演算法，首先，於建立距離陣列時採用A^*搜尋法尋求避開禁行區之替代路徑，接著採用二階段禁忌演算法，先對所有目標點規劃單一最佳路線，並將其路線分割求得初始解，再利用禁忌演算法結合2-Opt節線交換法進行各路線間及路線內之改善，使其趨近最佳解，已達成上述的目的，再將規劃的路線以自走車進行實驗。實驗過程中，若有自走車失效，將由遠端控制站重新規劃最佳路徑，將失效車路徑由其餘車輛進行補償，提供給正在進行之自走車，直到所有目標點均拜訪一次即任務完成。前述理論與實驗，均已成功地驗證完成。
 Unmanned vehicle is applied widely in environmental explorations nowadays, especially for the tasks where human beings are not able to reach. Due to limited capacities like power supply, it is almost impossible for any single one unmanned vehicle to complete a large assignment with multiple designated location to visit. As well as failure robot task won’t complemented when each car failing. Therefore, multiple unmanned vehicles (Multi-Agent System, MAS) are required as well as the well-planned routes to minimize unnecessary consumption and waste on time, distance and energy/fuels needed. In addition, robot cars are able to avoid no-travel zone and the task of failure robot was complemented by the other. Same as other large mathematic model, heuristic algorithm was used to obtain an approximate solution within a reasonable timeline for this research. First, establish distance array. If any two points through the no-travel zone, use A^* algorithm to find the alternative path to avoid no-travel zone. Then, a two-phase architecture was applied. In the 1st phase, Tabu search and 2-Opt exchange method were used to figure out the optimal path for visiting all target nodes, and then the initial solution by splitting it into multiple clusters. In the 2nd phase, the algorithm was used with 2-Opt path exchange were used to improve the in-route and cross-route solutions. Diversification strategy was adopted to approach the global optimal solution rather than a regional one. Once the objectives mentioned above were accomplished, we dispatched several robot cars to operate simultaneously on the routes we planned ahead. If one of the autonomous cars failing, new path will be programmed and reassigned to autonomous car of remaining by the ground station. until all the target points are visited. In the end, computer simulations and real vehicle had been accomplished in this research.
 摘要....................................................iAbstract...............................................ii誌謝..................................................iii目錄...................................................iv表目錄................................................vii圖目錄...............................................viii符號表..................................................x第一章 緒論..............................................11.1 研究背景.............................................11.2 研究動機與目的.......................................21.3 文獻回顧.............................................31.3.1 路徑規劃...........................................31.3.2 多代理人系統.......................................71.4 研究方法.............................................81.5 論文架構.............................................9第二章 軟硬體及系統架構.................................102.1 硬體規格............................................112.1.1 Arduino Mega 2560................................122.1.2 1/10 SCALE SHORT COURSE TRUCK 遙控車............122.1.4 HMC5883L電子羅盤..................................132.1.3 全球定位系統(Global Position System)..............142.1.5 XBee無線數據傳輸系統..............................152.1.6 SD 卡儲存模組.....................................152.1.7 LCD 顯示模組......................................162.1.8 動力元件..........................................162.1.9 遠端控制站........................................172.2 軟體介紹............................................182.2.1 Arduino IDE (Arduino Integrated Development Environment)...........................................182.2.2 LAbVIEW 2014....................................182.3 無線數據傳輸系統....................................192.4 系統架構............................................202.4.1 自走車系統架構....................................202.4.2 遠端控制站系統架構................................212.5 載具與遠端控制站溝通機制與格式........................23第三章 自動駕駛載具控制原理及載具........................263.1 自走車軟體控制......................................263.2 轉向系統............................................273.3 目標點判斷原理......................................28第四章 自動路徑規劃及分配原理............................294.1 問題定義............................................294.2 A*搜尋法...........................................304.2.1 A*搜尋法原理......................................304.2.2 A*搜尋法執行步驟..................................304.3 禁忌演算法..........................................334.3.1 禁忌演算法原理....................................334.3.2 禁忌演算法(Tabu Search)執行步驟...................354.3.3 改良式禁忌演算法(Improved Tabu Search)............384.4 多載具路徑規劃之流程.................................414.3.1 建立轉折點(Establish Turning point)...............424.3.2 建立距離陣列(Establish Distance Array)............424.3.3 建構初始解(Establish Initial Solution)............424.3.4 路線途程改善(Improved path solution)..............444.3.5 插入轉折點(Insert Turning point)..................474.3.6 各路徑分派(Paths allocation)......................474.4 失效路徑補償........................................484.4.1 問題定義..........................................484.4.2 失效補償之對策與流程...............................49第五章 實驗規劃與結果....................................515.1 電腦規劃結果測試....................................525.1.1 A*搜尋法避開禁行區測試.............................525.1.2 禁忌演演法收斂測試................................535.1.3 路徑規劃於不同案例之測試...........................535.1.4 失效補償測試......................................565.2 標竿試題測試與比較..................................585.2.1 Xu等人之試題......................................585.2.2 TSPLIB國際試題....................................585.2 實驗結果............................................605.2.1 實驗一：N=13,Dlmt=196.5 m.........................605.2.2 實驗二：N=13,Dlmt=185 m...........................625.2.3 實驗三(失效補償)：N=20,Dlmt=230 m.................635.2.4 實驗四(失效補償) ：N=20,Dlmt=340 m................655.3.5 最終實驗(失效補償及禁航區避讓)：N=30,Dlmt=390 m .......................................................67第六章 結論與未來展望....................................706.1 結論...............................................706.2 未來展望............................................71參考文獻................................................72Extended Abstract......................................75Abstract...............................................75簡歷(CV)...............................................80