Goal Recognition Design in Deterministic Environments

Sarah Keren, Avigdor Gal, Erez KarpasJAIR 2019 · OpenReview

TL;DR

This paper introduces "Goal Recognition Design" (GRD), a framework for optimizing how well an agent's goals can be identified by analyzing and modifying the environment. They propose a new metric, "Worst Case Distinctiveness" (WCD), to measure how long an agent can act before its goal is revealed, and develop efficient methods to minimize WCD through model redesign.

What Problem Does This Paper Address?

In many applications, from autonomous systems to security, it's crucial to quickly understand what an agent is trying to achieve. Traditional goal recognition focuses on inferring goals from observed actions. However, this paper tackles a related but distinct problem: how to design the environment itself to make goal recognition faster and more reliable. The challenge is that environments are often not designed with recognition in mind, leading to ambiguous actions that could serve multiple goals, thus delaying recognition. The authors aim to provide a systematic way to analyze and modify these environments to ensure an agent's goal is detected as early as possible, especially in deterministic settings.

Methods

The core of the paper lies in two main contributions:

  1. Worst Case Distinctiveness (WCD) Measure: They introduce WCD as a metric for evaluating a goal recognition model. WCD quantifies the maximum "cost" (e.g., number of steps or actions) an agent can take along a non-distinctive path before its goal is unambiguously identifiable. A non-distinctive path is one whose observed actions could lead to multiple goals.
  2. Goal Recognition Design (GRD) Framework: They formalize GRD as a search problem in the space of possible modifications to a goal recognition model. This involves:
  3. Evaluation: Calculating WCD for a given model. They propose novel compilations to classical planning for efficient WCD calculation, especially for bounded-suboptimal agents.
  4. Optimization (Redesign): Searching for a sequence of modifications (e.g., adding barriers, changing sensor models) that minimizes WCD. They introduce a pruned-search algorithm that intelligently explores modification sequences, avoiding those unlikely to improve WCD. They also define conditions under which this pruning is guaranteed to find an optimal solution.

Datasets

The authors evaluate their methods on several benchmark domains adapted from existing planning competitions:

  • Ramirez and Geffner (2009): GRID-NAVIGATION (GRID), IPC-GRID+ (GRID+), BLOCK-WORDS (BLOCK), LOGISTICS (LOG).
  • Pereira et al. (2017): Intrusion Detection (I-DET), Depots (DEP), Campus (CAM).
  • E-Martín et al. (2015): ISS-CAD (ISS) domain, which features non-uniform action costs.

They created various observability settings (Fully Observable, Non-Observable, Partially Observable Deterministic, Partially Observable Non-Deterministic) for these domains to test their framework under different conditions.

Key Insights and Ideas

  • Designing for Recognition: The paper shifts focus from just recognizing goals to actively designing environments that facilitate recognition. This is crucial for applications where timely goal identification is paramount.
  • WCD as a Unified Metric: WCD provides a principled way to quantify how "ambiguous" an environment is from a goal recognition perspective, allowing for systematic optimization.
  • Pruning for Efficiency: The proposed pruning strategy in the redesign process significantly reduces the search space, making it feasible to find optimal modifications even in complex scenarios. This is achieved by identifying modifications that are unlikely to affect the WCD value.
  • The Power of Modifications: Simple modifications like adding barriers (action conditioning) or improving sensor resolution can drastically reduce WCD, sometimes to zero, highlighting the practical impact of GRD.

Key Results

  • Efficient WCD Calculation: Their compilation-based methods for calculating WCD are shown to be efficient, outperforming baseline approaches. For example, the common-declare compilation handles various observability settings effectively.
  • Effective WCD Reduction: The redesign process, particularly using the pruned-reduce algorithm, demonstrates significant WCD reduction across various domains and observability settings. For instance, in the fully observable setting of Example 1, WCD was reduced from 4 to 0 by placing a single barrier.
  • Pruning Benefits: The pruned-reduce algorithm significantly outperforms the exhaustive-reduce approach in terms of the number of nodes expanded, especially in domains with large branching factors. This efficiency gain is crucial for practical applications.
  • Impact of Observability and Suboptimality: The results confirm that WCD generally increases with reduced observability and with agents exhibiting bounded-suboptimal behavior, underscoring the importance of considering these factors in GRD.

Limitations and Future Work

  • Deterministic Environments: The current framework is primarily designed for deterministic environments. Extending it to handle stochastic actions or outcomes would be a significant future direction.
  • Agent Knowledge: The current model assumes agents have perfect observability of the environment. Accounting for agents with partial information is identified as a promising area for future work.
  • Design Process Enhancements: The authors suggest exploring combinations of different search space reduction techniques and heuristics to further improve efficiency. They also propose investigating approximate solutions for real-world applications where optimality might be less critical than speed.
  • Modification Types: While the paper focuses on action conditioning and sensor refinement, exploring other types of modifications (e.g., changing initial states, goal positions) could expand the framework's applicability.
  • Real-World Applications: Applying the GRD framework to various real-world scenarios is suggested to demonstrate its practical utility.

Summary updated

Abstract

Goal recognition design (GRD) facilitates understanding the goals of acting agents through the analysis and redesign of goal recognition models, thus offering a solution for assessing and minimizing the maximal progress of any agent in the model before goal recognition is guaranteed. In a nutshell, given a model of a domain and a set of possible goals, a solution to a GRD problem determines (1) the extent to which actions performed by an agent within the model reveal the agent’s objective; and (2) how best to modify the model so that the objective of an agent can be detected as early as possible. This approach is relevant to any domain in which rapid goal recognition is essential and the model design can be controlled. Applications include intrusion detection, assisted cognition, computer games, and human-robot collaboration. A GRD problem has two components: the analyzed goal recognition setting, and a design model specifying the possible ways the environment in which agents act can be modified so as to facilitate recognition. This work formulates a general framework for GRD in deterministic and partially observable environments, and offers a toolbox of solutions for evaluating and optimizing model quality for various settings. For the purpose of evaluation we suggest the worst case distinctiveness (WCD) measure, which represents the maximal cost of a path an agent may follow before its goal can be inferred by a goal recognition system. We offer novel compilations to classical planning for calculating WCD in settings where agents are bounded-suboptimal. We then suggest methods for minimizing WCD by searching for an optimal redesign strategy within the space of possible modifications, and using pruning to increase efficiency. We support our approach with an empirical evaluation that measures WCD in a variety of GRD settings and tests the efficiency of our compilation-based methods for computing it. We also examine the effectiveness of reducing WCD via redesign and the performance gain brought about by our proposed pruning strategy.
BibTeX
@article{keren2019goal,
  author = {Sarah Keren and Avigdor Gal and Erez Karpas},
  title = {{Goal Recognition Design in Deterministic Environments}},
  journal = {J. Artif. Intell. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=qgeB-TFo54Z},
}
Figure