The Generalized A* Architecture

Pedro F. Felzenszwalb, David A. McAllester

TL;DR

This paper introduces a generalized A search architecture for "lightest derivation problems," which encompass a broad range of AI inference tasks. The authors present a novel hierarchical search algorithm (HALD) that leverages abstractions to efficiently solve complex problems, particularly in perceptual pipelines, by integrating multiple processing stages into a single global optimization.

What Problem Does This Paper Address?

Many AI problems, especially in perception, involve a pipeline of processing stages where information flows sequentially. Traditionally, each stage makes hard decisions, leading to suboptimal global solutions. The authors identify the "pipeline problem" as the challenge of integrating these stages into a single, globally optimized system. They frame this as "lightest derivation problems," where the goal is to find the minimum-cost way to derive a global structure from weighted rules. This is a generalization of classical AI search problems and can be applied to tasks like parsing, object recognition, and curve detection. Existing methods often struggle with the complexity of these problems, especially when dealing with cyclic rules or large state spaces.

Methods

The core contribution is the Generalized A* Architecture, which extends A* search to lightest derivation problems. This involves:

  • Lightest Derivation Problems: A formal framework using statements, weighted rules, and a goal statement, equivalent to AND/OR graph search.
  • Knuth's Lightest Derivation (KLD): A generalization of Dijkstra's algorithm for these problems, using prioritized rules and a priority queue.
  • A Lightest Derivation (ALD): A generalization of A search that incorporates a heuristic function to guide the search, similar to A in graph search. It uses a monotone heuristic to ensure correctness and efficiency.
  • Heuristics from Abstractions: A key innovation is using abstractions (simplified versions of the problem) to automatically generate admissible and monotone heuristic functions for A*LD. This is analogous to using pattern databases in classical search.
  • Hierarchical A Lightest Derivation (HALD): The most significant contribution, this algorithm searches through a hierarchy of abstractions simultaneously. It interleaves the computation of derivations and contexts at different levels, allowing higher-level abstractions to guide lower-level search. This is particularly effective for perceptual pipelines, enabling top-down influence on low-level processing.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic framework and demonstrates its application on synthetic and image-based problems.

Key Insights and Ideas

  • Unified Framework: Lightest derivation problems provide a powerful, unified way to model diverse AI inference tasks, from parsing to object recognition.
  • Abstractions as Heuristics: The automatic generation of heuristic functions from problem abstractions is a crucial insight, making A* search applicable to a wider range of problems without manual heuristic engineering.
  • Hierarchical Search for Pipelines: HA*LD offers a principled way to solve the "pipeline problem" by allowing higher-level interpretations to guide lower-level computations, avoiding brittle, stage-wise decision-making.
  • Bottom-Up vs. Top-Down: The paper highlights the advantages of bottom-up approaches (like HA*LD) for certain perceptual tasks (e.g., curve grouping) where starting with local features and building up is more efficient than top-down methods.

Key Results

The paper presents experimental results on two main applications:

  • Convex Object Detection: HALD significantly outperforms standard dynamic programming, CFDP, and A with pattern databases, especially as problem difficulty (noise level) increases. For example, in one experiment, HA*LD achieved times of 8.6 seconds compared to 6718.6 seconds for standard DP.
  • Finding Salient Curves: HALD, using heuristics derived from abstractions, efficiently finds salient curves in images, even in areas with low local evidence. The method is shown to be effective in capturing global shape constraints. Running times were competitive with other methods, with HALD often being the fastest.

Limitations and Future Work

  • Cyclic Rules: While the algorithms can handle cyclic rules, they require that the optimal solutions be acyclic.
  • Computational Complexity: While HA*LD is efficient, the worst-case complexity can still be high for certain problem structures.
  • Future Work: The authors suggest composing salient curve finding with rules for more complex structures and applying the pyramid-based abstraction approach to a wider range of computer vision problems. They also mention exploring inadmissible heuristics for faster, though potentially suboptimal, solutions.

Summary updated

Abstract

We consider the problem of computing a lightest derivation of a global structure using a set of weighted rules. A large variety of inference problems in AI can be formulated in this framework. We generalize A* search and heuristics derived from abstractions to a broad class of lightest derivation problems. We also describe a new algorithm that searches for lightest derivations using a hierarchy of abstractions. Our generalization of A* gives a new algorithm for searching AND/OR graphs in a bottom-up fashion. We discuss how the algorithms described here provide a general architecture for addressing the pipeline problem --- the problem of passing information back and forth between various stages of processing in a perceptual system. We consider examples in computer vision and natural language processing. We apply the hierarchical search algorithm to the problem of estimating the boundaries of convex objects in grayscale images and compare it to other search methods. A second set of experiments demonstrate the use of a new compositional model for finding salient curves in images.
BibTeX
@article{felzenszwalb2007generalized,
  author = {Pedro F. Felzenszwalb and David A. McAllester},
  title = {{The Generalized A* Architecture}},
  journal = {JAIR},
  year = {2007},
  doi = {10.1613/jair.2187},
}
Figure