Real-time Heuristic Search for Combinatorial Optimization and Constraint Satisfaction
Wheeler Ruml · 2002
We summarize a new approach to real-time heuristic tree search for problems with a fixed goal depth, such as com-binatorial optimization and constraint satisfaction problems. Best-leaf-first search (BLFS) is a general and complete algo-rithm that visits leaves in an order that efficiently approxi-mates increasing predicted cost. It can adapt its search order on-line to the current problem. Empirical results on a vari-ety of challenging synthetic benchmarks suggest that BLFS yields competitive or superior performance and is more ro-bust than previous methods.