Taking DCOP to the real world: efficient complete solutions for distributed multi-event scheduling

By R. Maheswaran, Milind Tambe, E. Bowring, J. Pearce, Pradeep Varakantham. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, 2004. AAMAS 2004., 2004

329 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/a3f55604a0a564592adb105da84da58e38940891

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Alessandro Farinelli
2. Boi Faltings
3. Harel Yedidsion
4. Adrian Petcu

In Computer Networks and Communications

1. Alessandro Farinelli
2. Boi Faltings
3. Adrian Petcu

In Signal Processing

1. Boi Faltings
2. Adrian Petcu

Citations in the corpus

• A Scalable Method for Multiagent Constraint Optimization (2005, methodology): “It was shown in [Bayardo and Miranker, 1995] that there are ways to obtain shallow pseudotrees (within a logarithmic factor of the induced width), but these require intricate heuristics like the ones from [Freuder and Quinn, 1985; Maheswaran et al., 2004], which have not yet been adapted to a distri”
• Applying max-sum to teams of mobile sensing agents (2018, methodology): “The local distributed search algorithms that were proposed for solving DCOP_MST, were adjustments of standard local search techniques (such as Maximum Gain Message (MGM) Maheswaran et al., 2004a and Distributed Stochastic Algorithm (DSA) Zhang et al., 2005) to the model, enhanced by specifically-des”