臺灣博碩士論文加值系統

本研究提出了一種最佳路徑規劃演算法，並在已知環境中應用於自主移動機器人導航，同時避免了可能的未知障礙。該算法結合了離線和在線的運動機制。離線路徑規劃是基於骨架提取以建立中軸圖，通過使用骨架圖，可以生成最短路徑。在本研究中，提出了一種多層修補演算法，用於記錄未知障礙物阻擋預定路徑時在線階段所需的信息。利用Dijkstra演算法和骨架圖，所提出的多層修補演算法能夠避開障礙物並克服局部最小的問題。在路徑追蹤方面，前瞻距離是純追蹤算法的主要參數。如果該參數能夠隨著機器人與障礙物之間的距離而變化，則跟蹤軌跡可以更加平滑和穩定。因而，我們提出了一種基於傳統純追踪方法的適應性純追踪演算法，其演算法可以考慮路徑與障礙物之間的距離值來設置前瞻距離參數。通過使用適應性純追踪演算法，所生成的路徑是平滑的，並且在移動機器人導航時可以與障礙物保持安全的距離，該算法的可行性在模擬實驗結果中得到了證實。

This study proposes an optimal path planning algorithm for autonomous mobile
robot navigation in a known environment, whereas avoiding possible unknown
obstacles. The algorithm incorporating an off-line and an on-line locomotion
mechanism. The off-line path planning is based on skeleton extraction to establish a medial axis graph. With the use of the skeleton graph, the shortest path can be generated. In this study, a multi-layer patching algorithm is proposed to record information required in the on-line stage when unknown obstacles block the pre-determined path. Taking advantages of the Dijkstra’s algorithm and skeleton graph, the proposed multilayer patching algorithm is capable of obstacle avoidance and overcoming the local minima problem. In respect of path tracking, the look-ahead distance is the main parameter of the traditional pure pursuit algorithm. If the parameter can be varied with the distance between the path and the obstacle, the tracking trajectory is to be smoother and more stable. Therefore, we propose an adaptive pure pursuit algorithm based on traditional pure pursuit method that can consider a distance value between the path and obstacle to set a parameter of look-ahead distance. Through the use of adaptive pure pursuit algorithm, the path generated is smooth and maintains a safe distance from obstacles when the mobile robot navigates. From the simulation results, the feasibility of the proposed algorithm is confirmed in several experimental results.

中文摘要............................................................ I
Abstract........................................................... II
致謝............................................................... III
Table of contents ................................................. IV
List of figures ................................................... VI
List of Tables .................................................... VIII
Chapter 1 Introduction ............................................ 1
1.1 Background .................................................... 1
1.2 Motivation .................................................... 2
1.3 System Architecture ........................................... 5
1.4 Organization of the Thesis .................................... 6
Chapter 2 Related work ............................................ 7
Chapter 3 Off-line Planning ....................................... 10
3.1 Map Pre-processing ............................................ 10
3.1.1 Configuration space ......................................... 10
3.1.2 Skeleton extraction.......................................... 12
3.1.3 Junction points ............................................. 15
3.2 Initialize starting point and target point .................... 17
3.3 Global Path Planning .......................................... 19
3.3.1 Layering the skeleton paths ................................. 19
3.3.2 Incremental line-of-sight ................................... 21
3.4 Adaptive Pure Pursuit algorithm ............................... 24
Chapter 4 On-line Planning ........................................ 33
Chapter 5 Experiment Results ...................................... 41
5.1 Test schemes .................................................. 41
5.2 Off-line planning ............................................. 42
5.3 On-line planning .............................................. 44
5.3.1 Scenario 1................................................... 44
5.3.2 Scenario 2................................................... 45
Chapter 6 Conclusions and future work ............................. 46
6.1 Conclusions ................................................... 46
6.2 Future work ................................................... 47
References ........................................................ 48

