Christopher Wilt

In many domains, different actions have different costs. In this paper, we show that various kinds of best-first search algorithms are sensitive to the ratio between the lowest and highest operator costs. First, we take common benchmark domains and show that when we increase the ratio of operator costs, the number of node expansions required to find a solution increases. Second, we provide a theoretical analysis showing one reason this phenomenon occurs. We also discuss additional domain features that can cause this increased difficulty. Third, we show that searching using distance-to-go estimates can significantly ameliorate this problem. Our analysis takes an important step toward understanding algorithm performance in the presence of differing costs. This research direction will likely only grow in importance as heuristic search is deployed to solve real-world problems.

We discuss the relationships between three approaches to greedy heuristic search: best-first search, hill-climbing search, and beam search. We consider the design decisions within each family and point out their oft-overlooked similarities. We consider the following best-first searches: weighted A*, greedy search, A* epsilon, window A* and multi-state commitment search. For hill climbing algorithms, we consider enforced hill climbing and LSS-LRTA*. We also consider a variety of beam searches, including BULB. We show how to best configure beam search in order to maximize robustness. An empirical analysis on six standard benchmarks reveals that beam search and best-first search have remarkably similar performance, and outperform hill-climbing approaches in terms of both time to solution and solution quality. Of these, beam search is preferable for very large problems and best first search is better on problems where the goal cannot be reached from all states.

There are many algorithms that are capable of solving the shortest path problem. Given a specific shortest path problem, it is not clear which of the myriad algorithms should be used. Based upon an empirical evaluation of six benchmark domains, we create a decision tree that considers domain features and approximate time/memory budget constraints to decide which algorithm should be used given a domain with known attributes and given time/memory budget. The decision tree also helps identify open questions regarding what information is needed to predict how well a given algorithm will perform.