AIMA Notizen

Inhalt

• ein formal definiertes Problem besteht aus
• Startzustand des Agenten
• Nachfolgerfunktion für die möglichen Folgezustände des Agenten; definiert implizit den Zustandsraum des Problems der sich als Graph darstellen lässt
• Menge von Zielzuständen oder Testfunktion die für Zustände bestimmt ob sie Zielzustände sind
• Kostenfunktion die den Kanten des Zustandsgraphen positive Kosten zuordnet
• die Lösung eines Problems ist ein Pfad vom Start- zu einem Zielzustand; die beste Lösung ist jene mit minimalen Kosten
• die Lösung von Problemen erfordert eine Abstraktion von den Agentenzuständen und seinen möglichen Aktionen hin zu größeren Zusammenfassungen von Zuständen
• Beispielprobleme:
• 8-Damen-Problem
• Streckenplanung
• Traveling-Salesman-Problem
• Roboternavigation
• VLSI-Layout
• ...
• Bewertung von Suchstrategien
• Vollständigkeit
• Optimalität: die Lösung mit den geringsten Kosten wird gefunden
  
• Zeit-Komplexität
  
• Platz-Komplexität
  
• Drei Werte:
• b: Verzweigungsfaktor
• d: Tiefe des flachsten Zielknotens
• m: maximale Länge eines Pfades im Suchraum
  
• Suchstrategien (blinde Strategien)
• anwendbar für vollständig beobachtbare und deterministische Umwelten in denen die Folgen von Aktionen bekannt sind.
  
• Breitensuche
• Knoten mit der niedrigsten Tiefe werden expandiert
  
• Platzkomplexität: O(b^d+1)
• keine Probleme bei zyklischen Zustandsräumen
• optimal für Probleme mit uniformen Kosten
  
• uniform-cost search
• es werden nicht die Knoten mit der niedrigsten Tiefe expandiert, sondern jene mit den niedrigsten Kosten
  
• gleiche Komplexität wie Breitensuche
• optimal
  
• Tiefensuche
• Knoten mit der größten Tiefe wird expandiert
• geringe Speicheranforderung O(b*m + 1)
  
• nicht optimal
• terminiert nicht für zyklische Zustandsräume
• tiefenbeschränkte Suche
• sucht nur bis in eine definierte Tiefe
• terminiert, sonst wie Tiefensuche
• iterativ vertiefende Tiefensuche
• geringe Speicheranforderungen
• bei gleichmäßigem (und großem) Verzweigungsfaktor besonders günstig
• tatsächlich effizienter als Breitensuche
• Breitensuche muss auch einige Knoten ein Niveau unterhalb des Zielknotens erzeugen (nämlich die Tochterknoten der Knoten auf Niveau des Zielknotens, die kein Zielknoten sind).
• iterativ vertiefende Tiefensuche ist in der Regel die beste blinde Suchstrategie wenn der Suchraum groß und die Zieltiefe unbekannt ist.
  
• Suche nach iterativ steigenden Kosten
• ähnlich der iterativ vertiefenden Tiefensuche, aber weniger effizient, da ein hoher Overhead erzeugt wird
• bidirektionale Suche
• nur möglich, wenn
• das oder die Ziele bekannt (und nicht zu zahlreich) sind
• Vorgängerknoten im Suchbaum effizient berechnet werden können
• Komplexität ist 2 * b^d/2 anstatt b^d
• einer der beiden Suchbäume muss im Speicher gehalten werden (-> Breitensuche), damit die Knoten der beiden Bäume verglichen werden können
• Tabelle der blinden Suchstrategien auf Seite 81.
• Mehrfacharbeit vermeiden
• Algorithmen die die Vergangenheit vergessen, wiederholen sie
• Suche in einem Graphen anstatt eines Baumes
  
• in vielen Problemen kommen Knoten mehrfach vor
• um die Effizienz zu steigern sollte jeder Knoten nur einmal expandiert werden
• Tiefensuche terminiert dadurch, weil Zyklen gefunden und verworfen werden können (ansonsten aber kein Vorteil für Tiefensuche)
• komplex, da alle Knoten im Speicher gehalten (und gegen sie verglichen) werden müssen
• Suchraum wird nicht mehr durch einen Suchbaum, sondern einen Suchgraphen beschrieben. Dieser kann direkt expandiert werden:
• unfertige Knoten
• fertige Knoten
• Suche mit partieller Information
• unbekannte Information (sensorless problems)
• der Agent hat keine vollständigen Informationen über seine Umwelt (zum Beispiel weil ein erforderlicher Sensor dafür fehlt)
• der Agent raisoniert nicht direkt über Zustände der Welt, sondern über Mengen von möglichen Zuständen
• durch geschickte Wahl der Aktionen kann er sicherstellen, dass er am Ende tatsächlich in einem Zielzustand ist (bzw. dass aller Elemente der Menge der möglichen Zustände Zielzustände sind).
  
• später bekannte Information (contingency problems)
• die Sensoren liefern nach der Durchführung neue, ergänzende Informationen
• Lösungen auf Kontingenz-Probleme sind baumförmig, bei denen Verzweigungen an Stellen auftreten, bei denen das weitere Vorgehen von den Sensorergebnissen abhängen
  
• Erkundungsprobleme
• der Agent kennt nicht die ganze Umwelt, hat aber die Chance, später noch entsprechendes Wissen zu erlangen.
• Spezialfall der contingency problems
  

letzte Änderung: 20. Dezember 2004.