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

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

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

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

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

Определения

DCOP

Основными ингредиентами проблемы DCOP являются агенты и переменные . Важно отметить, что каждая переменная принадлежит агенту; именно это делает проблему распределенной. Формально DCOP представляет собой кортеж. $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$ , где:

$A$ это набор агентов , $\{a_{1},\dots ,a_{|A|}\}$ .
$V$ это набор переменных , $\{v_{1},v_{2},\dots ,v_{|V|}\}$ .
${\mathfrak {D}}$ ${\mathfrak {D}}$ набор переменных-доменов , $\{D_{1},D_{2},\dots ,D_{|V|}\}$ , где каждый $D_{j}\in {\mathfrak {D}}$ $D_{j}\in {\mathfrak {D}}$ — конечное множество, содержащее возможные значения переменной $v_{j}$ $v_ {j}$ .
- Если $D_{j}\in {\mathfrak {D}}$ содержит только два значения (например, 0 или 1), тогда $v_{j}$ называется бинарной переменной .
$f$ $е$ – функция стоимости . Это функция ^[1] $f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R}$ $f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R}$ который сопоставляет каждое возможное частичное присвоение со стоимостью. Обычно лишь несколько значений $f$ $е$ ненулевые и представлены в виде списка кортежей, которым присвоено ненулевое значение. Каждый такой кортеж называется ограничением . Каждое ограничение $C$ $C$ в этом наборе есть функция $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ присвоение реального значения каждому возможному назначению переменных. Некоторые специальные виды ограничений:
- Унарные ограничения - ограничения на одну переменную, т.е. $f_{C}:D_{j}\to \mathbb {R}$ для некоторых $v_{j}\in V$ .
- Бинарные ограничения – ограничения на две переменные, т.е. $f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R}$ для некоторых $v_{j_{1}},v_{j_{2}}\in V$ .
$\alpha$ – это функция собственности . Это функция $\alpha :V\to A$ сопоставление каждой переменной со связанным с ней агентом. $\alpha (v_{j})\mapsto a_{i}$ означает, что переменная $v_{j}$ «принадлежит» агенту $a_{i}$ . Это означает, что это агент $a_{i}$ ответственность за присвоение значения переменной $v_{j}$ . Обратите внимание, что $\alpha$ не обязательно является инъекцией , т. е. один агент может владеть более чем одной переменной. Это также не обязательно является сюръекцией , т. е. некоторые агенты могут не иметь переменных.
$\eta$ является целевой функцией . Это оператор , который агрегирует все отдельные $f$ затраты на все возможные назначения переменных. Обычно это достигается суммированием: $\eta (f)\mapsto \sum _{s\in \bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}}f(s).$

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

Задания

Присвоение значения представляет собой пару $(v_{j},d_{j})$ где $d_{j}$ является элементом домена $D_{j}$ .

Частичное присвоение — это набор присвоений значений, где каждое $v_{j}$ появляется не более одного раза. Его еще называют контекстом. Это можно рассматривать как функцию, сопоставляющую переменные в DCOP с их текущими значениями: $t:V\to (D\in {\mathfrak {D}})\cup \{\emptyset \}.$ Обратите внимание, что контекст по сути является частичным решением и не обязательно должен содержать значения для каждой переменной в задаче; поэтому, $t(v_{i})\mapsto \emptyset$ подразумевает, что агент $\alpha (v_{i})$ еще не присвоил значение переменной $v_{i}$ . Учитывая это представление, « домен » (то есть набор входных значений) функции f можно рассматривать как набор всех возможных контекстов DCOP. Поэтому в оставшейся части этой статьи мы можем использовать понятие контекста (т. е. $t$ функция) в качестве входных данных для $f$ функция.

Полное задание – это задание, в котором каждый $v_{j}$ появляется ровно один раз, то есть присваиваются все переменные. Его еще называют решением DCOP.

Оптимальное решение – это полное задание, при котором целевая функция $\eta (f)$ оптимизирован (т.е. максимизирован или минимизирован, в зависимости от типа проблемы).

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

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

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

Задача о раскраске графа состоит в следующем: дан граф $G=\langle N,E\rangle$ и набор цветов $C$ , назначьте каждую вершину , $n\subset N$ , цвет, $c\leq C$ , так что количество смежных вершин одного цвета сведено к минимуму.

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

Задача о распределенных множественных рюкзаках

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

Чтобы закодировать эту проблему как DCOP, для каждого $i\in I$ создать одну переменную $v_{i}\in V$ со связанным доменом $D_{i}=K$ . Тогда для всех возможных контекстов $t$ : $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}}$ где $r(t,k)$ представляет общий вес, присвоенный контекстом $t$ рюкзак $k$ : $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 использует поиск по принципу «сначала лучшее», асинхронную синхронизацию, двухточечную связь между соседними агентами в графе ограничений и дерево ограничений в качестве основной топологии связи.

