Width-Based Backward Search

Authors

  • Chao Lei The University of Melbourne
  • Nir Lipovetzky The University of Melbourne

Keywords:

Classical Planning Techniques And Analysis

Abstract

It has been shown recently that duality mapping is a viable strategy to turn progression (forward search) into regression (backward search), but the experimental results suggest that the dual versions of standard IPC benchmarks are quite difficult to solve for heuristic search planners. We aim to study the performance of width-based planners over regression. Our experiments show that width-based search can solve dual problems efficiently when the goal state is restricted to single fluent, but it becomes challenging when the goal state contains conjunctive fluents. We then show that the backward version of best-first width-search (BFWS) with the evaluation function f5, BFWS(f5), and its polynomial variant, k-BFWS(f5), are not competitive with their forward versions, but can be orthogonal over the IPC benchmarks. Hence, we propose a front-to-end bidirectional search k-BDWS-e and its front-to-front variant by integrating forward and backward k-BFWS(f5) with the additional intersection check between expanded states whose novelty is 1 in the opposite Close list. Practical findings on the challenges of regression in classical planning are briefly discussed.

Downloads

Published

2021-05-17

How to Cite

Lei, C., & Lipovetzky, N. (2021). Width-Based Backward Search. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 219-224. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/15965