Algorithms And Ordering Heuristics For Distributed Constraint Satisfaction Problems
Distributed Constraint Satisfaction Problems (DisCSP) is a general framework for solving distributed problems. DisCSP have a wide range of applications in multi agent coordination. In this thesis, we extend the state of the art in solving the DisCSPs by proposing several algorithms. Firstly, we propose the Nogood Based Asynchronous Forward Checking (AFC ng) an algorithm based on Asynchronous Forward Checking (AFC) However, instead of using the shortest inconsistent partial assignments, AFC ng uses nogoods as justifications of value removals. Unlike AFC, AFC ng allows concurrent backtracks to be performed at the same time coming from different agents having an empty domain to different destinations. Then, we propose the Asynchronous Forward Checking Tree (AFCtree) In AFC tree, agents are prioritized according to a pseudo tree arrangement of the constraint graph. Using this priority ordering, AFC tree performs multiple AFC ng processes on the paths from the root to the leaves of the pseudo tree. Next, we propose to maintain arc consistency asynchronously on the future agents instead of only maintaining forward checking. Two new synchronous search algorithms that maintain arc consistency asynchronously (MACA) are presented. After that, we developed the Agile Asynchronous Backtracking (Agile ABT) an asynchronous dynamic ordering algorithm that does not follow the standard restrictions in asynchronous backtracking algorithms. The order of agents appearing before the agent receiving a backtrack message can be changed with a great freedom while ensuring polynomial space complexity. Next, we present a corrigendum of the protocol designed for establishing the priority between orders in the asynchronous backtracking algorithm with dynamic ordering using retroactive heuristics (ABT_DO Retro) Finally, the new version of the DisChoco open source platform for solving distributed constraint reasoning problems is described. The new version is a complete redesign of the DisChoco platform. DisChoco 2.0 is an open source Java library which aims at implementing distributed constraint reasoning algorithms.