(Eingereicht am 30. März 2020)

Abstract: Das Problem der Koalitionsbildung mit räumlichen und zeitlichen Beschränkungen (CFSTP)
ist ein Aufgabenzuweisungsproblem mit mehreren Agenten, bei dem die Agenten kooperieren und
wenige, die Aufgaben sind viele, räumlich verteilt, mit Fristen und Arbeitsaufwand,
und das Ziel besteht darin, einen Zeitplan zu finden, der die Anzahl der abgeschlossenen Arbeiten maximiert
Aufgaben. Der aktuell hochmoderne CFSTP-Löser, die Coalition Formation mit
Der Look-Ahead-Algorithmus (CFLA) weist zwei Haupteinschränkungen auf. Erstens ist es Zeit
Die Komplexität ist quadratisch mit der Anzahl der Aufgaben und exponentiell mit der
Anzahl der Agenten, was es nicht effizient macht. Zweitens ist es ein Ausblick
Die Technik ist in realen Szenarien, wie z. B. offenen Multi-Agenten, nicht effektiv
Systeme, in denen jederzeit neue Aufgaben auftauchen können. Motiviert daraus schlagen wir vor
eine Erweiterung von CFLA, die wir Coalition Formation with Improved nennen
Look-Ahead (CFLA+). Da CFLA+ die Einschränkungen von CFLA übernimmt, gilt dies auch
Entwickeln Sie einen neuartigen Algorithmus zur Lösung des CFSTP, der als erster sowohl jederzeit als auch jederzeit möglich ist
effizient, was wir Clustered-based Coalition Formation (CCF) nennen. Wir
empirisch zeigen, dass dies in Umgebungen geschieht, in denen die Look-Ahead-Technik stark ausgeprägt ist
effektiv erledigt CCF bis zu 20 % (bzw. 10 %) mehr Aufgaben als CFLA (bzw.
CFLA+) und ist dabei bis zu vier Größenordnungen schneller. Unsere Ergebnisse bestätigen
CCF als neuer hochmoderner CFSTP-Löser.