A Study of Search Methods: The Effect of Constraint Satisfaction and Adventurousness

Abstract

This msearch addresses how constraint satisfiJction interacts with the search mode, and how the ratio of breadth of effort to depth of effort can be controlied. Four search paradigrns, each the best of its kind for non -adversary problems, are investigated. One is depth-first, and the others best -first. Al! rnethods except one highly informed best -first search use the same knowlcdge, and each of thcse methods is tested with and without the use of a constraint satisfaction procedure on sets of progressively more diflicult problems. As expected, the most informed search does bctter than the less informed as the problems get more difficult. Constraint satisfaclion is found to have a pronounc edly greater effect when coupled with the most informed algorithm. Large performance increments over A • can be produced by the use of a coefficient associated with the h term, and this algorithm produces solutions that are only 5% worse than optimal. This is a known phenomenon; however, the range of this coefficient is very narrow. We term this coefficient, which controls the ratio of depth of effort to breadth of effort, the a(iventurousness coefficient. Thless tractable a problern the greater the adventurousness should be. We present evidence to support this.