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


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.