Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Event Scheduling
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 Distrib...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2004
|
| Subjects: | |
| 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | 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. |
|---|