Todd Michael Manseli
This paper describes the best first search strategy used by U-Plan, a planning system that constructs quantitatively ranked plans given an incomplete description of an uncertain environment. U-Plan accepts uncertain and incomplete information about the environment, characterizes it using a Dempster-Shafer interval, and generates a set of multiple possible world states. Plan construction takes place in an abstraction hierarchy where strategic decisions are made before tactical decisions. Search through this abstraction hierarchy is guided by a quantitative measure (expected fulfillment) based on decision theory. This search strategy is best first with the provision to update expected fulfillments and review previous decisions in the fight of planning developments. U-Plan generates multiple plans for multiple possible worlds, and will attempt to use existing plans for new world situation. A super-plan is then constructed, based on merging the set of plans and appropriately timed knowledge acquisition operators, which are used to decide between plan alternatives during plan execution.