Reordering all agents in asynchronous backtracking for distributed constraint satisfaction problems
dc.contributor.author | Mechqrane, Younes | |
dc.contributor.author | Wahbi, Mohamed | |
dc.contributor.author | Bessiere, Christian | |
dc.contributor.author | Brown, Kenneth N. | |
dc.contributor.funder | Science Foundation Ireland | en |
dc.contributor.funder | European Regional Development Fund | en |
dc.date.accessioned | 2021-02-23T11:45:18Z | |
dc.date.available | 2021-02-23T11:45:18Z | |
dc.date.issued | 2019-09-20 | |
dc.date.updated | 2021-02-23T11:38:12Z | |
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.description.status | Peer reviewed | en |
dc.description.version | Accepted Version | en |
dc.format.mimetype | application/pdf | en |
dc.identifier.articleid | 103169 | en |
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.doi | 10.1016/j.artint.2019.103169 | en |
dc.identifier.endpage | 28 | en |
dc.identifier.issn | 0004-3702 | |
dc.identifier.journaltitle | Artificial Intelligence Journal | en |
dc.identifier.startpage | 1 | en |
dc.identifier.uri | https://hdl.handle.net/10468/11094 | |
dc.identifier.volume | 278 | en |
dc.language.iso | en | en |
dc.publisher | Elsevier | 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 |
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 |