A Linear Time Transform for Probability Aware Planning 2000

Abstract:  We present a transform that enables traditional Shortest-Feasible-Pl an planners to reason about uncertain operators and produce plans which have higher probabilities of success. This transform converts a probability-aware domain description into a STRIPSstyle description, where the probability of success is expressed by plan length. Using this transformed description a plan can be generated by a traditional planner. The transform is shown to be at worst linear in the size of the input, and allows the planning system to trade-off accuracy against runtime as an anytime computation. 1 Introduction Beginning with General Problem Solvers[17], and the STRIPS[8] planning system, traditional planners have defined an optimal plan as the shortest plan which achieves the goal. Such planning systems assumed that the correct operators, applied in the correct order, would always achieve the goal. Unfortunately, in the real world, operators fail. As a result, the `best' plan may not be the shortes...