Название алгоритма	Год введения	Сложность памяти	Количество сообщений	Корректность (информатика) / Полнота (логика)	Реализации
АБТ ^{[ нужна ссылка ]} Асинхронный возврат	1992	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	Примечание: статический заказ завершен.	^{[ нужна ссылка ]}
АВК ^{[ нужна ссылка ]} Асинхронное слабое обязательство	1994	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	Примечание: переупорядочение, быстрое, полное (только с экспоненциальным пространством)	^{[ нужна ссылка ]}
администратор баз данных Алгоритм распределенного прорыва	1995	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	Примечание: неполное, но быстрое	ФРОДО версия 1 ^{[ постоянная мертвая ссылка ]}
СинкББ ^[4] Синхронная ветвь и граница	1997	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	Полный, но медленный
ИБР Итеративный распределенный прорыв	1997	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	Примечание: неполное, но быстрое
ААС ^{[ нужна ссылка ]} Асинхронный агрегированный поиск	2000	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	агрегирование значений в ABT	^{[ нужна ссылка ]}
ДФК ^{[ нужна ссылка ]} Распределенная прямая цепочка	2000	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	Примечание: низкий, сравним с ABT.	^{[ нужна ссылка ]}
АБТР ^{[ нужна ссылка ]} Асинхронный возврат с переупорядочением	2001	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	Примечание: переупорядочение в ABT с ограниченными товарами.	^{[ нужна ссылка ]}
ДМАК ^{[ нужна ссылка ]} Поддержание асинхронной согласованности	2001	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	Примечание: самый быстрый алгоритм	^{[ нужна ссылка ]}
Безопасные вычисления с полудоверенными серверами ^{[ нужна ссылка ]}	2002	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	Примечание. Безопасность возрастает с увеличением количества надежных серверов.	^{[ нужна ссылка ]}
Безопасные многосторонние вычисления для решения DisCSP (MPC-DisCSP1-MPC-DisCSP4) ^{[ нужна ссылка ]}	2003	^{[ нужна ссылка ]}	^{[ нужна ссылка ]}	Примечание: безопасно, если 1/2 участников заслуживают доверия.	^{[ нужна ссылка ]}
Усыновить Асинхронный возврат ^[5]	2003	Полиномиальный (или любой пространственный ^[6])	Экспоненциальный	Проверенный	Эталонная реализация: принять. Архивировано 16 сентября 2006 г. на Wayback Machine. ДКОполис ( GNU LGPL ) ФРОДО ( AGPL )
ОптАПО Асинхронное частичное наложение ^[7]	2004	Полиномиальный	Экспоненциальный	Доказано, но доказательство полноты было оспорено ^[8]	Эталонная реализация: «ОптАПО» . Центр искусственного интеллекта . НИИ Интернешнл . Архивировано из оригинала 15 июля 2007 г. ДКОполис ( GNU LGPL ); В разработке
ДПОП Процедура оптимизации распределенного псевдодерева ^[9]	2005	Экспоненциальный	Линейный	Проверенный	Эталонная реализация: FRODO ( AGPL ) ДКОполис ( GNU LGPL )
НЦББ Ветвь и граница без обязательств ^[10]	2006	Полиномиальный (или любой пространственный ^[11])	Экспоненциальный	Проверенный	Эталонная реализация: не опубликована. ДКОполис ( GNU LGPL )
КФЛ Обучение без общения ^[12]	2013	Линейный	Нет Примечание: сообщения не отправляются, но предполагается, что известно об удовлетворении локального ограничения.	Неполный

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

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

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

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

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

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

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

Простой способ решения ADCOP — заменить каждое ограничение $f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}$ с ограничением $f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R}$ , что равно сумме функций $f_{C}^{1}+\cdots +f_{C}^{k}$ . Однако это решение требует от агентов раскрытия своих функций затрат. Часто это нежелательно из соображений конфиденциальности. ^[14]^[15]^[16]

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

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

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

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

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

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

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

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

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

См. также

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

