分散制約最適化

分散制約最適化( DCOPまたはDisCOP ) は、制約最適化の分散版です。DCOP は、エージェントのグループが変数セットの値を分散的に選択し、変数に対する制約セットのコストが最小化される問題です。

分散制約充足は、異なる参加者 (エージェント) によって認識され、強制される制約の観点から問題を記述するためのフレームワークです。制約は、定義済みのドメインを持ついくつかの変数に記述され、異なるエージェントによって同じ値に割り当てられる必要があります。

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

このフレームワークは 1980 年代に別の名前で使用されていました。現在の名前で最初に使用されたのは 1990 年です。^{[引用が必要]}

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

• ${\displaystyle A}$はエージェントの集合です。${\displaystyle \{a_{1},\dots ,a_{|A|}\}}$
• ${\displaystyle V}$は変数の集合です。${\displaystyle \{v_{1},v_{2},\dots ,v_{|V|}\}}$
• ${\displaystyle {\mathfrak {D}}}$は変数領域の集合、であり、各 は変数 の可能な値を含む有限集合です。 ${\displaystyle \{D_{1},D_{2},\dots ,D_{|V|}\}}$${\displaystyle D_{j}\in {\mathfrak {D}}}$${\displaystyle v_{j}}$
  • 2 つの値 (例: 0 または 1) のみが含まれる場合、バイナリ変数と呼ばれます。${\displaystyle D_{j}\in {\mathfrak {D}}}$${\displaystyle v_{j}}$
• ${\displaystyle f}$はコスト関数です。これは、すべての可能な部分割り当てをコストにマッピングする関数^[1]です。通常、 の値がゼロ以外の値になるのはごくわずかで、ゼロ以外の値が割り当てられたタプルのリストとして表されます。このようなタプルはそれぞれ制約と呼ばれます。このセット内の各制約は、変数の可能な割り当てごとに実数値を割り当てる関数です。いくつかの特殊な制約は次のとおりです。 $${\displaystyle f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R} }$$${\displaystyle f}$${\displaystyle C}$${\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} }$
  • 単項制約- 単一の変数に対する制約、つまり、いくつかの に対する制約。${\displaystyle f_{C}:D_{j}\to \mathbb {R} }$${\displaystyle v_{j}\in V}$
  • バイナリ制約- 2 つの変数に対する制約、つまり、ある に対して。${\displaystyle f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R} }$${\displaystyle v_{j_{1}},v_{j_{2}}\in V}$
• ${\displaystyle \alpha}$は所有権関数です。これは、各変数をそれに関連付けられたエージェントにマッピングする関数です。 は、変数がエージェントに「属する」ことを意味します。これは、変数の値を割り当てることがエージェントの責任であることを意味します。 は必ずしも注入ではないことに注意してください。つまり、1 つのエージェントが複数の変数を所有する場合があります。 また、必ずしも全射ではない場合もあります。つまり、一部のエージェントは変数を所有しない場合があります。${\displaystyle \alpha :V\to A}$${\displaystyle \alpha (v_{j})\mapsto a_{i}}$${\displaystyle v_{j}}$${\displaystyle a_{i}}$${\displaystyle a_{i}}$${\displaystyle v_{j}}$${\displaystyle \alpha}$
• ${\displaystyle \eta}$は目的関数です。これは、すべての可能な変数割り当ての個々のコストをすべて集計する演算子です。これは通常、合計によって実行されます。${\displaystyle f}$$${\displaystyle \eta (f)\mapsto \sum _{s\in \bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}}f(s).}$$

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

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

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

完全割り当てとは、各変数が 1 回だけ出現する割り当て、つまりすべての変数が割り当てられる割り当てです。これは、DCOP の ソリューションとも呼ばれます。${\displaystyle v_{j}}$

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

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

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

DCOP の場合、頂点ごとに 1 つのエージェントが割り当てられ、関連付けられた色を決定します。各エージェントには、関連付けられたドメインがカーディナリティである 1 つの変数があります( 可能な色ごとに 1 つのドメイン値があります)。各頂点 には、ドメイン の変数があります。隣接する頂点 の各ペアには、関連付けられた変数の両方に同じ色が割り当てられている場合、コスト 1 の制約があります。したがって、目的は を最小化することです。 ${\displaystyle |C|}$${\displaystyle n_{i}\leq N}$${\displaystyle v_{i}\in V}$${\displaystyle D_{i}=C}$${\displaystyle \langle n_{i},n_{j}\rangle \in E}$$${\displaystyle (\forall c\subseteq C:f(\langle v_{i},c\rangle ,\langle v_{j},c\rangle )\mapsto 1).}$$${\displaystyle \eta (f)}$

