RRT* Motion Planning in 2D: Informed Sampling |…

What is RRT* Motion Planning?

RRT* (Rapidly-exploring Random Tree*) is a probabilistic algorithm designed to find feasible paths through complex environments. It builds a tree of possible paths, starting from an initial point and extending towards random points in the configuration space until it reaches a goal or exhausts its iterations.

In RRT*, each node represents a state (position) in the environment, and edges represent feasible transitions between states. The algorithm ensures that the path found is optimal with high probability.

How Does Informed Sampling Work?

Informed Sampling enhances RRT* by guiding new samples towards areas of interest based on the current best known path to the goal. This technique restricts further sampling within a cost-optimized ellipse, which is continually updated as the algorithm progresses.

By focusing on regions with lower costs and higher likelihoods of leading to the goal, Informed Sampling significantly reduces the number of unnecessary expansions and speeds up convergence.

live demo · related simulation● LIVE

Why Does RRT* with Informed Sampling Matter?

RRT* with Informed Sampling is crucial in robotics and autonomous navigation because it can efficiently find feasible paths through environments filled with obstacles. This capability is essential for applications ranging from drone flight planning to robotic surgery.

The algorithm’s ability to handle high-dimensional spaces makes it particularly valuable in complex real-world scenarios where traditional methods might fail.

Real-World Applications of RRT* Motion Planning

RRT* is widely used in autonomous vehicles for path planning, enabling safe and efficient navigation through urban environments. It also finds applications in robotics, where it helps robots avoid obstacles while performing tasks.

In medical robotics, such as robotic arms during surgeries, RRT* ensures precise movements by finding optimal paths around anatomical structures.

Frequently asked questions

What is the difference between RRT and RRT*?

RRT (Rapidly-exploring Random Tree) builds a tree of possible paths without reusing nodes, while RRT* optimizes these paths to ensure they are more likely to be optimal. RRT* also includes mechanisms for pruning less promising branches.

How does Informed Sampling improve the performance of RRT*?

Informed Sampling restricts future samples to areas with lower costs and higher likelihoods of leading to the goal, reducing unnecessary expansions and speeding up convergence. This makes the algorithm more efficient in complex environments.

Can RRT* be used for 3D environments?

Yes, RRT* can be extended to handle 3D environments by considering additional dimensions in the configuration space. However, this increases computational complexity and may require more advanced techniques to manage higher-dimensional spaces efficiently.

What are some limitations of RRT* motion planning?

RRT* can be sensitive to initial conditions and goal bias settings. Poorly chosen parameters or a large number of obstacles can lead to suboptimal paths or failure to find any path at all. Additionally, the algorithm’s performance can degrade in very high-dimensional spaces.

Try it live

Everything above runs in your browser — open RRT* Motion Planning in 2D — Informed Sampling and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open RRT* Motion Planning in 2D — Informed Sampling simulation