本論文提出一地圖建置與探索系統，此系統可在未知的環境中令機器人進行探索以及建置地圖的任務。此系統分為前端的SLAM技術以及後端的導航架構；前端SLAM技術使用的是Hector SLAM，利用雷射測距儀動態的將當下環境繪製成晶格地圖；後端的導航架構會將前端SLAM技術提供的地圖依機器人半徑轉換為權重地圖，再使用全域路徑及區域路徑做機器人移動路徑點。全域路徑使用A*演算法取得最短路徑，若目標點在未知區域時，全域路徑先規劃至未知地圖邊緣，接下來再規劃從機器人至目標點間的無障礙區路徑。區域路徑規劃使用動態視窗法結合A*演算法。此方法在每個時刻預先預測所有可能移動軌跡，再讓機器人依照最佳移動軌跡移動。在機器人移動時探索道未知區域時，此時會檢討全域路徑於未知區域的規劃。若全域路徑有穿過障礙物，則重新規劃全域路徑。該策略讓機器人在探索地圖時,遇到未預期障礙物可以迅速做出反應並有效地避開。根據實驗結果，本系統可使機器人於未知環境中做到探索並將周圍環境建置成2D地圖。

This paper proposes a mapping and exploration system. This system can let robot take the task of exploring and mapping under unknown environment. This system can be separated into front-end SLAM technique and back-end navigation architecture. Front-end SLAM uses Hector SLAM which according LiDAR information and dynamic draw the environment into the grid map. Back-end navigation architecture will consider the robot’s radius and turn the grid map from front end into threshold map. Then using global path planning and local path planning to make robot move correctly. Global path planning using A* algorithm. Global path will plan the path to edge of map then plan the path to target as obstacle free zone if the target is in unknown area. Local path planning using dynamic window approach combined with A* algorithm. This method will predict all possible moving trajectories and choose the best trajectory let robot follow the trajectory. While exploring the unknown Road area when the robot moves, then will review the global path planning in unknown areas.
If there are entire domain path through obstacles, the global re-planning path. This strategy allows the robot to explore the map when encountered unexpected obstacles can react quickly and effectively avoided. According to the results, the system can be done in an unknown environment and explore the surroundings to build 2D map robots.

第 1 章 緒論	1
1.1 研究背景	1
1.2 研究動機	2
1.3 論文架構	4
第 2 章 機器人系統介紹	5
2.1 ROS介紹	5
2.2 Gazebo模擬器介紹	10
第 3 章 地圖建置與導航系統	14
3.1地圖建置與導航系統架構簡介	14
3.2 Hector SLAM	16
3.3全域路徑規劃與區域路徑規劃	21
3.4 探索策略	35
第 4 章 模擬與實驗結果	38
4.1 Gazebo中的實驗平台與居家模擬環境	38
4.2 地圖建置與導航實驗結果	42
4.3探索策略實驗結果	50
4.4於複雜環境之導航結果	52
第 5 章 結論與未來展望	57
參考文獻	58
圖 1.1、機器人三大研究範圍之涵蓋示意圖	2
圖 1.2、華碩於Computex 2016所發表的ASUS Zenbo	3
圖 2.1、於ROS環境下製作之機器人	6
圖 2.2、ROS系統通訊結構圖	8
圖 2.3、Gazebo架構	12
圖 2.4、Gazebo的圖形化介面	13
圖 3.1、地圖建置與導航系統架構	14
圖 3.2、Hector SLAM之系統架構圖	16
圖 3.3、雙線性過濾後的插植點示意圖，Pm為待插值點	17
圖 3.4、繪製地圖與雷射測距儀間的匹配關係示意圖	19
圖 3.5、導航架構圖	21
圖 3.6、導航示意圖	22
圖 3.7、依機器人大小將原地圖轉換為權重地圖之示意圖	23
圖 3.8、A*演算法流程圖	24
圖 3.9、A*演算法實例	25
圖 3.10、g(n)計算方式	25
圖 3.11、h(n)計算方式(右邊晶格距終點晶格數為3，故成本為30)	25
圖 3.12、展開初始搜尋點之相鄰晶格的成本	26
圖 3.13、以新晶格為起點再次搜尋迭代(f = g + n)	26
圖 3.14、利用A*演算法所規劃之路徑	27
圖 3.15、目標點於已知區域	28
圖 3.16、目標點於未知區域	28
圖 3.17、dist(v,ω)計算方式	29
圖 3.18、速度空間與動態視窗關係圖(Vs為整體速度空間，Va為合適速度樣本，Vr為最終搜尋空間)	30
圖 3.19、"heading(v,ω)" 計算方式	31
圖 3.20、全域路徑規劃與區域路徑規劃流程圖	33
圖 3.21、結合A*之動態視窗法示意圖	34
圖 3.22、探索策略流程圖	35
圖 3.23、搜索示意圖	36
圖 4.1、本論文所使用之實驗平台	38
圖 4.2、實驗平台於Gazebo室內環境示意圖	39
圖 4.3、SICK LMS 系列產品	40
圖 4.4、實驗環境正視圖與坐標系	40
圖 4.5、實驗環境等視圖	41
圖 4.6、Rviz圖形化介面	41
圖 4.7、Hector SLAM所建置出的地圖	42
圖 4.8、根據機器人直徑放大後的權重地圖	42
圖 4.9、(10,20,0.01)	43
圖 4.10、(20,20,0.01)	43
圖 4.11、(30,20,0.01)	43
圖 4.12、(50,20,0.01)	43
圖 4.13、(50,0,0.01)	44
圖 4.14、(50,10,0.01)	44
圖 4.15、(50,20,0.01)	45
圖 4.16、(50,30,0.01)	45
圖 4.17、(50,20,0.01)	46
圖 4.18、(50,20,1.0)	46
圖 4.19、(50,20,10.0)	46
圖 4.20、機器人位移至左側第一個窄口時所建立的地圖	47
圖 4.21、初始全域路徑規劃	48
圖 4.22、重新規劃之全域路徑	48
圖 4.23、左下房間地圖更新	49
圖 4.24、第三次全域路徑規劃	49
圖 4.25、最終執行結果	49
圖 4.26、(0,0)，占30%	50
圖 4.27、(1.0,-0.60)，占60.95%	50
圖 4.28、(1.5,2.0)，占71%	50
圖 4.29、(-1.5,5.0)，占71.92%	50
圖 4.30、(-2.0,13)，占72.74%	50
圖 4.31、(-1.5,14)，占75.28%	50
圖 4.32、(3.0,14)，占75.28%	50
圖 4.33、(1.2,-3.2)，占90.36%	50
圖 4.34、探索後建置的平面地圖以及機器人探索時的移動軌跡	51
圖 4.35、迷宮環境	52
圖 4.36、迷宮環境俯視圖及目標點配置	52
圖 4.37、第一個目標點的探索結果	53
圖 4.38、由第一個目標點探索至第二個目標點之執行結果	54
圖 4.39、由第二個目標點回到起始點之執行結果	55
表 4.1、Husky a200物理條件	39
表 4.2、雷射測距儀效能	40
表 4.3、調整"αc" 的影響結果	44
表 4.4、調整"βc" 的影響結果	45
表 4.5、每段路徑之執行結果	56

