Abstract
Goal Recognition Design (GRD) aims to modify environments to reveal an agent's intentions as early as possible. While traditional models assume optimal agent behavior, real-world interactions often involve stochasticity and suboptimality. This paper presents Suboptimal Stochastic Goal Recognition Design (SS-GRD), a framework that accounts for boundedly rational agents. By utilizing Policy-Aware Augmented MDPs and decoupling agent-observer costs, the authors provide an efficient method for reducing goal ambiguity. Evaluations across multiple planning domains demonstrate the framework's effectiveness and scalability.
Introduction
Goal Recognition Design (GRD) is the "inverse" of goal recognition: instead of merely guessing an agent's goal, we proactively modify the environment to force the agent to reveal its intentions sooner. This is critical in human-AI collaboration, where early intent detection allows for better support or safer interventions. However, most existing work assumes agents are perfect optimizers. In practice, agents are often suboptimal due to limited computation, noisy sensors, or imperfect models.
The Challenge of Suboptimality
In stochastic environments with suboptimal agents, the number of possible trajectories grows exponentially. A key metric in GRD is worst-case distinctiveness (wcd), representing the maximum cost an agent can incur before its goal becomes clear. When agents can take suboptimal steps, they might enter loops or follow "weird" paths that confuse standard observers. The challenge lies in calculating $wcd$ efficiently while accounting for these "boundedly rational" behaviors.
Methodology: Policy-Aware Augmented MDPs
The authors introduce Suboptimal Stochastic Goal Recognition Design (SS-GRD) to handle these complexities through several key innovations:
- Bounded Suboptimality ($u$): Agents are allowed up to $u$ suboptimal actions, capturing realistic errors without allowing for infinite, non-goal-oriented loops.
- Policy-Aware Augmented MDPs: Standard models track possible goals. SS-GRD instead tracks Policy IDs. By augmenting the state space with these IDs, the observer can monitor which specific legal policies the agent might be following at any given state.
- Cost Decoupling: The framework separates the agent's cost (e.g., energy) from the observer's cost (e.g., time), allowing for more flexible recognition objectives.
Optimized Design Search
To find the best environment modifications (such as removing actions or refining sensors), the authors use a max-priority queue and pruning techniques. This approach avoids redundant calculations by only re-evaluating policies affected by a specific modification, leading to significant performance improvements.
Experimental Results
The framework was evaluated on five planning domains: GRID-NAVIGATION, ROOM, BLOCKSWORLD, BOXWORLD, and ATTACK-PLANNING.
- Scalability: The optimized algorithms achieved speedups of up to six orders of magnitude compared to naive approaches.
- Effectiveness: Small modifications (budget $k=1$ to $3$) significantly reduced $wcd$ in the majority of test cases.
- Robustness: Accounting for suboptimality ($u > 0$) makes the resulting designs more "forgiving" and effective in real-world scenarios where agents are not perfect.
Conclusion
SS-GRD addresses a vital gap in goal recognition by incorporating agent suboptimality and environmental stochasticity. While high branching factors remain a challenge for exact methods, the use of Policy-Aware Augmented MDPs provides a robust and scalable path forward for designing environments that are easier for AI systems to understand.
Summary updated