Distributed constraint satisfaction for formalizing distributed problem solving

Makoto Yokoo; Toru Ishida; Edmund H. Durfee; Kazuhiro Kuwabara

doi:10.1109/ICDCS.1992.235101

Distributed constraint satisfaction for formalizing distributed problem solving

Makoto Yokoo, Toru Ishida, Edmund H. Durfee, Kazuhiro Kuwabara

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

238 Citations (Scopus)

Abstract

Viewing cooperative distributed problem solving (CDPS) as distributed constraint satisfaction provides a useful formalism for characterizing CDPS techniques. This formalism and algorithms for solving distributed constraint satisfaction problems (DCSPs) are compared. A technique called asynchronous backtracking that allows agents to act asynchronously and concurrently, in contrast to the traditional sequential backtracking techniques used in constraint satisfaction problems, is presented. Experimental results show that solving DCSPs in a distributed fashion is worthwhile when the problems solved by individual agents are loosely coupled.

Original language	English
Title of host publication	Proceedings - 12th International Conference on Distributed Computing Systems, ICDCS 1992
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	614-621
Number of pages	8
ISBN (Electronic)	0818628650
DOIs	https://doi.org/10.1109/ICDCS.1992.235101
Publication status	Published - 1992
Externally published	Yes
Event	12th International Conference on Distributed Computing Systems, ICDCS 1992 - Yokohama, Japan Duration: 1992 Jun 9 → 1992 Jun 12

Publication series

Name	Proceedings - International Conference on Distributed Computing Systems
Volume	1992-June

Conference

Conference	12th International Conference on Distributed Computing Systems, ICDCS 1992
Country/Territory	Japan
City	Yokohama
Period	92/6/9 → 92/6/12

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1109/ICDCS.1992.235101

Cite this

Yokoo, M., Ishida, T., Durfee, E. H., & Kuwabara, K. (1992). Distributed constraint satisfaction for formalizing distributed problem solving. In Proceedings - 12th International Conference on Distributed Computing Systems, ICDCS 1992 (pp. 614-621). Article 235101 (Proceedings - International Conference on Distributed Computing Systems; Vol. 1992-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDCS.1992.235101

Distributed constraint satisfaction for formalizing distributed problem solving. / Yokoo, Makoto; Ishida, Toru; Durfee, Edmund H. et al.
Proceedings - 12th International Conference on Distributed Computing Systems, ICDCS 1992. Institute of Electrical and Electronics Engineers Inc., 1992. p. 614-621 235101 (Proceedings - International Conference on Distributed Computing Systems; Vol. 1992-June).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Yokoo, M, Ishida, T, Durfee, EH & Kuwabara, K 1992, Distributed constraint satisfaction for formalizing distributed problem solving. in Proceedings - 12th International Conference on Distributed Computing Systems, ICDCS 1992., 235101, Proceedings - International Conference on Distributed Computing Systems, vol. 1992-June, Institute of Electrical and Electronics Engineers Inc., pp. 614-621, 12th International Conference on Distributed Computing Systems, ICDCS 1992, Yokohama, Japan, 92/6/9. https://doi.org/10.1109/ICDCS.1992.235101

Yokoo M, Ishida T, Durfee EH, Kuwabara K. Distributed constraint satisfaction for formalizing distributed problem solving. In Proceedings - 12th International Conference on Distributed Computing Systems, ICDCS 1992. Institute of Electrical and Electronics Engineers Inc. 1992. p. 614-621. 235101. (Proceedings - International Conference on Distributed Computing Systems). doi: 10.1109/ICDCS.1992.235101

Yokoo, Makoto ; Ishida, Toru ; Durfee, Edmund H. et al. / Distributed constraint satisfaction for formalizing distributed problem solving. Proceedings - 12th International Conference on Distributed Computing Systems, ICDCS 1992. Institute of Electrical and Electronics Engineers Inc., 1992. pp. 614-621 (Proceedings - International Conference on Distributed Computing Systems).

@inproceedings{20ecfe20eade449a9ec1e3a27a03d2bf,

title = "Distributed constraint satisfaction for formalizing distributed problem solving",

abstract = "Viewing cooperative distributed problem solving (CDPS) as distributed constraint satisfaction provides a useful formalism for characterizing CDPS techniques. This formalism and algorithms for solving distributed constraint satisfaction problems (DCSPs) are compared. A technique called asynchronous backtracking that allows agents to act asynchronously and concurrently, in contrast to the traditional sequential backtracking techniques used in constraint satisfaction problems, is presented. Experimental results show that solving DCSPs in a distributed fashion is worthwhile when the problems solved by individual agents are loosely coupled.",

author = "Makoto Yokoo and Toru Ishida and Durfee, {Edmund H.} and Kazuhiro Kuwabara",

note = "Publisher Copyright: {\textcopyright} 1992 IEEE.; 12th International Conference on Distributed Computing Systems, ICDCS 1992 ; Conference date: 09-06-1992 Through 12-06-1992",

year = "1992",

doi = "10.1109/ICDCS.1992.235101",

language = "English",

series = "Proceedings - International Conference on Distributed Computing Systems",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "614--621",

booktitle = "Proceedings - 12th International Conference on Distributed Computing Systems, ICDCS 1992",

}

TY - GEN

T1 - Distributed constraint satisfaction for formalizing distributed problem solving

AU - Yokoo, Makoto

AU - Ishida, Toru

AU - Durfee, Edmund H.

AU - Kuwabara, Kazuhiro

PY - 1992

Y1 - 1992

N2 - Viewing cooperative distributed problem solving (CDPS) as distributed constraint satisfaction provides a useful formalism for characterizing CDPS techniques. This formalism and algorithms for solving distributed constraint satisfaction problems (DCSPs) are compared. A technique called asynchronous backtracking that allows agents to act asynchronously and concurrently, in contrast to the traditional sequential backtracking techniques used in constraint satisfaction problems, is presented. Experimental results show that solving DCSPs in a distributed fashion is worthwhile when the problems solved by individual agents are loosely coupled.

AB - Viewing cooperative distributed problem solving (CDPS) as distributed constraint satisfaction provides a useful formalism for characterizing CDPS techniques. This formalism and algorithms for solving distributed constraint satisfaction problems (DCSPs) are compared. A technique called asynchronous backtracking that allows agents to act asynchronously and concurrently, in contrast to the traditional sequential backtracking techniques used in constraint satisfaction problems, is presented. Experimental results show that solving DCSPs in a distributed fashion is worthwhile when the problems solved by individual agents are loosely coupled.

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

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

U2 - 10.1109/ICDCS.1992.235101

DO - 10.1109/ICDCS.1992.235101

M3 - Conference contribution

AN - SCOPUS:85043435920

T3 - Proceedings - International Conference on Distributed Computing Systems

SP - 614

EP - 621

BT - Proceedings - 12th International Conference on Distributed Computing Systems, ICDCS 1992

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 12th International Conference on Distributed Computing Systems, ICDCS 1992

Y2 - 9 June 1992 through 12 June 1992

ER -

Distributed constraint satisfaction for formalizing distributed problem solving

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this