Classical automated planning operates under an all-or-nothing paradigm: an agent is given a set of mandatory goals and must find a valid sequence of actions to achieve all of them at minimum cost. However, real-world autonomous systems—such as planetary rovers, orbital satellites, and tactical robots—frequently operate in oversubscribed environments. They face far more potential objectives than their limited time, fuel, or energy budgets allow them to satisfy.
To handle these scenarios, researchers developed Oversubscription Planning (OSP) and Partial Satisfaction Planning (PSP). Instead of treating goals as hard constraints, these frameworks assign a utility or reward to each goal. The planning problem then shifts from simple pathfinding to a joint optimization challenge: selecting the most valuable subset of goals to pursue while ensuring the execution cost remains strictly within a fixed resource budget.
The Core Difficulty: Coupling Pathfinding with Resource Allocation
To understand why OSP is challenging, it helps to look at its mathematical structure. If we strip away the planning aspect and assume all goals can be achieved independently with a known cost and reward, selecting the optimal subset of goals is exactly the Knapsack problem.
As Katz et al. demonstrate, this relationship means that OSP is inherently weakly NP-complete even under the simplest possible structural conditions (such as completely independent binary variables). However, real planning domains are rarely independent. Achieving Goal A might move the agent closer to Goal B but further from Goal C, dynamically altering the remaining costs of subsequent goals.
This creates a tight coupling between action sequencing (pathfinding) and goal selection (resource allocation). This complexity differentiates OSP from another common paradigm known as Net-Benefit Planning. As explored by van den Briel et al., net-benefit planning simply maximizes total utility minus total action cost without a hard ceiling. Katz et al. show that OSP is fundamentally more difficult than net-benefit planning because a hard budget constraint prevents the planner from making purely local trade-offs; it must track global resource depletion across the entire execution path.
Algorithmic Strategies: How to Search with a Budget
Because standard heuristic search algorithms assume a fixed target state, they struggle with OSP where the target state is an optimal combination of optional goals. Researchers have developed several distinct paradigms to make budget-constrained search tractable.
Bound-Sensitive Heuristics
Traditional $A^*$ search evaluates states based on the cost incurred so far ($g$) and an estimate of the remaining cost to the goal ($h$). In OSP, this logic must be inverted to track accumulated utility and remaining budget. Katz et al. reformulated OSP into a multi-cost classical planning framework and introduced bound-sensitive heuristics. These heuristics explicitly incorporate the remaining resource budget into their look-ahead estimates, allowing the search algorithm to prune paths that can no longer afford high-value goals early in the process.
Symbolic Search and BDDs
When resource budgets are large, explicit state-space search suffers from an exponential explosion of states that differ only slightly in their remaining budget. To circumvent this, Speck et al. introduced SYM-OSP, a framework that applies symbolic search to OSP. By utilizing Binary Decision Diagrams (BDDs), the planner can represent and evaluate entire sets of states simultaneously. This compact representation allows the system to scale efficiently in complex environments with generous cost bounds where explicit search methods stall.
Classical Compilation
Instead of inventing entirely new planners, can we leverage decades of optimization in classical planning? Aghighi et al. proved that OSP tasks can be compiled directly into standard classical planning problems. They achieved this by embedding a binary counter into the planning state variables to track resource consumption. This theoretical bridge allows off-the-shelf classical planners to solve oversubscription problems without modifying their underlying search engines.
Frontier and Incremental Search
When a planner discovers new information mid-search (such as a landmark that must be passed), restarting the search from scratch is computationally wasteful. Muller addressed this by developing a progressive frontier search for OSP. This technique compiles the search history into a reusable "frontier," allowing the planner to incrementally reconstruct plans and incorporate new constraints without abandoning prior computational effort.
Managing Uncertainty, Hierarchies, and Real-Time Dynamics
As OSP moved from theoretical models to real-world deployment, researchers had to account for concurrent actions, stochastic environments, and massive state spaces.
Early foundational work like the PYRRHUS planner by Williamson et al. established decision-theoretic utility models to balance soft deadlines and resource costs. To handle concurrent and uncertain environments, Li et al. introduced CPOAO, an algorithm designed for probabilistic, oversubscribed domains. CPOAO leverages parallel action execution to increase the probability of plan success, while strategically aborting redundant or failing actions mid-flight to conserve the remaining resource budget.
To scale to large-scale industrial problems, researchers often impose hierarchical structures:
- Hierarchical MDPs: Meuleau et al. introduced HiAO*, which partitions massive stochastic state spaces into smaller sub-problems and uses "macro-connectors" to bypass intermediate states, enabling rapid forward search under resource constraints.
- Hierarchical Task Networks (HTNs): Katz et al. extended total-order HTN planning to support partial satisfaction, allowing domain experts to encode procedural knowledge while letting the planner optimize goal selection within a strict cost bound.
In fast-paced, dynamic environments like real-time strategy games, static utility models fail. Young et al. demonstrated that agents can manage oversubscribed task queues by using genetic algorithms to evolve "Priority Profiles." By dynamically switching between these profiles based on the current game state, the agent can continuously re-prioritize its goals as resources fluctuate.
Real-World Applications
Oversubscription planning provides the mathematical foundation for several complex engineering domains:
- Earth Observation Satellites: Satellites orbit the Earth with strict mechanical, thermal, and orbital windows, yet they receive far more imaging requests than they can physically execute. Infantes et al. combined Graph Neural Networks (GNNs) with Deep Reinforcement Learning to learn scheduling policies that maximize observation utility within these rigid physical constraints.
- Open-World Robotics: In disaster response scenarios, a robot cannot know all objectives in advance. Talamadupula et al. integrated partial satisfaction planning with real-time execution monitoring. This allows a robot to discover new tasks opportunistically (e.g., finding a new survivor) and evaluate on the fly whether the reward justifies the battery and time expenditure.
- Queue Admission Control: Service systems often face incoming task volumes that exceed processing capacity. Rigter et al. designed scalable admission control policies using Markov Decision Processes and state abstractions to maximize the total value of processed tasks under time-varying arrival rates.
- Processor Speed-Scaling: In mobile and battery-powered computing, Angel et al. developed theoretical approximation algorithms to maximize weighted task throughput on multiprocessor systems operating under a hard energy budget.
Explaining the Sacrifices
Because OSP solvers must deliberately omit certain goals to remain within budget, their outputs can be counterintuitive to human operators. If a planner drops a high-value goal, users require a clear justification.
To provide transparency, Eifler et al. introduced a formal framework based on plan-property entailments. Instead of merely presenting an alternative plan, their system generates structural explanations of the trade-offs, such as: "Achieving Goal X mathematically forces the sacrifice of at least one goal from set B due to fuel constraints."
When a problem is completely overconstrained and no feasible plan exists, simply returning an error leaves operators at a dead end. To resolve this, l'Hermite et al. proposed a counterfactual explanation approach. Their method identifies the minimal, localized changes required to make a plan feasible—such as slightly relaxing a coverage requirement or marginally increasing the budget—turning an optimization failure into an actionable roadmap for human negotiation.
Key Foundational Work
Effective Approaches for Partial Satisfaction (Over-Subscription) Planning (2004) — contributed 1 concept elements to this direction.
Utility-Directed Planning (1994) — contributed 1 concept elements to this direction.