Width-Based Backward Search
| classical planning search regression |
PaperID: 123
pdf
poster
|
| 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 IPCs 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 versions of best-first width search with the evaluation function f5, BFWS(f5), and its polynomial variant, k-BFWS, 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 and its front-to-front variant by integrating forward and backward k-BFWS 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. | |
Session 9: Classical Planning | Search
Jump Point Search with Temporal Obstacles
Authors: Shuli Hu, Daniel Harabor, Graeme Gange, Peter Stuckey and Nathan Sturtevant
Keywords:
heuristicpathfindingjump point searchtemporal obstacles
Width-Based Backward Search
Authors: Chao Lei and Nir Lipovetzky
Keywords:
classical planningsearchregression
The Consistent Case in Bidirectional Search and a Bucket-to-Bucket Algorithm as a Middle Ground between Front-to-End and Front-to-Front
Authors: Vidal Alcázar
Keywords:
bidirectionalheuristicconsistency
Contracting and Compressing Shortest Path Databases
Authors: Bojie Shen, Muhammad Aamir Cheema, Daniel Harabor and Peter Stuckey
Keywords:
Shortest PathCompressed Path DatabasesContraction Hierarchies