Magazine article AI Magazine

TOKENPLAN: A Planner for Both Satisfaction and Optimization Problems

Magazine article AI Magazine

TOKENPLAN: A Planner for Both Satisfaction and Optimization Problems

Article excerpt

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 from the initial marking and propagating the tokens through the net, we can list the markings that can be reached in one step, two steps, and so on. In fact, TOKENPLAN approximates this listing. Indeed, all markings reachable in one step are unified in one sole marking: They are superposed, and copies of identical tokens in identical places are deleted. By keeping track of the evolution of this marking from one step to the next, we obtain a leveled plan graph similar to GRAPHPLAN'S. This plan graph is a compact representation of the search space. To extract a plan if any, a backward search is performed.

Of course, this search space is bigger than the actual space of reachable states because the set of states represented by each marking contains other states than the ones that are actually reachable. Indeed, some tokens, which appear in a same-level marking after the union of individual markings was completed, could not actually be where they are simultaneously otherwise. To make the approximation more accurate, pairwise mutual-exclusion relations are computed. The same rules as the ones for computing GRAPHPLAN'S mutex relations are applied (after being formulated in terms of tokens). However, part of the mutex relations, which we call permanent mutex, can be deduced with no costly computation using colored tokens. The idea is to use some "physical" properties of tokens to embed some structural properties of the planning domain. In some cases, TOKENPLAN can avoid the explicit computation of nearly half the mutex relations (nonubiquity of robots and balls in the gripper domain, for example). …

Search by... Author
Show... All Results Primary Sources Peer-reviewed


An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.