Оптимизация распределенных ограничений

редактировать

Оптимизация распределенных ограничений (DCOP или DisCOP ) - это распределенный аналог оптимизации ограничений. DCOP - это проблема, в которой группа агентов должна распределенно выбирать значения для набора переменных таким образом, чтобы стоимость набора ограничений по переменным была минимальной.

Распределенное удовлетворение ограничений - это структура для описания проблемы в терминах ограничений, которые известны и применяются отдельными участниками (агентами). Ограничения описываются для некоторых переменных с предопределенными доменами и должны быть присвоены одним и тем же значениям разными агентами.

Проблемы, определенные с помощью этой структуры, могут быть решены любым из алгоритмов, которые разработаны для нее.

Фреймворк использовался под разными названиями в 1980-х годах. Первое известное использование с текущим именем относится к 1990 году.

Содержание

1 Определения
- 1.1 DCOP
- 1.2 Контекст
2 Примеры проблем
- 2.1 Раскраска распределенного графа
- 2.2 Распределенное множественное проблема ранца
3 Алгоритмы
4 См. также
5 Примечания и ссылки
6 Книги и обзоры

Определения

DCOP

A DCOP можно определить как tuple $⟨A, V, D, f, α, η⟩ {\ displaystyle \ langle A, V, {\ mathfrak {D}}, f, \ alpha, \ eta \ rangle}$ $\ langle A, V, {\ mathfrak {D}}, f, \ alpha, \ eta \ rangle$ , где:

$A {\ displaystyle A}$ $A$ - набор из агентов ;
$V {\ displaystyle V}$ $V$ - это набор переменных, ${v 1, v 2, ⋯, v | V | } {\ displaystyle \ {v_ {1}, v_ {2}, \ cdots, v_ {| V |} \}}$ $\ {v_ {1}, v_ {2}, \ cdots, v_ {| V |} \}$ ;
$D {\ displaystyle {\ mathfrak {D}}}$ ${\ mathfrak {D}}$ - это набор доменов, ${D 1, D 2,…, D | V | } {\ displaystyle \ {D_ {1}, D_ {2}, \ ldots, D_ {| V |} \}}$ $\ {D_ {1}, D_ {2}, \ ldots, D_ {| V |} \}$ , где каждый $D ∈ D {\ displaystyle D \ in { \ mathfrak {D}}}$ $D \ in {\ mathfrak {D}}$ - это конечный набор, содержащий значения, которым может быть присвоена связанная с ним переменная;
$f {\ displaystyle f}$ $f$ является функцией $f: ⋃ S ∈ P (V) ∑ vi ∈ S ({vi} × D i) → N ∪ {∞} {\ displaystyle f: \ bigcup _ {S \ in {\ mathfrak {P}} (V)} \ sum {v_ {i} \ in S} \ left (\ {v_ {i} \} \ times D_ {i} \ right) \ rightarrow \ mathbb {N} \ cup \ {\ infty \}}$ $f: \ bigcup _ {S \ in {\ mathfrak {P }} (V)} \ sum {v_ {i} \ in S} \ left (\ {v_ {i} \} \ t imes D_ {i} \ right) \ rightarrow \ mathbb {N} \ cup \ {\ infty \}$ , который сопоставляет все возможные присвоения переменной стоимости. Эту функцию также можно рассматривать как определение ограничений между переменными, однако переменные не должны быть эрмитовыми;
$α {\ displaystyle \ alpha}$ $\ alpha$ - это функция $α: V → A {\ displaystyle \ alpha: V \ rightarrow A}$ $\ alpha: V \ rightarrow A$ отображение переменных на их связанный агент. $α (vi) ↦ aj {\ displaystyle \ alpha (v_ {i}) \ mapsto a_ {j}}$ $\ alpha (v_ {i}) \ mapsto a_ {j}$ подразумевает, что это агент $aj {\ displaystyle a_ {j}}$ $a_ {j}$ отвечает за присвоение значения переменной $vi {\ displaystyle v_ {i}}$ $v_ {i}$ . Обратите внимание, что не обязательно верно, что $α {\ displaystyle \ alpha}$ $\ alpha$ является либо инъекцией, либо сюръекцией ; и
$η {\ displaystyle \ eta}$ $\ eta$ - это оператор, который объединяет все индивидуальные затраты $f {\ displaystyle f}$ $f$ для всех возможные присвоения переменных. Обычно это достигается путем суммирования: $η (f) ↦ ∑ s ∈ ⋃ S ∈ P (V) ∑ vi ∈ S ({vi} × D i) f (s) {\ displaystyle \ eta ( е) \ mapsto \ sum _ {s \ in \ bigcup _ {S \ in {\ mathfrak {P}} (V)} \ sum {v_ {i} \ in S} \ left (\ {v_ {i} \ } \ times D_ {i} \ right)} f (s)}$ $\ eta (f) \ mapsto \ sum _ {s \ in \ bigcup _ {S \ in {\ mathfrak {P}} (V)} \ sum {v_ {i} \ in S} \ left (\ {v_ {i} \} \ times D_ {i} \ right)} f (s)$ .

