簡易檢索 / 詳目顯示

研究生: 魏楷燁
Wei, Kai-Yeh
論文名稱: 使用分散式計算之室內環境探索機器人
An Indoor-Exploration Mobile Robot Using Distributed Computing
指導教授: 王偉彥
Wang, Wei-Ten
許陳鑑
Hus, Chen-Chien
學位類別: 碩士
Master
系所名稱: 電機工程學系
Department of Electrical Engineering
論文出版年: 2017
畢業學年度: 105
語文別: 中文
論文頁數: 80
中文關鍵詞: 環境探索路徑規劃機器人作業系統Gmapping運動學控制器
英文關鍵詞: Gmapping, frontier-based exploration, Robot Operating System
DOI URL: https://doi.org/10.6345/NTNU202202869
論文種類: 學術論文
相關次數: 點閱:99下載:2
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 本論文提出一台以機器人作業系統(ROS)架構下 Gmapping結合環境探索和路徑規劃之機器人的設計與實現,使機器人能在未知環境中自主運用環境探索演算法、路徑規劃演算法和運動學控制器探索環境,並在探索環境的同時使用 Gmapping 建置二維平面地圖,使之完成自主探索環境並建置地圖的功能。環境探索演算法中使用的是本論文提出的「分群式邊界偵測法」,使機器人能先把周圍環境探索完畢後才繼續探索新的環境。而路徑規劃使用的的是本論文提出的「改良權重A*演算法」,能使機器人避開障礙物且規劃完整的路徑。由於本實驗室想設計一個輕量化的設備來取代笨重的電腦,但速度卻不會比電腦慢太多的方法,所以採用機器人作業系統(ROS)架構實作在多塊 Udoo Quad 板上,其分散式架構剛好符合要求,能把系統的架構分散開來,使單一程序可以完全使用一個 Udoo 板的效能。為了驗證系統的性能與效能,本論文利用室內環境進行諸多實驗,而由實驗結果可知,本論文設計的機器人導航系統確實能達到分散式處理之輕量化之導航與探索功能的目的。

    In this paper, a system integration of Gmapping, environmental exploration and path planning is provided based on Robot Operating System (ROS) and multiple Udoo single board computers in order to develop a mobile navigation robot. As such, the robot is capable of navigating in an unknown indoor environment using light-weight, low-cost, and high-computing platforms. To estimate the robot pose as well as building a top-view map, Gmapping is used due to its robust performances. Moreover, a clustering and frontier-based exploration method is proposed such that the robot is able to efficiently explore nearby environments before moving to newly observed ones. As for path planning, an improved A* algorithm is proposed to provide an optimal path without colliding with obstacles. To effectively operate the overall navigation system, a distributed computing system using ROS is designed so that algorithms can perform in parallel without decreasing the efficiencies of Udoos. To verify the performances of the proposed navigation system, various experiments are conducted, and experimental results show that the robot can reliably navigate and explore an unknown indoor environment.

    中文摘要 i 英文摘要 ii 誌  謝 iii 目  錄 iv 圖 目 錄 vi 表 目 錄 vii 第一章 緒論 1 1.1 研究背景與動機 1 1.2 文獻探討 2 1.3 論文架構 4 第二章 相關研究方法回顧 5 2.1 機器人作業系統 5 2.2 Gmapping 8 2.3 A*路徑規劃演算法 9 2.4 基於邊緣偵測的環境探索 17 2.5 連通元件標記法 21 2.6 機器人運動學控制器 22 2.6.1 輪型機器人之運動學模型 22 2.6.2 運動學控制器 23 第三章 改良權重A*路徑規劃算法 28 3.1 改良權重A*路徑規劃演算法 28 第四章 分群frontier-based環境探索方法 38 4.1 基於連通法的分群方法 38 4.2 frontier選取方法 40 4.3 分群frontier-based環境探索方法 42 第五章 室內環境探索機器人之設置 47 5.1 系統架構 47 5.2 硬體介紹 49 5.3 完整流程 54 第六章 實驗結果 57 6.1 實驗環境介紹 57 6.2 改良權重A*路徑規劃演算法模擬實驗結果 58 6.2.1 模擬實驗一結果 59 6.2.2 模擬實驗二結果 61 6.2.3 模擬實驗討論 64 6.3 分群frotier-based環境探索方法模擬實驗結果 64 6.3.1 模擬實驗一結果 65 6.3.2 模擬實驗二結果 66 6.3.3 模擬實驗討論 68 6.4 室內環境探索機器人之實作實驗結果 68 6.4 實驗討論 72 第七章 結論與未來展望 73 7.1 結論 73 7.2 未來展望 73 參考文獻 74 自傳 78 學術成就 80

    [1] http://www.roombavac.com.tw/
    [2] http://www.sks.com.tw/
    [3] http://www.yks.com.tw/news/142
    [4] R. Reid, A. Cann, C. Meiklejohn, L. Poli, A. Boeing, and T. Braunl, “Cooperative Multi-Robot Navigation, Exploration,Mapping and Object Detection with ROS,” IEEE Intelligent Vehicles Symposium, Australia, 2013, pp. 1083-1088.
    [5] Parker, and Lynne E. “Multiple mobile robot systems,” Springer Handbook of Robotics, Springer Berlin Heidelberg, 2008, pp 921-941.
    [6] S. Oßwald, M. Bennewitz, and W. Burgard, C. Stachniss, “Speeding-Up Robot Exploration by Exploiting Background Information,” IEEE Robotics and Automation Letters, July 2016, vol. 1, pp. 716-723.
    [7] C. Zhu1, R. Ding, M. Lin, and Y. Wu, “A 3D frontier-based exploration tool for MAVs,” Tools with Artificial Intelligence (ICTAI), 2015 IEEE 27th International Conference on, China, Nov. 2015, pp. 348-352.
    [8] E. Uslu, F. Çakmak, M. Balcilar, A. Akinci, M. F-. Amasyali, and S. Yavuz, “Implementation of Frontier-Based Exploration Algorithm for an Autonomous Robot,” Innovations in Intelligent SysTems and Applications (INISTA), 2015 International Symposium on, Turkey, Sept. 2015.
    [9] H. I-. M-. A-. Omara, and K. S-. M-. Sahari, “Indoor Mapping using Kinect and ROS,” Agents, Multi-Agent Systems and Robotics (ISAMSR), 2015 International Symposium on, Malaysia, Aug. 2015, pp. 110-116.
    [10] 簡江恆,”視覺型同時定位與建圖系統及其在FPGA上的實現”,臺灣師範大學電機工程學系,碩士論文,民國106年。
    [11] http://www.ros.org/
    [12] http://wiki.ros.org/gmapping
    [13] A. Doucet, N. de Freitas, K. Murphy, and S. Russell,” Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks,” In Proc. of the Conf. on Uncertainty in Artificial Intelligence (UAI2000), 2000.
    [14] R.C. Smith, and P. Cheeseman, “On the Representation and Estimation of Spatial Uncertainty,” The International Journal of Robotics Research, vol. 5, no. 4, 1986, pp. 56-68.
    [15] G. Grisetti, C.Stachniss, and W. Burgard, ”Improving Grid-based SLAM with Rao-Blackwellized Particle Filters by Adaptive Proposals and Selective Resampling,” Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on, Barcelona, April 2005, pp. 2432-2437.
    [16] G. Grisetti, C.Stachniss, and W. Burgard, ”Improved Techniques for Grid Mapping
    with Rao-Blackwellized Particle Filters,” IEEE Transactions on Robotics, vol. 23, no. 1, Feb. 2007, pp. 34-46.
    [17] W. Zeng, and R. L. Church, “Finding shortest paths on real road networks: the case for A*,” International Journal of Geographical Information Science, vol. 23, no.4, 2009, pp. 531-543.
    [18] J. Yao, C. Lin , X. Xie, A. J-. Wang, and C. Hung, ” Path Planning for Virtual Human Motion Using Improved A* Algorithm,” Information Technology: New Generations (ITNG), 2010 Seventh International Conference on, 2010, pp. 154-1158.
    [19] C. Wang, L. Wang, J, Qin, Z. Wu, L. Duan, Z. L-. M-. Cao, X. Su, W. Li, Z. Lu, M. Li, Y. Wang, J. Long, M. Huang, and Y. Li, Q. Wang, “Path Planning of Automated Guided Vehicles Based on Improved A-Star Algorithm,” Information and Automation, 2015 IEEE International Conference on, China, Aug. 2015, pp. 2071-2076.
    [20] E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematlk, vol. 23, no. 1, 1959, pp269-271.
    [21] E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens, “On-the-fly Garbage Collection: an Exercise in Cooperation,” Comm. of the ACM, vol. 21, no. 11, 1978, pp. 966-975.
    [22] N. Jasika, N. Alispahic, A. Elma, K. Ilvana, L. Elma, and N. Nosovic, “Dijkstra's shortest path algorithm serial and parallel execution performance analysis,” MIPRO, Proc. of the International Convention, Opatija, May 2012, pp. 1811-1815.
    [23] I. Pohl, “First results on the effect of error on heuristic search,” Machine Intelligence, vol. 5, 1970, pp. 219-236.
    [24] P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, July 1968, pp. 100-107.
    [25] B. Yamauchi, “Frontier-Based Exploration Using Multiple Robots,” In Agents-98, 1998, pp. 47-53.
    [26] B. Yamauchi, “A frontier-based approach for autonomous exploration,” In Proc. of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation, Moterey, CA, July 1997, pp. 146-151.
    [27] M. Keidar, and G. A. Kaminka, “Robot Exploration with Fast Frontier Detection:Theory and Experiments,” In Proc. AAMAS, 2012, pp. 113-120.
    [28] E.-H. Guechi, J. Lauber, M. Dambrine, and M. Defoort,” Brief Paper Output feedback controller design of a unicycle-type mobile robot with delayed measurements,” IET Control Theory and Applications, vol. 6, no. 5, March 2012, pp. 726-733.
    [29] C. D. L. Cruz, and R. Carelli, “Dynamic Modeling and Centralized Formation Control of Mobile Robots,” The 32nd Annual Conference on IEEE Industrial Electronics, Paris, Nov. 2006, pp. 3880-3885.
    [30] T. Fukao, H. Nakagawa, and N. Adachi, “Adaptive Tracking Control of a Nonholonomic
    Mobile Robot,” IEEE Transactions on Robotics and Automation, vol. 16, no. 5, Oct 2000, pp. 609-615.
    [31] Y. Ke, and R. Sukthankar, “PCA-SIFT: a more distinctive representation for local image descriptors,” in Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Washington, vol. 2, Jul. 2004, pp. 506–513.
    [32] L. Juan, and O. Gwun, “A comparison of SIFT, PCA-SIFT and SURF”, International Journal of Image Processing (IJIP), vol. 3, no. 4, Oct. 2009, pp. 143–152.
    [33] M. Calonder, V. Lepetit, M. Ozuysal, T. Trzcinski, C. Strecha, and P. Fua, “BRIEF: Computing a local binary descriptor very fast,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 34, no. 7, Jul. 2012, pp. 1281–1298.
    [34] L. Ming, W. Jun, and Z. Meiqiang, “On Skeleton Extraction Algorithm for Path Planning of Mobile Robots in Complex Planar Maps,” the 29th Chinese Control Conference (CCC), Beijing, July 2010, pp. 3704-3708.
    [35] O. Takahashi, and R.J. Schilling, “Motion planning in a plane using generalized Voronoi diagrams,” IEEE Transactions on Robotics and Automation, vol. 5, no. 2, April 1989, pp. 143-150.
    [36] Y. Koren, and J. Borenstein, “Potential Field Methods and Their Inherent Limitations
    for Mobile Robot Navigation,” The IEEE International Conference on Robotics and Automation, April 1991, pp. 1398-1404.
    [37] Y.K. Hwang, and N. Ahuja, “A potential field approach to path planning,” IEEE Transactions on Robotics and Automation, vol. 8, no. 1, Feb. 1992, pp. 23-32.
    [38] http://www.mobilerobots.com/Mobile_Robots.aspx
    [39] https://www.hokuyo-aut.jp/
    [40] https://www.asus.com/tw/3D-Sensor/Xtion_PRO_LIVE/
    [41] https://www.udoo.org/
    [42] http://www.edimax.com.tw/edimax/tw/
    [43] http://www.ntnu.edu.tw/

    下載圖示
    QR CODE