A dynamic extension of the asynchronous weak-commitment search algorithm

A current challenge in research is to deal with dynamically changing environments. This paper presents an algorithm to solve a dynamic distributed constraint satisfaction problem (dynamic DCSP) using a multi-agent system. The dynamic DCSP is a distributed CSP in which variables, values, and constraints are distributed among various agents, and those variables, values and constraints can be added to and removed from the system. Most real world applications can be mapped into a dynamic DCSP. The proposed algorithm is an extension of the asynchronous weak commitment search algorithm originally proposed by Yukoo (2001) designed to cope with the dynamically changing parameters of the problem. This paper presents a model for a dynamic DCSP and an agent system implementing the extended algorithm. To validate the algorithm, this paper applied it to a dynamic n-queens problem. The results show that the algorithm can successfully respond to changes to the size of the board and the number of queens, thus confirming its ability to deal with dynamic DCSPs