Searching with Probabilities

Search algorithms for finding optimal solutions are, at least from the practical point of view, often enough intractible, so that the search for good ('satisficing') solutions becomes a research topic of its own interest. Satisficing solutions and different approaches to obtain them under various criteria is the subject of these notes, published in the series "Research notes in artificial intelligence". In an introductory chapter the author presents the known point - value and the point - { { set of values} } identification used in search- based decision-algorithms for guiding the search and discusses some of their advantages and disadvantages. This motivates the here studied alternative approach using that evaluation functions do not return a point - value or a range of values corresponding to a point (state) in a tree but now a distribution function, that describes the possible location of the'value' of the state. Chapter 2 introduces this model, Chapter 6 resumes the basic results.