AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
K-Swaps: Cooperative Negotiation for Solving Task-Allocation Problems
Xiaoming Zheng, Sven Koenig

Last modified: 2009-06-24


In this paper, we study distributed algorithms for cooperative agents that  allow them to exchange their assigned tasks in order to reduce their team  cost. We define a new type of contract, called K-swaps, that describes multiple task exchanges among multiple agents at a time, which generalizes the concept of single task exchanges. We design a distributed algorithm that constructs all possible K-swaps that reduce the team cost of a given task allocation and show that each agent typically only needs to communicate a small part of its local computation results to the other agents. We then demonstrate empirically that K-swaps can reduce the team costs of several existing task-allocation algorithms significantly even if K is small.


Distributed Task Allocation; Distributed AI; Negotiation and Contract-Based Systems; Auctions and Market-Based Systems

Full Text: PDF