Informed Sampling for Accelerated Motion Planning

30 concepts20 papers1 proposal

Sampling-based motion planners, such as Rapidly-exploring Random Trees (RRT) and RRT*, have revolutionized robotics by making high-dimensional path planning computationally feasible. Traditionally, these algorithms rely on uniform random sampling across the configuration space. While uniform sampling guarantees that the planner will eventually explore every corner of the environment, it is highly inefficient in complex, non-uniform cost landscapes.

In environments with narrow passages, complex obstacle configurations, or non-geometric cost constraints (such as energy consumption, human comfort, or information density), uniform sampling wastes immense computational effort exploring regions that cannot possibly contribute to an optimal solution.

To overcome this bottleneck, a powerful paradigm has emerged: informed sampling. Instead of treating the configuration space as a blank canvas, informed sampling strategies dynamically warp, filter, or restrict the sampling distribution based on environmental costs, heuristics, or prior solutions. By focusing computational budget where it matters most, these methods drastically accelerate convergence to optimal paths without sacrificing theoretical guarantees.

Filtering the Space via Cost-Biased Rejection and Transition Tests

One of the most intuitive ways to move away from uniform sampling is to use an underlying cost map to filter out undesirable samples before they are added to the tree.

Suh, in developing Cost-Aware RRT (CA-RRT), demonstrates how a rejection sampling strategy biased by a continuous cost map can prioritize target points in low-cost regions. Instead of blindly accepting every random sample, the algorithm evaluates the sample against an environmental cost map (e.g., temperature or signal strength). High-cost samples are rejected with higher probability, naturally steering tree expansion through safer, more efficient corridors.

Uniform Sampling:   [ .  .  .  .  .  .  .  . ]  --> Explores everywhere equally
Cost-Biased:        [ .     .  .  .     .   ]  --> Concentrates samples in low-cost valleys

Rather than filtering samples globally, we can also filter them during the tree-expansion phase by evaluating the local transition between a parent node and a new candidate configuration. Alami et al. utilize a transition-based sampling algorithm within a human-aware costmap, probabilistically accepting or rejecting new configurations based on their relative cost increase.

This concept is formalized mathematically by Devaurs et al. and Simeon through the integration of a transition test into the RRT framework (T-RRT). This test acts as a thermodynamic filter: moves to lower-cost regions are always accepted, while moves to higher-cost regions are accepted with a probability governed by a temperature parameter. As Simeon explains, this mechanism forces the algorithm to generate sparser graphs focused almost exclusively on low-cost regions, preventing the planner from wasting resources on high-cost plateaus.

Geometrically Bounding the Search Space with Informed Sets

While cost maps help steer exploration, a different problem arises when an initial, suboptimal path has already been found: how do we efficiently refine it? Sampling uniformly across the entire state space to find a minor shortcut is incredibly wasteful.

If we know the cost of our current best path ($c_{\text{best}}$), we can mathematically define an informed set—a subregion of the state space containing only the configurations that could possibly yield a shorter path. For geometric distance metrics, this informed set forms a perfect hyper-ellipsoid where the start and goal states act as the foci.

          , - - - - - - - - ,
      , '                     ' ,
    ,             _.._            ,
   :   Start ====(____)====> Goal  :  <-- Ellipsoidal Informed Set
    ,                             ,        (Only sample inside this boundary)
      ,                         ,
        ' - - - - - - - - - - '

Belter leverages this mechanism in the Informed Guided RRT*-Connect (IGRSC) algorithm. By using a pre-computed feasible path to define an ellipsoidal sampling region, the search is instantly narrowed from the entire environment to a tight corridor surrounding the initial solution.

This concept extends gracefully to complex dynamical systems. Schwegel et al. apply an informed RRT* variant to differentially flat systems, such as 3D gantry cranes, restricting random sampling to a state-space informed set that accounts for both system dynamics and current path costs. As $c_{\text{best}}$ decreases during optimization, the ellipsoid shrinks, continuously focusing the sampling density around the global optimum.

Exploitation and Heuristic Biases for Complex Objectives

Informed sampling is not limited to simple geometric bounds; it can be driven by complex optimization heuristics, mathematical bounds, or machine learning models.

Bound-Based and Exploitative Sampling

When navigating high-dimensional spaces with multiple goals, calculating exact ellipsoids becomes intractable. Chour et al. introduce Informed Steiner Trees (IST*), which dynamically adjust sampling probabilities based on lower and upper bounds of edge costs between multiple target goals. Instead of uniform exploration, the algorithm prioritizes regions that are mathematically capable of improving the overall spanning tree.

Similarly, Zheng introduces Informed Batch Belief Trees (IBBT), incorporating samples in discrete batches guided by a cost-to-go heuristic to focus on high-potential regions before expanding into less promising sections of the state space. To accelerate convergence even further, Hutchinson proposes Locally Exploitative Sampling (LES), a strategy that actively biases samples toward refining existing paths by solving local optimization problems to improve the cost-to-come, favoring local exploitation over blind global exploration.

Information-Driven Exploration

For robotic information gathering (e.g., mapping or target tracking), the objective is to maximize information gain rather than minimize distance. As noted by Sukhatme et al., uniform sampling fails here because it allocates equal computational effort to completely uninformative regions.

To solve this, Kantaros et al. inject density biases—such as favoring exploration frontiers or predicted target locations—directly into the sampling process. In a similar vein, Moon et al. develop TIGRIS, which weights sampling probabilities based on predicted information rewards. By focusing samples on high-potential information-gain regions, the planner avoids wasting time in data-barren zones.

Learned and Adaptive Biases

In complex environments, traditional heuristics can fail to capture the underlying structure of the space. Modern approaches address this by learning the sampling bias or adapting it online:

  • Learned Critical Regions: Molina et al. introduce "Learn and Link," using Convolutional Neural Networks (CNNs) to predict narrow passages and bottlenecks from environmental images, seeding the planner directly with high-value samples in these critical zones.
  • Adaptive Obstacle Prediction: Fu utilizes an adaptive sampling strategy that dynamically shifts its focus based on real-time obstacle predictions, concentrating samples in low-risk areas to optimize robotic arm trajectories.
  • Operational Cost Integration: Rodrigues modifies RRT* edge weights to reflect the minimum Direct Operating Cost (DOC) for electric aircraft, integrating optimal cruise speed calculations directly into the trajectory search space.

Why Informed Sampling Preserves Optimality

A common concern when biasing a random planner is the loss of theoretical guarantees. If we stop sampling uniformly, do we lose the ability to find a solution (probabilistic completeness) or find the absolute best solution (asymptotic optimality)?

The reason informed sampling works without sacrificing these guarantees lies in how the sampling distributions are constructed. Algorithms like those proposed by Kantaros et al. and Molina et al. ensure that while the sampling density is heavily biased toward promising regions, the probability of sampling any valid region in the remaining space remains strictly greater than zero.

For methods that completely restrict sampling to an informed set (like the ellipsoids in Belter), optimality is preserved because the excluded space is mathematically proven to contain no solutions better than the current path. By discarding only the provably suboptimal search space, informed sampling compresses the problem size, transforming a needle-in-a-haystack search into a focused, rapid optimization process.

Key Foundational Work

A Cost-Aware RRT Planning Algorithm (2012) — contributed 2 concept elements to this direction.
Planning human-aware motions using a sampling-based costmap planner (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_informed_sampling_bf281955,
  title = {informed sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/informed-sampling/rdr_bf281955200744cc8eaf727aed956425},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_informed_sampling_bf281955_v1,
  title = {informed sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/informed-sampling/rdr_bf281955200744cc8eaf727aed956425/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake