Solving several planning problems with Picat
Neng‐Fa Zhou, Håkan Kjellerstrand · 2014
In this paper, we present programs in Picat for solving three planning puzzles, including 15-puzzle, Klotski, and the Rubik's cube. All these programs use the planner module of Picat. For a planning problem, we only need to specify the conditions on the final states and the set of actions, and call the planner on an initial state to find a plan or a best plan. The planner module uses tabling. It tables states encountered during search and performs resource-bounded search to fail states that cannot lead to a final state with the available resources. The Picat programs for the problems are straightforward. The programs for 15-puzzle and Klotski are very efficient. The Rubik's cube program has succeeded in solving instances that require 14 or fewer moves. As computers have more and more memories, we believe that the tabling approach to planning will become increasingly more effective and important.