In classical artificial intelligence, planning is often treated as an offline process. An agent is given a problem, time freezes while a search algorithm finds the mathematically optimal path, and only then does the agent begin to move.
In the real world, however, time does not stop. A drone navigating a changing environment, a robot operating under a strict deadline, or an autonomous vehicle avoiding an obstacle must pay a price for every second spent "thinking." This cost manifests as consumed battery life, missed opportunities, or the risk that the environment will change so much that the computed plan becomes obsolete.
To build truly rational agents for real-time environments, we must abandon the quest for perfect plans and instead optimize the total cost of both deliberation and action.
The Total Time Objective
The core insight of this research direction is that an agent's true objective function should not be the minimization of execution cost alone, but rather the minimization of the sum of planning time and execution time:
$$T_{\text{total}} = T_{\text{planning}} + T_{\text{execution}}$$
As early as 1971, John H. Munson recognized in Robot Planning, Execution, and Monitoring in an Uncertain Environment that computational resources spent on planning represent a significant cost that must be balanced against the utility of execution. When an agent faces a strict deadline, spending too much time calculating a path can lead to a superior route but cause the agent to exceed its deadline anyway, as noted by Babak Hamidzadeh et al. in Can Real-Time Search Algorithms Meet Deadlines?.
To visualize why this works, consider an agent that discovers a shortcut that could save 5 seconds of travel time. If verifying that this shortcut is safe requires 6 seconds of computation, a rational agent should ignore it. As Jonathan Tash et al. demonstrated in Control Strategies for a Stochastic Planner, agents can achieve higher overall efficiency by selecting physically longer but computationally cheaper paths that are already well-understood.
Treating computational cycles as a finite resource equivalent to physical fuel or battery power—a framing formalized by Ethan Andrew Burns in Planning Under Time Pressure—fundamentally changes how we evaluate search algorithms. A perfect plan is counterproductive if the search duration exceeds the execution savings, a principle originally implemented in the NORA framework by Shashi Shekhar 0001 et al. in Minimizing Response Times in Real Time Planning and Search.
Metareasoning and Performance Profiles
How can an agent decide exactly when to stop thinking and start acting? This requires metareasoning—the process of an agent managing its own computational resources. To do this effectively, an agent must predict how much its plan will improve if it spends a few more seconds deliberating.
This prediction is driven by performance profiles, which map planning time to expected solution quality. In their foundational work, Mark S. Boddy et al. introduced a deliberation scheduler in Solving Time-Dependent Planning Problems to determine the mathematically optimal moment to transition from planning to execution. Similarly, Jun Miura demonstrated in Vision-Motion Planning of a Mobile Robot considering Vision Uncertainty and Planning Cost that an iterative refinement approach using performance profiles allows a robot to ensure its deliberative effort is strictly proportional to the expected improvement in execution.
This shift moves the goalposts of AI from "perfect rationality" to bounded optimality. As formalized by Stuart J. Russell et al. in Provably Bounded Optimal Agents, a system is optimal if it maximizes expected utility given its specific hardware constraints and the time pressure of its environment. When the exact quality of a plan cannot be directly observed, modern approaches leverage deep reinforcement learning to learn these contextual performance profiles from data, as shown by Bruno Lacerda et al. in Stop! Planner Time: Metareasoning for Probabilistic Planning Using Learned Performance Profiles.
Interleaving and Concurrent Execution
The most direct way to minimize the idle time spent waiting for a plan is to break the sequential "plan-then-act" bottleneck entirely. Instead, agents can interleave planning and execution or perform both concurrently.
In multi-agent environments, waiting for a globally optimal, congestion-free plan can cause massive delays. The authors of A Formal Metareasoning Model of Concurrent Planning and Execution, Amihay Elboher et al., provided a principled framework to balance the risk of making an early physical mistake against the risk of running out of time while stationary.
Building on this concept for Multi-Agent Path Finding (MAPF), Yue Zhang et al. proposed the PIE (Planning and Improving while Executing) framework in Planning and Execution in Multi-Agent Path Finding: Models and Algorithms. Instead of remaining stationary while a powerful solver crunches numbers, agents immediately begin moving along a fast, suboptimal but valid path. While in motion, the system refines the plan to resolve congestion. This drastically reduces the total time to success by eliminating the initial idle period.
Traditional: |--- Deliberation (Stationary) ---|====== Action ======>
Interleaved: |- Deliberation -|== Action ==|-- Deliberation --|== Action ==>
Concurrent: |--- Deliberation (Thread 2) ---|
|====== Action (Thread 1) ===========================>
For highly dynamic, high-pressure environments, Yule Wen et al. designed AgileThinker in Real-Time Reasoning Agents in Evolving Environments. This dual-thread architecture allows a fast reactive thread to "peek" at the partial outputs of a slow, deep planning thread, ensuring the agent remains highly reactive without sacrificing long-term strategic depth.
Why It Works: The Intuition of Diminishing Returns
The reason balancing deliberation and action works so effectively boils down to a fundamental property of search spaces: the diminishing marginal utility of planning.
When a planning algorithm begins searching, it typically discovers the macro-structure of a good solution very quickly (e.g., finding the general direction of a goal). The remaining majority of its computational time is spent on micro-optimizations—smoothing out minor curves, resolving distant multi-agent conflicts, or verifying that an obscure shortcut is perfectly safe.
While these micro-optimizations steadily decrease the physical execution cost, the rate of improvement is highly non-linear. The curve of plan quality versus planning time is sharply concave. Meanwhile, the opportunity cost of time is linear or even worse; in a time-pressured scenario, every second spent sitting still is a second permanently lost from the deadline.
By explicitly modeling this trade-off, metareasoning frameworks identify the zone where the slope of execution savings matches the slope of time elapsed. Stopping deliberation at this inflection point ensures that an agent never spends more cognitive overhead than it can recover during physical execution.
Key Foundational Work
Robot Planning, Execution, and Monitoring in an Uncertain Environment (1971) — contributed 2 concept elements to this direction.
Solving Time-Dependent Planning Problems (1989) — contributed 2 concept elements to this direction.
Reflection and Action Under Scarce Resources: Theoretical Principles and Empirical Study (1989) — contributed 1 concept elements to this direction.