[1]	因應缺工荒 東莞無人工廠上路-工商時報http://www.chinatimes.com/newspapers/20150504000092-260203
[2]	ASUS Zenbo, https://zenbo.asus.com/ 
[3]	王旻君，使用超音波感測資訊之機器人在動態環境中之全域及區域路徑規劃，國立成功大學工程學系碩士論文(指導教授：王宗一)，2010。
[4]	謝明樺，基於VFH之混和導航系統設計，淡江大學電機工程研究所碩士論文(指導教授 : 李世安)，2015。
[5]	T. Goto, T. Kosaka, and H. Noborio, “On the heuristics of A* or a algorithm in ITS and robot path-planning,” 2003 IEEWRSJ International Conference on Intelligent Robots and Systems, Las Vegas, Nevada, pp. 1159-1166, 2003.
[6]	D. Fox, W. Burgard, and S. Thrun, “The Dynamic Window Approach to Collision Avoidance,” IEEE Robotics and Automation, vol.4, pp.23-33, 1997.
[7]	M. Quigley, K. Conley, B. P. Gerkey, J. Faust, T. Foote, J. Leibs, R. Wheeler, and A. Y. Ng, “ROS: an open-source Robot Operating System,” ICRA Workshop on Open Source Software, vol.3, pp.5, 2009.
[8]	A. Y. Ng, S. Gould, M. Quigley, A. Saxena, and E. Berger, “STAIR: The STanford Artificial Intelligence Robot project.” Snowbird, 2008.
[9]	A. Y. Ng, S. Gould, M. Quigley, A. Saxena and E. Berger, “STAIR: Hardware and Software Architecture.” AAAI 2007 Robotics Workshop, 2007
[10]	K. Wyrobek, E. Berger, H.F.M. Van der Loos, and K. Salisbury, “Towards a Personal Robotics Development Platform: Rationale and Design of an Intrinsically Safe Personal Robot,” 2008 IEEE International Conference on Robotics and Automation (ICRA), pp. 2165 – 2170, 2008.
[11]	J. Maitin-Shepard, M. Cusumano-Towner, J. Lei, and P. Abbeel, “Cloth Grasp Point Detection based on Multiple-View Geometric Cues with Application to Robotic Towel Folding,” 2010 IEEE International Conference on Robotics and Automation (ICRA), pp. 2308 – 2315, 2010.
[12]	N. Koenig and A. Howard, “Design and Use Paradigms for Gazebo, AnOpen-Source Multi-Robot Simulator, ” 2004 IEEE International Conference on Robotics and Automation (ICRA), pp. 2149–2154, 2004.
[13]	S. Kohlbrecher, J. Meyer, O. von Stryk, and U. Klingauf, “A Flexible and Scalable SLAM System with Full 3D Motion Estimation,” 2011 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), pp. 155-160, 2011.
[14]	S. Kohlbrecher, J. Meyer, T. Graber, K. Petersen, U. Klingauf, and O. von Stryk, “Hector Open Source Modules for Autonomous Mapping and Navigation with Rescue Robots,” RoboCup 2013: Robot World Cup XVII, pp. 624-631, 2014.
[15]	Santos, J. Machado, D. Portugal, and R. P. Rocha. “An evaluation of 2D SLAM techniques available in robot operating system, ” 2013 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), pp. 1-6, 2013.
[16]	B. D. Lucas and T. Kanade, “An iterative image registration techniquewith an application to stereo vision (darpa),” DARPA Image Understanding Workshop, pp. 121–130, 1981.
[17]	B. P. Gerkey, and K. Konolige, “Planning and control in unstructured terrain,” IEEE International Conference on Robotics and Automation (ICRA), 2008.