The Consistent Case in Bidirectional Search and a Bucket-to-Bucket Algorithm as a Middle Ground between Front-to-End and Front-to-Front
| bidirectional heuristic consistency |
PaperID: 140
pdf
poster
|
| Recently, the proposal of individual bounds that use heuristic inaccuracies in front-to-end bidirectional search has improved the state of the art. These bounds apply to pairs of states as well, so we create a new definition of must-expand pairs when consistency is exploited explicitly. Furthermore, the lower bound of such pairs can also be seen as an admissible estimation of the lowest cost of any path between both states thanks to its formulation as a triangle inequality. This cost depends only on the g values and the heuristic estimates and not on the states themselves. Therefore, by grouping nodes by these values in buckets, such an estimate can be computed for sets of nodes and not individual pairs without loss of information. This bucket-to-bucket computation, although as expensive as front-to-front in the worst case, allows implementing a near-optimal algorithm with respect to front-to-end algorithms that use heuristic inaccuracies. Experiments show that bucket-to-bucket algorithms are the state of the art in the Pancake Problem and offer an insightful measurement of how far front-to-end algorithms are from their theoretical limit. | |
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