Planning, the process of finding a course of action which can be executed to achieve some goal, is an important and well-studied area of AI. One of the central assumptions of classical AI-based planning is that after performing an action the resulting state can be predicted completely and with certainty. This assumption has allowed the development of planning algorithms that provably achieve their goals, but it has also hindered the use of planners in many real-world applications because of their inherent uncertainty.

Recently, several planners have been implemented that reason probabilistically about the outcomes of actions and the initial state of a planning problem. However, their representations and algorithms do not scale well enough to handle large problems with many sources of uncertainty. This thesis introduces a probabilistic planning algorithm that can handle such problems by focussing on a smaller set of relevant sources of uncertainty, maintained as the plan is developed. This is achieved by using the candidate plan to constrain the sources of uncertainty that are considered, incrementally considering more sources as they are shown to be relevant. The algorithm is demonstrated in an implemented planner, called Weaver, that can handle uncertainty about actions taken by external agents, in addition to the kinds of uncertainty handled in previous planners. External agents may cause many simultaneous changes to the world that are not relevant to the success of a plan, making the ability to determine and ignore irrelevant events a crucial requirement for an efficient planner.

Three additional techniques are presented that improve the planner's efficiency in a number of domains. First, the possible external events are analyzed before planning time to produce factored Markov chains which can greatly speed up the probabilistic evaluation of the plan when structural conditions are met. Second, domain-independent heuristics are introduced for choosing an incremental modification to apply to the current plan. These heuristics are based on the observation that the failure of the candidate plan can be used to condition the probability that the modification will be successful. Third, analogical replay is used to share planning effort across branches of the conditional plan. Empirical evidence shows that Weaver can create high-probability plans in a planning domain for managing the clean-up of oil spills at sea.

180 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu