Partial Satisfaction Planning under Time Uncertainty with Control on When Objectives Can Be Aborted

Sylvain Labranche, Eric BeaudryAAAI 2014 · DOI

Introduction

In classical AI planning, goals are typically treated as binary: they are either achieved in full, or the plan is considered a failure. However, real-world autonomous systems—such as planetary rovers or logistics drones—frequently operate in "over-subscription" environments where resources and time are insufficient to meet every objective. This is known as Partial Satisfaction Planning (PSP). The complexity of PSP is compounded by temporal uncertainty, where unexpected delays (e.g., a rover getting stuck in sand) can render a previously optimal plan impossible.

This paper introduces a novel approach to PSP under time uncertainty by formalizing the decision to abandon a goal as an explicit "Abort Action." By incorporating these actions with specific deadlines into a temporal planner, the authors provide a mechanism for systems to reason about the "point of no return" for any given objective.

The Abort Action Framework

The authors build upon ActuPlan, a planner that utilizes Bayesian networks to represent continuous time distributions rather than discrete steps. The core innovation lies in treating the abandonment of a soft goal ($g_i$) as a first-class planning action, $Abort(g_i)$.

Key components of this framework include:

  • Utility-Based Costing: The cost of an abort action is set equal to the utility (value) of the goal being abandoned. If the planner chooses to abort, it incurs a penalty equivalent to the lost value, allowing standard heuristic search algorithms to evaluate the trade-off between pursuing a risky goal and pivoting to others.
  • Abort Deadlines: Each abort action is assigned a deadline. Once the execution time exceeds this deadline, the abort action is no longer available. This forces the planner to "commit" to a goal; after the deadline, the soft goal effectively becomes a hard goal that must be completed.
  • Conditional Branching: Rather than a linear sequence, the planner generates a conditional tree. At specific branching points, the system decides whether to continue a task or trigger an abort action based on the elapsed time and the probability of successful completion within the remaining window.

Insights into Commitment and Information

A significant finding of this research is that the value of abort deadlines extends beyond simple optimization. While adding deadlines does not always significantly lower the "expected cost" of a plan, it provides critical information regarding the window of opportunity. It defines the maximum time a controller has to change its mind, which is often more valuable for system reliability and human oversight than a marginal increase in path efficiency.

Experimental Evaluation

The approach was evaluated using synthetic problems within the ActuPlan environment, scaling from small to large state spaces to test performance and scalability.

Performance and Scalability

  • Computational Overhead: For smaller problems, the inclusion of abort deadlines resulted in negligible CPU overhead. However, as the number of goals ($|G|$) increased, the state space expanded significantly. Each goal adds new state variables, leading to a "state space explosion" that impacts scalability for complex, many-goal scenarios.
  • Plan Stability: The experiments confirmed that the planner successfully "hardens" goals. Once a deadline passes, the search space is pruned of abortion options, ensuring the system focuses entirely on the committed task and ignores the now-impossible alternative of quitting.

Limitations and Future Work

The primary limitation identified is scalability. The current heuristic search techniques struggle with the increased state-space complexity introduced by adding $|G|$ variables for abort actions. Future research will focus on improving search heuristics and pruning strategies to handle larger problem sets.

Additionally, the authors propose applying this framework to competitive environments, such as modeling Non-Playable Brokers (NPBs) in real estate simulations. In such contexts, the strategic decision to "abort" a deal to pursue a more lucrative one is a central component of realistic agent behavior.

Summary updated

BibTeX
@inproceedings{labranche2014partial,
  author = {Sylvain Labranche and Eric Beaudry},
  title = {{Partial Satisfaction Planning under Time Uncertainty with Control on When Objectives Can Be Aborted}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9088},
}
Figure