Phase transitions in classical planning: An experimental study

Phase transitions in the solubility of problem instances are known in many types of computational problems relevant for artificial intelligence, most notably for the satisfiability problem of the classical propositional logic. However, phase transitions in classical planning have received far less atten-tion. Bylander has investigated phase transitions theoretically as well as experimentally by using simplified planning algo-rithms, and shown that most of the soluble problems can be solved by a naı̈ve hill-climbing algorithm. Because of the simplicity of his algorithms he did not investigate hard prob-lems on the phase transition region. In this paper, we address exactly this problem. We introduce two new models of problem instances, one eliminating the most trivially insoluble instances from Bylan-der’s model, and the other restricting the class of problem in-stances further. Then we perform experiments on the behav-ior of different types of planning algorithms on hard problems from the phase transition region, showing that a planner based on general-purpose satisfiability algorithms outperforms two planners based on heuristic local search