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

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Planning

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 and clarifies the main techniques that have been developed in the previous literature. Our algorithm decouples the search-control strategy for conditional and/or probabilistic planning from the underlying plan-refinement process. A similar decoupling has proven to be very useful in the analysis of classical planning algorithms, and we show that it can be at least as useful here, where the search-control decisions are even more crucial. Previous probabilistic/conditional planners have been severely limited by the fact that they do not know how to handle failure points to advantage. We show how a principled selection of failure points can be performed within the framework our algorithm. We also describe and show the effectiveness of additional heuristics. We describe our implemented system called Mahinur and experimentally demonstrate that our methods produce efficiency improvements of several orders of magnitude.