[1] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische
mathematik, vol. 1, no. 1, pp. 269-271, 1959.
[2] 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, pp. 100-107, 1968.
[3] T. Lozano-Pérez, and M. A. Wesley, “An algorithm for planning collision-free
paths among polyhedral obstacles,” Communications of the ACM, vol. 22, no. 10, pp. 560-570, 1979.
[4] T. Lozano-Perez, "Spatial planning: A configuration space approach," Autonomous robot vehicles, pp. 259-271: Springer, 1990.
[5] R. A. Brooks, and T. Lozano-Perez, “A subdivision algorithm in configuration
space for findpath with rotation,” IEEE Transactions on Systems, Man, and Cybernetics, no. 2, pp. 224-233, 1985.
[6] 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, pp. 143-150, 1989.
[7] R. Wen, H.-y. Wang, and J. Xie, "Path Planning of Mobile Robot Based on
Voronoi Diagram by Approximation Structuring and Zonal Ant Colony Algorithm," International Conference on Intelligence and Software Engineering, pp. 1-4, 2009.
[8] M. Li, J. Wang, and M. Zhu, "On skeleton extraction algorithm for path planning of mobile robots in complex planar maps," IEEE Control Conference (CCC),
pp. 3704-3708, 2010.
[9] Z. Guo, and R. W. Hall, “Parallel thinning with two-subiteration algorithms,”
Communication of ACM, vol. 32, no. 3, pp. 359-373, 1989.
[10] H. Breu, J. Gil, D. Kirkpatrick, and M. Werman, “Linear time Euclidean
distance transform algorithms,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 5, pp. 529-533, 1995.
[11] L. E. Kavraki, P. Svestka, J. C. Latombe, and M. H. Overmars, “Probabilistic
roadmaps for path planning in high-dimensional configuration spaces,” IEEE
Transactions on Robotics and Automation, vol. 12, no. 4, pp. 566-580, 1996.
[12] J. J. Kuffner, and S. M. LaValle, "RRT-connect: An efficient approach to single-query path planning," IEEE International Conference on Robotics and
Automation, pp. 995-1001, 2000.
[13] D. Hsu, J.-C. Latombe, and R. Motwani, "Path planning in expansive
configuration spaces," IEEE International Conference on Robotics and Automation, pp. 2719-2726, 1997.
[14] V. Boor, M. H. Overmars, and A. F. Van Der Stappen, "The Gaussian sampling
strategy for probabilistic roadmap planners," IEEE International Conference on
Robotics and Automation, pp. 1018-1023, 1999.
[15] K. Sugihara, and J. Smith, "Genetic algorithms for adaptive motion planning of an autonomous mobile robot," IEEE International Symposium on
Computational Intelligence in Robotics and Automation, pp. 138-143, 1997.
[16] I. Ashiru, C. Czarnecki, and T. Routen, “Characteristics of a genetic based
approach to path planning for mobile robots,” Journal of Network and Computer Applications, vol. 19, no. 2, pp. 149-169, 1996.
[17] M. Dorigo, and L. M. Gambardella, “Ant colony system: a cooperative learning
approach to the traveling salesman problem,” IEEE Transactions on evolutionary computation, vol. 1, no. 1, pp. 53-66, 1997.
[18] C. Tsai, H. Huang, and C. Chan, “Parallel Elite Genetic Algorithm and Its
Application to Global Path Planning for Autonomous Robot Navigation,” IEEE
Transactions on Industrial Electronics, vol. 58, no. 10, pp. 4813-4821, 2011.
[19] M. Gemeinder, and M. Gerke, “GA-based path planning for mobile robot
systems employing an active search algorithm,” Applied Soft Computing, vol.
3, no. 2, pp. 149-158, 2003.
[20] Y. Koren, and J. Borenstein, "Potential field methods and their inherent
limitations for mobile robot navigation," IEEE International Conference on
Robotics and Automation, pp. 1398-1404, 1991.
[21] I. Ulrich, and J. Borenstein, "VFH+: reliable obstacle avoidance for fast mobile robots," IEEE International Conference on Robotics and Automation, vol.2, pp. 50 1572-1577, 1998.
[22] J. Borenstein, and Y. Koren, "The vector field histogram-fast obstacle avoidance for mobile robots," IEEE Transactions on Robotics and Automation, vol. 7, no. 3, pp. 278-288, 1991.
[23] L. Zuo, Q. Guo, X. Xu, and H. Fu, “A hierarchical path planning approach based on A* and least-squares policy iteration for mobile robots,” Neurocomputing, vol. 170, no. C, pp. 257-266, 2015.
[24] K. G. Jolly, R. Sreerama Kumar, and R. Vijayakumar, “A Bezier curve based
path planning in a multi-agent robot soccer system without violating the acceleration limits,” Robotics and Autonomous Systems, vol. 57, no. 1, pp. 23-
33, 2009.
[25] L. Han, H. Yashiro, H. T. N. Nejad, Q. H. Do, and S. Mita, "Bézier curve based path planning for autonomous vehicle in urban environment," IEEE Intelligent Vehicles Symposium, pp. 1036-1042, 2010.
[26] Y. Ho, and J. Liu, "Collision-free curvature-bounded smooth path planning
using composite Bezier curve based on Voronoi diagram," IEEE International
Symposium on Computational Intelligence in Robotics and Automation(CIRA),
pp. 463-468, 2009.
[27] K. Renny Simba, N. Uchiyama, and S. Sano, “Real-time smooth trajectory
generation for nonholonomic mobile robots using Bézier curves,” Robotics and
Computer-Integrated Manufacturing, vol. 41, pp. 31-42, 2016.
[28] R. C. Coulter, Implementation of the pure pursuit path tracking algorithm,
Robotics Institute Carnegie Mellon University Pittsburgh PA Tech. Rep. CMURI-
TR-92-01 Jan. 1992.
[29] M. G. H. Bell, “Hyperstar: A multi-path Astar algorithm for risk averse vehicle navigation,” Transportation Research Part B: Methodological, vol. 43, no. 1, pp. 97-107, 2009.
[30] W. Yin, and X. Yang, “A Totally Astar-based Multi-path Algorithm for the
Recognition of Reasonable Route Sets in Vehicle Navigation Systems,” Procedia - Social and Behavioral Sciences, vol. 96, pp. 1069-1078, 2013.
[31] J. Y. Yen, “Finding the k shortest loopless paths in a network,” Management
Science, vol. 17, no. 11, pp. 712-716, 1971.
[32] W. Abu-Ain, S. N. H. S. Abdullah, B. Bataineh, T. Abu-Ain, and K. Omar,
“Skeletonization Algorithm for Binary Images,” Procedia Technology, vol. 11,
pp. 704-709, 2013.
[33] H. Blum, "A transformation for extracting new descriptors of shape", in Models for the Perception of Speech and Visual Form, W. Whaten-Dunn, Ed: MIT Press, pp. 362-380, 1967.