Database Reference
In-Depth Information
unvollstandiger
Plan
Plantransformation
Abbildung 11.12
Suchraum mit unvollstandigen Planen
11.7
Nichtklassische Planungssysteme
Wahrend die
STRIPS
-basierten Planungsverfahren klassische Verfahren genannt
werden, wurden in der Folge verschiedene Erweiterungen entwickelt, um die
STRIPS
anhaftenden Nachteile zu beseitigen, wobei als erstes die oben schon erwahnte Li-
nearitatsannahme zu nennen ist. Wie in Abbildung 11.6 angedeutet, besteht der
Suchraum bei
STRIPS
aus einem Graphen, dessen Knoten
STRIPS
-Datenbasen sind
und dessen Kanten Operatoranwendungen entsprechen.
Eine andere Vorgehensweise zur Planung besteht darin,
unvollstandige Plane
zu betrachten. Wahrend wir bisher davon ausgegangen waren, dass die Operatoren
in einem Plan linear geordnet sind, besteht ein unvollstandiger Plan aus einer Menge
von Operatoren, die nur partiell geordnet sind; derartige Plane werden daher auch
nichtlineare Plane
genannt. In dem nichtlinearen Plan
Op
3
Op
2
Op
1
Op
4
gibt es z.B. vier Operatoren, von denen
Op
1
vor
Op
2
und vor
Op
4
und
Op
2
vor
Op
3
ausgefuhrt werden soll; ob aber
Op
4
vor oder nach
Op
2
oder
Op
3
ausgefuhrt wird, ist
noch offen.
Der Suchraum beim Planen enthalt nun unvollstandige Plane, die durch Plan-
transformationen miteinander verknupft sind (vgl. Abbildung 11.12). Die wichtig-
sten Plantransformationsschritte, die einen unvollstandigen Plan in einen erweiter-
ten Plan uberfuhren, sind:
1. Hinzufugen eines Operators;
2. Anordnung eines Operators vor oder nach einem anderen Operator;
3. Instantiierung eines noch nicht vollstandig instantiierten Operators.