Titel

Verfahren zum Betreiben eines Roboters in einem Multiagentensystem, Roboter und Multiagentensystem

Technisches Gebiet

Die Erfindung betrifft Multiagentensysteme, und insbesondere Verfahren zum Steuern von Robotern eines Multiagentensystems durch Verteilung von Aufgaben mithilfe eines kooperativen Auktionsverfahrens.

Technischer Hintergrund

Das Koordinieren eines Teams von Robotern zur gemeinsamen Bewältigung einer Aufgabe ist insbesondere bei Unsicherheiten der Gegebenheiten der Umgebung sowie bei zeitlichen Abhängigkeiten in der Aufgabenspezifikation schwierig. Das Zerlegen der Aufgabenspezifikation in Teilaufgaben erfordert geeignete Mechanismen, wobei insbesondere die Handlungsanweisungen für die einzelnen Roboter aufgrund der Unsicherheiten der realen Umgebung nicht zufriedenstellend zugeordnet werden können.

Um zeitliche Abhängigkeiten zwischen einzelnen Handlungen von Robotern abzubilden, ist eine Beschreibungssprache, die sogenannte Linear Temporal Logic (LTL), bekannt, die eine Aufgabenspezifikation in Form einer LTL- Spezifikation abbildet. Aus der LTL-Spezifikation können Aktionspläne, d.h. eine Menge von Handlungsanweisungen für die einzelnen Roboter in an sich bekannter Weise abgeleitet werden. LTL für Roboteranwendungen ermöglicht es, zeitliche Randbedingungen in probabilistische Modelle zu integrieren, insbesondere mit Markov- Entscheidungsprozessen (MDP: Markov Decision Processes). Mit Markov- Entscheidungsprozessen können Unsicherheiten einschließlich unbekannten Zeitdauern der Ausführung von Aktionen und stochastischen Ereignissen in der Umgebung abgebildet werden.

Um Handlungsanweisungen unter Unsicherheit für LTL-Aufgabenspezifikationen zu erstellen, kann eine Planung für einen einzelnen Roboter vorgesehen sein, der eine Automatenrepräsentation der Aufgabenspezifikation mit einem Markov- Entscheidungsprozess kombiniert. Auch können Handlungsanweisungen für einzelne Roboter geplant werden, um einen Nutzen einer LTL- Aufgabenbeschreibung zu maximieren.

Um mehrere Roboter unabhängig von einem spezifischen Modell zu koordinieren, sind allgemein Auktionsverfahren bekannt. P. Schillinger et al. , "Auctioning over Probabilistic Options for Temporal Logic-Based Multi-Robot Cooperation under Uncertainty", IEEE International Conference on Robotics and Automation, 2018, offenbart ein Verfahren zum Koordinieren eines Teams von Robotern, eine gemeinsame Aufgabe zu erfüllen. Dabei können zeitliche Abhängigkeiten und Unsicherheiten der Umgebung berücksichtigt werden. Das dargestellte Verfahren ermöglicht es, Unsicherheiten und Beobachtungen während der Aufgabenausführung zu berücksichtigen, indem eine Aufgabenverteilung mithilfe eines Auktionsverfahrens durchgeführt wird.

Effiziente Planungsalgorithmen für die Koordination von Robotern eines Multiagentensystems in einer nicht-deterministischen Umgebung zur Lösung von Aufgaben mit zeitlich abhängigen Spezifikationen sind derzeit nicht bekannt.

Offenbarung der Erfindung

Erfindungsgemäß sind ein Verfahren zum Betreiben eines Roboters in einem Multiagentensystem gemäß Anspruch 1 sowie ein Roboter und ein Multiagentensystem gemäß den nebengeordneten Ansprüchen vorgesehen. Weitere Ausgestaltungen sind in den abhängigen Ansprüchen angegeben.

Gemäß einem ersten Aspekt ist ein Verfahren zum Betreiben eines Multi- Agentensystems mit mehreren Robotern vorgesehen, wobei eine vorgegebene Mission, die durch eine Abfolge von Systemzuständen definiert ist, auszuführen ist, wobei jeder der Roboter folgendes Verfahren zyklisch ausführt:

- Durchführen von einer oder mehreren Auktionsrunden, wobei in jeder Auktionsrunde folgende Schritte durchgeführt werden:

o ausgehend von einem betrachteten Systemzustand, Ermitteln von möglichen Optionen, wobei die Optionen Aktionen definieren, durch die ein Übergang von einem betrachteten zu einem Folgezustand erreicht werden kann;

o für jede der möglichen Optionen, Ermitteln von Aktionskosten zur Durchführung einer durch die Option angegebenen Aktion; o Bereitstellen der ermittelten Aktionskosten für jede der Optionen an die übrigen Roboter und Empfangen der Aktionskosten für jede der Optionen Durchführen von den übrigen Robotern

o Durchführen einer Auktion, so dass eine Option abhängig von der betreffenden Option zugeordneten Aktionskosten zugeordnet wird;

- Ausführen der durch die zugeordneten Optionen angegebenen Aktionen, die einer oder mehreren der Optionen entspricht, abhängig von allen zu den betreffenden Optionen ermittelten oder empfangenen Aktionskosten, wobei die Aktionskosten für eine betrachtete Option geschätzte Missionskosten berücksichtigen, wobei die Missionskosten abhängig von den Kosten zum Erreichen eines aktuellen Systemzustands, von Erfahrungskosten, die geschätzte Kosten zum Erreichen eines Zielzustands der Mission ausgehend von einem durch die Option erreichbaren Folgezustand angeben, und von den Kosten für die Durchführung der betrachteten Option ermittelt werden.

Eine Idee des obigen Verfahrens zum Betreiben eines Multiagentensystems mit mehreren Robotern (Agenten) besteht darin, einen deterministischen endlichen Automaten bereitzustellen, der die von einem Multiagentensystem zu lösende Aufgabenspezifikation definiert. Der deterministische endliche Automat weist mehrere Systemzustände auf, die einen oder mehrere Zustandspfade definieren, die zum Erreichen des Aufgabenziels durchlaufen werden müssen. In diesem deterministischen endlichen Automaten werden die Aktionen, die zum Erreichen von Zustandsübergängen führen, verschiedenen Robotern in einem Auktionsverfahren zugeordnet. Die von einem Roboter ausführbaren Zustandsübergänge zwischen den Systemübergangen entlang eines der Zustandspfade werden nachfolgend als Optionen bezeichnet.

In dem Prozess des Zuordnens der auszuführenden Zustandsübergänge zu einzelnen Robotern können Teilaufgaben, die zu Zustandsänderungen führen, als Optionen den einzelnen Robotern zugeordnet werden. Ein solches Auktionsverfahren ermöglicht es, mithilfe einer geeigneten Kostenfunktion für die gesamten Missionskosten eine Teilaufgabe denjenigen Robotern zuzuordnen, die die betreffende Teilaufgabe mit geringsten Kosten durchführen kann. Eine Kostenfunktion kann insbesondere den Zeitaufwand für die Durchführung der betreffenden Teilaufgabe sowie die Wahrscheinlichkeit, dass mit der Durchführung der Teilaufgabe die für den Systemzustand definierende Bedingung erfüllt wird, jedoch auch andere Kriterien, wie Energieverbrauch und/oder dergleichen, berücksichtigen.

Wird durch die Ausführung einer Option eine Systemzustandsbedingung für einen Systemzustand erfüllt, so wird das Ausführen aller laufenden Optionen in den übrigen Robotern unterbrochen und neue Auktionsrunden durchgeführt, bei der nun neue Optionen an die Roboter des Multiagentensystems verteilt werden. Die neuen Optionen werden entsprechen den von dem nun erreichten Systemzustand ausgehenden relevanten Zustandsübergängen in einem oder mehreren Auktionsrunden bestimmt. Dieses Verfahren wird so lange durchgeführt, bis der Zielzustand erreicht ist. Auf diese Weise kann eine Verteilung von Optionen in einem Multiagentensystem in effizienter Weise durchgeführt werden, wobei insbesondere zeitliche Abhängigkeiten in besonders effizienter Weise berücksichtigt werden können.

Durch Vorgabe des deterministischen endlichen Automaten an alle Roboter kann jeder der Roboter in verteilter Weise seine Optionen hinsichtlich des übergeordneten Aufgabenziels ermitteln, wobei ein sehr viel weniger komplexes probabilistisches Planungsproblem gelöst werden muss. Durch das dezentralisierte Auktionsschema werden die verschiedenen Optionen verschiedenen Robotern zugeordnet, wobei es der vorgeschlagene Auktionsalgorithmus ermöglicht, dass die Roboter Optionen durchführen, die zeitlich von anderen Optionen abhängig sind. Bei jeder Erfüllung einer Zustandsbedingung (durch Erreichen des Folgezustands durch das Ausführen einer entsprechenden Option) wird das Verfahren erneut durchgeführt, so dass das Wissen über Systemzustände in aktueller Weise berücksichtigt werden kann.

Das obige Verfahren ermöglicht, in effizienter Weise ein Multiagentensystem zu koordinieren, insbesondere bei Unsicherheiten der Umgebungsbedingungen. Dies gilt insbesondere für Spezifikationen, die zeitliche Logik enthalten, die von dem gesamten Team von Robotern bearbeitet werden sollen. Dazu werden den Robotern Teilaufgaben der Aufgabenspezifikation automatisch zugeordnet. Auch die Gegebenheiten der Systemumgebung können durch regelmäßiges Aktualisieren der geplanten Handlungsanweisungen berücksichtigt werden, so dass sich die Roboter flexibel an die Unsicherheiten anpassen können.

Weiterhin kann eine Option zugeordnet werden, wenn für die entsprechende Option Aktionskosten ermittelt werden, die die geringsten Kosten aller für die entsprechende Option empfangenen Aktionskosten angibt.

Gemäß einer Ausführungsform können solange Auktionsrunden durchgeführt werden, bis allen Robotern mindestens eine Option zugeordnet ist. Alternativ kann eine Obergrenze für eine maximale Anzahl an Auktionsrunden festgelegt werden oder die Auktionsrunden für eine begrenzte Zeit durchgeführt werden.

Es kann vorgesehen sein, dass die Aktionskosten abhängig von einer Wahrscheinlichkeit, dass die Mission die betrachtete Option nutzt, bestimmt werden.

Gemäß einer Ausführungsform können für die zweite und weitere Auktionsrunden die betrachteten Systemzustände zur Ermittlung der Optionen den Folgezuständen der in der vorherigen Auktionsrunde betrachteten Optionen entsprechen.

