Generalizing Informed Sampling for Asymptotically-Optimal Sampling-based Kinodynamic Planning via Markov Chain Monte Carlo

Sep 4, 2026

Uploaded by Rowan

Asymptotically-optimal motion planners like RRT* increasingly approximate shortest paths after an initial solution is obtained, but their gains depend on focusing new samples on an informed region Xinf. In non-Euclidean state spaces with differential constraints, Xinf lacks an analytic sampling method and existing rejection-based techniques can become prohibitively slow in high dimensions. This work proposes a generalized approach that reformulates sampling in Xinf as uniform sampling over the sub-level set of an implicit non-convex function and applies Monte Carlo methods, accelerating convergence to high-quality solutions.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages8

Reading Time20 min

AccessFree to download

Introduction

Informed subset in sampling-based planning

Limitations of rejection sampling in high dimensions

Proposed approach

Reformulating sampling in Xinf

Monte Carlo and MCMC sampling stages

Algorithmic framework

Retraction to the informed set boundary

Uniform coverage via sampling chains

Generalizing Informed Sampling for Asymptotically-Optimal Sampling-based Kinodynamic Planning via Markov Chain Monte Carlo Daqing Yi􀀃1, Rohan Thakker􀀃2, Cole Gulino2 , Oren Salzman2 and Siddhartha Srinivasa 1 Abstract—Asymptotically-optimal motion planners such as RRT* have been shown to incrementally approximate the shortest path between start and goal states. Once an initial solution is found, their performance can be dramatically improved by restricting subsequent samples to regions of the state space that can potentially improve the current solution. When the motionplanning problem lies in a Euclidean space, this region Xinf , called the informed set, can be sampled directly. However, when planning with differential constraints in non-Euclidean state spaces, no analytic solutions exists to sampling Xinf directly. State-of-the-art approaches to sampling Xinf in such domains such as Hierarchical Rejection Sampling (HRS) may still be slow in high-dimensional state space. This may cause the planning algorithm to spend most of its time trying to produces samples in Xinf rather than explore it. In this paper, we suggest an alternative approach to produce samples in the informed set Xinf for a wide range of settings. Our main insight is torecast this problem as one of sampling uniformly within the sub-level-set of an implicit non-convex function. This recasting enables us to apply Monte Carlo sampling methods, used very effectively in the Machine Learning and Optimization communities, to solve our problem. We show for a wide range of scenarios that using our sampler can accelerate the convergence rate to high-quality solutions in high-dimensional problems. I. INTRODUCTION Sampling-based motion-planning algorithms [1] have proven to be an effective tool at solving motion-planning problems. They search through a continuous state space X by sampling random states and maintaining a discrete graph G called a roadmap. Vertices and edges in G correspond to collision-free states and paths, respectively. Roughly speaking, these algorithms iteratively sample new states. This is required to ensure that, as the number of samples tends to inﬁnity, (i) a solution will be found and that (ii) given some optimization criteria, the quality of the solution will progressively converge to the quality of the optimal solution. Initially, when a path has yet to be found, the samples are drawn from the entire state space X. However, once a path 􀀍 is produced, algorithms that seek high-quality paths can limit their sampling domain to a subset of X only containing states that may be used to produce higher-quality paths than 􀀍 . Following Gammell et al. [2], we call this subset the informed subset and denote it Xinf . In this work we 􀀃 Daqing Yi and Rohan Thakker contributed equally to this paper. 1Daqing Yi and Siddhartha Srinivasa are with Paul G. Allen School of Computer Science & Engineering, University of Washington. fdqyi, [siddh](siddhg@cs.washington.edu)[g](siddhg@cs.washington.edu)[@cs.washington.edu](siddhg@cs.washington.edu) 2Rohan Thakker, Cole Gulino and Oren Salzman are with Robotics Institute, Carnegie Mellon University. frthakker, cgulino, [osalzman](osalzmang @andrew.cmu.edu)[g](osalzmang @andrew.cmu.edu)[ @andrew.cmu.edu](osalzmang @andrew.cmu.edu) q Fig. 1: Algorithmic approach. Cost function is depicted using isocontours (darker shades reﬂect lower cost) while the boundary of the informed set is depicted in purple. The root-ﬁnding and MCMC algorithms are depicted in red and turquoise, respectively. x 0 lies on the boundary of Xinf address the problem of efﬁciently producing samples in Xinf for systems with arbitrary complex costs. For Euclidean spaces optimizing for path length, Xinf can be analytically expressed as a prolate hyperspheroid and can be sampled directly using a closed-form solution [2] . Indeed, directly sampling in Xinf has been shown to dramatically improve computation time when compared to sam

FAQs

What is the purpose of informed sampling in asymptotically-optimal planners?

After an initial path is found, informed sampling restricts subsequent samples to the region Xinf where new samples can improve the current solution, improving convergence toward optimal path quality.

Why is sampling the informed set difficult in non-Euclidean kinodynamic planning?

When differential constraints produce non-Euclidean state spaces, Xinf cannot be derived in closed form for direct sampling, so analytic sampling strategies are unavailable.

What alternative does the paper propose to generate samples in Xinf?

It recasts the task as uniform sampling within the sub-level set of an implicit non-convex function, enabling Monte Carlo sampling with an MCMC chain seeded by a retracted sample.

Sep 4, 2026

Uploaded by Rowan