分散制約最適化

分散制約最適化（DCOPまたはDisCOP）は、制約最適化の分散版です。DCOPは、エージェントのグループが変数の集合に対して分散的に値を選択し、変数に対する制約集合のコストが最小化されるような問題です。

分散制約充足とは、異なる参加者（エージェント）によって認識され、強制される制約を用いて問題を記述する枠組みです。制約は、定義済みのドメインを持ついくつかの変数に記述され、異なるエージェントによって同じ値が割り当てられる必要があります。

このフレームワークで定義された問題は、このフレームワーク用に設計された任意のアルゴリズムによって解決できます。

このフレームワークは1980年代には様々な名称で使用されていました。現在の名称で初めて使用されたのは1990年です。

定義

DCOP

DCOP問題の主な構成要素は、エージェントと変数です。重要なのは、各変数がエージェントによって所有されていることです。これが問題を分散化するのです。正式には、DCOPはタプル であり、以下のようになります。 ⟨あ、V、D、f、α、η⟩{\displaystyle \langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle }

  • あ{\displaystyle A}はエージェントの集合です。{1つの1、…、1つの|あ|}{\displaystyle \{a_{1},\dots ,a_{|A|}\}}
  • V{\displaystyle V}は変数の集合です。{v1、v2、…、v|V|}{\displaystyle \{v_{1},v_{2},\dots ,v_{|V|}\}}
  • D{\displaystyle {\mathfrak {D}}}は変数領域の集合、であり、各 は変数 の可能な値を含む有限集合です。 {D1、D2、…、D|V|}{\displaystyle \{D_{1},D_{2},\dots ,D_{|V|}\}}Dj∈D{\displaystyle D_{j}\in {\mathfrak {D}}}vj{\displaystyle v_{j}}
    • 2 つの値 (例: 0 または 1) のみが含まれる場合、バイナリ変数と呼ばれます。Dj∈D{\displaystyle D_{j}\in {\mathfrak {D}}}vj{\displaystyle v_{j}}
  • f{\displaystyle f}はコスト関数である。これは、あらゆる可能な部分割り当てをコストにマッピングする関数[ 1 ]である。通常、 の値はゼロ以外の値はほとんどなく、ゼロ以外の値が割り当てられた組のリストとして表現される。そのような組はそれぞれ制約と呼ばれる。この集合内の各制約は、変数の可能な割り当てごとに実数値を割り当てる関数である。いくつかの特殊な制約には以下がある。 f:⋃S⊆V×vj∈SDj→R{\displaystyle f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R} }f{\displaystyle f}C{\displaystyle C}fC:D1×⋯×Dけ→R{\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} }
    • 単項制約- 単一の変数に対する制約、つまり、いくつかの に対する制約。fC:Dj→R{\displaystyle f_{C}:D_{j}\to \mathbb {R} }vj∈V{\displaystyle v_{j}\in V}
    • バイナリ制約- 2 つの変数に対する制約、つまり、ある に対して。fC:Dj1×Dj2→R{\displaystyle f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R} }vj1、vj2∈V{\displaystyle v_{j_{1}},v_{j_{2}}\in V}
  • α{\displaystyle \alpha}は所有権関数です。これは、各変数をそれに関連付けられたエージェントにマッピングする関数です。 は、変数 がエージェント に「属する」ことを意味します。これは、変数 の値を割り当てるのはエージェントの責任であることを意味します。 は必ずしも単射 とは限らないことに注意してください。つまり、1つのエージェントが複数の変数を所有する場合もあります。また、必ずしも全射とも限らないことに注意してください。つまり、変数を所有しないエージェントも存在する場合もあります。α:V→あ{\displaystyle \alpha :V\to A}α（vj）↦1つの私{\displaystyle \alpha (v_{j})\mapsto a_{i}}vj{\displaystyle v_{j}}1つの私{\displaystyle a_{i}}1つの私{\displaystyle a_{i}}vj{\displaystyle v_{j}}α{\displaystyle \alpha}
  • η{\displaystyle \eta}は目的関数です。これは、すべての可能な変数割り当てに対する個々のコストをすべて集計する演算子です。これは通常、合計によって行われます。f{\displaystyle f}η（f）↦∑s∈⋃S⊆V×vj∈SDjf（s）。{\displaystyle \eta (f)\mapsto \sum _{s\in \bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}}f(s).}

