跳到主要內容

臺灣博碩士論文加值系統

(44.221.66.130) 您好!臺灣時間:2024/06/24 05:08
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳柏宇
研究生(外文):Bo-Yu Chen
論文名稱:群組機器人路徑規劃及失效後之路徑補償研究
論文名稱(外文):Failure Robot Path Complementation for Robot Swarm Mission Planning
指導教授:李孟澤李孟澤引用關係
學位類別:碩士
校院名稱:國立虎尾科技大學
系所名稱:自動化工程系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:中文
論文頁數:80
中文關鍵詞:群組機器人路徑規劃失效路徑補償
外文關鍵詞:Robot SwarmPath ProgrammingFailure Complementation
相關次數:
  • 被引用被引用: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.
摘要....................................................i
Abstract...............................................ii
誌謝..................................................iii
目錄...................................................iv
表目錄................................................vii
圖目錄...............................................viii
符號表..................................................x
第一章 緒論..............................................1
1.1 研究背景.............................................1
1.2 研究動機與目的.......................................2
1.3 文獻回顧.............................................3
1.3.1 路徑規劃...........................................3
1.3.2 多代理人系統.......................................7
1.4 研究方法.............................................8
1.5 論文架構.............................................9
第二章 軟硬體及系統架構.................................10
2.1 硬體規格............................................11
2.1.1 Arduino Mega 2560................................12
2.1.2 1/10 SCALE SHORT COURSE TRUCK 遙控車............12
2.1.4 HMC5883L電子羅盤..................................13
2.1.3 全球定位系統(Global Position System)..............14
2.1.5 XBee無線數據傳輸系統..............................15
2.1.6 SD 卡儲存模組.....................................15
2.1.7 LCD 顯示模組......................................16
2.1.8 動力元件..........................................16
2.1.9 遠端控制站........................................17
2.2 軟體介紹............................................18
2.2.1 Arduino IDE (Arduino Integrated Development Environment)...........................................18
2.2.2 LAbVIEW 2014....................................18
2.3 無線數據傳輸系統....................................19
2.4 系統架構............................................20
2.4.1 自走車系統架構....................................20
2.4.2 遠端控制站系統架構................................21
2.5 載具與遠端控制站溝通機制與格式........................23
第三章 自動駕駛載具控制原理及載具........................26
3.1 自走車軟體控制......................................26
3.2 轉向系統............................................27
3.3 目標點判斷原理......................................28
第四章 自動路徑規劃及分配原理............................29
4.1 問題定義............................................29
4.2 A*搜尋法...........................................30
4.2.1 A*搜尋法原理......................................30
4.2.2 A*搜尋法執行步驟..................................30
4.3 禁忌演算法..........................................33
4.3.1 禁忌演算法原理....................................33
4.3.2 禁忌演算法(Tabu Search)執行步驟...................35
4.3.3 改良式禁忌演算法(Improved Tabu Search)............38
4.4 多載具路徑規劃之流程.................................41
4.3.1 建立轉折點(Establish Turning point)...............42
4.3.2 建立距離陣列(Establish Distance Array)............42
4.3.3 建構初始解(Establish Initial Solution)............42
4.3.4 路線途程改善(Improved path solution)..............44
4.3.5 插入轉折點(Insert Turning point)..................47
4.3.6 各路徑分派(Paths allocation)......................47
4.4 失效路徑補償........................................48
4.4.1 問題定義..........................................48
4.4.2 失效補償之對策與流程...............................49
第五章 實驗規劃與結果....................................51
5.1 電腦規劃結果測試....................................52
5.1.1 A*搜尋法避開禁行區測試.............................52
5.1.2 禁忌演演法收斂測試................................53
5.1.3 路徑規劃於不同案例之測試...........................53
5.1.4 失效補償測試......................................56
5.2 標竿試題測試與比較..................................58
5.2.1 Xu等人之試題......................................58
5.2.2 TSPLIB國際試題....................................58
5.2 實驗結果............................................60
5.2.1 實驗一:N=13,Dlmt=196.5 m.........................60
5.2.2 實驗二:N=13,Dlmt=185 m...........................62
5.2.3 實驗三(失效補償):N=20,Dlmt=230 m.................63
5.2.4 實驗四(失效補償) :N=20,Dlmt=340 m................65
5.3.5 最終實驗(失效補償及禁航區避讓):N=30,Dlmt=390 m .......................................................67
第六章 結論與未來展望....................................70
6.1 結論...............................................70
6.2 未來展望............................................71
參考文獻................................................72
Extended Abstract......................................75
Abstract...............................................75
簡歷(CV)...............................................80
[1] Luan Yichun, Xue Hongjun and Song Bifeng, “The Simulation of the Human-Machine Partnership in UCAV Operation,” College of Aeronautics, Northwestern Polytechnical University, Xi’an 710072, China, 7 Feb 2013.
[2] 萬年生,2016,”台灣首家無人機-跨國搶智慧農業千億商機”,今周刊,1023期,7月28日。
http://www.businesstoday.com.tw/article-content-80393-157085-%E5%8F%B0%E7%81%A3%E9%A6%96%E5%AE%B6%E7%84%A1%E4%BA%BA%E6%A9%9F%20%E8%B7%A8%E5%9C%8B%E6%90%B6%E6%99%BA%E6%85%A7%E8%BE%B2%E6%A5%AD%E5%8D%83%E5%84%84%E5%95%86%E6%A9%9F
[3] MoTuM,MoTuM AGV SOFTWARE,
http://www.motum.be/agv-software/#
[4] 蔡樸生,林盈灏,周利蔚,”結合轉折點偵測與 Dijkstra 演算法在最短路徑搜尋與應用”,Journal of China Institute of Technology,Vol. 28,2008。
[5] Peter E. Hart, “Nils J.Nilsson and Bertram Rapheal, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Trans. Syst. Sci. Cybern., Vol. 4, Issue. 2, 1968, pp.100-107.
[6] Richard M. Karp,“Reducibility Among Combinatorial Problems,” In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations,New York: Plenum, pp. 85–103.
[7] Solomon, M. M., 1983, “Vehicle Routing and Scheduling with Time Window Constraints: Models and Algorithms,” Ph.D. Dissertation, Dept. of Decision Sciences, University of Pennsylvania.
[8] Solomon, M. M., 1987, “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,” Operation Research, Vol. 35, pp. 254-265.
[9] Lin, S., 1965, “Computer Solutions of the Traveling Salesman Problem,” The Bell System Technical Journal, Vol. 44, pp. 2245-2269.
[10] 王春鎰,2005,”混合演化巨集啟發式解法 應用於具時間窗車輛路線問題之研究”,國立交通大學運輸科技與管理學系碩士論文。
[11] F. Glover, “Tabu search: Part I,” ORSA Journal of Computing, Vol. 1, No.3, pp. 190-206, 1989.
[12] F. Glover, “Tabu search: Part II,” ORSA Journal of Computing, Vol. 2, No.1, pp. 4-32, 1990.
[13] J.H.Holland, 1975, Adaptation in Natural and Artificial Systems, Univerity of MichiganPres, Ann Arbor.
[14] 徐嘉吟,黃士滔,2008,”蟻群演算法於宅配業路線最佳化之研究”,高雄應用科技大學工業工程與管理系碩士論文。
[15] 謝強,2016,”算法的”仿生學”:AI從生物上學到了什麼?”,科學人,3月14日,
http://www.guokr.com/article/441256/
[16] Majid Yousefikhoshbakht, Farzad Didehvar and Farhad Rahmati , “Modi_cation of the Ant Colony Optimization for Solving the Multiple Traveling Salesman Problem,” Romanian Journal of Information Science and Technology, Volume 16, Number 1, pp. 65-80, 2013.
[17] Raluca Necula, Mihaela Breaban, and Madalina Raschip, “Performance Evaluation of Ant Colony System For the Single-Depot Multiple Traveling Salesman Problem,” 10th International Conference on Hybrid Artificial Intelligence Systems, Bilbao Spain, Vol.9121, May 2015.
2
[18] Mingji Xu, Sheng Li and Jian Guo, “Optimization of Multiple Traveling Salesman Problem Based on Simulated Annealing Genetic Algorithm,” MATEC Web of Conferences, Zhengzhou, China, 100, Apr 2017.
[19] Jean-François Côté and Jean-Yves Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Private Fleet and Common Carrier,” European Journal of Operational Research, pp. 464-469, 2009.
[20] 廖彩雲,黃琬淑,以兩階段法求解即時需求物流配送問題之研究,資訊科技國際期刊,Vol. 2:1,June. 2008,pp. 76-94.
[21] 李孟澤,蔡博堯,賴來義,謝圓融,陳柏宇,2016,“無人地面載具之雙機自動路徑規畫系統”,中華民國航空太空學會學術演討會發表,高雄岡山,11月5日。
[22] Sanem Sariel-Talay, Tucker Balch and Nadia Erdogan, “Multiple traveling robot problem: A solution based on dynamic task selection and robust execution,” IEEE/ASME Trans. Mechatronics 14(2), pp. 198–206, 2009
[23] Multi-Agent System,多代理人系統,https://en.wikipedia.org/wiki/Multi-agent_system
[24] 陳禹銘,祝鈞毅,李雅萍,周子勤,2006,多工協調技術之應用與展望,機械工業雜誌,285期,工業技術研究院機械所,中2006年12月。
[25] Brian Paul Gerkey, August 2003, “On Multi-Robot Task Allocation,” Ph.D. Thesis, University of Southern California
[26] Harukazu Igarashi, “policy Gradient Method Using Fuzzy Controller in Policies and Its Application,” The International Conference on Artificial Intelligence and Pattern Recognition, Asia Pacific University of Technology & Innovation, Kuala Lumpur, Malaysia, 2014.
[27] 維基百科,RoboCup Middle Size League,
https://en.wikipedia.org/wiki/RoboCup_Middle_Size_League#/media/File:MSL_robocup_2006.jpg
[28] ebay,HMC5883L 3-Axis Digital Compass Module –Arduino Compatible,
http://www.ebay.com/itm/HMC5883L-3-Axis-Digital-Compass-Module-Arduino-Compatible-/281032742947
[29] ebay,Redcat Part 28446 550 19T Brushed Electric RC Motor Lightning Volcano Sandstorm,
http://www.ebay.com/itm/Redcat-Part-28446-550-19T-Brushed-Electric-RC-Motor-Lightning-Volcano-Sandstorm-/151953361159
[30] ebay,Hitec 112311 Servo HS-311,
https://www.ebay.com/p/Hitec-Servo-Hs-311-112311/642280773
[31] aliexpress,
https://ae01.alicdn.com/kf/HTB10EtTQVXXXXXkXXXXq6xXFXXXS/High-quality-IATA-7-4V-2600mAh-25C-2s-LiPo-font-b-Battery-b-font-For-font.jpg
[32] LabVIEW,維基百科,https://zh.wikipedia.org/wiki/LabVIEW
[33] Bektas, 2006, “The multiple traveling salesman problem: an overview of formulations and solution procedures,” Omega, 34(3), pp. 209-219.
[34] 楊明仁,模擬退火法結合禁忌搜尋法求解車輛回程途徑問題,2011,華梵大學資訊管理系碩士論文。
[35] 大圓距離,維基百科,
https://zh.wikipedia.org/wiki/%E5%A4%A7%E5%9C%86%E8%B7%9D%E7%A6%BB#cite_note-3
[36] Tang T. and Liu J., “Multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex,” European Journal of Operational Research, 24, pp. 267-282, 2000.
[37] Junjie P. and Dingwei W., “An ant colony optimization algorithm for multiple traveling salesman Problem,” ICICIC ’06: Proceedings of the First International Conference on Innovative Computing, IEEE Computer Society, Information and Control, pp. 210–213, Washington, DC, USA, 2006.
[38] Majid Yousefikhoshbakht and Mohammad Sedighpour, “A Combination of Sweep Algorithm and Elite Ant Colony Optimization for Solving the Multiple Traveling Salesman Problem,” Proceedings of the Romanian Academy A, Vol. 13, No. 4, pp. 295-302, 2012.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top