intelligente-agenten

So funktionieren intelligente Agenten – Basis Strategien

Was macht einen künstlichen Agenten intelligent?

Wir Menschen neigen dazu, ein System insbesondere dann für intelligent zu halten, wenn und solange wir nicht genau wissen, wie es funktioniert. Als es noch keinen Computer gab, der professionelle Schachspieler schlagen konnte, war man überzeugt, dass ein System wirklich „intelligent“ sein müsse, wenn es tatsächlich selbständig die besten Menschen im Schach besiegen könnte.

Nachdem das System gebaut wurde (IBM’s DeepBlue) und die besten Schachspieler der Welt schlagen konnte, drehte sich die Wahrnehmung sehr schnell, da es sich ja doch nur um einen raffinierten Algorithmus handelte, kombiniert mit sehr viel Rechenleistung (nach damaligen Maßstäben).

Intelligenz ist das, was wir nicht verstehen

Ähnlich verhält es sich mit vielen anderen Problemen, die heute scheinbar selbstverständlich mit KI Algorithmen gelöst werden können, bei denen man sich vor nicht allzu langer Zeit aber sicher war, dass für ihre Lösung Intelligenz erforderlich ist. Die Wahrnehmung von Intelligenz ist also einerseits beeinflusst davon, ob wir die Art und Weise der Lösungsfindung lückenlos verstehen. Andererseits bezieht sich Intelligenz immer auf eine bestimmte Problemstellung, und Menschen sind sehr gut darin, ihre Intelligenz zur Lösung sehr vieler unterschiedlicher Problemarten einzusetzen.

Intelligente Agenten dagegen sind schon heute sehr gut darin, bestimmte Probleme zu lösen, und sie können dies oft sehr viel schneller und besser als Menschen. Die Grenzen dessen, was dabei als intelligent bezeichnet werden kann, sind daher fließend. Ein Agent, der jedes noch so schwierige Sudoku in wenigen Millisekunden lösen kann, ist offensichtlich intelligent darin, Sudokus zu lösen. Er ist zwar kein selbstlernendes System, da er auf festen Algorithmen basiert, aber er findet selbständig die Lösung für jedes Problem seiner Domäne, auch wenn er es vorher noch nie gesehen hat.

Die Strategien, die für solche intelligenten Agenten eingesetzt werden, sind die Basis für viele Anwendungen und Weiterentwicklungen künstlicher Intelligenz und selbstlernender Systeme. Es lohnt sich daher, einen Blick auf die Funktionsweise intelligenter Agenten zu werfen.

So funktionieren intelligente Agenten

Die Basis-Strategie von künstlichen Agenten läßt sich gut am Beispiel von verschiedenen Spielen / Rätseln verdeutlichen. Beginnen wir mit dem Zahlen-Rätsel Sudoku.

In einer Tabelle mit 9×9 Feldern, die in 9 Unter-Tabellen mit je 3×3 Feldern unterteilt ist, sollen die Zahlen von 1-9 so eingetragen werden, dass in jeder Reihe und jeder Spalte und in jeder Unter-Tabelle jede Zahl nur ein Mal vorkommt. Diese Einschränkung sorgt bei einfachen Sudokus für einen relativ klaren Lösungsweg, sofern man immer alle Spalten, Reihen und Unter-Tabellen und die jeweils schon verwendeten Zahlen im Blick hat.

Aus den pro Reihe, Spalte und Unter-Tabelle bereits vorhandenen Zahlen ergibt sich eine Eingrenzung des Möglichkeits-Raumes (Constraint) für die verbleibenden leeren Felder der jeweiligen Kategorie. Es bleiben also jeweils nur bestimmte Zahlen übrig, die für diese Felder in Frage kommen.

sudoku-kuenstliche-intelligenz

Möglichkeits-Räume eines einfachen Sudokus

Constraint Propagation – Eingrenzen der möglichen Lösungen

Die erste Strategie eines intelligenten Sudoku-Agenten besteht daher darin, eine stets aktuelle Übersicht der pro leerem Feld noch möglichen Zahlen zu haben. Wann immer eine neue Zahl eingetragen werden kann, wird entsprechend der Möglichkeits-Raum der übrigen leeren Felder aktualisiert, sofern sie davon betroffen sind. Diese Strategie nennt man Constraint Propagation.

Einfache Sudokus, bei denen es immer mindestens ein eindeutiges nächstes leeres Feld gibt, können alleine mit dieser Strategie gelöst werden. Bei schwierigeren Sudokus gelangt man jedoch häufig an Punkte, bei denen es keinen eindeutigen nächsten Schritt gibt, sondern zwei oder mehrere Möglichkeiten, von denen aber nur eine richtig ist.

Hier greift dann sowohl bei Menschen als auch bei Maschinen die zweite Strategie: Die Suche.

Search – Such-Strategien intelligenter Agenten

