A Probabilistic Framework for Hierarchical Goal Recognition

Diese Arbeit stellt das erste planungsbasierte probabilistische Framework für die hierarchische Zielerkennung vor, das die Struktur von Hierarchical Task Networks (HTNs) nutzt, um unter Unsicherheit präzisere Rückschlüsse auf die Ziele eines Agenten zu ziehen.

Das Wesentliche

Das Rätsel des „Was macht er da eigentlich?“-Detektivs

Stell dir vor, du sitzt in einem Café und beobachtest eine Person am Nachbartisch. Die Person nimmt eine Gabel, schneidet etwas an, greift nach einem Glas und wischt sich den Mund ab. Dein Gehirn arbeitet sofort auf Hochtouren: „Will die Person gerade einen Kuchen essen? Oder bereitet sie sich nur auf ein großes Abendessen vor?“

Wir Menschen sind Meister darin, aus kleinen Handlungen große Pläne zu lesen. Wir denken nicht nur in „Handbewegung A“ oder „Handbewegung B“, sondern in Hierarchien. Wir sehen nicht nur „Gabel heben“, sondern wir verstehen das Konzept „Essen“.

Das Problem:
Bisherige Computerprogramme für „Zielerkennung“ (Goal Recognition) waren wie sehr unflexible Detektive. Wenn ein Computer sehen wollte, ob jemand „Suppe kocht“, und die Person zwischendurch kurz aufstand, um ein Glas Wasser zu holen (eine völlig irrelevante Handlung), sagte der Computer sofort: „Fehler! Das passt nicht zum Rezept für Suppe. Die Person kocht keine Suppe!“ Der Computer war zu starr. Er konnte nicht mit Unsicherheit umgehen oder mit „Störgeräuschen“ (wie dem Glas Wasser) umgehen.

Die Lösung des Papers (Die „Probabilistische Hierarchie-Methode“):
Die Forscher haben nun ein System entwickelt, das viel mehr wie ein echter menschlicher Detektiv arbeitet. Sie nutzen zwei Superkräfte:

1. Die „Baumstruktur“ (Hierarchie)

Anstatt jede einzelne Bewegung wie eine isolierte Perle auf einer Schnur zu sehen, betrachtet der Computer die Handlungen wie die Äste eines Baumes.

• Der Stamm: Das große Ziel (z. B. „Ein Festmahl vorbereiten“).
• Die Äste: Die Teilaufgaben (z. B. „Vorspeise machen“, „Hauptgang kochen“).
• Die Blätter: Die winzigen Einzelbewegungen (z. B. „Zwiebel schneiden“).

Wenn der Computer sieht, wie die „Blätter“ wackeln, kann er viel leichter vorhersagen, welcher „Ast“ oder welcher „Stamm“ sich dahinter verbirgt.

2. Die „Wahrscheinlichkeits-Brille“ (Probabilistik)

Das ist der eigentliche Clou. Anstatt zu sagen: „Das ist Ziel A oder es ist nichts!“, sagt der Computer jetzt: „Ich bin mir zu 80 % sicher, dass es Ziel A ist, zu 15 % Ziel B und zu 5 % einfach nur Chaos.“

Stell dir das wie eine Detektiv-Skala vor:
Wenn die Person plötzlich etwas völlig Unpassendes tut – zum Beispiel eine Serviette faltet, während sie eigentlich Suppe kocht – bricht das System nicht zusammen. Es sagt nicht: „Plan gescheitert!“, sondern es denkt sich: „Hm, das passt zwar nicht perfekt zum Rezept, aber die restlichen 90 % der Bewegungen passen immer noch so gut zur Suppe, dass die Wahrscheinlichkeit für 'Suppe kochen' immer noch sehr hoch ist.“

Zusammenfassend: Was haben die Forscher geschafft?

Sie haben eine mathematische Formel gebaut, die:

1. Strukturiert denkt: Sie nutzt die Logik von „großen Plänen, die aus kleinen Schritten bestehen“ (HTNs).
2. Flexibel bleibt: Sie kann mit „Störfaktoren“ umgehen (wenn jemand mal kurz vom Weg abkommt).
3. Unsicherheit managt: Sie gibt keine Ja/Nein-Antworten, sondern liefert eine Liste von Möglichkeiten, sortiert nach Wahrscheinlichkeit.

Das Ergebnis: In Tests (wie in einer virtuellen Küche) war dieser neue „Detektiv“ viel genauer als die alten, starren Systeme – besonders dann, wenn man nur Bruchteile der Handlungen sehen konnte oder wenn die Person sich mal „unlogisch“ verhalten hat.

Kurz gesagt: Der Computer lernt endlich, nicht nur auf die einzelnen Schritte zu starren, sondern das „große Ganze“ zu verstehen – selbst wenn das Leben ein bisschen chaotisch ist.

Technische Zusammenfassung

Technische Zusammenfassung: Ein probabilistischer Rahmen für hierarchische Zielerkennung

1. Problemstellung

Die Zielerkennung (Goal Recognition) befasst sich mit der Aufgabe, aus beobachtetem Verhalten eines Agenten dessen Absichten (Ziele) abzuleiten. In realen Szenarien treten zwei wesentliche Herausforderungen auf:

• Hierarchische Struktur: Menschliches Handeln ist hierarchisch organisiert (z. B. besteht „Kochen“ aus „Vorbereiten“ und „Garen“). Bestehende Methoden nutzen oft flache Aktionsmodelle und ignorieren diese Struktur.
• Unsicherheit und Rauschen: Beobachtungen sind oft unvollständig, verrauscht oder enthalten „exogene Aktionen“ (Handlungen, die nicht zum eigentlichen Ziel gehören, wie z. B. ein versehentliches Aufheben eines Gegenstands).

