Graphplan-Algorithmus

Der Graphplan-Algorithmus ist ein Algorithmus aus dem Gebiet der künstlichen Intelligenz. Er dient dem automatischen Finden einer Folge von Aktionen, die zu einem gewünschten Ziel führen. Die Lösung wird mit Hilfe eines sog. Planungsgraphen in polynomieller Zeit gefunden.

Planungsgraph

Der Planungsgraph ist ein bipartiter, gerichteter Graph, der aus Propositionsknoten und Aktionsknoten aufgebaut ist. Er wird in Schichten visualisiert, wobei die unterste Schicht Literale der Startsituation sind. Kanten zeigen von Vorbedingungen auf Aktionen und von Aktionen auf Nachbedingungen.

Da einige Aktionen eventuell in beliebigen Reihenfolgen oder sogar parallel ausführbar sind, andere jedoch nicht, werden sich gegenseitig ausschließende Aktionen über sog. Mutex-Links beschrieben.

Beispiel

Soll das Einräumen einer Spülmaschine geplant werden, so wären vorstellbare Propositionsknoten „ausgeschaltet“, „geöffnet“, „nicht geöffnet“ und „eingeräumt“. Eine Aktion „öffnen“ hätte als Vorbedingung „ausgeschaltet“ und „nicht geöffnet“ und als Nachbedingung „geöffnet“. Ein Mutex-Link wäre nun zwischen „geöffnet“ und „nicht geöffnet“.

Algorithmus

Der Algorithmus benötigt als Eingabe die Problemformulierung mit STRIPS.

Der Algorithmus lässt sich in zwei Teile unterteilen:

1. Die Expansion des Planungsgraphen
2. Die Extraktion der Lösung

In der ersten Phase wird der Planungsgraph erweitert, in der zweiten Phase wird in dem Planungsgraphen nach der Lösung der Aufgabe gesucht.