|
Planungsverfahren erzeugen Folgen elementarer Aktionen, die einen definierten Startzustand in einen Zielzustand überführen. Hierzu existieren unterschiedlichste Ansätze und Algorithmen (STRIPS, NLP, HTN-planning, SAT-planning, GRAPHPLAN u.a.m). Eine Vielzahl dieser Ansätze generiert nichtlineare Pläne, die die Reihenfolge der elementaren Aktionen nur partiell bestimmen. Solche Pläne lassen sich durch gerichtete, azyklische Graphen darstellen. Die Knoten der Graphen repräsentieren Aktionen, die Kanten definieren eine zeitliche Ordnungsbeziehung zwischen den Aktionen.
Die intuitive und zugängliche Darstellung von Graphen ist ein aktives Forschungsthema, da dies in vielen Bereichen eine Schlüsselrolle in Softwarewerkzeugen einnimmt. Während das Berechnen einer optimalen Darstellung (z.B. Minimierung der Kantenüberschneidungen) im allgemeinen Falle exponentielles Laufzeitverhalten zeigt, gibt es für viele eingeschränkte Spezialfälle effiziente Algorithmen. Ob sich ein solcher für eine konkrete Instanz eines Spezialfalls eignet, kann im Allgemeinen nur durch intensives Testen entschieden werden.
Der im Rahmen dieser Diplomarbeit entstandene Ansatz weist als Besonderheit auf, dass er zum einen die Fähigkeit besitzt, einen gegebenen Planungsgraphen übersichtlich darzustellen und zum anderen bei Modifikationen des Graphen die Ähnlichkeit weitgehend erhält.
|