Domain-Dependent and Domain-Independent Problem Solving Techniques

Roni SternIJCAI 2019 · DOI

Introduction

In the field of Artificial Intelligence, "search" is the fundamental mechanism by which an agent identifies a path from a starting state to a goal. While the classic A* algorithm remains a mathematical cornerstone due to its ability to find optimal solutions, its practical application is often limited by high memory consumption and slow execution in complex, real-world environments. This paper, presented at IJCAI-19, synthesizes a decade of research by Roni Stern into heuristic search, bridging the gap between general-purpose "black-box" algorithms and highly specialized solvers.

Redefining Search Objectives

Stern addresses the reality that finding the absolute best (optimal) solution is not always the primary goal. In many practical scenarios, users operate under specific constraints that require different search paradigms:

  1. Bounded-Cost Search: Finding any valid path that falls under a specific cost threshold (e.g., "Find a route that costs less than $100").
  2. Bounded-Suboptimal Search: Prioritizing speed while guaranteeing the solution is no more than a fixed percentage worse than the optimal (e.g., "Find a path quickly that is at most 20% more expensive than the best possible").
  3. Anytime Search: Returning the best possible solution found within a strict time limit, with the quality of the solution improving as more time is allocated.

The core contribution to domain-independent search is the Potential Search (PS) framework. Traditional search focuses on cost minimization; PS shifts this focus toward potential maximization, prioritizing nodes based on the probability that they will lead to a solution within a specific cost bound.

Key algorithms within this framework include:

  • ANA (Anytime Non-Parametric A): An anytime algorithm that eliminates the need for manual "weight" tuning—a process that previously made search algorithms brittle and difficult to deploy. ANA* automatically adjusts its parameters to find increasingly better solutions over time.
  • DPS (Dynamic Potential Search): A variation designed for bounded-suboptimal search that dynamically updates cost targets based on the best lower bounds discovered during the search process.
  • PBS (Probably Bounded-Suboptimal): A "risky" search strategy that guarantees a solution within a bound with a specific probability (1-δ). By accepting a tiny, controlled risk of error, PBS achieves massive speedups on previously intractable problems.

Domain-Dependent Applications

Stern also demonstrates how search principles can be specialized for high-stakes, specific domains:

Multi-Agent Pathfinding (MAPF)

In scenarios like warehouse robotics or airport towing, dozens of agents must move simultaneously without colliding. This creates a "branching factor explosion." Stern utilizes EPEA (Enhanced Partial Expansion A) to manage this complexity, allowing for efficient pathfinding even as the number of agents increases.

Model-Based Diagnosis (MBD)

For complex systems like software or circuits, Stern proposes a parallel search strategy that exploits mathematical duality. One search identifies "conflicts" (what is definitely broken), while a simultaneous search looks for "diagnoses" (explanations for the failure). Because these two tasks are duals, the searches can pass information back and forth, significantly accelerating the diagnostic process.

Key Insights and Results

The research highlights a fundamental shift in the search paradigm: viewing search as a probabilistic challenge rather than a simple cost-minimization problem.

  • Non-Parametric Success: ANA* has emerged as a state-of-the-art anytime algorithm because it removes the guesswork of parameter tuning, making it robust across different domains.
  • The Power of Duality: In specialized fields like MBD, exploiting the relationship between different search perspectives (conflicts vs. diagnoses) acts as a significant shortcut.
  • Speed vs. Risk: The success of PBS suggests that in many real-world applications, a small, calculated risk of suboptimality is a worthwhile trade-off for significant gains in computational speed.

Limitations and Future Directions

Despite these advancements, several challenges remain. While the theoretical understanding of optimal search (A) is mature, the theory surrounding suboptimal search is still developing. There is currently no unified theory for bounded-suboptimal search that matches the proven efficiency of A.

Furthermore, selecting the right algorithm for a new domain remains a manual task. Stern suggests that the "Holy Grail" of this research is automated domain learning—developing algorithms capable of analyzing a problem's properties and automatically customizing a search strategy without human intervention.

Summary updated

BibTeX
@inproceedings{stern2019domain,
  author = {Roni Stern},
  title = {{Domain-Dependent and Domain-Independent Problem Solving Techniques}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/898},
}
Figure