Abstract
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 (AFC- tree). 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.