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

Распределенная оптимизация ограничений ( 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}}$
  • Если содержит только два значения (например, 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}$
  • Бинарные ограничения — ограничения по двум переменным, т. е. для некоторых . ${\displaystyle f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R} }$ ${\displaystyle v_{j_{1}},v_{j_{2}}\in V}$
• ${\displaystyle \alpha }$является функцией владения . Это функция, сопоставляющая каждую переменную с ее связанным агентом. означает, что переменная «принадлежит» агенту . Это подразумевает, что агент несет ответственность за назначение значения переменной . Обратите внимание, что это не обязательно инъекция , т. е. один агент может владеть более чем одной переменной. Это также не обязательно сюръекция , т. е. некоторые агенты могут не владеть ни одной переменной. ${\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}}$

Частичное назначение — это набор назначений значений, где каждое появляется не более одного раза. Его также называют контекстом. Его можно рассматривать как функцию, отображающую переменные в 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}$

Полное назначение — это назначение, в котором каждая переменная появляется ровно один раз, то есть все переменные назначены. Это также называется решением 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, если обеим связанным переменным назначен один и тот же цвет: Таким образом, цель состоит в том, чтобы минимизировать . ${\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, для каждого создайте одну переменную с соответствующим доменом . Затем для всех возможных контекстов : где представляет собой общий вес, назначенный контекстом рюкзаку : ${\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]

• Добавьте бинарную переменную v _ij для каждого агента i и элемента j . Значение переменной равно "1", если агент получает элемент, и "0" в противном случае. Переменная принадлежит агенту i .
• Чтобы выразить ограничение, согласно которому каждый элемент предоставляется не более чем одному агенту, добавьте бинарные ограничения для каждых двух различных переменных, относящихся к одному и тому же элементу, с бесконечной стоимостью, если обе переменные одновременно равны «1», и нулевой стоимостью в противном случае.
• Чтобы выразить ограничение, согласно которому все элементы должны быть распределены, добавьте n -арное ограничение для каждого элемента (где n — количество агентов) с бесконечной стоимостью, если ни одна переменная, связанная с этим элементом, не равна «1».

Другие приложения

DCOP применялся к другим проблемам, таким как:

• координация мобильных датчиков;
• планирование встреч и задач.

Алгоритмы

Алгоритмы DCOP можно классифицировать несколькими способами: ^[3]

• Полнота — алгоритмы полного поиска находят оптимальное решение, в отличие от алгоритмов локального поиска, находящих локальный оптимум .
• Стратегия поиска — поиск по первому наилучшему совпадению или поиск в глубину методом ветвей и границ;
• Синхронизация между агентами — синхронная или асинхронная;
• Связь между агентами — «точка-точка» с соседями в графе ограничений или широковещательная передача;
• Топология связи — цепочка или дерево.

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

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

Асимметричный DCOP

Асимметричный DCOP — это расширение DCOP, в котором стоимость каждого ограничения может быть разной для разных агентов. Вот некоторые примеры приложений: ^[13]

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

Одним из способов представления ADCOP является представление ограничений в виде функций: $${\displaystyle f_{C}:D_{1}\times \dots \times D_{k}\to \mathbb {R} ^{k}}$$

Здесь для каждого ограничения существует не одна стоимость, а вектор стоимости — по одной для каждого агента, вовлеченного в ограничение. Вектор стоимости имеет длину k , если каждая переменная принадлежит разным агентам; если две или более переменных принадлежат одному агенту, то вектор стоимости короче — существует одна стоимость для каждого вовлеченного агента , а не для каждой переменной.

Подходы к решению ADCOP

Простой способ решения 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}}$

Другой подход называется Private Events as Variables (PEAV). ^[17] В этом подходе каждая переменная владеет, в дополнение к своим собственным переменным, также «зеркальными переменными» всех переменных, принадлежащих ее соседям в сети ограничений. Существуют дополнительные ограничения (со стоимостью бесконечности), которые гарантируют, что зеркальные переменные равны исходным переменным. Недостатком этого метода является то, что количество переменных и ограничений намного больше исходного, что приводит к более высокому времени выполнения.

Третий подход заключается в адаптации существующих алгоритмов, разработанных для DCOP, к структуре ADCOP. Это было сделано как для алгоритмов полного поиска, так и для алгоритмов локального поиска. ^[13]

Сравнение со стратегическими играми

