Rückblick auf 70 Jahre KI Geschichte

 Seit der Erfindung des Computers in den 1950er Jahren gab es parallel dazu eine philosophische Debatte über Künstliche Intelligenz und Robotik. Demnach blickt die Erforschung künstlicher Intelligenz auf eine rund 70 jährige Geschichte zurück, worin Mathematiker und Programmierer aus mehreren Generationen mitgewirkt haben.

Das ungelöste Problem in diesem Zeithorizont war die kombinatorische Explosion des Suchraums. Bereits die ersten Schachprogramme in Software waren von der Größe des game trees (=Suchbaums) überfordert. Es gab große Anstrenungen mit Hilfe von Bewertungsfunktionen, schnellen Algorithmen und besserer Hardware die kombinatorische Explosion zu überwinden aber es gelang nicht. Die aufkommende Robotik war von dem selben Hinderniss blockiert. Man kann anhand des piano movers und mittels motion planning Aufgaben zeigen, dass auch hier der Suchbaum sehr groß ist und gegen unendlich geht wodurch es nicht möglich ist für einen Computer eine Entscheidung zu treffen was in einer Situation zu tun ist.

Theoreitsch gesehen kann man künstliche Inteliigenz dadurch realisieren indem man den Suchbaum durchprobiert um die beste Aktion zu finden, nur dauert das je nach Domäne Jahre bis Jahrzehnte auf aktueller Computerhardware. Eine KI Software die jedoch nur ausgibt, dass sie nachdenkt, aber keine Antwort liefert ist praktisch nutzlos.

Die kombinatorische Explosion ist ein Fakt den die Künstliche Intelligenz seit ihren Anfängen begleitet hat. Man kann für ein konkretes Computerspiel wie Schach, Lemmings oder Autorennen im Detail berechnen wie umfangreich der Suchbaum jeweils ist, anderer Forscher können diese Berechnung überprüfen und gelangen zum selben Ergebnis, nur dadurch wird das Problem nicht gelöst sondern es gibt lediglich einen Konsens darüber dass die Aufgabe unlösbar ist.

Es ist verständlich warum einige KI Forscher in der Vergangenheit vermuteten, dass Künstliche Intelligenz vielleicht nicth realisierbar ist auf einem Computer. Das es also ähnlich wie ein Perpetuum mobile ein Naturgesetz gibt wonach denkende Maschinen nur in der Science Fiction möglich sind. Es gibt in der Informatik sogar ein Pendant zum Energieerhaltungssatz und zwar die Vermutung P!=NP, was diese Vermutung auf eine mathematische Grundlage stellt. Was man gesichert annehmen kann ist dass es keine mathematische Lösung gibt für KI Probleme wie das piano movers problem. Sondern dass die Lösung außerhalb der Mathematik zu suchen ist.

Die Mathematik verwendet als wichtiges Werkzeug das Zahlensystem sowie Algorithmen die auf den Zahlen angewendet werden. Mit diesem Werkzeugkasten lassen sich bestimmte Aufgaben lösen und andere nicht. Leider liegen KI Probleme wie die Steuerung von robotern oder das automatische Spielen von Computerspielen in jener Klasse von Problemen für die es keine mathematischen Lösungsverfahren gibt. Selbst neuartige propabilistische sampling Verfahren wie RRT sind nicht leistungsfähig genug für motion planning Probleme. Die einzige Methode um KI Aufgaben zu lösen wäre eine generalisierte Heuristik. Allerdings hat die Erforschung der KI in über 70 Jahren keine solche Metaheuristik finden können.

Um den Pessimismus zu verstärken hier einige Versuche aus der Vergangenheit Robotikprobleme zu lösen, die sich jedoch als nicht leistungsfähig genug erwiesen haben:

1. Pfadplanung mit A* Graphensuche
2. Dynamische Programmierung nach Richard Bellman 
3. STRIPS plannungsalgorithmus
4. potential field method
5. genetische Algorithmen
6. Simulated Annealing
7. Expertensysteme
8. Ant Colony Optimization
9. Partikelschwarm-Optimierung
10. Neuronale Netze
11. Probabilistische Roadmaps
12. Rapidly-exploring Random Trees

Anzahlmäßig gab es also mehrere Ansätze die als metaheuristik angepriesen wurden, allerdings in der Praxis gescheitert sind. Keiner der Verfahren ist in der Lage die kompbinatorische Explosion zu vermindern. Das bedeutet konkret, dass sobald man z.b. einen Simulated Annealing Algorithmus startet um die Greifplanung eines Roboters durchzuführen, dass dieser Algorithm 100% der CPU Leistung benötigt und nach 1 Woche Rechenzeit immernoch keine Antwort gefunden hat.

Das eigentliche Problem mit den obigen Verfahren ist dass sie alle mathematisch orientiert sind. Sie versuchen ein optimierungsproblem zu lösen was als unlösbar bekannt ist. Die neueren Verfahren wie Partikelschwarm-Optimierung arbeiten dabei mit statistischen Ungenauigkeiten um so den Suchraum zu verkleinern, trotzdem bleiben sie innerhalb des mathematischen Horizonts verhaftet.

Das vermutlich höchst-entwickelteste Verfahren in der Liste sind neuronale Netze die eine eigene Kategorie bilden und viele Unterbereiche aufweisen. Es gibt mehrere Neuronale Netze mit vielen Lernverfahren. Aber auch hier gelang es nicht, Roboter zu steuern, grund ist dass der Rechenaufwand zum Finden der richtigen Gewichte für das Netz zu lange dauert und das unklar ist wie lange man genau warten muss bis ein neuronales Netz konvergiert.

Ein hochentwickeltes Verfahren ist Neuroevolution of augmenting topologies (NEAT) aus dem Jahr 2002 was genetische Algorithmen mit neuronalen Netzen kombiniert und in der Theorie eine Metaheuristik ist mit der jedes Optimierungsproblem gelöst werden kann. Allerdings nur theoretisch, in der Praxis scheitert NEAT an der hohen Rechenzeit.

Die Grafik zeigt unterschiedliche Verfahren innerhalb eines Koordinatensystems da. Klassische optiimierungsalgorithmen sind mathematisch und batch orientiert zugleich. Es wird ein Zahlenproblem gelöst ohne dass von außen der Nutzer eingreifen kann.

Im Gegensatz dazu sind Sprachorientierte verfahren wie Ontologien nicht länger zahlenbasiert, aber setzen immernoch voraus dass der Roboter die Lösung von allein findet und zwar mit Hilfe eines semantic networks. 

Das neueste und mächtigste Verfahren "voice control" ist einerseits linguistisch orientiert und zugleich interaktion. Ein Menschlicher Benutzer gibt dem Roboter von Außen Kommandos in natürlicher Sprache.