Robots that move through the world face a deceptively simple question: how do I get from here to there without hitting anything, and how do I do it as efficiently as possible? For high-dimensional systems such as multi-jointed robotic arms, dual-arm manipulators, or humanoid robots, the number of possible configurations grows so quickly that exhaustively searching the space is computationally impossible. Sampling-based motion planners have become the workhorse solution, probing the space with random samples and stitching collision-free segments together into feasible paths. Yet a persistent frustration has dogged these methods: once a planner finds a workable path, it can take an enormous amount of additional computation to refine that path toward the optimal one. A new study published in Autonomous Robots by Phone Thiha Kyaw and colleagues at the University of Toronto Institute for Aerospace Studies, working with collaborators at Ton Duc Thang University and the Singapore University of Technology and Design, offers a sharper answer to this refinement problem through a concept they call the greedy informed set.

To appreciate why the contribution matters, it helps to understand how modern optimal planners work. Algorithms such as Rapidly-exploring Random Tree star, or RRT*, introduced by Karaman and Frazzoli in 2011, guarantee asymptotic optimality, meaning that given enough samples the solution converges to the best possible path. The catch lies in the rate of that convergence. Early samples tend to produce long, winding, inefficient routes, and the planner must then sift through an astronomically large configuration space to find better alternatives. Informed sampling techniques addressed this by restricting new samples to a subset of the state space that could conceivably contain an improvement. The most famous example, Informed RRT*, draws samples from an ellipsoidal region whose size shrinks as the current best path cost decreases. Any point outside the ellipse, by the triangle inequality, cannot lie on a path shorter than the current solution, so sampling there is wasted effort.

The Toronto-led team, however, identified a subtle weakness in this widely adopted strategy. The informed subset is only as tight as the current solution path allows. When that path contains redundant detours, unnecessary loops, or tortuous segments, the ellipsoidal informed set remains bloated, and the planner continues to scatter samples across regions that are almost certainly useless. In other words, the quality of the guidance depends on the quality of the incumbent solution, and early solutions are typically poor. The researchers’ prior work proposed the greedy informed set as a remedy: instead of defining the sampling region by the total cost of the current path, it uses the maximum heuristic cost along that path, producing a substantially smaller region that focuses samples where improvements are genuinely plausible.

In the new article, the authors go well beyond the initial proposal by formally characterizing how the greedy informed set behaves within RRT*-like planners. They analyze what happens to exploration when sampling is biased so aggressively, a crucial theoretical question because over-constraining the search risks excluding regions that a future, better solution might need to traverse. The analysis demonstrates that greedy sampling can be integrated without sacrificing the properties that make RRT* attractive: the planner still finds an initial solution rapidly and still converges asymptotically to optimal paths. This combination of aggressive focus and retained completeness guarantees is the theoretical heart of the paper, and it distinguishes the approach from heuristic shortcuts that speed things up at the cost of optimality assurances.

Building on this foundation, the team presents Greedy RRT*, abbreviated G-RRT*, a bi-directional anytime variant of RRT* that exploits the greedy informed set in practice. The bi-directional design means the planner grows search trees simultaneously from the start and goal configurations, meeting in the middle, a strategy long known to accelerate the discovery of initial solutions. The anytime property means the planner can be stopped at any moment and return the best path found so far, then continue improving that path if given more time. By combining these established design principles with greedy informed sampling, G-RRT* concentrates its computational budget on the most promising pockets of the search space, tightening the sampling region aggressively as soon as any solution exists.

The empirical evaluation is notably broad. The researchers tested G-RRT* on abstract planning benchmarks, which isolate algorithmic behavior from the idiosyncrasies of any particular robot, and on manipulation tasks drawn from the MotionBenchMaker dataset, a tool developed by Chamzas and colleagues to generate standardized, reproducible motion planning benchmarks for robotic manipulation. They also tackled a dual-arm Barrett WAM problem, a genuinely high-dimensional scenario in which two articulated arms must coordinate their movements without colliding with each other or the environment. Across these domains, G-RRT* found initial solutions quickly and converged to optimal paths faster than state-of-the-art sampling-based planners, including informed variants that rely on the conventional ellipsoidal subset.

