Aufgabenverteilung
In einer initialen Implementierung sollen die Aufgaben heuristisch verteilt werden.
Dort sollen aber die Mechanismen für eine spätere Auktion schon verwendet werden. Das bedeutet es soll nicht beim Erstellen eines Agentthreads eine Teilmenge der Aufgaben mitgegeben werden, sondern die Aufgaben werden heuristisch von den einzelnen Agents beansprucht.
Erste Idee
Heuristische Verteilung durch zufällige Auswahl einer Aufgabe und dem Versuch diese für sich zu beanspruchen. Dabei ist keine faire Verteilung an Aufgaben gewährleistet. Das Ziel wäre es eine verlässliche und komplette Aufteilung der Aufgaben zu schaffen.
Beanspruchungsprozess von Aufgaben
Wie kann ein Agent eine Aufgabe für sich beanspruchen?
Das Ziel muss es sein, dass ein Agent eine Aufgabe für sich beansprucht ohne Konflikte mit anderen Agenten zu verursachen. Folgende Fälle müssen verhindert werden:
- Zwei Agents dürfen auch wenn Sie sich gleichzeitig für eine Aufgabe entschieden haben, nicht beide letztendlich diese Aufgabe ausführen
- Wenn sich mehrere Agenten für eine Aufgabe interessiert haben und alle diese Aufgabe verwerfen, darf diese Aufgabe nicht im Nirvana landen
Auktion
Version 1
Für die Auktion hat jeder Teilnehmer einen aktiven und einen passiven Part. Der aktive Part ist in folgender Graphik skizziert.
Der passive Part wird solange ausgeführt wie der aktive Part der Auktion lebt.
Version 2
Version 3
Diese Version ist sehr ähnlich zu der zweiten Version, außer das die Kommunikation die aufgabenspezifisch ist jetzt auch über die Aufgabentopics läuft. Außerdem wurde diese Version auch implementiert. Dafür wurde ein neues Nachrichtenformat in ROS eingeführt, dass auf die Eigenschaften dieser Kommunikation zugeschnitten ist.
Folgendes Beispiel konnte mit dieser Version erstellt werden:
Ein besonders großer Nachteil an dieser Version ist aktuell, dass zwei Agents zur gleichen Zeit eine Auktion starten können von der sie gegenseitig zwar was mitkriegen aber beide Auktionen werden zu Ende geführt dies führt zu einem Chaos, da entweder eine Aufgabe zu zwei Agents assigned wird oder ein Agent eine Assign-Nachricht viermal bekommt.
Der letztere Punkt wurde damit behoben, dass in einem Pfad eine Aufgabe nur einmal vorkommen darf. So können alle weiteren Assignment Nachrichten ignoriert werden. Dies ist sollte jedoch nochmal hinterfragt werden.
Topics
Für die Aktionen soll es nicht ein Topic geben in dem alle Auktionen von verschiedenen Räumen abgehalten werden. Es gibt zwei Alternativen, die verwendet werden können. Entweder kann die Auktion über ein Topic gehalten werden, dass dem Auktionator entspricht oder ein Topic ist aufgabenspezifisch und mit der Id der zu versteigernden Id versehen.
Topic pro Auktionator | Topic pro Aufgabe |
---|---|
Durch einen speziellen Auktionator kann auch später die Zuweisung durch einen bestimmte Person erfolgen | Es können nicht zwei Agenten zur gleichen Zeit ein gleiches Versteigerungstopic erstellen |
Durch einen Hauptverantwortlichen muss nicht jeder Agent die Gebote aller anderen speichern und verwalten. Der große Vorteil ist, dass die anderen Teilnehmer so nur reagieren müssen auf die "Aussagen" des Auktionators. | Der Auktionator kann auch mitbieten, da seine Rolle mehr ein Initiator als ein Auktionator ist. |
Unter Berücksichtigung der oben stehenden Abwägung soll folgende Funktionalität implementiert werden.
Version 1 Die Aufgaben sollen in einem Topic, dass der Aufgabe spezifisch ist versteigert werden. Es existiert zwar das Problem, dass zwei Initiatoren gleichzeitig die Versteigerung initiieren. In diesem Fall kann in einer späteren Version, nach der Initiative noch ein Machtkampf ausführen wer von den Initiatoren diese Auktion dann leiten kann. In dieser Version wird kurz vor dem Initiieren noch einmal geprüft ob son ein Topic schon existiert. So sollte in den meisten Fällen nur ein Auktionator übrig bleiben.
Nebenläufigkeit
Sollten mehrere Auktionen gleichzeitig stattfinden?
Pros:
- Eine schnellere Verteilung der Aufgaben kann erfolgen.
Cons:
- Wenn eine Auktion läuft und ein anderer Agent startet eine andere Auktion mit welchem Gebot soll er starten wenn er in der laufenden Aktion der Höchstbietende ist? Es würde zwei abschätzende Kosten geben mit oder ohne die Aufgabe.
Ein vielleicht geeigneter Mittelweg ist die verbindliche Teilnahme an nur einer Auktion von dem Höchstbietenden. Das bedeutet ein Agent der in einer Auktion der Höchstbietende ist kann keine Auktionen initiieren und auch nicht in anderen Auktionen mitbieten.
Dieser Umgang mit den Agents hat den Vorteil, dass bei einer Auktion nicht berücksichtigt werden muss, dass ein Agent ein Gebot zurückzieht oder Agents zu viele falsche Gebote unterbreiten unter falschen Annahmen.