Ambiguity-Driven Lookahead for Task and Motion Planning

Robots that plan long manipulation tasks, such as stacking blocks, clearing a cluttered shelf, or climbing stairs, face two coupled problems. The number of possible action sequences grows exponentially with plan length. The geometry that decides whether an action is physically possible is usually approximated with spheres, convex hulls, or bounding boxes so that it stays cheap to check. The standard fix for the first problem is receding-horizon planning: solve only the next $h$ actions, commit to the first one, and slide the window forward. That fix fails in a predictable place. If an early commitment quietly makes a later step impossible, for example by placing an object where it later blocks a narrow gap, a short window cannot see the dead end coming.

This proposal argues that the geometric approximation already tells us where such dead ends can hide. The planner checks each geometric condition twice, once with a conservative, too-large version of the shapes and once with an optimistic, too-small version. Wherever the two checks disagree, the approximation cannot settle feasibility. The proposal is to let those disagreements set the planning window: look further ahead only when disagreements lie near the end of the current window, and refine the geometry only on the specific shapes that cause disagreement. Lookahead depth and geometric precision become two ways of spending a single error budget, and the budget is spent only where the approximation is actually uncertain.

Core Claim

In receding-horizon task and motion planning (TAMP), meaning planning that interleaves a symbolic search over discrete actions with continuous checks for reachability and collision, the harm of committing early is concentrated at a small number of geometrically ambiguous steps. These are steps where an outer (conservative) and an inner (optimistic) approximation of the scene disagree about feasibility. For each geometric predicate $p$ (a reach or collision-free-placement check), define $g_{\text{out}}(p)$ and $g_{\text{in}}(p)$ as its signed clearance computed with outer-bounding and inner-bounded geometry respectively, with negative values meaning infeasible. The predicate is ambiguous when

$$ g_{\text{out}}(p) < 0 < g_{\text{in}}(p). $$

In that case feasibility depends on shape details the approximation has discarded. The planner extends its window past the last ambiguous predicate by a small margin, up to a cap. It refines the geometry only for the shape elements responsible for ambiguous predicates. When the whole window is unambiguous, it keeps the window short.

The claim is that this rule matches the success rate of a long fixed window while paying close to the cost of a short one. It is the geometric analogue of the "bottleneck states" that Planning and Learning with Adaptive Lookahead showed dominate convergence in abstract Markov decision processes (MDPs).

Relation to Prior Work

The nearest system is RHH-LGP. It runs Logic-Geometric Programming, a formulation that couples symbolic action choice with trajectory optimization, over a sliding window of $h$ actions. It prunes symbolic actions with a reachability sphere around the manipulator base, and it scaled Stair Climbing from 4 stairs (plain LGP) to 64. Two of its design choices are exactly what this proposal changes. Its window $h$ is a fixed hyperparameter, and its sphere is a one-sided approximation that yields both false positives and false negatives. Here the window length becomes a function of geometric ambiguity, and the sphere is replaced by paired inner and outer reachability sets.

Several papers supply the method. KABouM builds outer-bounding convex decompositions with one-sided guarantees: if the bounds are collision-free, so is the real object. We reuse its outer bounds and add inner bounds to obtain a two-sided test. KABouM also found that once collision checks are made roughly 10x cheaper, symbolic search becomes the bottleneck, and it timed out at 8 stacked objects. That finding constrains the design: faster geometry alone will not solve these problems, so any gain must come from reducing symbolic lookahead, not only from faster checks. GNPP feeds minimal infeasible sets of continuous constraints back to the symbolic planner as "nogoods," which are learned rules that prune every branch sharing the same failure. It relaxes collision constraints to catch about 90% of failures cheaply. However, GNPP reasons over the full plan horizon and toggles constraints on or off rather than changing their resolution. Our ambiguity test can be seen as a graded version of its relaxation, used to decide depth instead of to prune.

Two further papers motivate the work by documenting the dead-end problem. Learned backjumping shows that geometric choices made early cause failures many steps later in Packing and in NAMO (navigation among movable obstacles), and it repairs these failures after the fact by predicting which earlier action caused them. PIGINet ranks complete, fixed-length candidate plans by learned feasibility. Neither method gives guarantees, and neither decides how far ahead to look.

On the adaptive-horizon side, optimal-horizon DDP optimizes horizon length inside differential dynamic programming (DDP), a trajectory optimizer, using a quadratic value approximation whose error grows cubically with distance from the nominal trajectory. The same work notes that this approximation breaks down under strongly non-convex geometry. Rosenberg et al. adapt lookahead per state in tabular and Atari settings with no geometry. Our contribution is a geometric signal for where depth is needed. That signal is available in continuous, non-convex, multi-object scenes where neither of these methods applies.

The clinical literature supplies a cautionary parallel. One-sided shape primitives are biased in a consistent direction: ellipsoid formulas overestimate hematoma volume (3D Slicer vs. Tada), and vendor ablation ellipsoids overestimate lesion volume (lung ablation prediction). A single approximation cannot report its own uncertainty. A paired inner and outer approximation can.

Research Program

