臺灣博碩士論文加值系統

本論文是關於機器人在足球比賽中之路徑規劃研究，由於在足球比賽中若是只靠本身的感測器去避開障礙物的話，速度過於緩慢而且可能遭遇另一台機器人也使用相同的避障方式並且朝著相同方向避障的問題，因此在比賽中必須使用路徑規劃來避開這種問題，而本論文提出加強式RRT (Rapidly-exploring random tree) 路徑規劃的方法來幫助機器人解決上面所提到的問題並且快速尋找抵達目標點的路徑。單純使用RRT做路徑規劃有個重要的問題，由於RRT本身是隨機取樣建立地圖，因此會產生許多轉折點，而這些轉折點很可能是不需存在的，為了解決此問題本論文的主要目標在於改進RRT的路徑規劃演算法，使得本論文加強式路徑規劃法能夠縮短單純使用RRT所求得的路徑成本且擁有動態避障的能力以避開足球場上其他機器人，最後透過模擬的方式來驗證提出的演算法確實有效減低路徑成本與增加動態避障能力。

This thesis focuses on path planning for a robot soccer game. In a soccer game, path planning helps a robot go toward a ball. Conventional path-planning methods use sensors to make a robot avoid obstacles and then achieve a goal. However, path-planning methods based on obstacle avoidance are slow and problematic because robots on a soccer field using sensors to avoid obstacles might be toward to the same direction. Thus, a fast path-planning method is important to a robot soccer game.

This work uses the rapidly-exploring random tree (RRT) algorithm to provide fast path planning and enhances it to derive a shorter path than the basic RRT algorithm. The enhanced RRT algorithm makes the path generated by the basic RRT algorithm smooth and adapts the planned path to avoid dynamic obstacles. Accordingly, the proposed method for path planning in a soccer game is competitive.

In the simulation results, this work demonstrates the capability of path planning for dynamic obstacles and compares with several common path-planning methods. The results show that the proposed method is generally superior to the other methods in distance and spent time. Particularly, the proposed method provides a shorter path than the RRT method adopted in B-human team, the RoboCup 2011 champion.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 前言 1
1.2 文獻回顧 1
1.2.1 路徑規劃-靜態 2
1.2.2 路徑規劃-動態環境 9
1.3 研究動機與目的 10
1.4 貢獻與章節說明 11
第二章 實驗背景與模擬場地介紹 13
2.1 簡介 13
2.2 環境介紹 14
2.3 路徑規劃 15
2.4 改良方向 16
2.5 總結 19
第三章 系統架構與演算法介紹 20
3.1 系統架構 20
3.2 演算法 21
A. Bi-directional RRT 21
B. 刪除節點法 22
C. 平滑處理演算法 24
D. 變形處理-取樣演算法 26
E. 碰撞偵測演算法 27
第四章 實驗模擬 29
4.1 PRM 29
4.2 Visib-PRM 31
4.3 APF 32
4.4 RRT 33
4.5 Bi-RRT 34
4.6 所有演算法之比較 35
4.7 變更起點與終點 35
4.8 動態障礙物-變形處理 38
4.9 比賽場地模擬 40
4.9.1 動態障礙物模擬 43
4.10 總結 46
第五章 討論與未來展望 47
參考文獻 51

References

[1] H. M. Choset, Principles of Robot Motion: Theory, Algorithms, and Implementation, Cambridge, Massachusetts: MIT, 2005, pp. 77-187.

[2] G. Song, S. Thomas and N. M. Amato, "A general framework for PRM motion planning," in Robotics and Automation (ICRA), vol. 3 , 2003, pp. 4445-4450.

[3] L. E. Kavraki, M. N. Kolountzakis and J. -. Latombe, "Analysis of probabilistic roadmaps for path planning, " Robotics and Automation, vol. 14, 1998, pp. 166-171.

[4] M. Morales, S. Rodriguez and N. M. Amato, "Improving the connectivity of PRM roadmaps," in Robotics and Automation (ICRA), vol. 3, 2003, pp. 4427-4432.

