Graphplan

The graph plan algorithm is an algorithm from the field of artificial intelligence. He used to automatically find a sequence of actions that lead to a desired destination. The solution is found with the help of a so called planning graph in polynomial time.

Planning graph

The planning graph is a bipartite, directed graph, which is constructed from Propositionsknoten and action nodes. It is visualized in layers, wherein the lowermost layer is a literal of the start situation. Edges show of preconditions to actions and actions on Nachbedinungungen.

Since some actions may have in any orders or even executed in parallel, but not others, will be described mutually exclusive actions on so-called mutex links.

Example

If the grant of a dishwasher are planned, would be conceivable Propositionsknoten " off ", " open ", " not open " and " granted ". " Open " An action would have "turned off" as a precondition and " not open " and " open " as Nachbedinung. A mutex link would now be "opened" and between " not open ".

Algorithm

The algorithm takes as input the problem formulation with STRIPS.

The algorithm can be divided into two parts:

In the first phase of the planning graph is expanded in the second phase of the task is in the planning graph for the solution sought.