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.
展开▼
