Planning Climbs on Rock You Have Only Touched a Few Times

A climbing robot that grips rock with microspines (arrays of tiny sprung hooks that catch on surface bumps) never knows for certain whether a given handhold will hold. Whether a hook catches or the bump crumbles is a matter of chance. In practice the robot's belief about each candidate hold rests on a handful of test pulls. Current planners treat the estimated grip-success probability as known. They also choose holds and compute forces in separate stages. As a result, a plan can look 95% safe on paper while depending on a hold tested twice. We propose a single planner, posed as a mixed-integer linear program (an optimization problem mixing yes/no choices with continuous quantities). It picks holds and contact forces together and scores each hold by an honest lower confidence bound on its success probability, computed from the actual number of test pulls. It also refuses to trust any one failure model when several fit the sparse test data equally well.

The idea in two sentences: treat each handhold the way a particle physicist treats a weak signal from few events, with error bars that shrink only as one over the square root of the number of trials, plus explicit hedging across models the data cannot tell apart. Then make the joint hold-and-force decision tractable at the scale of thousands of candidate holds, using learned warm starts whose output is always checked by an exact solver.

Core Claim

Our claim is that, for stochastic-grip climbing, most of the gap between the success a plan predicts and the success it actually achieves comes from two sources. The first is treating estimated grip probabilities as exact. The second is separating hold selection from force feasibility. A joint program built on confidence bounds should close that gap without making plans much longer.

The baseline pipeline is Motion Planning for a Climbing Robot with Stochastic Grasps. It models microspine grip limits as a confidence ellipsoid in force-and-torque space and turns success probability into a convex cost through a negative log. It chooses footholds first, by A* search minimizing step count, and then optimizes forces with sequential convex programming. In their 2D simulation they report a planned success rate above 90% in 86% of 100 randomized trials, with about one minute for foothold search and 10–50 seconds for trajectory optimization. That paper motivates this work: it shows that stochastic grip models are usable for planning. Its open edges are the ones we target. Its hold choice ignores force feasibility, and its grip model is a fixed calibrated object, not an estimate with sample-size-dependent uncertainty.

The Formulation

For a candidate hold $i$ tested $n_i$ times with $k_i$ successful holds, we replace the point estimate $k_i/n_i$ with an exact binomial lower confidence bound $L_i$. The width of this bound shrinks roughly as $1/\sqrt{n_i}$ under Poisson/binomial counting statistics. Grip probability also depends on load, so $L_i$ becomes a load-dependent curve. For any route that commits to a set of holds, the bound on overall success is a product of per-hold terms. Taking logs turns the product into a sum, which keeps the problem linear:

$$\max_{z,\,f}\ \sum_i z_i \, \ell_i(f_i) \quad \text{s.t.}\quad \text{force and torque balance},\ \ f_i \in z_i \cdot \mathcal{P}_i,\ \ \text{reach and sequencing constraints on } z.$$

Here $z_i \in \{0,1\}$ selects hold $i$ and $f_i$ is the force applied there. $\ell_i(f_i)$ is a piecewise-linear under-approximation of $\log L_i$ as a function of load. $\mathcal{P}_i$ is a polyhedral inner approximation of the ellipsoidal grip limit, chosen as an inner approximation so that approximation errors stay on the safe side. The linking constraints $f_i \in z_i\mathcal{P}_i$ are standard big-M constraints. The rigid-body path-planning MILP of Rigid Body Path Planning using Mixed-Integer Linear Programming supplies the encoding style. Its model covers only geometric free space, with no contact mechanics.

The second ingredient addresses model degeneracy, and it is borrowed from hadron spectroscopy. In Observation of an anomalous line shape of the η′π+π− mass spectrum near the pp̄ threshold, BESIII fit a threshold structure with two physically incompatible models: a Flatté threshold opening and two interfering resonances. The data could not prefer either. Sparse pull tests have the same problem. A "hook slips" model and an "asperity fractures" model can fit three to five pulls equally well, yet extrapolate very differently to high loads. Following the physics lesson that indistinguishable models must both be carried forward, we keep every failure model whose fit to the test data is statistically indistinguishable from the best. We then set $\ell_i$ to the pointwise minimum across those models. A minimum of concave piecewise-linear functions is still concave piecewise-linear, so the epigraph stays linear and the program remains a MILP.

Research Program

The work has three parts. First, we will build a stochastic rock simulator with known asperity statistics. This simulator is the ground truth for realized success, so we can measure the gap between predicted and actual success. Real pull-test datasets for microspines are not in our file, so physical validation would require new data collection. We flag this as a dependency rather than a reported resource.

