Author(s): Emma Bowring, Milind Tambe and Makoto Yokoo
Title: Distributed Multi-Criteria Coordination in Multi-Agent Systems
Abstract: Distributed constraint optimization (DCOP) has emerged as a key technique for multiagent coordination. Unfortunately, while previous work in DCOP focuses on optimizing a single team objective, domains often require satisfying additional criteria. This paper provides a family of novel multi-criteria DCOP algorithms, based on two key ideas: (i) automatically transforming multi-criteria problems via additional virtual variables to harness the latest single-criteria DCOP algorithms, while maintaining privacy of the additional criteria; (ii) revealing bounds on criteria to neighbors, where privacy is not essential, to gain efficiency. These ideas result in interleaved multi-criteria searches by multiple agents, illustrated by modifying ADOPT, one of the most efficient current DCOP algorithms. Our Multi-Criteria Adopt algorithm (MCA) family includes MCA-Private that does not reveal the additional criteria to neighbors and MCA-Shared that shares the additional criteria to gain efficiency.
Download: PDF
Thursday, 19-May-2005 20:51:15 CEST