Predicting Optimal Solution Cost with Bidirectional Stratified Sampling (Abstract)

Authors

  • Levi Lelis University of Alberta
  • Roni Stern Ben Gurion University
  • Ariel Felner Ben Gurion University
  • Sandra Zilles University of Regina
  • Robert Holte University of Alberta

DOI:

https://doi.org/10.1609/socs.v3i1.18223

Keywords:

Optimal Solution Cost Prediction, SCP

Abstract

Optimal planning and heuristic search systems solve state-space searchproblems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i.e., without actually finding a solution path of that cost. We present an efficient algorithm, BiSS, based on ideas of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. Our method is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity.

Downloads

Published

2021-08-20

Issue

Section

Extended Abstracts of Papers Presented Elsewhere