A robot or game character that must plan a route and then walk it pays for both. Every millisecond spent searching for a shorter path is a millisecond it is not moving. In 1989, Shekhar and Dutta proposed a simple rule for this situation. Keep improving the plan, and stop as soon as the time already spent planning reaches a fixed fraction λ of the execution cost of the best plan found so far. They proved that this rule keeps total response time (planning plus execution) within $\max(1+\lambda, 1+1/\lambda)$ of the best achievable. That is a factor of 2 at $\lambda=1$. The rule costs almost nothing to check. Yet it has never been tested on a modern search benchmark. Its only evaluation was one simulated database query. Its follow-ups were tested on 30-node random graphs and a 10×20 grid.
This note proposes to close that gap, and to do more than rerun the old rule on bigger maps. We attach the ratio rule to ARA, an anytime planner that produces a sequence of improving paths. ARA also reports how far each path can be from optimal, which gives a provable lower bound on the best possible path cost. That lower bound lets us do two new things. First, the ratio rule can be applied to the savings that are still possible rather than to the whole execution cost. Second, every run can issue an online certificate of how close it came to the best achievable total time. The certificate needs no oracle and no hindsight. The result is a validation method that other theory-heavy stopping rules could reuse.
Core Claim
The obvious study, "benchmark NORA (the Near Optimal Response-time Algorithm) on Moving AI grids," is unclaimed in the literature but is thin by itself. The claim here is sharper and has three parts.
First, when NORA's rule is wrapped around a state-reusing anytime planner on standard game and maze maps, its empirical ratio to the best-in-hindsight total response time will sit well below the worst-case bound on open maps. It should approach the bound on maze and corridor maps, where large improvements arrive late in the search.
Second, a "remaining-savings" variant of the rule will stop earlier when further search can provably save little, while keeping a comparable worst-case guarantee. That variant replaces the incumbent execution cost with the gap between the incumbent cost and ARA*'s lower bound.
Third, the ratio of achieved total time to the ARA* lower bound gives a per-instance certificate. This turns "does the theory hold in practice?" into a quantity measured on every run.
Concretely, let $\tau$ be planning time spent so far. Let $c$ be the cost of the current best path. Let $\varepsilon'$ be ARA*'s current suboptimality bound, so the optimal path cost is at least $L = c/\varepsilon'$. Let $\kappa$ be execution seconds per unit path cost, a stand-in for how fast the agent moves relative to the computer. NORA stops when $\tau \ge \lambda\kappa c$. The remaining-savings rule stops when
$$\tau \ge \lambda\,\kappa\,(c - L),$$
that is, when planning time reaches λ times the most execution time that any further planning could still save. After stopping, the run reports the certificate
$$R = \frac{\tau + \kappa c}{\kappa L},$$
which upper-bounds the ratio of achieved total time to any plan-then-execute strategy. The bound holds because no strategy can execute a path cheaper than $L$.
Prior Work and Where This Sits
The ratio rule itself comes from Minimizing Response Times in Real Time Planning and Search. That paper proved the $\max(1+\lambda,1+1/\lambda)$ bound. Its evidence is a single simulated shipping-database query, which stopped at iteration 3 with response time 1.5× optimal at λ=1. We reuse its rule and its bound as the hypothesis under test.
Two follow-ups by Hamidzadeh and Shekhar motivate the proposal by showing that ratio rules beat fixed-lookahead search, but only on tiny synthetic graphs. Can Real-Time Search Algorithms Meet Deadlines? showed DYNORAII (a deadline-driven version of the ratio rule) reaching 100% completion within 400 time units versus 970 for Real-Time A (RTA), on 30-node graphs. Deadline Compliance, Predictability, and On-line Optimization in Real-Time Problem Solving adjusted the ratio from remaining slack on a 10×20 grid. The second paper also constrains us. It found that predictability depends on whether the heuristic over- or underestimates. That is why we restrict the rule to complete incumbent paths with known cost, rather than heuristic guesses of remaining cost. Using the heuristic would break the premise of NORA's proof.
The planner comes from ARA: Anytime A with Provable Bounds on Sub-Optimality. ARA reuses search effort across iterations while shrinking an inflation factor toward 1. It was shown 140× faster than repeated A on a 20-degree-of-freedom arm. But it has no internal stopping rule; it relies on an external deadline or a hand-set ε schedule. We supply the stopping rule it lacks, and we reuse its suboptimality bound as the lower bound $L$.
The closest connected work uses a different stopping mechanism in a different setting. Stopping Rules for Randomized Greedy Triangulation Schemes (MTQT, Minimum Total Query Time) stops a randomized search when the expected wait for a better solution exceeds the predicted savings. It fits Poisson and Dirichlet models and was validated on real Bayesian networks. It differs from our proposal in two ways. It assumes random arrivals of improvements, which deterministic A*-family search does not produce. Its meta-level modeling has runtime cost, and that overhead is exactly what a millisecond-scale planner cannot afford.
LRTDP Versus UCT for Online Probabilistic Planning shows that a sound convergence signal beats hand-tuned lookahead. GOURMAND scored 0.9183 against PROST's 0.8608 on IPPC-2011, the 2011 International Probabilistic Planning Competition. However, it works under per-step deadlines with a known transition model, not unconstrained total time. We cite it as evidence that hand-tuned budgets fail, not as a direct competitor.
The benchmark is Benchmarks for Grid-Based Pathfinding.
Research Program
The program has four pieces.
The first is a replay harness. For each Moving AI scenario, we run ARA* once from a high inflation factor down to ε=1. We record the full anytime profile: every incumbent cost, its ε′, and the wall-clock and expansion time at which it appeared. Given a profile and a value of κ, the best-in-hindsight stopping point is the minimum of $\tau_k + \kappa c_k$ over recorded improvements $k$. Any stopping rule can then be scored exactly and cheaply across many λ and κ values. This addresses the "single instance" weakness of the original evaluation by making millions of rule-instance-κ evaluations affordable.
The second is live runs. Replay ignores the cost of checking the rule and of timer noise. We therefore rerun a stratified subset live and measure the overhead of each rule in wall-clock time. This takes up the file's point that meta-level computation is often left out of analysis.
The third is theory. We will try to prove a worst-case bound for the remaining-savings rule, in the style of NORA's argument. The bound would hold relative to the excess $\kappa(c^*-L)$ plus the unavoidable $\kappa L$. If the proof fails, we will construct the adversarial profile that breaks it and report that instead.
The fourth is a characterization study. It relates the empirical ratio and certificate tightness to map class (maze, room, open game map, random) and to the time at which large improvements arrive in the profile. This directly tests the concern that late or deceptive improvements trigger premature stopping.
Baselines
The naive reference points are the two endpoints of the anytime profile. One is "execute the first solution," meaning ARA's first inflated-heuristic path with no refinement. The other is "run to convergence," meaning ARA down to ε=1. Both are scored on the same profiles. Our rules must beat the better of the two at every κ. Otherwise the stopping question is moot in that regime.
The strongest simple competitor is a fixed planning budget, either in time or in ARA* iterations, tuned per map class. For fairness, we tune it by grid search on a held-out half of the scenarios, separately for each κ. That gives it an advantage our rules do not have, since our λ is set once at the worst-case-optimal value λ=1 and then also tuned on the same held-out split. Beating it means a lower mean and lower 95th-percentile ratio to hindsight-optimal total time on the test half. We also run a stricter test: transfer to map classes and κ values the budget was not tuned on.
The strongest existing method with a principled stopping criterion is MTQT. We adapt it by fitting its improvement-arrival model and its savings predictor to the incumbent sequence, using the authors' formulation. It runs with the same profiles and the same live overhead accounting. Its best reported result is the 90 hours of total computation saved on Mastermind relative to ad hoc rules Stopping Rules for Randomized Greedy Triangulation Schemes. For any ratio or total-time metric on Moving AI grids, no reported result was found on Lacuna, for MTQT or for any other rule. The only numbers for a ratio rule are DYNORAII's 400 versus 970 time units for RTA* on 30-node graphs. That is not comparable, which is precisely the gap.
Two ablations isolate the key ingredient. The first is plain NORA versus the remaining-savings rule, on identical profiles. This separates the effect of using ARA's lower bound from the effect of the ratio idea. The second is ARA with state reuse versus restarted weighted A* under the same rule. This tells us whether state reuse matters to how well the rule performs.
Why not just…?
Why not just give the planner a fixed time budget? This is the real threat. On a single map class at a single κ, a tuned budget may match the ratio rule within a few percent. The ratio rule's possible advantage is that it scales automatically: its stopping time grows with the execution cost of each instance. A fixed budget must be retuned whenever map size or agent speed changes. The transfer experiment across κ and map classes settles this. If the tuned budget transfers as well as λ=1 does, the method contribution shrinks to the validation study and the certificate, and we will say so. The deadline results in Can Real-Time Search Algorithms Meet Deadlines? and LRTDP Versus UCT for Online Probabilistic Planning suggest fixed budgets fail on goal-oriented domains, but neither result is on our objective.
Why not just run ARA* until a deadline, as its authors do? There is no natural deadline when the objective is total time. Any deadline is a fixed budget in disguise, so the previous experiment covers it. The run-to-convergence baseline also shows what happens with no stopping at all.
Why not just use a marginal-utility rule like MTQT? In principle it should stop closer to the hindsight optimum. But its arrival model assumes random improvements, and fitting the model takes time at every check. The live-overhead runs measure whether its better stopping decisions survive that cost at millisecond planning scales. If MTQT wins even after overhead, that is a publishable negative result for ratio rules.
Proposed Experiments
We use the Moving AI grid suites: Dragon Age and StarCraft game maps, mazes, room maps, and random grids, all with their standard scenario files. Each runs with octile-distance ARA* starting from an inflation factor of 3. We sweep κ over several orders of magnitude, from "slow robot, fast CPU" to "fast agent, slow CPU." We sweep λ over a log grid. The metrics are as follows. The primary metric is the ratio of achieved total time to the hindsight-optimal stopping point on the same profile. We also report the certificate $R$ and its gap to the true hindsight ratio, wall-clock overhead per rule check, and the fraction of instances exceeding NORA's worst-case bound. That fraction should be zero if the proof's assumptions hold.
Three checks are decisive. First, any instance where plain NORA's ratio exceeds $\max(1+\lambda,1+1/\lambda)$ would falsify the bound's applicability. Such a violation would reveal an assumption that wall-clock timing or incumbent behavior breaks. Second, the remaining-savings rule should reduce mean and tail ratio on open game maps, where ARA*'s bound tightens fast. It should not help on mazes, where $L$ stays loose. Third, the median certificate $R$ should land within a small factor of the true hindsight ratio. If it does, $R$ can serve as a deployable, oracle-free audit of stopping quality.
References
- Minimizing Response Times in Real Time Planning and Search
- Can Real-Time Search Algorithms Meet Deadlines?
- Deadline Compliance, Predictability, and On-line Optimization in Real-Time Problem Solving
- ARA*: Anytime A* with Provable Bounds on Sub-Optimality
- Stopping Rules for Randomized Greedy Triangulation Schemes
- LRTDP Versus UCT for Online Probabilistic Planning
- Benchmarks for Grid-Based Pathfinding