The practical implications extend across robotics. Manipulation planning for industrial arms, warehouse robots, surgical systems, and space robotics all involve configuration spaces with a dozen or more degrees of freedom, exactly the regime where sampling-based planners dominate and where convergence speed determines whether a robot can plan in real time or must pause awkwardly while computing. Faster convergence to high-quality paths translates directly into robots that respond more quickly, consume less energy executing shorter routes, and can replan on the fly when the environment changes. The authors note that implementations of G-RRT* are publicly available both within the Open Motion Planning Library, the field’s standard open-source planning framework maintained through OMPL, and in VAMP, a vector-accelerated motion planning platform, lowering the barrier for other research groups to adopt and extend the technique.

The study also situates itself within a rich lineage of sampling heuristics. Researchers have long experimented with biasing samples toward free space, toward narrow passages, or along potential fields, and variants such as RRT*-Smart, Quick-RRT*, and F-RRT* have each proposed tricks for accelerating convergence, often by shortcutting or smoothing the incumbent path. Batch-oriented planners such as Batch Informed Trees and bidirectional asymmetric search methods like Adaptively Informed Trees represent a parallel line of work that fuses sampling with graph-search ideas. The greedy informed set contributes a distinct and principled mechanism to this ecosystem: rather than post-processing paths or restructuring the search, it redefines the geometry of the sampling region itself, using a heuristic bound that remains valid even when the current path is far from optimal. Recent work on vectorized planning, exemplified by the VAMP system from Thomason, Kingston, and Kavraki, has shown that raw computational throughput can be pushed to remarkable heights, and greedy sampling composes naturally with such speedups because it reduces the number of wasted samples rather than the speed of each sample.

Simulations for the study were performed in an Ubuntu 20.04 Docker container on an Intel Core i7-10875H processor with 40 gigabytes of memory, with all planners implemented in C++, and path simplification was evaluated only in separate post-processing experiments so that it would not contaminate the convergence measurements. This methodological care matters in a field where benchmarking practices have historically varied widely, and the authors leveraged the Planner Developer Tools framework, designed for reproducible experiments and statistical analysis of motion planners. The paper’s theoretical proofs, which the authors note benefited from assistance with the formal arguments, establish the asymptotic guarantees that practitioners need before trusting a new sampling bias in safety-relevant applications.

What makes this work resonate beyond its immediate subfield is the way it reframes a familiar trade-off. Exploration versus exploitation is a tension that recurs throughout artificial intelligence, from reinforcement learning to combinatorial search, and motion planning offers an unusually concrete instance of it. The greedy informed set shows that, with the right heuristic characterization, a planner can lean hard toward exploitation, sampling only where improvement is provably possible, without forfeiting the exploratory completeness that guarantees eventual optimality. As robots proliferate in homes, hospitals, factories, and hazardous environments, the demand for planners that deliver near-optimal paths in milliseconds rather than seconds will only intensify. Greedy RRT* offers a mathematically grounded step toward that goal, and its availability in open-source planning libraries means the broader robotics community can put the greedy principle to work immediately.

Subject of Research: Greedy informed sampling for asymptotically optimal sampling-based robot motion planning in high-dimensional state spaces

Article Title: Greedy heuristics for sampling-based motion planning in high-dimensional state spaces

Article References: Kyaw, P. T., Le, A. V., Mohan, R. E., & Kelly, J. (2026). Greedy heuristics for sampling-based motion planning in high-dimensional state spaces. Autonomous Robots, 50(4), Article 44. https://doi.org/10.1007/s10514-026-10269-0

Image Credits: AI Generated

DOI: 10.1007/s10514-026-10269-0

Keywords: sampling-based motion planning, RRT*, greedy heuristics, informed sampling, robot motion planning, high-dimensional state spaces, asymptotic optimality, bidirectional search, robotic manipulation, MotionBenchMaker, OMPL, path optimization