An improved probabilistic planning algorithm based on PGraphPlan

Abstract

With the fast development of AI planning, planning technology has been widely applied to robotics and automated cybernetics. Many researchers pay more and more attention to the uncertainty in AI planning. This paper provides a probabilistic planning algorithm based on PGraphPlan. This paper introduces two new concepts: new proposition and mutex propositions. During the expansion of the planning graph, each operator and each way of instantiating the preconditions of the operator to propositions in the previous level do not insert an action node if any two of its preconditions are labeled as mutex propositions. So the amount of nodes created is reduced. The algorithm is implemented in C. This paper provides empirical evidence in favor of this approach, which show that this algorithm outperforms PGraphPlan and has excellent performance in terms of storage space.