Symbolic Greedy Best-First Search with Operator-Potential Heuristics

Abstract

Symbolic search has long been recognized as one of the state-of-the-art techniques for exhaustive state-space exploration and cost-optimal planning, leveraging compact state representations and efficient set-based operations. Despite its success in optimal planning, symbolic search has not traditionally been considered suitable for satisficing search, where heuristic guidance is paramount. In this paper, we investigate how to perform symbolic satisficing search aimed at efficiently finding good-quality solutions without guaranteeing optimality. We show that operator-potential heuristics are effective at guiding the search. Empirical results demonstrate that symbolic greedy best-first search with operator-potential heuristics is competitive with explicit state-space search.