Title | ||
---|---|---|
Resource constrained distributed constraint optimization using resource constraint free pseudo-tree |
Abstract | ||
---|---|---|
The Distributed Constraint Optimization Problem (DCOP) is a fundamental formalism for multi-agent cooperation. A dedicated framework called Resource Constrained DCOP (RCDCOP) has recently been proposed. RCDCOP models objective functions and resource constraints separately. A resource constraint is an n-ary constraint that represents the limit on the number of resources of a given type available to agents. Previous research addressing RCDCOPs employs the Adopt algorithm, which is a basic solver for DCOPs. In this paper we propose another version of the Adopt algorithm for RCDCOP using a pseudo-tree that is generated ignoring resource constraints. The key ideas of our work are as follows: (i) The pseudo-tree is generated ignoring resource constraints. (ii) Virtual variables are introduced, representing the usage of resources. These virtual variables are used to share resources among sub-trees. These ideas are used to extend Adopt. The proposed method reduces the previous limitations in the construction of RCDCOP pseudo-trees. The efficiency of our technique depends on the class of problems being considered, and we describe the obtained experimental results. |
Year | DOI | Venue |
---|---|---|
2008 | 10.5555/1402821.1402884 | AAMAS (3) |
Keywords | Field | DocType |
constraint optimization,resource constraint free pseudo-tree,virtual variable,previous limitation,rcdcop model,rcdcop pseudo-trees,previous research,resource constrained dcop,resource constraint,adopt algorithm,n-ary constraint,share resource,multi agent systems | Constraint satisfaction,Local consistency,Mathematical optimization,Computer science,Constraint programming,Theoretical computer science,Constraint satisfaction problem,Distributed constraint optimization,Constraint logic programming,Binary constraint,Hybrid algorithm (constraint satisfaction),Distributed computing | Conference |
Citations | PageRank | References |
1 | 0.35 | 6 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Toshihiro Matsui | 1 | 380 | 62.51 |
Marius C. Silaghi | 2 | 375 | 47.09 |
Katsutoshi Hirayama | 3 | 472 | 44.79 |
Makoto Yokoo | 4 | 3632 | 421.99 |
Hirohsi Matsuo | 5 | 13 | 1.42 |