Agent Compromises in Distributed Problem Solving

Yi Tang*, Jiming Liu, Xiaolong Jin

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

2 Citations (Scopus)


ERA is a multi-agent oriented method for solving constraint satisfaction problems [5]. In this method, agents make decisions based on the information obtained from their environments in the process of solving a problem. Each agent has three basic behaviors: least-move, better-move, and random-move. The random-move is the unique behavior that may help the multi-agent system escape from a local minimum. Although random-move is effective, it is not efficient. In this paper, we introduce the notion of agent compromise into ERA and evaluate its effectiveness and efficiency through solving some benchmark Graph Coloring Problems (GCPs). When solving a GCP by ERA, the edges are transformed into two types of constraints: local constraints and neighbor constraints. When the system gets stuck in a local minimum, a compromise of two neighboring agents that have common violated neighbor constraints may be made. The compromise can eliminate the original violated neighbor constraints and make the two agents act as a single agent. Our experimental results show that agent compromise is an effective and efficient technique for guiding a multi-agent system to escape from a local minimum. Keywords: Agent Compromises, Distributed Constraint Satisfaction Problem, Graph Coloring Problem, Distributed GCP Solving

Original languageEnglish
Pages (from-to)35-42
Number of pages8
JournalLecture Notes in Computer Science
Publication statusPublished - 2004

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Agent Compromises in Distributed Problem Solving'. Together they form a unique fingerprint.

Cite this