Цель DCOP состоит в том, чтобы каждый агент присваивал значения связанным с ним переменным, чтобы минимизировать или максимизировать $η (f) { \ displaystyle \ eta (f)}$ $\ eta (f)$ для заданного присвоения переменных.

Контекст

A контекст - это присвоение переменной для DCOP. Это можно представить как функцию преобразования переменных в DCOP в их текущие значения:

t: V → (D ∈ D) ∪ {∅}. {\ displaystyle t: V \ rightarrow (D \ in {\ mathfrak {D}}) \ cup \ {\ emptyset \}.}

t: V \ rightarrow (D \ in {\ mathfrak {D}}) \ cup \ {\ emptyset \}.

Обратите внимание, что контекст, по сути, является частичным решением и не обязательно должен содержать значения для каждой переменной в проблеме; следовательно, $t (vi) ↦ ∅ {\ displaystyle t (v_ {i}) \ mapsto \ emptyset}$ $t (v_ {i}) \ mapsto \ emptyset$ подразумевает, что агент $α (vi) {\ displaystyle \ alpha (v_ {i})}$ $\ alpha (v_ {i})$ еще не присвоило значение переменной $vi {\ displaystyle v_ {i}}$ $v_ {i}$ . При таком представлении «домен » (то есть набор входных значений) функции fможно рассматривать как набор всех возможных контекстов для DCOP. Поэтому в оставшейся части этой статьи мы можем использовать понятие контекста (т.е. функцию $t {\ displaystyle t}$ $t$ ) в качестве входных данных для $f {\ displaystyle f }$ $f$ функция.

Примеры задач

Раскраска распределенного графа

Проблема раскраски графа выглядит следующим образом: для graph $G = ⟨N, E⟩ {\ displaystyle G = \ langle N, E \ rangle}$ $G = \ langle N, E \ rangle$ и набор цветов $C {\ displaystyle C}$ $C$ , назначьте каждому вершина, $n ⊂ N {\ displaystyle n \ subset N}$ ${\ displaystyle n \ subset N}$ , цвет, $c ≤ C {\ displaystyle c \ leq C}$ ${\ displaystyle c \ leq C}$ , такое, что количество соседних вершин одного цвета минимизировано.

В качестве DCOP на каждую вершину назначается один агент, который определяет соответствующий цвет. У каждого агента есть одна переменная, связанный домен которой имеет мощность $| C | {\ displaystyle | C |}$ $| C |$ (для каждого возможного цвета существует одно значение домена). Для каждой вершины $ni ≤ N {\ displaystyle n_ {i} \ leq N}$ ${\ displaystyle n_ {i} \ leq N}$ создайте переменную в DCOP $vi ∈ V {\ displaystyle v_ {i} \ in V}$ $v_ {i} \ in V$ с доменом $D i = C {\ displaystyle D_ {i} = C}$ $D_{i}=C$ . Для каждой пары смежных вершин $⟨ni, nj⟩ ∈ E {\ displaystyle \ langle n_ {i}, n_ {j} \ rangle \ in E}$ $\ langle n_ {i}, n_ {j} \ rangle \ in E$ создайте ограничение стоимости 1, если обеим ассоциированным переменным присваивается один и тот же цвет:

(∀ c ⊆ C: f (⟨vi, c⟩, ⟨vj, c⟩) ↦ 1). {\ displaystyle (\ forall c \ substeq C: f (\ langle v_ {i}, c \ rangle, \ langle v_ {j}, c \ rangle) \ mapsto 1).}

{\ displaystyle (\ forall c \ substeq C: f (\ langle v_ {i}, c \ rangle, \ langle v_ {j}, c \ rangle) \ mapsto 1).}

Таким образом, цель - для минимизации $η (f) {\ displaystyle \ eta (f)}$ $\ eta (f)$ .

Распределенная задача о множестве ранцев

Распределенный множественный вариант задачи о ранце выглядит следующим образом: учитывая набор предметов разного объема и набор ранцев различной вместимости, назначьте каждый предмет рюкзаку таким образом, чтобы количество переполнения было минимальным. Пусть $I {\ displaystyle I}$ $I$ будет набором элементов, $K {\ displaystyle K}$ $K$ будет набором ранцев, $s: I → N {\ displaystyle s: I \ rightarrow \ mathbb {N}}$ $s: I \ rightarrow \ mathbb {N}$ быть функцией, отображающей элементы в их объем, и $c: K → N {\ displaystyle c: K \ rightarrow \ mathbb { N}}$ $c: K \ rightarrow \ mathbb {N}$ - функция, отображающая рюкзаки на их возможности.