Second, we will implement the joint program in 2D, matching the ReachBot setting, and in 3D. The 3D version adds out-of-plane torque limits, which the adhesion literature flags as poorly handled.

Third, we will address scale. With thousands of candidate holds and tens of steps, the number of binary variables reaches the tens of thousands, where Apollo-MILP and Differentiable Integer Linear Programming both report that standalone Gurobi slows sharply. We will train a graph network on simulated walls to predict hold selections. Following Apollo-MILP's rule, we fix only those variables on which the prediction and a trust-region solver correction agree. The exact solver then certifies force feasibility of the final plan. A violated balance constraint here means the robot falls, so no learned output is ever executed uncertified. An extension, not the core claim, makes probing itself a decision: the robot chooses which holds to test further before committing.

Baselines

The naive reference point is a shortest-step plan with deterministic friction limits and no stochastic model. It shows how much any risk modeling matters.

The strongest existing method is the Newdick et al. two-stage pipeline: A* foothold search followed by sequential convex programming over the stochastic grip ellipsoid. We will re-implement it on the same simulated walls, with the same grip calibration data and the same wall-clock budget, so its 86%-of-trials figure can be reproduced before comparing. Beating it means a higher fraction of trials whose realized success exceeds 90%, at comparable planning time and plan length.

A stronger variant we construct ourselves is risk-aware A*. It uses $-\log$ of the point-estimated success probability as the edge cost, followed by the same convex force stage. It isolates the benefit of joint optimization from the benefit of probability-aware hold choice.

The key ablation is our joint MILP using plug-in probabilities $k_i/n_i$ instead of confidence bounds, and a single best-fit failure model instead of the minimum over indistinguishable models. If this ablation matches the full method on realized success, the statistical ingredient is not doing the work.

For scale, we compare four solvers on identical instances with equal time limits: standalone Gurobi, Apollo-style prediction-correction, a DiffILO-style unsupervised relaxation followed by solver repair, and naive neural diving. Apollo-MILP reports more than an 80% primal-gap reduction over Gurobi on academic benchmarks. DiffILO reports feasible-solution rates of only 50.8% on Set Covering. On contact-planning instances, no reported result was found on Lacuna for any of these methods.

Why not just…?

Why not just use risk-aware A* followed by convex force optimization? This is the real threat. If grip success depends mostly on which hold is chosen and only weakly on load direction, a good graph cost may capture nearly everything. The risk-aware A baseline tests this directly. If it matches the joint MILP on realized success, we will report that the joint formulation is unnecessary and keep only the confidence-bound scoring. That scoring can be dropped into A edge costs.

Why not just plug in point estimates of grip probability? With three or four pulls per hold, the point estimate can be 1.0 for a hold that fails a third of the time. The plug-in ablation measures how often plans route through such holds. The relevant evidence is the gap between predicted and realized success, binned by test count $n_i$. We expect that gap to grow as $n_i$ falls. The BABAR X(3872) radiative-decay analysis is a reminder of how wide few-event intervals are: its branching ratio of 3.4 ± 1.4 carried 40% uncertainty at 3.5σ.

Why not just hand the MILP to Gurobi? At the scale of ReachBot instances this may well suffice, and we will say so if it does. The learned warm start only earns its place if Gurobi's time to a good certified plan grows sharply as candidate holds go from hundreds to thousands. The scaling sweep tests exactly this.

Why not sample scenarios of hold outcomes instead of using bounds? Scenario sampling still needs a distribution for each hold's success probability. With few pulls, that distribution is exactly what is uncertain. Scenarios drawn from point estimates inherit the plug-in problem. Scenarios drawn from a posterior are a reasonable alternative, and we will include a posterior-sampled scenario program as a secondary comparison.

Decisive Checks

The method succeeds only if three things hold on held-out simulated walls. First, the predicted lower bound on success is calibrated: realized success meets or exceeds it in at least the nominal fraction of trials, for every test-count bin, while the plug-in ablation does not. Second, the fraction of trials with realized success above 90% clearly exceeds the re-run 86% of the Newdick pipeline at similar planning time. Third, at 5,000 or more candidate holds, the certified prediction-correction solver reaches a feasible plan within a fixed time budget on instances where standalone Gurobi does not.

If the first check fails, the statistical modeling is wrong. If the second fails while risk-aware A* matches us, the joint program is not needed. If only the third fails, the contribution narrows to the formulation itself, without the scaling machinery.