Abstract
In real-time AI planning, time spent deliberating is time lost for execution. This paper introduces the AE2 (Allocating Effort when Actions Expire) problem, where an agent must distribute limited computational resources across multiple potential plans, each subject to its own expiration deadline. We formalize this as a Markov Decision Process (SEA2) and demonstrate its computational hardness. By drawing parallels to job scheduling with diminishing returns, we propose a suite of algorithms, including a high-performance greedy real-time heuristic. Empirical evaluations on synthetic and realistic search trees show that our methods significantly outperform standard planning heuristics, particularly in environments with uncertain deadlines.
Introduction
Classical AI planning often operates under the assumption that the world remains static during the deliberation process. However, in dynamic environments, actions have deadlines. For instance, if an agent is deciding between taking a bus or a taxi to the airport, the utility of the "bus" plan drops to zero once the bus departs. Every second spent refining one plan is a second not spent on another.
This "metareasoning" challenge requires an agent to decide not just what to do, but what to think about. Most modern planners use heuristic search to explore a frontier of partial plans, but they rarely account for the fact that actions expire or that planning effort itself is a finite resource.
Problem Formalization: The SEA2 MDP
The authors formalize the challenge as the SEA2 (Scheduling Effort for Actions that Expire) problem, modeled as a Markov Decision Process (MDP). Given $n$ partial plans, each characterized by an estimated completion time and an expiration deadline, the goal is to allocate processor time to maximize the probability of finding at least one valid, timely solution.
Solving the full SEA2 MDP is PSPACE-complete, necessitating the development of efficient approximations:
- Linear Policies: Pre-set sequences of node expansions that do not adapt to mid-process failures.
- ScheduleDR: An adaptation of job scheduling algorithms for scenarios with "diminishing returns," assuming that additional work on a plan yields decreasing marginal gains in success probability.
- The Greedy Real-Time Algorithm: A practical heuristic that selects the next node to expand by balancing urgency (proximity to deadline) and efficiency (success probability per unit of time).
Experimental Setup
The proposed algorithms were evaluated against several baselines, including Round-robin (RR) and Most Promising Plan (MPP). The testing used two primary data sources:
- Synthetic Distributions: Performance profiles and deadlines generated using Boltzmann (B), Normal (N), Uniform (U), and Poisson (P) distributions to test mathematical robustness.
- Realistic Search Trees: Data extracted from the OPTIC temporal planner running on the Robocup Logistics League domain, providing real-world statistics on node expansion and expiration.
Results
The experimental results, summarized in the table below, highlight the strengths of the proposed metareasoning strategies across different deadline distributions and numbers of processes (# pr).
Key findings include:
- Greedy Dominance in Uncertainty: The greedy real-time algorithm consistently achieved the highest solution quality (Q) when deadlines were unknown (UK). While it is computationally more intensive than simpler heuristics, it remains well within the bounds for real-time application and is orders of magnitude faster than the full MDP solution.
- ScheduleDR for Known Deadlines: When deadlines are known (K) and returns are diminishing,
ScheduleDRproves nearly optimal and extremely fast, often outperforming the more complex MDP solutions which suffer from high computational overhead (T). - The Scheduling Connection: The results validate the theoretical link between AI planning under deadlines and "minimum tardiness job scheduling," showing that operations research techniques can be effectively adapted for AI metareasoning.
Conclusion and Future Work
This work establishes a robust framework for allocating planning effort in time-sensitive domains. By treating planning as a resource-constrained scheduling problem, the AE2 model allows agents to make smarter decisions about their own deliberation.
Future research will address the Dynamic AE2 problem, where the set of available plans changes as the search tree grows. Integrating these metareasoning "brains" into live temporal planners like OPTIC will be a crucial step toward more resilient autonomous systems in high-stakes environments.
Summary updated