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

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

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

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

Фреймворк использовался под разными названиями в 1980-х годах. Первое известное использование с нынешним названием относится к 1990 году.^{[нужна цитата ]}

Определения

DCOP

А DCOP можно определить как кортеж ${displaystyle langle A,V,{mathfrak {D}},f,alpha ,eta angle }$, куда:

• ${displaystyle A}$ это набор из агенты;
• ${displaystyle V}$ набор переменных, ${displaystyle {v_{1},v_{2},cdots ,v_{|V|}}}$;
• ${displaystyle {mathfrak {D}}}$ это набор доменов, ${displaystyle {D_{1},D_{2},ldots ,D_{|V|}}}$, где каждый ${displaystyle Din {mathfrak {D}}}$ это конечный набор содержащие значения, которым может быть присвоена соответствующая переменная;
• ${displaystyle f}$ это функция^[1][2]${displaystyle f:igcup _{Sin {mathfrak {P}}(V)}sum {v_{i}in S}left({v_{i}} imes D_{i}ight)ightarrow mathbb {N} cup {infty }}$который сопоставляет все возможные присвоения переменной стоимости. Эту функцию также можно рассматривать как определение ограничений между переменными, однако переменные не должны быть эрмитовыми;
• ${displaystyle alpha }$ это функция ${displaystyle alpha :Vightarrow A}$ отображение переменных на связанного с ними агента. ${displaystyle alpha (v_{i})mapsto a_{j}}$ подразумевает, что это агент ${displaystyle a_{j}}$обязан присвоить значение переменной ${displaystyle v_{i}}$. Обратите внимание, что это не обязательно верно, что ${displaystyle alpha }$ является либо инъекция или же сюрприз; и
• ${displaystyle eta }$ является оператор который объединяет все отдельные ${displaystyle f}$ затраты на все возможные присвоения переменных. Обычно это достигается путем суммирования:${displaystyle eta (f)mapsto sum _{sin igcup _{Sin {mathfrak {P}}(V)}sum {v_{i}in S}left({v_{i}} imes D_{i}ight)}f(s)}$.

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

Контекст

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

${displaystyle t:Vightarrow (Din {mathfrak {D}})cup {emptyset }.}$

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

Примеры проблем

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

В раскраска графика проблема в следующем: учитывая график ${displaystyle G=langle N,Eangle }$ и набор цветов ${displaystyle C}$назначить каждому вершина, ${displaystyle nsubset N}$, цвет, ${displaystyle cleq C}$, такое, что количество соседних вершин одного цвета минимизировано.

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

${displaystyle (forall csubseteq C:f(langle v_{i},cangle ,langle v_{j},cangle )mapsto 1).}$

Таким образом, цель состоит в том, чтобы минимизировать ${displaystyle eta (f)}$.

Распределенная задача с несколькими рюкзаками

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

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

${displaystyle f(t)mapsto sum _{kin K}{egin{cases}0&r(t,k)leq c(k), (t,k)-c(k)&{ ext{otherwise}},end{cases}}}$

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

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

Алгоритмы

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

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

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

Смотрите также

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

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

1. "${displaystyle {mathfrak {P}}({mathfrak {V}})}$"обозначает набор мощности из ${displaystyle V}$
2. "${displaystyle imes }$" и "${displaystyle sum }$"обозначают Декартово произведение.
3. Ага, Уильям; Фельнер, Ариэль; Кениг, Свен (2008), "BnB-ADOPT: асинхронный алгоритм DCOP с переходом и границей", Материалы седьмой международной совместной конференции по автономным агентам и многоагентным системам, стр. 591–598
4. Чечетка, Антон; Сикара, Катя (май 2006 г.), «Переход без обязательств и поиск границ для оптимизации распределенных ограничений» (PDF), Труды Пятой международной совместной конференции по автономным агентам и многоагентным системам, стр. 1427–1429
5. Чечетка, Антон; Сикара, Катя (март 2006 г.), "Алгоритм произвольного пространства для оптимизации распределенных ограничений" (PDF), Материалы весеннего симпозиума AAAI по распределенному плану и управлению расписанием
6. Петку, Адриан; Фалтингс, Бои (август 2005 г.), «DPOP: масштабируемый метод многоагентной оптимизации ограничений», Труды 19-й международной совместной конференции по искусственному интеллекту, IJCAI 2005, Эдинбург, Шотландия, стр. 266-271.
7. Майллер, Роджер; Меньший, Виктор (2004), «Решение задач оптимизации распределенных ограничений с помощью кооперативного посредничества» (PDF), Труды Третьей международной совместной конференции по автономным агентам и многоагентным системам, IEEE Computer Society, стр. 438–445
8. Гриншпоун, Тал; Зазон, Моше; Биншток, Максим; Майзельс, Амнон (2007), «Проблема завершения алгоритма APO» (PDF), Материалы восьмого международного семинара по распределенным ограничениям., стр. 117–124
9. Первоначально опубликованная версия Adopt не была информирована, см.Моди, Прагнеш Джей; Шэнь, Вэй-Минь; Tambe, Milind; Йоку, Макото (2003), «Асинхронный полный метод для оптимизации распределенных ограничений» (PDF), Труды второй международной совместной конференции по автономным агентам и мультиагентным системам, ACM Press, стр. 161–168.. Первоначальная версия Adopt была позже расширена для информирования, то есть для использования оценок стоимости решения, чтобы сфокусировать поиск и работать быстрее, см.Али, Сайед; Кениг, Свен; Тамбе, Милинд (2005), «Методы предварительной обработки для ускорения алгоритма DCOP ADOPT» (PDF), Труды четвертой международной совместной конференции по автономным агентам и мультиагентным системам, ACM Press, стр. 1041–1048.. Это расширение Adopt обычно используется как эталонная реализация Adopt.
10. Мацуи, Тошихиро; Мацуо, Хироши; Ивата, Акира (февраль), «Эффективный метод для алгоритма оптимизации асинхронных распределенных ограничений» (PDF), Труды по искусственному интеллекту и приложениям, стр. 727–732 Проверить значения даты в: | дата = и | год = / | дата = несоответствие (помощь)
11. Даффи, К.Р .; Лейт, Д.Дж. (Август 2013 г.), «Децентрализованное удовлетворение ограничений», Транзакции IEEE / ACM в сети, 21 (4), 21, стр. 1298–1308, arXiv:1103.3240, Дои:10.1109 / TNET.2012.2222923

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

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