[5] N. M. Amato, O. B. Bayazit, L. K. Dale, C. Jones and D. Vallejo, "Choosing good distance metrics and local planners for probabilistic roadmap methods," Robotics and Automation, vol. 16, 2000, pp. 442-447.

[6] J. D. Z. and J. B. Su , "Narrow passages identification for probabilistic roadmap method, " in Control Conference (CCC) , 2011, pp. 3908-3912.

[7] C. Nissoux, T. Simeon and J. -. Laumond, "Visibility based probabilistic roadmaps," in Intelligent Robots and Systems (IROS), vol. 3, 1999, pp. 1316-1321.

[8] J. Nieto, E. Slawinski, V. Mut and B. Wagner, "Online path planning based on rapidly-exploring random trees," in Industrial Technology (ICIT), 2010, pp. 1451-1456.

[9] Y. K. Hwang and N. Ahuja, "A potential field approach to path planning," Robotics and Automation, vol. 8, 1992, pp. 23-32.

[10] L. Tang, S. Dian, G. Gu, K. Zhou, S. Wang and X. Feng, "A novel potential field method for obstacle avoidance and path planning of mobile robot," in Computer Science and Information Technology (ICCSIT), 2010, pp. 633-637.

[11] E. Masehian and D. Sedighizadeh, "A multi-objective PSO-based algorithm for robot path planning," in Industrial Technology (ICIT) , 2010, pp. 465-470.

[12] Y. Q. Qin, D. B. Sun, N. Li and Y. G. Cen, "Path planning for mobile robot using the particle swarm optimization with mutation operator," in Machine Learning and Cybernetics, vol. 4, 2004, pp. 2473-2478.

[13] I. K. Jung, K. B. Hong, S. K. Hong and S. C. Hong, "Path planning of mobile robot using neural network," in Industrial Electronics (ISIE), vol. 3, 1999, pp. 979-983.

[14] M. Y. Ju and C. W. Cheng, "Smooth path planning using genetic algorithms," in Intelligent Control and Automation (WCICA) , 2011, pp. 1103-1107.

[15] G. Nagib and W. Gharieb, "Path planning for a mobile robot using genetic algorithms, " in Electrical, Electronic and Computer Engineering (ICEEC), 2004, pp. 185-189.

[16] M. Naderan-Tahan and M. T. Manzuri-Shalmani, "Efficient and safe path planning for a mobile robot using genetic algorithm, " in Evolutionary Computation (CEC), 2009, pp. 2091-2097.

[17] W. G. Han, S. M. Baek and T. Y. Kuc, "Genetic algorithm based path planning and dynamic obstacle avoidance of mobile robots," in Systems, Man, and Cybernetics, Computational Cybernetics and Simulation., vol. 3, 1997, pp. 2747-2751.

[18] S. C. Yun, S. Parasuraman and V. Ganapathy, "Dynamic path planning algorithm in mobile robot navigation," in Industrial Electronics and Applications (ISIEA), 2011, pp. 364-369.

[19] Q. Cao, Y. W. Huang and J. L. Zhou, "An evolutionary artificial potential field algorithm for dynamic path planning of mobile robot, " in Intelligent Robots and Systems, 2006, pp. 3331-3336.

[20] L. Jaillet and T. Simeon, "A PRM-based motion planner for dynamically changing environments, " in Intelligent Robots and Systems (IROS), vol. 2, 2004, pp. 1606-1611.

[21] D. Ferguson, N. Kalra and A. Stentz, "Replanning with RRTs," in Robotics and Automation (ICRA), 2006, pp. 1243-1248.

[22] E. Yoshida, K. Yokoi and P. Gergondet, "Online replanning for reactive robot motion: Practical aspects," in Intelligent Robots and Systems (IROS), 2010, pp. 5927-5933.

[23] E. Yoshida and F. Kanehiro, "Reactive robot motion using path replanning and deformation," in Robotics and Automation (ICRA), 2011, pp. 5456-5462.

[24] S. Rodriguez, Xinyu Tang, Jyh-Ming Lien and N. M. Amato, "An obstacle-based rapidly-exploring random tree," in Robotics and Automation (ICRA), 2006, pp. 895-900.