Es kann vorgesehen sein, dass die Erfahrungskosten bei Erreichen eines Folgezustands beim Ausführen einer einer der Optionen zugehörigen Aktion durch einen der Roboter aktualisiert werden, indem die Kosten zur Ausführung der Aktion durch den betreffenden Roboter ermittelt und der Erfahrungsparameter abhängig von den ermittelten Kosten und insbesondere abhängig von einem Anpassungsparameter angepasst wird.

Weiterhin können die Aktionskosten für eine Option abhängig von einer Zeitdauer oder als eine Zeitdauer für eine Ausführung der der Option zugeordneten Aktion angegeben werden.

Es kann vorgesehen sein, dass die Aktionskosten für eine Option abhängig von einer Zustandswahrscheinlichkeit, dass bei der Ausführung der der Option zugeordneten Aktion eine Zustandsbedingung für ein Erreichen des Folgezustands, zu der die Option hinführt, ermittelt werden.

Gemäß einer Ausführungsform kann eine Zustandswahrscheinlichkeit, dass bei der Ausführung einer einer Option zugeordneten Aktion eine Zustandsbedingung für ein Erreichen des Systemzustands erreicht wird, während der Ausführung der Aktion aktualisiert werden.

Gemäß einem weiteren Aspekt ist ein Roboter zum Betreiben eines Multi- Agentensystems, wobei eine vorgegebene Mission, die durch eine Abfolge von Systemzuständen definiert ist, auszuführen ist, wobei der Roboter ausgebildet ist, um folgende Schritte zyklisch auszuführen:

- Durchführen von einer oder mehreren Auktionsrunden, wobei in jeder Auktionsrunde folgende Schritte durchgeführt werden:

o ausgehend von einem betrachteten Systemzustand, Ermitteln von möglichen Optionen, wobei die Optionen Aktionen definieren, durch die ein Übergang von einem betrachteten zu einem Folgezustand erreicht werden kann;

o für jede der möglichen Optionen, Ermitteln von Aktionskosten zur Durchführung einer durch die Option angegebenen Aktion; o Bereitstellen der ermittelten Aktionskosten für jede der Optionen an die übrigen Roboter und Empfangen der Aktionskosten für jede der Optionen Durchführen von den übrigen Robotern

o Durchführen einer Auktion, so dass eine Option abhängig von der betreffenden Option zugeordneten Aktionskosten zugeordnet wird; - Ausführen der durch die zugeordneten Optionen angegebenen Aktionen, die einer oder mehreren der Optionen entspricht, abhängig von allen zu den betreffenden Optionen ermittelten oder empfangenen Aktionskosten, wobei die Aktionskosten für eine betrachtete Option geschätzte Missionskosten berücksichtigen, wobei die Missionskosten abhängig von den Kosten zum Erreichen eines aktuellen Systemzustands, von Erfahrungskosten, die geschätzte Kosten zum Erreichen eines Zielzustands der Mission ausgehend von einem durch die Option erreichbaren Folgezustand angeben, und von den Kosten für die Durchführung der betrachteten Option ermittelt werden.

Gemäß einem weiteren Aspekt ist ein Multiagentensystem mit mehreren der obigen Roboter vorgesehen.

Kurzbeschreibung der Zeichnungen

Ausführungsformen werden nachfolgend anhand der beigefügten Zeichnungen näher erläutert. Es zeigen:

Figur 1 eine schematische Darstellung eines Roboters eines

Mehragentensystems;

Figur 2 eine Darstellung eines deterministischen endlichen

Automaten;

Figur 3 eine Darstellung eines zyklischen endlichen Automaten;

Figur 4 ein Flussdiagramm zur Veranschaulichung eines Verfahrens zum Betreiben des Multiagentensystems zur Lösung einer Aufgabenspezifikation an gegebenen Aufgaben; und

Figuren 5a - 5c beispielhafte Darstellungen der Optionen für mehrere aufeinanderfolgende Auktionsrunden. Beschreibung von Ausführungsformen

Nachfolgend wird ein Verfahren beschrieben, mit dem in einem Multiagentensystem, bei dem Agenten als mit der Umgebung interagierende Roboter vorgesehen sind, beschrieben. Die Roboter 1 weisen eine Konfiguration auf, wie sie in Figur 1 schematisch dargestellt ist. Die Roboter 1 umfassen dazu jeweils eine Steuereinheit 2, die zur Ausführung von Teilaufgaben ausgebildet ist. Zur Kommunikation mit anderen Robotern 1 weist jeder der Roboter 1 weiterhin eine Kommunikationseinrichtung 3 auf, um Informationen zu anderen Robotern 1 zu übertragen und von diesen zu empfangen.

Mithilfe einer Aktuatorik 4 kann der Roboter 1 mit der Systemumgebung interagieren. Die Aktuatorik 4 kann beispielsweise eine Fortbewegungsaktuatorik, Greifaktuatorik und dergleichen umfassen, die entsprechend der dem Roboter 1 zugewiesenen Teilaufgabe in an sich bekannter Weise betrieben wird. Dadurch kann der Roboter 1 sich insbesondere fortbewegen, Objekte aufnehmen und absetzen und dergleichen.

Weiterhin können mithilfe einer Sensorik 5 Umgebungszustände erfasst werden. Die Sensorik 5 kann beispielsweise eine Kamera, andere zur Objektdetektion verwendbare Sensorik, wie beispielsweise Ultraschallsensorik, und dergleichen umfassen. Mithilfe der Kamera können Positionen von Objekten, mit denen interagiert werden kann/soll, erkannt und identifiziert werden, und eine Fortbewegung innerhalb der Systemumgebung zu ermöglichen, wobei Objekte, die Hindernisse darstellen, umfahren werden.

