| Paper Details: | Downloads: 642 |
| Serial Number: | P1120827002
|
| Title: | Asynchronous Backtracking with Compilation Formulation for handling complex local problems
|
| Authors: | Redouane EZZAHIR, Christian BESSIERE, El Houssine Bouyakhf, Mustapha BELAISSAOUI
|
| Abstract: | The Asynchronous Backtracking (ABT) algorithm is a well known algorithm for solving distributed constraint satisfaction problems. However, several works concerned with ABT suppose that each agent owns a single variable. This paper presents the compilation formulation for Asynchronous Backtracking with complex local problems, resulting in the Asynchronous Backtracking with compilation formulation algorithm (ABT-cf). The ABT-cf algorithm and its correctness proof are described in detail. A new interchangeability technique is also presented in detail. The performances of ABT-cf are compared to the standard ABT in which the distributed problem is reformulated by decomposition. Experimental evaluation shows that our interchangeability technique gives a consistent performance improvements in terms of non-concurrent constraint checks, and that ABT-cf increases the performance of the distributed search and outperforms standard ABT by a large scale.
|
| Keywords: | DCR, Distributed constraints satisfaction problem, ABT algorithm, complex local problems, interchangeability.
|
| Journal/Conference: | International Journal of Artificial Intelligence and Machine Learning
|
| Volume: | 8
|
| Issue: | 3
|
| Submission Date: | 7/4/2008 12:00:00 AM
|
| Review Date: | 7/25/2008 12:00:00 AM
|
| Publishing Date: | 10/26/2008 12:00:00 AM
|
| Article Downloads: | 642
|
| Download: |
|