SLIM: Semi-Lazy Inference Mechanism for Plan Recognition

Reuth Mirsky, Ya'akov (Kobi) GalIJCAI 2016

Abstract

Plan recognition is a computationally intensive task that involves inferring an agent's hierarchical plan from observed actions. Traditional approaches often suffer from combinatorial explosion as the number of observations increases. We present the Semi-Lazy Inference Mechanism (SLIM), a hybrid algorithm that optimizes plan recognition by focusing on local action fragments and deferring complete hierarchical construction. Empirical results demonstrate that SLIM significantly reduces computational load and runtime compared to state-of-the-art methods like PHATT.

Introduction

Understanding not just the goal of an agent but the specific hierarchical steps they are taking is critical for applications ranging from cybersecurity to medical assistance. However, plan recognition is notoriously difficult. Unlike goal recognition, which identifies a final state, plan recognition must reconstruct the entire task hierarchy. Existing methods, such as the Probabilistic Hostile Agent Task Tracker (PHATT), maintain exhaustive sets of complete plan trees, leading to scalability issues in complex domains as the number of possible future paths grows combinatorially.

The SLIM Approach

The Semi-Lazy Inference Mechanism (SLIM) addresses these challenges through a "semi-lazy" hybrid architecture that combines bottom-up and top-down parsing.

Bottom-Up Fragment Construction

SLIM begins with a bottom-up phase. Instead of building trees from the root goals down, it creates "fragments"—single-depth trees that explain how an observed action fits into immediate parent rules. These fragments are then fused based on temporal and ordering constraints defined in the plan library. This approach allows the system to maintain local clusters of behavior without committing to a global plan prematurely, following a "least commitment" policy.

Lazy Top-Down Inference

The "lazy" component of SLIM involves deferring the construction of the full hierarchy. The system only performs top-down inference to connect fused fragments to root goals when specifically queried. This ensures that the heavy lifting of full-tree construction is only performed when necessary, keeping the real-time observation phase efficient.

Experimental Evaluation

The performance of SLIM was evaluated using a standard benchmark domain based on AND/OR trees. The plan library consisted of 140 complex actions and 244 production rules. The researchers compared SLIM against PHATT across 100 instances, each involving a sequence of nine basic actions.

Results and Discussion

SLIM demonstrated a clear advantage in computational efficiency. As shown in the runtime analysis, SLIM variants consistently achieved lower average runtimes than PHATT. Specifically, at the final observation step, PHATT required an average of 9.48 seconds, while SLIM completed the task in 4.45 seconds.

Average runtime comparison between SLIM variants and PHATT.

The efficiency of SLIM stems from its ability to minimize the number of combinations considered. While SLIM may track a higher number of individual hypotheses (fragments), the number of ways these fragments can be legally combined is significantly lower than the combinations required to maintain full trees in PHATT. Empirical data shows that SLIM's "Possible Combinations" metric is an order of magnitude lower than PHATT's as the number of observations increases.

Comparison of possible combinations considered by PHATT and SLIM across increasing observations.

Conclusion

SLIM offers a scalable alternative for real-time plan recognition by prioritizing local inference and deferring global consistency checks. While it currently assumes a uniform distribution of goal probabilities, future work aims to transform SLIM into an anytime algorithm and integrate more sophisticated goal recognition to guide the top-down inference phase.

Summary updated

BibTeX
@inproceedings{mirsky2016slim,
  author = {Reuth Mirsky and Ya'akov (Kobi) Gal},
  title = {{SLIM: Semi-Lazy Inference Mechanism for Plan Recognition}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure