Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-22T08:11:00.007Z Has data issue: false hasContentIssue false
  • English
  • Français

Sensor-based global planning for mobile robot navigation

Published online by Cambridge University Press:  01 March 2007

S. Garrido ,
L. Moreno ,
D. Blanco  and
M. L. Munoz
S. Garrido
Affiliation:
Carlos III University, Avd. de la Universidad, 30 28911, Leganés, Madrid, Spain
L. Moreno*
Affiliation:
Carlos III University, Avd. de la Universidad, 30 28911, Leganés, Madrid, Spain
D. Blanco
Affiliation:
Carlos III University, Avd. de la Universidad, 30 28911, Leganés, Madrid, Spain
M. L. Munoz
Affiliation:
Facultad de Informática, Universidad Politécnica de Madrid, 28660 Boadilla del Monte, Madrid, Spain
*
*Corresponding author. E-mail: [email protected].
Get access Rights & Permissions [Opens in a new window]

Summary

The proposed algorithm integrates in a single planner the global motion planning and local obstacle avoidance capabilities. It efficiently guides the robot in a dynamic environment. This eliminates some of the traditional problems of planned architectures (model-plan-act scheme) while obtaining many of the qualities of behavior-based architectures. The computational efficiency of the method allows the planner to operate at high-rate sensor frequencies. This avoids the need for using both a collision-avoidance algorithm and a global motion planner for navigation in a cluttered environment. The method combines map-based and sensor-based planning operations to provide a smooth and reliable motion plan. Operating on a simple grid-based world model, the method uses a fast marching technique to determine a motion plan on a Voronoi extended transform extracted from the environment model. In addition to this real-time response ability, the method produces smooth and safe robot trajectories.

Keywords

