Article Preview
TopIntroduction
The planning problem in AI aims to find a set of actions (a plan) in order to obtain a goal state from a given initial state. The classical planning problem is PSPACE-Complete (Bylander, 1994), nevertheless industry, transport and robotics are examples of areas that are directly benefited from the recent advances on automated planning.
One of the breakthroughs in methods for solving planning problems was Graphplan (Blum & Farst, 1995; Weld, 1999). It is based on a data structure that represents the search space of a planning problem in a smart and economic way. It allows parallelism among actions through the identification of mutually exclusive actions and propositions. The so called Planning Graph is the basis for many algorithms which were proposed in the past few years.
The strategy of encoding planning problems as satisfiability ones was shown to be competitive. The transformation of a Planning Graph into as satisfiability one presented good results on intrinsically hard problems. A good example is Satplan (Kautz & Selman, 2006).
The idea of representing the planning problem in a Petri Net also seems promising since Petri Nets is a model to represent a system structure and behavior based on preconditions and effects.
In this paper we present a data structure based on Petri Nets in order to solve a planning problem. Our idea is to use the dynamics of Petri Nets in order to improve the classical Planning Graph, which is a static structure, replacing it by a Petri Net, which is a dynamic one, in order to obtain a faster planner (Silva et. al. 2000; Schreiner et. al, 2012).
A planning method based on Petri Nets, called Petriplan, was proposed by Silva (2000). This method converts the planning problem into the reachability problem in Petri Nets. The solver was initially based on integer programming techniques and was not as efficient as it could be.
In this paper we present the Planning Net, which is a data structure based on Petri Nets. It includes a more precise way to classify relations between actions in terms of order relations.
We explore Petri Nets in a more effective way. We propose (i) a smarter way to use the Petri Net flow; (ii) a more precise way to classify the relations between actions; and (iii) a more precise way to classify the relations between propositions.
In Graphplan, pairs of conflicting actions are classified as mutually exclusive based on two criteria: interference and competing needs. The conflicts between pairs of action on the Planning Net are an improvement of the interference conflict. The Petri Net flow analysis showed the uselessness of the competing needs mutexes in the Planning Net. The reason is that the net flow ensures that pairs of actions in this mutex type do not occur in parallel. The net flow also allows to reduce the number of maintenance actions on the net when compared to the Planning Graph.
We specify a partial ordering on actions, which theoretically captures information in a richer way. Pairs of actions are classified in four different ways. Given two actions a and b, we define that they may occur in parallel, non-parallel, a precede b or they are mutually exclusive (Schreiner, 2012).
We also present a new form to capture order relations on propositions. Partial orderings between two propositions represents the information from one or more order relation of actions. In this way, the order relation of propositions encapsulates restrictions of the order relations of actions (Schreiner, 2013).