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

Authors

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

DOI:

https://doi.org/10.1609/icaps.v29i1.3462

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.

Downloads

Published

2021-05-25

How to Cite

Castro, M. P., Piacentini, C., Cire, A. A., & Beck, J. C. (2021). Relaxed BDDs: An Admissible Heuristic for Delete-Free Planning Based on a Discrete Relaxation. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 77-85. https://doi.org/10.1609/icaps.v29i1.3462