Graph plan algorithm
The graph plan algorithm is an algorithm from the field of artificial intelligence . It is used to automatically find a sequence of actions that lead to a desired goal. 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 that is made up of proposition nodes and action nodes. It is visualized in layers, with the lowest layer being the literals of the start situation. Edges point from preconditions to actions and from actions to postconditions.
Since some actions can possibly be executed in any order or even in parallel, but others cannot, mutex links are used to describe mutex links.
example
If the loading of a dishwasher is to be planned, conceivable proposition nodes would be “switched off”, “open”, “not open” and “loaded”. An action “open” would have “switched off” and “not opened” as a precondition and “open” as a postcondition. A mutex link would now be between "open" and "not open".
algorithm
The algorithm needs the problem formulation with STRIPS as input .
The algorithm can be divided into two parts:
- The expansion of the planning graph
- Extraction of the solution
In the first phase, the planning graph is expanded; in the second phase, the task is searched for in the planning graph.
Individual evidence
- ↑ Introduction to AI. (No longer available online.) Archived from the original on September 4, 2014 ; Retrieved July 12, 2013 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.
- ↑ Günther Görz: Handbook of Artificial Intelligence . 4th edition. Oldenbourg Verlag, 2003, ISBN 3-486-27212-8 , p. 505 .
