Computer Science Department
School of Computer Science, Carnegie Mellon University
Planning under Uncertainty in Dynamic Domains
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.