Planungsgraphen und Heuristiken

Planungsgraphen und domänenunabhängige Heuristiken sind die Techniken, die die klassische Planung schnell gemacht haben, indem sie die Erreichbarkeit kompakt analysierten und die Distanz von einem Zustand zum Ziel automatisch abschätzten.

Definition

Ein Planungsgraph ist eine geschichtete Struktur, die Propositionen- und Aktionsebenen mit Mutex-Einschränkungen verschränkt, um die Erreichbarkeit zu approximieren; Planungsheuristiken sind Funktionen, die oft aus solchen Strukturen oder aus delete-relaxierten Problemen berechnet werden und die Kosten schätzen, um das Ziel von einem Zustand aus zu erreichen.

Scope

Dieses Thema behandelt die Datenstruktur des Planungsgraphen, die von Graphplan eingeführt wurde, einschließlich der Ebenen von Propositionen und Aktionen und der Mutual-Exclusion (Mutex)-Beziehungen, die erfassen, welche Fakten und Aktionen nicht gleichzeitig auftreten können, sowie die Familie der domänenunabhängigen Heuristiken, die aus relaxierten Problemen (insbesondere unter Ignorierung von Löscheffekten) abgeleitet werden und moderne heuristische Suchplaner antreiben. Es wird behandelt, wie Erreichbarkeitsinformationen berechnet und zur Steuerung der Suche verwendet werden. Das zugrunde liegende klassische Planungsmodell wird im verwandten Thema behandelt.

Core questions

• Wie stellt ein Planungsgraph erreichbare Propositionen und Aktionen Ebene für Ebene dar?
• Was sind Mutex-Beziehungen und wie erfassen sie die Inkompatibilität zwischen Fakten und Aktionen?
• Wie wird die Delete-Relaxation verwendet, um zulässige oder informative Planungsheuristiken abzuleiten?
• Wie wandeln diese Heuristiken die Planung in eine effiziente heuristische Suche um?

Key concepts

• Planungsgraph
• Propositionen- und Aktionsebenen
• gegenseitiger Ausschluss (Mutex)
• Graphplan
• Delete-Relaxation
• h-max- und h-add-Heuristiken
• FF-Heuristik und relaxierte Pläne
• heuristische Vorwärtssuche

Key theories

Planungsgraph und Graphplan

Graphplan erstellt einen Planungsgraphen, der kompakt kodiert, welche Propositionen und Aktionen auf jeder Ebene erreichbar sind und welche Paare sich gegenseitig ausschließen, und extrahiert dann einen Plan, indem er rückwärts durch diese Struktur sucht, was die Planung dramatisch beschleunigt.

Delete-Relaxations-Heuristiken

Das Ignorieren der Löscheffekte von Aktionen führt zu einem relaxierten Planungsproblem, das viel einfacher zu lösen ist; die Kosten der Lösung dieser Relaxation liefern informative, oft zulässige Heuristiken (wie h-max und h-add und die FF-Heuristik), die die Vorwärtssuche leiten.

Heuristische Suchplanung

Modernste klassische Planer kombinieren automatisch abgeleitete Heuristiken mit Best-First- oder Greedy-Suche und Verbesserungen wie bevorzugten Operatoren, wodurch eine starke allgemeine Leistung in verschiedenen Domänen erzielt wird.

Clinical relevance

Planungsgraphen und Delete-Relaxations-Heuristiken sind die Kerntechnologie von wettbewerbsgewinnenden Planern, die in der Robotik, Logistik und autonomen Steuerung eingesetzt werden, wo sie domänenunabhängigen Planern ermöglichen, große Probleme schnell ohne handgefertigte Suchführung zu lösen.

History

Graphplan von Blum und Furst (1995, Journalversion 1997) führte den Planungsgraphen ein und revolutionierte die Planungsgeschwindigkeit. Die späten 1990er und 2000er Jahre sahen den Aufstieg der Delete-Relaxations-Heuristiken, wobei der FF-Planer (Hoffmann und Nebel, 2001) und später Fast Downward (Helmert, 2006) die heuristische Vorwärtssuche als dominanten Ansatz etablierten.

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

Was ist ein Mutex in einem Planungsgraphen?

Eine Mutex-Beziehung (Mutual Exclusion) kennzeichnet zwei Propositionen oder zwei Aktionen, die nicht beide auf derselben Ebene gelten oder angewendet werden können, zum Beispiel weil eine Aktion eine Vorbedingung der anderen löscht. Mutexes machen den Planungsgraphen zu einer genaueren Annäherung an die wahre Erreichbarkeit.

Warum liefert das Ignorieren von Löscheffekten eine nützliche Heuristik?

Ohne Löscheffekte macht das Erreichen eines Ziels niemals ein anderes rückgängig, sodass das relaxierte Problem viel einfacher zu lösen und niemals schwieriger als das Original ist. Die Kosten des relaxierten Plans sind daher eine Untergrenze oder eine informierte Schätzung der tatsächlichen Kosten, was sie zu einer effektiven Heuristik zur Steuerung der Suche macht.