Information About ™Graphplan |
| CATEGORIES ABOUT GRAPHPLAN | |
| artificial intelligence | |
| algorithms | |
|
The graph used by graphplan ''is not'' the search space graph, a graph in which possible states are nodes and edges indicate reachability. The nodes of the graph are instead conditions and actions, arranged into alternate levels of conditions and actions. The conditions of the first levels are those initially true. The third level contains all conditions that can actually be made true at the second time point by executing some actions, etc. The odd levels contain the actions that can be perfomed at each time step. By definition, each level (of actions or conditions) can be built from the previous one (of conditions or actions, respectively). A level of action can contain two actions that can be executed in isolation but not together. As a result, the next level of conditions can contain conditions that cannot be made true at the same time because they are made true by actions that cannot all be executed at the same time. Graphplan stores incompatibility of actions and conditions at each level, and uses them to determine the incompatibilities at the next level. The graph produced by graphplan contains all conditions that can be made true and all actions that can be executed at some time point, but can also contain other conditions and actions. The actual search for a plan can be done by Backward Chaining (starting from the goal and recursively establishing which subgoals have to be reached to reach the goal). The graph is used in this phase to reduce the number of possibilities the algorithm has to consider. REFERENCES
EXTERNAL LINKS |
|
|