Lösung verteilter Constraint-Optimierungsprobleme mittels kooperativer Mediation

Verteilte Constraint-Optimierungsprobleme (DCOP) gelten seit langem als ein wichtiges Forschungsgebiet für Multi-Agenten-Systeme, da zahlreiche reale Situationen durch sie modelliert werden können. Ziel vieler Forscher, die sich für DCOP interessieren, war es, Wege zu finden, diese effizient mit vollständig verteilten Algorithmen zu lösen, die oft auf bestehenden zentralen Techniken basieren. In diesem Papier präsentieren wir einen optimalen, verteilten Algorithmus namens optimal asynchronous partial overlay (OptAPO) zur Lösung von DCOPs, der auf einer partiellen Zentralisierungstechnik namens kooperative Mediation basiert. Die Schlüsselfunktionen dieses Algorithmus bestehen darin, dass Agenten, die als Mediator fungieren, relevante Teile des DCOP zentralisieren, dass diese zentralisierten Teilprobleme sich überschneiden und dass Agenten die Größe ihrer Teilprobleme während des Problemlösungsprozesses erhöhen. Wir präsentieren empirische Beweise, die zeigen, dass OptAPO besser abschneidet als andere bekannte, optimale DCOP-Techniken.