3-Layer Architektur
Seminarvortrag zu „Lernalgorithmen in der Robotik“
Thema: Die Subsumption-Architektur und deren Erweiterungen
René Pachernegg (rene_p@sbox.tu-graz.ac.at)
Bis zur Veröffentlichung von Brook (1986) hat allgemein die Ansicht vorgeherrscht, daß ein Kontroll-System für autonome, mobile Roboter im wesentlichen aus 3 funktionellen Elementen bestehen sollte:
Sensing System
Planning System
Macht aus diesem Modell der Welt und einem bestimmten Ziel einen Plan für die weitere Vorgehensweise.
Execution (Action) System
Dieses System wird allgemein als SPA-System (Sense-Plan-Act) bezeichnet (siehe Folien).
Problem:
Planning und World-Modelling sind komplexe Probleme, zu rechenaufwendig, und daher zu langsam angesichts einer sich dauernd verändernden Umwelt.
Mitte der 80er hat man dann erkannt, daß man möglicherweise in eine Sackgasse gelaufen ist. Die Lösungsvorschläge verwendeten alle das Stichwort „reactive planning“.
Eine konkrete Lösung wurde zuerst von Rodney Brooks mit seiner Subsumption Theorie präsentiert, die bereits vorgestellt wurde (siehe Folien). Die häufigsten Probleme der Roboter, die mit diesem System arbeiteten, waren:
Mangel an Flexibilität
Das Ziel, das ein Roboter zu verfolgen hatte, wird direkt in das Reactive-System implementiert. Weiters sind ja Verhaltensweisen auf höherem Niveau von denen auf niedrigerem abhängig. Das Verändern des Ziels eines Roboters oder eines Verhaltens auf niedrigem Niveau erfordert somit oft eine umfangreiche Umprogrammierung.
Unverläßlichkeit
Es wird immer nur auf direkte Reize reagiert, und damit nur die Gegenwart betrachtet. Allerdings können Vergangenheits und Zukunftsbetrachtungen sehr wichtig sein. Außerdem wird der Sensoren-Unsicherheit nicht Rechnung getragen.
Ausgehend von diesen Erkenntnissen entwickelten 1991 3 Forschungsgruppen unabhängig voneinander Architekturen, die man als 3 Layer Architekturen bezeichnet und die im wesentlichen gleich sind. Der Hauptunterschied liegt in der Benennung der einzelnen Layers. Im weiteren wird nur die sogenannte Atlantis Architektur von Erann Gat behandelt, die aber repräsentativ für alle 3 Lösungen ist.
Internal State
Unter internal State versteht man die interne Repräsentation der Umwelt im Roboter. Diese Repräsentation ist von wesentlicher Bedeutung für die Motivation und den Aufbau der 3-Layer Architektur.
Zurück zur SPA Architektur. Während der Erstellung eines Planes, was sehr zeitaufwendig ist, kann sich die Umgebung auf eine Art und Weise verändern, die diesen Plan ungültig macht. Weiters kann ein unerwartetes Resultat der Ausführung eines Planes, weitere Aktionen im falschen Zusammenhang hervorrufen. Das ergibt ein Problem, daß man „runnig researcher syndrome“ nennt, da das oft darauf hinauslaufen kann, daß man einem wild gewordenen Roboter hinterherjagen muß, um den Emergency-Stop-Knopf zu drücken.
Andererseits kann es passieren, daß rein reaktive Roboter in Hindernisse hineinlaufen, die aufgrund der Sensorenunsicherheit nicht gesehen werden konnten, obwohl sie erst vor kurzer Zeit aus den selben Gründen in das selbe Hinderniss gerannt sind.
Alle diese drei Probleme kann man auf den Umgang mit den Informationen über den internen Status zurückführen. Die SPA-Architektur erzeugt mittels aufwendiger Berechnungen einen internen Status, der die Vergangenheit, die Gegenwart (World Models) und die Zukunft (Pläne) repräsentiert. Diese Roboter versagen nun, wenn der interne Status die Synchronität zur realen Unmgebung verliert.
Die Architektur von Brooks verzichtet hingegen ganz auf die Speicherung und Verarbeitung eines internen Status (Slogan: „The world is it’s own best model.“). Manchmal könnte es aber ganz angenehm sein, wenn ein Roboter sich erinnern könnte, daß da gerade noch eine Wand vor ihm war und dementsprechen reagiert, obwohl seine Sensoren, vielleicht aufgrund von spekularen Refektionen nichts mehr anzeigen. Auch ein Mensch läuft nicht öfter als einmal direkt hintereinander in die selbe gut geputzte Glastür.
Durch diese Elimination des internen Status wird dessen zeitaufwendige Verarbeitung vermieden. Das verschlimmert aber die Folgen von ungenauen Sensoren.
Die 3 Layers des 3T Systems sind nun so organisiert, daß die jeweiligen Algorithmen, abhängig von den zu verarbeitenden internal States, einem bestimmten Layer zugeordnet werden:
kein interne Status, nur sensor-basierend (Controler).
Informationen über die Vergangenheit (Sequencer).
Voraussagen über die Zukunft (Deliberator).
Die Komponenten der 3-Layer Architektur (siehe Folien)
Der Controller
Der Controller arbeitet im wesentlichen ähnlich wie Brooks reaktives System. Auch hier werden die Sensordaten ohne Umschweife von den Verhaltensalgorithmen mehr oder weniger direkt in Befehle für dir Robotermotorik umgewandelt. Diese Verhalten sind nichts anderes als Transferfunktionen und können Run-Time verändert werden. Üblicherweise enthält der Controller eine ganze Library solcher Transferfunktionen, die über einen externen Input aktiviert, bzw. deaktiviert werden können.
Die Architektur des Controllers unterliegt mehreren, sich von den Entwicklern selbst auferlegten Einschränkungen:
Transferfunktionen sollen eine durch eine Konstante beschränkte Rechenzeit und Speicherbedarf besitzen.
Algorithmen müssen erkennbar versagen. D.h. sie sollen so aufgebaut sein, daß ein Fehler mit 100% Wahrscheinlichkeit entdeckt werden kann, da es unmöglich ist Algorithmen zu entwerfen, die auf unsicheren Sensordaten aufbauen und zu 100% fehlerfrei sind. Damit können andere Komponenten des Systems die Fehlerkorrektur übernehmen.
Die Verwendung von internal states sollte wenn möglich vermieden werden. Falls sie doch verwendet wird, sollte das nur mit Ablaufdatum geschehen. Denn, wenn diese internal states einmal nicht die tartsächliche Umwelt reflektieren, so entsteht ein Fehler nur für einen konstanten Zeitraum.
Der internal state soll keine Diskontinuitäten in ein Verhalten bringen. D.h.: Unabhängig vom internal State soll die Transferfunktion immer verläßlich ausführbar sein.
3.2 Der Sequencer
Die Aufgabe des Sequencers ist es zu bestimmen, welche Verhaltensweise (bzw.: Transferfunktion des Controllers) zu einem bestimmten Zeitpunkt aktiv sein soll. Durch das Wechseln von Verhalten zu strategisch günstigen Zeitpunkten kann der Roboter dazu gebracht werden, sinnvolle Tasks auszuführen. Da allerdings die Wahl eines bestimmten Verhaltens in bestimmten Situationen nicht immer die richtige Entscheidung ist, und damit eine ganze Sequenz unverläßlich wird, muß der Sequencer fähig sei auf aktuelle Situationen zu reagieren und damit mehrere unterschiedliche Sequenzen von Verhaltensweisen für ein und denselben Task zur Verfügung haben.
Eine Lösung dafür besteht darin, für alle Kombinationen von möglichen Situationen ein Sequenz bereitzuhalten, was aber nur für eingeschränkte Aufgabengebiete funktioniert. Einerseits ist nicht immer eindeutig festzustellen in welcher Situation man sich gerade befindet, und andererseits wird dabei keine Rücksicht auf vergangene Ereignisse genommen, die durchaus als Hilfestellung für Entscheidungen dienen können.
Eine andere Möglichkeit ist das „conditional sequencing“. Ausgangspunkt für diese Alternative ist die Fähigkeit des Menschen, genau umrissene Aufgaben unter unterschiedlichen Bedingungen verläßlich ausführen zu können.
In keiner der verwendeten Unterlagen konnte ich etwas Genaueres darüber finden. Ich nehme allerdings an, daß die „Vergangenheitsbewältigung“ hier eine größere Rolle spielt. Das Versagen einer bestimmten Sequenz zu einer bestimmten Situation in der Vergangenheit könnte den Sequenzer dazu bewegen eine andere Saquenz zu verwenden (oder sogar auszuprobieren). Hier könnten verschiedene Lernalgorithmen Anwendung finden.
3.3 Der Deliberator
Hier finden die zeitaufwendigen Berechnungen, wie Planen und Suchalgorithmen statt. Eine Aufgabe des Deliberators kann auch die rechenintensive Analyse von Videobildern sein. Das Problem dabei ist, daß während der Berechnungszeit wieder viel passieren kann. Daher muß er sich mit Problemen beschäftigen, deren Parameter sich nicht oder nur sehr langsam ändern, bzw. deren Lösung nicht allzu schnell benötigt wird.
Es gibt zwei Möglichleiten, wie der Deliberator mit dem Rest des Systems zusammenarbeiten kann. Entweder produziert er Pläne, die der Sequenzer dann exekutiert oder er beantwortet Anfragen des Sequencers (z.B.: Suchen oder Optimieren). Natürlich können diese beiden Möglichkeiten auch kombiniert werden.
Eine Fallstudie
Am besten versteht man die 3-Layer Architektur anhand eines Beispiels. Es gibt bereits einige Roboter, die diese Architektur verwenden. Im folgenden werde ich die Programmierung des Roboters Alfred anläßlich eines Wettbewerbs der AAAI (American Association for Artificial Intelligence) 1993 beschreiben.
Alfred ist ein zylindrischer Roboter, mit einem Gespak-Board, auf dem sich ein 68000er Prozessor befindet. Über die serielle Schnittstelle dieses Boards wurde außerdem noch ein Macintosh Powerbook verbunden. Der Code für den Controller wurde am Gespak Board ausgeführt, der Sequencer und der Deliberator am Powerbook. Der Roboter besitzt 12 Sonar-Sensoren und kann zusätzlich Kollisionen entdecken.
Der Wettbewerb bestand aus zwei Aufgaben. Im ersten mußten die Roboter aus einem Büroraum voll mit Hindernissen einen Weg zu einer offen Tür finden. Beim zweiten mußte in einem Labyrinth eine Kaffetasse gefunden und zu einem bestimmten Punkt gebracht werden. Im weiteren werde ich die Rolle der einzelnen Layer bei diesem Wettbewerb beschreiben.
Control Layer
Der Controller von Alfred hatte im wesentlichen 5 interessante Verhalten: obstacle avoiding, wall finding, wall alignment, wall following und wandering.
Bei der Hindernisvermeidung unterschied Alfred abhängig von der Entfernung der Hindernisse zwischen „hard obstacles“ und „soft obstacles“ (siehe Folien). Der Controller Code dazu hat in etwa so ausgesehen:
IF there is a collision while moving forward
BACK UP slowly for a few seconds
ELSE IF there is a collision while moving backwards
STOP for a few seconds
ELSE IF there is an obstacle in one of the hard obstacle regions
STOP
ELSE IF there is an obstacle in one of the soft obstacle regions
set the current speed to SLOW
ELSE (no obstacles)
gradually increase the forward speed up to the maximum value
o
o
o
IF there is an obstacle in the soft-right obstacle region and not in the soft-left obstacle region
turn slowly to the left
IF there is an obstacle in the soft-left obstacle region and not in the soft-right obstacle region
turn slowly to the right
ELSE
go straight or turn toward a commanded heading
Damit wird der Roboter immer langsamer je näher ein Hindernis kommt und beschleunigt sofort, wenn keine Hinderniss mehr im Weg sind. Wen es klar ist, in welche Richtung man vor einem Hindernis ausweichen muß, wird das im Controller erledigt. Ist es nicht ganz klar, so wird diese Aufgabe dem Sequencer überlassen (siehe dort).
Dieser Code verwendet „internal states“ in den ersten zwei Bedingungen. Daher sollten sich diese Zeilen eigentlich im Sequencer befinden. Da aber bei einer Kollision die Steuerung stark belastet wird, war es sicherer für den Roboter, diesen Teil im schnelleren Controller zu belassen. Daran kann man sehen, daß die Entscheidungsgrenzen in welches Layer ein bestimmter Code gehört nicht immer eindeutig ist und etwas Spielraum erlauben muß.
Sequencing Layer
Zu Beginn des ersten Bewerbes wurde dem Roboter seine Anfangsausrichtung und die Größe des Raumes mitgeteilt, allerdings weder seine eigene Position noch die der Hindernisse.
Zu Beginn wanderte Alfred nur zufällig herum, immer die aktuellen x- und y-Koordinaten speichernd, bis er seine Position im Raum erkannt hatte. Dann begab er sich in die Mitte des Raumes und richtete sich nach der ersten der drei möglichen Tür-Positionen aus, die im auch vorher schon mitgeteilt wurden. Er steuerte einfach auf die Tür zu, die Hindernisvermeidung eingeschaltet und wartete dann, ob er entkommen war. Wenn nicht versuchte er das ganze nochmals mit der nächsten Tür. Die Hindernisvermeidung für nicht eindeutige Fälle (siehe Kontroller) bewältigte er, indem er sich abwechselnd immer nach links und rechts drehte und gleichzeitig den Winkel dieser Drehung erhöhte, bis sich ein eindeutiger Fall ergab. Wichtig dabei ist darauf zu achten, daß man dabei in keinen „endless loop“ kommt.
Im zweiten Bewerb wurde dem Roboter ein Plan des Labyrinths mitgegeben, sowohl dessen offene Räume als auch eine Repräsentation der Mauern, und eine ungefähre Position der Kaffetasse die er finden sollte. Seine eigene Position mußte er selbst herausfinden.
Der Roboter versuchte zu Beginn eine Mauer zu finden. Um sicher zu sein, daß es sich auch um eine Mauer handelte und nicht um ein Hindernis, folgte er ihr und nach zwei Metern erkannte er „das Ding“ als Mauer. Indem er einer Mauer immer weiter folgte, konnte er so einen Teilausschnitt der Labyrinthmauern aufnehmen und mit den ihm mitgegebenen Informationen vergleichen. Diese Vergleiche geschahen im Deliberator. Sobald er wußte wo er war, fuhr er die möglichen Positionen der Kaffetasse ab und dann auf direktem Weg zum Ziel.
Besonders zu beachten ist, daß der Sequencer sehr oft „internal states“ verwendet.
Der Deliberator
Der Deliberator wurde nur im 2. Bewerb eingesetzt, wo er die Vergleiche zwischen abgefahrener Mauerpartie und mitgegebener Karte vornahm und zum Planen der Wege zur Kaffetasse, bzw. zurück zum Ziel.
Tatsächlich war der Deliberator der uninteressanteste Teil von Alfred.