Sensor-based global path plannerFast marchingmobile robotsmobile manipulators
Type
Article
Information
Robotica , Volume 25 , Issue 2 , March 2007 , pp. 189 - 199
Copyright
Copyright © Cambridge University Press 2007

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.Meystel, A., “Planning in a hierarchical nested autonomous control system,” Mobile Robots, SPIE Proc. 727, 42–76 (1986).Google Scholar
2.Brooks, R., “A robust layered control system for a mobile robot,” IEEE Trans. Robot. Autom. 2 (1), 14–23 (1986).CrossRefGoogle Scholar
3.Arkin, R. C., “Integrating behavioral, perceptual and world knowledge in reactive navigation,” Robot. Autonomous Syst. 6, 105–122 (1990).CrossRefGoogle Scholar
4.Arkin, R. C., Behaviour-Based Robotics (MIT Press, Cambridge, MA, 1998).Google Scholar
5.Alami, R., Chatila, R., Fleury, S., Ghallab, M. and Ingrand, F., “An architecture for autonomy,” Int. J. Robot. Res. 17 (4), 315–337 (1998).CrossRefGoogle Scholar
6.Chatila, R., “Deliberation and reactivity in autonomous mobile robot,” J. Robot. Syst. Autonomous Syst. 16, 197–211 (1995).CrossRefGoogle Scholar
7.Bonasso, R., Kortenkamp, D., Miller, D. and Slack, M., “Experiences with an architecture for intelligent, reactive agents,” Lect. Notes Comput. Sci. 1037, 187–202 (1996).CrossRefGoogle Scholar
8.Low, K. H., Leow, W. K. and Ang, M. H., “A hybrid mobile robot architecture with integrated planning and control,” in Proceedings of the 1st International Conference on Autonomous Agents and Multiagent (AMAS'02), Bologna, Italy (2002) pp. 219–226.Google Scholar
9.Sethian, J., Level Set Methods (Cambridge University Press, Cambridge, UK, 1996).Google Scholar
10.Latombe, J.-C., Robot Motion Planning (Kluwer, Dordrecht, The Netherlands, 1991).CrossRefGoogle Scholar
11.Khatib, O., “Real-time obstacle avoidance for manipulators and mobile robots,” Int. J. Robot. Res. 5, 90–98 (1986).CrossRefGoogle Scholar
12.Borenstein, J. and Koren, Y., “The vector field histogram—Fast obstacle avoidance for mobile robots,” IEEE Trans. Robot. Autom. 7 (3), 278–288 (1991).CrossRefGoogle Scholar
13.Ulrich, I. and Borenstein, J., “Vfh+: Reliable obstacle avoidance for fast mobile robots,” in Proceedings of the IEEE International Conference on Robotics and Automation, Leuven, Belgium (1998) pp. 1572–1577.Google Scholar
14.Ulrich, I. and Borenstein, J., “Vfh*: Local obstacle avoidance with look-ahead verification,” in Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA (2000) pp. 2505–2511.Google Scholar
15.Simmons, R., “The curvature-velocity method for local obstacle avoidance,” in Proceedings of the IEEE International Conference on Robotics and Automation, Minneapolis, MN (1996) pp. 3375–3382.CrossRefGoogle Scholar
16.Fox, D., Burgard, W. and Thrun, S., “The dynamic window approach to collision avoidance,” IEEE Robot. Autom. Mag. 4, 23–33 (1997).CrossRefGoogle Scholar
17.Minguez, J. and Montano, L., “Nearness diagram navigation: Collision avoidance in troublesome scenarios,” IEEE Trans. Robot. Automat. 20, 45–59 (2004).CrossRefGoogle Scholar
18.Quinlan, S. and Khatib, O., “Elastic bands: Connecting path planning and control,” in Proceedings of the IEEE International Conference on Robotics and Automation, Atlanta, GA (1993) pp. 802–807.Google Scholar
19.Koren, Y. and Borenstein, J., “Potential field methods and their inherent limitations for mobile robot navigation,” in Proceedings of the IEEE International Conference on Robotics and Automation, Sacramento, CA (1991) pp. 1398–1404.Google Scholar
20.Rimon, E. and Koditschek, D., “Exact robot navigation using artificial potential functions,” IEEE Trans. Robot. Autom. 8 (5), 501–518 (1992).CrossRefGoogle Scholar
21.Moreno, S. L., “Evolutionary filter for robust mobile robot global localization,” Robot. Autonomous Syst. 54 (7), 590–600 (2006).CrossRefGoogle Scholar
22.Breu, H., Gil, J., Kirkpatrick, D. and Werman, M., “Linear time Euclidean distance transform algorithms,” IEEE Trans. Pattern Anal. Mach. Intell. 17 (5), 529–533 (1995).CrossRefGoogle Scholar
23.Yatziv, L., Bartesaghi, A. and Sapiro, G., “A fast o(n) implementation of the fast marching algorithm,” J. Comput. Phys. 212, 393–399 (2005).CrossRefGoogle Scholar
24.Maurer, J. C. R., Qi, R. and Raghavan, V., “A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions,” J. IEEE Trans. Pattern Anal. Mach. Intell. 25 (2), 265–270 (2003).CrossRefGoogle Scholar
25.Sethian, J. A., “A fast marching level set method for monotonically advancing fronts,” Proc. Natl. Acad. Sci. U.S.A. 93 (4), 1591–1595 (1996).CrossRefGoogle ScholarPubMed
26.Sethian, J. A., “Theory, algorithms, and aplications of level set methods for propagating interfaces,” Acta Numerica (Cambridge University Press, Cambridge, UK, 1996) pp. 309–395.Google Scholar
27.Adalsteinsson, D. and Sethian, J., “A fast level set method for propagating interfaces,” J. Comput. Phys. 118 (2), 269–277 (1995).CrossRefGoogle Scholar
28.Minguez, J. and Montano, L., “Global nearness diagram navigation,” in Proceedings of the IEEE International Conference on Robotics and Automation, Seoul, Korea (2001) pp. 33–39.Google Scholar
29.Prestes, E.Silva, e Jr., Engel, P., Trevisan, M. and Idiart, M., “Exploration method using harmonic functions,” J. Robot. Autonomous Syst. 40 (1), 25–42 (2002).CrossRefGoogle Scholar
30.Prestes, E.Silva, e Jr., Engel, P., Trevisan, M. and Idiart, M., “Autonomous learning architecture for environmental mapping,” J. Intell. Robot. Syst. 39, 243–263 (2004).Google Scholar
31.Garrido, S. and Moreno, L., “Robotic navigation using harmonic functions and finite elements,” in Proceedings of the Intelligent Autonomous System (IAS'9), Tokyo, Japan (2006) pp. 94–103.Google Scholar
32.Fomel, S., “A variational formulation of the fast marching eikonal solver,” Stanford Exploration Project, Technical Report (2000) pp. 455–477.Google Scholar
33.Zhao, H., “A fast sweeping method for eikonal equations,” Math. Comput. 74 (250), 603–627 (2005).CrossRefGoogle Scholar
34.Smirnov, V. I., (1964), A course on higher mathematics: Pergamon Press.Google Scholar