Distributed Search Methods for Quantified Distributed Constraint Optimization Problem
スポンサーリンク
概要
- 論文の詳細を見る
Distributed Constraint Optimization problems (DCOPs) have been studied as a fundamental model of multi-agent cooperation. In traditional DCOPs, all agents cooperate to optimize the sum of their cost functions. However, in practical systems some agents may desire to select the value of their variables without cooperation. In special cases, such agents may take the values with the worst impact on the quality of the result reachable by the optimization process. Similar classes of problems have been studied as Quantified (Distributed) Constraint Problems, where the variables of the CSP have existential/universal quantifiers. All constraints should be satisfied independently of the value taken by universal variables. In this paper, a Quantified Distributed Constraint Optimization problem (QDCOP) that extends the framework of DCOPs is presented. We apply existential/universal quantifiers to distinct uncooperative variables. A universally quantified variable is left unassigned by the optimization as the result has to hold when it takes any value from its domain, while an existentially quantified variable takes exactly one of its values for each context. We consider that the QDCOP applies the concept of game tree search to DCOP. If the original problem is a minimization problem, agents that own universally quantified variables may intend to maximize the cost value in the worst case. Other agents normally intend to optimize the minimizing problems. Therefore, only the bounds, especially the upper bounds, of the optimal value are guaranteed. The purpose of the new class of problems is to compute such bounds, as well as to compute sub-optimal solutions. For the QDCOP, we propose solution methods that are based on min-max/alpha-beta and ADOPT algorithms.
著者
-
松井 俊浩
名古屋工業大学
-
松尾 啓志
名古屋工業大学
-
平山 勝敏
神戸大学大学院海事科学研究科
-
横尾 真
九州大学大学院システム情報科学府
-
松尾 啓志
名古屋工業大学大学院工学研究科
-
Silaghi Marius
フロリダ工科大学
-
横尾 真
九州大学大学院 システム情報科学府
関連論文
- 4D-4 制約最適化・分散制約最適化問題における半正定値計画法の適用の検討(人工知能(2),一般セッション,人工知能と認知科学)
- ヒステリシス署名による改竄防止機構を備えたログ用ファイルシステムの提案(セッション5-A:不正アクセス対策(1))
- システムコールとライブラリ関数の監視による侵入防止システムの実現(セキュリティ)
- システムコールの実行順と実行位置に基づく侵入検知システムの実現(OS-2 : セキュリティ)
- FPGAを用いた制約最適化問題の解法の検討 (ディペンダブルコンピューティング)
- FPGAを用いた制約最適化問題の解法の検討 (コンピュータシステム)
- 分散制約最適化手法を適用した協調カメラ網アルゴリズムと実装 (ヒューマン情報処理)
- 分散制約最適化手法を適用した協調カメラ網アルゴリズムと実装 (パターン認識・メディア理解)
- 1G-1 出欠データと学習データを用いた学生の修学傾向分析(教育支援システム・教育実践,一般セッション,コンピュータと人間社会)
- D-8-10 制約最適化問題への半正定値計画法の適用についての一検討(D-8. 人工知能と知識処理,一般セッション)
- RM-002 確率的な分散制約最適化手法を用いた分散カメラ資源割り当て手法の実装(ユビキタス・モバイルコンピューティング,査読付き論文)
- RL-001 ライブラリ関数毎のシステムコール監視による侵入検知システムの開発(ネットワーク・セキュリティ,査読付き論文)
- C-018 A new File Transfer Protocol for a Hybrid Cluster-based File System
- A-008 Erlangを用いたマルチエージェントシミュレーションのための基礎的研究(モデル・アルゴリズム・プログラミング,一般論文)
- RC-010 自動メモ化プロセッサにおけるアドレス比較削減手法(ハードウェア・アーキテクチャ,査読付き論文)
- RC-009 自動メモ化プロセッサにおける再利用オーバヘッド削減(ハードウェア・アーキテクチャ,査読付き論文)
- RA-004 ループレス画像処理記述言語の提案と実装(モデル・アルゴリズム・プログラミング,査読付き論文)
- 複数スレッドを用いた自動メモ化プロセッサのオーバヘッド削減手法(ARC-7:マルチコア2,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- DHTを用いた双方向匿名通信路の提案
- 分散制約最適化問題へのソフトアーク整合の適用
- IUE(画像理解用標準ソフトウェア)とCalibrated Image Databaseの現状
- D-8-14 制約最適化問題のハードウェア解法のための処理要素の基礎検討(D-8.人工知能と知識処理,一般セッション)
- 拡張フーリエ変換法によるオプティカルフロー算出手法
- A-7-14 ファイル移動を制限する情報漏洩防止システム(A-7. 情報セキュリティ,一般セッション)
- 解像度調整機能を備える並列動画像処理ライブラリRaVioliの実装
- HMMを用いた動画像注目領域フィルタリング
- クラスタリングを用いたホルター心電図波形分類
- スマートカード認証履歴を用いた位置情報の取得とそれに基づく学内ソーシャルネットワークサービス
- 範囲検索と複数属性のデータの処理に適応した分散データストア
- 複数イタレーションの一括再利用による並列事前実行の高速化
- FPGAを用いた制約最適化問題の解法の検討
- FPGAを用いた制約最適化問題の解法の検討
- FPGAを用いた制約最適化問題の解法の検討
- FPGAを用いた制約最適化問題の解法の検討
- IUE(画像理解用標準ソフトウェア)とCalibrated Image Databaseの現状
- N-011 名古屋工業大学におけるMoodleの構築と運用(N分野:教育・人文科学)
- 分散制約最適化手法を適用した協調カメラ網アルゴリズムと実装(一般,顔・人物・ジェスチャ・行動)
- 高速ディジタル回線を用いた遠隔医療情報システム実験
- 名古屋工業大学情報基盤センターの紹介
- 動画像処理ライブラリRaVioliにおける領域別処理量調整の実現(2010年並列/分散/協調処理に関する『金沢』サマー・ワークショップSWoPP2010)
- GPU及びCell/B.E.に対応した解像度非依存型動画像処理ライブラリRaVioliの提案と実装(2010年並列/分散/協調処理に関する『金沢』サマー・ワークショップSWoPP2010)
- ライブラリ関数呼び出し監視による侵入防止システムの実現
- 不正入力データ除去と関数戻りアドレス保護によるself-healingシステムの実現
- 侵入防止システムにおける動作規則保護機構の開発
- 分散制約最適化問題に基づく提携構造形成問題
- 敵対者に対応する協調問題解決:限量記号付き分散制約充足問題
- 分散ラグランジュ緩和プロトコルにおける適応的な価格更新
- ディスク擬似書き込みと仮想マシンモニタによる機密情報閲覧作成環境の実現
- ディスク擬似書き込みと仮想マシンモニタによる機密情報閲覧作成環境の実現
- ディスク擬似書き込みと仮想マシンモニタによる機密情報閲覧作成環境の実現
- 範囲検索と複数属性のデータの処理に適応した分散データストア
- 分散型画像処理環境VIOS
- 多重解像度表現を用いた閉曲線画像の階層化マッチング手法
- 大規模ニューラルネット"OmbNET-II"
- ログエントリ数を考慮した LogTM のアボート対象選択手法とその評価
- ログエントリ数を考慮したLogTMのアボート対象選択手法とその評価
- 周囲環境照度変化にロバストな搬送部品の印字文字認識
- 不均一な表面反射率をもつ物体の3次元形状計測方式
- 表面反射率が不均一な物体の3次元形状計測
- 3H-2 学生の修学データを用いた修学指導支援システムの検討(教育学習支援システム,一般セッション,コンピュータと人間社会,情報処理学会創立50周年記念)
- FPGAを用いた制約最適化問題の解法の検討
- FPGAを用いた制約最適化問題の解法の検討
- FPGAを用いた制約最適化問題の解法の検討
- FPGAを用いた制約最適化問題の解法の検討
- 分散制約最適化手法を適用した協調カメラ網アルゴリズムと実装(一般,顔・人物・ジェスチャ・行動)
- 自動メモ化プロセッサを支援するプログラム変換手法の提案と実装
- データのアクセス頻度を考慮した動的負荷分散機構の Dynamo への適用
- データのアクセス頻度を考慮した動的負荷分散機構の Dynamo への適用
- データのアクセス頻度を考慮した動的負荷分散機構のDynamoへの適用
- データのアクセス頻度を考慮した動的負荷分散機構のDynamoへの適用
- 解像度非依存型動画像処理ライブラリ RaVioli の提案と実装
- 自動メモ化プロセッサにおける消費エネルギー制御
- 解像度非依存型動画像処理ライブラリの提案と実装
- I-063 解像度非依存型画像処理ライブラリの提案と実装(I分野:グラフィクス・画像)
- LC-005 自動メモ化プロセッサの消費エネルギー評価(ハードウェア・アーキテクチャ)
- 自動メモ化プロセッサの低消費エネルギー化(ARC-7 : 低消費電力アーキテクチャ,2007年並列/分散/協調処理に関する『旭川』サマー・ワークショップ(SWoPP旭川2007))
- 並列化および再利用によるGAの高速化(ARC-5 : マルチプロセッサ応用,2007年並列/分散/協調処理に関する『旭川』サマー・ワークショップ(SWoPP旭川2007))
- 分散ハッシュテーブルによるノード管理を行う匿名通信方式の設計と実装
- 分散ハッシュテーブルによるノード管理を行う匿名通信方式の設計と実装
- 分散ハッシュテーブルによるノード管理を行う匿名通信方式の設計と実装
- 分散ハッシュテーブルによるノード管理を行う匿名通信方式の設計と実装
- 確率的ルーティングアルゴリズムARHを用いた無線LAN環境におけるストリーミング配信実験(ユビキタスネットワーク,ITS,センサーネットワーク,アドホックネットワーク)
- 確率的ルーティングアルゴリズムARHを用いた無線LAN環境におけるストリーミング配信実験(ユビキタスネットワーク,ITS,センサーネットワーク,アドホックネットワーク)
- RF-004 階層化された分散制約充足/最適化手法を用いた分散センサ網における観測資源割り当ての検討(人工知能・ゲーム,査読付き論文)
- F-029 分散制約最適化手法を用いたコアロケーションスケジューリングへの適用(F分野:人工知能・ゲーム)
- LF-010 確率的な分散制約最適化手法を用いたセンサ網の資源割り当て手法の提案(人工知能・ゲーム)
- 擬似的な木を用いた分散制約最適化手法のための木の幅を考慮した空間複雑度の削減(分散協調とエージェント)
- 分散制約最適化問題の非同期分散探索における上下界の導出と学習を用いた効率改善手法(分散協調とエージェント)
- 分散制約充足問題の観測資源割当てへの適用
- D-8-1 多重解像度的な状態空間を用いた領域選択手法
- 多体軌跡推定における対応付け・軌跡推定のための協調アルゴリズム
- 分散制約最適化問題の解法Max-Sumにおける評価関数の動的な変更手法
- 制約充足や最適化に関するエージェント研究の最近の動向(エージェント)
- Distributed Search Methods for Quantified Distributed Constraint Optimization Problem
- RF-002 分散ラグランジュ緩和プロトコルにおける局所情報にもとづく価格更新の効果(学習・最適化,F分野:人工知能・ゲーム)
- RF-003 Action-GDLにおける集中処理化と情報漏洩を考慮するJunction-Treeの変形手法(学習・最適化,F分野:人工知能・ゲーム)
- 可変な離散化単位を用いる資源制約付き分散制約最適化問題の検討(「持続可能エネルギー社会とAI」及び一般)
- RF-003 分散制約最適化問題の異なる非厳密解法の統合手法(F分野:人工知能・ゲーム)
- PRIMA 2012
- 制約充足や最適化に関するエージェント研究の最近の動向