The Planning Net: A Structure to Improve Planning Solvers with Petri Nets

In this paper the classical planning problem is formalized as a Petri Net. The authors review the Graphplan notions of mutex relation and maintenance actions based on the Petri Net flow. They also classify pairs of conflicting actions in terms of four different control structures, which are used to build the Plan Net. In addition the authors present the order relation of propositions, i.e., pairs of conflicting propositions that allow inclusion of more information in the Planning Net. The planning problem represented on Planning Net is translated into a SAT instance and solved by a modern SAT solver. The authors show the advantages provided by the inclusion of the propositions ordering relation and compare their experimental results with Satplan.