Abstract:
Distributed optimization requires the optimization of a global objective function that is distributed among a set of autonomous, communicating agents and is unknown by any individual agent. The problem is inherently distributed and the solution strategy has no control over a given distribution. Constraint based techniques offer a promising approach for coordinating a set of distributed agents to find optimal solutions. However previous work has the following limitations. First, representation is limited to binary good/nogood constraints. In many domains, it is more natural to represent constraints as having degrees of valuation. Second, previous work on distributed optimization problems has relied on synchronous sequential computation to find optimal solutions. This is slow and requires agents to block for messages. Third, previous asychronous approaches lack any guarantees of optimality even when given sufficient time and provide little guidance on how to trade-off solution quality for time-to-solution when time is limited. This work proposes Adopt, an asynchronous, distributed, complete method for solving distributed optimization problems. The fundamental ideas in Adopt are to represent constraints as discrete functions (or valuations) --- instead of binary good/nogood values --- and to use the evaluation of these constraints to measure progress towards optimality. In addition, Adopt uses a sound and complete partial solution combination method to allow non-sequential, asychronous computation. Finally, Adopt is not only provably optimal when given enough time, but allows solution time/quality tradeoffs when time is limited. Adopt is applied to a real-world distributed resource allocation problem. Distributed resource allocation is a general problem in which a set of agents must optimally assign their resources to a set of tasks with respect to certain criteria. It arises in many real-world domains such as distributed sensor networks, disaster rescue, hospital scheduling, and others.