AIMA Notizen

Inhalt

1. Planen
   
• im Unterschied zum Suchen:
• siehe auch http://www.rci.rutgers.edu/~cfs/472_html/Planning/Intro_Planning_472.html
• nutzt die (formale) Struktur des Problems um schnelle Lösungswege zu finden
• für "real world"-Probleme (z. B. Bauklötze spapeln)
• jeder Zustand im Suchraum muss vollständig spezifiziert (ja, nein, vielleicht) sein, Planzustände dagegen sind meist nur partiell in ihren relevanten Eigenschaften spezifiziert
• Suche ist lokal: an jedem Knoten muss ich mich für einen Variablenwert entscheiden und möglicherweise durch backtracking die verschiedenen Belegungen durchprobieren bis ich eine passende gefunden habe. beim Planen wird die Variable einfach passend eingeschränkt und später genau spezifiziert. das spart Backtracking
• ...
• problemlösende Agenten probieren aus, planende Agenten haben Wissen über Aktionen (ihre Vor- und Nachbedingungen) und nutzen dieses Wissen um nicht wahllos (bis auf die Heuristiken) herumzusuchen.
• Problemlösen durch Zerteilung in (nahezu) unabhängige Teilprobleme. ("nahezu" sorgt möglicherweise für suboptimale Lösungen...)
  
• STRIPS
• Einschränkung der Prädikatenlogik
• keine Funktionen
  
• Konjunktionen positiver Literale ohne Variablen und Funktionen als Zustände und Ziele
• Zustände
  
• eingeschränkt auf Konjunktionen positiver Literale ohne Variablen und Funktionen
• closed-world assumption: alles was nicht wahr ist, ist falsch
• Ziele sind Konjunktionen positiver Literale
• Aktionen
• Name und Parameter (=Signatur)
  
• Vorbedingungen als Konjunktion von positiven Literalen
• Effekt als Liste von positiven und negativen Literalen. positive Literale sind nach der Aktion gültig (add-list), negative sind ungültig (delete-list).
• STRIPS-Annahme: nur durch Effekte beschriebene Literale in einem Zustand ändern sich durch die Aktion (daher kein Frame-Problem).
• Lösung: eine (partiell) geordnete Menge von Aktionen die vom Ausgangszustand in einen Zielzustand überführt
• was STRIPS nicht kann:
• Funktionen
  
• unbestimmte Literale (immer entweder wahr oder falsch, closed-world)
• quantifizierte Variablen in Zielen
• Disjunktionen in Zielen
• bedingte Effekte (lassen sich natürlich mit mehreren Aktionen nachbilden)
• Gleichheits-/Ungleichheitsprüfung
  
• Typisierung der Variablen
• -> ADL, Action Description Language
• trotzdem kann man mit STRIPS ziemlich viel modelieren
  
2. Planen als Suchen im Zustandsraum
• Vorwärtssuche (auch: progressive search)
  
• nicht wirklich etwas neues
• nicht wirklich effizient, weil es meist zu viele abwegige Möglichkeiten gibt
• Rückwärtssuche im Zustandsraum (auch: regressive search)
  
• Beschränkung auf relevante Aktionen, die einen Teil (der Konjunktion) des Problems lösen
• Aktionen dürfen keine Teillösungen verwerfen (consistency)
• Heuristiken sind problemunabhängig
• Berechnung von vereinfachten Problemen, teilweise aufwändig zu berechnen
• Entfernung der Prämissen von den Aktionen
  
• Entfernung negativer Nebeneffekte von den Aktionen
  
3. partiell geordnetes Planen (partial-order planning, POP)
• least commitment Strategie (minimale Bindung)
  
• die Reihenfolge von Aktionen muss nicht immer spezifiziert werden
  
• sie kann partiell spezifiziert werden: A vor B, aber nicht unbedingt A direkt vor B
• implementiert als Suche im Raum der unvollständigen Pläne:
• ein unfertiger Plan besteht aus:
• Menge von Aktionen die der Plan ausführt
• Menge von Einschränkungen der Reihenfolge der Aktionen (dürfen nicht widersprüchlich sein: (A vor B) und (B vor A)
  
• Menge von kausalen Verbindungen zwischen Aktionen: "A erfüllt p für B" also darf C mit dem Effekt ¬p nicht zwischen A und B liegen. Kausale Verbindungen heißen deswegen auch protection intervals.
• Menge von offenen Prämissen.
  
• ein konsistenter Plan ohne offene Prämissen ist eine Lösung
  
• ein partial order planner versucht die Menge der Prämissen zu leeren ohne dabei Kontradiktionen zu erzeugen um eine Lösung zu finden.
  
• jede Serialisierung einer partiell geordneten Lösung ist eine total geordnete Lösung.
• der Algorithmus ist wie folgt:
• beginne mit dem leeren Plan, der nur die beiden "Aktionen" START und STOP, die Ordnung START vor STOP und die offenen Prämissen für STOP enthält
• die Nachfolgerfunktion eines Plans wählt eine Aktion mit einer offenen Prämisse und sucht diese Prämisse zu erfüllen. Dabei achtet sie darauf, dass keine Kontradiktionen entstehen (bzw. versucht sie zu lösen) und erzeugt für alle neuen konsistenten Pläne neue Zustände
• wenn keine Prämissen mehr erfüllt werden müssen terminiert der Algorithmus korrekt, da insgesamt nur konsistente Pläne erzeugt werden.
• der Algorithmus kann effizienter sein, wenn die Wahl der offenen Prämisse geschickt vorgenommen wird
  
• der Algorithmus teilt automatisch ein Problem in seine Teilprobleme, weil er immer nur eine Aktion und nie alle Aktionen für die Generierung der Nachfolgepläne auswählt
• weiteres least commitment: zu erfüllende Literale dürfen noch ungebundene Variablen enthalten, die erst später im Verlauf der Suche gebunden werden, je nachdem welche Bindungsmöglichkeiten sich noch ergeben.
• Möglichkeit der Einführung von Ungleichheits-Constraints um bestimmte Bindungen zu verhindern
  
4. Planungsgraphen
• wird inkrementell vom Anfangszustand aufgebaut, enthält jeweils mögliches Wissen
• Graphplan sucht rückwärts im Planungsgraphen nach einem (teils partiell geordneten) Plan
  
5. Planen mit Aussagenlogik
• SATPlan übersetzt das Planungsproblem in Aussagenlogik und benutzt einen Erfüllbarkeitsalgorithmus um ein Modell zu finden, das dann eine Lösung darstellt
• mehrere Varianten in der aussagenlogischen Darstellung mit ihren jeweiligen Vor- und Nachteilen
  
6. Vergleich von Planungsansätzen
• derzeit aktive Forschung und Entwicklung
• vor allem muss die Zustandsexplosion unter Kontrolle gebracht werden
• Zerteilbarkeit (oder annähernde)
  
• Serialisierbarkeit von Teilzielen
• gegenseitige Befruchtung
• z. B. Blackbox: übersetzt den Planungsgraphen in Aussagenlogik und sucht dann nach der Lösung
  

letzte Änderung: 22. Dezember 2004.