Plan Recognition Design

Reuth Mirsky, Roni Stern, Ya'akov (Kobi) Gal, Meir KalechAAAI 2017 · DOI

Abstract

This paper introduces Plan Recognition Design (PRD), a framework for modifying a domain’s rules to make an agent’s intended plan easier to identify. By introducing a new metric called worst-case plan distinctiveness (wcpd), the authors provide a way to quantify and minimize the ambiguity of agent behavior in complex, hierarchical environments.

Introduction

In the field of Artificial Intelligence, Goal Recognition (GR) focuses on identifying an agent's ultimate objective. Previous research into Goal Recognition Design (GRD) explored how to structure environments to facilitate rapid goal identification. However, many real-world scenarios require understanding the "how" (the plan) rather than just the "what" (the goal). Plan Recognition is significantly more complex as it involves identifying a hierarchy of actions and sub-tasks.

Plan Recognition Design (PRD) addresses this by asking: how can we design a domain's plan library—the set of allowable rules—so that an observer can distinguish between different plans with the fewest possible observations?

Methods

The authors formalize PRD by building on standard plan library definitions where activities are represented as hierarchies of basic (observable) and complex (abstract) actions.

Worst-Case Plan Distinctiveness (wcpd)

The core metric introduced is the worst-case plan distinctiveness (wcpd). While the wcd metric in GRD measures the longest sequence of actions before a goal is clear, wcpd measures the longest sequence before the entire hierarchical plan becomes clear. Identifying a plan is inherently more ambiguous than identifying a goal because multiple plans may share initial steps and lead to the same goal.

Optimization via Rule Removal

To optimize a domain, the authors propose an anytime search algorithm that removes specific rules from the plan library to reduce wcpd without making any goals unreachable. The algorithm iteratively tests the removal of single rules, then combinations of rules, stopping when no further reductions are possible or when wcpd reaches zero (perfect clarity).

Results

The PRD approach was evaluated on three domains: Monroe (disaster management), Soccer (tactical plays), and a Simulated synthetic domain.

Table 1: Reduction of worst-case plan distinctiveness (wcpd) and associated computation times across three domains.

As shown in Table 1, the effectiveness of rule removal varied significantly by domain complexity:

  • Soccer: The wcpd was reduced by 50% (from 2 to 1) by removing a single rule, representing the maximum possible reduction for that domain.
  • Simulated: The algorithm achieved a 90% reduction in ambiguity, bringing wcpd from 0.82 down to 0.07.
  • Monroe: This highly flexible domain proved resistant to simple rule removal. Removing up to four rules simultaneously failed to reduce wcpd, highlighting the challenges of high-flexibility domains where exhaustive search is computationally infeasible due to the massive number of possible rule combinations.

Discussion and Future Work

The study reveals a clear trade-off between domain flexibility and observability. Strategic removal of redundant rules can force agents into distinctive patterns, but this "restrictive" manipulation may be too heavy-handed for some applications.

Future research directions include:

  • Less Restrictive Interventions: Exploring ordering constraints (e.g., requiring action A before B) instead of outright banning actions.
  • Computational Heuristics: Developing smarter shortcuts for rule selection to handle the exponential search space in complex domains like Monroe.
  • Robustness to Noise: Adapting the wcpd calculation for real-world scenarios where sensor data may be imperfect or noisy.

Summary updated

BibTeX
@inproceedings{mirsky2017plan,
  author = {Reuth Mirsky and Roni Stern and Ya'akov (Kobi) Gal and Meir Kalech},
  title = {{Plan Recognition Design}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11092},
}
Figure