Bisherige Ansätze auf Basis von Hierarchical Task Networks (HTNs) waren weitgehend deterministisch. Sie konnten lediglich entscheiden, ob eine Hypothese mit den Beobachtungen kompatibel ist (Ja/Nein), konnten aber keine Wahrscheinlichkeiten berechnen, um konkurrierende Hypothesen zu ranken oder mit Rauschen umzugehen.

2. Methodik

Die Autoren führen einen probabilistischen Rahmen ein, der die HTN-Zielerkennung als Bayessches Inferenzproblem formuliert. Das Ziel ist die Berechnung der Posterior-Verteilung $P(N_g | \hat{o}, s_0)$ über die Zielhypothesen $N_g$ gegeben die Beobachtungen $\hat{o}$.

Das dreistufige generative Modell:
Um die Likelihood $P(\hat{o} | N_g, s_0)$ zu schätzen, schlagen die Autoren einen Prozess vor, der die Entstehung der Beobachtungen simuliert:

1. Netzwerk-Dekomposition (Stage I): Ein Ziel wird mittels HTN-Methoden in primitive Aufgaben zerlegt. Die Auswahl der Methoden folgt einer Boltzmann-Verteilung (Softmax), wobei kostengünstigere Dekompositionen wahrscheinlicher sind.
2. Ausführbare Linearisierung (Stage II): Die dekomponierten Aufgaben werden in eine Sequenz von Aktionen umgewandelt. Die Wahrscheinlichkeit hängt von der Verfügbarkeit (Preconditions) der Aktionen ab.
3. Beobachtungsmodell (Stage III): Hier wird modelliert, wie die tatsächlichen Beobachtungen $\hat{o}$ aus dem geplanten Pfad $\pi$ hervorgehen. Dies berücksichtigt auch die Dauer der Ausführung (Progress Prior) und die Übereinstimmung der Sequenz (Alignment Likelihood).

Inferenz-Approximation:
Da die exakte Berechnung der Likelihood mathematisch nicht handhabbar (intractable) ist, nutzen die Autoren eine Approximation. Sie verwenden einen Standard-HTN-Planer, um zwei repräsentative Ausführungen zu finden:

• Eine beobachtungskonsistente Ausführung (die die Beobachtungen erklärt).
• Eine unbeschränkte Ausführung (die das Ziel ohne Rücksicht auf die Beobachtungen optimal verfolgt).
  Das Verhältnis dieser beiden Wahrscheinlichkeiten dient als Schätzer für die Likelihood. Um die Rechenlast zu begrenzen, wird ein Top-K-Verfahren angewandt, das nur die vielversprechendsten Hypothesen detailliert berechnet.

Umgang mit exogenen Aktionen:
Das Framework erweitert die Theorie um die Task-Insertion-Semantik. Dies erlaubt es, Handlungen in den Plan einzufügen, die nicht durch die HTN-Hierarchie des Ziels legitimiert sind. Dadurch kann das Modell auch dann noch eine hohe Wahrscheinlichkeit für ein Ziel berechnen, wenn der Agent „unlogische“ Zwischenschritte macht.

3. Kernbeiträge

• Erster probabilistischer HTN-Rahmen: Integration von hierarchischer Struktur mit Bayesscher Inferenz für die Zielerkennung.
• Generatives Modell: Ein dreistufiger Prozess, der die Hierarchie, die Ausführbarkeit und die Beobachtungsgüte mathematisch verknüpft.
• Praktische Implementierung: Ein effizientes Inferenzverfahren, das bestehende, kommerzielle HTN-Planer nutzt, anstatt neue komplexe Algorithmen zu benötigen.
• Robustheit: Theoretische und empirische Belege dafür, dass das Modell besser mit Rauschen und exogenen Aktionen umgehen kann als rein deterministische Modelle.

4. Ergebnisse

Die Evaluierung erfolgte in den Benchmarks Kitchen und Monroe:

• Verbesserte Genauigkeit: Das Modell übertrifft den aktuellen Stand der Technik (Baseline) signifikant in der Top-k-Genauigkeit (insbesondere Top-3 und Top-5), besonders wenn nur ein kleiner Teil der Handlung beobachtet wurde.
• Robustheit bei Teilbeobachtung: Selbst bei nur 20 % der beobachteten Aktionen liefert das Modell bessere Vorhersagen als deterministische Ansätze.
• Effizienz: Die Rechenzeit steigt zwar moderat an (von ca. 5 auf 24 Sekunden pro Instanz), was für die meisten praktischen Anwendungen jedoch ein vertretbarer Kompromiss für die deutlich höhere Zuverlässigkeit ist.
• Sanity Check (Exogene Aktionen): Während deterministische Modelle bei einer einzigen zusätzlichen, irrelevanten Aktion scheitern oder falsche Ziele wählen, bleibt das probabilistische Modell stabil.

5. Bedeutung

Die Arbeit ist wegweisend, da sie die Brücke zwischen der symbolischen KI (HTN-Planung) und der probabilistischen Inferenz schlägt. Sie bewegt die Zielerkennung weg von einer rein theoretischen „Passend oder Nicht“-Prüfung hin zu einem robusten, realitätsnahen System, das Unsicherheiten und menschliches, teils suboptimales Verhalten mathematisch fundiert verarbeiten kann.