Block-Level Goal Recognition Design

Tsz-Chiu AuAAAI 2024 · DOI

Introduction

Goal Recognition Design (GRD) focuses on modifying an environment to reveal an agent's intentions as early as possible. A common metric in this field is Worst Case Distinctiveness (WCD), which represents the maximum number of steps an agent can take before its goal becomes uniquely identifiable. For example, in airport security, one might design corridors such that a person heading toward a restricted area is identified quickly.

Traditional GRD methods treat environmental modifications as atomic actions, such as removing a single transition between states. In complex, real-world scenarios, this approach leads to a combinatorial explosion of possible designs. Moreover, physical modifications are often "all-or-nothing"—installing a wall blocks a whole set of paths, not just one. This paper addresses these challenges by introducing a block-level hierarchical framework for GRD.

Methods: Blocks, Hierarchy, and Pruning

The proposed framework introduces three core innovations to improve the efficiency and realism of environment design:

Blocks and Regions

Instead of individual action removals, the authors define "blocks"—predefined sets of modifications that affect specific regions of the environment. This ensures that environmental constraints are respected by design, preventing the search algorithm from evaluating nonsensical or physically impossible combinations of atomic changes.

Example of a grid environment with predefined blocks $b_1, b_2, b_3$ representing sets of environmental modifications.

Hierarchical Design Models

Drawing inspiration from Hierarchical Task Network (HTN) planning, the framework organizes these blocks into a tree structure. High-level blocks represent broad structural decisions, while child blocks implement specific, localized design choices. This hierarchical organization transforms a massive, flat search space into a structured, manageable tree, allowing designers to "zoom in" on critical areas.

Advanced Pruning Rules

To further accelerate the search, two novel pruning rules are introduced:

  • Block-Based Pruned-Reduce: This rule skips modifications that do not directly interfere with the paths currently contributing to the highest WCD.
  • Design Subtree Pruning: This rule calculates lower and upper bounds for "Relative WCD" at various junctions. If a specific design branch is mathematically guaranteed to result in a higher WCD than a previously explored branch, the entire subtree is pruned.

Experimental Evaluation

The approach was tested on four classic domains from the International Planning Competition (IPC): LOGISTICS, DEPOTS, GRID, and DRIVERLOG. For each domain, 30 instances were generated with varying sizes and goal counts (typically 2 to 10 goals).

Key Results

The experiments compared a standard Breadth-First Search (BFS) using atomic modifications against the new block-level BFS and a fast local search variant.

Performance comparison between the original BFS, the proposed block-level BFS, and a local search heuristic across four domains.

The results demonstrate a significant performance leap:

  • Order-of-Magnitude Speedup: The block-level BFS consistently outperformed the original atomic BFS by roughly 10x. In the GRID domain, for instance, processing time was reduced from 37.64 seconds to just 3.24 seconds.
  • Optimality vs. Efficiency: While the block-level BFS always finds the optimal WCD, the "Local Search" heuristic offers even faster execution (under 0.5s) at the cost of occasional slight suboptimality.
  • Pruning Efficacy: Pruning rules were essential for these gains. While "Pruned-Reduce" provided the most significant speedup, "Design Subtree Pruning" offered additional benefits in complex layouts.

Conclusion and Future Work

By shifting from atomic modifications to a hierarchical, block-based approach, this research significantly reduces the computational burden of Goal Recognition Design. The use of abstraction not only improves efficiency but also aligns the design process with real-world physical constraints.

Future work will explore integrating this framework with HTN planners, handling partial observability where the observer cannot see every agent action, and incorporating "sensing actions" (e.g., camera placement) as part of the design space.

Summary updated

BibTeX
@inproceedings{au2024block,
  author = {Tsz-Chiu Au},
  title = {{Block-Level Goal Recognition Design}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.29979},
}
Figure