Resource constrained distributed constraint optimization with virtual variables

Toshihiro Matsui, Hiroshi Matsuo, Katsutoshi Hirayama, Marius Silaghi, Makoto Yokoo

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

16 被引用数 (Scopus)

抄録

Cooperative problem solving with resource constraints are important in practical multi-agent systems. Resource constraints are necessary to handle practical problems including distributed task scheduling with limited resource availability. 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 an efficient solver for DCOPs. An important graph structure for Adopt is the pseudo-tree for constraint networks. A pseudo-tree implies a partial ordering of variables. In this variable ordering, n-ary constrained variables are placed on a single path of the tree. Therefore, resource constraints that have large arity augment the depth of the pseudo-tree. This also reduces the parallelism, and therefore the efficiency of Adopt. In this paper we propose another version of the Adopt algorithm for RCDCOP using a pseudo-tree that is generated ignoring resource constraints. The proposed method reduces the previous limitations in the construction of RCDCOP pseudo-trees. 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. However, the addition of virtual variables increases the search space. To handle this problem, influence of placement of virtual variables/resources constraints in the pseudo tree is considered. Moreover the search is pruned using the bounds defined by the resource constraints if possible. These ideas are used to extend Adopt. The efficiency of our technique depends on the class of problems being considered, and we describe the obtained experimental results.

本文言語英語
ホスト出版物のタイトルAAAI-08/IAAI-08 Proceedings - 23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference
ページ120-125
ページ数6
出版ステータス出版済み - 2008
外部発表はい
イベント23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference, AAAI-08/IAAI-08 - Chicago, IL, 米国
継続期間: 7月 13 20087月 17 2008

出版物シリーズ

名前Proceedings of the National Conference on Artificial Intelligence
1

その他

その他23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference, AAAI-08/IAAI-08
国/地域米国
CityChicago, IL
Period7/13/087/17/08

!!!All Science Journal Classification (ASJC) codes

  • ソフトウェア
  • 人工知能

フィンガープリント

「Resource constrained distributed constraint optimization with virtual variables」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル