View in EDS

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

Saved in:
Bibliographic Details
Title: Asynchronous Partial Overlay: A New Algorithm for Solving Distributed Constraint Satisfaction Problems.
Authors: Mailler, Roger1 MAILLER@AI.SRI.COM, Lesser, Victor R.2 LESSER@CS.UMASS.EDU
Source: Journal of Artificial Intelligence Research. 2006, Vol. 25, p529-576. 48p. 7 Diagrams, 12 Charts, 15 Graphs.
Subjects: Constraint satisfaction, Algorithms, Problem solving, Computer systems, Artificial intelligence
Abstract: 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. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Artificial Intelligence Research is the property of AI Access Foundation and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 25888495
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Asynchronous Partial Overlay: A New Algorithm for Solving Distributed Constraint Satisfaction Problems.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Mailler%2C+Roger%22">Mailler, Roger</searchLink><relatesTo>1</relatesTo><i> MAILLER@AI.SRI.COM</i><br /><searchLink fieldCode="AR" term="%22Lesser%2C+Victor+R%2E%22">Lesser, Victor R.</searchLink><relatesTo>2</relatesTo><i> LESSER@CS.UMASS.EDU</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Artificial+Intelligence+Research%22">Journal of Artificial Intelligence Research</searchLink>. 2006, Vol. 25, p529-576. 48p. 7 Diagrams, 12 Charts, 15 Graphs.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Constraint+satisfaction%22">Constraint satisfaction</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+solving%22">Problem solving</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+systems%22">Computer systems</searchLink><br /><searchLink fieldCode="DE" term="%22Artificial+intelligence%22">Artificial intelligence</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Artificial Intelligence Research is the property of AI Access Foundation and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=25888495
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1613/jair.1786
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 48
        StartPage: 529
    Subjects:
      – SubjectFull: Constraint satisfaction
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Problem solving
        Type: general
      – SubjectFull: Computer systems
        Type: general
      – SubjectFull: Artificial intelligence
        Type: general
    Titles:
      – TitleFull: Asynchronous Partial Overlay: A New Algorithm for Solving Distributed Constraint Satisfaction Problems.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Mailler, Roger
      – PersonEntity:
          Name:
            NameFull: Lesser, Victor R.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: 2006
              Type: published
              Y: 2006
          Identifiers:
            – Type: issn-print
              Value: 10769757
          Numbering:
            – Type: volume
              Value: 25
          Titles:
            – TitleFull: Journal of Artificial Intelligence Research
              Type: main
ResultId 1