  This paper describes the best first search strategy used by U-Plan (Mansell
1993a), a planning system that constructs quantitatively ranked plans given an
incomplete description of an uncertain environment. U-Plan uses uncertain and
incomplete evidence de scribing the environment, characterizes it using a
Dempster-Shafer interval, and generates a set of 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. The search strategy is best first with the provision to update expected
fulfillment and review previous decisions in the light of planning
developments. U-Plan generates multiple plans for multiple possible worlds, and
attempts to use existing plans for new world situations. 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.