The system is a receding-horizon LGP-style planner reimplemented from RHH-LGP's description, since no public code is referenced in our sources. It has three additions.

The first is a two-sided geometry layer. Outer bounds are KABouM-style enclosing convex pieces. Inner bounds are convex pieces inscribed in each mesh, and inner reachability sets are shrunken hulls of configurations whose inverse kinematics has been verified. Both are organized as hierarchies so that any piece can be split to tighten it.

The second is the ambiguity-driven window rule. After each symbolic expansion, the planner evaluates every geometric predicate in the window under both bounds. If an ambiguous predicate falls within $m$ steps of the window's end, the window grows. The planner commits the first action only when the window's last $m$ steps are determinate.

The third is local refinement. Before growing the window, the planner may split the hierarchy nodes that underlie an ambiguous predicate, since one split is often cheaper than one extra step of lookahead. The choice between refining and deepening is made greedily by comparing the expected number of predicates each would resolve per unit of compute, using costs measured online.

The analysis component is deliberately modest. In a chain-structured construction extending Rosenberg et al.'s Chain MDPs, we will prove the following. If every predicate beyond the window is determinate-feasible under the outer bounds, then committing the first action cannot create a geometric dead end. We will also measure how often this sufficient condition holds in practice. We do not claim that it prevents dead ends caused by purely symbolic structure.

Baselines

The naive reference point is RHH-LGP with a short fixed window ($h=1$ or $2$) and its original reachability sphere. This shows how much a cheap planner loses to early commitment.

The strongest existing method is RHH-LGP with $h$ tuned per benchmark by grid search. Its reported result is solving Stair Climbing at 64 stairs where baseline LGP timed out after 4. We give it the same grid-search budget in planner calls that our method uses for tuning its margin $m$ and window cap. All methods run on identical scenes, random seeds, and wall-clock timeouts.

The second strong baseline is GNPP on its own benchmarks. It reports a 12-action Laboratory plan in 8.88 seconds and reliable Workshop solutions where competing solvers failed within 100 seconds. We run it at the same timeout.

On Packing and NAMO the relevant competitor is learned backjumping. It reports a 40% efficiency gain in Packing and 99% fewer visited nodes in NAMO relative to chronological backtracking. We did not find absolute success rates or times for these tasks, so we rerun it with the same simulator and training data budget.

Three ablations isolate the key ingredient. One pairs ambiguity-driven depth with fixed, coarse geometry. One pairs ambiguity-driven refinement with a fixed window. The third deepens randomly on steps chosen to match our method's total extra-depth budget. That last control tests whether where we deepen matters or only how much.

Beating the baselines means one of two things. Either our method reaches the tuned-$h$ baseline's success rate with at least a 2x reduction in median planning time, or it solves strictly larger instances (more stairs, more stacked objects) at equal time.

Why not just…?

Why not just deepen the window whenever planning fails (iterative deepening)? This is the most serious threat, because it is simple and needs no geometry changes. Its weakness is that it reacts only after a committed action has already produced a dead end. At that point it must backtrack through executed commitments, which is the overhead learned backjumping exists to reduce. We include it as a baseline at matched compute. If it matches our method on Packing and NAMO, where dead ends are late and severe, then the ambiguity signal adds nothing, and we would reframe the contribution around refinement alone.

Why not just use exact meshes everywhere with a tuned fixed window? KABouM is direct evidence against this. Its 10x cheaper collision checks still left symbolic search as the bottleneck, with a timeout at 8 stacked objects. Exact geometry also removes ambiguity entirely, and with it the signal for where to look deeper. The fixed-window, exact-geometry ablation measures this directly.

Why not just learn a feasibility predictor, as in PIGINet, and rank plans? PIGINet cuts planning time by 10–50% in complex kitchens. However, it scores complete fixed-length plans without guarantees, and it requires large offline datasets from classical solvers. Our signal needs no training, and its outer bounds keep KABouM's safety property. The two approaches are complementary: a learned predictor could order expansions inside our adaptive window. We treat that combination as an extension, not a competitor.

Proposed Experiments

The benchmarks are RHH-LGP's Stair Climbing, Multi-Robot Pick-and-Place, and Parkour; KABouM's Stacked $n$ Objects and Bartender; GNPP's Laboratory and Workshop; and Packing and NAMO in PyBullet, following Sung et al. The metrics are success rate within a fixed timeout, median wall-clock time, symbolic nodes expanded, number of geometric queries by resolution level, and plan length.

Three results would settle the proposal. First, on Stacked $n$ Objects we measure the largest $n$ solved within the timeout, against KABouM's failure at $n=8$ and against tuned RHH-LGP. Second, the random-deepening ablation at matched depth budget tests whether ambiguity locates the bottleneck steps. If random placement performs as well, the core claim is false. Third, on Packing and NAMO we record the fraction of dead ends that occur at steps flagged ambiguous before commitment. We expect most of them to be flagged. A low fraction would show that geometric ambiguity is not where dead ends originate in these domains. Finally, we report how often the outer-certified-tail condition holds, which indicates how much of the practical gain the analysis explains.