RRT-connect: An efficient approach to single-query path planning
Abstract
A simple and efficient randomized algorithm is presented for solving single-query path planning problems in high-dimensional configuration spaces. The method works by incrementally building two rapidly-exploring random trees (RRTs) rooted at the start and the goal configurations. The trees each explore space around them and also advance towards each other through, the use of a simple greedy heuristic. Although originally designed to plan motions for a human arm (modeled as a 7-DOF kinematic chain) for the automatic graphic animation of collision-free grasping and manipulation tasks, the algorithm has been successfully applied to a variety of path planning problems. Computed examples include generating collision-free motions for rigid objects in 2D and 3D, and collision-free manipulation motions for a 6-DOF PUMA arm in a 3D workspace. Some basic theoretical analysis is also presented.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Sampling-based motion planning faces performance degradation with increasing occluders as the probability of valid sampling rapidly diminishes.
“Moreover, sampling-based motion planning [19, 35], a kind of commonly used approach for planning and manipulation, also faces performance degradation with increasing occluders [38] as the probability of valid sampling rapidly diminishes.”
From Learning Environment-Aware Affordance for 3D Articulated Object Manipulation under Occlusions (2023) · cites this paper as [19]
Point-level affordance may be more suitable than sampling-based planners for manipulating articulated objects within complex constraints, because it directly provides per-point actionable priors.
“Comparisons between RTT-CA and affordance methods show that, while sampling-based planners may face difficulty in complicated scenes, point-level affordance may be more suitable by directly providing per-point actionable priors for manipulating articulated objects within complex constraints.”
From Learning Environment-Aware Affordance for 3D Articulated Object Manipulation under Occlusions (2023) · cites this paper as [19]
Cites
Probabilistic roadmaps for path planning in high-dimensional configuration spaces
Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.508439 · Cited by 6,343 · see citing works
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Perception, Planning, Control, and Coordination for Autonomous Vehicles
Pendleton, S., Andersen, H., Du, X., Shen, X., Meghjani, M., Eng, Y., Rus, D., & Ang, M. (2017) · Machines · doi:10.3390/machines5010006 · Cited by 657 · see citing works
A review of verbal and non-verbal human–robot interactive communication
Mavridis, N. (2015) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2014.09.031 · Cited by 453 · see citing works
Task Space Regions: A framework for pose-constrained manipulation planning
Berenson, D., Srinivasa, S., & Kuffner, J. (2011) · The International Journal of Robotics Research · doi:10.1177/0278364910396389 · Cited by 368 · see citing works
Self-citationA dynamical system approach to realtime obstacle avoidance
Khansari-Zadeh, S. M., & Billard, A. (2012) · Autonomous Robots · doi:10.1007/s10514-012-9287-y · Cited by 264 · see citing works
Anticipatory robot control for efficient human-robot collaboration
Huang, C.-M., & Mutlu, B. (2016) · 2016 11th ACM/IEEE International Conference on Human-Robot Interaction (HRI) · doi:10.1109/hri.2016.7451737 · Cited by 227 · see citing works
Folding clothes autonomously: A complete pipeline
Doumanoglou, A., Stria, J., Peleka, G., Mariolis, I., Petrik, V., Kargakos, A., Wagner, L., Hlavac, V., Kim, T.-K., & Malassiotis, S. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2016.2602376 · Cited by 122 · see citing works
Learning grasp affordance densities
Detry, R., Kraft, D., Kroemer, O., Bodenhagen, L., Peters, J., Krüger, N., & Piater, J. (2011) · Paladyn Journal of Behavioral Robotics · doi:10.2478/s13230-011-0012-x · Cited by 79 · see citing works
Towards learning-based planning: The nuPlan benchmark for real-world autonomous driving
Karnchanachari, N., Geromichalos, D., Tan, K. S., Li, N., Eriksen, C., Yaghoubi, S., Mehdipour, N., Bernasconi, G., Fong, W. K., Guo, Y., et al. (2024) · 2024 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra57147.2024.10610077 · Cited by 46 · see citing works
“By carefully designing a cost function, the optimization aims to generate the optimal trajectory that minimizes the cost function in the corresponding search space (e.g., A* search [27], [28], sampling-based methods [32], [33], dynamic programming [30]).”
BackgroundHonerkamp, D., Welschehold, T., & Valada, A. (2023) · IEEE Transactions on Robotics · doi:10.1109/tro.2023.3284346 · Cited by 30 · see citing works
Li, C., Zhang, R., Wong, J., Gokmen, C., Srivastava, S., Martín-Martín, R., Wang, C., Levine, G., Ai, W., Martinez, B., et al. (2024) · arXiv · doi:10.48550/arxiv.2403.09227 · Cited by 6 · see citing works
“The action primitives are implemented with the same sampling-based motion planning algorithm as in simulation [62, 49] with additional tuning.”
MethodLearning Environment-Aware Affordance for 3D Articulated Object Manipulation under Occlusions
Wu, R., Cheng, K., Shen, Y., Ning, C., Zhan, G., & Dong, H. (2023) · arXiv · doi:10.48550/arxiv.2309.07510 · Cited by 11 · see citing works
“Moreover, sampling-based motion planning [19, 35], a kind of commonly used approach for planning and manipulation, also faces performance degradation with increasing occluders [38] as the probability of valid sampling rapidly diminishes.”
Planetary Terrain Datasets and Benchmarks for Rover Path Planning
Chancán, M., Banerjee, A., & Nikolakopoulos, G. (2025) · arXiv · doi:10.48550/arxiv.2512.21438
“Sampling-based planners, such as Rapidly-exploring Random Trees (RRT) (LaValle, 1998) and its variants RRT Connect (Kuffner and LaValle, 2000) and Dynamic RRT (Ferguson et al., 2006), randomly sample the map or configuration space C to build a tree of feasible paths.”
- Authors
- Kuffner, J. J., & LaValle, S. M.
- Affiliations
- Stanford University (US)
- Iowa State University (US)
- ORCID
- LaValle, S.M.
- Venue
- Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065)
- Publisher
- IEEE
- Published
- 2000
- Pages
- 995-1001 vol.2
- ISSN
- 1050-4729 (ISSN-L)
- OpenAlex
- W2141664020
- Cited by
- 3,555
- References
- 2
- Citations by year
- 2026: 145 · 2025: 323 · 2024: 291 · 2023: 285 · 2022: 248 · 2021: 319 · 2020: 219 · 2019: 200 · 2018: 176 · 2017: 153 · 2016: 140 · 2015: 131 · 2014: 108 · 2013: 113 · 2012: 105
- FWCI
- 23.02
- Type
- conference paper
- Language
- en
- Open access
- closed
- Licence
- Locations
- Proceedings - IEEE International Conference on Robotics and Automation/Proceedings (publishedVersion)
- Funders
- National Science Foundation
- Iowa State University
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Robotic Path Planning Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Keywords
- RRT-Connect, rapidly-exploring random tree, randomized motion planning, high-dimensional configuration space, greedy algorithm
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