^ " $\times$ «или «×» обозначает декартово произведение .
^ Нетцер, Арнон; Мейзельс, Амнон; Живан, Рой (01 марта 2016 г.). «Минимизация распределенной зависти к распределению ресурсов» . Автономные агенты и мультиагентные системы . 30 (2): 364–402. дои : 10.1007/s10458-015-9291-7 . ISSN 1387-2532 . S2CID 13834856 .
^ Jump up to: ^а ^б Да, Уильям; Фельнер, Ариэль; Кениг, Свен (2008), «BnB-ADOPT: асинхронный алгоритм DCOP ветвей и границ» , Труды седьмой международной совместной конференции по автономным агентам и мультиагентным системам , vol. 2, стр. 591–8, ISBN. 9780981738116
^ Хираяма, Кацутоши; Ёко, Макото (1997). «Задача распределенного частичного удовлетворения ограничений» . В Смолке, Герт (ред.). Принципы и практика программирования с ограничениями-CP97 . Конспекты лекций по информатике. Том. 1330. Берлин, Гейдельберг: Springer. стр. 222–236. дои : 10.1007/BFb0017442 . ISBN 978-3-540-69642-1 .
^ Первоначально опубликованная версия Adopt не содержала информации, см. Моди, Прагнеш Джей; Шен, Вэй-Мин; Тамбе, Милинд; Йоко, Макото (2003), «Асинхронный полный метод оптимизации с распределенными ограничениями» (PDF) , Материалы второй международной совместной конференции по автономным агентам и мультиагентным системам , ACM Press, стр. 161–168, заархивировано из оригинала (PDF) ) 4 ноября 2019 г. , получено 7 сентября 2009 г. Первоначальная версия Adopt позже была расширена для информирования, то есть для использования оценок стоимости решения, чтобы сфокусировать поиск и ускорить работу, см. Али, Сайед; Кениг, Свен; Тамбе, Милинд (2005), «Методы предварительной обработки для ускорения алгоритма DCOP ADOPT» (PDF) , Материалы четвертой международной совместной конференции по автономным агентам и мультиагентным системам , ACM Press, стр. 1041–8, doi : 10.1145/1082473.1082631 , ISBN 1595930930 , S2CID 10882572 , заархивировано из оригинала (PDF) 7 июля 2010 г. , получено 7 сентября 2009 г. Это расширение Adopt обычно используется в качестве эталонной реализации Adopt.
^ Мацуи, Тошихиро; Мацуо, Хироши; Ивата, Акира (февраль 2005 г.), «Эффективный метод для асинхронного алгоритма оптимизации с распределенными ограничениями» (PDF) , Proceedings of Artificial Intelligence and Applications , стр. 727–732, CiteSeerX 10.1.1.408.7230
^ Мейллер, Роджер; Лессер, Виктор (2004), «Решение задач оптимизации с распределенными ограничениями с использованием кооперативного посредничества» (PDF) , Труды Третьей международной совместной конференции по автономным агентам и мультиагентным системам , Компьютерное общество IEEE , стр. 438–445, ISBN 1581138644 ^{[ постоянная мертвая ссылка ]}
^ Гриншпоун, Таль; Зазон, Моше; Бишток, Максим; Мейзелс, Амнон (2007), «Проблема завершения алгоритма APO» (PDF) , Материалы восьмого международного семинара по рассуждениям о распределенных ограничениях , стр. 117–124.
^ Петку, Адриан; Фалтингс, Бой (август 2005 г.), «DPOP: масштабируемый метод мультиагентной оптимизации ограничений» , Труды 19-й Международной совместной конференции по искусственному интеллекту, IJCAI 2005, Эдинбург, Шотландия, стр. 266-271.
^ Чечетка, Антон; Сикара, Катя (май 2006 г.), «Ветвь без обязательств и ограниченный поиск для оптимизации с распределенными ограничениями» (PDF) , Материалы пятой международной совместной конференции по автономным агентам и мультиагентным системам , стр. 1427–9, doi : 10.1145/1160633.1160900 , ISBN 1595933034 , S2CID 43918609
^ Чечетка, Антон; Сикара, Катя (март 2006 г.), «Алгоритм в любом пространстве для оптимизации с распределенными ограничениями» (PDF) , Материалы весеннего симпозиума AAAI по распределенному планированию и управлению расписанием
^ Даффи, КР; Лейт, DJ (август 2013 г.), «Удовлетворение децентрализованных ограничений», Транзакции IEEE/ACM в сети , 21 (4): 1298–1308, arXiv : 1103.3240 , doi : 10.1109/TNET.2012.2222923 , S2CID 11504393
^ Jump up to: ^а ^б ^с Гриншпоун, Т.; Грубштейн А.; Живан, Р.; Нетцер, А.; Мейзельс, А. (30 июля 2013 г.). «Задачи оптимизации с асимметричными распределенными ограничениями» . Журнал исследований искусственного интеллекта . 47 : 613–647. arXiv : 1402.0587 . дои : 10.1613/jair.3945 . ISSN 1076-9757 .
^ Гринштадт, Рэйчел; Пирс, Джонатан П.; Тамбе, Милинд (16 июля 2006 г.). «Анализ потери конфиденциальности при оптимизации распределенных ограничений» . Материалы 21-й Национальной конференции по искусственному интеллекту. Том 1 . АААИ'06. Бостон, Массачусетс: AAAI Press: 647–653. ISBN 978-1-57735-281-5 .
^ Махешваран, Раджив Т.; Пирс, Джонатан П.; Боуринг, Эмма; Варакантам, Прадип; Тамбе, Милинд (01 июля 2006 г.). «Потеря конфиденциальности в рассуждениях о распределенных ограничениях: количественная основа анализа и ее приложений» . Автономные агенты и мультиагентные системы . 13 (1): 27–60. дои : 10.1007/s10458-006-5951-y . ISSN 1573-7454 . S2CID 16962945 .
^ Ёко, Макото; Сузуки, Котаро; Хираяма, Кацутоши (2002). «Удовлетворение безопасных распределенных ограничений: достижение соглашения без раскрытия частной информации» . В Ван Хентенрик, Паскаль (ред.). Принципы и практика программирования с ограничениями – CP 2002 . Конспекты лекций по информатике. Том. 2470. Берлин, Гейдельберг: Springer. стр. 387–401. дои : 10.1007/3-540-46135-3_26 . ISBN 978-3-540-46135-7 .
^ Раджив Т. Махешваран, Милинд Тамбе, Эмма Боуринг, Джонатан П. Пирс, Прадип Варакантам (2004). «Применение DCOP в реальном мире: эффективные комплексные решения для распределенного планирования нескольких событий» . www.computer.org . Проверено 12 апреля 2021 г. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Jump up to: ^а ^б Живан, Рой; Грубштейн, Алон; Фридман, Михал; Мейзельс, Амнон (4 июня 2012 г.). «Частичное сотрудничество в мультиагентном поиске» . Материалы 11-й Международной конференции по автономным агентам и мультиагентным системам - Том 3 . ААМАС '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), Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы , Нью-Йорк: Издательство Кембриджского университета , 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

