The planning system is an interleaved plan/execute system called BUMP (Basic University of Minnesota Planner). The interleaving is used to acquire additional information during plan execution. The planning domain is Tool Box World, which provides the planner with both incomplete information, and a wold which defeats locally greedy planning algorithms. The world consists of a set of 'tool boxes' which can be opened, closed, and bolted shut by the simulated robot. These tool boxes contain wrenches and bolts of specific, non-interchangeable, sizes. The task is to lock specific tool boxes with specific sized bolts. Incomplete information is provided by limiting the knowledge of where specific wrenches and bolts are located.
A critical component for any comparison is the metric. This paper establishes two plan quality criteria which will be used to compare planning strategies:
These criteria are considered under multiple planning strategies, including changes to goal ordering, when to sense, and what to sense. So each planning strategy consists of a policy for each of these areas. These planning strategies are evaluated according to the rates of failures, and the nature of the failures, either a premature action, which must be undone to complete the plan, or failures due to bad sensor data (either incorrectly sensed or invalid default values).
The paper presents a detailed mathematical analysis of the costs associated with actions and for recovering from bad data, the expected number of premature actions over the problem space, and from these the expected cost of using a specific policy. In addition, the cost of recovering from bad data is calculated, and a O(b log b) (where b is the number of boxes) algorithm for finding a near-optimal policy is presented. The algorithm is near-optimal because an approximation to the actual cost of recovering from bad data is used.