Agent Compromises in Distributed Problem Solving

Yi Tang; Jiming Liu; Xiaolong Jin

doi:10.1007/978-3-540-45080-1_5

Agent Compromises in Distributed Problem Solving

Yi Tang^*, Jiming Liu, Xiaolong Jin

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

2 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Intelligent Data Engineering and Automated Learning
Subtitle of host publication	4th International Conference, IDEAL 2003 Hong Kong, China, March 21–23, 2003 Revised Papers
Editors	Jiming Liu, Yiu-ming Cheung, Hujun Yin
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	35-42
Number of pages	8
Edition	1st
ISBN (Electronic)	9783540450801
ISBN (Print)	9783540405504
DOIs	https://doi.org/10.1007/978-3-540-45080-1_5
Publication status	Published - 29 Jul 2003
Event	4th International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2003 - Hong Kong Convention and Exhibition Centre, Hong Kong, China Duration: 21 Mar 2003 → 23 Mar 2003 https://link.springer.com/book/10.1007/b11717 http://www.comp.hkbu.edu.hk/IDEAL2003/ (conference website) http://www.comp.hkbu.edu.hk/IDEAL2003/ (conference program)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2690
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	International Conference on Intelligent Data Engineering and Automated Learning

Conference

Conference	4th International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2003
Country/Territory	China
City	Hong Kong
Period	21/03/03 → 23/03/03
Internet address	https://link.springer.com/book/10.1007/b11717 http://www.comp.hkbu.edu.hk/IDEAL2003/ (conference website) http://www.comp.hkbu.edu.hk/IDEAL2003/ (conference program)

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

User-Defined Keywords

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

Access to Document

10.1007/978-3-540-45080-1_5

Cite this

Tang, Y., Liu, J., & Jin, X. (2003). Agent Compromises in Distributed Problem Solving. In J. Liu, Y. Cheung, & H. Yin (Eds.), Intelligent Data Engineering and Automated Learning: 4th International Conference, IDEAL 2003 Hong Kong, China, March 21–23, 2003 Revised Papers (1st ed., pp. 35-42). (Lecture Notes in Computer Science; Vol. 2690), (International Conference on Intelligent Data Engineering and Automated Learning). Springer. https://doi.org/10.1007/978-3-540-45080-1_5

Tang, Yi ; Liu, Jiming ; Jin, Xiaolong. / Agent Compromises in Distributed Problem Solving. Intelligent Data Engineering and Automated Learning: 4th International Conference, IDEAL 2003 Hong Kong, China, March 21–23, 2003 Revised Papers. editor / Jiming Liu ; Yiu-ming Cheung ; Hujun Yin. 1st. ed. Berlin, Heidelberg : Springer, 2003. pp. 35-42 (Lecture Notes in Computer Science). (International Conference on Intelligent Data Engineering and Automated Learning).

@inproceedings{3e6a56d4feed4422b8dabb52030b96d5,

title = "Agent Compromises in Distributed Problem Solving",

abstract = "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",

author = "Yi Tang and Jiming Liu and Xiaolong Jin",

note = "Copyright: Copyright 2008 Elsevier B.V., All rights reserved.; 4th International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2003 ; Conference date: 21-03-2003 Through 23-03-2003",

year = "2003",

month = jul,

day = "29",

doi = "10.1007/978-3-540-45080-1_5",

language = "English",

isbn = "9783540405504",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "35--42",

editor = "Jiming Liu and Yiu-ming Cheung and Hujun Yin",

booktitle = "Intelligent Data Engineering and Automated Learning",

edition = "1st",

url = "https://link.springer.com/book/10.1007/b11717, http://www.comp.hkbu.edu.hk/IDEAL2003/, http://www.comp.hkbu.edu.hk/IDEAL2003/",

}

Tang, Y, Liu, J & Jin, X 2003, Agent Compromises in Distributed Problem Solving. in J Liu, Y Cheung & H Yin (eds), Intelligent Data Engineering and Automated Learning: 4th International Conference, IDEAL 2003 Hong Kong, China, March 21–23, 2003 Revised Papers. 1st edn, Lecture Notes in Computer Science, vol. 2690, International Conference on Intelligent Data Engineering and Automated Learning, Springer, Berlin, Heidelberg, pp. 35-42, 4th International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2003, Hong Kong, China, 21/03/03. https://doi.org/10.1007/978-3-540-45080-1_5

Agent Compromises in Distributed Problem Solving. / Tang, Yi; Liu, Jiming; Jin, Xiaolong.
Intelligent Data Engineering and Automated Learning: 4th International Conference, IDEAL 2003 Hong Kong, China, March 21–23, 2003 Revised Papers. ed. / Jiming Liu; Yiu-ming Cheung; Hujun Yin. 1st. ed. Berlin, Heidelberg: Springer, 2003. p. 35-42 (Lecture Notes in Computer Science; Vol. 2690), (International Conference on Intelligent Data Engineering and Automated Learning).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Agent Compromises in Distributed Problem Solving

AU - Tang, Yi

AU - Liu, Jiming

AU - Jin, Xiaolong

PY - 2003/7/29

Y1 - 2003/7/29

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

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

KW - Agent Compromises

KW - Distributed Constraint Satisfaction Problem

KW - Graph Coloring Problem

KW - Distributed GCP Solving

UR - http://www.scopus.com/inward/record.url?scp=35048823419&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-45080-1_5

DO - 10.1007/978-3-540-45080-1_5

M3 - Conference proceeding

AN - SCOPUS:35048823419

SN - 9783540405504

T3 - Lecture Notes in Computer Science

SP - 35

EP - 42

BT - Intelligent Data Engineering and Automated Learning

A2 - Liu, Jiming

A2 - Cheung, Yiu-ming

A2 - Yin, Hujun

PB - Springer

CY - Berlin, Heidelberg

T2 - 4th International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2003

Y2 - 21 March 2003 through 23 March 2003

ER -

Tang Y, Liu J, Jin X. Agent Compromises in Distributed Problem Solving. In Liu J, Cheung Y, Yin H, editors, Intelligent Data Engineering and Automated Learning: 4th International Conference, IDEAL 2003 Hong Kong, China, March 21–23, 2003 Revised Papers. 1st ed. Berlin, Heidelberg: Springer. 2003. p. 35-42. (Lecture Notes in Computer Science). (International Conference on Intelligent Data Engineering and Automated Learning). doi: 10.1007/978-3-540-45080-1_5

Agent Compromises in Distributed Problem Solving

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this