Consistent Actions im Regression Planning (Planning F. 37)

[Rodent Bait]

Auf Folie 37 (und entsprechend im RN) steht, dass beim Regression Planning nur konsistente Aktionen, also solche, die kein Unterziel rückgängig machen, verwendet werden dürfen. Ist das eigentlich immer zielführend?

Wenn ich an das bekannte Wolf-Ziege-Kohlkopf-Ruderboot-Beispiel denke, dann könnte das doch so aussehen:
Ausgangszustand: at(wolf,ufer1), at(ziege,ufer1), at(kohl,ufer1)
Zielzustand: at(wolf,ufer2), at(ziege,ufer2), at(kohl,ufer2)
Aktionen: rudere(Ausgangsufer,Zielufer) und rudere(Ausgangsufer,Zielufer,Mitwas).

Eine möglicher Plan:
1. rudere(ufer1,ufer2,ziege)
2. rudere(ufer2,ufer1)
3. rudere(ufer1,ufer2,kohl)
4. rudere(ufer2,ufer1,ziege)
5. rudere(ufer1,ufer2,wolf)
6. rudere(ufer2,ufer1)
7. rudere(ufer1,ufer2,ziege)

Alternative: Aktion 3 und 5 vertauscht. In jeder Variante macht Aktion 4 ein Teilziel, nämlich at(ufer2,ziege) wieder rückgängig. Könnte man dieses Problem also mit einem Regression-Planer nicht lösen?

[Tillmann]

Auf Folie 37 (und entsprechend im RN) steht, dass beim Regression Planning nur konsistente Aktionen, also solche, die kein Unterziel rückgängig machen, verwendet werden dürfen. Ist das eigentlich immer zielführend?

Eher nicht. Beispiel:

• Ausgangszustand: a
• Zielzustand: a, b
• Aktionen: p() add a precond b und q() add b delete a precond a

Der Zustandsraum sieht so aus:

1. \(a \,\,\, \to_q \,\,\, b\)
2. \(b \,\,\, \to_p \,\,\, a,\,b\)
3. \(a,\,b \,\,\, \to_p \,\,\, a,\,b\)
4. \(a,\,b \,\,\, \to_q \,\,\, a\)

Offensichtlich muß jeder Plan (1) enthalten, weil dies die einzige Kante ist, die b einführt. q ist aber nicht konsistent, weil Unterziel a gelöscht wird. Also gibt es keinen Plan, der nur konsistente Aktionen enthält, also kann ein Planer, der nur konsistente Aktionen in Betracht zieht, keinen Plan finden.


Warum werden denn beim Regression-Planing nur konsistente Aktionen berücksichtigt?

[Rodent Bait]

Warum werden denn beim Regression-Planing nur konsistente Aktionen berücksichtigt?

Tja, gute Frage. Wenn es eine Heuristik wäre, in dem Sinne, dass man zuerst alle konsistenten Aktionen probiert, bevor man eine inkonsistente in Erwägung zieht, könnte ich das ja noch eher verstehen. Aber in der Praxis wird es bei komplexeren Problemen doch immer mal wieder vorkommen, dass man im Zuge einer Problemlösung zwischendurch Teilziele erreicht, die dann aber noch mal umstoßen muss, um zum endgültigen Ziel zu gelangen.

[Tillmann]

Aber in der Praxis wird es bei komplexeren Problemen doch immer mal wieder vorkommen, dass man im Zuge einer Problemlösung zwischendurch Teilziele erreicht, die dann aber noch mal umstoßen muss, um zum endgültigen Ziel zu gelangen.

Man könnte die Probleme ja in die Klasse der bei Beschränkung auf konsistente Aktionen lösbaren und die Klasse der anderen teilen. Auch für Menschen sind häufig Probleme viel einfacher zu lösen, wenn man nur konsistente Aktionen betrachten muß, während das Ziege-Koplkopf-usw.-Problem auch für Menschen schwierig zu lösen ist, gerade weil der Suchraum durch die notwendige Einbeziehung nicht-konsistenter Aktionen viel größer wird.

Daraus ergeben sich für mich zwei Fragen:

