Recognizing Plan/Goal Abandonment

Christopher W. Geib, Robert P. GoldmanIJCAI 2003

Introduction

In the field of plan recognition, systems aim to infer an agent's goals by observing their actions. Traditionally, these systems operate under the assumption of goal persistence—the idea that once an agent begins a plan, they will inevitably see it through to completion. However, real-world agents frequently change their minds, encounter obstacles, or simply lose interest. This paper addresses the critical need for systems to recognize when a goal has been abandoned, treating it as an operational requirement for real-time, continuous environments.

The Problem of "Zombie" Plans

Failing to account for abandonment leads to two primary failures in plan recognition systems:

  1. Computational Bloat: Systems accumulate a growing list of "open plans," consuming memory and processing power to track goals the agent is no longer pursuing.
  2. Logical Absurdity: Without a mechanism to prune dead hypotheses, a system might expect the second step of a brief task to occur weeks after the first step was observed, leading to nonsensical inferences.

To solve this, the authors propose a method to detect abandonment as a signal, effectively pruning "zombie" plans from the inference process.

Probabilistic Model Revision

The authors introduce a solution based on Probabilistic Model Revision. Rather than explicitly modeling abandonment as a state in a complex Hidden Markov Model—which would lead to exponential complexity—they monitor the mismatch between the agent's actions and the expected plan.

Key Concepts

  • The Pending Set: The set of all possible next actions an agent could take to satisfy their current goals.
  • The $notContrib$ Statistic: A novel metric that calculates the probability that a sequence of observations does not contribute to a specific goal ($G$).
  • Probability of Abandonment Threshold (PAT): A threshold used to trigger model revision. If the probability that an agent is still pursuing goal $G$ falls below the PAT, the system assumes abandonment and removes all associated pending actions.
Probability of goal validity over time for varying pending set sizes.

As shown in Figure 3, the strength of evidence for abandonment is intrinsically linked to the size of the pending set. If an agent has only a few possible actions (e.g., a "1 of 2" pending set) and performs something else, the probability of the goal's validity drops rapidly. Conversely, a larger pending set requires more observations to reach the same level of certainty.

Experimental Evaluation

The theory was tested using synthetic data generated for the PHATT (Probabilistic Hostile Agent Task Tracker) algorithm. The researchers used a plan library with three root goals, each containing eight unordered steps. They generated 1,000 test cases where actions were interleaved and goals were abandoned at random intervals, removing subsequent steps from the observation stream.

Results and the "Sweet Spot"

The empirical evaluation revealed a clear trade-off in setting the PAT. If the threshold is too low, the system is overly aggressive, pruning goals that are still active and leaving future actions "unexplained." If the threshold is too high, the system fails to recognize abandonment in a timely manner.

System performance metrics across different Probability of Abandonment Thresholds (PAT).

As illustrated in Figure 4, the system achieved a peak accuracy of approximately 75% when the PAT was set between 0.6 and 0.7. Beyond this range, performance degraded either due to premature pruning (at low PAT) or insufficient evidence for abandonment within the observation window (at high PAT).

Conclusion and Future Work

Recognizing abandonment allows plan recognition systems to remain efficient and logically consistent over long periods. While the current model assumes uniform probability for pending actions, future work could incorporate prior probabilities to refine the $notContrib$ calculation. Additionally, longer observation windows in real-world scenarios may allow for higher, more conservative thresholds to perform even better.

Summary updated

BibTeX
@inproceedings{geib2003recognizing,
  author = {Christopher W. Geib and Robert P. Goldman},
  title = {{Recognizing Plan/Goal Abandonment}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure