Reaktive Planung

In der künstlichen Intelligenz bezeichnet reaktive Planung eine Gruppe von Techniken zur Auswahl von Aktionen durch autonome Agenten. Diese Techniken unterscheiden sich von der klassischen Planung in zwei Aspekten. Erstens arbeiten sie zeitnah und können daher mit hochdynamischen und unvorhersehbaren Umgebungen umgehen. Zweitens berechnen sie in jedem Moment nur eine nächste Aktion, basierend auf dem aktuellen Kontext. Reaktive Planer nutzen häufig (aber nicht immer) reaktive Pläne, die gespeicherte Strukturen sind, die die Prioritäten und das Verhalten des Agenten beschreiben.

Obwohl der Begriff reaktive Planung mindestens 1988 zurückgeht, ist der Begriff „reaktiv“ mittlerweile ein Abwertungsfaktor, der als Gegenbegriff für proaktive Zwecke verwendet wird. Da fast alle Agenten, die reaktive Planung verwenden, proaktiv sind, bezeichnen einige Forscher die reaktive Planung als dynamische Planung.

Reaktive Planrepräsentation
Es gibt verschiedene Möglichkeiten, einen reaktiven Plan darzustellen. Alle erfordern eine grundlegende Darstellungseinheit und ein Mittel, um diese Einheiten zu Plänen zusammenzusetzen.

Condition-Action-Regeln (Produktionen)
Eine Bedingungsaktionsregel oder Wenn-Dann-Regel ist eine Regel im Formular: Wenn Bedingung, dann Aktion. Diese Regeln werden als Produktionen bezeichnet. Die Regel hat folgende Bedeutung: Wenn die Bedingung erfüllt ist, führen Sie die Aktion aus. Die Aktion kann entweder extern sein (z. B. etwas aufnehmen und verschieben) oder intern (z. B. einen Fakt in den internen Speicher schreiben oder ein neues Regelwerk auswerten). Bedingungen sind normalerweise boolesch und die Aktion kann entweder ausgeführt werden oder nicht.

Produktionsregeln können in relativ flachen Strukturen organisiert sein, sind jedoch häufiger in einer bestimmten Hierarchie angeordnet. Beispielsweise besteht die Subsumtionsarchitektur aus Schichten miteinander verbundener Verhaltensweisen, von denen jede tatsächlich eine Zustandsmaschine ist, die auf eine geeignete Eingabe reagiert. Diese Ebenen werden dann in einem einfachen Stapel organisiert, wobei höhere Ebenen die Ziele der unteren Ebenen vereinigen. Andere Systeme verwenden möglicherweise Bäume oder enthalten spezielle Mechanismen zum Ändern, welche Ziel- / Regel-Teilmenge derzeit am wichtigsten ist. Flache Strukturen sind relativ einfach zu bauen, erlauben aber nur die Beschreibung eines einfachen Verhaltens oder erfordern immens komplizierte Bedingungen, um die fehlende Struktur zu kompensieren.

Ein wichtiger Bestandteil aller Auswahlalgorithmen für verteilte Aktionen ist ein Mechanismus zur Konfliktlösung. Dies ist ein Mechanismus zum Lösen von Konflikten zwischen vorgeschlagenen Aktionen, wenn mehr als eine Regelbedingung in einem bestimmten Moment gilt. Der Konflikt kann zum Beispiel durch gelöst werden

den Regeln im Voraus feste Prioritäten zuweisen,
Präferenzen zuweisen (zB in Soar-Architektur),
relativen Nutzen zwischen Regeln lernen (zB in ACT-R),
eine Form der Planung nutzen.
Expertensysteme verwenden häufig andere einfachere Heuristiken, wie z. B. Aktualität, um Regeln auszuwählen. Es ist jedoch schwierig, mit einfachen Ansätzen ein gutes Verhalten in einem großen System zu gewährleisten.

Konfliktlösung ist nur für Regeln notwendig, die sich gegenseitig ausschließende Maßnahmen ergreifen wollen (vgl. Blumberg 1996).

Einige Einschränkungen dieser Art von reaktiver Planung sind in Brom (2005) zu finden.

Finite-State-Maschinen
Finite State Machine (FSM) ist ein Verhaltensmodell eines Systems. FSMs sind in der Informatik weit verbreitet. Das Modellierungsverhalten von Agenten ist nur eine ihrer möglichen Anwendungen. Ein typischer FSM besteht, wenn er zur Beschreibung des Verhaltens eines Agenten verwendet wird, aus einer Reihe von Zuständen und Übergängen zwischen diesen Zuständen. Die Übergänge sind eigentlich Bedingungsaktionsregeln. In jedem Moment ist nur ein Zustand des FSM aktiv und seine Übergänge werden ausgewertet. Wenn ein Übergang genommen wird, wird ein anderer Status aktiviert. Das heißt, im Allgemeinen sind die Übergänge die Regeln in der folgenden Form: Wenn Bedingung, dann Aktivierungs-Neuzustand. Übergänge können jedoch in einigen Systemen auch mit dem „Selbstzustand“ verbunden werden, um die Ausführung von Übergangsaktionen zu ermöglichen, ohne den Zustand tatsächlich zu ändern.

