A decision-theoretic approach to heuristic planning

Many important planning problems are characterized by uncertainty about the current situation and about the consequences of future action. These problems also inevitably involve tradeoffs between the costs and benefits associated with possible actions. Decision theory is an extensively studied methodology for reasoning under these conditions, but has not been explicitly and satisfactorily integrated with artificial intelligence approaches to planning. Likewise, many perceived practical limitations of decision theory, such as problem-solving results that are difficult to explain and computational needs that are difficult to satisfy, can be overcome through the use of artificial intelligence techniques.;This dissertation presents an axiomatic approach to the construction of computer-based systems that solve and explain complex planning problems. Not only does the axiomatic approach advocate the use of formal tools in the early stages of system design, but also it embraces the use of heuristic techniques to find pragmatic solutions that combine formal and heuristic reasoning. The success of this approach is critically dependent on the ability to implement corresponding explanation techniques. To address this need, this dissertation presents a model for the explanation of axiomatic advice embodied in QxQ, a computer program that uses text and graphics to explain and interpret the differences in expected utility among branches of a decision tree. QxQ demonstrates that the combination of decision-theoretic and artificial intelligence approaches allows planning decisions derived from formal models to be justified in a manner that does not require familiarity with the formal model itself.