Revisiting Replanning from Scratch: Real-Time Incremental Planning with Fast Almost-Surely Asymptotically Optimal Planners

AI summary

Overview

Research area: Robotics, specifically motion planning — incremental/replanning in unknown or changing environments.

Technical level: Intermediate. The core idea is intuitive, but the paper assumes familiarity with sampling-based planners (RRT*, RRT-Connect, EIT*), asymptotic optimality, and concepts such as homotopy classes and solution-tree rewiring.

Scope: The paper argues, and tests in simulation and on hardware, that running a fast almost-surely asymptotically optimal (ASAO) planner from scratch at every replanning step beats plan-reuse methods that update existing search trees.

What This Paper Is About

When a robot operates among unknown or moving obstacles, it must repeatedly replan as new obstacle information arrives. The standard assumption in the field is that fast reactive replanning requires reusing information from previous plans (as in D*, LPA*, and RRT^X). This paper challenges that assumption, showing that simply solving a brand-new planning problem each time information changes can be both faster and higher quality, provided the planner used is a fast ASAO planner such as EIT* or AORRTC.

Key Contributions

1. Revisits and challenges the long-held assumption that reactive replanning requires plan reuse. The paper reframes the incremental planning problem as a series of independent planning problems solved by fast ASAO planners.

2. Demonstrates that independent EIT outperforms purpose-built incremental planners.* In simulated experiments, EIT* found shorter median global solution paths than RRT-Connect (with and without smoothing), RRT*, and RRT^X, and had the highest success rate on every tested world and planning budget.

3. Provides best-case benchmarking for a plan-reuse baseline. RRT^X was given an advantage by ignoring the computational cost of detecting invalidated edges, and a truncated version ("RRT^X (initial)") that stops after finding an initial solution was also tested — both still failed to solve more than 90% of trials.

4. Validates the approach on real hardware. A VAMP implementation of AORRTC replanned around moving obstacles on a seven degree-of-freedom Franka Research 3 arm using a collision-affording point tree (CAPT) obstacle map, without stopping the arm and with no prior knowledge of obstacle locations.

Main Findings

• Independent ASAO planning is competitive without plan reuse: The paper shows the incremental planning problem can be solved by independently replanning from the current state each time obstacle information changes, with no explicit reuse of previous search structures.

• EIT won on path quality:* EIT* had the shortest median global path length on all problems. On the representative Random Rectangles world it found a median path of 0.718 (95% nonparametric interval [0.717, 0.719]), versus 4.78 for RRT-Connect and 3.14 for smoothed RRT-Connect; RRT*, RRT^X, and RRT^X (initial) are listed as infinite (no successful trials).

• EIT won on success rate:* EIT* achieved 100% success on the Wall Gap and Double Enclosure worlds and 100% on the representative Random Rectangles world, versus 88% for RRT-Connect and 87% for smoothed RRT-Connect on Double Enclosure, and 0% for RRT* and both RRT^X variants on Double Enclosure. Across the 40 random worlds, total success was 98.9% for EIT*, 95.2% for RRT-Connect, 96.0% for smoothed RRT-Connect, 26.2% for RRT*, 8.13% for RRT^X, and 8.70% for RRT^X (initial).

• RRT^X struggled badly: The full RRT^X failed to find a complete global solution within the incremental planning budget on more than 90% of trials across all simulated worlds, attributed to the cost of rewiring potentially very large solution trees when many edges are invalidated. Limiting it to finding only an initial solution also failed on more than 90% of trials.

• RRT was too slow to find initial solutions:* Although its ASAO properties produced consistent intermediate paths and shorter median global paths than RRT-Connect and RRT^X when it succeeded, RRT* failed more than half the time on the Double Enclosure problems and all sets of Random Rectangles due to slow initial solution times (e.g., 79% success on Wall Gap, 9% on the representative Random Rectangles world).

• Replanning as fast as 50 ms is feasible: EIT* successfully replanned as quickly as 50 ms in simulated experiments, and was the only planner that solved more than 50% of all trials on all of the worlds in the 50 ms experiments — which is why only success rates are reported for that budget.

• Non-optimal planners were inconsistent rather than slow: RRT-Connect returned quickly (e.g., median 0.070 s global solution time on Wall Gap and 1.14 s on Double Enclosure) and reached 100% success on Wall Gap, but its lack of solution-quality guarantees produced longer global paths and more queries (23 queries on the representative Random Rectangles world versus 7 for EIT*).

• Smoothing helped but did not close the gap: Smoothed RRT-Connect improved on unsmoothed RRT-Connect in path length and query count, but still had a longer median path length and more queries than EIT* on all problems.

• Hardware demonstration: AORRTC navigated the Franka Research 3 arm around each tested moving-obstacle configuration in real time without modelling obstacle motion, using the VAMP implementation and a CAPT map.

Methodology in Plain English

The researchers define the setting as a robot that only senses obstacles within a limited radius (a maximum sensor range, r_s) of its current position, where sensed obstacles are assumed stationary (a retrospective time horizon τ of infinity in the simulation). The robot plans a path through the free space defined by everything it has sensed so far, follows the path until it reaches the edge of the sensed area, senses again, and repeats until it reaches the goal.

