In this work, we present a heuristic search technique (Contract Search) which can be automatically adapted for a specified node expansion limitation. We analyze the node expansion properties of best first search and propose a probabilistic model (rank profile) to characterize heuristic search under restricted expansions. We identify the basic properties of the rank profile and establish its relation with the search space configuration. In Contract Search, we use the rank profile model to formulate an optimal strategy to choose level dependent restriction bounds maximizing the probability of obtaining the goal node under the specified contract. Experimental comparison with anytime search techniques like ARA* and beam search shows that Contract Search outperforms these techniques over a range of constraint specifications.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com