Es gibt zwei Möglichkeiten, wie ein FSM ein Verhalten erzeugen kann. Sie hängen davon ab, was von einem Designer mit den Zuständen in Verbindung gebracht wird – sie können entweder „Acts“ oder Skripts sein. Eine ‚Aktion‘ ist eine atomare Aktion, die der Agent ausführen soll, wenn seine FSM der angegebene Status ist. Diese Aktion wird dann in jedem Zeitschritt ausgeführt. Häufiger ist jedoch der letztere Fall. Jeder Status ist hier einem Skript zugeordnet, das eine Folge von Aktionen beschreibt, die der Agent ausführen muss, wenn sich sein FSM in einem bestimmten Status befindet. Wenn ein Übergang einen neuen Zustand aktiviert, wird das vorherige Skript einfach unterbrochen und das neue gestartet.

Wenn ein Skript komplizierter ist, kann es in mehrere Skripts zerlegt werden und eine hierarchische FSM kann ausgenutzt werden. In einem solchen Automaten kann jeder Zustand Unterzustände enthalten. Nur die Zustände auf atomarer Ebene sind einem Skript (das nicht kompliziert ist) oder einer atomaren Aktion zugeordnet.

Berechnungsmäßig sind hierarchische FSMs FSMs gleichwertig. Das bedeutet, dass jeder hierarchische FSM in einen klassischen FSM konvertiert werden kann. Hierarchische Ansätze erleichtern jedoch das Design. In der Arbeit von Damian Isla (2005) finden Sie ein Beispiel für ASM von Computerspiel-Bots, die hierarchische FSMs verwenden.

Fuzzy-Ansätze
Sowohl Wenn-Dann-Regeln als auch FSMs können mit Fuzzy-Logik kombiniert werden. Die Bedingungen, Zustände und Aktionen sind nicht mehr boolesch bzw. „ja / nein“, sondern ungefähr und glatt. Folglich wird das resultierende Verhalten glatter, insbesondere bei Übergängen zwischen zwei Aufgaben. Die Bewertung der Fuzzy-Bedingungen ist jedoch viel langsamer als die Bewertung ihrer scharfen Gegenstücke.

Sehen Sie die Architektur von Alex Champandard.

Connectionists Ansätze
Reaktive Pläne können auch durch verbindungsorientierte Netzwerke wie künstliche neuronale Netzwerke oder Free-Flow-Hierarchien ausgedrückt werden. Die grundlegende Darstellungseinheit ist eine Einheit mit mehreren Eingabeverknüpfungen, die die Einheit mit einer „abstrakten Aktivität“ versorgen, und Ausgabeverknüpfungen, die die Aktivität an folgende Einheiten weiterleiten. Jede Einheit arbeitet als Aktivitätswandler. Typischerweise sind die Einheiten in einer Schichtstruktur verbunden.

Positiv für verbindungsorientierte Netzwerke ist erstens, dass das resultierende Verhalten glatter ist als das Verhalten durch scharfe Wenn-Dann-Regeln und FSMs, zweitens sind die Netzwerke oft adaptiv, und drittens kann ein Inhibitionsmechanismus verwendet werden, und somit kann das Verhalten sein auch proskriptiv beschrieben (mittels Regeln kann man Verhalten nur präskriptiv beschreiben). Die Methoden haben jedoch auch einige Mängel. Erstens ist es für einen Designer viel komplizierter, Verhalten durch ein Netzwerk zu beschreiben, wenn es mit Wenn-Dann-Regeln verglichen wird. Zweitens kann nur ein relativ einfaches Verhalten beschrieben werden, insbesondere wenn das adaptive Merkmal ausgenutzt werden soll.

Reaktive Planungsalgorithmen
Ein typischer reaktiver Planungsalgorithmus wertet nur Wenn-Dann-Regeln aus oder berechnet den Zustand eines Verbindungseinsatznetzes. Einige Algorithmen weisen jedoch besondere Merkmale auf.

Rete-Auswertung: Mit einer richtigen Logikdarstellung (die nur für scharfe Regeln geeignet ist) müssen die Regeln nicht bei jedem Zeitschritt neu bewertet werden. Stattdessen kann eine Form eines Cache-Speichers verwendet werden, der die Bewertung aus dem vorherigen Schritt speichert.
Skriptsprachen: Manchmal sind die Regeln oder FSMs direkt die Grundelemente einer Architektur (z. B. in Soar). Häufig werden reaktive Pläne jedoch in einer Skriptsprache programmiert, bei der die Regeln nur eine der Grundformen sind (wie in JAM oder ABL).
Lenkung
Lenkung ist eine spezielle reaktive Technik, die bei der Navigation von Agenten verwendet wird. Die einfachste Form der reaktiven Lenkung wird in Braitenberg-Fahrzeugen eingesetzt, die Sensoreingänge direkt auf Effektorausgänge abbilden und folgen oder vermeiden können. Komplexere Systeme basieren auf einer Überlagerung von Anziehungs- oder Abstoßungskräften, die auf den Agenten wirken. Diese Art der Lenkung basiert auf der Originalarbeit von Craig Reynolds. Durch die Steuerung kann eine einfache Form erreicht werden:

in Richtung einer Zielnavigation
Hindernisvermeidungsverhalten
eine wand folge verhalten
Feind nähert sich
Raubtiervermeidung
Verhalten der Menschenmenge
Die Lenkung hat den Vorteil, dass sie rechnerisch sehr effizient ist. In Computerspielen können hunderte Soldaten mit dieser Technik gefahren werden. In einem komplizierteren Gelände (z. B. einem Gebäude) muss jedoch die Lenkung mit der Wegfindung (wie z. B. in Milani) kombiniert werden. Dies ist eine Form der Planung.