DCOP の目的は、各エージェントに関連付けられた変数に値を割り当てて、指定された変数の割り当てを最小化または最大化することです。 η（f）{\displaystyle \eta (f)}

課題

値の割り当ては、ドメインの要素である のペアです。 （vj、dj）{\displaystyle (v_{j},d_{j})}dj{\displaystyle d_{j}}Dj{\displaystyle D_{j}}

部分的な割り当てとは、それぞれが最大で1回出現する値の割り当てのセットです。これはコンテキストとも呼ばれます。これは、DCOP内の変数をそれぞれの現在の値にマッピングする関数と考えることができます。 コンテキストは本質的に部分的な解であり、問​​題内のすべての変数の値を含む必要はないことに注意してください。したがって、はエージェントがまだ変数に値を割り当てていないことを意味します。この表現を考えると、関数の「ドメイン」（つまり、入力値の集合）は、DCOPのすべての可能なコンテキストの集合と考えることができます。したがって、この記事の残りの部分では、コンテキスト（つまり、関数）という概念を関数への入力として使用します。 vj{\displaystyle v_{j}}t:V→（D∈D）∪{∅}。{\displaystyle t:V\to (D\in {\mathfrak {D}})\cup \{\emptyset \}.}t（v私）↦∅{\displaystyle t(v_{i})\mapsto \emptyset }α(vi){\displaystyle \alpha (v_{i})}vi{\displaystyle v_{i}}ft{\displaystyle t}f{\displaystyle f}

完全代入とは、各変数が正確に一度だけ出現する代入、つまりすべての変数が代入される代入です。これはDCOPの 解とも呼ばれます。vj{\displaystyle v_{j}}

最適解とは、目的関数が最適化される（つまり、問題の種類に応じて最大化または最小化される）完全な割り当てです。 η(f){\displaystyle \eta (f)}

例題

さまざまなドメインのさまざまな問題を DCOP として提示できます。

分散グラフ彩色

グラフの色付け問題は次のとおりです。グラフ と色のセットが与えられた場合、同じ色を持つ隣接頂点の数が最小になるように 、各頂点、に色を割り当てます。G=⟨N,E⟩{\displaystyle G=\langle N,E\rangle }C{\displaystyle C}n⊂N{\displaystyle n\subset N}c≤C{\displaystyle c\leq C}

DCOP では、頂点ごとに 1 つのエージェントが割り当てられ、各エージェントは関連付けられた色を決定します。各エージェントは、関連付けられたドメインが である単一の変数を持ちます（ 考えられる色ごとに 1 つのドメイン値があります）。各頂点 には、ドメイン を持つ変数が 1 つあります。隣接する頂点 の各ペアでは、関連付けられた変数の両方に同じ色が割り当てられている場合、コスト 1 の制約があります。したがって、目標は を最小化することです。 |C|{\displaystyle |C|}ni≤N{\displaystyle n_{i}\leq N}vi∈V{\displaystyle v_{i}\in V}Di=C{\displaystyle D_{i}=C}⟨ni,nj⟩∈E{\displaystyle \langle n_{i},n_{j}\rangle \in E}(∀c⊆C:f(⟨vi,c⟩,⟨vj,c⟩)↦1).{\displaystyle (\forall c\subseteq C:f(\langle v_{i},c\rangle ,\langle v_{j},c\rangle )\mapsto 1).}η(f){\displaystyle \eta (f)}

分散型多重ナップサック問題

ナップザック問題の分散多重版は以下のとおりです。体積の異なるアイテムの集合と容量の異なるナップザックの集合が与えられたとき、オーバーフロー量が最小となるように各アイテムをナップザックに割り当てます。アイテムの集合を 、ナップザックの集合を 、アイテムとその体積を対応付ける関数を 、ナップザックとその容量を対応付ける関数を とします。 I{\displaystyle I}K{\displaystyle K}s:I→N{\displaystyle s:I\to \mathbb {N} }c:K→N{\displaystyle c:K\to \mathbb {N} }

