Publication Type

Conference Proceeding Article

Publication Date

7-2004

Abstract

Distributed Constraint Optimization (DCOP) is an elegant formalism relevant to many areas in multiagent systems, yet complete algorithms have not been pursued for real world applications due to perceived complexity. To capably capture a rich class of complex problem domains, we introduce the Distributed Multi-Event Scheduling (DiMES) framework and design congruent DCOP formulations with binary constraints which are proven to yield the optimal solution. To approach real-world efficiency requirements, we obtain immense speedups by improving communication structure and precomputing best case bounds. Heuristics for generating better communication structures and calculating bound in a distributed manner are provided and tested on systematically developed domains for meeting scheduling and sensor networks, exemplifying the viability of complete algorithms.

Discipline

Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Decision Analytics

Publication

AAMAS '04: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems: New York, USA, July 19-23, 2004

First Page

310

Last Page

317

ISBN

9781581138641

Identifier

10.1109/AAMAS.2004.257

Publisher

IEEE Computer Society

City or Country

Los Alamitos, CA

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://portal.acm.org/citation.cfm?id=1018762