GOAP: Aktionsfolge per Suche ermitteln und ihre Ausführung validieren

Suche über mögliche Weltzustände

Goal-oriented Action Planning (GOAP) sucht nach einer Abfolge von Aktionen, die einen gewünschten Weltzustand herbeiführt. Jede Aktion definiert Vorbedingungen, Effekte und Planungskosten. Die Suche arbeitet auf hypothetischen Zuständen; erst danach führt die Laufzeitumgebung die gewählten Aktionen aus. Orkin beschreibt diesen Ansatz in seiner ursprünglichen Erläuterung zu F.E.A.R., und ReGoap bietet eine konkrete Implementierung, in der Planung und Ausführung getrennte Zuständigkeiten sind. [1][2]

Dem Modell ausreichend Information geben

Fakten abbilden, die tatsächlich beeinflussen, ob eine Aktion verfügbar ist. Einen Schlüssel zu besitzen und vor einer verschlossenen Tür zu stehen, sind zwei verschiedene Bedingungen. Für jede Aktion festlegen, was sie hinzufügt, entfernt oder verbraucht, und verhindern, dass die Suche unbekannte Fakten stillschweigend als bestätigt behandelt. Die Kosten sollten den Zielkonflikt ausdrücken, der optimiert wird, etwa Zeit- oder Ressourcenverbrauch, und zwar in vergleichbaren Einheiten. Ein günstiger Plan ist nur innerhalb dieses Modells günstig.

Durchgerechnetes Beispiel: Stromversorgung auf zwei Wegen wiederherstellen

In einem fiktiven Beispiel befindet sich ein Worker in einem Lager ohne Sicherung; der Generator ist ausgeschaltet. Das Ziel lautet powerOn = true. Ein möglicher Plan besteht aus FetchFuse mit Kosten 2, gefolgt von ReachGenerator mit Kosten 3 und InstallFuse mit Kosten 1. Für den Einbau sind sowohl die Sicherung als auch die Anwesenheit am Generator erforderlich; dabei wird die Sicherung verbraucht und der Strom eingeschaltet. Die Gesamtkosten betragen 2 + 3 + 1 = 6.

Ein alternativer Plan besteht aus ReachGenerator und anschliessend HandCrank, das vor Ort Kosten von 5 verursacht, insgesamt also 3 + 5 = 8. Ist eine Sicherung vorhanden, ist der erste modellierte Weg günstiger. Ist das Lager leer, muss FetchFuse unverfügbar sein, und der zweite Weg bleibt möglich. Es handelt sich um frei erfundene Planungskosten, nicht um gemessene Aktionsdauern.

Ausführung in der sich verändernden Welt

Vor dem Start jeder Aktion die relevanten Bedingungen in der realen Welt erneut prüfen. Umkämpfte Ressourcen über das Gameplay-System reservieren; dass der Planer eine Sicherung findet, reserviert sie noch nicht. Bestätigte Weltfakten erst dann aktualisieren, wenn der Effekt zur Laufzeit tatsächlich eingetreten ist, statt die vorhergesagten Effekte nach Abschluss der Planung in die Realität zu übernehmen.

Einen Diagnose-Trace erstellen, der das Ziel, die Ausgangsfakten, die gewählten Aktionsbindungen, die geschätzten Kosten und die Ausführungsergebnisse enthält. Die Sicherung nach der Planung, aber vor dem Abholen entfernen. Den Weg zum Generator sperren. Den Worker während des Einbaus unterbrechen. Prüfen, dass ein Fehlschlag Reservierungen freigibt, den bekannten Zustand aktualisiert und entweder eine Neuplanung auslöst oder einen expliziten Fallback wählt. Vermeiden, denselben unmöglichen Plan endlos erneut zu versuchen.

Suche und ihre Grenzen kontrollieren

Viele mögliche Ziele vervielfachen die Aktionsbindungen und vergrössern den Suchraum. Den Aufwand pro Planungsanfrage begrenzen und unterscheiden, ob das Budget erschöpft ist oder nachgewiesen wurde, dass kein Plan existiert. Einen Cache nur so lange verwenden, wie seine Annahmen gültig bleiben. Kurze Pläne lassen sich leichter nachvollziehen, doch ein zu kurzer Planungshorizont kann notwendige Vorbereitungsschritte übersehen. GOAP koordiniert nicht automatisch mehrere Worker, erfindet keine fehlenden Aktionen und sagt keine nicht modellierten Folgen voraus. Den Erfolg sowohl an der gültigen Ausführung als auch am beabsichtigten Verhalten messen.

Quellen

• [1] Three States and a Plan: The A.I. of F.E.A.R. — Jeff Orkin, Game Developers Conference 2006.
• [2] ReGoap — luxkun und ReGoap-Mitwirkende.