Efficient symbolic search for cost-optimal planning

In cost-optimal planning we aim to find a sequence of operators that achieve a set of goals with minimum cost. Symbolic search with Binary Decision Diagrams (BDDs) performs efficient state space exploration in terms of time and memory. This is crucial in optimal settings, in which large parts of the...

Full description

Saved in:
Bibliographic Details
Published in:Artificial intelligence 2017-01, Vol.242, p.52-79
Main Authors: Torralba, Álvaro, Alcázar, Vidal, Kissmann, Peter, Edelkamp, Stefan
Format: Article
Language:English
Subjects:
Bidirectional
Computation
Computational efficiency
Cost engineering
Cost-optimal planning
Heuristic
Image computation
Interprocessor communication
Minimum cost
Operators
Optimization
Planning
Regression
Regression analysis
Search algorithms
Searching
Space exploration
State invariants
Symbolic search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In cost-optimal planning we aim to find a sequence of operators that achieve a set of goals with minimum cost. Symbolic search with Binary Decision Diagrams (BDDs) performs efficient state space exploration in terms of time and memory. This is crucial in optimal settings, in which large parts of the state space must be explored in order to prove optimality. However, the development of accurate heuristics for explicit-state search in recent years have left symbolic search techniques in a secondary place. In this article we propose two orthogonal improvements for symbolic search planning. On the one hand, we analyze and compare different methods for image computation in order to efficiently perform the successor generation on symbolic search. Image computation is the main bottleneck of symbolic search algorithms so an efficient computation is paramount for efficient symbolic search planning. On the other hand, we study how to use state-invariant constraints to prune states in symbolic search. This is essential in regression search but it is yet to be exploited in symbolic search planners. Experiments with symbolic bidirectional uniform-cost search and symbolic A⁎ search with PDBs show remarkable performance improvements on most IPC benchmark domains. Overall, with the help of our improvements, symbolic bidirectional search outperforms explicit-state search with state-of-the-art heuristics such as LM-cut across many different domains.
ISSN:0004-3702
1872-7921
DOI:10.1016/j.artint.2016.10.001