Abstraction Heuristics for Symbolic Bidirectional Search

Álvaro Torralba, Carlos Linares López, Daniel Borrajo

Introduction

In cost-optimal planning, the objective is to identify the least-cost sequence of actions to transition from an initial state to a goal state. While the A* algorithm guided by heuristics has been the standard approach, bidirectional search—searching forward from the start and backward from the goal simultaneously—offers a theoretical advantage by potentially meeting in the middle. However, bidirectional search often struggles in high-dimensional spaces where frontiers may fail to intersect efficiently. Furthermore, integrating admissible heuristics into a two-way search is mathematically complex; improper implementation can lead to suboptimality or search inefficiency.

This paper introduces SymBA (Symbolic Bidirectional A), a framework that addresses these challenges by combining symbolic search with dynamic abstraction heuristics. By representing sets of states using Binary Decision Diagrams (BDDs), SymBA* processes entire frontiers at once and only resorts to expensive heuristic computations when the "blind" symbolic search becomes computationally unfeasible.

Methodology: Symbolic Bidirectional A*

SymBA* utilizes several novel techniques to optimize the search process:

  1. Symbolic Bidirectional Search: The algorithm uses BDDs to represent and manipulate sets of states, significantly reducing the overhead of detecting collisions between forward and backward search frontiers.
  2. Lazy Heuristic Refinement: The planner initially performs a blind bidirectional search. It only triggers the computation of abstraction heuristics when the BDD size exceeds a predefined threshold (e.g., 10 million nodes), treating heuristics as a fallback rather than a constant requirement.
  3. Perimeter Abstractions: When the search stalls, SymBA* uses current frontiers to define a "perimeter." It then constructs an abstract version of the problem where the goal is to reach this perimeter, providing a more accurate distance estimate for the original state space.
Conceptual illustration of abstraction heuristics in symbolic search, showing the relationship between the original state space and the abstract search frontiers.
  1. Partial Abstractions with A*: Unlike traditional methods that solve the entire abstract state space, SymBA uses A to explore only relevant portions. This allows for the use of larger, more detailed abstractions than previously possible.
  2. Search Selection Strategy: The algorithm maintains a pool of active searches (original and abstract) and dynamically decides which to advance based on estimated utility and feasibility.

Experimental Evaluation

The researchers evaluated SymBA* using optimal-track STRIPS planning instances from the International Planning Competitions (IPC) between 1998 and 2014. This dataset encompasses a wide variety of domains, including logistics (Airport, Elevators) and logic puzzles (Sokoban).

Key Results

SymBA was the winner of the optimal track at IPC-2014, demonstrating its state-of-the-art performance. As shown in the table below, SymBA configurations (particularly ipc2) outperformed both the baseline symbolic bidirectional search (SB) and METIS, a top-tier explicit-state planner.

Coverage results across various IPC domains, comparing SymBA* configurations against baseline symbolic search (SB) and the Metis planner.

In its best configuration, SymBA solved 25 more problems than the baseline across 14 domains. It achieved a total score of 21.24, compared to 20.93 for the baseline and 19.99 for METIS. The planner proved especially efficient in complex domains like NoMystery and Satellite*, where the ability to switch from blind search to heuristic-guided search was critical.

Discussion and Future Work

A key insight from this work is that heuristics are not always a net positive in symbolic search; the overhead of their computation can sometimes outweigh the search time saved. SymBA* successfully manages this trade-off through its lazy refinement strategy. Furthermore, this work marks the first time bidirectional search has been used within abstract state spaces to generate heuristics, allowing frontiers to exchange information and avoid redundant work.

Despite its success, the authors note that abstraction generation is not free; in some instances, the overhead led to lower coverage than a simple blind search. Future work will focus on improving automated strategies for variable selection in abstractions and applying these bidirectional techniques to other hierarchical search algorithms.

Summary updated

Abstract

Symbolic bidirectional uniform-cost search is a prominent technique for cost-optimal planning. Thus, the question whether it can be further improved by making use of heuristic functions raises naturally. However, the use of heuristics in bidirectional search does not always improve its performance. We propose a novel way to use abstraction heuristics in symbolic bidirectional search in which the search only resorts to heuristics when it becomes unfeasible. We adapt the definition of partial and perimeter abstractions to bidirectional search, where A* is used to traverse the abstract state spaces and/or generate the perimeter. The results show that abstraction heuristics can further improve symbolic bidirectional search in some domains. In fact, the resulting planner, SymBA*, was the winner of the optimal-track of the last IPC.
BibTeX
@inproceedings{torralba2016abstraction,
  author = {Álvaro Torralba and Carlos Linares López and Daniel Borrajo},
  title = {{Abstraction Heuristics for Symbolic Bidirectional Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure