  This paper describes ongoing research into planning in an uncertain
environment. In particular, it introduces U-Plan, a planning system that
constructs quantitatively ranked plans given an incomplete description of the
state of the world. U-Plan uses a DempsterShafer interval to characterise
uncertain and incomplete information about the state of the world. The planner
takes as input what is known about the world, and constructs a number of
possible initial states with representations at different abstraction levels. A
plan is constructed for the initial state with the greatest support, and this
plan is tested to see if it will work for other possible initial states. All,
part, or none of the existing plans may be used in the generation of the plans
for the remaining possible worlds. Planning takes place in an abstraction
hierarchy where strategic decisions are made before tactical decisions. A
super-plan is then constructed, based on merging the set of plans and the
appropriately timed acquisition of essential knowledge, which is used to decide
between plan alternatives. U-Plan usually produces a super-plan in less time
than a classical planner would take to produce a set of plans, one for each
possible world.