この問題をDCOPとしてエンコードするには、それぞれに対して、ドメインに関連付けられた変数を1つ作成します。次に、すべての可能なコンテキストに対して、コンテキストによってナップサックに割り当てられる重みの合計を表します。i∈I{\displaystyle i\in I}vi∈V{\displaystyle v_{i}\in V}Di=K{\displaystyle D_{i}=K}t{\displaystyle t}f(t)↦∑k∈K{0r(t,k)≤c(k),r(t,k)−c(k)otherwise,{\displaystyle f(t)\mapsto \sum _{k\in K}{\begin{cases}0&r(t,k)\leq c(k),\\r(t,k)-c(k)&{\text{otherwise}},\end{cases}}}r(t,k){\displaystyle r(t,k)}t{\displaystyle t}k{\displaystyle k}r(t,k)=∑vi∈t−1(k)s(i).{\displaystyle r(t,k)=\sum _{v_{i}\in t^{-1}(k)}s(i).}

分散アイテム割り当て問題

アイテム割り当て問題は以下の通りである。複数のエージェント間で分配する必要があるアイテムが複数存在する。各エージェントはアイテムに対して異なる評価を持つ。目標は、効用合計の最大化や羨望の最小化といった、ある全体目標を最適化することである。アイテム割り当て問題は、以下のようにDCOPとして定式化できる。[ 2 ]

  • 各エージェントiとアイテムjに対して、 2値変数v ijを追加します。エージェントがアイテムを取得した場合は変数の値が「1」、そうでない場合は「0」になります。この変数はエージェントiが所有します。
  • 各アイテムが最大 1 つのエージェントに与えられるという制約を表現するには、同じアイテムに関連する 2 つの異なる変数ごとにバイナリ制約を追加します。2 つの変数が同時に「1」の場合はコストが無限大になり、それ以外の場合はコストがゼロになります。
  • すべてのアイテムを割り当てる必要があるという制約を表現するには、各アイテムにn項制約 ( nはエージェントの数) を追加します。このアイテムに関連する変数がどれも "1" でない場合はコストが無限大になります。

その他のアプリケーション

DCOP は次のような他の問題にも適用されました。

  • モバイルセンサーの調整。
  • 会議とタスクのスケジュール。

アルゴリズム

DCOPアルゴリズムはいくつかの方法で分類できる: [ 3 ]

  • 完全性- 最適な解決策を見つける完全探索アルゴリズムと、局所最適解を見つけるローカル探索アルゴリズム。
  • 検索戦略- 最良優先検索または深さ優先の分岐限定検索。
  • エージェント間の同期- 同期または非同期。
  • エージェント間の通信- 制約グラフ内の近隣エージェントとのポイントツーポイント、またはブロードキャスト。
  • 通信トポロジ- チェーンまたはツリー。

たとえば、ADOPT は、最良優先検索、非同期同期、制約グラフ内の隣接エージェント間のポイントツーポイント通信、および制約ツリーを主要な通信トポロジとして使用します。

アルゴリズム名 導入年 メモリの複雑さメッセージ数 正確性（コンピュータサイエンス） /完全性（論理）実装
シンクBB [ 4 ]

同期分岐限定法

1997 完了だが遅い
非同期バックトラッキングを採用する[ 5 ]2003 多項式（または任意の空間[ 6 ]） 指数関数 実証済み リファレンス実装: Adopt 2006年9月16日アーカイブWayback Machine

DCOPolis ( GNU LGPL ) FRODO ( AGPL )

OptAPO非同期部分オーバーレイ[ 7 ]2004 多項式 指数関数 証明されているが、完全性の証明には疑問が呈されている[ 8 ]リファレンス実装：「OptAPO」。人工知能センター。SRIインターナショナル。2007年7月15日時点のオリジナルからアーカイブ。

DCOPolis ( GNU LGPL ); 開発中

DPOP分散擬似木最適化手順[ 9 ]2005 指数関数 リニア 実証済み リファレンス実装: FRODO ( AGPL )

DCOPolis ( GNU LGPL )

NCBBノーコミットメント分岐限定法[ 10 ]2006 多項式（または任意の空間[ 11 ]） 指数関数 実証済み リファレンス実装:非公開

DCOPolis ( GNU LGPL )

CFLコミュニケーションフリー学習[ 12 ]2013 リニア なし注: メッセージは送信されませんが、ローカル制約の充足に関する知識があることを前提としています。不完全

これらのDCOPアルゴリズムのハイブリッドも存在します。例えば、BnB-Adopt [ 3 ]はAdoptの探索戦略を最良優先探索から深さ優先の分岐限定探索に変更します。

非対称DCOP

非対称DCOPはDCOPの拡張であり、各制約のコストがエージェントごとに異なる場合がある。いくつかの応用例としては[ 13 ]が挙げられる。

  • イベントのスケジュール: 同じイベントに参加するエージェントは、イベントから異なる値を導き出す可能性があります。
  • スマートグリッド：負荷時間帯の電気料金の上昇は、さまざまな要因によって発生する可能性があります。

ADCOP を表現する 1 つの方法は、制約を関数として表現することです。 fC:D1×⋯×Dk→Rk{\displaystyle f_{C}:D_{1}\times \dots \times D_{k}\to \mathbb {R} ^{k}}

ここで、各制約には単一のコストではなく、コストのベクトル（制約に関与するエージェントごとに1つ）が存在します。各変数が異なるエージェントに属する場合、コストのベクトルの長さはkです。2つ以上の変数が同じエージェントに属する場合、コストのベクトルは短くなります。つまり、各変数ではなく、関与するエージェントごとに単一のコストが存在します。

ADCOPを解決するためのアプローチ

ADCOPを解く簡単な方法は、各制約を、関数 の和に等しい制約 に置き換えることです。しかし、この解法では、エージェントがコスト関数を明らかにする必要があります。プライバシーの観点から、これは望ましくないことがよくあります。[ 14 ] [ 15 ] [ 16 ]fC:D1×⋯×Dk→Rk{\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}}fC′:D1×⋯×Dk→R{\displaystyle f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R} }fC1+⋯+fCk{\displaystyle f_{C}^{1}+\cdots +f_{C}^{k}}

