Solving Distributed Constraint Optimization Problems Using Cooperative Mediation

Distributed Constraint Optimization Problems (DCOP) have, for a long time, been considered an important research area for multi-agent systems because a vast number of real-world situations can be modeled by them. The goal of many of the researchers interested in DCOP has been to find ways to solve t...

Full description

Saved in:
Bibliographic Details
Main Authors: Mailler, Roger, Lesser, Victor
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Computing methodologies > Artificial intelligence > Distributed artificial intelligence > Cooperation and coordination
Computing methodologies > Artificial intelligence > Distributed artificial intelligence > Multi-agent systems
Constraint optimization
Distributed algorithms
Government
Iterative algorithms
Mathematics of computing > Mathematical analysis > Mathematical optimization
Mediation
Multiagent systems
Permission
Problem-solving
Theory of computation > Design and analysis of algorithms > Mathematical optimization
Yarn
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Distributed Constraint Optimization Problems (DCOP) have, for a long time, been considered an important research area for multi-agent systems because a vast number of real-world situations can be modeled by them. The goal of many of the researchers interested in DCOP has been to find ways to solve them efficiently using fully distributed algorithms which are often based on existing centralized techniques. In this paper, we present an optimal, distributed algorithm called optimal asynchronous partial overlay (OptAPO) for solving DCOPs that is based on a partial centralization technique called cooperative mediation. The key ideas used by this algorithm are that agents, when acting as a mediator, centralize relevant portions of the DCOP, that these centralized subproblems overlap, and that agents increase the size of their subproblems as the problem solving unfolds. We present empirical evidence that shows that OptAPO performs better than other known, optimal DCOP techniques.
DOI:10.5555/1018409.1018777