Agent Compromises in Distributed Problem Solving

Yi Tang*, Jiming Liu, Xiaolong Jin

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-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.

Original languageEnglish
Title of host publicationIntelligent Data Engineering and Automated Learning
Subtitle of host publication4th International Conference, IDEAL 2003 Hong Kong, China, March 21–23, 2003 Revised Papers
EditorsJiming Liu, Yiu-ming Cheung, Hujun Yin
Place of PublicationBerlin, Heidelberg
Number of pages8
ISBN (Electronic)9783540450801
ISBN (Print)9783540405504
Publication statusPublished - 29 Jul 2003
Event4th International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2003 - , Hong Kong
Duration: 21 Mar 200323 Mar 2003

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameInternational Conference on Intelligent Data Engineering and Automated Learning


Conference4th International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2003
Country/TerritoryHong Kong
Internet address

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Agent Compromises
  • Distributed Constraint Satisfaction Problem
  • Graph Coloring Problem
  • Distributed GCP Solving


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

Cite this