もう一つのアプローチは、プライベートイベントを変数として扱う（PEAV）と呼ばれる。[ 17 ]このアプローチでは、各変数は自身の変数に加えて、制約ネットワーク内の隣接する変数が持つすべての変数の「ミラー変数」も持つ。ミラー変数が元の変数と等しくなることを保証する追加の制約（コストは無限大）が設けられる。この方法の欠点は、変数と制約の数が元の変数よりもはるかに多くなり、実行時間が長くなることである。

3つ目のアプローチは、DCOP向けに開発された既存のアルゴリズムをADCOPフレームワークに適応させることです。これは、完全探索アルゴリズムと局所探索アルゴリズムの両方で行われてきました。[ 13 ]

戦略ゲームとの比較

ADCOP問題の構造は、ゲーム理論における同時ゲームの概念に似ています。どちらの場合も、変数（ゲーム理論では、変数とはエージェントの可能な行動または戦略）を制御するエージェントが存在します。どちらの場合も、異なるエージェントによる変数の選択は、各エージェントに異なる利得をもたらします。しかし、根本的な違いがあります。[ 13 ]

  • 同時ゲームにおいては、エージェントは利己的であり、それぞれが自身の効用を最大化（または自身のコストを最小化）しようとします。したがって、このような状況において追求できる最良の結果は均衡、つまりどのエージェントも一方的に自身の利得を増やすことができない状況です。
  • ADCOPでは、エージェントは協力的であるとみなされます。つまり、自身の効用が減少する場合でも、プロトコルに従って行動します。したがって、目標はより困難になります。つまり、効用の合計を最大化（またはコストの合計を最小化）することです。ナッシュ均衡は、この問題における局所最適解にほぼ相当しますが、ここでは大域最適解を求めています。

