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

Distributed constraint optimization

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

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

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

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

Определения

DCOP

А DCOP можно определить как кортеж , куда:

  • это набор из агенты;
  • набор переменных, ;
  • это набор доменов, , где каждый это конечный набор содержащие значения, которым может быть присвоена соответствующая переменная;
  • это функция[1][2]
    который сопоставляет все возможные присвоения переменной стоимости. Эту функцию также можно рассматривать как определение ограничений между переменными, однако переменные не должны быть эрмитовыми;
  • это функция отображение переменных на связанного с ними агента. подразумевает, что это агент обязан присвоить значение переменной . Обратите внимание, что это не обязательно верно, что является либо инъекция или же сюрприз; и
  • является оператор который объединяет все отдельные затраты на все возможные присвоения переменных. Обычно это достигается путем суммирования:
    .

Задача DCOP состоит в том, чтобы каждый агент присваивал значения связанным с ним переменным, чтобы минимизировать или максимизировать для данного присвоения переменных.

Контекст

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

Обратите внимание, что контекст по сути является частичным решением и не должен содержать значений для каждый переменная в задаче; следовательно, подразумевает, что агент еще не присвоил значение переменной . Учитывая это представление, "домен" (т.е., набор входных значений) функции ж можно рассматривать как набор всех возможных контекстов для DCOP. Поэтому в оставшейся части этой статьи мы можем использовать понятие контекста (т.е., то функция) в качестве входа в функция.

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

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

В раскраска графика проблема в следующем: учитывая график и набор цветов назначить каждому вершина, , цвет, , такое, что количество соседних вершин одного цвета минимизировано.

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

Таким образом, цель состоит в том, чтобы минимизировать .

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

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

Чтобы закодировать эту проблему как DCOP, для каждого создать одну переменную со связанным доменом . Затем для всех возможных контекстов :

куда функция такая, что

Алгоритмы

Алгоритмы 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. ^ ""обозначает набор мощности из
  2. ^ "" и ""обозначают Декартово произведение.
  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

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