Utility Maximization in Oversubscription Planning

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 225 papers35 conceptsfrozen 2026-10-04

In classical AI planning, success is binary: an agent either achieves all its goals or it fails. However, real-world agents—from Mars rovers to satellite constellations—rarely have the luxury of infinite resources. When the list of desired objectives exceeds the available time, fuel, or battery life, the problem shifts from reachability to Oversubscription Planning (OSP). The goal is no longer to find any path to a complete state, but to select the most valuable subset of goals that can be achieved within a fixed budget.

From Binary Goals to Utility Models

The transition away from "all-or-nothing" planning began with the realization that goals have varying importance. Mike Williamson and Steve Hanks introduced the PYRRHUS planner to handle decision-theoretic utility models, where plans are evaluated by balancing goal value against resource costs and deadlines Utility-Directed Planning.

This framing changes the fundamental search objective. Instead of stopping at the first valid plan, the system must search for an optimal plan. As Sriram Gopalakrishnan and colleagues demonstrate in the context of travel planning, this involves treating objectives as "soft goals" with associated utility scores, allowing an automated solver to identify the sequence of actions that maximizes total reward within a strict temporal budget TRIP-PAL.

The Computational Bottleneck: Planning as Knapsack

Why is oversubscription planning harder than classical planning? Michael Katz and Vitaly Mirkis identify the core difficulty: OSP inherently embeds the Knapsack problem In Search of Tractability for Partial Satisfaction Planning.

In classical planning, the challenge is the "state space explosion." In OSP, you add a second layer of complexity: selecting which items (goals) to put in your "knapsack" (resource budget). Even if the goals are entirely independent, deciding the optimal subset is weakly NP-complete. This relationship explains why simple heuristics often fail and why specialized algorithms are required to navigate the trade-off between goal value and action cost.

Search Strategies for Resource Bounds

To manage this complexity, researchers have developed specialized search techniques that prioritize high-utility frontiers:

Strategic Abandonment and Open Worlds

In dynamic or uncertain environments, the optimal subset of goals might change mid-execution. Sylvain Labranche and Eric Beaudry introduced the concept of Abort Actions. By making the decision to give up on a goal an explicit part of the plan, the agent can strategically reallocate resources when it realizes a specific objective is no longer worth the time Partial Satisfaction Planning under Time Uncertainty.

This is particularly vital in "open-world" robotics. Kartik Talamadupula and colleagues demonstrated how robots can use partial satisfaction planning to handle opportunistic goals—like discovering a new victim during a search-and-rescue mission—and decide on the fly if the new goal's reward justifies the deviation from the existing plan Integrating a Closed World Planner with an Open World Robot.

Scaling to Real-World Missions

The most extreme examples of oversubscription occur in satellite scheduling, where thousands of requests compete for limited orbital windows. Guillaume Infantes and his team have moved toward learning-based approaches, using Graph Neural Networks (GNNs) to represent the complex dependencies between observation requests. Their system learns to identify high-utility scheduling patterns that generalize far beyond the capacity of traditional greedy heuristics Earth Observation Satellite Scheduling with Graph Neural Networks.

By shifting the focus from "completing the task" to "maximizing the value of the mission," this research direction provides the mathematical and algorithmic tools necessary for autonomous systems to operate effectively in resource-scarce environments.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 20 papers
  2. Version 1 · 2026-10-04 · 25 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_resource_constrained_goal_selection_73be4391,
  title = {resource-constrained goal selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/resource-constrained-goal-selection/rdr_73be43913397485db371b46ca7c3451b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_utility_maximization_in_oversubscription_73be4391_v1,
  title = {Utility Maximization in Oversubscription Planning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/utility-maximization-in-oversubscription-planning/rdr_73be43913397485db371b46ca7c3451b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}