部分的な協力

エージェントが部分的に協力的である中間的なモデルもいくつか存在する。エージェントは、全体目標の達成に貢献するために自身の効用を低下させることを厭わないが、それは自身のコストが高すぎない場合に限る。部分的に協力的なエージェントの例としては、企業の従業員が挙げられる。従業員はそれぞれ、自身の効用を最大化したいと考える一方で、企業の成功にも貢献したいと考えている。したがって、負担が大きすぎない限り、他者を助けたり、企業に貢献する時間のかかる作業を行ったりすることにも積極的である。部分的に協力的なエージェントのモデルとしては、以下のものがある。[ 18 ]

  • 保証された個人的利益: エージェントは、自身の効用が非協力的な設定と少なくとも同じくらい高い場合、地球全体の利益のために行動することに同意します (つまり、最終結果は元の状態のパレート改善である必要があります)。
  • ラムダ協力：パラメータ が存在する。エージェントは、自身の効用が非協力的効用の倍以上である場合、地球全体の利益のために行動することに同意する。λ∈[0,1]{\displaystyle \lambda \in [0,1]}(1−λ){\displaystyle (1-\lambda )}

このような部分協力ADCOPを解くには、ADCOPアルゴリズムの適応が必要である。[ 18 ]

参照

注釈と参考文献

  1. ^ "" または "×" は直積を表します。×{\displaystyle \times }
  2. ^ Netzer, Arnon; Meisels, Amnon; Zivan, Roie (2016-03-01). 「資源配分のための分散羨望最小化」 .自律エージェントとマルチエージェントシステム. 30 (2): 364– 402. doi : 10.1007/s10458-015-9291-7 . ISSN 1387-2532 . S2CID 13834856 .  
  3. ^ a b Yeoh, William; Felner, Ariel; Koenig, Sven (2008)、「BnB-ADOPT: 非同期分岐限定DCOPアルゴリズム」、自律エージェントおよびマルチエージェントシステムに関する第7回国際合同会議論文集、第2巻、Ifaamas、pp.  591–8、ISBN 9780981738116
  4. ^平山克俊、横尾誠 (1997). 「分散部分制約充足問題」 . スモルカ, ゲルト (編).制約プログラミングの原理と実践-CP97 . コンピュータサイエンス講義ノート. 第1330巻. ベルリン, ハイデルベルク: シュプリンガー. pp.  222– 236. doi : 10.1007/BFb0017442 . ISBN 978-3-540-69642-1。
  5. ^ Adoptの初版は情報不足でした。Modi , Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo, Makoto (2003) 「分散制約最適化のための非同期完全手法」（PDF）を参照してください。自律エージェントとマルチエージェントシステムに関する第2回国際合同会議の議事録、ACM Press、pp.  161– 168。 2019年11月4日にオリジナル（PDF）からアーカイブ。2009年9月7日に取得。Adoptのオリジナルバージョンは後に、情報に基づいて探索を絞り込み、実行速度を上げるために、解のコスト推定値を使用するように拡張されました。Ali , Syed; Koenig, Sven; Tambe, Milind (2005)、「DCOPアルゴリズムADOPTの高速化のための前処理技術」(PDF)、自律エージェントとマルチエージェントシステムに関する第4回国際合同会議の議事録、ACM Press、pp.  1041– 8、doi : 10.1145/1082473.1082631、ISBNを参照。 1595930930, S2CID  10882572 , 2010年7月7日にオリジナル（PDF）からアーカイブ、 2009年9月7日取得この Adopt の拡張機能は、通常、Adopt のリファレンス実装として使用されます。
  6. ^松井俊宏、松尾博、岩田明（2005年2月）「非同期分散制約最適化アルゴリズムの効率的な手法」（PDF）、人工知能と応用論文集、pp.  727– 732、CiteSeerX 10.1.1.408.7230 
  7. ^メイラー、ロジャー、レッサー、ビクター (2004). 「協調的仲介を用いた分散制約最適化問題の解決」 .第3回自律エージェントおよびマルチエージェントシステム国際合同会議議事録. IEEEコンピュータソサエティ. pp.  438– 445. ISBN 1581138644。
  8. ^ Grinshpoun, Tal; Zazon, Moshe; Binshtok, Maxim; Meisels, Amnon (2007)、「APOアルゴリズムの終了問題」(PDF)、第8回国際分散制約推論ワークショップの議事録、pp.  117– 124
  9. ^ Petcu, Adrian; Faltings, Boi (2005年8月)、「DPOP: マルチエージェント制約最適化のためのスケーラブルな手法」、第19回国際人工知能合同会議議事録、IJCAI 2005、エディンバラ、スコットランド、pp. 266-271
  10. ^ Chechetka, Anton; Sycara, Katia (2006年5月)、「分散制約最適化のためのノーコミットメント分岐限定探索」(PDF)、自律エージェントおよびマルチエージェントシステムに関する第5回国際合同会議の議事録、pp.  1427– 9、doi : 10.1145/1160633.1160900、ISBN 1595933034、S2CID  43918609
  11. ^ Chechetka, Anton; Sycara, Katia (2006年3月)、「分散制約最適化のための任意空間アルゴリズム」(PDF)、分散計画・スケジュール管理に関するAAAI春季シンポジウム議事録
  12. ^ Duffy, KR; Leith, DJ (2013年8月)、「分散型制約充足」、IEEE/ACM Transactions on Networking、21 (4): 1298– 1308、arXiv : 1103.3240、doi : 10.1109/TNET.2012.2222923、S2CID 11504393 
  13. ^ a b c Grinshpoun, T.; Grubshtein, A.; Zivan, R.; Netzer, A.; Meisels, A. (2013-07-30). 「非対称分散制約最適化問題」 . Journal of Artificial Intelligence Research . 47 : 613–647 . arXiv : 1402.0587 . doi : 10.1613/jair.3945 . ISSN 1076-9757 . 
  14. ^グリーンシュタット、レイチェル、ピアース、ジョナサン・P、タンベ、ミリンド (2006年7月16日). 「分散制約最適化におけるプライバシー損失の分析」 .第21回人工知能全国会議議事録 - 第1巻. AAAI'06. ボストン: AAAI Press: 647–653 . ISBN 978-1-57735-281-5。
  15. ^ Maheswaran, Rajiv T.; Pearce, Jonathan P.; Bowring, Emma; Varakantham, Pradeep; Tambe, Milind (2006-07-01). 「分散制約推論におけるプライバシー損失：分析とその応用のための定量的枠組み」 .自律エージェントとマルチエージェントシステム. 13 (1): 27– 60. doi : 10.1007/s10458-006-5951-y . ISSN 1573-7454 . S2CID 16962945 .  
  16. ^横尾 誠、鈴木 幸太郎、平山 克俊 (2002). 「セキュアな分散制約充足：個人情報を漏らさずに合意に達する」 . Van Hentenryck, Pascal (編). 『制約プログラミングの原理と実践 – CP 2002』 . コンピュータサイエンス講義ノート. 第2470巻. ベルリン、ハイデルベルク：シュプリンガー. pp.  387– 401. doi : 10.1007/3-540-46135-3_26 . ISBN 978-3-540-46135-7。
  17. ^ Rajiv T. Maheswaran、Milind Tambe、Emma Bowring、Jonathan P. Pearce、Pradeep Varakantham (2004). 「DCOPを現実世界へ：分散型マルチイベントスケジューリングのための効率的で完全なソリューション」 . computer.org . 2021年4月12日閲覧。
  18. ^ a b Zivan, Roie; Grubshtein, Alon; Friedman, Michal; Meisels, Amnon (2012-06-04). 「マルチエージェント探索における部分的協力」 . Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3. AAMAS '12. 3. Valencia, Spain: International Foundation for Autonomous Agents and Multiagent Systems: 1267–1268 . ISBN 978-0-9817381-3-0。

書籍と調査

「 https://en.wikipedia.org/w/index.php?title=Distributed_constraint_optimization&oldid=1309082591」より取得