Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-22T07:30:42.100Z Has data issue: false hasContentIssue false
  • English
  • Français

Nonprobabilistic anytime algorithm for high-quality trajectories in high-dimensional spaces

Published online by Cambridge University Press:  23 June 2011

Andrés S. Vázquez  and
Antonio Adán
Andrés S. Vázquez*
Affiliation:
Escuela Superior de Informática, Universidad de Castilla-La Mancha, Paseo de la Universidad, 4, 13071, Ciudad Real, Spain E-mail: [email protected]
Antonio Adán
Affiliation:
Escuela Superior de Informática, Universidad de Castilla-La Mancha, Paseo de la Universidad, 4, 13071, Ciudad Real, Spain E-mail: [email protected]
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

This paper proposes a feasible variation of approximate grid-based path-planning methods, which have been replaced with probabilistic methods nowadays, due mainly to their impracticality in high-dimensional spaces. Our aim is to demonstrate that, with an incremental exploration of the CSpace by means of Interpolated walk primitives and ANY-Time algorithms, we can generate – online – high-quality solutions that can be compared with probabilistic methods and can even improve some aspects, such as the completeness. Computational time, path smoothness, path clearance, and path distance are the qualifiers used to evaluate the path planner. These quality factors are critical in robotics. In fact, in both mobile and industrial robots, the computational time is a primary requirement to work online, the clearance gives security to the movements of the robot, and the smoothness can prolong the life of the mechanical components. Our method has been compared to probabilistic path planners, with the feasibility and benefits of our algorithm being proved in terms of the quality factors aforementioned.

Keywords

Path planningAnytime algorithms
Type
Articles
Information
Robotica , Volume 30 , Issue 2 , March 2012 , pp. 289 - 303
Copyright
Copyright © Cambridge University Press 2011

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.LaValle, S. M., Planning Algorithms (Cambridge University Press, New York, NY, USA, 2006).CrossRefGoogle Scholar
2.Latombe, J.-C., Robot Motion Planning (Kluwer Academic Publishers, Norwell, MA, USA, 1991).CrossRefGoogle Scholar
3.Zilberstein, S. and Russell, S., “Approximate Reasoning Using Anytime Algorithms,” In: Imprecise and Approximate Computation (Kluwer Academic Publishers, Dordrecht, 1995) vol. 318, pp. 43–62.CrossRefGoogle Scholar
4.Hansen, E., Zhou, R. and Zilberstein, S., “Anytime heuristic search,” J. Artif. Intell. Res. 28, 267–297 (2007).CrossRefGoogle Scholar
5.Likhachev, M., Ferguson, D., Gordon, G., Stentz, A. and Thrun, S., “Anytime Dynamic A*: An Anytime, Replanning Algorithm,” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), Monterey, CA, USA (2005) pp. 262–271.Google Scholar
6.Kavraki, L. and Latombe, J., “Probabilistic Roadmaps for Robot Path Planning,” In: Practical Motion Planning in Robotics: Current Approaches and Future Directions (John Wiley & Sons, New York, NY, USA, 1998) vol. 53, pp. 33–53.Google Scholar
7.Belghith, K., Kabanza, F., Hartman, L. and Nkambou, R., “Anytime Dynamic Path-Planning with Flexible Probabilistic Roadmaps,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Orlando, FL, USA (2006).Google Scholar
8.LaValle, S., Rapidly-Exploring Random Trees: A New Tool for Path Planning. Technical Report, TR1-98-11. Computer Science Department, Iowa State University (1998).Google Scholar
9.van den Berg, J., Ferguson, D. and Kuffner, J., “Anytime Path Planning and Replanning in Dynamic Environments,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Orlando, FL, USA (2006), pp. 2366–2371.Google Scholar
10.LaValle, S. M., Kuffner, J. and James, J., “Randomized kinodynamic planning,” Int. J. Robot. Res. 20 (5), 378–400 (2001).CrossRefGoogle Scholar
11.Knepper, R. A. and Kelly, A., “High Performance State Lattice Planning Using Heuristic Look-Up Tables,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, China (2006), pp. 3375–3380.Google Scholar
12.Likhachev, M. and Ferguson, D., “Planning long dynamically feasible maneuvers for autonomous vehicles,” Int. J. Robot. Res. 28 (8), 933–945 (2009).CrossRefGoogle Scholar
13.Blum, A. and Furst, M., “Fast planning through planning graph analysis,” Artif. Intell. 90 (1–2), 281–300 (1997).CrossRefGoogle Scholar
14.Geraerts, R. and Overmars, M., “Creating high-quality paths for motion planning,” Int. J. Robot. Res. 26 (8), 845–863 (2007).CrossRefGoogle Scholar
15.Paulos, E., On-Line Collision Avoidance for Multiple Robots Using b-Splines. Technical Report, UCB/CSD-98-977. EECS Department, University of California, Berkeley (Jan. 1998).Google Scholar
16.Yueshi Shen Huper, K., “Optimal Trajectory Planning of Manipulators Subject to Motion Constraints,” Proceedings of the International Conference on Advanced Robotics (ICAR) Seattle, WA, USA (2005).Google Scholar
17.Song, G. and Amato, N. M., “Randomized Motion Planning for Car-Like Robots with c-prm,” Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), Maui, HI, USA (2001), pp. 37–42.Google Scholar
18.Piazzi, C. G. L. B. A. and Romano, M., “eta 3-Splines for the Smooth Path Generation of Wheeled Mobile Robots,” IEEE Transactions on Robotics 23 (5), 1089–1095 (Oct. 2007).CrossRefGoogle Scholar
19.Mcconley, M. W., Piedmonte, M. D., Appleby, B. D., Frazzoli, E., Feron, E. and Dahleh, M. A., “Hybrid Control for Aggressive Maneuvering of Autonomous Aerial Vehicles,” Proceedings of the Digital Avionics Systems Conferences (DASC), Philadelphia, PA, USA (2000) pp. 1E4/1–1E4/8.Google Scholar
20.Gordeau, R., Roboop – A Robotics Object Oriented Package in C++, Département de génie électrique École Polytechnique de Montréal (2005).Google Scholar
21.Smith, R., Open dynamics engine, at http://www.ode.orgGoogle Scholar
22.Davies, R., Newmat C++ Matrix Library (2002).Google Scholar
23.Sanchez, G. and Latombe, J.-C., “A single-query bi-directional probabilistic roadmap planner with lazy collision checking,” Int. J. Robot. Res. 6, 403–417 (2003).CrossRefGoogle Scholar
24.Nissoux, C., Simeon, T. and Laumond, J., “Visibility Based Probabilistic Roadmaps,” Proceedings of the IEEE/RSJ Intelligent Robots and Systems (IROS), Kyongju, Korea (1999) vol. 3, pp. 1316–1321.Google Scholar
25.Bohlin, R. and Kavraki, L., “Path Planning Using Lazy PRM,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, USA (2000) vol. 1, pp. 521–528.Google Scholar
26.LaValle, S. and Kuffner, J., “Rapidly-Exploring Random Trees: Progress and Prospects,” Proceedings of the Fourth Workshop on the Algorithmic Foundations of Robotics, AK Peters Ltd. (2001).Google Scholar
27.Kuffner, J. Jr., and LaValle, S., “RRT-Connect: An Efficient Approach to Single-Query Path Planning,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, USA (2000) vol. 2, pp. 995–1001.Google Scholar