• Kann man effizient feststellen, ob zur Lösung eines Problemes auch nicht-konsistente Aktionen benötigt werden?
• Was hat die Unterscheidung "Beschränkung auf konsistente Aktionen oder nicht" mit der Unterscheidung "progressive / regressive Planung" zu tun? (Oder steht das nur zufällig auf derselben Folie?)

[Rodent Bait]

während das Ziege-Koplkopf-usw.-Problem auch für Menschen schwierig zu lösen ist

Tja, aber das folgende Problem ist für die allermeisten Menschen sehr einfach zu lösen:

Startzustand: Ich im Haus, Haustür zu
Zielzustand: Ich draußen, Haustür zu

Regression Planning mit konsistenten Aktionen würde aber auch schon bei so was einfachem versagen.

Ich hab' heute in der Mensa Herrn Grieser auf die Frage angesetzt... mal sehen, was ihm dazu noch einfällt.

[grieser]

Ich hab' heute in der Mensa Herrn Grieser auf die Frage angesetzt... mal sehen, was ihm dazu noch einfällt.

Und der konnte deswegen die ganze Nacht nicht schlafen:-)))

Im Ernst, ich denke, der Denkfehler liegt darin, daß sie "Ziel" immer als globales Ziel betrachten, d.h. das, was wir am Ende erreichen wollen. In Wirklichkeit jedoch bezieht sich Konsistenz immer auf die aktuelle Liste der Teilziele; und aus dieser "verschwinden" ja immer die "erledigten" Ziele, d.h. in tieferen Ebenen des Suchbaums dürfen sie schon als negative Effekte auftreten, falls sie nicht mehr in der Teilzielliste stehen.

Zunächst zum Grund, warum wir Konsistenz der Aktionen fordern. Betrachten wir das Beispiel von Tillmann:

• Ausgangszustand: a
• Zielzustand: a, b
• Aktionen: p() add a precond b und q() add b delete a precond a

Rückwärtsplanung beginnt beim Ziel [a,b]
Wenn wir Aktion q anwenden (die inkonsitent ist), erhalten wir als neue Zielliste [a]. Damit haben wir bereits einen Plan gefunden, da diese im Startzustand enthalten ist.
Der Plan ist aber offensichtlich falsch.


Auf einem anderen Weg geht Regression übrigens ohne Probleme durch:
Rückwärtsplanung beginnt beim Ziel [a,b]
Die Aktion p ist relevant und consistent.
Als neue Zielliste erhalten wir .
In diesem Zustand ist die Aktion q konsistent (es wird keines der Teilziele rückgängig gemacht).
Als neue Zielliste ergibt sich [a] und wir sind fertig. Dieser Plan ist auch korrekt.

Also, man braucht die Konsistenzbedingung schon, um falsche Pläne zu verhindern.

Auch das Beispiel mit der Haustür geht durch:

Startzustand: Ich im Haus, Haustür zu
Zielzustand: Ich draußen, Haustür zu

Wir haben folgende Aktionen:

• öffnen: prec: zu; add: auf; del: zu
• schließen: prec: auf; add: zu; del: auf
• rausgehen: prec: drin, auf add: draußen; del: drin

Wir starten unsere Regression bei [draußen,zu].
Die Aktion schließen ist konsistent, es ergibt sich [draußen,auf].
Die Aktion rausgehen ist konsistent, es ergibt sich [drin,auf].
Und schließlich ist öffnen konsistent, es ergibt sich [drin,zu], fertig...

[Tillmann]

Erstmal vielen Dank für die ausführliche Antwort. Die Konsistenzprüfung soll also dafür sorgen, daß keine Aktionen für den Plan ausgewählt werden, die an dieser Stelle gar nicht auftauchen dürfen, weil sie ein Literal entfernen, was später noch gebraucht wird? In diesem Sinne entspräche die Prüfung auf Konsistenz beim Regressionsplanen der Prüfung auf Erfüllung der Preconditions beim Progressionsplanen. Tatsächlich hatte ich "subgoals" auf das globale Goal bezogen, nicht auf den aktuellen State.

Kann man Progressions- und Regressionsplanen als Suche im selben Zustandsraum darstellen?

