Multi-agent oriented constraint satisfaction

Jiming LIU*, Han Jing, Y. Y. Tang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

162 Citations (Scopus)

Abstract

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 probabiities.

Original languageEnglish
Pages (from-to)101-144
Number of pages44
JournalArtificial Intelligence
Volume136
Issue number1
DOIs
Publication statusPublished - Mar 2002

Scopus Subject Areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

User-Defined Keywords

  • Behavior prioritization
  • Behavior selection
  • Constraint satisfaction
  • Experimental validation
  • Multi-agent
  • Reactive moving behaviors

Fingerprint

Dive into the research topics of 'Multi-agent oriented constraint satisfaction'. Together they form a unique fingerprint.

Cite this