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

This paper challenges the conventional assumption that reactive replanning requires updating existing plans by demonstrating that using fast almost-surely asymptotically optimal (ASAO) algorithms to solve a series of independent planning problems offers a more efficient and effective approach for navigating changing environments.

The Gist

Here is an explanation of the paper using simple language and creative analogies.

The Big Idea: "Start Over" vs. "Patch It Up"

Imagine you are driving a car through a city where traffic lights and construction zones appear and disappear randomly. You need to get from Point A to Point B as fast as possible.

For years, robot scientists believed that when a new obstacle appeared, the smartest thing to do was patch the old map. They thought, "I already have a great route; I just need to fix the tiny part that got blocked." This is like taking a complex, hand-drawn treasure map, finding a hole in the paper, and trying to tape a new piece over it without messing up the rest of the drawing.

This paper argues that this "patching" approach is actually a trap.

Instead, the authors suggest that the best strategy is to throw the old map away and draw a brand new one instantly. It sounds wasteful, but if you can draw a new map fast enough, it's actually better than trying to fix a messy old one.

The Problem with "Patching" (Incremental Planning)

Traditional "reactive" planners (the patchers) try to reuse information.

• The Analogy: Imagine you are walking through a forest. You have a path marked with blue ribbons. Suddenly, a tree falls across your path.
• The Patching Method: You stop, look at your blue ribbon map, find exactly where the tree fell, cut the ribbon, and try to weave a new path around the tree while keeping the rest of the ribbon intact.
• The Downside: If the forest is huge and the tree falls in a weird spot, you might spend so much time untangling the ribbons and checking if the old path is still safe that you never actually move forward. You get stuck "rewiring" your brain.

The New Solution: "The Fast Artist" (ASAO Planners)

The authors propose using a new type of planner called ASAO (Almost-Surely Asymptotically Optimal).

• The Analogy: Instead of patching the ribbon, imagine you are a super-fast artist. Every time a tree falls, you instantly throw away the old map and sketch a completely new, perfect route from your current spot to the goal.
• Why it works: Because these "artists" are so fast, they can draw a new, high-quality route in milliseconds. They don't waste time checking if the old path is still valid; they just assume the new path is the best one for right now.

The Key Players in the Study

The researchers tested several "drivers" (algorithms) to see who could navigate the changing city best:

1. The "Fixer-Upper" (RRTX): This is the traditional patcher. It tries to be smart by reusing old paths.
   • Result: It got bogged down. Every time an obstacle moved, it had to check thousands of connections in its old map to see what was broken. It spent more time fixing the map than driving.
2. The "Rush Driver" (RRT-Connect): This driver just wants to get there fast. It draws a quick path, even if it's a bit wobbly.
   • Result: It was fast, but because its paths were messy, it often took a detour that made the total trip much longer. It kept changing its mind (switching "homotopy classes," or taking different loops around the same hill).
3. The "Master Artist" (EIT):* This is the new champion. It is an ASAO planner.
   • Result: It found the perfect balance. It drew a new map every time an obstacle appeared, but it did it so quickly and so well that the total trip was shorter than anyone else's. It didn't get stuck fixing old maps, and it didn't take messy detours.

The Real-World Test: The Robot Arm

To prove this wasn't just a computer game, they tested it on a real Franka Research 3 robot arm (a mechanical arm used in factories).

• The Setup: They moved obstacles around the arm while it was trying to pick something up.
• The Outcome: The robot arm used the "Master Artist" (EIT*) approach. Every time an obstacle moved, the arm instantly recalculated a brand new path from scratch. It moved smoothly and avoided collisions without stopping, proving that "starting over" is faster and safer than "patching up" in the real world.

The Takeaway

The paper flips a long-held belief in robotics on its head.

• Old Belief: "Don't throw away your work; fix it."
• New Discovery: "If you are fast enough, throwing it away and starting fresh is actually the most efficient way to solve the problem."

By using these super-fast planners, robots can react to a chaotic, changing world by constantly reinventing their path, ensuring they always take the shortest, safest route without getting stuck in the past.

Technical Summary

Here is a detailed technical summary of the paper "Revisiting Replanning from Scratch: Real-Time Incremental Planning with Fast Almost-Surely Asymptotically Optimal Planners."

1. Problem Statement

Robots operating in dynamic environments must navigate around obstacles that may change position or appear unexpectedly. Traditional approaches to this incremental planning problem generally fall into two categories:

• Predictive Approaches: Rely on priors about obstacle motion (e.g., velocity, trajectories). These fail when predictions are inaccurate or data is scarce.
• Reactive Approaches: Do not assume obstacle motion but must replan quickly. The standard paradigm for reactive planning is Plan Reuse (e.g., D*, LPA*, RRTX). These algorithms attempt to update an existing search graph by propagating changes caused by new obstacle information.

