Front-to-Front Heuristic Search for Satisficing Classical Planning

Ryo Kuroiwa, Alex FukunagaIJCAI 2020 · DOI

TL;DR

This paper introduces "Top-to-Top Bidirectional Search" (TTBS), a novel front-to-front heuristic search strategy for classical planning. TTBS aims to overcome the limitations of previous bidirectional approaches by effectively "meeting in the middle" of the search space, leading to improved performance and the ability to solve problems that elude traditional forward or backward search methods.

What Problem Does This Paper Address?

Classical planning aims to find a sequence of actions to transform an initial state into a goal state. While optimal planning has seen success with bidirectional search (searching from both start and goal simultaneously), satisficing planners (which prioritize finding any solution quickly over the best solution) have largely stuck to unidirectional forward search. Previous attempts at bidirectional satisficing planning, like biFD, often failed to achieve true "meet-in-the-middle" behavior, instead acting like a simple portfolio of independent forward and backward searches. This meant they didn't offer significant advantages over running forward and backward searches separately. The core problem is how to effectively combine forward and backward search in a way that leverages their complementary strengths and genuinely benefits from searching from both ends, especially when optimality isn't the primary goal.

Methods

The paper proposes Top-to-Top Bidirectional Search (TTBS), a front-to-front heuristic search strategy. Unlike "front-to-end" approaches that evaluate states based on their distance to the goal or start, TTBS evaluates states based on their estimated distance to the opposite search frontier.

Here's how it works:

  • Front-to-Front Evaluation: When expanding a node s in the forward search, TTBS estimates its distance to the "top" node (the node with the lowest heuristic value) in the backward search's open list. Similarly, backward search nodes are evaluated against the top node in the forward search's open list.
  • "Meet-in-the-Middle" Approximation: The intuition is that if both searches are progressing well towards each other, the top nodes of their respective open lists should be good approximations of states that are "in the middle" of the search space.
  • Re-evaluation Mechanism: To avoid the high overhead of re-evaluating every node when the opposite frontier changes (as in some prior methods like DNR), TTBS uses a more moderate re-evaluation. When a node s is expanded, it's checked against the current "top" node d of the opposite frontier. If d is "similar" to the node D(s) that s was previously evaluated against, s is expanded. Otherwise, s is re-evaluated against the new d and re-inserted into the open list. This prioritizes re-evaluated nodes.
  • Efficient Intersection Detection: TTBS checks for frontier intersection by seeing if a newly generated state has already been encountered by the opposite search. This is done efficiently using hash sets, trading off the possibility of missed intersections for speed.

Datasets

The paper evaluates TTBS on 47 planning domains from the International Planning Competition (IPC) 98-2018. These domains are in the SAS+ representation and do not contain axioms or conditional effects.

Key Insights and Ideas

  • True Bidirectional Synergy: The key insight is that a well-designed front-to-front approach can achieve genuine "meet-in-the-middle" behavior in satisficing planning, unlike previous attempts that often devolved into portfolio effects.
  • The "Top" as a Proxy: Using the top node of the opposite frontier as the target for heuristic evaluation is a surprisingly effective heuristic for guiding searches towards each other.
  • Balancing Overhead and Performance: TTBS strikes a good balance between the computational cost of re-evaluation and the effectiveness of front-to-front search, outperforming methods like DNR and SFBS in terms of solved instances and search efficiency.
  • Complementarity is Key: The real power of TTBS emerges when it's used in conjunction with traditional forward and backward search. A portfolio including TTBS significantly outperforms portfolios without it, demonstrating its unique ability to solve problems that others miss.

Key Results

  • Improved Coverage: TTBS solved 38 instances that neither FD (forward GBFS) nor FDr (backward GBFS) could solve.
  • "Meet-in-the-Middle" Behavior: TTBS exhibited meet-in-the-middle behavior (meet metric > 0.2) on a majority (26/47) of the tested IPC domains, and strong behavior (meet > 0.4) on 18 domains. This contrasts sharply with biFD, which showed almost no meet-in-the-middle behavior.
  • Portfolio Performance: A portfolio combining FD, FDr, and TTBS (FD+FDr+TTBS) achieved the highest coverage among all tested portfolios, outperforming even a simple FD+FDr portfolio.
  • Efficiency: While TTBS alone wasn't always faster than FD, its ability to solve more problems and its efficient re-evaluation mechanism made it competitive. It generally outperformed SFBS in terms of search time and node expansions due to SFBS's higher overhead.

Limitations and Future Work

  • SFBS vs. TTBS: The paper notes that SFBS (Single-Frontier Bidirectional Search) demonstrates stronger meet-in-the-middle behavior on many domains. This is because SFBS more strictly approximates the ideal front-to-front search but incurs significant overhead.
  • Future Work: The authors suggest exploring improved re-evaluation strategies for TTBS to more closely approximate the strict front-to-front behavior of SFBS without its associated overhead. This could potentially lead to even better meet-in-the-middle performance.

Summary updated

BibTeX
@inproceedings{kuroiwa2020front,
  author = {Ryo Kuroiwa and Alex Fukunaga},
  title = {{Front-to-Front Heuristic Search for Satisficing Classical Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/567},
}
Figure