Multi-agent oriented constraint satisfaction

摘要

This paper presents a multi-agent oriented method for solving CSPs (Constraint Satisfaction Problems). In this method, distributed agents represent variables and a two-dimensional grid-like environment in which the agents inhabit corresponds to the domains of the variables. Thus, the positions of the agents in such an environment constitute the solution to a CSP. In order to reach a solution state, the agents will rely on predefined local reactive behaviors; namely, better-move, least-move, and random-move. While presenting the formalisms and algorithm, we will analyze the correctness and complexity of the algorithm, and demonstrate the proposed method with two benchmark CSPs, i.e., n-queen problems and coloring problems. In order to further determine the effectiveness of different reactive behaviors, we will examine the performance of this method in deriving solutions based on behavior prioritization and different selection probabilities.