資源制約に束縛されないpseudo-treeを用いた資源制約付き分散制約最適化問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
Cooperative problem solving with shared resources is important in practical multi-agent systems. Resource constraints are necessary to handle practical problems such as distributed task scheduling with limited resource availability. As a fundamental formalism for multi-agent cooperation, the Distributed Constraint Optimization Problem (DCOP) has been investigated. With DCOPs, the agent states and the relationships between agents are formalized into a constraint optimization problem. However, in the original DCOP framework, constraints for resources that are consumed by teams of agents are not well supported. A framework called Resource Constrained Distributed Constraint Optimization Problem (RCDCOP) has recently been proposed. In RCDCOPs, a limit on resource usage is represented as an n-ary constraint. Previous research addressing RCDCOPs employ a pseudo-tree based solver. The pseudo-tree is an important graph structure for constraint networks. A pseudo-tree implies a partial ordering of variables. However, n-ary constrained variables, which are placed on a single path of the pseudo-tree, decrease efficiency of the solver. We propose another method using (i) a pseudo-tree that is generated ignoring resource constraints and (ii) virtual variables representing the usage of resources. However the virtual variables increase search space. To improve pruning efficiency of search, (iii) we apply a set of upper/lower bounds that are inferred from resource constraints. The efficiency of the proposed method is evaluated by experiment.
論文 | ランダム
- 都市におけるアメニティ評価に関する研究 : その6・II 住みつき態度とアメニティ評価 : 都市計画
- 都市におけるアメニティ評価に関する研究 : その5・I 住みつき態度と社会的環境 : 都市計画
- 都市におけるアメニティ評価に関する研究(その4) : バス通勤とアメニティ : 都市計画
- 都市におけるアメニティ評価に関する研究(その3) : 通勤交通手段とアメニティ : 都市計画
- 都市におけるアメニティ評価に関する研究 : その2 適合性分析と.アメニティ評価