Reordering all agents in asynchronous backtracking for distributed constraint satisfaction problems

Show simple item record

dc.contributor.author Mechqrane, Younes
dc.contributor.author Wahbi, Mohamed
dc.contributor.author Bessiere, Christian
dc.contributor.author Brown, Kenneth N.
dc.date.accessioned 2021-02-23T11:45:18Z
dc.date.available 2021-02-23T11:45:18Z
dc.date.issued 2019-09-20
dc.identifier.citation Mechqrane, 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.103169 en
dc.identifier.volume 278 en
dc.identifier.startpage 1 en
dc.identifier.endpage 28 en
dc.identifier.issn 0004-3702
dc.identifier.uri http://hdl.handle.net/10468/11094
dc.identifier.doi 10.1016/j.artint.2019.103169 en
dc.description.abstract Distributed 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.sponsorship Science Foundation Ireland (under Grant No. 12/RC/2289 P2 which is co-funded under the European Regional Development Fund) en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Elsevier en
dc.relation.uri https://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.uri https://creativecommons.org/licenses/by-nc-nd/4.0/ en
dc.subject Asynchronous backtracking en
dc.subject Distributed constraint reasoning en
dc.subject Dynamic variable ordering en
dc.title Reordering all agents in asynchronous backtracking for distributed constraint satisfaction problems en
dc.type Article (peer-reviewed) en
dc.internal.authorcontactother Kenneth Brown, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: k.brown@cs.ucc.ie en
dc.internal.availability Full text available en
dc.date.updated 2021-02-23T11:38:12Z
dc.description.version Accepted Version en
dc.internal.rssid 500437589
dc.contributor.funder Science Foundation Ireland en
dc.contributor.funder European Regional Development Fund en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Artificial Intelligence Journal en
dc.internal.copyrightchecked Yes
dc.internal.licenseacceptance Yes en
dc.internal.IRISemailaddress k.brown@cs.ucc.ie en
dc.identifier.articleid 103169 en
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ en


Files in this item

This item appears in the following Collection(s)

Show simple item record

© 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/ Except where otherwise noted, this item's license is described as © 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/
This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement