Real-Time Heuristic Search for Combinatorial Optimization and Constraint Satisfaction

Wheeler Ruml

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.