Compilation Formulation for Asynchronous Backtracking with Complex Local Problems

Author

Ezzahir, Redouane ; Belaissaoui, Mustapha ; Bessiere, Christian ; Bouyakhf, El Houssine

Author_Institution

Univ. of Mohammed V Agdal, Rabat

fYear

2007

fDate

28-30 March 2007

Firstpage

205

Lastpage

211

Abstract

The Asynchronous BackTracklng (ABT) algorithm is a well known algorithm for solving distributed constraint satisfaction problems. However, several work which interest to ABT suppose that each agent owns one single variable. In this paper, we present the compilation formulation for Asynchronous Backtracking with complex local problems, resulting in the ABT-cf algorithm. The ABT-cf algorithm is described in detail and its correctness proof. An extensive experimental evaluation of the proposed algorithm is carried on random binary DisCSP. The performances of ABT-cf is compared to the standard ABT in which the distributed problem is reformulated by decomposition. Experimental evaluation shows that ABT-cf increases the performance of the distributed search and outperforms standard ABT by a large scale.

Keywords

backtracking; distributed algorithms; program compilers; asynchronous backtracking algorithm; compilation formulation; complex local problem; correctness proof; distributed constraint satisfaction problem; distributed search; Artificial intelligence; Autonomous agents; Large-scale systems; Libraries; Multiagent systems; Performance evaluation; Protocols;

fLanguage

English

Publisher

ieee

Conference_Titel

Computational Intelligence and Intelligent Informatics, 2007. ISCIII '07. International Symposium on

Conference_Location

Agadir

Print_ISBN

1-4244-1158-0

Electronic_ISBN

1-4244-1158-0

Type

conf

DOI

10.1109/ISCIII.2007.367390

Filename

4218423