本論文提出一台以機器人作業系統(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.

[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/