MP-ABT: A Minimal Perturbation Approach for Complex Local Problems
Ghizlane El Khattabi, El Mehdi El Graoui, Imade Benelallam, El Houssine Bouyakhf · 2017
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.