The Core Challenge:
While plan-reuse algorithms offer theoretical guarantees on optimality, they suffer from significant computational bottlenecks in dynamic settings:

1. Detection Overhead: Identifying exactly which edges in a dense search graph are invalidated by new obstacles can be computationally prohibitive.
2. Rewiring Cost: Updating a dense tree (rewiring) to maintain optimality after a change is expensive, often making the update slower than solving a new problem from scratch.
3. Assumption Dependency: Many algorithms assume the system knows exactly where changes occurred, which is not always true in real-world sensing.

The paper challenges the long-held assumption that efficient incremental planning requires plan reuse. It posits that replanning from scratch using fast Almost-Surely Asymptotically Optimal (ASAO) planners can be more efficient and effective.

2. Methodology

The authors propose an Independent Incremental Planning approach. Instead of maintaining and updating a single global search tree, the robot solves a series of independent optimal planning problems as it moves.

• Algorithm: The robot uses an ASAO planner (specifically Effort Informed Trees (EIT)* and Asymptotically Optimal RRT-Connect (AORRTC)) to solve a new path planning problem at every replanning cycle.
• Process:
  1. The robot senses obstacles within a specific range ($r_s$) and time horizon ($\tau$).
  2. It defines a local "free space" based on current sensor data.
  3. It runs the ASAO planner to find a path from its current state to the goal within this local free space.
  4. The robot executes the path until it reaches the edge of the sensor range or detects a change, at which point it repeats the process.
• Theoretical Basis: ASAO planners are designed to find an initial feasible solution quickly and then converge toward the optimal solution as time permits. The authors argue that if the intermediate solutions are of high quality (near-optimal), the concatenation of these paths will naturally avoid unnecessary homotopy class switches (zig-zagging) and result in a near-optimal global path, without the overhead of explicit consistency checks or tree updates.

3. Key Contributions

1. Paradigm Shift: The paper demonstrates that the "replan from scratch" strategy, previously considered inefficient for dynamic environments, is actually superior to state-of-the-art plan-reuse methods when using fast ASAO planners.
2. Superiority of EIT:* The authors show that EIT* outperforms specialized incremental planners like RRTX (designed specifically for plan reuse) and standard sampling-based planners like RRT* and RRT-Connect.
3. Real-World Validation: The approach is validated not just in simulation but on a physical Franka Research 3 robot arm navigating moving obstacles in real-time, proving the viability of the method in high-dimensional, real-world scenarios.
4. Simplicity: The proposed method eliminates the need for complex change-detection mechanisms, prior knowledge of obstacle dynamics, or sophisticated tree-density management.

4. Experimental Results

The authors conducted extensive experiments comparing EIT*, RRT*, RRT-Connect, and RRTX across three simulated environments (Random Rectangles, Wall Gap, Double Enclosure) and a real-world robotic arm task.

• Success Rates:

  • EIT* achieved the highest success rates across all environments and planning budgets (0.01s to 0.1s).
  • RRTX failed to find a complete global solution in >90% of trials due to the computational cost of rewiring its tree. Even a "truncated" version of RRTX (stopping after the first solution) failed to maintain consistency.
  • RRT* struggled with small planning budgets, often failing to find an initial solution before time ran out.
  • RRT-Connect found solutions quickly but produced suboptimal paths that frequently changed homotopy classes, leading to longer global paths and more replanning cycles.

• Path Quality:

  • EIT* found the shortest median global path lengths in all scenarios. Its ASAO properties ensured that intermediate paths were consistent and near-optimal, preventing the robot from wandering into suboptimal regions.
  • RRT-Connect (even with smoothing) produced significantly longer paths than EIT*.

• Real-World Performance:

  • Using AORRTC on a Franka arm, the system successfully navigated moving obstacles in real-time. The planner could generate new paths fast enough to replan without stopping the arm, demonstrating that independent ASAO replanning is viable for high-dimensional, dynamic control.

5. Significance and Conclusion

This paper fundamentally re-evaluates the trade-off between plan reuse and replanning from scratch.

• Computational Efficiency: The overhead of detecting changes and rewiring dense trees in plan-reuse algorithms (like RRTX) often exceeds the cost of simply solving a new, high-quality problem from scratch.
• Robustness: The independent approach does not rely on the assumption that the system knows where obstacles have changed; it simply reacts to the new sensor data by solving a new problem.
• Practicality: The method requires minimal tuning (primarily just the planning budget) and no prior knowledge of obstacle dynamics, making it highly adaptable to unstructured environments.

Conclusion: The authors conclude that for real-time dynamic planning, fast ASAO planners running independently are a superior strategy to traditional incremental plan-reuse algorithms. They offer a better balance of speed, solution quality, and robustness, enabling robots to navigate complex, changing environments with near-optimal efficiency.