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.
As shown in Table 1, the effectiveness of rule removal varied significantly by domain complexity:
- Soccer: The
wcpdwas 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
wcpdfrom 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
wcpdcalculation for real-world scenarios where sensor data may be imperfect or noisy.
Summary updated