Reordering all agents in asynchronous backtracking for distributed constraint satisfaction problems

Simple item page
dc.contributor.authorMechqrane, Younes
dc.contributor.authorWahbi, Mohamed
dc.contributor.authorBessiere, Christian
dc.contributor.authorBrown, Kenneth N.
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderEuropean Regional Development Funden
dc.date.accessioned2021-02-23T11:45:18Z
dc.date.available2021-02-23T11:45:18Z
dc.date.issued2019-09-20
dc.date.updated2021-02-23T11:38:12Z
dc.description.abstractDistributed constraint satisfaction problems (DisCSPs) can express decision problems where physically distributed agents control different decision variables, but must coordinate with each other to agree on a global solution. Asynchronous Backtracking (ABT) is a pivotal search procedure for DisCSPs. ABT requires a static total ordering on the agents. However, reordering agents during search is an essential component for efficiently solving a DisCSP. All polynomial space algorithms proposed so far to improve ABT by reordering agents during search only allow a limited amount of reordering. In this paper, we propose AgileABT, a general framework for reordering agents asynchronously that is able to change the ordering of all agents. This is done via the original notion of termination value, a label attached to the orders exchanged by agents during search. We prove that AgileABT is sound and complete. We show that, thanks to termination values, our framework allows us to implement the main variable ordering heuristics from centralized CSPs, which until now could not be applied to the distributed setting. We prove that AgileABT terminates and has a polynomial space complexity in all these cases. Our empirical study shows the significance of our framework compared to state-of-the-art asynchronous dynamic ordering algorithms for solving distributed CSP.en
dc.description.sponsorshipScience Foundation Ireland (under Grant No. 12/RC/2289 P2 which is co-funded under the European Regional Development Fund)en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.articleid103169en
dc.identifier.citationMechqrane, Y., Wahbi, M., Bessiere, C. and Brown, K. N. (2020) 'Reordering all agents in asynchronous backtracking for distributed constraint satisfaction problems', Artificial Intelligence, 278, 103169 (28 pp). doi: 10.1016/j.artint.2019.103169en
dc.identifier.doi10.1016/j.artint.2019.103169en
dc.identifier.endpage28en
dc.identifier.issn0004-3702
dc.identifier.journaltitleArtificial Intelligence Journalen
dc.identifier.startpage1en
dc.identifier.urihttps://hdl.handle.net/10468/11094
dc.identifier.volume278en
dc.language.isoenen
dc.publisherElsevieren
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.urihttps://www.sciencedirect.com/science/article/pii/S0004370218303643
dc.rights© 2019 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/en
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/en
dc.subjectAsynchronous backtrackingen
dc.subjectDistributed constraint reasoningen
dc.subjectDynamic variable orderingen
dc.titleReordering all agents in asynchronous backtracking for distributed constraint satisfaction problemsen
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
v82-12-10-2019-cb-very-crc.pdf
Size:
774.52 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Journal Articles
Insight Centre for Data Analytics - Journal Articles