Enforcing Full Arc Consistency in Asynchronous Forward Bounding Algorithm
Abstract
The AFB BJ+ DAC* is the latest variant of asynchronous forward bounding algorithms used to solve Distributed Constraint Optimization Problems (DCOPs). It uses Directional Arc Consistency (DAC*) to remove, from domains of a given DCOP, values that do not belong to its optimal solution. However, in some cases, DAC∗ does not remove all suboptimal values, which causes more unnecessary research to reach the optimal solution. In this paper, to clear more and more suboptimal values from a DCOP, we use a higher level of DAC* called Full Directional Arc Consistency (FDAC*). This level is based on reapplying AC* several times, which gives the possibility of making more deletions and thus quickly reaching the optimal solution. Experiments on some benchmarks show that the new algorithm, AFB BJ+ FDAC*, is better in terms of communication load and computation effort.
Keywords
DCOP, AFB BJ+ AC*, Soft Arc Consistency, Full Directional Arc Consistency
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
R. Adrdor and L. Koutti, "Enforcing Full Arc Consistency in Asynchronous Forward Bounding Algorithm," in Journal of Communications Software and Systems, vol. 18, no. 1, pp. 9-16, January 2022, doi: https://doi.org/10.24138/jcomss-2021-0083
@article{adrdor2022enforcingfull,
author = {Rachid Adrdor and Lahcen Koutti},
title = {Enforcing Full Arc Consistency in Asynchronous Forward Bounding Algorithm},
journal = {Journal of Communications Software and Systems},
month = {1},
year = {2022},
volume = {18},
number = {1},
pages = {9--16},
doi = {https://doi.org/10.24138/jcomss-2021-0083},
url = {https://doi.org/https://doi.org/10.24138/jcomss-2021-0083}
}