- 學位論文
群組機器人路徑規劃及失效後之路徑補償研究
Failure Robot Path Complementation for Robot Swarm Mission Planning
摘要
現今無人載具在環境探勘的應用已相當廣泛，人們利用無人載具去勘查幾個指定的危險地點，但單一無人載具往往受到電量限制而無法完成大量的任務，以及失效後無能遞補其任務。因此我們派多載具完成大量的任務，並且試圖規劃其路線，達成短時間、短距離、低燃料消耗等，避免路線上做不必要的浪費，以及失效後之任務能由其餘車輛進行補償並且避開禁行區。對於這種大型的數學模型問題，若需要在合理的時間求得最佳解是一件非常困難的事情，所以一般都以啟發式演算法來求得一個近似解，故本研究將採用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.