The distributed constraint satisfaction problem: formalization and algorithms Export

@article{citeulike:906122, abstract = {We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems}, author = {Yokoo, M. and Durfee, E. H. and Ishida, T. and Kuwabara, K.}, booktitle = {Knowledge and Data Engineering, IEEE Transactions on}, citeulike-article-id = {906122}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/69.729707}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=729707}, doi = {10.1109/69.729707}, journal = {Knowledge and Data Engineering, IEEE Transactions on}, keywords = {constraints}, number = {5}, pages = {673--685}, posted-at = {2006-10-19 18:12:37}, priority = {4}, title = {The distributed constraint satisfaction problem: formalization and algorithms}, url = {http://dx.doi.org/10.1109/69.729707}, volume = {10}, year = {1998} }

TY - JOUR ID - citeulike:906122 L3 - citeulike-article-id:906122 N2 - We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems IS - 5 JF - Knowledge and Data Engineering, IEEE Transactions on EP - 685 TI - The distributed constraint satisfaction problem: formalization and algorithms VL - 10 T2 - Knowledge and Data Engineering, IEEE Transactions on SP - 673 KW - constraints AU - Yokoo, M AU - Durfee, EH AU - Ishida, T AU - Kuwabara, K PY - 1998/// UR - http://dx.doi.org/10.1109/69.729707 ER -