Toward a Search Strategy for Anytime Search in Linear Space Using Depth-First Branch and Bound

Authors

  • Carlos Hernandez Universidad Catolica de la Santisima Concepcion
  • Jorge Baier Pontificia Universidad Catolica de Chile

Keywords:

Depth-First Branch and Bound, Anytime Search

Abstract

Depth-First Branch and Bound (DFBnB) is an anytime algorithm for solving combinatorial optimization problems. In this paper we present a weighted version of DFBnB, wDFBnB, which incorporates standard techniques for using weights in heuristic search and offers suboptimality guarantees. Our main contribution drawn from a preliminary evaluation is the observation that wDFBnB, used along with automated or hand-crafted weight schedules, can significantly outperform DFBnB both in terms of anytime behavior and convergence to the optimal. We think this small study calls for more research on the design of automated weight schedules that could provide superior anytime performance across a wider range of domains.

Downloads

Published

2021-09-01