Presented at AAAI-23, this research introduces a formal framework for agents that must act in the real world while simultaneously refining their plans. Moving beyond traditional "think then act" models, the proposed "think and act simultaneously" approach provides a principled way to balance the risk of early mistakes against the risk of running out of time.
Abstract
In time-pressured environments, agents often cannot afford to wait for a complete plan before taking action. This paper formalizes CoPE (Concurrent Planning and Execution), a metareasoning model that allows an agent to execute parts of a plan while search continues. By modeling the tradeoff between the time gained by acting early and the risk of irreversible commitments, the authors develop algorithms that significantly improve success rates in situated planning tasks.
The Problem: Planning as a Situated Activity
In classical AI planning, the world is often assumed to be static while the agent computes. However, in reality, time is a finite resource. If an agent spends too long deciding on an optimal path, it may miss the opportunity to act entirely. Previous "situated planning" models acknowledged that planning takes time but still required a complete plan before execution. CoPE addresses the "bolder" agent: one that can start executing a known prefix of a plan while still calculating the remainder. The primary challenge is irreversibility; an early action might preclude the eventual optimal plan if the search later reveals a conflict.
The CoPE Model and Algorithms
The authors define CoPE as a Markov Decision Process (MDP) where planning is represented as $n$ parallel processes. Each process consists of a "head" (a known action sequence) and a "remainder" (the unknown part of the plan). Executing a head action frees up time for the planner but invalidates any processes incompatible with that action.
To solve this, several algorithms were proposed:
- Max-LET$_A$: An execution-focused approach that schedules actions at their "Latest Execution Time" to maximize planning time.
- Demand-Execution: A reactive approach that only executes an action when it is absolutely necessary to avoid missing a deadline.
- MCTS: A hybrid approach using Monte Carlo Tree Search to navigate the complex MDP state space.
Evaluation and Key Results
The model was evaluated using the 15-puzzle, with 10,000 instances solved to generate meta-level statistics and performance profiles. These profiles allowed the simulation of realistic scenarios where the agent knows the statistical likelihood of search duration and plan length.
Success Under Pressure
CoPE-aware algorithms significantly outperformed traditional situated planning methods, especially when time pressure was high (i.e., actions have longer durations). Standard "timid" algorithms that wait for a full plan saw success rates drop toward zero as deadlines tightened, whereas CoPE agents maintained high performance by committing to early actions.
Efficiency and Runtime
The Max-LET$_{BGS}$ algorithm emerged as a particularly effective solution, achieving high success probability with a runtime of less than one second. This makes it highly suitable for real-time integration into existing planners.
Insights and Future Directions
A core insight of this work is that execution is a resource: by starting a known plan prefix, the agent pushes back the "induced deadline" for the remaining search. The study also highlights the optimality of "lazy" policies—delaying execution as long as possible to preserve options without becoming tardy.
Future work aims to extend CoPE to stochastic environments where the world itself is uncertain, and to integrate these metareasoning techniques into online planners that re-evaluate the CoPE instance dynamically as search progresses.
Summary updated