COMPLAN: A Conformant Probabilistic Planner ⁄

摘要

COMPLAN is a conformant probabilistic planner that finds a plan with maximum probability of success for a given hori-zon. The core of the planner is a a depth-first branch-and-bound search in the plan space. For each potential search node, an upper bound is computed on the success probability of the best plans under the node, and the node is pruned if this upper bound is not greater than the success probability of the best plan already found. A major source of efficiency for this algorithm is the efficient computation of these upper bounds, which is possible by encoding the original planning problem as a propositional formula and compiling the formula into de-terministic decomposable negation normal form. Conformant Probabilistic Planning Consider the SLIPPERY-GRIPPER domain (Kushmerick, Hanks, & Weld 1995), where a robot needs to have a block painted and held in his gripper, while keeping his gripper clean. The gripper starts out clean, but may be wet, which may prevent him from holding the block; painting the block, while certain to succeed, may make his gripper dirty; a dryer is available to dry the gripper. Given probability distribu-tions quantifying these uncertainties and a planning horizon, the robot requires a plan that achieves the goal with maxi-mum probability. A probabilistic planning problem can be characterized by a tuple 〈S, I,A,G,n 〉 where S is the set of possible world states, I is a probability distribution over S quantifying the uncertainty about the initial state, A is the set of actions, all of which are assumed to be applicable in every state, G is the set of goal states, and n is the planning horizon. To quantify the uncertainty in action effects, each action a ∈ A is a function that maps each state s ∈ S to a prob-ability distribution Pras over all states S. Starting from our initial belief state B0, which is equal to I, each action a ∈ A taken will bring us to a new belief state with updated proba-bilities for the world states S: Bn(s′) = s∈S