Problem Solving (via Search) PDF

Problem Solving (via Search) Formalisierung des Suchproblems Problem lösender Agent Stammen aus Goal-based Agent Verwenden atomare Repräsenta8onen von Weltzuständen Problemlösende Agenten agieren ra8onal à indem sie Ziele verfolgen (binär: erfüllt/nicht erfüllt)...

Problem Solving (via Search) Formalisierung des Suchproblems Problem lösender Agent Stammen aus Goal-based Agent Verwenden atomare Repräsenta8onen von Weltzuständen Problemlösende Agenten agieren ra8onal à indem sie Ziele verfolgen (binär: erfüllt/nicht erfüllt) o Probleme können auf Grundlage von Zielen modelliert werden Kann vom Benutzer oder Agenten selbst durchgeführt werden o Formulierte Problem durch Suche nach Lösung gelöst Lösung besteht aus Sequenz von Ak8onen(„Pfad“) à führen zu Zielzuständen Pseudocode: Einmal im Voraus planen und Ak8onen ausführen Schri4weise zur Herangehensweise an Suchproblemen „Formulate, search, execute“ Agentenprozedur 1. Zielformulierung a. Wich8g, weil Ziele sind abstrakt b. Ziele helfen dabei à Verhalten von Agenten zu organisieren (durch Limita8on aktueller Ziele) c. Ziele ermöglichen Abstrak8on von allen denkbaren Zwischenhandlungen à die in realer Welt notwendig sind d. Ziele als Gruppe von Weltzuständen repräsen8ert à für die Ziele erfüllt sind e. Ziel nicht unbedingt Zustand, kann auch abstrakte EigenschaUen des Zustands sein à z.B. Staubsaugerroboter: alle Räume sind sauber 2. Problemformulierung (PEAS) a. Welche Zustände und Ak8onen muss Agent in Betracht ziehen à um Ziel zu erreichen = was muss Agent über Umwelt wissen b. Formal: geeigneten Zustandsraum (S) und Ak8onsraum (A) definieren 3. Lösungssuche a. Agent pflegt interne „Karte“/internen Plan à welche Ak8onen führen zu welchen Zustand? (=Transi8onsmodell) b. Agent kann „mental“ Zustands-Ak8ons-Zustandssequenzen (state-ac8on-state) planen à führen letztendlich zum Zielzustand c. Suche ist Denkprozess à wird vor tatsächlichem Agieren ausgeführt 4. Ausführung von gefundenen Lösungen a. Sobald Agent Sequenz gefunden à kann er Schri` für Schri` Ak8onen ausführen b. Sobald Lösungssequenz erschöpU à Agentenprogramm beendet à oder neues Ziel kann formuliert werden Suchproblem formal durch 5 Komponenten beschrieben o Ini8alzustand § Start des Agenten in Realwelt § Bei t=0 (bis n-Zustand) o Ak8onsraum § Mögliche verfügbare Ak8onen für aktuellen Zustand s § Nicht jede Ak8on kann in jedem Zustand ausgeführt werden o Transi8onsfunk8on/-modell § Ergebnis einer Ak8on a auf Zustand s der Welt § Gibt nächsten (neuen) Zustand s‘ zurück à resul8ert aus Ak8on a im Zustand s o Zielteshunk8on § Bes8mmt, ob vorgegebener Zustand s Zielzustand ist oder überprüiare EigenschaU erfüllt o Pfadkostenfunk8on § Bewertet Ak8onsfolge im Gesamten § Weist numerische Kosten zu Pfad (Sequenz von Ak8onen) zu § Annahme, dass Pfadkosten die Summe der nicht-neg. Ak8ons-(Schri`)-kosten c(s,a,s‘) sind Zustandsraum (State space) [Graph] Menge aller Zustände à von Startzustand durch beliebige Sequenz von Ak8onen erreichbar Für Suchprobleme wird Zustandsraum implizit durch folg. Elemente gegeben: o Startzustand (ini8al state) o Ak8onsraum (ac8on space) o Transi8onsfunk8on (transi8on func8on) Kann durch gerichteten Graph dargestellt werden: o Knoten § Repräsen8eren mögliche Zustände o Kanten § Anwendbare Ak8onen zwischen Knoten o Richtung der Kanten § Transi8onsfunk8on o Pfad § Im Zustandsraumgraphen § Zustandssequenz mit Ak8onssequenz verbunden Lösung des Suchproblems: o Pfad, vom Startzustand S zum Zielzustand G o Pfad mit geringsten Kosten à op8male Lösung Beispiel: Suchproblem für Romänientour Startzustand o Ak8onsraum o Transi8onsfunk8on o Zieltest o Pfadkostenfunk8on o Typische Suchprobleme Routenplanung/Pfadfindung o Netzwerkverkehr im WWW o Naviga8onssysteme in Autos o Flugreiseplanung auf Websites Touring o Erweiterung einfacher Routenprobleme o Problem des Handlungsreisenden o Autonomer Mähroboter Roboter-Naviga8on o Verallgemeinerung von Routenproblemen o Weniger Abstrak8on möglich o Naviga8on autonomer landwirtschaUlicher Roboter Automa8sche Montagesequenz o Finden der Reihenfolge von Teilen komplexer Produkte à ohne Notwendigkeit vorherige Schri`e rückgängig zu machen Generelle Suchalgorithmen Suchbaum Baum o Datenstruktur o In denen funk8onieren Suchalgorithmen Wurzelknoten (Elternbla`) o Startpunkt des Suchalgorithmus o Baum verzweigt vom Startzustand (Ini8al State)  Zweige o Verbinden Blä`er/Knoten miteinander o Ak8onen führen zu Kinderknoten im Baum (Kind-)Knoten o States aus Zustandsraum des Problems Bla`knoten (=Fron8er) o Knoten ohne weitere Kindknoten/Abzweigung Knotenexpansion Baum inkrementell (schri`weise) gebaut Aktueller Zustand (Knoten) erweitert o Indem alle möglichen Ak8onen und erreichbaren nachfolgenden Zustände in Betracht gezogen werden o „Mentales“ Anwenden jeder legalen Ak8on auf aktuellen Zustand à durch Nutzung von Transi8onsfunk8on o Erweiterung von Knoten erzeugt neue Knoten (=Kinder) à platziert sie a Grenze o Entscheidung, welchen Knoten als nächstes zu erweitern à durch Suchstrategie bes8mmt FronGer (Prioritätsschlange; priority queue) Froni8er o Kern der Suchalgorithmen o Größter Unterschied der Suchalgorithmen à wie man Kindknoten aus Fron8er weiterexpandiert (à Suchstrategie) o Reihe an Bla`knoten à noch nicht erweitert Implemen8erung gemacht durch Prioritätsschlange (Datenstruktur) o Priorität unterschiedlich (Zeit, Kosten etc.) o Last-in-first-out (LIFO) à “Stack” o First-in-first-out (FIFO) à “Queue” Baumsuchenalgorithmus Prozess des Erweiterns von Knoten an Fron8er bis: o Lösung gefunden (=Zielzustand erreicht) o Es gibt keine weiteren zu expandierenden Knoten Baumsuche anfällig für „loopy“ (redundante) Pfade Pseudocode: o Loop do: unendliche Schleife Beispiel: Graphsuchenalgorithmus Lösung für Baumsuchenalgorithmus o Einführung erforschter Menge (explored set) à Datenstruktur § Speichert bereits expandierte Knoten § Idealerweise: Hash-Menge für 0(1) Zugriff o Wertvolle EigenschaU § Fron8er trennt erforschte von nicht erforschten Knoten im Graph à Baum dadurch nicht mehr unendlich (s.o.) Pseudocode:  Beispiel: Unterschied zwischen Graph und Baum Graph o Hat explored set § welche Knoten schon besucht? à werden nicht noch einmal besucht § kleinerer, übersichtlicherer Suchbaum o Keine unendliche Schleife Baum o Loopy und redundante Pfade à unendlich lange Suche à irgendwann sehr großer, unübersichtlicher Baum Bla4 ≠ Zustand Zustand o Mögliche (beobachtbare) Konfigura8on der Umgebung Knoten n à Andere Datenstruktur innerhalb eines Suchbaums o § Entspricht Zustand im Zustandsraum n o § Knoten im Baum à generiert n o § Auf Elternknoten angewandte Ak8on à um n zu erreichen o § Summierten Schri`kosten von Startknoten (Ausgangsknoten) zu n Parent Pointer verbindet Knoten zu Bäume Pseudocode, um Kindbla` zu generieren: Beispiel: Romänien-Tour EvaluaGon der Performance Suchalgorithmen hin sichtlich Effek8vität und Komplexität vergleichen: o Vollständigkeit § Findet Algo sicher eine Lösung, wenn eine exis8ert? § Algo in Lage eine Lösung zu finden o Op8malität § Findet Algo immer die op8male Lösung? § Wenn Algo garan8ert immer beste Lösung findet o Zeitkomplexität § Wie „lange“ dauert es, eine Lösung zu finden? o Raumkomplexität § Wie viel Speicher wird benö8gt, um eine Lösung zu finden? Komplexität als EvaluaGon der Performance Komplexität als abstrakte Messung der Problemschwierigkeit Für Suchalgorithmen im Graphen: o Anzahl an Knoten |V| und Kanten |E| o Nur geeignet, wenn ganzer Graph als Input im Algo gegeben Für KI-Suchalgos, die Graphen (hier Baum) implizit und inkrementell repräsen8eren: o Branching Factor (Verzweigungsfaktor) b § Max. Anzahl an nachfolgenden Knoten im Baum o Tiefe d § Tiefe der flachsten Zielknoten im Graphen à wie viele Schri`e bis zum Zielknoten o Max. Pfadlänge m § Maximale Länge eines beliebigen Pfads im Zustandsraum à wie weit wir uns maximal uns im Suchraum bewegen können Zeitkomplexität gemessen anhand o Anzahl an zu generierenden/expandierenden Knoten Speicherkomplexität gemessen anhand o Max. Anzahl der im Speicher gespeicherten Knoten Uniformed (blinde) Suche è Suche ohne zusätzl. Infos über Zustände, die über die in Problemformulierung bereitgestellten hinausgehen Breadth-first Suche (BFS) [Breitensuche] Immer auf gleichen Tiefenlänge in die Breite suchen Alle Knoten in bes8mmter Tiefe zuerst erweitert Wurzelknoten à alle ihre Nachfolger à alle ihre Nachfolger à … Einfache Implemen8erung o FIFO-Warteschlange als Fron8er à flachsten Knoten (in Fron8er obersten) nehmen Pseudocode: o Expansion mithilfe von for-Schleife EigenschaUen o Immer flachster Pfad zu allen Knoten auf Fron8er (auch Zielknoten) à kleinste Anzahl an Ak8onen o Vollständig à Ziel immer auffindbar o Op8mal § Unter Bedingung à dass Pfadkosten monoton steigende Funk8on der Tiefe eines Knotens ist § Z.B. alle Ak8onen haben gleiche Schri`kosten § à Uniform-cost Suche überwindet diese Einschränkung o Nachteil: Datenintensiver, Speicherplatzintensiv o Komplexität § Gehen vom Worst Case aus Jeder Knoten hat b Nachfolger Lösung auf Tiefe d à worst case: letzter generierter Knoten auf dem Level Beim Expandieren des Knoten und der Nachfolger à gleichzei8g wird Zieltest generiert o Zeitkomplexität § Summe aller generierten Knoten bis zum 8efsten Zielknoten d § o Speicherkomplexität § Jeder Knoten in Suche entweder im explored set oder im Fron8er IteraGve deepening search (IDS) Basiert auf 8efenlimi8erte Variante der DFS Bei Tiefensuche Problem: o Sehr (unendlich) 8efe Suchbäume à Suchalgorithmus kommt nicht zu Lösung è Mit IDS verhindern: max. Tiefenlimit für Tiefensuche anlegen Tiefenlimit itera8v anpassbar Performen Tiefenlimit 0 à Limit 1 à Limit 2 à Limit 3 à … à bis wir Flachste des Zielknotens gefunden haben/ die im Suchgraphen vorliegt EigenschaUen o Kombiniert Vorteile von BFS und Baumsuche DFS o Bevorzugt, wenn § Suchraum sehr groß § Tiefe der Lösung unbekannt o Vollständig o Op8mal § Unter Bedingung (wie bei BFS), à dass Pfadkostenfunk8on in Tiefe nicht abnimmt à so dass flachster Zielknoten auch op8malster Knoten ist o Komplexität § Gehen vom Worst case aus Jeder Knoten hat b Nachfoler Zielknoten in Tiefe d o Zeitkomplexität § Vorteil von BFS übernommen § Generiert keine Knoten auf oberen Ebenen mehrmals o Speicherkomplexität § Vorteil von DFS übernommen Pseudocode (rechts): Wenn in Limit 1 Zielknoten nicht gefunden à dann zu Limit 2 à wenn dort nicht gefunden auf Limit 3 erhöhen usw. Uniform-cost Suche (UCS) Unterschied zu BFS: o Auf Fron8er immer Knoten mit kürzeren Pfad ersetzen (mit niedrigeren Kosten) o Pfadkosten im Vordergrund nicht Ebene Erweitert BFS à um bei jeder Schri`kostenfunk8on op8mal zu sein à gleicht Nachteil von BFS aus Erweitert Knoten in der Reihenfolge der Pfadkosten g o Sor8ert nach Pfadkosten, die es bisher gibt à das mit geringsten Pfadkosten wird weiterexpandiert Implemen8erung der Fron8er o Prioritätswarteschlange geordnet nach g à nach Ordnung der Pfadkosten (Knoten mit geringsten Pfadkosten) Weitere Modifika8onen: o Führt Zielprüfung durch à wenn Knoten zur Expansion ausgewählt wird o Aktualisiert Pfad zu Knoten auf Fron8er à wenn besserer Pfad (mit geringeren Kosten) gefunden wurde EigenschaUen o Findet Pfad zu jedem Knoten auf Fron8er mit niedrigsten Pfadkosten g o Vollständig [findet garan8ert 1 Lösung] § Unter Bedingung à dass jeder Schri` mind. eine geringe posi8ve Konstante übersteigt (=sollte Minimum an Kosten haben) o Op8mal [findet garan8ert beste Lösung] § Schri`kosten per Defini8on nicht nega8v § Knoten nur dann expandiert à wenn op8maler Pfad gefunden o Komplexität § Gehen vom Worst Case aus Von Pfadkosten abgeleitet nicht von Tiefe C* = Kosten der op8malen Lösung Jede Handlungskosten = mind. o Zeitkomplexität § § Höhere Zeitkomplexität als BFS § Op8maler Fall: wenn alle Pfadkosten gleich o Speicherkomplexität § Pseudocode Depth-first Suche (DFS) [Tiefensuche] Immer 8efster Knoten in Fron8er zuerst erweitert o Geht sofort zur 8efsten Ebene des Suchbaums o Wenn aktueller Knoten keine Nachfolger à „geht“ Suche zurück zum nächszefsten Knoten mit Nachfolgern à = „back up“ o Schneidet vollständig erkundete Baumzweige ab à d.h. enhernt bereits erkundete Knoten aus Speicher à spart Speicher [Vorteil+] Implemen8erung der Fron8er o LIFO-Warteschlange à 8efsten Knoten (in Fron8er untersten) nehmen 2 Varianten: o Graphensuche DFS o Baumsuche DFS EigenschaUen o Nicht vollständig in unendlichen Zustandsräumen à wenn kein Ende à immer weiter nach unten expandieren und suchen o Vollständigkeit in endlichen Zustandsräumen hängt von Variante ab: § Graphensuche DFS à vollständig § Baumsuche DFS à nicht vollständig o Nicht op8mal § Kann 8efere Zielknoten als Lösung zurückgeben als op8malen Zielknoten o Komplexität vom Suchbaum DFS § Gehen vom Worst Case aus Jeder Knoten hat b Nachfolger Max. Tiefe von jedem Knoten m (m>=d) o Zeitkomplexität § Baumsuche DFS: à viel höher als bei BFS § Graphensuche DFS: Anzahl an Knoten und Kanten o Speicherkomplexität [vorteilhaU+] § Speichert nur 1 Pfad zu einem Bla`knoten ab à unexpandierende Knoten müssen nicht in Speicher aufgenommen werden § Enhernt Knoten aus Speicher à wenn alle folgenden Knotenschon durchsucht wurden § Baumsuche DFS: à sehr geringe Speicherkapazität § Graphensuche DFS: nur Anzahl der zu generierenden Knoten Pseudocode: Vergleich von Uniformed Suchstrategien Strategieanwendungsempfehlung: o Unter Einschränkung à dass Knoten endliche Anzahl von Nachfolgern haben o Bei iden8schen Schri`kosten: § BFS für kleiner Suchräume oder wenn keine Speicherplatzbeschränkung vorliegt § IDS für große Suchräume oder wenn Speicherplatz begrenzt ist o Bei unterschiedlichen Schri`kosten: § UCS, aber nur garan8ert vollständig, wenn jede Schri`kosten à für posi8ve Welcher Algo am besten wann? o Abhängig vom Problem o Wenn Einschränkungen bekannt o Wich8g: Endliche Menge an Nachfolgern Informierte (Heuris