資源制約に束縛されない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.
論文 | ランダム
- 地理資料 オランダにおける越境地域連携の展開--独蘭国境地帯に注目して
- Long-term Psychosocial Outcomes in Children and Adolescents with Congenital Heart Disease, and in Their Parents : Rotterdam Follow-up Studies
- 「日本型社会住宅」の可能性--オランダの住宅政策を踏まえて (特集 居住の貧困化プロセスに抗する)
- Geomorphological Studies of Southern Part of Ganjam Coast, Orissa, India
- The Psychosocial Consequences of a Congenital Heart Disease in Adult Life : Young Female Patients at Risk