Aufgaben zwischen >=2 Agents tauschen
Es sollen Aufgaben zwischen mehreren Agents getauscht werden können. Dies kann durch einen zufälligen Agent initiiert werden. Dieser könnte zum Beispiel eine deutliche Verbesserung durch das weglassen einer Aufgabe feststellen (langer Weg abseits aller anderen Aufgaben). Durch ein Tauschangebot könnte er versuchen diese Aufgabe loszuwerden.
Update 12.05
- Der Tauschprozess startet nach der Auktion. Aktuell wird nach der Auktion von dem Auktionator ein 'Auktion beendet' gesendet. Dies soll als Startpunkt der eigentlichen Simulation dienen.
- Die eigentliche Simulation soll auf Events basieren. Dabei werden bestimmte Zeitpunkte definiert zu denen die Roboter handeln können. Wenn so ein Zeitpunkt aktiv wird, kann der Roboter mit der 'gesparten' Zeit seit dem letzten Event arbeiten. Dies kann zum Beispiel ein Tauschgeschäft sein, dass in der Realität zwischen den Events gelaufen wäre.
- Aktuell sind diese Events das Ende einer Reinigung von einem Raum. Daraus folgt, dass der Weg zu einem Raum sowie die Reinigung eines Raums als eine unzertrennliche Einheit angesehen werden kann.
- Der Grund: Sollte eine Einheit nicht aus einem Raum sowie dem Pfad bestehen, könnte end möglich sein, dass während der Fahrt der nächste Raum getauscht wird. Dies würde zu einer zwingenden Neuberechnung des Pfades führen. Diese kann nicht durchgeführt werden, da in diesem Projekt nur der Graph und keine Karte vorhanden ist.
- Während eines Events kann der Roboter Aufgaben zum Tausch anbieten: Der Roboter beginnt sein Event mit dem berechnen der Aufgaben, die noch nicht abgearbeitet sind und seine objektiven Kosten am schlimmsten beeinflussen. Diese Aufgaben sollen während dieser Pause zum Tausch angeboten werden. Dabei ist es essentiell, dass die Roboter zusammen versuchen möglichst geringe gesamte objektive Kosten zu haben. Daraus folgt, dass ein Roboter beim Handelsangebot immer verdeutlichen muss um welche objektiven Kosten es sich handeln wird, nach und vor dem Tausch. So kann sichergestellt werden, dass sich kein Roboter wesentlich in seinen gesamten objektoven Kosten verschlechtern kann und so auch das Risiko einer Verschlechterung der Flottenkosten minimiert werden kann.
- In einem ersten Schritt werden Gegenangebote mit anderen Aufgaben ausgelassen. Auch soll es sich lediglich nur um eine Aufgabe handeln und das Ausgangsangebot kann auch nicht angepasst werden. Für den Fall, dass ein Roboter in mehreren Tauschprozessen tätig ist, gibt es die Möglichkeit eine ABORT Nachricht zu senden, wenn zum Beispiel ein Tausch stattfand und der Roboter sich aus dem anderen Tauschgeschäft Zurückziehen will.
- Zusätzlich ist das Ziel einen Durchlauf zu simulieren und nicht mehrere. Dies führt dazu, dass die erfahrenen Kosten nicht zurückgeschrieben werden sondern lediglich die objektiven Kosten des Roboters für diesen Durchlauf verändern. Für die Kosten soll vor dem Antritt einer neuen Einheit die subjektiven Kosten verrauscht werden, die die initialen Kosten lediglich Schätzungen sind. Durch die verrauschten subjektiven Kosten, entstehen auch andere objektive Kosten (Zeit) weswegen die nächste Eventausführung anders getimed werden muss.
- Die Roboter können auch während sie zwischen zwei Events sind auf die Anfragen von anderen Robotern, die in einem Event sind, antworten. Dabei gilt die Aufgabe, die aktuell in Arbeit ist schon als abgearbeitet und kann nicht getauscht werden noch abgebrochen werden.
Update 20.12
Der Weg des Tauschens ist in einer ersten Version implementiert und soll in diesem Abschnitt kurz skizziert werden.
Nachrichtenformat
Das Nachrichtenformat ExchangeInfo ist dem Nachrichtenformat für die Auktion sehr ähnlich.
Feld | Beschreibung |
---|---|
string Method | Die gibt an von welchem Subtyp die Nachricht ist. |
string TaskId | Damit wird angegeben um was sich diese Nachricht überhaupt dreht. |
string Source | Dieses Feld dient der Identifizierung von Nodes. Es ist nicht der Absender sondern die Quelle des Gebots. |
string OldObjectiveCost | Die objektiven Kosten einer Node vor dem Hinzufügen oder Entfernen der in TaskId spezifizierten Aufgabe. |
string NewObjectiveCost | Die objektiven Kosten einer Node nach dem Hinzufügen oder Entfernen der in TaskId spezifizierten Aufgabe. |
Die aktuellen Subtypen für das Feld Method sind:
- OFFER: Dies wird von einem Agenten als ein initiales Tauschangebot gesendet. Auf dieses Tauschangebot können dann die anderen Agenten antworten.
- BID: Dies stellt die Antwort auf ein Tauschangebot dar. Außerdem kann ein Agent mehrere BID Nachrichten zu dem selben initialen Tauschangebot senden. Dabei werden vorherige Angebote immer überschrieben.
- RESET: Mit dieser Methode kann ein Agent sein Angebot zurückziehen.-
- ASSIGN: Wenn der initiale Tauschpartner, keine Zeit mehr hat oder durch irgend eine andere Heuristik, sich dazu entschließt den Tausch abzuschließen, wird diese Nachricht benutzt um den Tausch zu bestätigen und allen anderen zu symbolisieren, dass der Tausch geschlossen wurde.
Szenarien
Szenario 1: Es findet ein einfacher Tausch statt. Der Roboter 1 hat aktuelle objektive Kosten von 5 und durch das Loswerden von Aufgabe Room 2 wären es nur noch 3. Auf das Tauschangebot meldet sich ein zweiter Roboter, der durch die Hinzunahme der Aufgabe seine objektiven Kosten auf 4 erhöht, damit aber potenziell der Gruppe zu Gute kommt. Deswegen wird der Tausch bestätigt.
Szenario 2: Zwei Agents bieten eine Aufgabe an und ein dritter Agent beietet auf beide Aufgaben zur gleichen Zeit. Nachdem er nun bei einem Tausch den Zuschlag bekommen hat muss er den anderen Roboter darüber informieren, dass sich seine Kosten geändert haben. Dies kann durch ein Ändern der Kosten passieren oder durch das Zurückziehen seines Tauschangebots.