Search Reduction in Planning with Primary Effects

The use of primary effects in planning is an effective approach for reducing search costs, closely related to abstraction planning. However, there has been little analysis of planning with primary effects and few experimental results. In this paper we demonstrate the connection between primary effects and abstraction hierarchies and provide analytical and empirical results on the efficiency of planning with primary effects. First, we show how the relationship between primary effects and abstraction can be used for automatically selecting primary effects and generating good abstraction hierarchies. Then we analytically demonstrate that the use of primary effects may lead to an exponential reduction of the running time and identify factors that influence the efficiency of planning with primary effects. Finally, we describe experiments that confirm our analysis and demonstrate the practical efficiency of using primary effects.