Content area
Full text
TOKENPLAN is a planner based on the use of Petri nets. Its main feature is the flexibility it offers in the way it builds the planning graph. The Fifth International Conference on Artificial Intelligence Planning and Scheduling planning competition validated its behavior with a GRAPHPLAN-like behavior. The next step is to demonstrate the benefits we expect from our planner in planning problems involving optimization and uncertainty handling.
Action planning is generally done in two stages: (1) building the search space and (2) searching it for a solution. The way work load is shared between these stages depends on the particular approach in use. Similarly to GRAPHPLAN (Blum and Furst 1997), TOKENPLAN alternates explicit stages of search-- space expansion, with explicit stages of plan search and extraction. The particularity of our planner lays in the flexibility it offers in the way it builds the search space, which, in turn, leads to valuable consequences over the search itself. This flexibility is implemented using Petri nets as a basis for our representation.
Insights of TOKENPLAN cannot be detailed here, but the reader will find its description in full length in Fabiani and Meiller (2000). Instead, this article sketches out the approach Of TOKENPLAN, along with the benefits we expect from it in planning problems involving optimization and uncertainty handling.
TOKENPLAN and Petri Nets
The reader unfamiliar with Petri nets needs only know the following: They are made of places, transitions, and tokens. A place can be seen as a token holder. When it contains one or more tokens, it is said to be marked. Transitions allow tokens to circulate from place to place. When all the places connected as input to a transition are marked, this transition can be triggered. When it is triggered, tokens flow through it toward places connected as output. The parallel with a STRIPS-like description of a planning domain appears clearly: Transitions correspond to operators, input places to preconditions, and output places to effects. TOKENPLAN starts by completing this exact conversion. All subsequent work considers the obtained Petri net representation.
For a state to be represented, relevant places are marked with tokens. These tokens hold on a label of the specific bindings of the variables of the predicate associated with the place. Starting...