Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

This is an Open Access publication published under CSC-OpenAccess Policy.
Path Planning for Mobile Robot Navigation Using Voronoi Diagram and Fast Marching
Santiago Garrido, Luis Moreno, Dolores Blanco, Piotr Pawel Jurewicz
Pages - 42 - 64     |    Revised - 31-03-2011     |    Published - 04-04-2011
Volume - 2   Issue - 1    |    Publication Date - March / April 2011  Table of Contents
Voronoi Diagram, Path Planning, Fast Marching
For navigation in complex environments, a robot needs to reach a compromise between the need for having efficient and optimized trajectories and the need for reacting to unexpected events. This paper presents a new sensor-based Path Planner which results in a fast local or global motion planning able to incorporate the new obstacle information. In the first step the safest areas in the environment are extracted by means of a Voronoi Diagram. In the second step the Fast Marching Method is applied to the Voronoi extracted areas in order to obtain the path. The method combines map-based and sensor-based planning operations to provide a reliable motion plan, while it operates at the sensor frequency. The main characteristics are speed and reliability, since the map dimensions are reduced to an almost unidimensional map and this map represents the safest areas in the environment for moving the robot. In addition, the Voronoi Diagram can be calculated in open areas, and with all kind of shaped obstacles, which allows to apply the proposed planning method in complex environments where other methods of planning based on Voronoi do not work.
CITED BY (35)  
1 Jeddisaravi, K., Alitappeh, R. J., Pimenta, L. C., & Guimarães, F. G. (2016). Multi-objective approach for robot motion planning in search tasks. Applied Intelligence, 1-17.
2 Subramanian, M. B., Sudhagar, K., & Rajarajeswari, G. (2016). Design of Navigation Control Architecture for an Autonomous Mobile Robot Agent. Indian Journal of Science and Technology, 9(10).
3 Abbadi, A., & Matousek, R. (2016). Hybrid rule-based motion planner for mobile robot in cluttered workspace. Soft Computing, 1-17.
4 Weerakoon, T., Ishii, K., & Nassiraei, A. A. F. (2015). An Artificial Potential Field Based Mobile Robot Navigation Method To Prevent From Deadlock. Journal of Artificial Intelligence and Soft Computing Research, 5(3), 189-203.
5 Raja, R., Dutta, A., & Venkatesh, K. S. (2015). New potential field method for rough terrain path planning using genetic algorithm for a 6-wheel rover. Robotics and Autonomous Systems, 72, 295-306.
6 Root long history, Kai & Industry. (2015). D * Improved algorithm based on hierarchical indoor path planning. Computer Application Research, 32 (12), 3609-3612.
7 Pol, R. S., & Murugan, M. (2015, May). A review on indoor human aware autonomous mobile robot navigation through a dynamic environment survey of different path planning algorithm and methods. In Industrial Instrumentation and Control (ICIC), 2015 International Conference on (pp. 1339-1344). IEEE.
8 Hargas, Y., Mokrane, A., Hentout, A., Hachour, O., & Bouzouia, B. (2015, December). Mobile manipulator path planning based on artificial potential field: Application on RobuTER/ULM. In 2015 4th International Conference on Electrical Engineering (ICEE) (pp. 1-6). IEEE.
9 Hoy, M., Matveev, A. S., & Savkin, A. V. (2015). Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey. Robotica, 33(03), 463-497.
10 Shi, Q., Ishii, H., Sugahara, Y., Kinoshita, S., Takanishi, A., Okabayashi, S., ... & Fukuda, T. (2014, May). Control of posture and trajectory for a rat-like robot interacting with multiple real rats. In Robotics and Automation (ICRA), 2014 IEEE International Conference on (pp. 975-980). IEEE.
11 Triharminto, H. H., Prabuwono, A. S., Sulaiman, R., Setiawan, N. A., & Adji, T. B. (2014, January). Turning Strategy based on Modified Dubins Algorithm for Unmanned Aerial Vehicle Dynamic Path Planning. In International Conference on Advances in Intelligent Systems in Bioinformatics (2013). Atlantis Press.
12 Triharminto, H. H., Prabuwono, A. S., Sulaiman, R., Setiawan, N. A., & Adji, T. B. (2014). Turning decision strategy of dynamic path planning based on curve algorithm. Advances in Intelligent Systems, 53, 135.
13 Al-Mayyahi, A., Wang, W., & Birch, P. (2014). Adaptive Neuro-Fuzzy Technique for Autonomous Ground Vehicle Navigation. Robotics, 3(4), 349-370.
14 Thedchanamoorthy, S. (2014). Optimisation-based verification process of obstacle avoidance systems for unmanned vehicles (Doctoral dissertation, © Sivaranjini Thedchanamoorthy).
15 Goel, P., & Singh, D. (2014). Efficient ABC Algorithm for Dynamic Path Planning. International Journal of Computer Applications, 88(2).
16 Tamilselvi, D. (2014). Agent based path planning for Robot navigation.
17 Subramanian, M. B., Sudhagar, D. K., & RajaRajeswari, G. (2014). Optimal Path Forecasting of an Autonomous Mobile Robot Agent Using Breadth First Search Algorithm. International Journal of Mechanical & Mechatronics Engineering (IJMME-IJENS), 14(02).
18 Kumbhakar, C., Joshi, A., & Kumari, P. (2014, January). Fast Marching Method to Study Traveltime Responses of Three Dimensional Numerical Models of Subsurface. In Proceedings of the Third International Conference on Soft Computing for Problem Solving (pp. 411-421). Springer India.
19 Shi, Q., Ishii, H., Sugahara, Y., Takanishi, A., Huang, Q., & Fukuda, T. (2014). Design and control of a biomimetic robotic rat for interaction with laboratory rats.
20 Lekkas, A. M. (2014). Guidance and Path-Planning Systems for Autonomous Vehicles.
21 Qin, L., Yin, Q., Zha, Y., & Peng, Y. (2013). Dynamic Detection of Topological Information from Grid-Based Generalized Voronoi Diagrams. Mathematical Problems in Engineering, 2013.
22 Reyes, N. H., Barczak, A. L., & Susnjak, T. (2013). Tuning fuzzy-based hybrid navigation systems using calibration maps. In Robot Intelligence Technology and Applications 2012 (pp. 713-722). Springer Berlin Heidelberg.
23 Miao, X. F., & Wang, S. (2013). Path planning for mobile robot with artificial endocrine system. International Journal of Modelling, Identification and Control, 18(4), 387-394.
24 Nakhaeinia, D., & Karasfi, B. (2013). A behavior-based approach for collision avoidance of mobile robots in unknown and dynamic environments. Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology, 24(2), 299-311.
25 Huy, Q., Seiichi, M. I. T. A., Nejad, H. T. N., & Long, H. A. N. (2013). Dynamic and safe path planning based on support vector machine among multi moving obstacles for autonomous vehicles. IEICE TRANSACTIONS on Information and Systems, 96(2), 314-328.
26 Borkar, K. K., Tiwari, P., & Tiwari, V. (2013). Heuristic Rule Base Network Path Analysis and Planning of Wheeled Mobile Robots.
27 Li, Y., Song, Z. H., & Zhao, L. (2013, February). Path Planning for Mobile Robot with Clonal Selection Algorithm. In Applied Mechanics and Materials (Vol. 256, pp. 2943-2946).
28 Cruz-Bernal, A. (2013). Meta-Heuristic Optimization Techniques and Its Applications in Robotics. INTECH Open Access Publisher.
29 MP, S. K. (2013).Grid based path planning algorithms for extinguishing forest fires.
30 Guterman, H. (2013).Robil-robot israel. ben-gurion univ of the negev beersheba (israel) dept of electrical and computer engineering.
31 Raja, P., & Pugazhenthi, S. (2012). Optimal path planning of mobile robots: A review. International Journal of Physical Sciences, 7(9), 1314-1320.
32 Akhtaruzzaman, M., Shafie, A. A., & Rashid, M. (2012). Designing an Algorithm for Bioloid Humanoid Navigating in its Indoor Environment. Journal of Mechanical Engineering and Automation, 2(3), 36-44.
33 Subramanian, M. B., Sudhagar, K., & RajaRajeswari, G. Intelligent Path Planning Of Mobile Robot Agent By Using Breadth First Search Algorithm.
34 Akhtaruzzaman, M., & Shafie, A. (2011, December). Contriving a turning gait for an anthropomorphous system. In Research and Development (SCOReD), 2011 IEEE Student Conference on (pp. 95-100). IEEE.
35 Reyes, N. H., Barczak, A. L. C., & Susnjak, T. (2011). A reconfigurable hybrid intelligent system for robot navigation.
1 Google Scholar
2 CiteSeerX
3 refSeek
4 Scribd
5 slideshare
6 PdfSR
1 D. Adalsteinsson and J. Sethian, “A fast level set method for propagating interfaces,” J.Comput. Phys., vol. 118, no. 2, pp. 269–277, (1995).
2 F. Aurenhammer. “Voronoi Diagrams: A survey of a fundamental Geometric Data Structure,”ACM Computing Surveys, no. 23, 345-405, (1991).
3 F. Aurenhammer and R. Klein, Chapter 5 in Handbook of Computational Geometry. Eds. J.R.Sack and J. Urrutia, pp. 201–290, (2000).
4 H. Alt and O. Schwarzkopf, “The Voronoi Diagram of curved objects,” in Proc. 11th Annual ACM Symposium on Computational Geometry, pp. 89–97, (1995).
5 M. de Berg, M. van Krefeld, M. Overmars and O. Schwarzkopf, Computational Geometry:Algorithms ans Applications, 2nd rev.. Springer, (2000).
6 H. Blum, “A transformation for extracting new descriptors of shape,” in Models for Perception of Speech and Visual Form, W. W. Dunn, Ed.MIT Press, Cambridge, Mass., pp. 153–171, (1967).
7 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).
8 C. S. Chiang. “The Euclidean Distance Transform,” Ph. D. Thesis, Dept. Comp. Sci., Purdue University, (1992).
9 H. Choset. “Sensor Based Motion Planning: The Hierarchical Generalized Voronoi Graph,”PhD thesis, California Institute of Technology, Pasadena, California, March (1996).
10 H. Choset and Burdic. “Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph,” The International Journal of Robotics Research, vol. 19, pp. 96–125, (2000).
11 H. Choset et al., Principles of Robot Motion: Theory, Algorithms, and Implementations. The MIT Press, (2005).
12 J. L. Davis, Wave propagation in solids and fluids. Springer, (1988).
13 E. Dijkstra, “ A note on two problems in conexion with graphs,” Numerische Mathematik,vol. 1, pp. 269-271, (1959) .
14 D. Ferguson and A. Stentz, Advances in Telerobotics Field D*: An Interpolation-Based Path Planner and Replanner, Springer Berlin, pp. 239-253, (2007).
15 D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,”IEEE Robot. Automat. Mag., vol. 4, pp. 23–33, (1997).
16 N. Gagvani and D. Silver, “Parameter controlled skeletonization of three dimensional objects,” Technical Report CAIP-TR-216, Rutgers State University of New Jersey,http://citeseer.ist.psu.edu/gagvani97parameter.html, (1997).
17 S. Garrido, L.Moreno, “Robotic navigation using harmonic functions and finite elements,” in Intelligent Autonomous Systems IAS’9, pp. 94–103, (2006).
18 S. Garrido, L. Moreno, D. Blanco, and F. Martin, “Voronoi Diagram and Fast Marching applied to Path Planning.” in Proc of IEEE International conference on Robotics and Automation,ICRA’06. pp.3049-3054. (2006).
19 S. Garrido, L. Moreno and D. Blanco. “Sensor-based global planning for mobile robot navigation.” in Robotica. vol. 25. pp.189-199. (2007).
20 S. Garrido, L. Moreno, and D. Blanco, Exploration of a cluttered environment using voronoi transform and fast marching method, Robotics and Autonomous Systems,doi:10.1016/j.robot.2008.02.003 (2008).
21 M. Held. “Voronoi Diagrams and Offset Curves of Curvilinear Polygons.” Computer Aided Design, (1997).
22 S.S. Keerthi, C.J. Ong, E. Huang, and E.G. Gilbert, “Equidistance diagram- a new roadmap method for path planning,” In Proc. IEEE Int. Conf. On Robotics and Automation, pp 682-687,(1999).
23 O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” Int. J. Robot.Res., vol. 5, pp. 90–98, (1986).
24 Y. Koren and J. Borenstein, “Potential field methods and their inherent limitations for mobile robot navigation,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1398–1404, (1991).
25 S. Koenig and M. Likhachev, “ Improved fast replanning for robot navigation in unknown terrain,” in Proceedings of the IEEE International Conference on Robotics and Automation(ICRA), (2002).
26 J.-C. Latombe, Robot motion planning. Dordrecht, Netherlands: Kluwer Academic Publishers, (1991).
27 D.T. Lee, “Medial Axis Transform of a Planar Shape,” IEEE Trans. Pattern Anal.Mach. Intell.,PAMI-4, pp. 363-369, (1982).
28 M. Likhachev, G. Gordon, and S. Thrun,“ Advances in Neural Information Processing Systems ARA*: Anytime A* with provable bounds on sub-optimality ,” MIT Press, (2003).
29 S. R. Lindemann and S. M. LaValle,“ Simple and efficient algorithms for computing smooth,collision-free feedback laws”. International Journal of Robotics Research, (2007).
30 S. R. Lindemann and S. M. LaValle, “Smooth feedback for car-like vehicles in polygonal environments”. In Proceedings IEEE International Conference on Robotics and Automation,(2007).
31 R. Mahkovic and T. Slivnik “Generalized local Voronoi Diagram of visible region. In Proc.IEEE Int. Conf. On Robotics and Automation, pp. 349-355, Leuven, Belgium, May (1998).
32 S. Mauch, “Efficient algorithms for solving static Hamilton-Jacobi equations,” Ph.D.dissertation, California Inst. of Technology, (2003).
33 P. Melchior, B. Orsoni, O. Laviale, A. Poty, and A. Oustaloup, “Consideration of obstacle danger level in path planning using A* and fast marching optimisation: comparative study,”Journal of Signal Processing, vol. 83, no. 11, pp. 2387–2396, (2003).
34 J. Minguez and L. Montano, “Nearness diagram navigation: collision avoidance in troublesome scenarios,” IEEE Trans. Robot. and Automat., vol. 20, pp. 45–59, (2004).
35 K. Nagatani, H. Choset, and S. Thrun. “Towards exact localization without explicit localization with the generalized voronoi graph,” In Proc. IEEE Int. Conf. On Robotics and Automation, pp. 342-348, Leuven, Belgium, May (1998).
36 A. Nash, K. Danie, S. Koenig, and A. Felner, “Theta*: Any-Angle Path Planning,” on Grids Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), p. 1177-1183, (2007).
37 N. Nilsson, “Principles of artificial intelligence,” Palo alto, CA: Tioga Publishing Company.(1980).
38 R. Ogniewicz and O. Kubler, “Hierarchic Voronoi Skeletons,” Pattern Reconition, (1995).
39 A. Okabe, B. Boots, and K. Sugihara, “Spatial Tessellations: Concepts and Applications of Voronoi Diagrams”. John Wiley and Sons, Chichester, UK, (1992).
40 C. Petres, Y. Pailhas, P. Patron, Y. Petillot, J. Evans, D. Lane, “Path planning for autonomous underwater vehicles,” IEEE Trans. on Robotics, vol. 23, no. 2, pp. 331–341, (2007).
41 R. Philippsen, “An interpolated dynamic navigation function,” in 2005 IEEE Int. Conf. on Robotics and Automation, (2005).
42 A. Oustaloup. A. Poty, and P. Melchior, “Dynamic path planning by fractional potential,” in Second IEEE International Conference on Computational Cybernetics, (2004).
43 E. Prestes. Jr., P. Engel, M. Trevisan, and M. Idiart, “Exploration method using harmonic functions,” Journal of Robotics and Autonomous Systems, vol. 40, no. 1, pp. 25–42, (2002).
44 E. Prestes. Jr., P. Engel, M. Trevisan, and M. Idiart, “Autonomous learning architecture for environmental mapping,” Journal of Intelligent and Robotic Systems, vol. 39, pp. 243–263,(2004).
45 S. Quinlan and O. Khatib, “Elastic bands: connecting path planning and control,” in Proc.IEEE Int. Conf. on Robotics and Automation, pp. 802–807, (1993).
46 S. Quinlan and O. Khatib. “Efficient distance computation between non-convex objects,” in IEEE Int. Conf Robot and Autom., pp. 3324-3329, (1994).
47 J. A. Sethian, “A fast marching level set method for monotonically advancing fronts,” Proc.Nat. Acad Sci. U.S.A., vol. 93, no. 4, pp. 1591–1595, (1996).
48 J. A. Sethian, “Theory, algorithms, and applications of level set methods for propagating interfaces,” Acta numerica, pp. 309–395, (1996).
49 J. Sethian, Level set methods. Cambridge University Press, (1996).
50 R. Simmons, “The curvature-velocity method for local obstacle avoidance,” in Proc. IEEE Int.Conf. on Robotics and Automation, pp. 3375–3382, (1996).
51 R. W. Smith, “Computer processing of line images: A survey”, Pattern Recognition, vol. 20,no. 1, pp. 7-15, (1987).
52 A. Stentz, “The focused D* Algorithm for Real-Time Replanning,” Proceedings of the Internatinal Joint Conference on Artificial Intelligence (IJCAI), (1995).
53 N. Sudha, S. Nandi, and K. Sridharan, “ A parallel algorithm to construct Voronoi Diagram and its VLSI architecture,” In Proc. IEEE Int. Conf. On Robotics and Automation, pages 1683-1688, (1999).
54 J. N. Tsitsiklis, “Efficient Algorithms for Globally Optimal Trajectories,” IEEE Transactions on Automatic Control, vol. 40, pp. 1528-1538, (1995).
55 I. Ulrich and J. Borenstein, “Vfh+: reliable obstacle avoidance for fast mobile robots,” in Proc.IEEE Int. Conf. on Robotics and Automation, pp. 1572–1577, (1998).
56 I. Ulrich and J. Borenstein, “Vfh*: local obstacle avoidance with look-ahead verification,” in Proc. IEEE Int. Conf. on Robotics and Automation, pp. 2505–2511, (2000).
57 S. A. Wilmarth, N. M. Amato, and P. F. Stiller, “MAPRM: A probabilistic roadmap Planner with sampling on the medial axis of the free space”. In Proc. IEEE Int. Conf. On Robotics and Automation, pp. 1024-1031, (1999).
58 L. Yang and S. M. LaValle, “A framework for planning feedback motion strategies based on a random neighborhood graph”. In Proceedings IEEE International Conference on Robotics and Automation, pp. 544–549, (2000).
59 L.Yatziv, A. Bartesaghi, and G.Sapiro, “A fast O(n) implementation of the fast marching algorithm,” Journal of Computational Physics, vol. 212, pp. 393–399, (2005).
Associate Professor Santiago Garrido
Departamento de sistemas y automática Universidad Carlos III de Madrid Leganés - Spain
Dr. Luis Moreno
Departamento de sistemas y automática Universidad Carlos III de Madrid Leganés - Spain
Dr. Dolores Blanco
Departamento de sistemas y automática Universidad Carlos III de Madrid Leganés - Spain
Mr. Piotr Pawel Jurewicz
Departamento de sistemas y automática Universidad Carlos III de Madrid Leganés - Spain