Angesichts des aktuellen Hypes rund um LLM und Robotik ist es lehrreich einen Blick in die Vergangenheit zu unternehmen und zu untersuchen woran früher die Umsetzung Künstlicher Intelligenz gescheitert ist. Das dominante ungelöste Problem über Jahrzehnte innerhalb der Informatik waren NP harte Probleme. Damit ist eine Kategorie von Aufgabenstellungen gemeint, die einen sehr großen Suchbaum aufweisen wie motion planning in der Robotik, trajectory optimiziation, state space planning und model predictive control.
Es gab früher durchaus Ansätze um np harte probleme zu lösen und zwar mittels Heuristiken, allerdings gab es dafür keine Generalisierung. Bei Motion planning wurden z.b. Kostenfunktionen verwendet um zu entscheiden, welche Knoten des Suchbaums zuerst erweitert werden. Der RRT Algorithmus verwendet eine solche Heuristik, aber auch A* nutzt es.
Sobald ein Problem als np hart erkannt wurde und es keine Heuristiken zu dessen Lösung gibt, ist der Rechenaufwand zu hoch um es mit einem Computer zu lösen. So kann man zeigen dass bestimmte Computerspiele unlösbar sind für eine KI. Nur bei kleinem Suchbaum und vorhandenen Heuristiken konnten Computerprogramme in der Vergangenheit Spiele gewinnen, wie dies bei Computerschach oder Tictactoe demonstriert wurde.
Robotikprobleme wie dexterous grasping und biped walking hingegen wurden als np harte Probleme erkannt, es fehlte an Heuristiken und folglich waren diese Probleme unlösbar für damalige Computerhardware.
Das erwähnte NP Hard Problem ist ein sehr wichtiges Gebiet innerhalb der Informatik wie auch der Künstlichen Intelligenz und es gibt sehr viele Bücher und Paper zu der Thematik. Google Scholar findet z.B. 2 Millionen Paper zu "np hard problems". Gleichzeitig stellt es eine Sackgasse in der Forschung da, die meisten Wissenschaftler waren der Meinung dass es unlösbar ist und folglich KI nicht möglich ist.
Der Diskurs betrachtet Probleme aus der realen Welt unter einem streng mathematischen Blick. zuerst wird untersucht wie groß der Problemraum ist, also wie viele Möglichkeiten in einem Computerspiel existieren eine Entscheidung zu treffen. Dann wird untersucht wieviele Möglichkeiten es gibt wenn man die Zeitachse berücksichtigt, z.B. kann in einem Jump'n'Spiel der Charakter bei timecode #00:01 in die Luft springen oder bei timecode #0:05. Und zu Letzt wird untersucht in welchen Fällen das Computerspiel gewonnen wird, also ob statistisch gesehen es viele Wege ins Ziel gibt oder nur sehr wenige.
Aus dieser Analyse kann man dann abschätzen wie groß der Suchraum ist, und ob es möglich ist Computerspiele nur durch zufälliges Durchprobieren zu lösen. Teilweise wird versucht mittels Optimierungsverfahren wie reinforcement learning einen Algorithmus zu konstruieren, der von allein Spiele gewinnen kann.
Wie schon erwähnt stellen diese Ansätze eine Sackgasse da. Sowohl die mathematische Analyse des Problemraumes, als auch stochastische Suchverfahren sind nicht im Stande Robotikprobleme zu lösen. Über Jahrzehnte drehte sich die Forschung im Kreis, es gelang nicht die erwähnten NP Harten probleme zu lösen, Heuristiken zu konstruieren oder zu ergründen woran es genau scheiterte.
Interessanterweise erbrachte selbst der Einsatz von neuronalen Netzen keinen Fortschritt. Wenn man beispielsweise einen Deep learning Algorithmus auf einer modernen GPU Grafikkarte startet damit dieser Algorithmus ein Jump'n'Run Videospiel gewinnt, wird der Ansatz scheitern. Der Problemraum ist viel zu groß, als das das neuronale Netz von allein die richtigen Entscheidungen lernt. Es gab in den 2010er Jahren dazu mehrere Beispiele aber keines davon war in der Lage künstliche Intelligenz zu realisieren.
Das Dilemma der KI in der Forschung in der Vergangenheit war, dass für die meisten Computerspiele wie auch Robotikprobleme klar erkannt wurde, dass es sich um np hard probleme handelte. Gleichzeitig fehlte es an einem Algorithmus um diese Probleme zu lösen. Was es gab waren Brute Force Algorithmen zum vollständigen Durchsuchen des State Space, diese hatten aber eine sehr hohe Laufzeit auf einer CPU und waren damit nicht praktikabel.
Die Analyse von np harten Problemen sowie der Beweis, dass eine bestimmte Aufgabe zu dieser Kategorie gehört, kann man als klassische Informatik definieren, welche nach mathematischen Prinzipien erfolgte. Über mathematische Formeln wurde gezeigt wie groß der Problemraum ist, auf dem Computer wurden Algorithmen implementiert um diesen zu durchsuchen und die Ausführung der Algorithmen auf Hardware ergab, dass das Problem nicht lösbar ist. Der Diskursraum war also klar definiert. Die einzige Innovation bestand darin sehr spezielle Heuristiken zu erfinden welche die Ausführungszeit der Suche leicht verbesserten. Das also mit der richtigen Heuristik eine Pfadplanung in einer 2d Karte nicht länger 10 Sekunden dauert sondern nur 1 Sekunde.
Leider waren verbesserten Heuristiken und neuartige Suchalgorithmen wie RRT nicht im Stande Real life Probleme zu lösen wie sie in der Robotik existierten. Selbst stark vereinfachte Robotik-Challanges wie Micromouse erzeugen einen hochkomplexen Suchraum. Man wusste zwar durch mathematische Analyse wie groß der Suchraum genau ist und wie lange es dauert diesen vollständig zu durchsuchen aber es war unklar wie man das Problem, also z.b. micromouse, lösen kann.
Die Forschung zu np harten Problemen lässt sich in Phasen unterteilen:
1980er Jahre, optimistische Sicht, mit schnellerer Hardware und neuen Algorithmen lassen sich derartige Probleme lösen
2000er Jahre, neutrale Sicht, bestimmte Motion Planning probleme sind so komplex dass man probabilistische Algorithmen benötigt und nur Teilprobleme lösen kann
2010er Jahren, pessimistische Sicht, np harte Probleme sind unlösbar, Mathematik ist prinzipiell nicht in der Lage das Problem zu lösen, vorhandene Algorithmen sind nutzlos
Erst die pessimistische Sicht in den 2010er Jahre machte den Weg frei für eine komplett andere Sichtweise. Damit ist gemeint, eine nicht mathematische und eine nicht algorithmische Sichtweise zu nutzen. Selbst heute im Jahr 2026 erscheint ein solcher gegensätzlicher Ansatz als absurd, weil ja Informatik auf Mathematik aufbaut und weil Algorithmen das zentrale Element der Informatik sind. Computer basieren auf Logik, aber nicht auf Intuition und Algorithmen enthalten Anweisungen aber keinen Kontext. Es verwundert wenig dass sich die Informatik schwer damit tat, das vertraute Gebiet zu verlassen und komplett neue Ansätze zu verfolgen.
Es gab eine Meilensteine in der Geschichte der Robotik welche ein Ablösung von der Mathematik und von Algorithmen propagierten: So hat im Jahr 1990 Rodney Brooks postuliert, dass die Umgebung eines Roboters als Steuerung verwendet werden kann, während im Jahr 2000 Cynthia Breazeal erstmals die Interaktion von Robotern mit Menschen näher erforscht hat. In beiden Fällen lag der Fokus nicht länger auf dem Roboter selber sondern auf der Umgebung innerhalb derer der Roboter agiert. Diese Umgebung kann ein Labyrinth sein, in dem der Roboter herumfährt oder es kann ein Mensch der in die Kamera schaut. Der Fokus auf die Umgebung stellt einen wichtigen Beitrag da um np harte Probleme anders zu untersuchen.
No comments:
Post a Comment