A probabilistic model for uncertain problem solving

Until recently, artificial intelligence (AI) research on problem solving ignored issues of uncertainty. With a growing desire to apply research results in real-world contexts, such issues have begun to receive attention. Real-world contexts are inherently uncertain due to several factors, including incomplete and imprecise interpretation of environmental information, unreliable execution of plan actions, and unforeseen interactions among multiple agents. A theoretical framework is offered for addressing issues of problem solving under conditions of uncertainty. The model is a probabilistic generalization of the usual notion of problem space. An admissible forward-directed search algorithm is presented. The need for information-gathering operators to control state disunity and provide pragmatic focusing is established; a representation for such operators is proposed. Aspects of the model are compared to Markov processes and utility-based techniques of decision analysis. A discussion of the limitations of the model is given as well as suggestions for its application.