[1] " $\times$ «или «×» обозначает декартово произведение .

[:2-2] Нетцер, Арнон; Мейзельс, Амнон; Живан, Рой (01 марта 2016 г.). «Минимизация распределенной зависти к распределению ресурсов» . Автономные агенты и мультиагентные системы . 30 (2): 364–402. дои : 10.1007/s10458-015-9291-7 . ISSN 1387-2532 . S2CID 13834856 .

[yeoh06-3] Jump up to: ^а ^б Да, Уильям; Фельнер, Ариэль; Кениг, Свен (2008), «BnB-ADOPT: асинхронный алгоритм DCOP ветвей и границ» , Труды седьмой международной совместной конференции по автономным агентам и мультиагентным системам , vol. 2, стр. 591–8, ISBN. 9780981738116

[4] Хираяма, Кацутоши; Ёко, Макото (1997). «Задача распределенного частичного удовлетворения ограничений» . В Смолке, Герт (ред.). Принципы и практика программирования с ограничениями-CP97 . Конспекты лекций по информатике. Том. 1330. Берлин, Гейдельберг: Springer. стр. 222–236. дои : 10.1007/BFb0017442 . ISBN 978-3-540-69642-1 .

[5] Первоначально опубликованная версия Adopt не содержала информации, см. Моди, Прагнеш Джей; Шен, Вэй-Мин; Тамбе, Милинд; Йоко, Макото (2003), «Асинхронный полный метод оптимизации с распределенными ограничениями» (PDF) , Материалы второй международной совместной конференции по автономным агентам и мультиагентным системам , ACM Press, стр. 161–168, заархивировано из оригинала (PDF) ) 4 ноября 2019 г. , получено 7 сентября 2009 г. Первоначальная версия Adopt позже была расширена для информирования, то есть для использования оценок стоимости решения, чтобы сфокусировать поиск и ускорить работу, см. Али, Сайед; Кениг, Свен; Тамбе, Милинд (2005), «Методы предварительной обработки для ускорения алгоритма DCOP ADOPT» (PDF) , Материалы четвертой международной совместной конференции по автономным агентам и мультиагентным системам , ACM Press, стр. 1041–8, doi : 10.1145/1082473.1082631 , ISBN 1595930930 , S2CID 10882572 , заархивировано из оригинала (PDF) 7 июля 2010 г. , получено 7 сентября 2009 г. Это расширение Adopt обычно используется в качестве эталонной реализации Adopt.