Die Roboter 1 können des Weiteren mit einer Interaktionseinrichtung 6, wie z.B. einem Touch-Display oder eine Sprachein-/ausgabeeinrichtung, versehen sein, um mit Objekten oder Personen der Umgebung kommunikativ zu interagieren. Auf diese Weise können Personen Eingaben an den Robotern 1 vornehmen und Informationen erhalten.

Ausgangspunkt des nachfolgend beschriebenen Verfahrens ist eine Aufgabenspezifikation in Form einer Linear Temporal Logic (LTL), insbesondere einer co-safe Linear Temporal Logic (scLTL). Diese stellt eine Beschreibungssprache für eine Aufgabenspezifikation einer zu lösenden Aufgabe dar, die zeitliche Modalitäten aufweist. Jede scLTL-Aufgabenspezifikation kann in einen deterministischen endlichen Automaten (DEA) übersetzt werden.

Ein solcher deterministischer endlicher Automat (DEA) ist beispielhaft in Figur 2 dargestellt. Dieser zeigt Systemzustände (Fortschrittszustände) (q1-q10), die einen Anfangszustand 1 1 (q1), mehrere Zwischenzustände 12 (q2-q9) und einen oder mehrere Zielzustände 13 (q10) enthalten. Ist ein Zielzustand erreicht, so ist die Mission des Multiagentensystems abgeschlossen. In dem Schaubild zur Darstellung des deterministischen endlichen Automatens zeigen Pfeile Zustandsübergänge von dem Anfangszustand 11 (q1) zu dem Zielzustand 13 (q10) entlang eines oder mehrerer Pfade. Ein Systemzustand wird erreicht, wenn eine dem betreffenden Systemzustand zugeordnete Zustandsbedingung erfüllt ist. Die Systemzustände von dem Anfangszustand 11 zu dem Zielzustand 13 wird durch Fortschritte entlang des Pfades erreicht. Ein Fortschritt entlang einer der Pfade wird dann erreicht, wenn von einem Systemzustand zu einem darauffolgenden Systemzustand keine Möglichkeit eines Rückpfades besteht. Der Fortschritt entlang der Pfade wird durch Fortschrittniveaus, insbesondere aufsteigende Fortschrittniveaus, angegeben.

Figur 3 zeigt eine schematische Darstellung eines zyklischen endlichen Automaten mit den Systemzuständen q0-q4, der zur Beschreibung von sich wiederholenden zyklischen Aufgaben geeignet ist. Der zyklische endliche Automat kann Teil eines endlichen Automaten sein oder diesen darstellen. Ein zyklischer endlicher Automat zeichnet sich beispielsweise dadurch aus, dass, wenn der Zielzustand (q4) 13 erreicht worden ist, dieser auf einen früheren Zustand, beispielsweise den Startzustand (q0) 11 , zurückgesetzt wird. Wo im Folgenden nicht anders angegeben, können die Begriff deterministischer endlicher Automat und zyklischer endlicher Automat für das beschriebene Verfahren äquivalent verstanden werden. Der dargestellte zyklische endliche Automat entspricht der folgenden LTL-Formel:

F =♢ (a L♢ b) L ♢ d

Die Steuereinheit 2 ist ausgebildet, um durch Auswerten der Sensorik 5 und/oder durch Auswerten von Eingaben in der Interaktionseinrichtung 6 zu erkennen, ob ein durch eine Aufgabenspezifikation vorgegebener Systemzustand erreicht worden ist.

Nachfolgend wird ein Verfahren zum Zuordnen von Optionen zu einzelnen Robotern 1 in einem zyklischen endlichen Automaten beschrieben. Die Zuordnung von Optionen in einem nichtzyklischen Teil des deterministischen endlichen Automaten kann nach dem gleichen oder einem davon abweichenden Verfahren durchgeführt werden.

Unter einer Option wird hierin eine mögliche Aktion eines Roboters verstanden, die einen Übergang von einem aktuellen Systemzustand q zu einem Folgezustand q' des Automaten bewirkt. Befindet sich der Automat bzw. das System in einem Systemzustand q, der nicht der Zielzustand ist, sind ein oder mehrere Folgezustände q' möglich. Im Unterschied zu den Systemzuständen, die den Fortschritt bei der Bewältigung der durch den Automaten vorgegebene Mission (bestimmt durch die Aufgabenspezifikation) angibt, sind die physikalischen Zustände der einzelnen Roboter durch deren momentanen Roboterzustand, wie z.B. die eigene Position, bestimmt.

Voraussetzung für das Verfahren zum Betreiben des Multiagentensystems ist, dass jeder Roboter 1 in der Lage ist, mit jedem der übrigen Roboter 1 zu kommunizieren, und dass jedem Roboter 1 der zyklische endliche Automat DEA bekannt gemacht ist. Das nachfolgende Verfahren, das in Verbindung mit Figur 4 dargestellt ist, beschreibt den Ablauf in einem der Roboter 1 zu einem beliebigen Zeitpunkt, der einem Anfangszustand oder einem Zeitpunkt nach dem Erreichen eines weiteren Systemzustands, der nicht Zielzustand ist, entspricht, wobei das Verfahren grundsätzlich parallel in jedem der Roboter 1 ausgeführt wird.

