Consistent Actions im Regression Planning (Planning F. 37)

Moderator: Einführung in die Künstliche Intelligenz

Benutzeravatar
Rodent Bait
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 26. Apr 2005 14:50
Wohnort: Darmstadt
Kontaktdaten:

Consistent Actions im Regression Planning (Planning F. 37)

Beitrag von 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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Re: Consistent Actions im Regression Planning (Planning F. 3

Beitrag von Tillmann »

Rodent Bait hat geschrieben: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?

Benutzeravatar
Rodent Bait
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 26. Apr 2005 14:50
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von 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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag von Tillmann »

Rodent Bait hat geschrieben: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?)

Benutzeravatar
Rodent Bait
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 26. Apr 2005 14:50
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von 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
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 16. Dez 2003 14:12

Beitrag von grieser »

Rodent Bait hat geschrieben: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:
Rodent Bait hat geschrieben:
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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag von 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
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 16. Dez 2003 14:12

Beitrag von grieser »

Tillmann hat geschrieben: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....)
Tillmann hat geschrieben:Tatsächlich hatte ich "subgoals" auf das globale Goal bezogen, nicht auf den aktuellen State.
Ich zunächst auch:-)
Tillmann hat geschrieben:Kann man Progressions- und Regressionsplanen als Suche im selben Zustandsraum darstellen?
Nein, siehe oben.

grieser
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 16. Dez 2003 14:12

Beitrag von grieser »

Tillmann hat geschrieben: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.

Benutzeravatar
Rodent Bait
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 26. Apr 2005 14:50
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Rodent Bait »

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

Antworten

Zurück zu „Einführung in die Künstliche Intelligenz“