Operator-Potentials in Symbolic Search: From Forward to Bi-directional Search

Authors

  • Daniel Fišer Saarland University, Saarland Informatics Campus, Saarbrücken, Germany Czech Technical University in Prague, Faculty of Electrical Engineering, Czech Republic
  • Álvaro Torralba Aalborg University, Denmark
  • Jörg Hoffmann Saarland University, Saarland Informatics Campus, Saarbrücken, Germany

Keywords:

Symbolic Search, BDD, Potential Heuristics

Abstract

Symbolic search using binary decision diagrams is a state-of-the-art technique for cost-optimal planning. Heuristic search in this context has been problematic as even a very informative heuristic can be detrimental in case it induces difficult-to-represent state partitionings. It was recently shown that operator-potential heuristics can address this issue in forward search by computing a numeric potential for each operator corresponding to the change of the heuristic value induced by that operator. Forward search is, however, not the best known variant of symbolic search. Here we investigate the integration with backward and bi-directional search instead. We prove that forward search (distance-to-goal) operator-potential heuristics can be turned into backward search (distance-to-initial-state) heuristics elegantly in this context, by summing the backward search path operator-potentials with the initial state goal-distance estimate. We run exhaustive experiments on IPC benchmarks, showing that significant performance improvements can be obtained over symbolic forward search and other state-of-the-art techniques.

Downloads

Published

2022-06-13

How to Cite

Fišer, D., Torralba, Álvaro, & Hoffmann, J. (2022). Operator-Potentials in Symbolic Search: From Forward to Bi-directional Search. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 80-89. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19788