Asynchronous Partial Overlay: A New Algorithm for Solving Distributed Constraint Satisfaction Problems

Distributed Constraint Satisfaction (DCSP) has long been considered an important problem in multi-agent systems research. This is because many real-world problems can be represented as constraint satisfaction and these problems often present themselves in a distributed form. In this article, we pres...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of artificial intelligence research 2006-01, Vol.25, p.529-576
Main Authors: Mailler, R., Lesser, V. R.
Format: Article
Language:English
Subjects:
Algorithms
Artificial intelligence
Multiagent systems
Problem solving
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Distributed Constraint Satisfaction (DCSP) has long been considered an important problem in multi-agent systems research. This is because many real-world problems can be represented as constraint satisfaction and these problems often present themselves in a distributed form. In this article, we present a new complete, distributed algorithm called Asynchronous Partial Overlay (APO) for solving DCSPs that is based on a cooperative mediation process. The primary ideas behind this algorithm are that agents, when acting as a mediator, centralize small, relevant portions of the DCSP, that these centralized subproblems overlap, and that agents increase the size of their subproblems along critical paths within the DCSP as the problem solving unfolds. We present empirical evidence that shows that APO outperforms other known, complete DCSP techniques.
ISSN:1076-9757
1076-9757
1943-5037
DOI:10.1613/jair.1786