• Ein Knoten ist eine Menge von Literalen. Zwischen zwei Knoten A und B ist eine Kante, wenn es ein Aktionsschema gibt, das sich zu einer Aktion mit \(precond \,\in\, A\), \(add \,\subseteq\, B\) und \(delete \,\cap\, B \,=\, \emptyset\) instatiieren läßt.
  
  Wenn X die Menge ist, die nur aus dem Startzustand besteht, und Y die Menge aller Zielknoten ist, dann sucht Progressionsplanen (Regressionsplanen) einen Weg von einem Knoten in X (Y) nach Y (X) im Zustandsraum (im dualen Zustandsraum, der durch herumdrehen aller Kanten entsteht).

Für das Progressionsplanen realisiert die Bedingung \(precond \,\in\, A\) die Anwendbarkeitsprüfung und die Bedingungen \(add \,\subseteq\, B\) und \(delete \,\cap\, B \,=\, \emptyset\) realisieren die Effekte einer Aktion. Für das Regressionsplanen realisiert die Bedingung \(add \,\subseteq\, B\) die Relevanzprüfung und \(delete \,\cap\, B \,=\, \emptyset\) die Konsistenzprüfung, und die Bedingungen \(precond \,\in\, A\) und \(add \,\subseteq\, B\) realisieren die Effekte einer Aktion.

Stimmt das? Ist das sinnvoll? Beim Vorwärts-Anwenden können ja durch add hinzugefügte Literale schon vor der Aktion im State enthalten sein, beim Rückwärts-Anwenden werden aber alle durch add hinzugefügte Literale gelöscht.

Kann man sich das Vorgehen eines Regressionplaners (schrittweise Umwandlung des Zieles bis alle geforderten Literale bereits im Startzustand enthalten sind) ähnlich vorstellen wie das Vorgehen eines top-down-Theorembeweisers (schrittweise Umwandlung des Zieles bis alle geforderte Terme bereits in den Hypothesen enthalten sind)?

[grieser]

In diesem Sinne entspräche die Prüfung auf Konsistenz beim Regressionsplanen der Prüfung auf Erfüllung der Preconditions beim Progressionsplanen.

Sinngemäß, aber nicht 1:1. Bei der Vorwärtssuche fkönnen Sie quasi eine Simulation durchführen, d.h. in jedem Schritt kennen sie den exakten zustand der Welt.

Bei der Regression haben Sie es mit unvollständigen Weltbeschreibungen zu tun, daran können sie auch nichts ändern. Die Konsistenzbedingung sorgt nun dafür, daß ein paar sinnlose Wege ausgeschlossen werden, andere dagegen bleiben erhalten. (In der Übung hatten wir bspw. Welten, in denen gleichzeitig auf_kiste und auf_boden galt....)

Tatsächlich hatte ich "subgoals" auf das globale Goal bezogen, nicht auf den aktuellen State.

Ich zunächst auch:-)

Kann man Progressions- und Regressionsplanen als Suche im selben Zustandsraum darstellen?

Nein, siehe oben.

[grieser]

Kann man sich das Vorgehen eines Regressionplaners (schrittweise Umwandlung des Zieles bis alle geforderten Literale bereits im Startzustand enthalten sind) ähnlich vorstellen wie das Vorgehen eines top-down-Theorembeweisers (schrittweise Umwandlung des Zieles bis alle geforderte Terme bereits in den Hypothesen enthalten sind)?

Sie können Fragen stellen...
Ich bin jetzt etwas überfragt, was die Theorembeweiser angeht, denke jedoch, daß der Vergleich hinkt. Theorembeweiser arbeiten üblicherweise in monotonen Logiken, und dort sollten m.E. Vorwärts- und Rückwärtssuche äquivalent sein. Beim STRIPS-Planen haben wir es mit einer nichtmonotonen Logik zu tun, das macht die Probleme beim Rückwärtsplanen.

[Rodent Bait]

Ich glaube, ich habe es jetzt auch verstanden und kann jetzt bis zur Übung noch ein wenig schlafen Vielen Dank für die ausführliche Erklärung!