[matsui05efficient-6] Мацуи, Тошихиро; Мацуо, Хироши; Ивата, Акира (февраль 2005 г.), «Эффективный метод для асинхронного алгоритма оптимизации с распределенными ограничениями» (PDF) , Proceedings of Artificial Intelligence and Applications , стр. 727–732, CiteSeerX 10.1.1.408.7230

[mailler04solving-7] Мейллер, Роджер; Лессер, Виктор (2004), «Решение задач оптимизации с распределенными ограничениями с использованием кооперативного посредничества» (PDF) , Труды Третьей международной совместной конференции по автономным агентам и мультиагентным системам , Компьютерное общество IEEE , стр. 438–445, ISBN 1581138644 ^{[ постоянная мертвая ссылка ]}

[dcr07proceedings-8] Гриншпоун, Таль; Зазон, Моше; Бишток, Максим; Мейзелс, Амнон (2007), «Проблема завершения алгоритма APO» (PDF) , Материалы восьмого международного семинара по рассуждениям о распределенных ограничениях , стр. 117–124.

[petcu04distributed-9] Петку, Адриан; Фалтингс, Бой (август 2005 г.), «DPOP: масштабируемый метод мультиагентной оптимизации ограничений» , Труды 19-й Международной совместной конференции по искусственному интеллекту, IJCAI 2005, Эдинбург, Шотландия, стр. 266-271.

[chechetka06no-10] Чечетка, Антон; Сикара, Катя (май 2006 г.), «Ветвь без обязательств и ограниченный поиск для оптимизации с распределенными ограничениями» (PDF) , Материалы пятой международной совместной конференции по автономным агентам и мультиагентным системам , стр. 1427–9, doi : 10.1145/1160633.1160900 , ISBN 1595933034 , S2CID 43918609

[chechetka06anyspace-11] Чечетка, Антон; Сикара, Катя (март 2006 г.), «Алгоритм в любом пространстве для оптимизации с распределенными ограничениями» (PDF) , Материалы весеннего симпозиума AAAI по распределенному планированию и управлению расписанием

[cfl-12] Даффи, КР; Лейт, DJ (август 2013 г.), «Удовлетворение децентрализованных ограничений», Транзакции IEEE/ACM в сети , 21 (4): 1298–1308, arXiv : 1103.3240 , doi : 10.1109/TNET.2012.2222923 , S2CID 11504393

[:0-13] Jump up to: ^а ^б ^с Гриншпоун, Т.; Грубштейн А.; Живан, Р.; Нетцер, А.; Мейзельс, А. (30 июля 2013 г.). «Задачи оптимизации с асимметричными распределенными ограничениями» . Журнал исследований искусственного интеллекта . 47 : 613–647. arXiv : 1402.0587 . дои : 10.1613/jair.3945 . ISSN 1076-9757 .

[14] Гринштадт, Рэйчел; Пирс, Джонатан П.; Тамбе, Милинд (16 июля 2006 г.). «Анализ потери конфиденциальности при оптимизации распределенных ограничений» . Материалы 21-й Национальной конференции по искусственному интеллекту. Том 1 . АААИ'06. Бостон, Массачусетс: AAAI Press: 647–653. ISBN 978-1-57735-281-5 .

[15] Махешваран, Раджив Т.; Пирс, Джонатан П.; Боуринг, Эмма; Варакантам, Прадип; Тамбе, Милинд (01 июля 2006 г.). «Потеря конфиденциальности в рассуждениях о распределенных ограничениях: количественная основа анализа и ее приложений» . Автономные агенты и мультиагентные системы . 13 (1): 27–60. дои : 10.1007/s10458-006-5951-y . ISSN 1573-7454 . S2CID 16962945 .

[16] Ёко, Макото; Сузуки, Котаро; Хираяма, Кацутоши (2002). «Удовлетворение безопасных распределенных ограничений: достижение соглашения без раскрытия частной информации» . В Ван Хентенрик, Паскаль (ред.). Принципы и практика программирования с ограничениями – CP 2002 . Конспекты лекций по информатике. Том. 2470. Берлин, Гейдельберг: Springer. стр. 387–401. дои : 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: несколько имен: список авторов ( ссылка )

[:1-18] Jump up to: ^а ^б Живан, Рой; Грубштейн, Алон; Фридман, Михал; Мейзельс, Амнон (4 июня 2012 г.). «Частичное сотрудничество в мультиагентном поиске» . Материалы 11-й Международной конференции по автономным агентам и мультиагентным системам - Том 3 . ААМАС '12. 3 . Валенсия, Испания: Международный фонд автономных агентов и мультиагентных систем: 1267–1268. ISBN 978-0-9817381-3-0 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]