Pontificia Universidad Católica de Chile Pontificia Universidad Católica de Chile
Margarita P. Castro, Chiara Piacentini, Andre A. Cire, J. Christopher Beck. Relaxed Decision Diagram Based Heuristics for Delete-Free Planning Tasks. Journal of Artificial Intelligence Research, 2020, 67:607-651 (2020)

Relaxed Decision Diagram Based Heuristics for Delete-Free Planning Tasks

Revista : Journal of Artificial Intelligence Research
Volumen : 67
Páginas : 607-651
Tipo de publicación : Publicaciones WOS sin afiliación UC Ir a publicación


We investigate the use of relaxed decision diagrams (DDs) for computing admissible heuristics for the cost-optimal delete-free planning (DFP) problem. Our main contributions are the introduction of two novel DD encodings for a DFP task: a multivalued decision diagram that includes the sequencing aspect of the problem and a binary decision diagram representation of its sequential relaxation. We present construction algorithms for each DD that leverage these different perspectives of the DFP task and provide theoretical and empirical analyses of the associated heuristics. We further show that relaxed DDs can be used beyond heuristic computation to extract delete-free plans, find action landmarks, and identify redundant actions. Our empirical analysis shows that while DD-based heuristics trail the state of the art, even small relaxed DDs are competitive with the linear programming heuristic for the DFP task, thus, revealing novel ways of designing admissible heuristics.