Wenn sich einem intelligenten Agenten mehr als eine Möglichkeit für den nächsten Schritt bietet, beginnt er damit, alle Möglichkeiten nacheinander auszuprobieren. Die Auswahl des Suchalgorithmus und ggfs. einer Bewertungsfunktion für die zur Verfügung stehenden Optionen entscheidet dabei über die Such-Reihenfolge und damit auch über die Effizienz und Schnelligkeit der Suche.

Eine der simpelsten Varianten ist dabei die Depth-First-Search. Dabei handelt es sich um einen Suchalgorithmus, der die zur Verfügung stehenden Entscheidungsbäume immer zuerst in Richtung möglicher End-Ziele durchsucht. Das heißt, es wird jeder Ast zunächst bis zum Ende durchsucht, bevor der nächste Ast an die Reihe kommt. Im Gegensatz dazu wird bei der Breadth-First-Search jede Ebene des Entscheidungsbaums komplett durchsucht, bevor eine Ebene tiefer gesucht wird.

depth-first-search breadth-first-search

Beide Varianten sind sogenannte Brute Force Strategien, d.h. man versucht, ein Problem mit schierer Rechenpower zu lösen, indem man einfach alle möglichen Varianten bis zum Ende durchrechnet. Wenn der Such-Raum hierfür schlicht zu groß ist, kommen komplexere und mächtigere Suchalgorithmen wie z.B. Uniform Cost Search und A-Star Search zum Einsatz. Bei unserem Sudoku-Beipiel ist eine Depth-First-Search eine ausreichende Strategie, um Lösungen auch für extrem schwierige Sudokus zu finden. Die Suche kann dabei durch sinnvolle Zusatzregeln vereinfacht werden:

Natürlich macht es Sinn, als erstes das Feld mit den wenigsten Möglichkeiten auszuprobieren und die Suche durch den Entscheidungsbaum dort zu starten. Des Weiteren kann auch die Constraint-Propagation verbessert werden, indem man die Möglichkeits-Räume zum Beispiel mit der Naked Twins Strategie weiter einschränkt:

Naked Twins – Effiziente Strategien zur Kombination von Suche und Eingrenzung

Wenn zwei Felder jeweils nur die gleichen beiden Zahlen als aktuellen Möglichkeitsraum aufweisen, so ist zwar nicht bekannt, zu welchem Feld welche Zahl gehört, aber es ist klar, dass alle anderen Felder innerhalb der betroffenen Reihen, Spalten und Unter-Tabellen nicht diese Zahl enthalten können. Beide Zahlen können also entsprechend aus den Möglichkeitsräumen aller anderen betroffenen Felder gelöscht werden.

Der Sudoku-Algorithmus des intelligenten Agenten funktioniert dann also in einem Loop wie folgt:

  1. Constraint Propagation – Update der Möglichkeits-Räume
  2. OnlyChoice – Felder füllen, bei denen es eine eindeutige Möglichkeit gibt
  3. NakedTwins – Weitere Einschränkung der Möglichkeits-Räume anwenden
  4. Search – Auswahl des Feldes mit den wenigsten Möglichkeiten, erneutes Anwenden der o.g. Strategien inklusive Search bis eine Lösung oder ein Fehler zurückgegeben wird

Im Ergebnis kann der intelligente Sudoku-Agent auch diagonale Sudokus der schwersten Kategorie in wenigen Millisekunden lösen. Verlangsamt sieht der Lösungsprozess des Agenten dann z.B. so aus:

Intelligenter Sudoku Agent

So löst ein intelligenter Agent ein schwieriges diagonales Sudoku (Darstellung stark verlangsamt)

Zusammenfassung

Die Suche und die Eingrenzung des Möglichkeits-Raums sind effiziente Strategien, mit denen spezialisierte intelligente Agenten vielfältige Probleme intelligent lösen können. Auch wenn es sich dabei „nur“ um Algorithmen handelt, so sind diese Agenten bei der Lösung der Probleme ihres Spezialgebietes unbestreitbar sehr intelligent und vor allem viel schneller, zuverlässiger und besser als menschliche Agenten.

Interessanterweise kann die Entwicklung von intelligenten Agenten für bestimmte Aufgaben auch dazu führen, dass Menschen, die diese Aufgabe vormals interessant fanden und gerne gelöst haben, danach kaum noch Interesse an der manuellen Lösung haben. Als Beispiel sei hier der Taschenrechner genannt – oder vielleicht auch Sudoku?


Grafik Depth-First Search vs. Breadth-First Search: UNSW, Sydney

Grafik Möglichkeits-Räume eines einfachen Sudokus: By Wikipit CC BY-SA 3.0

1 Antwort

Trackbacks & Pingbacks

  1. […] einen künstlichen Agenten als intelligent wahrnehmen und mit welchen Basis-Methoden spezialisierte intelligente Agenten Probleme lösen können. Eine wichtige Methode ist die Suche nach den jeweils besten […]

Dein Kommentar

Want to join the discussion?
Feel free to contribute!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.