Constraint Programming research is currently aimed at solving problems in a dynamically changing environment. This paper addresses the problem of solving a Dynamic Distributed Constraint Satisfaction Problem (Dynamic DCSP). The solution proposed is an algorithm implemented in a multi- agent system. A Dynamic DCSP is a problem in which variables, values and constraints are distributed among various agents. Agents can be freely added to or removed from the system. Most advanced applications cannot be represented by DCSPs, but they can be modeled by Dynamic DCSPs. The algorithm described in this paper is an extension of the Asynchronous Weak Commitment Search algorithm (AWCS) originally proposed by Yukoo [10]. The extended algorithm is designed to cope with the dynamically changing parameters of a Dynamic DCSP. The proposed algorithm differs from other Dynamic DCSP algorithms because it allows an unlimited number of changes to any of the variables, values, or constraints. This paper describes an agent system implementing the modified AWCS algorithm and verifies its effectiveness by applying it to a dynamic N-Queens problem. The results prove the applicability of the modified algorithm to Dynamic DCSP.
展开▼
