Algorithms for Distributed Constraint Satisfaction: A Review Export

@article{yokoo00a, abstract = {When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to nd a consistent combination of actions that satis es these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs. This paper gives an overview of the existing research on distributed CSPs. First, we briefly describe the problem formalization and algorithms of normal, centralized CSPs. Then, we show the problem formalization and several MAS application problems of distributed CSPs. Furthermore, we describe a series of algorithms for solving distributed CSPs, i.e., the asynchronous backtracking, the asynchronous weak-commitment search, the distributed breakout, and distributed consistency algorithms. Finally, we show two extensions of the basic problem formalization of distributed CSPs, i.e., handling multiple local variables, and dealing with over-constrained problems.}, author = {Yokoo, Makoto and Hirayama, Katsutoshi}, citeulike-article-id = {1090245}, citeulike-linkout-0 = {http://jmvidal.cse.sc.edu/library/yokoo00a.pdf}, doi = {10.1023/A:1010078712316}, journal = {Autonomous Agents and Multi-Agent Systems}, keywords = {agent, dcsp, multiagent, survey}, number = {2}, pages = {185--207}, posted-at = {2007-02-06 08:52:22}, priority = {2}, title = {Algorithms for Distributed Constraint Satisfaction: A Review}, url = {10.1023/A:1010078712316}, volume = {3}, year = {2000} }

TY - JOUR ID - yokoo00a L3 - citeulike-article-id:1090245 N2 - When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to nd a consistent combination of actions that satis es these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs. This paper gives an overview of the existing research on distributed CSPs. First, we briefly describe the problem formalization and algorithms of normal, centralized CSPs. Then, we show the problem formalization and several MAS application problems of distributed CSPs. Furthermore, we describe a series of algorithms for solving distributed CSPs, i.e., the asynchronous backtracking, the asynchronous weak-commitment search, the distributed breakout, and distributed consistency algorithms. Finally, we show two extensions of the basic problem formalization of distributed CSPs, i.e., handling multiple local variables, and dealing with over-constrained problems. IS - 2 JF - Autonomous Agents and Multi-Agent Systems EP - 207 TI - Algorithms for Distributed Constraint Satisfaction: A Review VL - 3 SP - 185 KW - agent KW - dcsp KW - multiagent KW - survey AU - Yokoo, Makoto AU - Hirayama, Katsutoshi PY - 2000/// UR - http://jmvidal.cse.sc.edu/library/yokoo00a.pdf ER -