Problemlösen durch heuristische Suche in der Artificial Intelligence

Die Zielsetzung der Artificial Intelligence (AI) ist es, Maschinen, zu erzeugen, die "intelligentes" Verhalten zeigen. Dabei spielt in vielerlei Hinsicht das Problemlösen eine zentrale Rolle. Die in diesem Buch behandelten Ansätze basieren auf heuristischer Suche. Das Buch bietet eine umfassende Behandlung des "State-of-the-art" dieses Teilbereichs der AI und zeigt fundamentale Zusammenhänge verschiedenster Problemstellungen und ihrer Lösungen auf. Bei der Darstellung steht die intuitive Vermittlung von Ideen im Vordergrund (unterstützt durch leicht verständliche Beispiele). Wo es die Thematik erfordert, kommt jedoch auch mathematische Notation zum Einsatz, und es werden exakte Beweise angegeben. Die derzeit bekannten Such-Verfahren werden hier in einem einheitlichen Formalismus präsentiert, um eine Gegenüberstellung zu ermöglichen. Die Begriffswelt dieses Teilbereiches der AI wird unter Zuhilfenahme von (großteils informalen) Definitionen umfassend erläutert, um eine klare Darstellung der Materie zu erreichen. Außerdem soll dem Leser dieses Buches ein guter Einstieg in die einschlägigge (größtenteils englischsprachige) Fachliteratur ermöglicht werden.

1 Problemdarstellung.- 1.1 Produktionssysteme.- 1.1.1 Beispiele für Produktionssysteme.- 1.1.2 „Constraint Satisfaction“ Probleme.- 1.1.3 Produktionssysteme „im engeren Sinn“.- 1.1.4 Kommutative Produktionssysteme.- 1.2 Graphen.- 1.2.1 Begriffliche Übersicht.- 1.2.2 Darstellung des Vorgehens eines Produktionssystems.- 1.3 Zerlegbare Produktionssysteme.- 1.3.1 UND/ODER-Graphen.- 1.3.2 Spielbäume.- 1.4 Beziehungen zwischen verschiedenen Begriffen und Formalismen.- 1.4.1 Richtung des Vorgehens.- 1.4.2 Beziehungen zwischen kommutativen und zerlegbaren Produktionssystemen.- 1.4.3 Begriffliche Zusammenhänge.- 2 Problemlösen mittels Suche.- 2.1 Allgemeines.- 2.1.1 Ein allgemeines Schema für Such-Verfahren.- 2.1.2 Ein Graph-Such-Verfahren.- 2.1.3 Suche in UND/ODER-Graphen.- 2.2 „Irrevocable Control“.- 2.2.1 Kommutativität.- 2.2.2 „Hill-Climbing“.- 2.3 „Breadth-First Search“.- 2.3.1 Vorgangsweise.- 2.3.2 Komplexität.- 2.3.3 „Uniform-Cost Search“.- 2.4 „Depth-First Search“.- 2.4.1 Vorgangsweise.- 2.4.2 „Backtracking“.- 2.4.3 Komplexität.- 2.5 „Best-First Search“.- 2.5.1 Bewertungsfunktion von A*.- 2.5.2 Die heuristische Komponente: Ermittlung und Anwendung.- 2.5.3 Zulässigkeit.- 2.5.4 Geometrische Darstellung.- 2.5.5 Gewichtete Bewertungsfunktionen.- 2.5.6 Vergleich von Bewertungsfunktionen für A*.- 2.5.7 Konsistente (monotone) heuristische Funktionen.- 2.5.8 Konsistenz und vereinfachte Modelle.- 2.5.9 Nicht-konsistente Funktionen und Modifikationen von A*.- 2.5.10 Komplexität von A*.- 2.5.11 Bewertungsfunktionen ohne Garantie für optimale Lösungen.- 2.5.12 Allgemeine Funktionen für Kosten und Bewertungen.- 2.5.13 Ist A* optimal?.- 2.5.14 „Best-First Search“ in UND/ODER-Graphen.- 2.6 „Depth-First Iterative-Deepening“.- 2.6.1 DFID.- 2.6.2 IDA*.- 2.6.3 PIDA* — Eine parallele Version von IDA*.- 2.7 „Bidirectional Search“.- 2.7.1 „Blinde“ Suche in beide Richtungen.- 2.7.2 Suche in beide Richtungen mit Heuristik.- 2.8 „Conflict Resolution“.- 3 Begrenzte Suche zum Fällen von Entscheidungen.- 3.1 Allgemeines.- 3.1.1 Entscheidungen bei Problemen.- 3.1.2 Lösen von Spielbäumen.- 3.1.3 Bewerten von Spielbäumen.- 3.1.4 „Minimaxing“.- 3.1.5 Modifikationen und Alternativen bezüglich „Minimaxing“.- 3.2 „Depth-First Search“.- 3.2.1 Suche zur Berechnung des Minimax-Werts.- 3.2.2 Das ?-?-Verfahren.- 3.2.3 Die Verwendung eines „Fensters“.- 3.2.4 PAB und SCOUT.- 3.3 „Depth-First Iterative-Deepening“.- 3.4 „Best-First Search“.- 3.4.1 SSS* und DUAL*.- 3.4.2 B* und PB*.- 3.5 Die Effizienz der Minimax-Verfahren im Vergleich.- 3.5.1 Ungünstigste und günstigste Bedingungen.- 3.5.2 Der „durchschnittliche“ Fall.- 3.6 Zusätzliche Aspekte und Heuristika.- 3.6.1 Erreichen einer „guten“ Anordnung der Nachfolger.- 3.6.2 Statische Bewertungsfunktionen.- 3.6.3 „Quiescence“ und der Horizont-Effekt.- 3.6.4 Variable Such-Tiefe.- 3.7 Die Qualität der Entscheidungen.- Epilog.- Literatur.- Notation.