Planen ist ein wichtiges Teilgebiet der künstlichen Intelligenz. Zum einen aus theoretischen Gründen: wir möchten besser verstehen, wie menschliches Planen funktioniert, zum anderen aus ganz praktischen Gründen: wir möchten unsere Ressourcen effizient verplanen.
Im Alltag werden Pläne fast ausschließlich von Menschen erstellt. Sicherlich unterstützen uns Computer dabei: sie berechnen Dauern, überwachen den Bedarf an Mitteln und helfen uns beim Visualisieren von Plänen. Die Kernfunktionen, die Entscheidung, was beim Planen beachtet werden muss und ob der Plan wirklich funktioniert, treffen wir in der Regel selbst.
Sind alle Bestandteile klar, die für den Plan benötigt werden, können Computer die Planung komplett autonom übernehmen. Eines der bekanntesten Beispiele aus dem Alltag dazu sind Navigations-Systeme. Das Finden einer optimalen oder zumindest einer sehr guten Route, sind Beispiele von automatischem Planen, wie es beim Problem des Handlungsreisenden auftritt (kam in diesem Artikel vor).
Viel schwieriger wird es im Umgang mit realen Objekten. Das klassische Beispiel aus dem Automated Planning ist ein Roboter-Kran, der Container von einer Palette auf eine andere Palette und auf einen LKW verladen kann.
Hier wird, ähnlich wie bei der Navigation, ein Ziel-Zustand gesucht: Der Container liegt am Ende des Plans auf dem LKW. Dazu hat das System verschiedene Aktionen wie take(Container von Palette), move(Roboter-LKW), load(Container auf LKW). Diese Aktionen müssen nun nur noch in der richtigen Reihenfolge kombiniert werden und schon hat das System seinen Plan.
Um nun zu wissen, welche Aktionen im Plan hintereinander passieren müssen, muss das System wissen, wann welche Aktionen ausgeführt werden können: Man muss modellieren, welche Aktionen welche Auswirkungen haben, und welche Vorbedingungen erfüllt sein müssen, damit eine Aktion ausgeführt werden kann.
Beispielsweise:
- take:
- Vorbedingung: Container liegt auf Palette,
- Effekt: Container hängt im Kran
- load:
- Vorbedingung: Container hängt an Kran,
- Effekt: Container liegt auf LKW
Der findige Leser merkt aber schnell, dass das an Bedingungen nicht ausreicht. Für take muss bspw. der Kran auch leer sein. Für load muss auch der LKW leer sein und er muss an der richtigen Stelle stehen. Um von einem Start-Zustand zu einem Ziel-Zustand zu kommen, müssen die Zustände genau beschrieben sein.
Was weißt du eigentlich?!?…
Je mehr Möglichkeiten es gibt, desto mehr muss beschrieben werden, denn in der Planungs-Phase kann das System ja nicht einfach beobachten was passiert: Stehen Container in einem Stapel, dann muss der Container ganz oben sein, damit der Kran ihn nehmen kann. Habe ich zwei Paletten, dann muss der Container auf der richtigen Palette sein und so weiter und so fort.
Hier ist die Beschreibung eines solchen Zustandes. Für jeden Container ist einzeln angegeben, wo er sich gerade befindet, auf welcher Palette (in), welcher Container auf welchem steht (on) und welcher Container ganz oben steht (top).
Bei einer Aktion muss exakt beschrieben werden, was sich alles dadurch ändert. Beispielsweise muss bei put auch festgelegt werden, welcher Container jetzt oben liegt. Das System kann in der Planungsphase ja nicht einfach beobachten, welche Container nach eine Aktion oben liegt – es muss es irgendwie „wissen“.
Man sieht schon, dass es relativ aufwändig werden kann, einen Zustand exakt genug zu beschreiben und auch die Effekt einer Aktion richtig festzulegen. Vergisst man beispielsweise bei der Operation put festzulegen, welcher Container jetzt oben liegt, dann entwirft das System einen völlig falschen Plan – oder findet gar keine Lösung.
Dass das sehr komplex werden kann, merkt man, wenn man sich überlegt, dass auf dem Container nochmal kleine Pakete liegen: Verschiebt man den Container, dann verschiebt man auch die Pakete. Das „weiß“ das System aber nicht einfach so. Für jedes einzelne Paket müsste dem System gesagt werden, wo es sich nach dem Verschieben des Containers befindet.
Man könnte sich Vereinfachungen dazu überlegen. Nach einem put könnte man automatisch berechnen, welche „Seiteneffekte“ die Aktion auf andere Objekte hat. D.h. man benötigt eine Art „Welt-Modell“, wie man es aus Computer-Spielen kennt. Bewege ich Objekt x, dann stößt es an Objekt y und bewegt dieses auch.
Hat man ein solches Welt-Modell, dann wird es einfacher. Aber das Welt-Modell muss man eben erst einmal haben. Es muss exakt genug sein, um die Werte aller Prädikate eines Welt-Zustands herauszubekommen, wie:
Zustand x =
- „Container1 ist in Stapel1“
- „Container1 liegt auf der Palette2“
- „Container2 ist auch in Stapel1“
- „Container2 liegt auf Container1“
- „Container2 ist ganz oben in Stapel1“
- usw…
Auch in Computerspielen entsprechen solche 3D-Welt-Modelle nie exakt der Wirklichkeit: manche Dinge kann man nicht bewegen, manchmal kann ein Spieler durch einen graphischen Fehler scheinbar in eine Wand laufen, usw.
Ob man nun jedes Prädikat von Hand angibt oder von einem Welt-Modell berechnen lässt – es gibt weitere wichtige Herausforderungen:
- Effekte – nicht alles wird durch Aktionen des Systems hervorgerufen. Vieles passiert von ganz alleine! In einer Umgebung, in der es spontane Bewegung gibt, kann es recht kompliziert sein. Wie berücksichtige ich in meinem Plan beispielsweise, ob ein Hindernis vor meinen Roboter auftaucht?
- Replanning – wenn ein Plan nicht funktioniert – also einer der geplanten Zustände nicht erreicht wird – muss der Plan angepasst werden.
- Zeitliche Abläufe – wartet der Plan darauf, dass ein Zustand erreicht wird, oder kann eine Aktion bereits parallel ausgeführt werden.
- Wiederverwendbarkeit – muss berücksichtigt werden, dass Ressourcen nur einmal verwendet werden können? Wenn ein Koch-Plan das Salzen der Suppe einplant, dann muss auch Salz da sein.
- etc.
Einfach ausprobieren?
Im letzten Artikel ging es um Reinforcement Learning. Ein System kann dort durch Ausprobieren lernen, in welchem Zustand welche Aktion am besten ist. Wenn man es oft durchlaufen lässt, dann könnte ein System doch einfach lernen, wie es seine Aktionen planen kann?
Mal abgesehen vom zeitlichen Aufwand kann man ein Programm nicht in 1000 Durchläufen versuchen lassen Container ins Leere zu stapeln oder LKWs zu beladen, die nicht da sind, bis ein passender Algorithmus gefunden ist. Das ist vielleicht doch ein wenig zu kostspielig… Dagegen kann es lohnend sein, den Lernprozess erstmal nur in einem Welt-Modell zu simulieren und nur das, was dort funktioniert, auf die Welt loszulassen. Solche Hybrid Systeme zwischen Reinforcement Learning und Automated Planning werden erforscht.
Was machen eigentlich Menschen?
Auch wir lernen durch Ausprobieren. Im Gegensatz zur „Reinforcement Learning“-Technologie probieren wir aber in einer Situation nicht erstmal alle Möglichkeiten aus. Wir nutzen interne Modelle. In unserem Kopfe drehen und wenden wir Gegenstände und setzen sie zusammen.
Menschen verbessen ihr Welt-Modell (oder eher: ihre Welt-Modelle) ständig und sind auch zu Generalisierungen und Übertragungen von (Teil-) Modellen auf andere Situationen fähig. Wir orientieren uns dabei an unserer Erfahrung, probieren Bewegungen aus, und lernen aus neuen Beobachtungen an.
Wie funktioniert das mit den Modellen beim Menschen?
Das wüssten wir gerne. Dieses konzeptionelle, übertragungs- und anpassungsfähige Lernen wird eifrig erforscht und ist noch ein großes Rätsel. Alle bisher entwickelten Systeme sind Lösungen für spezielle Probleme und Situationen. Es gibt kein System das in einer Vielzahl von Situationen oder gar im Alltag plan- und handlungsfähig wäre.
Bei meinen Recherchen bin ich bisher auf verschiedene Ansätze gestoßen und bin gespannt was da noch kommt. Mein Bild setzt sich gerade aus drei Bestandteilen zusammen:
- Logik und Planung – Inferenz, Induktion, Suche: der klassische Ansatz, bei dem kognitive Fähigkeiten vor allem als Symbolmanipulationen angesehen werden: Das Welt-Modell liegt in seiner kompletten Beschreibung vor, wie oben diskutiert. Daraus lassen sich nun durch Kombination der Regeln und Suche in den Kombinationsmöglichkeiten alle Schlüsse ziehen und Regeln für die Handlungen ableiten.
- Wahrscheinlichkeit und Unsicherheit – Markov, POMDP, Hidden Markov, Particle Filter, Bayes Netze: Mittels Beobachtungen und modellierter Abhängigkeiten lassen sich Rückschlüsse über den aktuellen Zustand der Welt ziehen und welche Handlungen oder Urteile wahrscheinlich am besten wären.
- Feedback-Schleifen und Machine Learning – Reinforcement Learning, Clustering, Support Vector Machines, Neurale Netze, Backpropagation: nach Bewertung eigener Aktionen oder durch Feedback eines Lehrers ändern sich die Werte der internen Variablen, die zur Beurteilung einer Situation genutzt werden. Man nutzt sie um Cluster und Muster in Daten zu finden, im Lernprozess von Bildererkennungssystemen oder eben Handlungsplanung.
In Anwendungen finden sich natürlich Mischformen. In der Spracherkennung (Natural Language Processing) beispielsweise, bei der Laute mit Wahrscheinlichkeiten auf Worte überführt werden und diese dann anhand von logischen Modellen in Sätzen gruppiert werden. Das Zusammenspiel der verschiedenen Ansätze kann sich gegenseitig korrigieren. So können Laute im Kontext eines Satzes neu bewertet und als andere Worte erkannt werden. Auch in der Bilderkennung werden nicht nur Neurale Netze eingesetzt und im Reinforcement Learning werden auch Wahrscheinlichkeiten beurteilt (wie wahrscheinlich ist es, dass Aktion a zu Zustand s geführt hat)
Die drei Ansätze lassen aber ganz gut erkennen, zwischen welchen Polen die Forschung der künstlichen Intelligenz hin und her schwingt – zwischen Intern und Extern: interne Modelle müssen zu den externen Beobachtungen passen und werden über Wahrscheinlichkeiten und Feedback zugeordnet.
Die Herausforderung ist: wie dynamisch machen wir die Modelle und über welche Feedback-Schleifen verbinden wir Internes und Externes. Es ist offensichtlich unmöglich mit beschreibenden Modellen die Wirklichkeit komplett und auch noch richtig darzustellen, wie oben am Beispiel des Automated Planning klar wurde. Modelle müssen offensichtlich immer unvollständig sein und sich erweitern und verändern können, wenn neues beobachtet wird. Wie kann das technologisch möglich sein?
Mehr dazu beim nächsten Mal…
