Asynchronous algorithms for approximate distributed constraint optimization with quality bounds

Asynchronous algorithms for approximate distributed constraint optimization with quality bounds,10.1145/1838206.1838225,Christopher Kiekintveld,Zhengy

Asynchronous algorithms for approximate distributed constraint optimization with quality bounds   (Citations: 1)
BibTex | RIS | RefWorks Download
Distributed Constraint Optimization (DCOP) is a popular frame- work for cooperative multi-agent decision making. DCOP is NP- hard, so an important line of work focuses on developing fast in- complete solution algorithms for large-scale applications. One of the few incomplete algorithms to provide bounds on solution qual- ity is k-size optimality, which defines a local optimality criterion based on the size of the group of deviating agents. Unfortunately, the lack of a general-purpose algorithm and the commitment to forming groups based solely on group size has limited the use of k-size optimality. This paper introduces t-distance optimality which departs from k-size optimality by using graph distance as an alternative criteria for selecting groups of deviating agents. This throws open a new re- search direction into the tradeoffs between different group selection and coordination mechanisms for incomplete DCOP algorithms. We derive theoretical quality bounds for t-distance optimality that improve known bounds for k-size optimality. In addition, we de- velop a new efficient asynchronous local search algorithm for find- ing both k-size and t-distance optimal solutions — allowing these concepts to be deployed in real applications. Indeed, empirical re- sults show that this algorithm significantly outperforms the only ex- isting algorithm for finding generalk-size optimal solutions, which is also synchronous. Finally, we compare the algorithmic perfor- mance ofk-size andt-distance optimality using this algorithm. We find that t-distance consistently converges to higher-quality solu- tions in the long run, but results are mixed on convergence speed; we identify cases wherek-size andt-distance converge faster.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Most of the incomplete algorithms in the literature provide no guarantees on solution quality, but two new methods based on local optimality criteria, k-size optimality [23] and t-distance optimality [11], offer both fast solutions and bounds on solution quality...
    • ...1 More details about the algorithm can be found elsewhere [11]...

    Matthew E. Tayloret al. Two Decades of Multiagent Teamwork Research: Past, Present, and Future

Sort by: