本論文研究移動機器人在動態環境的即時避障和路徑規劃。先在靜態環境中使用廣義的Voronoi圖產生全域的拓撲地圖，在拓撲地圖上使用A*演算法規劃出起點到終點的最短路徑，使用機器人運動學的控制設計使最短路徑平滑化，初始路徑規劃這樣就完成了。為了在動態環境避障，機器人使用雷射測距儀(Laser Range Finder, LRF)感測障礙物，使用卡爾曼濾波器來估測移動障礙物的位置與速度，移動障礙物的位置與速度當作路徑重規劃的判斷條件。路徑重規劃是在拓撲地圖裡的一個矩形局部區域，也是使用A*演算法完成的。最後，本論文以軟體模擬與硬體實驗結果驗證本論文所提出的演算法。

This research studies the real-time obstacle avoidance and path planning for mobile robot in the dynamic environment. The global topological map is generated by generalized Voronoi diagram in the static environment. The shortest path is planned from starting point to end point by A* algorithm in the topological map. The smoothing of shortest path is achieved by the robot kinematics with control design. The initial path planning is accomplished. For obstacle avoidance in the dynamic environment, the robot uses laser range finder to detect obstacles. The position and velocity of the moving obstacle are estimated by Kalman filter. The conditions of the path replanning are based on the position and velocity of the moving obstacle. The path replanning is at a local rectangle region of the topological map. The path replanning is also realized by A* algorithm. Finally, the simulation and practical experimental results verify feasibility of the proposed algorithm.

摘要 i
Abstract ii
目錄 iii
圖目錄 v
表目錄 vii
第一章 緒論 1
1.1研究動機與目的 1
1.2文獻探討 1
1.3論文架構 3
第二章 系統架構與硬體設備 4
2.2車體規格 5
2.3雷射測距儀規格 6
2.4電腦規格與硬體架構 7
2.5 移動障礙物 8
第三章 初始路徑規劃 9
3.1地圖建置格點化與安全處理 9
3.2機器人定位 10
3.3產生拓撲地圖 11
3.4路徑規劃 15
3.5機器人移動路徑平滑化 16
第四章 路徑重規劃 21
4.1移動障礙物分析 21
4.1.1比對出在原始地圖裡沒有的障礙物 22
4.1.2比對前後時刻的移動障礙物 24
4.1.3估測移動障礙物的位置、移動方向與移動速度 26
4.2重規劃策略 27
4.2.1重新規劃區 28
4.2.2重規劃路線選擇 30
第五章 實驗結果 32
5.1軟體模擬 32
5.2在靜態環境下路徑規劃 38
5.3在動態環境下路徑規劃 40
5.3.1機器人往右閃避移動障礙物 40
5.3.2機器人往左閃避移動障礙物 43
5.3.3遇到移動障礙物不重新規劃路徑 47
第六章 結論與未來展望 51
6.1結論 51
6.2未來展望 51
參考文獻 52