Instead of repairing a previous plan, the robot throws its plan away and calls the planner fresh at each of these iterations. The key requirement is that the planner finds a good enough solution within the time budget, because high-quality intermediate paths prevent the robot from oscillating between homotopy classes and producing an unnecessarily long global path.

To test this, the authors built an incremental simulation on top of the Planner Development Tools (PDT) and used publicly available OMPL implementations. They compared EIT* against RRT-Connect (with and without smoothing), RRT*, and RRT^X across three simulated world types: Random Rectangles (20 randomly placed rectangles with side lengths uniformly distributed between 0.1 and 0.2, start at (-0.1, -0.1), goal at (0.4, 0.4)), Wall Gap (two rectangles with a narrow gap at the world's center), and Double Enclosure (two rectangular enclosures containing the start and goal, so the initially visible route is revealed to be blocked). All worlds are 2D path-length minimization problems in X = [-1, 1]², with sensor ranges of 0.1 (Random Rectangles), 0.075 (Wall Gap), and 0.05 (Double Enclosure).

The experiment protocol: 100 runs per planner on Wall Gap, Double Enclosure, and 40 different Random Rectangles problems at a 0.1 s budget; 100 more runs at 0.05 s on Wall Gap, Double Enclosure, and a representative Random Rectangles world; and 10 runs each at 0.01 s, 0.05 s, and 0.1 s across 100 different Random Rectangles worlds per budget. Metrics were per-query success rate, global solution time, global path length, and number of queries, with Clopper-Pearson 95% confidence intervals for success rates and nonparametric 95% intervals for medians. To give RRT^X its best case, the cost of detecting which edges new obstacles invalidated was ignored. Finally, the same independent-replanning strategy was applied on a real Franka Research 3 arm with AORRTC.

Why This Matters

Impact on research: The paper pushes back on a foundational assumption in the incremental planning literature — that reacting to change requires updating existing plans. It shows that the field's reliance on efficient change detection is a liability: D*, LPA*, L-GLS, and RRT^X all assume they know which edges have changed and largely ignore the cost of detecting those changes. The results also unify two previously separate lines of work by positioning incremental planning as a sequence of optimal planning problems, which means progress in single-query ASAO planning transfers directly to replanning.

Real-world applications:

• Robot arms sharing a workspace with moving obstacles, as demonstrated with the Franka Research 3 replanning without stopping the arm.
• Mobile robots with limited sensor range, where each new sensed region reveals obstacles the robot could not previously see.
• Vehicles or robots facing dynamic obstacles whose motion is unknown or unmodelled, where predictive planners would need a strong prior.
• High-dimensional manipulation problems, where the CAPT-based VAMP/AORRTC demonstration suggests the approach scales beyond 2D simulation.

Industry relevance: The approach reduces engineering burden. It requires no prior obstacle model (no maximum velocity, no trajectory probabilities), and the only tuning parameter is to use the largest planning budget that can be afforded. It also avoids the tuning or sophisticated density-control machinery that plan-reuse systems need to keep solution trees from becoming dense over long horizons — a concern the paper explicitly raises for long-horizon problems like the Franka arm experiment.

Future Directions

• Applying the independent ASAO approach on robots that also have obstacle predictions, to find better solutions in environments with dynamic obstacles.
• Extending the approach to robots with kinodynamic or other constraints beyond the geometric path-length problems tested here.
• Determining how the independent replanning strategy behaves when the sensor model is not "sensed obstacles are stationary" — the simulation assumed τ = ∞, so the effect of a finite retrospective time horizon is not reported.
• Addressing the paper's observation that none of the evaluated planners achieved 100% success on all problems, since some randomly generated worlds require passing through very narrow gaps; the authors state that increasing the planning budget would raise success rates on these difficult problems.

Target Audience

Robotics researchers and graduate students working on motion planning, especially those in incremental, dynamic, or real-time planning; practitioners implementing planners on robot arms or mobile platforms who need a simple, robust replanning strategy; and readers interested in the trade-off between information reuse and replanning from scratch in anytime algorithms.

Authors’ abstract

Robots operating in changing environments either predict obstacle changes and/or plan quickly enough to react to them. Predictive approaches require a strong prior about the position and motion of obstacles. Reactive approaches require no assumptions about their environment but must replan quickly and find high-quality paths to navigate effectively. Reactive approaches often reuse information between queries to reduce planning cost. These techniques are conceptually sound but updating dense planning graphs when information changes can be computationally prohibitive. It can also require significant effort to detect the changes in some applications. This paper revisits the long-held assumption that reactive replanning requires updating existing plans. It shows that the incremental planning problem can alternatively be solved more efficiently as a series of independent problems using fast almost-surely asymptotically optimal (ASAO) planning algorithms. These ASAO algorithms quickly find an initial solution and converge towards an optimal solution which allows them to find consistent global plans in the presence of changing obstacles without requiring explicit plan reuse. This is demonstrated with simulated experiments where Effort Informed Trees (EIT*) finds shorter median solution paths than the tested reactive planning algorithms and is further validated using Asymptotically Optimal RRT-Connect (AORRTC) on a real-world planning problem on a robot arm.