Структура задачи ADCOP похожа на игровую концепцию одновременной игры . В обоих случаях есть агенты, которые контролируют переменные (в теории игр переменные — это возможные действия или стратегии агентов). В обоих случаях каждый выбор переменных разными агентами приводит к разным выплатам для каждого агента. Однако есть фундаментальное различие: ^[13]

• В одновременной игре агенты эгоистичны - каждый из них хочет максимизировать свою собственную полезность (или минимизировать свои собственные издержки). Поэтому наилучшим результатом, к которому можно стремиться в такой обстановке, является равновесие - ситуация, в которой ни один агент не может в одностороннем порядке увеличить свою собственную выгоду.
• В ADCOP агенты считаются кооперативными: они действуют в соответствии с протоколом, даже если это снижает их собственную полезность. Поэтому цель более сложная: мы хотели бы максимизировать сумму полезностей (или минимизировать сумму затрат). Равновесие Нэша примерно соответствует локальному оптимуму этой задачи, в то время как мы ищем глобальный оптимум.

Частичное сотрудничество

Существуют некоторые промежуточные модели, в которых агенты частично кооперативны : они готовы уменьшить свою полезность, чтобы помочь глобальной цели, но только если их собственные издержки не слишком высоки. Примером частично кооперативных агентов являются сотрудники фирмы. С одной стороны, каждый сотрудник хочет максимизировать свою собственную полезность; с другой стороны, они также хотят внести свой вклад в успех фирмы. Поэтому они готовы помогать другим или выполнять некоторые другие трудоемкие задачи, которые помогают фирме, пока это не слишком обременительно для них. Вот некоторые модели для частично кооперативных агентов: ^[18]

• Гарантированная личная выгода : агенты соглашаются действовать ради глобального блага, если их собственная полезность по крайней мере столь же высока, как и в некооперативной обстановке (т. е. конечный результат должен быть улучшением по Парето исходного состояния).
• Лямбда-кооперация : есть параметр . Агенты соглашаются действовать ради глобального блага, если их собственная полезность по крайней мере так же высока, как и их некооперативная полезность. ${\displaystyle \lambda \in [0,1]}$ ${\displaystyle (1-\lambda )}$

Решение таких частично кооперативных ADCOP требует адаптации алгоритмов ADCOP. ^[18]

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

• Проблема удовлетворения ограничений
• Распределенный алгоритм
• Проектирование распределенного алгоритмического механизма

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

