Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT


Syed M. Ali, Sven Koenig, and Milind Tambe. 2005. “Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT .” In Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS).


Methods for solving Distributed Constraint Optimization Problems (DCOP) have emerged as key techniques for distributed reasoning. Yet, their application faces significant hurdles in many multiagent domains due to their inefficiency. Preprocessing techniques have successfully been used to speed up algorithms for centralized constraint satisfaction problems. This paper introduces a framework of different preprocessing techniques that are based on dynamic programming and speed up ADOPT, an asynchronous complete and optimal DCOP algorithm. We investigate when preprocessing is useful and which factors influence the resulting speedups in two DCOP domains, namely graph coloring and distributed sensor networks. Our experimental results demonstrate that our preprocessing techniques are fast and can speed up ADOPT by an order of magnitude.
See also: 2005