MP-ABT: A Minimal Perturbation Approach for Complex Local Problems

Ghizlane El Khattabi, El Mehdi El Graoui, Imade Benelallam, El Houssine Bouyakhf

2017

Abstract

The ability of Distributed Constraints Reasoning (DCR) to solve distributed combinatorial problems brings the DCR to have a considerable interest in multi-agent community. Hence, many DisCSP algorithms have been proposed in order to solve such distributed problems. The major limit of these algorithms is the simplification assumptions. The scientists assume that each agent is a simple one; it handles just one variable. But in the complex local problem case; where each agent has more than one variable; two methods are used: The compilation and the decomposition. These methods transform the original problem so as to make it as a simple one. In this paper, we propose a new protocol: MP-ABT (Minimal Perturbation complex local problems in the Asynchronous Backtracking). It is a resolution algorithm of DisCSPs with complex local problems. It is based on the ABT algorithm and the Dynamic CSP. Each complex agent is seen as a Minimal Perturbation Problem (MPP) and any received message is considered as a new intra-constraint perturbation event. The complex local problem is updated and a new MPP local solution is reported. The MP-ABT is presented and compared to three ABT families. Our experimental results show the MP-ABT effectiveness.

Paper Citation

in Harvard Style

El Khattabi G., El Graoui E., Benelallam I. and Bouyakhf E. (2017). MP-ABT: A Minimal Perturbation Approach for Complex Local Problems . In Proceedings of the 9th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-758-219-6, pages 268-275. DOI: 10.5220/0006203502680275

in Bibtex Style

@conference{icaart17,
author={Ghizlane El Khattabi and El Mehdi El Graoui and Imade Benelallam and El Houssine Bouyakhf},
title={MP-ABT: A Minimal Perturbation Approach for Complex Local Problems},
booktitle={Proceedings of the 9th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2017},
pages={268-275},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0006203502680275},
isbn={978-989-758-219-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 9th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - MP-ABT: A Minimal Perturbation Approach for Complex Local Problems
SN - 978-989-758-219-6
AU - El Khattabi G.
AU - El Graoui E.
AU - Benelallam I.
AU - Bouyakhf E.
PY - 2017
SP - 268
EP - 275
DO - 10.5220/0006203502680275