Skoči na glavni sadržaj

Izvorni znanstveni članak

https://doi.org/10.24138/jcomss-2021-0083

Enforcing Full Arc Consistency in Asynchronous Forward Bounding Algorithm

Rachid Adrdor orcid id orcid.org/0000-0002-7885-0713 ; Department of Computer Science, Faculty of Sciences, Agadir, Morocco
Lahcen Koutti ; Department of Computer Science, Faculty of Sciences, Agadir, Morocco


Puni tekst: engleski pdf 901 Kb

str. 9-16

preuzimanja: 40

citiraj


Sažetak

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.

Ključne riječi

DCOP, AFB BJ+ AC*, Soft Arc Consistency, Full Directional Arc Consistency

Hrčak ID:

271059

URI

https://hrcak.srce.hr/271059

Posjeta: 126 *