Relaxed BDDs: An Admissible Heuristic for Delete-Free Planning Based on a Discrete Relaxation

  • Margarita P. Castro University of Toronto
  • Chiara Piacentini University of Toronto
  • Andre A. Cire University of Toronto Scarborough
  • J. Christopher Beck University of Toronto

Abstract

We investigate the use of relaxed binary decision diagrams (BDDs) as an alternative to linear programming (LP) for computing an admissible heuristic for the cost-optimal delete-free planning (DFP) problem. Our main contributions are the introduction of a novel BDD encoding, a construction algorithm for the sequential relaxation of a DFP task and a study of the effectiveness of relaxed BDD heuristics, both from a theoretical and practical perspective. We further show that relaxed BDDs can be used beyond heuristic computation to extract delete-free plans, find action landmarks, and identify redundant actions. Our empirical analysis shows that while BDD-based heuristics trail the state of the art, even small relaxed BDDs are competitive with the LP heuristic for the DFP task.

Published
2019-07-06