Heeten Choxi, Pragnesh Jay Modi
We present a new algorithm called Variable Message Size (VMS) ADOPT for solving Distributed Constraint Optimization Problems (DCOP) which trades off message size and memory usage for running time. The algorithm is applied to a wireless network optimization problem, in which small robots act as wireless routers with the objective of maximizing signal strength in the network by repositioning themselves. Memory and bandwidth are limited resources in this application; our algorithm incorporates features of ADOPT and DPOP and introduces a parameter which controls the memory usage and message size at each agent. Bounded-error approximation can also be used to trade off solution quality for running time.
Subjects: 15.2 Constraint Satisfaction; 7.1 Multi-Agent Systems
Submitted: May 14, 2007