Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-21T22:25:19.234Z Has data issue: false hasContentIssue false
  • English
  • Français

Tangent bundle RRT: A randomized algorithm for constrained motion planning

Published online by Cambridge University Press:  28 May 2014

Beobkyoon Kim ,
Terry Taewoong Um ,
Chansu Suh  and
F. C. Park
Beobkyoon Kim
Affiliation:
Robotics Laboratory, Seoul National University, Seoul 151-744, Korea
Terry Taewoong Um
Affiliation:
Robotics Laboratory, Seoul National University, Seoul 151-744, Korea
Chansu Suh
Affiliation:
Robotics Laboratory, Seoul National University, Seoul 151-744, Korea
F. C. Park*
Affiliation:
Robotics Laboratory, Seoul National University, Seoul 151-744, Korea
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

The Tangent Bundle Rapidly Exploring Random Tree (TB-RRT) is an algorithm for planning robot motions on curved configuration space manifolds, in which the key idea is to construct random trees not on the manifold itself, but on tangent bundle approximations to the manifold. Curvature-based methods are developed for constructing tangent bundle approximations, and procedures for random node generation and bidirectional tree extension are developed that significantly reduce the number of projections to the manifold. Extensive numerical experiments for a wide range of planning problems demonstrate the computational advantages of the TB-RRT algorithm over existing constrained path planning algorithms.

Keywords

