Safe and Efficient Path Planning for Omni-directional Robots using an Inflated Voronoi Boundary

Year 2019, Volume: 16 Issue: 2, 46 - 69, 01.11.2019

Mohammed Rabeea Hashim Al-dahhan , Klaus Werner Schmıdt

Abstract

Path planning algorithms for mobile robots are concerned with finding a feasible path between a

start and goal location in a given environment without hitting obstacles. In the existing literature, important

performance metrics for path planning algorithms are the path length, computation time and path safety,

which is quantified by the minimum distance of a path from obstacles.

The subject of this paper is the development of path planning algorithms for omni-directional robots,

which have the ability of following paths that consist of concatenated line segments. As the main contribution

of the paper, we develop three new sampling-based path planning algorithms that address all of the stated

performance metrics. The original idea of the paper is the computation of a modified environment map that

confines solution paths to the vicinity of the Voronoi boundary of the given environment. Using this modified

environment map, we adapt the sampling strategy of the popular path planning algorithms PRM (probabilistic

roadmap), PRM* and FMT (fast marching tree). As a result, we are able to generate solution paths with a

reduced computation time and increased path safety. Computational experiments with different environments

show that the proposed algorithms outperform state-of-the-art algorithms.

Keywords

Path planning, omni-directional robots, sampling-based algorithms, Voronoi diagram

References

