Goal Recognition Design - Survey

Sarah Keren, Avigdor Gal, Erez KarpasIJCAI 2020 · OpenReview

Abstract

Goal recognition is the task of recognizing the objective of agents based on online observations of their behavior. Goal recognition design (GRD), the focus of this survey, facilitates goal recognition by the analysis and redesign of goal recognition models. In a nutshell, given a model of a domain and a set of possible goals, a solution to a GRD problem determines: (1) to what extent do actions performed by an agent reveal the agent’s objective? and (2) what is the best way to modify the model so that the objective of an agent can be detected as early as possible? GRD answers these questions by offering a solution for assessing and minimizing the maximal progress of any agent before recognition is guaranteed. This approach is relevant to any domain in which efficient goal recognition is essential and in which the model can be redesigned. Applications include intrusion detection, assisted cognition, computer games, and human-robot collaboration. This survey presents the solutions developed for evaluation and optimization in the GRD context, a discussion on the use of GRD in a variety of real-world applications, and suggestions of possible future avenues of GRD research.

Introduction

Traditional Goal Recognition (GR) is inherently passive. An observer monitors an agent's actions and attempts to infer their destination or objective. However, many environments are ambiguous; an agent might take several steps that are optimal for multiple goals, leaving the observer uncertain until the agent is very close to their target.

Goal Recognition Design (GRD) shifts this paradigm by treating the environment itself as a design variable. Instead of merely observing, GRD asks how the environment can be modified so that an agent's actions reveal their intent as early as possible. This is particularly vital in high-stakes scenarios like intrusion detection, where early recognition is the difference between prevention and failure.

The GRD Framework

The core metric of GRD is Worst Case Distinctiveness (WCD). WCD measures the maximum progress (or cost) an agent can make toward a goal before their specific target becomes clear to the observer. An environment with a high WCD is "opaque," while a WCD of 0 implies that the very first action reveals the agent's goal.

Illustration of a GRD scenario and its corresponding model. (a) and (c) show the original environment and grid model where multiple paths are ambiguous. (b) and (d) show how adding a physical obstacle (a fountain) or a logical barrier reduces ambiguity, forcing earlier goal revelation.

The GRD process involves two primary stages:

  1. Evaluation: Assessing the current WCD of a model.
  2. Optimization: Searching for the most effective modifications—such as removing an action, adding a sensor, or placing a physical barrier—to minimize WCD within a specific "design budget" while ensuring the agent can still reach their goals.

Computational Approaches and Taxonomy

Researchers employ several techniques to solve the design problem:

  • Planning-based search: Treating design as a state-space search where each step is an environment modification.
  • Answer Set Programming (ASP): Utilizing logic-based solvers, which have shown superior performance for fully observable models with optimal agents.
  • Information Shaping: Influencing agent behavior by selectively revealing information.

The survey categorizes models based on their complexity, moving from deterministic environments to Stochastic GRD (S-GRD), which accounts for real-world uncertainty where actions might fail or agents might take sub-optimal paths.

Key Insights and Results

The most significant shift in GRD is viewing system rules and maps as tools for transparency rather than fixed constraints. Early work demonstrated that simple modifications could reduce WCD from several steps to zero without increasing the agent's travel cost. Furthermore, the field has expanded to include "privacy-preserving" actors who actively hide their goals, leading to game-theoretic formulations.

Recent advancements have also successfully applied GRD to sensor placement, determining the optimal locations for sensors in partially observable settings to maximize information gain.

Limitations and Future Directions

Despite its potential, GRD faces several challenges:

  • Computational Complexity: The search space for environment modifications grows exponentially with model realism (stochasticity, multi-agent systems).
  • Utility Trade-offs: There is a tension between making an environment transparent for recognition and maintaining its efficiency or comfort for the user.
  • Online Design: Most current research focuses on "offline" design. A major future direction is "online" GRD, where the environment is modified in real-time based on agent movement.
  • Human Factors: Incorporating complex human behavioral models beyond simple rationality remains a significant hurdle for practical deployment.

Summary updated

Abstract

Goal recognition is the task of recognizing the objective of agents based on online observations of their behavior. Goal recognition design (GRD), the focus of this survey, facilitates goal recognition by the analysis and redesign of goal recognition models. In a nutshell, given a model of a domain and a set of possible goals, a solution to a GRD problem determines: (1) to what extent do actions performed by an agent reveal the agent’s objective? and (2) what is the best way to modify the model so that the objective of an agent can be detected as early as possible? GRD answers these questions by offering a solution for assessing and minimizing the maximal progress of any agent before recognition is guaranteed. This approach is relevant to any domain in which efficient goal recognition is essential and in which the model can be redesigned. Applications include intrusion detection, assisted cognition, computer games, and human-robot collaboration. This survey presents the solutions developed for evaluation and optimization in the GRD context, a discussion on the use of GRD in a variety of real-world applications, and suggestions of possible future avenues of GRD research.
BibTeX
@inproceedings{keren2020goal,
  author = {Sarah Keren and Avigdor Gal and Erez Karpas},
  title = {{Goal Recognition Design - Survey}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=VGooBaNJYl2},
}
Figure