Was sind Intelligente Agenten?

Intelligente Agenten sind schon heute sehr gut darin, bestimmte Probleme zu lösen. Sie können das sogar oft sehr viel schneller und besser als Menschen. Intelligente Agenten sind zwar keine selbstlernenden Systeme, da ein Intelligenter Agent 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.

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.

Strategien der Eingrenzung

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.

Menschen und Maschinen wenden an dieser Stelle eine zweite Strategie an: Suchen.

Strategien der Suche

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  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. Das ist ein 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.

Beide Varianten sind sogenannte Brute Force Strategien. Bei diesen Strategien versucht man, 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 zum Beispiel Uniform Cost Search und A-Star Search zum Einsatz. 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:

Kombination von Suche und Eingrenzung

Wenn zwei Felder in dem genannten Sudoku Beispiel 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 Durchlauf folgendermaßen:

Constraint Propagation: Update der Möglichkeits-Räume

OnlyChoice: Felder füllen, bei denen es eine eindeutige Möglichkeit gibt

NakedTwins: Weitere Einschränkung der Möglichkeits-Räume anwenden

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

Die Suche und die Eingrenzung des Möglichkeitsraums 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.

Besonderes Detail bei der Sache: Die Entwicklung von intelligenten Agenten kann 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. Der gute alte Taschenrechner ist ein perfektes Beispiel dafür.

Team WEGOFIVE
team@wegofive.net
No Comments

Post A Comment

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.