Stochastic Goal Recognition Design Problems with Suboptimal Agents

Christabel Wayllace, William Yeoh

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.

Figure 2: Goal Recognition Design in stochastic environments. (a) shows a base environment with goals $g_0$ and $g_1$. (b) illustrates how partial observability groups states into observation sets (e.g., $o1_{01}$), which can be modified to reduce ambiguity.

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:

  1. Bounded Suboptimality ($u$): Agents are allowed up to $u$ suboptimal actions, capturing realistic errors without allowing for infinite, non-goal-oriented loops.
  2. 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.
  3. 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.
Figure 5: The SS-GRD framework components. (a) The underlying MDP. (b) The set of possible proper policies. (c) The augmented MDP tree where nodes represent sets of active policies, enabling the observer to track the reduction of ambiguity.

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

Abstract

Goal Recognition Design (GRD) problems identify the minimum number of environmental modifications aiming to force an interacting agent to reveal its goal as early as possible. Researchers proposed several extensions to the original model, some of them handling stochastic agent action outcomes. While this generalization is useful, it assumes optimal acting agents, which limits its applicability to more realistic scenarios. This paper presents the Suboptimal Stochastic GRD model, where we consider boundedly rational agents that, due to limited resources, might follow a suboptimal policy. Inspired by theories on human behavior asserting that humans are (close to) optimal when making perceptual decisions, we assume the chosen policy has at most m suboptimal actions. Our contribution includes (I) Extending the stochastic goal recognition design framework by supporting suboptimal agents in cases where an observer has either full or partial observability; (ii) Presenting methods to evaluate the ambiguity of the model under these assumptions; and (iii) Evaluating our approach on a range of benchmark applications.
BibTeX
@inproceedings{wayllace2022stochastic,
  author = {Christabel Wayllace and William Yeoh},
  title = {{Stochastic Goal Recognition Design Problems with Suboptimal Agents}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21233},
}
Figure