Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Event Scheduling

• Main Authors: MAHESWARAN, Rajiv, Tambe, Milind, Bowring, Emma, Pearce, Jonathan, VARAKANTHAM, Pradeep
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2004
• Subjects: Artificial Intelligence and Robotics; Business; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/935; https://ink.library.smu.edu.sg/context/sis_research/article/1934/viewcontent/RealWorldDCOP.pdf
• Institution: Singapore Management University

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.