Name
Title | ||
|---|---|---|
Cooperative problem solving against adversary: quantified distributed constraint satisfaction problem |
Abstract | ||
|---|---|---|
In this paper, we extend the traditional formalization of distributed constraint satisfaction problems (DisCSP) to a quantified DisCSP. A quantified DisCSP includes several universally quantified variables, while all of the variables in a traditional DisCSP are existentially quantified. A universally quantified variable represents a choice of nature or an adversary. A quantified DisCSP formalizes a situation where a team of agents is trying to make a robust plan against nature or an adversary. In this paper, we present the formalization of such a quantified DisCSP and develop an algorithm for solving it by generalizing the asynchronous backtracking algorithm used for solving a DisCSP. In this algorithm, agents communicate a value assignment called a good in addition to the nogood used in asynchronous back-tracking. Interestingly, the procedures executed by an adversarial/cooperative agent for good/nogood are completely symmetrical. Furthermore, we develop a method that improves this basic algorithm. Experimental evaluation results illustrate that we observe an easy-hard-easy transition by changing the tightness of the constraints, while very loose problem instances are relatively hard. The modification of the basic algorithm is also effective and reduces the cycles about 25% for the hardest problem instances. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.5555/1838206.1838310 | Transactions of The Japanese Society for Artificial Intelligence |
Keywords | Field | DocType |
loose problem instance,hardest problem instance,basic algorithm,traditional formalization,cooperative agent,asynchronous back-tracking,asynchronous backtracking algorithm,constraint satisfaction problem,easy-hard-easy transition,traditional discsp,cooperative problem | Cooperative problem solving,Asynchronous communication,Mathematical optimization,Generalization,Computer science,Constraint satisfaction problem,Adversary,Backtracking,Distributed computing | Conference |
Citations | PageRank | References |
5 | 0.53 | 11 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Satomi Baba | 1 | 8 | 0.97 |
| Atsushi Iwasaki | 2 | 292 | 31.81 |
| Makoto Yokoo | 3 | 3632 | 421.99 |
| Marius C. Silaghi | 4 | 375 | 47.09 |
| Katsutoshi Hirayama | 5 | 472 | 44.79 |
| Toshihiro Matsui | 6 | 380 | 62.51 |