When an autonomous agent operates in the real world, it faces a fundamental tension between thinking and doing. Imagine a drone navigating a dense forest or a robot on a fast-moving assembly line. If the agent spends too much time planning a perfectly optimal path, the time spent thinking might outweigh the execution time saved. Conversely, if it acts too quickly on a shallow, poorly thought-out plan, it may waste massive amounts of time and energy during execution.
To optimize performance, an agent should not aim to minimize execution cost alone. Instead, it must minimize total response time:
$$\text{Total Response Time} = \text{Planning Cost} + \text{Execution Cost}$$
The core challenge is that the agent does not know the true optimal execution cost in advance. How can an algorithm decide exactly when to stop searching for a better plan and finally commit to action?
A powerful family of strategies addresses this by treating search termination as a dynamic optimization problem, balancing the cumulative cost of computation against the estimated remaining cost of execution.
The Proportional Termination Rule
The foundational insight behind optimizing total response time is that planning exhibits diminishing returns. Early search iterations yield massive improvements to a plan, while later iterations spend significant computation making minor refinements.
To prevent a system from spending more time refining a plan than the refinement actually saves, early real-time frameworks like NORA (Near Optimal Response-time Algorithm), introduced by Shashi Shekhar 0001 et al. in Minimizing Response Times in Real Time Planning and Search, propose a proportional stopping criterion. The search algorithm tracks two metrics in real time: the accumulated cost of the planning phase so far ($C_{\text{plan}}$) and the estimated execution cost of the best solution found so far ($C_{\text{exec}}$).
The search is terminated immediately when the planning cost reaches a predefined fraction ($\lambda$) of the current best execution cost:
$$C_{\text{plan}} \ge \lambda \cdot C_{\text{exec}}$$
Why does this simple ratio-based threshold work so effectively? The elegance of this mechanism lies in its ability to provide provable performance bounds without knowing the global optimum. As detailed in Minimizing, if an agent halts planning when the computational effort reaches a fraction $\lambda$ of the best execution cost, the total response time is mathematically guaranteed not to exceed $(1 + \lambda)$ times the optimal response time. By tying the computational budget directly to the current quality of the solution, the system ensures its total latency remains strictly constrained even within massive or unknown search spaces.
Generalizing to Marginal Utility
This trade-off is not unique to pathfinding; it applies to any multi-stage optimization process where computation precedes execution. The underlying principle can be framed as maximizing the marginal utility of computation: an agent should continue searching if and only if the expected reduction in execution cost exceeds the cost of the computation required to find it.
For instance, in complex graphical model inference, researchers often face a "stopping problem" when searching for optimal graph decompositions. Andrew Gelfand et al. leveraged this principle in Stopping Rules for Randomized Greedy Triangulation Schemes by introducing the Minimum Total Query Time (MTQT) rule. Instead of using a fixed ratio, the MTQT rule statistically models the stochastic search process. It halts the search phase the moment the predicted cost of further search iterations outweighs the expected time savings in the subsequent execution phase.
Remarkably, this rational balancing act even explains quirks in human psychology. Falk Lieder et al. demonstrate in The anchoring bias reflects rational use of cognitive resources that the human "anchoring bias"—our tendency to stick too close to an initial guess—is not an inherent flaw in human reasoning, but a resource-rational strategy. By modeling the mind as an agent minimizing a joint cost function of estimation error and cognitive effort, the authors show that humans stop adjusting their estimates precisely when the marginal benefit of further mental refinement drops below the cost of the cognitive effort required.
Cost
▲
│ Total Cost (Planning + Execution) ▼ [Optimal Stopping Point]
│ \ .-------.
│ \ / \
│ \ / \____
│ '--' --- Execution Cost
│ / \
│ / \
│ / \____ Planning Cost
│ /
└──────────────────────────────────────────────► Search Effort / Time
Managing Hard Deadlines with Temporal Slack
Minimizing total response time is ideal when time is flexible, but real-time systems often operate under strict, hard deadlines. In these environments, an agent cannot simply track ratios; it must explicitly monitor the clock.
To bridge this gap, algorithms like DYNORAII, developed by Babak Hamidzadeh et al. in Can Real-Time Search Algorithms Meet Deadlines?, adapt ratio-based termination to handle strict temporal constraints. Instead of a static parameter, the system dynamically adjusts its search intensity based on temporal slack—the difference between the remaining time before the deadline and the estimated execution time of the current plan.
As explored in Deadline Compliance, Predictability, and On-line Optimization in Real-Time Problem Solving and the parallel work in Deadline Compliance, Predictability, and On-line Optimization in Real-Time, this slack dictates the agent's behavioral mode:
- High Slack: When the deadline is far away, the agent allocates a larger budget to planning, executing an exhaustive search to discover highly efficient, low-cost paths.
- Low Slack: As the deadline approaches and slack shrinks, the control parameters automatically shift. The algorithm curtails further planning and transitions into a rapid, greedy execution mode to guarantee deadline compliance.
This dynamic time allocation is also vital in probabilistic planning. Traditional tree-search methods often suffer from an inability to self-terminate, leading to deadline violations. To fix this, Andrey Kolobov et al. developed the GOURMAND architecture in LRTDP Versus UCT for Online Probabilistic Planning. By continuously monitoring computation speed at shallower search depths, the system accurately projects future computational costs. This allows it to dynamically decide whether to commit to a deeper lookahead or to terminate the search immediately, ensuring the agent always acts within its allocated time budget.
Key Foundational Work
Minimizing Response Times in Real Time Planning and Search (1989) — contributed 4 concept elements to this direction.
Minimizing Response Times in Real Time Planning and Search (1989) — contributed 3 concept elements to this direction.
Can Real-Time Search Algorithms Meet Deadlines? (1992) — contributed 2 concept elements to this direction.