Real-Time Heuristic Search for Combinatorial Optimization and Constraint Satisfaction

Contents

We summarize a new approach to real-time heuristic tree search for problems with a fixed goal depth, such as combinatorial optimization and constraint satisfaction problems. Best-leaf-first search (BLFS) is a general and complete algorithm that visits leaves in an order that efficiently approximates increasing predicted cost. It can adapt its search order on-line to the current problem. Empirical results on a variety of challenging synthetic benchmarks suggest that BLFS yields competitive or superior performance and is more robust than previous methods.