Conditional, Probabilistic Planning: A Unifying Algorithm and Effective Search Control Mechanisms

Several recent papers describe algorithms for generating conditional and/or probabilistic plans. In this paper, we synthesize this work, and present a unifying algorithm that incorporates andclarifies the main techniques that have been developed in the previous literature. Ouralgorithm decouplesthe search-control strategy for conditional and/or probabilistic planning from the underlying plan-refinementprocess. A similar decouplinghas provento be very useful in the analysis of classical planning algorithms, and weshowthat it can be at least as useful here, wherethe search-control decisions are even morecrucial. Previous probabilistic/conditional planners havebeenseverely limited by the fact that they do not knowhowto handle failure points to advantage. Weshowhowa principled selection of failure points can be performedwithin the frameworkour algorithm. Wealso describe and show the effectiveness of additional heuristics. Wedescribe our implemented system called Mahinurand experimentally demonstrate that our methodsproduce efficiency improvements of several orders of magnitude.

Authors

• Nilufer Onder Michigan Technological University
• Martha E. Pollack
• University of Pittsburgh

Keywords

No keywords are indexed for this paper.