Grundlagen der Künstlichen Intelligenz: Agenten, Suche und Logik

Punkt 2: Agenten und ihre Arbeitsumgebung

Ein Agent ist etwas, das wahrnimmt und entsprechend handelt. Die Rolle des Agenten beschreibt die Aktionen, die ein Agent als Reaktion auf eine empfangene Leistungsmessung ausführt. Die Reihenfolge der durchgeführten Aktionen bewertet das Verhalten des Agenten. Ein rationaler Agent agiert mit dem Ziel, den erwarteten Wert der Leistungsmessung zu maximieren, basierend auf der bisher beobachteten Reihenfolge der Wahrnehmungen.

Die Arbeitsumgebung umfasst Spezifikationen für die Leistungsmessung, das externe Umfeld, Aktoren und Sensoren. Der erste Schritt bei der Entwicklung einer Agenten-Spezifikation sollte immer die möglichst vollständige Beschreibung der Arbeitsumgebung sein. Das Arbeitsumfeld ist von verschiedenen Parametern abhängig. Es kann ganz oder teilweise sichtbar, deterministisch oder stochastisch, episodisch oder sequenziell, statisch oder dynamisch, diskret oder kontinuierlich sein und von einem einzelnen Agenten oder mehreren Agenten gebildet werden.

Das Agentenprogramm implementiert die Agentenfunktion. Es gibt eine Vielzahl von Agentenprogramm-Designs, die die Art der Informationen widerspiegeln, die im Entscheidungsprozess explizit gemacht und verwendet werden. Die Ausführungen unterscheiden sich in Leistungsfähigkeit, Robustheit und Flexibilität. Die entsprechende Gestaltung des Agentenprogramms hängt weitgehend von der Natur der Umgebung ab.

• Einfache reaktive Agenten reagieren direkt auf Wahrnehmungen.
• Modellbasierte reaktive Agenten unterhalten einen internen Zustand, der es ihnen ermöglicht, Aspekte der Welt zu verfolgen, die nicht als aktuelle Wahrnehmungen offensichtlich sind.
• Zielbasierte Agenten handeln mit der Absicht, ihre Ziele zu erreichen.
• Nutzenbasierte Agenten versuchen, ihren Nutzen oder ihr gewünschtes „Glück“ zu maximieren.

Alle Agenten können ihre Effizienz mithilfe von Lernmechanismen verbessern.

Punkt 3: Problemlösung durch Suche

Bevor ein Agent mit der Suche nach Lösungen beginnen kann, muss er ein Ziel formulieren und dieses Ziel dann nutzen, um ein Problem zu definieren. Ein Problem besteht aus vier Teilen: dem Anfangszustand, einer Menge von Aktionen, einer Zieltestfunktion und einer Pfadkostenfunktion. Die Problemstellung wird durch einen Zustandsraum repräsentiert. Ein Pfad im Zustandsraum vom Anfangszustand zu einem Zielzustand ist eine Lösung.

Ein einfacher und allgemeiner Suchbaum-Algorithmus kann verwendet werden, um jedes Problem zu lösen; algorithmspezifische Varianten übernehmen unterschiedliche Strategien. Suchalgorithmen werden anhand von Vollständigkeit, Optimalität, Zeitkomplexität und Speicherkomplexität beurteilt. Die Komplexität hängt von b, dem Verzweigungsfaktor im Zustandsraum, und d, der Tiefe der Lösung, ab.

• Die Breitensuche erweitert Knoten nicht oberflächlicher im Suchbaum. Sie ist vollständig, optimal für einheitliche Schrittkosten und hat eine Zeit- und Raumkomplexität von O(b^d). Die Raumkomplexität macht sie in den meisten Fällen unpraktisch.
• Die uniforme Kostensuche ähnelt der Breitensuche, erweitert jedoch den Knoten mit den geringsten Pfadkosten, g(n). Sie ist vollständig und optimal, wenn die Kosten für jeden Schritt eine positive Untergrenze E überschreiten.
• Die Tiefensuche erweitert Knoten, die nicht tiefer im Suchbaum liegen. Sie ist weder vollständig noch optimal und hat eine Zeitkomplexität von O(b^m) und eine Raumkomplexität von O(bm), wobei m die maximale Tiefe eines Pfades im Zustandsraum ist.
• Die tiefenbegrenzte Suche legt eine feste Tiefengrenze für die Tiefensuche fest.
• Die iterative Tiefensuche ruft die tiefenbegrenzte Suche auf und erhöht diese Grenze, bis ein Ziel gefunden wird. Sie ist vollständig, optimal für einheitliche Schrittkosten und hat eine Zeitkomplexität von O(b^d) sowie eine Raumkomplexität von O(bd).
• Die bidirektionale Suche kann die Zeitkomplexität erheblich reduzieren, ist aber nicht immer anwendbar und kann auch mehr Speicherplatz erfordern.

Wenn der Zustandsraum ein Graph statt eines Baumes ist, kann es sinnvoll sein, wiederholt besuchte Zustände im Suchbaum zu überprüfen. Der GRAPH-SEARCH-Algorithmus eliminiert alle doppelten Zustände. Wenn die Umgebung teilweise beobachtbar ist, kann der Agent Suchalgorithmen im Raum der Glaubenszustände oder Gruppen möglicher Zustände implementieren, in denen sich der Agent befinden könnte. In einigen Fällen kann eine einfache Lösungssequenz erstellt werden; in anderen Fällen muss der Agent einen Notfallplan für unbekannte Umstände erstellen.

Punkt 4: Informierte Suche und lokale Verfahren