Чтобы закодировать эту задачу как DCOP, для каждого $i ∈ I {\ displaystyle i \ in I}$ $i \ in I$ создайте одну переменную $vi ∈ V {\ displaystyle v_ { i} \ in V}$ $v_ {i} \ in V$ со связанным доменом $D i = K {\ displaystyle D_ {i} = K}$ $D_ {i} = K$ . Тогда для всех возможных контекстов $t {\ displaystyle t}$ $t$ :

f (t) ↦ ∑ k ∈ K {0 r (t, k) ≤ c (k), r (t, k) - c (k) в противном случае {\ Displaystyle f (t) \ mapsto \ sum _ {k \ in K} {\ begin {cases} 0 r (t, k) \ leq c (k), \\ r (t, k) -c (k) {\ text {else}}, \ end {cases}}}

f (t) \ mapsto \ sum _ {k \ in K} {\ begin {cases} 0 r (t, k) \ leq c (k), \\ r (t, k) -c (k) {\ text {else}}, \ end {cases}}

где $r (t, k) {\ displaystyle r (t, k)}$ $r ( t, k)$ - это функция такая, что

r (t, k) = ∑ vi ∈ t - 1 (k) s (i). {\ displaystyle r (t, k) = \ sum _ {v_ {i} \ in t ^ {- 1} (k)} s (i).}

r (t, k) = \ sum _ {v_ {i} \ in t ^ {- 1} (k)} s (i).

Алгоритмы

алгоритмы DCOP могут быть классифицируются в соответствии со стратегией поиска (поиск лучшего первого или поиск в глубину с ветвлением и границей), синхронизацией между агентами (синхронной или асинхронной), обменом данными между агентами (точка-точка с соседями в графе ограничений или широковещательная передача) и основная топология связи (цепочка или дерево). ADOPT, например, использует поиск лучшего первого, асинхронную синхронизацию, двухточечную связь между соседними агентами в графе ограничений и дерево ограничений в качестве основной топологии связи.

Название алгоритма	Год внедрения	Сложность памяти	Количество сообщений	Корректность (информатика) /. Полнота (логика)	Реализации
NCBB . Ветвление и граница без обязательств	2006	Многочлен (или любой пробел)	Экспоненциальный	Проверенный	Ссылка Реализация: публично не выпущено. DCOPolis (GNU LGPL )
DPOP . Процедура оптимизации распределенного псевдодерева	2005	Exponential	Линейный	Проверенная	Эталонная реализация: FRODO (GNU Affero GPL ). DCOPolis (GNU LGPL )
OptAPO . Асинхронное частичное наложение	2004	Полиномиальное	Экспоненциальное	Доказано, но доказательство полноты оспаривается	Ссылочная реализация: «OptAPO». Центр искусственного интеллекта. SRI International. Архивировано из оригинала 2007-07 гг. -15.. DCOPolis (GNU LGPL ); В разработке
Adopt. Асинхронный поиск с возвратом	2003	Многочлен (или любой пробел)	Экспоненциальный	Доказано	Эталонная реализация: Принять. DCOPolis (GNU LGPL ). FRODO (GNU Affero GPL )
Безопасное многостороннее вычисление для решения DisCSP . (MPC-DisCSP1-MPC-DisCSP4)	2003			Примечание: безопасно, если половина участников заслуживает доверия
Безопасные вычисления с полу-доверенными серверами	2002			Примечание: безопасность повышается с увеличением количества надежных серверов
ABTR . Асинхронный возврат с переупорядочиванием	2001			Примечание: заказ в ABT с ограниченными товарами
DMAC . Поддержание асинхронной согласованности	2001			Примечание: самый быстрый алгоритм
AAS . Асинхронный поиск агрегирования	2000			агрегирование значений в ABT
DFC . Распределенная прямая цепочка	2000			Примечание: низкий, сопоставимый с ABT
DBA . Distrib Используемый алгоритм прорыва	1995			Примечание: неполный, но быстрый	FRODO версии 1
AWC . Асинхронное слабое обязательство	1994			Примечание: переупорядочивание, быстрое, полное (только с экспоненциальным пространством)
ABT . Асинхронное отслеживание с возвратом	1992			Примечание: статическое упорядочивание, полное
CFL . Связь -Свободное обучение	2013	Линейное	Нет Примечание: сообщения не отправляются, но предполагается знание об удовлетворении локальных ограничений	Неполный

Гибриды из этих алгоритмов DCOP также существуют. BnB-Adopt, например, изменяет стратегию поиска Adopt с поиска по принципу «сначала лучший» на поиск по ветвям и границам, сначала в глубину.

См. Также

Проблема удовлетворения ограничений

Примечания и ссылки

^" $P (V) {\ displaystyle {\ mathfrak {P}} ({\ mathfrak {V}})}$ ${\ mathfrak {P}} ({\ mathfrak {V}})$ "обозначает набор мощности из $V {\ displaystyle V}$ $V$
^" $× {\ displaystyle \ times}$ $\ times$ " и " $∑ {\ displaystyle \ sum}$ $\ sum$ "обозначают декартово произведение.
^ Йео, Уильям; Фельнер, Ариэль; Кениг, Свен (2008), «BnB-ADOPT: асинхронный алгоритм DCOP с ветвями и границами», Труды Седьмой международной совместной конференции по автономным агентам и многоагентным системам, стр. 591–598
^Чечетка, Антон; Сикара, Катя (май 2006 г.), «Ответвление без обязательств и поиск границ для оптимизации распределенных ограничений» (PDF), Труды Пятой международной совместной конференции по автономным агентам и многоагентным системам, стр. 1427–1429
^Чечетка, Антон; Сикара, Катя (март 2006 г.), «Алгоритм в любом пространстве для оптимизации распределенных ограничений» (PDF), Материалы весеннего симпозиума AAAI по распределенному плану и управлению расписанием
^Петку, Адриан ; Фалтингс, Бой (август 2005 г.), «DPOP: масштабируемый метод для многоагентной оптимизации ограничений», Труды 19-й Международной совместной конференции по искусственному интеллекту, IJCAI 2005, Эдинбург, Шотландия, стр. 266-271
^Мейллер, Роджер; Лессер, Виктор (2004), «Решение задач оптимизации распределенных ограничений с использованием кооперативного посредничества» (PDF), Труды Третьей международной совместной конференции по автономным агентам и многоагентным системам, Компьютерное общество IEEE, pp. 438–445
^Гриншпун, Тал; Зазон, Моше; Биншток, Максим; Майзельс, Амнон (2007), «Проблема завершения алгоритма APO» (PDF), Труды восьмого международного семинара по распределенному обоснованию ограничений, стр. 117–124
^Первоначально опубликованная версия Adopt был не информирован, см. Моди, Прагнеш Джей; Шэнь, Вэй-Минь; Tambe, Milind; Йоку, Макото (2003), «Асинхронный полный метод для оптимизации распределенных ограничений» (PDF), Труды второй международной совместной конференции по автономным агентам и мультиагентным системам, ACM Press, С. 161–168. Первоначальная версия Adopt была позже расширена для информирования, то есть для использования оценок стоимости решения, чтобы сфокусировать поиск и работать быстрее, см. Али, Сайед; Кениг, Свен; Tambe, Milind (2005), «Методы предварительной обработки для ускорения алгоритма DCOP ADOPT» (PDF), Труды четвертой международной совместной конференции по автономным агентам и многоагентным системам, ACM Press, С. 1041–1048. Это расширение Adopt обычно используется как эталонная реализация Adopt.
^Мацуи, Тошихиро; Мацуо, Хироши; Ивата, Акира (февраль), «Эффективный метод для асинхронного алгоритма оптимизации с распределенными ограничениями» (PDF), Proceedings of Artificial Intelligence and Applications, pp. 727–732 Проверить значения даты в: | date =и | year = / | date = mismatch()
^Duffy, KR; Leith, DJ (август 2013), "Decentralized Constraint Satisfaction", IEEE / ACM Транзакции в сети, 21 (4), 21, стр. 1298–1308, arXiv : 1103.3240, doi : 10.1109 / TNET.2012.2222923

Книги и обзоры

Фиоретто, Фердинандо; Понтелли, Энрико; Йео, Уильям (2018), «Проблемы оптимизации распределенных ограничений и приложения: обзор», Журнал исследований искусственного интеллекта, 61: 623–698, arXiv : 1602.06347, doi : 10.1613 / jair.5565
Faltings, Бой (2006), «Распределенное программирование в ограничениях», в Уолш, Тоби (ред.), Справочник по программированию в ограничениях, Elsevier, ISBN 978 -0-44 4-52726-4 Глава отредактированной книги.
Майзелс, Амнон (2008), Распределенный поиск ограниченными агентами, Springer, ISBN 978 -1-84800-040-7
Шохам, Йоав; Лейтон-Браун, Кевин (2009), Многоагентные системы: алгоритмические, теоретико-игровые и логические основы, Нью-Йорк: Cambridge University Press, ISBN 978-0-521-89943-7 См. Главы 1 и 2; загружается бесплатно в Интернете.
Йоку, Макото (2001), Распределенное удовлетворение ограничений: основы сотрудничества в многоагентных системах, Springer, ISBN 978-3 -540-67596-9
Ёко, М., и Хираяма, К. (2000). Алгоритмы выполнения распределенных ограничений: обзор. Труды Международной совместной конференции по автономным агентам и многоагентным системам (стр. 185–207). Обзор.