Thesis Proposal: Robust Planning Under Uncertainty

Jim Blythe, January 1995.


Planning, the process of finding sets of actions which can be executed to achieve some desired result, is an important and well-studied component of artificial intelligence. One of the central assumptions of classical AI-based planning is that the state resulting after performing an action can be predicted completely and with certainty. This assumption has allowed the development of provably correct planning algorithms, but it has also hindered the use of planners in many real-world applications because of the inherent uncertainty in the domains.

My goal is to design a planner that can efficiently build plans with a provably high probability of success in domains with uncertain initial state, action outcomes and external events. Planners that deal with uncertainty have not coped well with external events before, because of the potentially exponential increase in the number of states to consider and the possible effects of actions. My thesis is that such a planner can be built by combining conventional planning methods with an evaluation technique that exploits probabilistic independence among domain variables. This approach is demonstrated in a prototype system called Weaver that exploits independence in two ways. First, external changes to the environment are represented independently from the actions available to the planner. Second, the probability of plan success is evaluated in a way that only represents aspects of the domain that are required for each particular situation. Using this approach, Weaver is able to create and evaluate plans for problems that would otherwise be intractable.

I propose to further develop the approach demonstrated in Weaver to be able to construct plans with a high probability of success in more complex dynamic domains. The proposal outlines some possible examples and describes several heuristics that might be used in the planner and the probabilistic reasoner to cope with such domains.