[1] N. Tran et al., “Global path planning for autonomous robots using modified visibility-graph,” International Conference on Control, Automation and Information Sciences, pp. 25-28, 2013.
[2] Y.J. Wang and Y. Huang, “Mobile robot path planning algorithm based on rapidly-exploring random tree,” IEEE International Conferences on Ubiquitous Computing & Communications and Data Science and Computational Intelligence and Smart Computing, Networking and Services, pp. 21-23, 2019.
[3] 黃聖凱，2016，移動機器人之即時路徑規劃與控制，淡江大學機械與機電工程學系碩士論文
[4] 周成翰，2012，即時機器人路徑重規劃之Delaunay Triangulation/Voronoi Diagram之拓樸結構，淡江大學機械與機電工程學系碩士論文
[5] 蕭孟華，2011，隨機散佈障礙環境下動態路徑規劃–結合GVD、D* Lite、與SVM之研究，淡江大學機械與機電工程學系碩士論文
[6] E. Masehian and M. R. Amin-Naseri, “A Voronoi diagram-visibility graph-potential field compound algorithm for robot path planning,” Journal of Robotic Systems, vol. 21, pp. 275–300,2004.
[7] S. Garrido, L. Moreno, and D. Blanco, “Voronoi diagram and fast marching applied to path planning,” IEEE International Conference on Robotics and Automation, pp. 15-19, 2006.
[8] F. Benavides et al., “Real path planning based on genetic algorithm and Voronoi diagrams,” IX Latin American Robotics Symposium and IEEE Colombian Conference on Automatic Control, pp. 1-4, 2011.
[9] W.C. Yu et al., “Dynamic path planning under randomly distributed obstacle environment,” International Automatic Control Conference, pp. 26-28, 2014
[10] L.Q. Jiang et al., “A fast path planning method for mobile robot based on Voronoi diagram and improved D* algorithm,” IEEE/ASME International Conference on Advanced Intelligent Mechatronics, pp. 8-12, 2019.
[11] H.Y. Liu, X. Jiang and H.H. Ju, “Multi-goal path planning algorithm for mobile robots in grid space,” 25th Chinese Control and Decision Conference, pp. 25-27, 2013.
[12] F. Aurenhammer, “Voronoi diagrams — a survey of a fundamental geometric data structure,” ACM Computing Surveys, vol. 23, pp. 345-405, 1991.
[13] C.Y. Yang, J.S. Yang and F.L. Lian, “Safe and smooth: mobile agent trajectory smoothing by SVM,” International Journal of Innovative Computing, Information and Control, vol. 8, pp. 4959-4978, 2012.
[14] D.Y. Dong et al., “A novel path planning method based on extreme learning machine for autonomous underwater vehicle,” OCEANS 2015 - MTS/IEEE Washington, pp. 19-22, 2015.
[15] B.B.K. Ayawli et al., “Mobile robot path planning in dynamic environment using Voronoi diagram and computation geometry technique,” IEEE Access, vol. 7, pp. 86026-86040, 2019.
[16] M. Candeloro et al., “A 3D dynamic Voronoi diagram-based path-planning system for UUVs,” OCEANS 2016 MTS/IEEE Monterey, pp. 19-23, 2016.
[17] J.M. Guo et al., “Kalman prediction based VFH of dynamic obstacle avoidance for intelligent vehicles,” International Conference on Computer Application and System Modeling, pp. 22-24, 2010.
[18] ROS, http://wiki.ros.org/Documentation (2020/07/16 accessed)
[19] RViz, http://wiki.ros.org/rviz (2020/07/16 accessed)
[20] Turtlebot3, https://emanual.robotis.com/docs/en/platform/turtlebot3/overview/ (2020/07/16 accessed)
[21] H. Durrant-Whyte, and T. Bailey, “Simultaneous localization and mapping: part I,” IEEE Robotics & Automation Magazine, vol. 13, pp. 99-110, 2006.
[22] GMapping, http://wiki.ros.org/gmapping (2020/07/16 accessed)
[23] Laser_scan_matcher, http://wiki.ros.org/laser_scan_matcher (2020/07/16 accessed)
[24] OpenCV, https://opencv.org/ (2020/07/16 accessed)
[25] AMCL, http://wiki.ros.org/amcl (2020/07/16 accessed)
[26] 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, pp. 100-107, 1968.
[27] W.J. Sohn and K.S Hong, “Moving obstacle avoidance using a LRF sensor,” SICE-ICASE International Joint Conference, pp. 18-21, 2006.
[28] K.S. Arun, T.S. Huang and S.D. Blostein, “Least-squares fitting of two 3-D point sets,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 9, pp. 698-700,1987.
[29] R. Faragher, “Understanding the basis of the Kalman filter via a simple and intuitive derivation,” IEEE Signal Processing Magazine, vol. 29, pp. 128–132, 2012.