Abstract
Path planning constitutes one of the most crucial abilities an autonomous robot should possess, apart from Simultaneous Localization and Mapping algorithms (SLAM) and navigation modules. Path planning is the capability to construct safe and collision free paths from a point of interest to another. Many different approaches exist, which are tightly dependent on the map representation method (metric or feature-based). In this work four path planning algorithmic families are described, that can be applied on metric Occupancy Grid Maps (OGMs): Probabilistic RoadMaps (PRMs), Visibility Graphs (VGs), Rapidly exploring Random Trees (RRTs) and Space Skeletonization. The contribution of this work includes the definition of metrics for path planning benchmarks, actual benchmarks of the most common global path planning algorithms and an educated algorithm parameterization based on a global obstacle density coefficient.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Lozano-Prez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM 22(10), 560–570 (1979)
Ghosh, S.K.: Visibility Algorithms in the Plane, ISBN:9780521875745. Cambridge University Press (2007)
Ghosh, S.K., Goswami, P.P.: Unsolved problems in visibility graphs of points, segments and polygons. In: Proceedings of India-Taiwan Conference on Discrete Mathematics, Taipei, pp 44–54 (2009)
Kim, J., Kim, M., Kim, D.: Variants of the quantized visibility graph for efficient path planning. Adv. Robot. 25(18), 2341–2360 (2011)
Bhattacharya, P., Gavrilova, M.L.: Voronoi diagram in optimal path planning. In: 4th International Symposium on Voronoi Diagrams in Science and Engineering, 2007. ISVD ’07, pp. 38–47
Garrido, S., Moreno, L., Abderrahim, M., Martin, F.: Path Planning for Mobile Robot Navigation using Voronoi Diagram and Fast Marching. In: 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp 2376–2381 (2006)
Ok, K.-C., Ansari, S., Gallagher, B., Sica, W., Dellaert, F., Stilman, M.: Path planning with uncertainty: Voronoi uncertainty fields. In: 2013 IEEE International Conference on Robotics and Automation (ICRA), pp 4596–4601. IEEE (2013)
Geraerts, R., Overmars, M.H.: A comparative study of probabilistic roadmap planners. In: Workshop on the algorithmic foundations of robotics, pp 43–57 (2002)
Geraerts, R.J., Overmars, M.H.A.: Sampling Techniques for Probabilistic Roadmap Planners. Intelligent Autonomous Systems 8, 600–609 (2004)
Kavraki, L.E., Latombe, J.-C.: Probabilistic Roadmaps for Robot Path Planning, Practical Motion Planning in Robotics: Current Approaches and Future Directions, pp 33–53. Wiley (1998)
Kavraki, L.E., Kolountzakis, M.N., Latombe, J.-C.: Analysis of probabilistic roadmaps for path planning. IEEE Trans. Robot. Autom. 14(1), 166–171 (1998)
Kavraki, L.E., Svestka, P., Latombe, J.-C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation 12(4), 566–580 (1996)
Laumond, J.-P., Nissoux, C.: Visibility-based probabilistic roadmaps for motion planning. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 1999. IROS ’99, vol. 3, pp 1316–1321 (1999)
Bohlin, R., Kavraki, L.E.: Path planning using lazy PRM. In: Proceedings of the IEEE International Conference on Robotics and Automation, 2000. ICRA ’00, vol. 1, pp 521–528 (2000)
Hsu, D., Sanchez-Ante, G., Sun, Z.: Hybrid PRM Sampling with a Cost-Sensitive Adaptive Strategy. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation 2005, ICRA 2005, pp 3874–3880
Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30(7), 846–894 (2011)
Marble, J.D., Bekris, K.E.: Asymptotically near-optimal is good enough for motion planning. In: International Symposium on Robotics Research (2011)
Marble, J.D., Bekris, K.E.: Towards small asymptotically near-optimal roadmaps. IEEE (2012)
Li, Y., Li, D., Maple, C., Yue, Y., Oyekan, J.: K-Order Surrounding roadmaps path planner for robot path planning. J. Intell. Robot. Syst. 75(3-4), 493–516 (2014)
LaValle, S.M.: Rapidly-exploring random trees: A New Tool for Path Planning. TR 98–11, Computer Science Dept., Iowa State University (1998)
Bruce, J., Veloso, M.: Real-time randomized path planning for robot navigation. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 3, pp 2383–2388 (2002)
Martin, S.R., Wright, S.E., Sheppard, J.W.: Offline and Online Evolutionary Bi-Directional RRT Algorithms for Efficient Re-Planning in Dynamic Environments (2007)
Karaman, S., Frazzoli, E.: Incremental Sampling-based Algorithms for Optimal Motion Planning coRR (2010)
Nasir, J., Islam, F., Malik, U., Ayaz, Y., Hasan, O., Khan, M., Muhammad, M.S.: RRT*-SMART: a rapid convergence implementation of RRT*. Int. J. Adv. Robot. Syst., 10 (2013)
Jaillet, L., Corts, J., Simon, T.: Sampling-based path planning on configuration-space costmaps. IEEE Transactions on Robotics 26(4), 635–646 (2010)
Guitton, J., Farges, J.-L., Chatila, R.: Cell-RRT: Decomposing the environment for better plan. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009. IROS 2009, pp. 5776–5781
Jacobs, S.A., Stradford, N., Rodriguez, C., Thomas, S., Amato, N.M.: A scalable distributed RRT for motion planning. In: 2013 IEEE International Conference on Robotics and Automation (ICRA), pp. 5088–5095, p 2013. IEEE
Felzenszwalb, P., Huttenlocher, D.: Distance transforms of sampled functions Cornell University (2004)
Barraquand, J., Latombe, J.-C.: Robot motion planning: A distributed representation approach. Int. J. Robot. Res. 10(6), 628–649 (1991)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tsardoulias, E.G., Iliakopoulou, A., Kargakos, A. et al. A Review of Global Path Planning Methods for Occupancy Grid Maps Regardless of Obstacle Density. J Intell Robot Syst 84, 829–858 (2016). https://doi.org/10.1007/s10846-016-0362-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-016-0362-z