A Two-Phase Search Method for Solving Configuration Problems

We consider the problem of finding solutions to resource-based configuration problems under real-time conditions. The objective of finding the best solutions possible, given the time restrictions, is formalized within a decision theoretic framework. The utility of a configuration returned by a search algorithm depends on the cost of this configuration as well as on the time required to find it. We propose a heuristic search strategy as an approximation of a (computationally intractable) search algorithm which is optimal in the sense that it maximizes the (expected) value of computation. This search strategy consists of two phases. In connection with the heuristic principles underlying both search phases, the decision whether to continue or break off the search along a certain path of the search tree has to be made. We propose a formalization of as well as a solution to this termination problem. Experimental studies show very promising results for the search algorithm. 1 Introduction H..