Motion planningPath planningControl of robotic systemsRedundant manipulatorsService robots
Type
Articles
Information
Robotica , Volume 34 , Issue 1 , January 2016 , pp. 202 - 225
Copyright
Copyright © Cambridge University Press 2014 

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.Berenson, D., Srinivasa, S., Ferguson, D. and Kuffner, J., “Manipulation Planning on Constraint Manifolds,” Proceedings of the IEEE International Conference Robotics and Automation (2009) pp. 625–632.Google Scholar
2.Berenson, D., Srinivasa, S. and Kuffner, J., “Task space regions: A framework for pose-constrained manipulation planning,” Int. J. Robot. Res. 30 (12), 1435–1460 (2011).CrossRefGoogle Scholar
3.Cortés, J. and Siméon, T., “Probabilistic Motion Planning for Parallel Mechanisms,” Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3 (2003) pp. 4354–4359.Google Scholar
4.Han, L., Rudolph, L., Blumenthal, J. and Valodzin, I., “Stratified Deformation Space and Path Planning for a Planar Closed Chain with Revolute Joints,” In: Algorithmic Foundation of Robotics VII (WAFR 2006), Springer Tracts in Advanced Robotics, vol. 47 (Akella, S., Amato, N., Huang, W. and Mishra, B., eds.) (Springer New York, 2006) pp. 235–250.Google Scholar
5.Henderson, M. E., “Multiple parameter continuation: Computing implicitly defined k-manifolds,” Int. J. Bifurcation Chaos 12 (3), 451–476 (2001).CrossRefGoogle Scholar
6.Jaillet, L., Yershova, A., LaValle, S. and Simeon, T., “Adaptive Tuning of the Sampling Domain for Dynamic-Domain RRTs,” Proceedings of the IEEE/RSJ International Conference Intelligent Robots and Systems (2005) pp. 2851–2856.Google Scholar
7.Koga, Y., Kondo, K., Kuffner, J. and Latombe, J., “Planning Motions with Intentions,” Proceedings of the Siggraph (1994) pp. 395–408.Google Scholar
8.LaValle, S., Rapidly-Exploring Random Trees: A New Tool for Path Planning, TR 98-11 (Computer Science Dept., Iowa State University, Oct. 1998).Google Scholar
9.LaValle, S. and Kuffner, J., “Rapidly Exploring Random Trees: Progress and Prospects,” In: Algorithmic and Computational Robotics: New Directions (Donald, B. R., Lynch, K. M. and Rus, D., eds.) (A K Peters, Wellesley, MA, 2001) pp. 293–308.Google Scholar
10.Sanchez, G. and Latombe, J., “A Single Query Bi-Directional Probabilistic Roadmap Planner with Lazy Collision Checking,” In: Springer Tracts in Advanced Robotics, vol. 6 (Springer, 2003) pp. 403–417.Google Scholar
11.Sentis, S. and Khatib, O., “Synthesis of whole-body behaviors through hierarchical control of behavioral primitives,” Int. J. Humanoid Robot. 2 (4), 505–518 (2005).CrossRefGoogle Scholar
12.Shvalb, N., Liu, L. G., Shoham, M. and Trinkle, J. C., “Motion planning for a class of planar closed-chain manipulators,” Int. J. Robot. Res. 26 (5), 457–474 (2007).CrossRefGoogle Scholar
13.Stilman, M., “Task Constrained Motion Planning in Robot Joint Space,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (2007) pp. 3074–3081.Google Scholar
14.Tang, X., Thomas, S., Coleman, P. and Amato, N., “Reachable distance space: efficient sampling-based planning for spatially constrained systems,” Int. J. Robot. Res. 29 (7), 916–934 (2010).CrossRefGoogle Scholar
15.Um, T. T., Suh, C., Kim, B. and Park, F. C., “Tangent Space RRT with Lazy Projection: An Efficient Planning Algorithm for Constrained Motions,” In: Advances in Robot Kinematics (Lenarcic, J. and Stanisic, M., eds.) (Springer Netherlands, 2010) pp. 251–260.Google Scholar
16.Yakey, J. H., LaValle, S. and Kavraki, L., “Randomized path planning for linkages with closed kinematic chains,” IEEE Trans. Robot. Autom. 17 (6), 951–958 (2001).CrossRefGoogle Scholar
17.Yamane, K., Kuffner, J. and Hodgins, J., “Synthesizing animations of human manipulation tasks,” ACM Trans. Graph. 23 (3), 532–539 (2004).CrossRefGoogle Scholar
18.Yershova, A., MPNN: Nearest Neighbor Library for Motion Planning, (2005) [Online]. Available at http://msl.cs.uiuc.edu/~yershova/MPNN/MPNN.htm.Google Scholar
19.Yershova, A., Jaillet, L., Simeon, T. and LaValle, S., “Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain,” Proceedings of the IEEE International Conference on Robotics and Automation (2005) pp. 3856–3861.Google Scholar
20.Lindermann, S. and LaValle, S., “Incrementally Reducing Dispersion by Increasing Voronoi Bias in RRTs,” Proceedings of the IEEE International Conference on Robotics and Automation, vol. 4 (2004) pp. 3251–3257.Google Scholar
21.Suh, C., Um, T., Kim, B., Noh, H., Kim, M. and Park, F. C., “Tangent Space RRT: A Randomized Planning Algorithm on Constraint Manifolds,” Proceedings of the IEEE International Conference on Robotics and Automation (2011) pp. 4968–4973.Google Scholar
22.Suh, C., Kim, B. and Park, F. C., “The Tangent Bundle RRT Algorithms for Constrained Motion Planning,” Proceedings of the 13th World Congress in Mechanism and Machine Science, Guanajuato, Mexico (2011).Google Scholar
23.Porta, J. M. and Jaillet, L., “Path Planning on Manifolds Using Randomized Higher-Dimensional Continuation,” In: Algorithmic Foundations of Robotics IX (WAFR 2010) (Hsu, D., Isler, V., Latombe, J.C. and Lin, M., eds.) (Springer Berlin Heidelberg, 2011) pp. 337–353.Google Scholar
24.Jaillet, L. and Porta, J. M., “Path Planning with Loop Closure Constraints Using an Atlas-Based RRT,” Proceedings of the 15th International Symposium on Robotics Research (ISRR), Flagstaff, USA (2011).Google Scholar
25.Park, F. C. and Bobrow, J., “Geometric optimization algorithms for robot kinematic design,” J. Robot. Syst. 12 (6), 453–463 (1995).CrossRefGoogle Scholar