Сетевой протокол контракта
Contract Net Protocol (CNP) — это протокол разделения задач в многоагентных системах , представленный в 1980 году Ридом Г. Смитом. [1] Он используется для распределения задач между автономными агентами. Это близко к протоколам закрытых аукционов . В основном он опирается на Субподрядчика : менеджер предлагает задачу нескольким агентам. Последние вносят предложение, среди которого руководитель решает распределить задачу. Затем эту задачу можно разделить и передать субподрядчикам.
Формальное описание
[ редактировать ]Формализация протокола может быть осуществлена посредством теории речевых актов . В этом протоколе каждый агент может быть либо менеджером , либо подрядчиком.
- Протокол инициализируется менеджером, который отправляет запрос предложений . подрядчикам
- Подрядчики могут отправить либо предложение, если они заинтересованы, либо отказ, если они не заинтересованы. Данное предложение снабжено всеми элементами, необходимыми менеджеру для совершения своего выбора.
- Менеджер выбирает среди предложений наиболее подходящее и отправляет соответствующему исполнителю акцепт . Он отправляет отказ другим подрядчикам, чтобы сообщить им о своем решении.
- После завершения контракта подрядчик информирует менеджера с помощью информационного сообщения. Если есть результат для сообщения, он также сообщается через информационное сообщение. Если подрядчик не может выполнить свое задание, он информирует об этом менеджера посредством сообщения об отмене .
Протокол Contract Net можно представить с помощью формализма AUML :
Этот протокол можно использовать для реализации иерархических организаций, где менеджер назначает задачи подрядчикам, которые, в свою очередь, разлагаются на задачи более низкого уровня и назначают их на более низкий уровень. Этот тип организации может использоваться, когда агенты сотрудничают, т. е. когда их цели идентичны. В такой ситуации можно убедиться, что подрядчики не лгут менеджеру, делая свое предложение. Когда агенты конкурируют, протокол превращается в рыночную организацию, очень похожую на аукционы. [2]
Выполнение
[ редактировать ]Протокол реализован FIPA в ACL ( язык связи агентов). [3]
Протокол Contract Net был реализован для решения различных проблем и контекстов. В оригинальной статье описывается вариант использования сенсорной сети. Последующие работы показали его полезность в этом контексте. [4] Он также использовался для распределения задач между несколькими роботами. [5] Он также использовался в качестве протокола переговоров как на торговых площадках электронной коммерции, так и на торговых площадках. [6] и для цепочек поставок. [7]
Проблемы и расширения
[ редактировать ]Рид Дж. Смит выявил несколько проблем, связанных с протоколом. В частности, он предлагает создавать только короткие сообщения и взаимодействовать только с агентами, которые могут иметь отношение к предложенной задаче, чтобы не перегружать сетевое общение обмениваемыми сообщениями. Чтобы ограничить количество взаимодействий, в случае, если менеджер знает, с каким подрядчиком он хотел бы заключить контракт, он может связаться с ним напрямую, чтобы сделать предложение, которое подрядчик может принять или нет.
Второй вопрос связан с занятостью подрядчика, когда задач много. Действительно, в этом случае менеджеру может быть сложно найти доступных подрядчиков. Чтобы решить эту проблему, подрядчик может ответить на запрос предложений, даже если он уже работает по другому контракту. Этот трюк можно использовать, чтобы предотвратить ситуацию, когда менеджер объявляет конкурс предложений, не получая ответа, поскольку все подрядчики заняты. В этом случае подрядчики добавляют в свое предложение момент, когда они будут готовы заключить предложение от менеджера. Аналогично в этой ситуации можно вести список всех доступных подрядчиков, чтобы менеджер мог первым с ними связаться. Этот трюк позволяет избежать перегрузки сети из-за того, что менеджеры снова и снова рассылают запросы предложений всем агентам, гарантируя при этом, что они в конечном итоге найдут подрядчика для заключения контракта на предложенную задачу. Эту информацию подрядчики напрямую пересылают менеджерам.
Помимо расширений, предложенных автором, несколько работ расширили протокол Contract Net. Одна из проблем, возникающих в связи с этим, заключается в том, что менеджер не может точно определить, что он ценит больше всего. Ему придется выбирать среди предложений, которые он получает от подрядчиков. В случае, когда каждый подрядчик может внести ряд предложений, это может привести к неоптимальным решениям. Для решения этой проблемы FIPA также предлагает итерированную версию протокола, в которой менеджер может сделать новый запрос предложений одним из ответивших на него подрядчиков и отказать другим, в конечном итоге приняв одного из них. Полученный протокол можно сравнить с протоколами итерированных аукционов. Как и CNP, этот протокол можно представить в виде AUML. диаграммы [8]
Еще одна проблема протокола связана с этой задачей. В исходном протоколе подрядчик, вносящий предложение, обязуется выполнить задачу, по которой он сделал предложение, чего бы это ни стоило. Невыполнение задачи учитывается только посредством сообщения об отмене , информирующего менеджера о том, что задача не будет решена, без каких-либо санкций со стороны подрядчика. Таким образом, в случае, когда агент эгоистичен, у него может быть стимул сделать как можно больше предложений и выполнить только самые выгодные из них. В контексте совместной работы у агента нет возможности узнать, полезен ли для всей системы отказ от задачи, чтобы перейти к другой. Расширение протокола было выпущено в 1995 году Туомасом Сандхольмом и Виктором Лессером , чтобы принять во внимание эти элементы и заранее определить стоимость обязательств, которую подрядчик должен будет заплатить, если он не сможет выполнить задачу. [9]
Ссылки
[ редактировать ]- ^ Смит (декабрь 1980 г.). «Контрактный сетевой протокол: высокоуровневая связь и управление в распределенном решении проблем». Транзакции IEEE на компьютерах . С-29 (12): 1104–1113. дои : 10.1109/TC.1980.1675516 . ISSN 0018-9340 . S2CID 15267324 .
- ^ Хорлинг, Брайан; Лессер, Виктор (11 ноября 2005 г.). «Обзор многоагентных организационных парадигм». Обзор инженерии знаний . 19 (4): 281. дои : 10.1017/S0269888905000317 . ISSN 0269-8889 . S2CID 562855 .
- ^ «Спецификация протокола сетевого взаимодействия контрактов FIPA» . fipa.org . Проверено 9 апреля 2019 г.
- ^ Чен, Л.; Сюэ-сонг, Ц.; Ян, Ю.; Гао, З.; Цюй, З. (июль 2012 г.). «Алгоритм распределения задач на основе контрактной сети для беспроводной сенсорной сети». Симпозиум IEEE по компьютерам и коммуникациям (ISCC) 2012 г. стр. 000600–000604. дои : 10.1109/ISCC.2012.6249362 . ISBN 978-1-4673-2713-8 . S2CID 11799626 .
- ^ Грабовскис, Арвидс; Лавенделис, Эгонс; Лиекна, Алексис (08.11.2012). «Экспериментальный анализ протокола контрактной сети при распределении задач между несколькими роботами» . Прикладные компьютерные системы . 13 (1): 6–14. дои : 10.2478/v10312-012-0001-7 .
- ^ Сандхольм, Туомас (1993). «Реализация сетевого протокола контракта, основанная на расчетах предельных затрат» (PDF) . Слушания AAAI-93 . стр. 256–262.
- ^ (Роджер) Цзяо, Цзяньсинь; Ты, Сяо; Кумар, Арун (июль 2006 г.). «Агентская система для совместных переговоров в глобальной сети производственных цепочек поставок». Робототехника и компьютерно-интегрированное производство . 22 (3): 239–255. дои : 10.1016/j.rcim.2005.04.003 .
- ^ «Спецификация протокола сетевого взаимодействия итерированных контрактов FIPA» . fipa.org . Проверено 9 апреля 2019 г.
- ^ Сандхольм, Туомас; Лессер, Виктор (1995). «Проблемы автоматизированных переговоров и электронной коммерции: расширение структуры контрактной сети» (PDF) . Материалы Первой международной конференции по мультиагентным системам . стр. 328–335.