ナップザック問題の分散多重バリアントは次のようになります。さまざまな体積のアイテムのセットとさまざまな容量のナップザックのセットが与えられた場合、オーバーフロー量が最小になるように各アイテムをナップザックに割り当てます。アイテムのセットを 、ナップザックのセットを 、アイテムをその体積にマッピングする関数を 、ナップザックをその容量にマッピングする関数を とします。 ${\displaystyle I}$${\displaystyle K}$${\displaystyle s:I\to \mathbb {N} }$${\displaystyle c:K\to \mathbb {N} }$

この問題を DCOP としてエンコードするには、それぞれに対して、関連付けられたドメインを持つ1 つの変数を作成します。次に、すべての可能なコンテキストに対して、次のようになります。ここで、 はコンテキストによってナップザックに割り当てられた合計の重みを表します。${\displaystyle i\in I}$${\displaystyle v_{i}\in V}$${\displaystyle D_{i}=K}$${\displaystyle t}$$${\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}}}$$${\displaystyle r(t,k)}$${\displaystyle t}$${\displaystyle k}$$${\displaystyle r(t,k)=\sum _{v_{i}\in t^{-1}(k)}s(i).}$$

アイテム割り当て問題は以下のとおりです。複数のエージェント間で分割する必要があるアイテムがいくつかあります。各エージェントはアイテムに対して異なる評価を持っています。目標は、効用の合計を最大化したり、羨望を最小化したりするなど、いくつかのグローバル目標を最適化することです。アイテム割り当て問題は、次のように DCOP として定式化できます。^[2]

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

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

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

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

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

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

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

非対称DCOPはDCOPの拡張であり、各制約のコストがエージェントごとに異なる可能性がある。いくつかの応用例は以下の通りである: ^[13]

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

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

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

ADCOPを解く簡単な方法は、各制約を制約 に置き換えることです。これは関数 の合計に等しくなります。しかし、この解決法では、エージェントがコスト関数を明らかにする必要があります。多くの場合、プライバシーの観点からこれは望ましくありません。^{[14] [15] [16]}${\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}}$${\displaystyle f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R} }$${\displaystyle f_{C}^{1}+\cdots +f_{C}^{k}}$

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

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

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

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

エージェントが部分的に協力的である中間モデルもいくつかある。エージェントは、グローバル目標達成のために自分の効用を下げても構わないが、それは自分のコストが高すぎない場合に限られる。部分的に協力的なエージェントの例としては、企業の従業員が挙げられる。一方では、各従業員は自分の効用を最大化したいと考えている。他方では、企業の成功にも貢献したいと考えている。したがって、自分にとって負担が大きすぎない限り、他の人を助けたり、企業に役立つ時間のかかる作業を行ったりしても構わないと考えている。部分的に協力的なエージェントのモデルには次のようなものがある。^[18]

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

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

• 制約充足問題
• 分散アルゴリズム
• 分散アルゴリズムメカニズム設計

• フィオレット、フェルディナンド; ポンテッリ、エンリコ; ヨー、ウィリアム (2018)、「分散制約最適化問題とその応用: 概観」、人工知能研究ジャーナル、61 : 623–698、arXiv : 1602.06347、doi :10.1613/jair.5565、S2CID  4503761
• Faltings, Boi (2006)、「分散制約プログラミング」、Walsh, Toby (編)、『制約プログラミングハンドブック』、Elsevier、ISBN 978-0-444-52726-4編集された本の章。
• マイゼルス、アムノン（2008）、制約付きエージェントによる分散検索、シュプリンガー、ISBN 978-1-84800-040-7
• ショーハム、ヨアブ、レイトンブラウン、ケビン（2009）、マルチエージェントシステム：アルゴリズム、ゲーム理論的、論理的基礎、ニューヨーク：ケンブリッジ大学出版局、ISBN 978-0-521-89943-7第 1 章と第 2 章を参照してください。オンラインで無料でダウンロードできます。
• 横尾​​誠（2001）「分散制約充足：マルチエージェントシステムにおける協力の基礎」Springer、ISBN 978-3-540-67596-9
• 横尾​​ 正之 平山 健一 (2000)、「分散制約充足アルゴリズム: レビュー」、自律エージェントとマルチエージェントシステム、3 (2): 185–207、doi :10.1023/A:1010078712316、S2CID  2139298