• [1] Z. Kingston, M. Moll, L. E. Kavraki, Sampling-Based Methods for Motion Planning with Constraints, AnnualReview of Control, Robotics, and Autonomous Systems, 1(1), (2018), 159–185.
• [2] M. M. Costa, M. F. Silva, A Survey on Path Planning Algorithms for Mobile Robots, IEEE International Conferenceon Autonomous Robot Systems and Competitions, (2019), 1–7.
• [3] A. Khan, I. Noreen, Z. Habib, On Complete Coverage Path Planning Algorithms for Non-holonomic MobileRobots: Survey and Challenges, Journal of Information Science and Engineering, 33, (2017), 101–121.
• [4] A. S. H. H. V. Injarapu, S. K. Gawre, A survey of autonomous mobile robot path planning approaches, InternationalConference on Recent Innovations in Signal Processing and Embedded Systems, (2017), 624–628.
• [5] T. T. Mac, C. Copot, D. T. Tran, R. De Keyser, Heuristic approaches in robot path planning: A survey, Roboticsand Autonomous Systems, 86 (2016), 13–28.
• [6] P. Corke, Robotics, vision and control: fundamental algorithms in MATLAB 2nd ed, Springer, (118), (2017).
• [7] H. M.Choset, S.Hutchinson, K. M.Lynch, G.Kantor, W. Burgard, Kavraki, L. E., S. Thrun, Principles of robotmotion: theory, algorithms, and implementation. MIT press, (2005).
• [8] P. Bhattacharya, M. L.Gavrilova, Roadmap-Based Path Planning Using the Voronoi Diagram for a Clearance-Based Shortest Path, IEEE Robotics & Automation Magazine, 15(2), (2008), 58–66.
• [9] N. Y, D. Kim, W. I. Ko, H. Suh, Confidence random tree-based algorithm for mobile robot path planning consideringthe path length and safety, International Journal of Advanced Robotic Systems, 16(2), (2019), 1–10.
• [10] L. E. Kavraki, P. Svestka, J. C. Latombe, M. H. Overmars, Probabilistic roadmaps for path planning in highdimensionalconfiguration spaces, IEEE Transactions on Robotics and Automation, 12(4), (1996), 566-–580.
• [11] L. Kavraki, J.Latombe, Randomized preprocessing of configuration for fast path planning, IEEE InternationalConference on Robotics and Automation, 3, (1994), 2138–2145.
• [12] S. Karaman, E.Frazzoli, Sampling-based algorithms for optimal motion planning, The International Journal ofRobotics Research, 30(7), (2011), 846-–894.
• [13] S. M. LaValle, J. J. Kuffner, Randomized Kinodynamic Planning, The International Journal of Robotics Research,20(5), (2001), 378–400.
• [14] L. Janson, M. Pavone, Fast Marching Trees: A Fast Marching Sampling-Based Method for Optimal MotionPlanning in Many Dimensions, Robotics Research, Springer Tracts in Advanced Robotics, 114, (2016).24 M. R. H. AL-Dahhan et al.
• [15] B. K. Patle, G. Babu L, A. Pandey, D. R. K. Parhi, A. Jagadeesh, A review: On path planning strategies fornavigation of mobile robot, Defence Technology, 15(4), (2019), 582–606.
• [16] D. A. L. Garcla, F. Gomez-Bravo, Vodec: A fast Voronoi algorithm for car-like robot path planning in dynamicscenarios, Robotica, 30(7), (2012), 1189-1201.
• [17] B. B. K. Ayawli, X. Mei, M. Shen, A. Y. Appiah, F. Kyeremeh, Mobile Robot Path Planning in Dynamic Environmentusing Voronoi Diagram and Computation Geometry Technique, IEEE Access,(2019), 86026-86040.
• [18] M. R. H. Al-Dahhan, M. M. Ali, Path tracking control of a mobile robot using fuzzy logic, In 2016 13th InternationalMulti-Conference on Systems, Signals and Devices (SSD), (2016), 82–88.
• [19] L. Gang, J. Wang, PRM path planning optimization algorithm research, Wseas Transactions on Systems andcontrol, (2016), (11), 81-86.
• [20] I. B. Jeong, S. J. Lee, J. H. Kim, Quick-RRT*: Triangular inequality-based implementation of RRT* with improvedinitial solution and convergence rate, Expert Systems with Applications, (2019), 82-90.
• [21] T. Bai, Z. Fan, M. Liu, S. Zhang, R. Zheng, Multiple Waypoints Path Planning for a Home Mobile Robot, In2018 Ninth International Conference on Intelligent Control and Information Processing (ICICIP) IEEE, (2018),53–58).
• [22] K. Yang, Anytime synchronized-biased-greedy rapidly-exploring random tree path planning in two dimensionalcomplex environments, International Journal of Control, Automation and Systems, (2011), 9(4), 750.
• [23] H. Dong, W. Li, J. Zhu, S. Duan, The path planning for mobile robot based on Voronoi diagram, In 2010 ThirdInternational Conference on Intelligent Networks and Intelligent Systems, (2010), 446–449.
• [24] M. Foskey, M. Garber, M. C. Lin, D. Manocha, A Voronoi-based hybrid motion planner, IEEE/RSJ InternationalConference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium,(2001), 55–60.
• [25] E. Masehian, M. R. Amin-Naseri, A voronoi diagram-visibility graph-potential field compound algorithm forrobot path planning. Journal of Robotic Systems, fbf 21g(6). (2004), 275–300.
• [26] Q. Wang, M. Wulfmeier, B. Wagner, Voronoi-Based Heuristic for Nonholonomic Search-Based Path Planning,Intelligent Autonomous Systems 13. Advances in Intelligent Systems and Computing, 302. (2016), 445–458.
• [27] E.W. Dijkstra, A Note on Two Problems in Connection with Graphs.Numerische Mathematik. 1, (1959), 269–271.
• [28] S. Garrido, L. Moreno, M. Abderrahim, F. Martin, Path planning for mobile robot navigation using voronoi diagramand fast marching, In 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems IEEE,(2006), 2376–2381).
• [29] M. R. H. Al-Dahhan, K. W. Schmidt, Path Planning Based on Voronoi Diagram and PRM for OmnidirectinalMobile Robots, II. International Conference on Digital Transformation and Smart Systems, (2019).
• [30] M. ALANDES, Comparison among different sampling-based planning techniques, Politedcnco Di Milano university,(2015).
• [31] K. E. Hoff, III, J. Keyser, M. Lin, D. Manocha, T. Culver, Fast computation of generalized Voronoi diagramsusing graphics hardware. Proceedings of the 26th Annual Conference on Computer Graphics and InteractiveTechniques, (1999), 277–286.
• [32] D. Ji, J. Cheng, B. Wang, Path planning for mobile robots in complex environment via laser sensor, ChineseControl And Decision Conference, (2018), 2715-2719.