Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-30T15:58:37.485Z Has data issue: false hasContentIssue false
  • English
  • Français

Vodec: A fast Voronoi algorithm for car-like robot path planning in dynamic scenarios

Published online by Cambridge University Press:  23 January 2012

Diego A. López García  and
Fernando Gomez-Bravo
Diego A. López García
Affiliation:
Department of Electronic Engineering and Automation, University of Huelva, La Rábida, Huelva, Spain
Fernando Gomez-Bravo*
Affiliation:
Department of Electronic Engineering and Automation, University of Huelva, La Rábida, Huelva, Spain
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

Traditionally, robot motion planners use Voronoi Diagrams for generating admissible paths that connect an initial with a final configuration. When dynamic scenarios are involved, these techniques imply a heavy computational cost. The novelty of the technique presented here is that it can provide fast and particularly suitable routes without considering the full scenario if environmental changes appear. The new method is designed to work with a post-process technique in order to provide admissible paths for car-like robots coping with kinematic constraints. This new approach is capable of supplying continuous paths and also elaborate maneuvers if cluttered environments are involved.

Keywords

Path planningVoronoi diagramsNonholonomic robotsRestricted maneuvers
Type
Articles
Information
Robotica , Volume 30 , Issue 7 , December 2012 , pp. 1189 - 1201
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Aichholzer, O. and Aurenhammer, F., “Straight skeletons for general polygonal figures,” Technical Report 432, (Institute of Theoretical Computer Science, Graz University of Technology, Graz, Austria, 1995).CrossRefGoogle Scholar
2. Aurenhammer, F. and Klein, R., “Voronoi diagrams,” Handbook of Computational Geometry (Sack, J. and Urrutia, G., eds.) (Elsevier, Amsterdam, Netherlands, 2000) pp. 201–290.CrossRefGoogle Scholar
3. Cuesta, F., Gómez-Bravo, F. and Ollero, A., “Parking manoeuvres of industrial-like electrical vehicles with and without trailer,” IEEE Trans. Ind. Electron. 51 (2), 257–269 (2004).CrossRefGoogle Scholar
4. Gomez-Bravo, F., López, D., Real, F. J., Merino, L. and Sánchez-Matamoros, J. M. l., “Integrated Path Planning and Tracking for Autonomous Car-Like Vehicles Maneuvering,” Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics, Milan, Italy (2009) pp. 457–464.Google Scholar
5. Gomez-Bravo, F., Cuesta, F., Ollero, A. and Viguria, L. A., “Continuous curvature path generation based on β-spline curves for parking manoeuvres,” Robot. Auton. Syst. 56 (4), 360–372 (2008).CrossRefGoogle Scholar
6. Martin, J. M., López, D., Gomez-Bravo, F. and Blanco, A., “Application of multicriteria decision-making techniques to manoeuvre planning in nonholonomic robots,” Expert Syst. Appl. 37, 3962–3976 (2010).CrossRefGoogle Scholar
7. Gomez-Bravo, F., Ollero, A., Cuesta, F. and López, D., “A new approach for car like robots manoeuvring based on RRT,” Robótica: Automaçao, Controlo e Instrumentaçao, 71, 10–14 (2008).Google Scholar
8. Gomez-Bravo, F., Ollero, A., Cuesta, F. and Lopez, D., “Rrt-d: A Motion Planning Approach for Autonomous Vehicles Based on Wireless Sensor Network Information,” Proceedings of the 6th IFAC Symposium on Intelligent AutonomousVehicles, Toulouse, Francia (2007) pp. C.D.Google Scholar
9. Fortune, S. J., “A sweepline algorithm for Voronoi diagrams,” Algorithmica, 2, 153–174 (1987).CrossRefGoogle Scholar
10. Latombe, J. C., Robot Motion Planning (Kluwer Academic Pulisher, Boston, MA 1991).CrossRefGoogle Scholar
11. Laumont, J. P., Jacobs, P. E., Taix, M. and Murray, M., “A motion planner for nonholonomic mobile robots,” IEEE Trans. Robot. Autom., 10 (5), 577–593 (1994).CrossRefGoogle Scholar
12. LaValle, S. M., Planning Algorithms (Cambridge University Press, Cambridge, U.K. 2006).CrossRefGoogle Scholar
13. LaValle, S. M., “Rapidly-Exploring Random Trees: Progress and Prospects,” In: Algorithmic and Computational Robotics: New Directions (Peters, A. K., ed.) (Wellesley, MA, 2001) pp. 293–308.Google Scholar
14. McAllister, M., Kirkpatrick, D. and Snoeyink, J., “A compact piecewise-linear Voronoi diagram for convex sites in the plane,” Discrete Comput. Geom. 15, 73–105 (1996).CrossRefGoogle Scholar
15. Ollero, A., Arrue, B. C., Ferruz, J., Heredia, G., Cuesta, F., Lopez-Pichaco, F. and Nogales, C., “Control and perception componenets for autonomous vehicle guidance. application to the romeo vehicles,” Control Eng. Pract. 7, 1291–1299 (1999).CrossRefGoogle Scholar
16. Papadopoulou, E. and Lee, D. T., “The L∞ Voronoi Diagram of segments and VLSI applications,” Int. J. Comput. Geom. Appl. 11 (5), 503–528 (2001).CrossRefGoogle Scholar
17. Lamiraux, F. and Lamond, J. P., “Smooth motion planning for car-like vehicles,” IEEE Trans. Robot. Autom. 17 (4), 498–502 (2001).CrossRefGoogle Scholar
18. Rezaei, S., Guivant, J. and Nebot, E., “Car-Like Robot Path Following in Large Unstructured Environments,” Proceedings of 1993 IEEE International Conference on Intelligent Robots and Systems, Las Vegas, USA (2003) pp. 2468–2473.Google Scholar
19. Baran, N. and Kumar, D., “Automatic design of fuzzy logic controller using a genetic algorithm for collision-free, time-optimal navigation of a car-like robot,” Int. J. Hybrid Intell. Syst. 2 (3), 161–187 (2005).Google Scholar
20. Esquivel, W. D. and Chiang, L. E., “Nonholonomic path planning among obstacles subject to curvature restrictions,” Robotica 20, 49–58 (2002).CrossRefGoogle Scholar
21. Rosales, A., Scaglia, G.o., Mut, V. and di Sciascio, F., “Trajectory tracking of mobile robots in dynamic environments a linear algebra approach,” Robotica 27, 981–997 (2009).CrossRefGoogle Scholar
22. Xidias, E. K. and Aspragathos, N. A., “Motion planning for multiple non-holonomic robots: a geometric approach,” Robotica 26, 525–536 (2008).CrossRefGoogle Scholar
23. López, D., Nuevas aportaciones en algoritmos de planificación para la ejecución de maniobras en robots autónomos no holónomos Ph. D. dissertation (Spain: University of Huelva, 2011).Google Scholar
24. Razvan, S. and Urbano, N., “Trajectory planning and sliding-mode control based trajectory-tracking for cybercars,” Integr. Comput.-Aided Eng. 14 (1), 33–48 (2007).Google Scholar
25. Sipahioglu, A., Yazici, A., Parlaktuna, O. and Gurel, U., “Real-time tour construction for a mobile robot in a dynamic environment,”. Robot. Auton. Syst. 56 (4), 289–384 (2008).CrossRefGoogle Scholar