Zunächst werden in Schritt S1 1 ausgehend von dem momentanen Systemzustand q im deterministischen endlichen Automaten, insbesondere beim ersten Durchlauf ausgehend von dem Anfangszustand 1 1 , alle möglichen Optionen ermittelt. Die Optionen (dargestellt als Zustandsübergänge von einem gesetzten (aktuellen) Systemzustand q zu einem möglichen Folgezustand q') stellen Möglichkeiten zum Erreichen eines nächsten möglichen Systemzustandes des deterministischen endlichen Automaten dar. Nun werden in Schritt S12 für alle der in Schritt S1 1 ermittelten möglichen Optionen Aktionskosten AK ermittelt. Die Aktionskosten AK können beispielsweise von einer Zeitdauer zur Ausführung der Mission für den betreffenden Roboter 1 oder einer abhängen. Weiterhin können die Aktionskosten AK bei einer Systemumgebung, die mit Unsicherheiten belegt ist, Wahrscheinlichkeiten berücksichtigen.

Die Bestimmung der Aktionskosten AK bezüglich einer Option wird weiter unten näher beschrieben.

In Schritt S13 werden die so ermittelten Kosten nun für jede der möglichen Optionen des betreffenden Roboters 1 an alle übrigen Roboter 1 kommuniziert. Somit liegen in allen Robotern 1 Informationen über die Kosten für jede der Optionen vor.

In Schritt S14 werden nun für jeden möglichen Systemzustand, der durch eine der selbst ermittelten oder von anderen Robotern 1 erhaltenen Optionen erreichbar ist, die minimalen Aktionskosten AK ermittelt.

Anschließend wird in Schritt S15 in jedem der Roboter 1 überprüft, ob für einen durch eine Option erreichbaren Zwischenzustand die eigenen Kosten die minimalen Kosten über alle bereitgestellten Aktionskosten AK darstellen. Ist dies der Fall (Alternative: Ja), so wird dem betreffenden Roboter 1 (der dies festgestellt hat) in Schritt S18 die betreffende Option (mit den geringsten Kosten) zugeordnet und in eine Handlungsanweisung zum Erreichen des durch die Option angegebenen Systemzustands umgesetzt. Dieser Prozess findet in jedem Roboter parallel statt, so dass jedem Roboter 1 die Zuordnungen der übrigen Roboter 1 bekannt sind. Anschließend wird das Verfahren mit Schritt S16 fortgesetzt. Wird in Schritt S15 festgestellt, dass für dem durch eine Option erreichbaren Zwischenzustand die eigenen Aktionskosten nicht die minimalen Kosten über alle bereitgestellten Aktionskosten AK darstellen (Alternative: Nein), so wird das Verfahren direkt mit Schritt S16 fortgesetzt.

In Schritt S16 wird nun überprüft, ob eine weitere Auktionsrunde (Index k) durchgeführt wird. Eine weitere Auktionsrunde berücksichtigt jeden möglichen erreichbaren Folgezustand (Folgesystemzustand) von in der vorangegangenen Auktionsrunde zugewiesenen Optionen als möglichen Startzustand (Startsystemzustand), d.h. die Folgezustände, die durch die zuvor evaluierten Optionen erreichbar sind, und ermittelt weitere zu evaluierende Optionen mit deren entsprechenden Folgezuständen. Dies wird durch die schematisch dargestellten Auktionsrunden der Figur 5 veranschaulicht. Wird in Schritt S16 festgestellt, dass noch nicht allen Robotern 1 mindestens eine Option zugewiesen wurde und/oder dass keiner der Folgezustände dem Zielzustand entspricht (Alternative: Ja), wird eine weitere Auktionsrunde durchgeführt und das Verfahren wird mit Schritt S11 fortgesetzt. Andernfalls (Alternative: Nein) wird das Verfahren mit Schritt S17 fortgesetzt.

In Schritt S17 wird entsprechend mit der Ausführung der durch die zugeordneten Optionen definierten Handlungsanweisungen sofort begonnen.

In Schritt S19 wird in jedem Roboter 1 überprüft, ob durch die eigene Aktion die Zustandsbedingung erfüllt wurde oder ob eine entsprechende Information über ein Erfüllen einer Zustandsbedingung von einem weiteren der Roboter 1 empfangen wurde. Das Erfüllen der Zustandsbedingung entspricht der vollständigen Ausführung einer Option, die zum Erreichen eines Folgezustands q' geführt hat. Ist dies nicht der Fall (Alternative: Nein), wird zu Schritt S19 zurückgesprungen und entweder die eigene Option weitergeführt oder auf das Erfüllen der Zustandsbedingung durch einen weiteren der Roboter 1 gewartet, andernfalls (Alternative: Ja), wird zu Schritt S20 gesprungen.

In Schritt S20 wird überprüft, ob ein definierter Zielsystemzustand, der z.B. eine Abbruchbedingung definiert, erreicht worden ist. Ist dies der Fall (Alternative. Ja), wird das Verfahren beendet. Andernfalls (Alternative: Nein) wird das Erfüllen der Zustandsbedingung bzw. die vollständige Ausführung einer Option an die übrigen Roboter 1 in Schritt S21 kommuniziert und zu Schritt S11 zurückgesprungen.

Wird in Schritt S15 für jede der Optionen festgestellt, dass keine der Optionen mit den minimalen Kosten ausgeführt werden kann (Alternative: Nein), wird das Verfahren mit Schritt S17 fortgesetzt.

Bei gleichen minimalen Kosten können u.U. mehreren Robotern 1 die betreffende Option gleichzeitig zugeordnet werden, so dass diese die jeweils der Option entsprechenden Handlungsanweisungen gleichzeitig durchführen. Alternativ kann die betreffende Option nur einem einzelnen, zufällig ausgewählten der Roboter 1 mit den minimalen Kosten zugeordnet werden. Durch den Zuordnungsprozess mit den mehreren Auktionsrunden werden in der Regel jedem Roboter 1 eine oder mehrere Optionen zugeordnet.

Während der Ausgabenausführung führt jeder Roboter 1 das Verfahren zyklisch aus, wobei der gemeinsame Systemzustand q des zyklischen endlichen Automaten sowie der eigene Roboterzustand s beachtet wird. Ausgehend von diesen Zuständen führt jeder der Roboter 1 das oben beschriebene Verfahren aus, um eine Zuweisung einer oder mehrerer Optionen zu erhalten.

Jeder Roboter 1 führt dann die diesem zugeordneten Optionen in der Reihenfolge der Zuweisung aus, indem den entsprechenden Handlungsanweisungen gefolgt wird. Wenn einer der Roboter 1 einen Folgezustand erreicht, wird an alle anderen Roboter 1 ein Interrupt-Signal gesendet, um ihre momentane Aktion abzubrechen. Gleichzeitig wird der erreichte Systemzustand an die übrigen Robotern 1 kommuniziert und ein neuer Auktionsprozess gestartet. Insbesondere bei Verwendung des zyklischen endlichen Automaten wird der Systemzustand auf den Anfangszustand 11 eingestellt, immer wenn ein Zielzustand 13 erreicht ist.

Die Aktionskosten AK, mit denen jeder Roboter 1 die Auktion bestreitet, werden wie nachfolgend beschrieben ermittelt.

Die Aktionskosten AK, die jeder Roboter 1 für die Auktion ermittelt, entsprechen den gesamten Kosten bis zum Beenden der Mission, d.h. bis zum Erfüllen der Aufgabenstellung bzw. dem Erreichen des Zielzustands unter der Annahme, dass der betreffende aktuelle Roboter 1 die Aktion der aktuell betrachteten Option ausführt. Insgesamt werden mehrere Auktionen für jede der aufeinanderfolgenden Optionen durchgeführt, die einen Pfad zu einem Zielzustand darstellen.

Figur 5 zeigt entsprechend den Fortschritt entlang der Systemzustände des deterministischen endlichen Automaten für die iterativ erfolgenden Aktionskostenberechnungen in jeder Auktionsrunde. So können die Aktionskosten AK für die erste Auktionsrunde berechnet werden durch:

wobei q dem anfänglichen Systemzustand für die erste Auktionsrunde und q' denjenigen Systemzuständen entsprechen, die wahrscheinlich aus der Ausführung der Option o resultieren. Eine allgemeinere Form der Aktionskosten AK für alle Auktionsrunden ergibt sich aus:

Alle Kosten können als Zeitangaben bis zum Erreichen des Folgezustands bzw. eines Zielsystemzustands angegeben werden. Selbstverständlich können Kosten auch andere Ressourcenverbrauche berücksichtigen. Dabei entspricht der erste Term in den eckigen Klammern den erwarteten Ausführungskosten bis zum Erreichen eines jeweiligen Folgezustands q', wenn die Option o ausgewählt wird.

Der erste Term wird berechnet als Summe von:

dem Maximum der Kosten D(q), d.h. den Kosten, den Systemzustand q der jeweils betrachteten Option zu erreichen, in dem die betrachtete Option o angewendet werden kann, und den gesamten (akkumulierten) Kosten d für die Ausführung aller dem betreffenden Roboter 1 bereits zugewiesenen Optionen.

den geschätzten Kosten d ₀ (ŝ) zur Durchführung der Option ausgehend von dem momentanen Roboterzustand ŝ. Dazu kann insbesondere der momentane Zustand, wie z.B. die Position des Roboters 1 berücksichtigt werden, so dass die Kosten den geschätzten Aufwand des Roboters zum Erreichen eines Roboterzustands, der die Zustandsbedingung der Option erfüllt, angeben.

dem Erwartungswert der Erfahrungskosten, die dem Produkt aus der Übergangswahrscheinlichkeit für die betrachtete Option und den Erfahrungskosten bis zum Erreichen des Zielzustands q'

entsprechen. Die Ermittlung der Übergangswahrscheinlichkeit.

Die Kosten des ersten Terms bis zum Erreichen des Zielzustands werden dann durch die Zustandswahrscheinlichkeit gewichtet, mit der die Aktion der Option o tatsächlich in der Zukunft ausgeführt wird. Zudem werden die gewichteten Kosten bis zum Erreichen des Zielsystemzustands durch einen zweiten Term berücksichtigt, der die Kosten berücksichtigt, dass der Zustand q nicht erreicht wird und die Aktion der Option o nicht gewählt wird. Der zweite Term stellt die Summe aller mit der entsprechenden Zustandswahrscheinlichke gewichteten Kosten dar, die Mission über einen der Alternativpfade zu beenden. Das heißt, es werden die Kosten berücksichtigt, mit denen anstatt q einer der anderen Systemzustände erreicht wird. Diese

Kosten beinhalten für jeden Systemzustand die Kosten um zu erreichen

und den Erfahrungskosten als erwartete Kosten bis zum Erreichen des

Zielzustand.

Die Zustandswahrscheinlichkeit ergibt sich aus den

Übergangswahrscheinlichkeiten zu dem nächsten Systemzustand q, d.h.

der Wahrscheinlichkeit, dass eine Option o zu einem Systemzustand q' führt.

Die Übergangswahrscheinlichkeit , die der Wahrscheinlichkeit entspricht,

dass eine Option o zu einem Folgezustand q' führt kann wie folgt aus dem physikalischen Modell eines jeden Roboters 1 ermittelt werden. Sie basiert auf der Wahrscheinlichkeit, dass eine Menge SA von physikalischen Zielzuständen s von diesem Roboter 1 erreicht werden kann. Zu diesem Zweck werden aus den Transitionswahrscheinlichkeiten des physikalischen Robotermodells und

den geplanten Aktionen des Roboters 1 die folgenden erforderlichen

Größen bestimmt. Die Wahrscheinlichkeit gibt an, von einem physikalischen Zustand s des Systems, den nächsten physikalischen Zustand t zu erreichen. Systemzustände, die durch die Ausführung einer Option erreichbar sind, werden Absorptionszustände genannt. Die übrigen Systemzustände werden Übergangszustände genannt. Ausgehend von p _MC kann die Matrix in kanonischer Form geschrieben werden:

Wobei Q die Transitionswahrscheinlichkeiten in der Menge der Übergangszustände und R die Transitionswahrscheinlichkeiten von einem Übergangszustand zu einem Absorptionszustand bezeichnet. I entspricht einer Identitätsmatrix Die Fundamentalmatrix N ist dann:

wobei N ausdrückt, dass ein Element N _j die erwartete Anzahl von Einnahmen des Übergangszustands S _j angibt, wenn von dem Übergangszustand s, ausgegangen wird.

Die zu erwartenden Kosten der Option o hängt von der erwarteten Anzahl von Schritten ab, bevor ein Absorptionszustand erreicht wird und kann ermittelt werden mit: wobei einem Vektor über den Übergangszuständen s mit

entspricht. Insbesondere entsprechen die Kosten 0 wenn von einem Absorptionszustand ausgegangen wird.

Die schließliche Zustandsverteilung nach dem Beenden der Option o d.h. die Verteilung über den Absorptionszuständen entspricht wobei wie oben einem Vektor über Absorptionszuständen s mit

entspricht.

Die Übergangswahrscheinlichkeit entspricht dann:

wodurch die gesamte Wahrscheinlichkeit bestimmt wird, einen der Zielzustände in der Menge SA der Zielzustände s zu erreichen.

Die Zustandswahrscheinlichkeit ergibt sich aus den Übergangswahrscheinlichkeiten zu dem nächsten Systemzustand. Für die erste Aukionsrunde beträgt d.h. entsprechend der Zustandswahrscheinlichkeit, dass eine zuvor ausgeführte Option o zu dem Systemzustand q geführt hat. Für die nächste Auktionsrunde k+1 wird nach dem Auswählen der Option, die die vorherige Auktionsrunde„gewonnen“ hat, die Zustandswahrscheinlichkeit abhängig von den

Übergangswahrscheinlichkeiten p(q'|q, o) für alle möglichen Optionen q' wie folgt aktualisiert.

Nach dieser Aktualisierung wird gesetzt, da eine nachfolgende Option

sicherstellt, dass die Mission nicht an dem Zustand q endet.

Die Erfahrungskosten V geben im Wesentlichen die Kosten an, die benötigt wird, um ausgehend von einem bestimmten Systemzustand zum Zielzustand zu gelangen. V(q) gibt also die Kosten an, ausgehend von dem momentanen Systemzustand zu dem Zielzustand zu gelangen. V(q') gibt die Kosten an, ausgehend von dem durch die Option o bestimmten Folgezustand zu dem Zielzustand zu gelangen. Insbesondere können diese Kosten der erwarteten Zeitdauer bis zum Erreichen des Zielzustands entsprechen. Die Erfahrungskosten V sind schwer zu berechnen, und es wird daher vorgeschlagen, diese mithilfe eines nachfolgenden Reinforcement Learning-Prozesses zu ermitteln.

Wie oben beschrieben, folgt jeder Roboter 1 einer Option parallel, nachdem die entsprechende Auktion beendet ist, und der Roboter, der die erste Auktionsrunde gewonnen hat, beendet schließlich die Aktion der Auktion o. Beim Beenden der Option o werden die benötigten Aktionskosten, die der betreffende Roboter 1 für die Aktion der entsprechenden Option benötigt hat, aufgezeichnet. Reinforcement Learning kann angewendet werden auf die Iterationen, bei denen jeweils ein Roboter 1 eine nächste Option auswählt, diese ausführt, was zu beobachteten Aktionskosten (Ausführungszeitdauer) und einem Folgezustand q' führt.

Um aus diesen Beobachtungen die Erfahrungskosten V für einen erreichten Systemzustand q _k abzuleiten, werden die Erfahrungskosten des Systemzustands q _k nach jeder Ermittlung von Aktionskosten wie folgt aktualisiert: V _{k+ 1} q _k ) V _k q _k ) a _k d _k

Mit einem nicht negativen vorgegebenen Schrittparameter a _k und dem TD-Fehler d _{k k} V _k (q _k+1 -

Die Erfahrungskosten V ₀ (q ) werden anfänglich für alle q auf 0 festgelegt. Nach Ausführung jeder Option o werden entsprechend die Erfahrungskosten V für den erreichten Systemzustand q wie folgt aktualisiert: d _i = d _i + V _k (q' _i ) - V _k (q _i )

V _{k+ 1} q _i ) V _k q _i ) a _k d _i

Die Erfahrungskosten können zwischen den Robotern 1 explizit aktualisiert werden. Alternativ können diese auch in jedem der Roboter 1 implizit durch Übermitteln der für die Ausführung der beendeten Option o benötigten Kosten aktualisiert werden.

Die Kosten D(q), d.h. den Kosten, den initialen Systemzustand q zu erreichen, in dem die betrachtete Option o angewendet werden kann, werden für jede Auktionsrunde k wie folgt ermittelt.

Wobei den kumulierten Wahrscheinlichkeiten entspricht.

Die Figuren 5a bis 5c illustrieren für einen beispielhaften Automaten die Betrachtungen von Optionen bei aufeinanderfolgenden Auktionsrunden, nämlich einer ersten, zweiten bzw. dritten Auktionsrunde. In Figur 5a befindet sich der Systemzustand bei Zustand q1 , von dem ausgehend zwei Folgezustände q2 und q3 möglich sind. Diese werden in entsprechenden Optionen o1 , o2 bewertet. Nun werden in jeden Roboter 1 alle möglichen Optionen o1 , o2, d.h. mögliche Übergänge zu einem Folgezustand q2 und q3 bewertet und die Aktionskosten ermittelt. In diesem Beispiel wird nun davon ausgegangen, dass die ermittelten Aktionskosten für o1 die geringsten sind und das System auch diese Option wählt, um sie einem der Roboter 1 zuzuweisen.

Figur 5b zeigt ein aktualisiertes Modell des Systems unter dieser Annahme als Grundlage für die zweite Auktionsrunde um den übrigen Robotern 1 ebenfalls Optionen zuzuweisen.

Den Übergängen zwischen q1 und q2 sowie q1 und q3 unter der Annahme dass Option o1 gewählt wurde sind jeweils Übergangswahrscheinlichkeiten p(q ₂ |q ₁ , o ₁ ) = 0,8 und p(q ₃ |q ₁ , o ₁ ) = 0,2 zugeordnet, wobei die Zahlenwerte für dieses Beispiel willkürlich gewählt sind und ansonsten aus dem physikalischen Robotermodell des ausführenden Roboters 1 ermittelt werden können. Aus diesen Übergangswahrscheinlichkeiten ergeben sich nun gemäß der oben beschriebenen Vorgehensweise die Zustandswahrscheinlichkeiten (q ₂ ) = 0,8 und (q ₃ ) = 0,2

die nun bei der Berechnung der folgenden Aktionskosten als Faktor berücksichtigt werden.

Die Aktionskosten berücksichtigen immer die für die gesamte Mission geschätzten Kosten. D.h. die Kosten bis zum Erreichen des jeweiligen Systemzustands, d.i. max{D(q), d ^r }, die Kosten für die betrachtete Option, d.i. d ₀ (ŝ), und die Kosten für den Rest der Mission ausgehend von dem durch die betrachtete Option erreichbaren Folgezustand, d.i.

Für die zweite Auktionsrunde, siehe Figur 5b, werden somit zusätzlich zu den Zustandswahrscheinlichkeiten auch die Kosten (Dauer) D(q ₂ ) berücksichtigt um durch die zugewiesene Option o1 den Systemzustand q2 zu erreichen, sowie für jeden der Roboter r die Kosten d ^r , die dieser Roboter 1 bereits zugewiesenen Optionen folgt.

Zusätzlich werden die gewichteten Gesamtkosten für alle übrigen Systemzustände, die von dem aktuellen Systemzustand erreichbar sind aber in denen die jeweilige betrachtete Option nicht anwendbar ist, ermittelt, d.i.

. Dadurch wird der Fall berücksichtigt, dass die

betrachtete Option nicht ausgeführt wird und stattdessen eine der übrigen Optionen ausgeführt wird. Dies erfolgt durch die mit den entsprechenden Wahrscheinlichkeiten gewichteten gesamten Missionskosten bei Durchführen der übrigen Optionen.

In diesem Fall bedeutet das zum Beispiel für die Berechnung der Aktionskosten einer Option o3 von q2 nach q3, dass der Term [max{D(q ₂ ), d ^r } + d ₀ (ŝ) + å _q' p(q'|q, o)V(q')] mit der Zustandswahrscheinlichkeit (q ₂ )

= 0,8 gewichtet berücksichtigt wird und zusätzlich der Term (D(q ₃ ) + V(q ₃ )) mit (q ₃ ) = 0,2 gewichtet berücksichtigt wird, um die Missionsdauer in dem Fall zu betrachten, dass q2 nicht erreicht und daher Option o3 nicht aktiviert wird.

Für die dritte Aktionsrunde in Figure 5c wird dann nach dem gleichen Prinzip die Zustandswahrscheinlichkeit aktualisiert. Zum Beispiel für angenommene Übergangswahrscheinlichkeiten p(q ₃ |q ₂ , o ₃ ) 0,7 und p(q ₄ |q ₂ , o ₃ ) = 0,3 ergibt sich in der dritten Auktionsrunde die neue Zustandswahrscheinlichkeit für q ₃ als (q ₃ ) = 0,2 + 0,8 · 0,7 = 0,76, wobei der erste Term 0,2 den Fall betrifft dass q ₃ direkt von q ₁ aus erreicht wird, wie bereits in der zweiten Auktionsrunde berücksichtigt, und der zweite Term 0,8 · 0,7 den Fall abdeckt, dass q ₃ über q ₂ erreicht wird.