1. " " или "×" обозначает декартово произведение . ${\displaystyle \times }$
2. Нецер, Арнон; Майзелс, Амнон; Зиван, Ройе (2016-03-01). «Минимизация распределенной зависти для распределения ресурсов». Автономные агенты и многоагентные системы . 30 (2): 364–402. doi :10.1007/s10458-015-9291-7. ISSN  1387-2532. S2CID  13834856.
3. Yeoh, William; Felner, Ariel; Koenig, Sven (2008), "BnB-ADOPT: асинхронный алгоритм ветвей и границ DCOP", Труды Седьмой международной совместной конференции по автономным агентам и многоагентным системам , т. 2, стр. 591–8, ISBN 9780981738116
4. Хираяма, Кацутоши; Йоко, Макото (1997). "Распределенная проблема частичного удовлетворения ограничений". В Смолька, Герт (ред.). Принципы и практика программирования ограничений-CP97 . Конспект лекций по информатике. Том 1330. Берлин, Гейдельберг: Springer. стр. 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) , Труды второй международной совместной конференции по автономным агентам и многоагентным системам , ACM Press, стр. 161–168, архивировано из оригинала (PDF) 2019-11-04 , извлечено 2009-09-07. Первоначальная версия Adopt была позже расширена, чтобы быть информированной, то есть использовать оценки затрат на решение, чтобы сосредоточить свой поиск и работать быстрее, см. Ali, Syed; Koenig, Sven; Tambe, Milind (2005), "Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT" (PDF) , Труды четвертой международной совместной конференции по автономным агентам и многоагентным системам , ACM Press, стр. 1041–8, doi :10.1145/1082473.1082631, ISBN 1595930930, S2CID  10882572, заархивировано из оригинала (PDF) 2010-07-07 , извлечено 2009-09-07. Это расширение Adopt обычно используется как эталонная реализация Adopt.
6. Мацуи, Тосихиро; Мацуо, Хироши; Ивата, Акира (февраль 2005 г.), «Эффективный метод асинхронного распределенного алгоритма оптимизации ограничений» (PDF) , Труды по искусственному интеллекту и приложениям , стр. 727–732, CiteSeerX 10.1.1.408.7230 
7. Мейлер, Роджер; Лессер, Виктор (2004), «Решение задач оптимизации распределенных ограничений с использованием кооперативного посредничества» (PDF) , Труды Третьей международной совместной конференции по автономным агентам и многоагентным системам , IEEE Computer Society , стр. 438–445, ISBN 1581138644^{[ постоянная мертвая ссылка ‍ ]}
8. Гриншпун, Таль; Зазон, Моше; Биншток, Максим; Мейселс, Амнон (2007), «Проблема завершения алгоритма APO» (PDF) , Труды Восьмого международного семинара по рассуждениям с распределенными ограничениями , стр. 117–124
9. Петку, Адриан; Фалтингс, Бой (август 2005 г.), «DPOP: масштабируемый метод оптимизации ограничений для нескольких агентов», Труды 19-й Международной совместной конференции по искусственному интеллекту, IJCAI 2005, Эдинбург, Шотландия, стр. 266-271
10. Чечетка, Антон; Сикара, Катя (май 2006 г.), «Поиск ветвей и границ без обязательств для оптимизации распределенных ограничений» (PDF) , Труды Пятой международной совместной конференции по автономным агентам и многоагентным системам , стр. 1427–9, doi :10.1145/1160633.1160900, ISBN 1595933034, S2CID  43918609
11. Чечетка, Антон; Сикара, Катя (март 2006 г.), «Алгоритм любого пространства для оптимизации распределенных ограничений» (PDF) , Труды весеннего симпозиума AAAI по распределенному управлению планами и расписаниями
12. Даффи, KR; Лейт, DJ (август 2013 г.), «Децентрализованное удовлетворение ограничений», IEEE/ACM Transactions on Networking , 21 (4): 1298–1308, arXiv : 1103.3240 , doi : 10.1109/TNET.2012.2222923, S2CID  11504393
13. Гриншпун, Т.; Грубштейн, А.; Зиван, Р.; Нецер, А.; Мейселс, А. (2013-07-30). «Асимметричные распределенные задачи оптимизации ограничений». Журнал исследований искусственного интеллекта . 47 : 613–647. arXiv : 1402.0587 . doi : 10.1613/jair.3945 . ISSN  1076-9757.
14. Гринштадт, Рэйчел; Пирс, Джонатан П.; Тамбе, Милинд (2006-07-16). «Анализ потери конфиденциальности при оптимизации распределенных ограничений». Труды 21-й Национальной конференции по искусственному интеллекту — Том 1. AAAI'06. Бостон, Массачусетс: AAAI Press: 647–653. ISBN 978-1-57735-281-5.
15. Махешваран, Раджив Т.; Пирс, Джонатан П.; Боуринг, Эмма; Варакантам, Прадип; Тамбе, Милинд (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. Берлин, Гейдельберг: Springer. стр. 387–401. doi :10.1007/3-540-46135-3_26. ISBN 978-3-540-46135-7.
17. Раджив Т. Махешваран, Милинд Тамбе, Эмма Боуринг, Джонатан П. Пирс, Прадип Варакантам (2004). «Перевод DCOP в реальный мир: эффективные комплексные решения для распределенного многособытийного планирования». www.computer.org . Получено 12 апреля 2021 г.{{cite web}}: CS1 maint: multiple names: authors list (link)
18. Zivan, Roie; Grubshtein, Alon; Friedman, Michal; Meisels, Amnon (2012-06-04). "Частичное сотрудничество в многоагентном поиске". Труды 11-й Международной конференции по автономным агентам и многоагентным системам - Том 3. AAMAS '12. 3. Валенсия, Испания: Международный фонд автономных агентов и многоагентных систем: 1267–1268. ISBN 978-0-9817381-3-0.

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

• Фиоретто, Фердинандо; Понтелли, Энрико; Йео, Уильям (2018), «Проблемы и приложения оптимизации распределенных ограничений: обзор», Журнал исследований искусственного интеллекта , 61 : 623–698, arXiv : 1602.06347 , doi : 10.1613/jair.5565, S2CID  4503761
• Фалтингс, Бой (2006), «Распределенное программирование в ограничениях», в Уолш, Тоби (ред.), Справочник по программированию в ограничениях , Elsevier , ISBN 978-0-444-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), «Алгоритмы для удовлетворения распределенных ограничений: обзор», Автономные агенты и многоагентные системы , 3 (2): 185–207, doi :10.1023/A:1010078712316, S2CID  2139298