Greedy Heuristics for Sampling-Based Motion Planning in High-Dimensional State Spaces

Jul 16, 2026

Upload by Jiven

Informed sampling speeds up sampling-based motion planning by biasing random samples toward state-space regions that are more likely to produce high-quality solutions. When the current path contains redundant, tortuous segments, the informed subset can remain overly large and slow convergence. This work analyzes greedy informed set behavior in RRT*-like planners, studying how greedy sampling influences exploration and asymptotic optimality. It introduces Greedy RRT* (G-RRT*), a bidirectional anytime variant that rapidly finds initial solutions and converges to optimal paths, outperforming leading methods across benchmarks and manipulation tasks.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages18

Reading Time45 min

Abstract

Introduction

Path planning in high-dimensional state spaces

Sampling-based planners and informed sets

Greedy informed sets and their analysis

Greedy RRT* (G-RRT*)

Bidirectional anytime variant

Experiments and results

arXiv :2405 .03411v4 [ cs .RO] 10 Jul 2026 Greedy Heuristics for Sampling-Based Motion Planning in High-Dimensional State Spaces Phone Thiha Kyaw 1*, Anh Vu Le 2 , Rajesh Elara Mohan 3 , Jonathan Kelly 1 1 Space & Terrestrial Autonomous Robotic Systems (STARS) Laboratory, University of Toronto Institute for Aerospace Studies, 4925 Dufferin Sreet, Toronto, M3H 5T6, Ontario, Canada. 2 Advanced Intelligent Technology Research Group, Faculty of Electrical and Electronics Engineering, Ton Duc Thang University, Ho Chi Minh City, 700000, Vietnam. 3 ROAR Lab, Engineering Product Development, Singapore University of Technology and Design, Singapore, 487372, Singapore. *Corresponding author(s). E-mail(s): [phone.thiha@robotics.utias.utoronto.ca](phone.thiha@robotics.utias.utoronto.ca) ; Contributing authors: [leanhvu@tdtu.edu.vn](leanhvu@tdtu.edu.vn) ; [rajeshelara@sutd.edu.sg](rajeshelara@sutd.edu.sg) ; [jonathan.kelly@robotics.utias.utoronto.ca](jonathan.kelly@robotics.utias.utoronto.ca) ; Abstract Informed sampling techniques accelerate the convergence of sampling-based motion planners by biasing sampling toward regions of the state space that are most likely to yield better solutions. However, when the current solution path contains redundant or tortuous segments, the resulting informed subset may remain unnecessarily large, slowing convergence. Our prior work addressed this issue by introducing the greedy informed set, which reduces the sampling region based on the maximum heuristic cost along the current solution path. In this article, we formally characterize the behavior of the greedy informed set within Rapidly-exploring Random Tree (RRT*)-like planners and analyze how greedy sampling affects exploration and asymptotic optimality. We then present Greedy RRT* (G-RRT*), a bi-directional anytime variant of RRT* that leverages the greedy informed set to focus sampling in the most promising regions of the search space. Experiments on abstract planning benchmarks, manipulation tasks from the MotionBenchMaker dataset, and a dual-arm Barrett WAM problem demonstrate that G-RRT* rapidly finds initial solutions and converges asymptotically to optimal paths, outperforming state-of-the-art sampling-based planners. Keywords: Sampling-based motion planning, optimal path planning, informed sampling, bidirectional search, greedy heuristics, high-dimensional planning 1 Introduction Path planning is the problem of finding a collisionfree path from an initial state to a goal state while also considering specific optimization objectives, such as minimizing path length or energy use, for example (LaValle 2006) . Many planning algorithms exist, including graph search, artificial potential fields, and sampling-based methods (Elbanhawi and Simic 2014) . However, it remains challenging to find collision-free, optimal paths, especially in high-dimensional state spaces; the general path planning problem is known to be PSPACE-hard (Reif 1979) . Sampling-based planners, such as the probabilistic roadmap (Kavraki et al. 1996, PRM) and rapidlyexploring random tree (LaValle and Kuffner Jr 2001, RRT) algorithms, tackle the complexity of highdimensional path planning by sacrificing completeness for efficiency, providing only probabilistic guarantees. The asymptotically optimal variants PRM* and RRT* (Karaman and Frazzoli 2011) improve solution quality over time but remain computationally expensive due to their reliance on random sampling. A substantial portion of the computational effort is often wasted exploring irrelevant portions of the state space. To improve planning performance, it is crucial to focus sampling on promising regions of the problem domain. Existing direct informed sampling methods (Gammell et al. 2014, 2018) mitigate inefficiency by defining bounded, hyperellipsoidal sampling regions, called informed sets, based on the cost of the current solution. While this significantly reduces the size of the search space

FAQs

What problem does informed sampling address in motion planning?

Informed sampling accelerates convergence by biasing samples toward state-space regions most likely to yield better solutions. It reduces wasted exploration of irrelevant regions once a solution cost is known.

Why can standard informed sets slow convergence for tortuous paths?

Redundant, tortuous segments increase the solution cost, which enlarges the informed sampling region. A larger region makes it harder to focus on states that could belong to a better solution.

What is Greedy RRT* (G-RRT*) and how does it improve RRT*?

G-RRT* introduces greedy informed sets and uses them within a bidirectional anytime variant of RRT*. It concentrates sampling in more promising regions, rapidly finds initial solutions, and converges asymptotically to optimal paths.

Jul 16, 2026

Upload by Jiven