Title: A Distributed Constraint Optimization Approach for Coordination under Uncertainty
Speaker:James Atlas
University of Delaware
Abstract:
Distributed Constraint Optimization (DCOP) provides a rich framework
for modeling multi-agent coordination problems. Existing problem
domains for DCOP focus on small (<100 variables), deterministic
domains. We present a mapping to DCOP for large-scale team
coordination problems that were used in the DARPA Coordinators
program.
This domain requires distributed, scalable algorithms to meet difficult bounds on computation and communication time. To achieve this goal, we develop a new DCOP algorithm that scales to problems involving hundreds of variables and constraints while converging to better solution qualities than existing DCOP algorithms. In addition, we introduce a new DCOP formalization that allows for our algorithm to process uncertain task qualities and durations represented by discrete utility distributions. We show that our algorithm outperforms other DCOP algorithms for this domain and that our approach is competitive with other general approaches used in the DARPA Coordinators program.
Note: The presented work is part of a paper submitted for review to AAMAS2009.