Die Best-First-Suche ist eine Graphensuche, bei der Knoten mit den geringsten Kosten (nach einem bestimmten Maß) zur Erweiterung ausgewählt werden. Die Best-First-Algorithmen verwenden üblicherweise eine heuristische Funktion h(n), die die Kosten einer Lösung von n schätzt. Die Gierige Best-First-Suche erweitert Knoten mit minimalem h(n). Sie ist nicht optimal, aber oft effizienter.

Die A*-Suche erweitert Knoten mit minimalem f(n) = g(n) + h(n). A* ist vollständig und optimal, vorausgesetzt, h(n) ist zulässig (für Suchbäume) oder konsistent (für Suchgraphen). Die Raumkomplexität von A* ist jedoch immer noch prohibitiv.

Die Leistung heuristischer Suchalgorithmen hängt von der Qualität der heuristischen Funktion ab. Gute Heuristiken können durch eine Lockerung der Problemdefinition, durch vorkalkulierte Lösungskosten für Unterprobleme, in einer Modelldatenbank oder durch Lernen aus Erfahrung für bestimmte Problemtypen konstruiert werden. IDA* und SMA* sind robuste und optimale A*-Suchalgorithmen mit begrenztem Speicher, die mit der Zeit Probleme lösen können, die A* nicht lösen kann, weil es an Speicher mangelt.

Lokale Suchverfahren wie das Hügelklettern arbeiten mit vollständigen Zustandsformulierungen und halten nur eine kleine Anzahl von Knoten im Speicher. Es wurden mehrere stochastische Algorithmen entwickelt, darunter das simulierte Annealing, das eine optimale Lösung zurückgibt, wenn ein korrektes Abkühlungsprogramm verwendet wird. Viele lokale Suchmethoden können auch verwendet werden, um Probleme in kontinuierlichen Bereichen zu lösen.

Ein genetischer Algorithmus ist eine stochastische Hügelkletter-Suche, die eine große Population von Zuständen pflegt. Neue Zustände werden durch Mutation und Crossover erzeugt, indem Paare von Zuständen aus der Population kombiniert werden.

Explorationsprobleme entstehen, wenn der Agent keine Kenntnis über die Zustände und Aktionen seiner Umgebung hat. In sicher erforschbaren Umgebungen kann der Agent online eine Karte erstellen und ein Ziel erreichen, falls vorhanden. Schätzungen von Heuristiken, die durch Erfahrung aktualisiert werden, sind eine effektive Methode, um lokalen Minima zu entkommen.

Punkt 5: Wissensrepräsentation und Logik

Intelligente Agenten benötigen Wissen über die Welt, um fundierte Entscheidungen zu treffen. Agenten repräsentieren Wissen in Form von Wissensrepräsentationssätzen über eine Sprache, die in einer Wissensbasis gespeichert werden. Ein wissensbasierter Agent besteht aus einer Wissensbasis und einem Inferenzmechanismus. Der Agent arbeitet, indem er Urteile über die Welt in seiner Wissensbasis speichert, über den Inferenzmechanismus neue Sätze ableitet und mit diesen Urteilen entscheidet, welche weiteren Maßnahmen er ergreifen sollte.

Eine Wissensrepräsentationssprache wird durch ihre Syntax definiert, die die Struktur von Sätzen angibt, und durch ihre Semantik, die den Wahrheitswert jedes Satzes in jeder möglichen Welt oder jedem Modell definiert. Die Beziehung zwischen Sätzen der Implikation ist von entscheidender Bedeutung für unser Verständnis des Schlussfolgerns. Ein Satz A impliziert einen weiteren Satz B, wenn B in allen Welten wahr ist, in denen A wahr ist. Die Definitionen sind mit diesem Konzept vertraut: die Gültigkeit des Satzes A => B und die Unerfüllbarkeit des Satzes A ¬ B. Die Inferenz ist der Prozess der Ableitung neuer Sätze aus alten. Korrekte Inferenzalgorithmen leiten nur Sätze ab, die impliziert sind; vollständige Algorithmen leiten alle implizierten Sätze ab.

Die Aussagenlogik ist eine sehr einfache Sprache, bestehend aus propositionalen Symbolen und logischen Konnektiven. Auf diese Weise können Sätze behandelt werden, die bekanntermaßen wahr, falsch oder vollständig unbekannt sind. Bei einem festen propositionalen Vokabular ist die Anzahl der potenziellen Modelle begrenzt, und so ist die Implikation offensichtlich nur aus der Liste der Modelle ersichtlich.

Inferenzalgorithmen, die auf der Modellprüfung für die Aussagenlogik basieren, darunter lokale Suchverfahren und Backtracking, können oft sehr komplexe Probleme recht schnell lösen. Inferenzregeln sind korrekte Schlussfolgerungsformen, die verwendet werden können, um Beweise zu finden. Mit der Resolutionsregel erhalten wir einen vollständigen Inferenzalgorithmus für Wissensbasen, die in konjunktiver Normalform ausgedrückt werden. Die Vorwärtsverkettungs- und Rückwärtsverkettungs-Algorithmen sind sehr gut für Wissensbasen geeignet, die in Horn-Klauseln ausgedrückt werden.

Man kann zwei Arten von Agenten mit Aussagenlogik entwerfen: Inferenz-Agenten, die Schlussfolgerungsalgorithmen verwenden, um den Zustand der Welt zu verfolgen und verborgene Eigenschaften abzuleiten, während schaltungsbasierte Agenten Sätze durch Bits in Registern repräsentieren und diese mit der Signalausbreitung von Logikschaltungen aktualisieren. Die Aussagenlogik ist für bestimmte Aufgaben eines Agenten wirksam, skaliert aber nicht auf Umgebungen unbegrenzter Größe, da ihr die Ausdruckskraft fehlt, um genaue Zeit, Raum oder generische Muster von Beziehungen zwischen Objekten zu behandeln.