Контрактный сетевой протокол - Contract Net Protocol

В Контрактный сетевой протокол (CNP) - это протокол разделения задач в мультиагентные системы, представленный в 1980 г. Ридом Г. Смитом.[1] Он используется для распределения задач между автономными агентами. Это близко к протоколы закрытых аукционов. Он в основном полагается на Субподрядчик: менеджер предлагает задачу нескольким агентам. Последние вносят предложение, среди которого менеджер выбирает выделить задачу. Затем эту задачу можно разделить и передать на субподряд.

Формальное описание

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

  1. Протокол инициализируется менеджером, который отправляет конкурс предложений подрядчикам
  2. Подрядчики могут отправить либо предложение если они заинтересованы или отклонять если их нет. В этом предложении есть все элементы, необходимые менеджеру для выбора.
  3. Менеджер выбирает среди предложений наиболее подходящее и отправляет соответствующему исполнителю принимать. Он посылает отклонять другим подрядчикам, чтобы сообщить им о своем решении.
  4. После выполнения контракта подрядчик информирует менеджера, используя сообщить сообщение. Если есть результат для сообщения, он также передается через сообщить сообщение. Если подрядчик не может выполнить свое задание, он сообщает об этом менеджеру через Отмена сообщение.

Протокол Contract Net может быть представлен с помощью AUML формализм:

Схема AUML протокола Contract Net

Этот протокол может использоваться для реализации иерархических организаций, в которых менеджер назначает задачи подрядчикам, которые, в свою очередь, распадаются на задачи более низкого уровня и назначают их на более низкий уровень. Такой тип организации может использоваться, когда агенты действуют совместно, т.е. когда их цели идентичны. В этой ситуации можно убедиться, что подрядчики не лгут менеджеру, когда они делают свое предложение. Когда агенты конкурируют, протокол заканчивается организацией рынка, очень похожей на аукционы.[2]

Выполнение

Протокол был реализован ФИПА в ACL (Язык общения агента).[3]

Протокол Contract Net был реализован для различных задач и контекстов. В исходной статье описан пример использования сенсорной сети. Последующая работа показала свою полезность в этом контексте.[4] Он также использовался для распределения задач с несколькими роботами.[5] Он также использовался в качестве протокола переговоров на торговых площадках электронной коммерции. [6] и для цепочек поставок.[7]

Проблемы и расширения

Рид Дж. Смит выявил несколько проблем, связанных с его протоколом. В частности, он предлагает создавать только короткие сообщения и взаимодействовать только с агентами, которые могут иметь отношение к предлагаемой задаче, чтобы избежать перегрузки сетевого взаимодействия с точки зрения обмена сообщениями. Чтобы ограничить количество взаимодействий, в случае, если менеджер знает, с каким подрядчиком он хотел бы заключить договор, он может связаться с ним напрямую, чтобы сделать предложение, которое подрядчик может принять или нет.

Вторая проблема связана с занятостью подрядчика при большом количестве задач. Действительно, в этом случае менеджеру может быть сложно найти доступных подрядчиков. Чтобы решить эту проблему, подрядчик может ответить на запрос предложений, даже если он уже работает по другому контракту. Этот трюк можно использовать, чтобы предотвратить ситуацию, когда менеджер делает запрос предложений, не получив ответа, потому что все подрядчики заняты. В этом случае подрядчики добавляют к своему предложению момент, когда они будут готовы скрепить предложением от менеджера. Аналогичным образом в этой ситуации можно вести список всех доступных подрядчиков, чтобы менеджер мог сначала связаться с ними. Этот трюк позволяет избежать перегрузки сети из-за того, что менеджеры снова и снова рассылают запросы предложений всем агентам, гарантируя, что они в конечном итоге найдут подрядчика для выполнения предложенной задачи. Эта информация напрямую отправляется менеджерам подрядчиками.

Помимо расширений, предложенных автором, несколько работ расширили Contract Net Protocol. Одна из проблем, связанных с этим, заключается в том, что менеджер не может точно определить, что он ценит больше всего. Он должен выбрать среди предложений, которые он получает от подрядчиков. В случае, когда каждый подрядчик может сделать ряд предложений, это может привести к неоптимальным решениям. Для решения этой проблемы FIPA также предлагает итеративную версию протокола, в которой менеджер может сделать новый запрос предложений одним из ответивших на него подрядчиков и отказать другим, в конечном итоге приняв одного из них. Полученный протокол можно сравнить с протоколами повторных аукционов. В качестве CNP этот протокол может быть представлен как AUML диаграмма [8]

Схема AUML Iterated Contract Net Protocol

Другая проблема протокола фактически связана с этой задачей. В исходном протоколе подрядчик, который делает предложение, обязуется выполнить поставленную задачу, чего бы это ни стоило. Невыполнение задачи учитывается только через Отмена сообщение, информирующее менеджера о том, что задача не будет решаться без каких-либо санкций для исполнителя. В случае, когда агент эгоистичен, у него может быть стимул делать столько предложений, сколько они могут, и выполнять только самые выгодные из них. В контексте совместной работы агент не имеет возможности узнать, хорошо ли для всей системы отказ от одной задачи с целью ее перехода к другой. Расширение протокола было выпущено в 1995 году Туомасом Сандхольмом и Виктор Лессер чтобы учесть эти элементы и заранее определить обязательную стоимость, которую подрядчик должен заплатить, если он не может выполнить задачу.[9]

Рекомендации

  1. ^ Смит (декабрь 1980 г.). «Протокол Contract Net: высокоуровневое взаимодействие и управление в распределенном средстве решения проблем». Транзакции IEEE на компьютерах. С-29 (12): 1104–1113. Дои:10.1109 / TC.1980.1675516. ISSN  0018-9340.
  2. ^ Хорлинг, Брайан; Меньший, Виктор (11.11.2005). «Обзор многоагентных организационных парадигм». Обзор инженерии знаний. 19 (4): 281. Дои:10.1017 / S0269888905000317. ISSN  0269-8889.
  3. ^ «Спецификация протокола сетевого взаимодействия контракта FIPA». fipa.org. Получено 2019-04-09.
  4. ^ Chen, L .; Сюэ-песня, Q .; Ян, Й .; Gao, Z .; Цюй, З. (июль 2012 г.). «Алгоритм распределения задач на основе контрактной сети для беспроводной сенсорной сети». Симпозиум IEEE по компьютерам и коммуникациям 2012 г. (ISCC). С. 000600–000604. Дои:10.1109 / ISCC.2012.6249362. ISBN  978-1-4673-2713-8.
  5. ^ Грабовскис, Арвидс; Lavendelis, Egons; Лекна, Алексис (2012-11-08). «Экспериментальный анализ протокола контрактной сети при распределении задач с несколькими роботами». Прикладные компьютерные системы. 13 (1): 6–14. Дои:10.2478 / v10312-012-0001-7.
  6. ^ Сандхольм, Туомас (1993). «Внедрение протокола нетто контракта на основе расчета предельной стоимости» (PDF). AAAI-93 Протоколы. С. 256–262.
  7. ^ (Роджер) Цзяо, Цзяньсинь; Ты, Сяо; Кумар, Арун (июль 2006 г.). «Основанная на агентах структура для совместных переговоров в глобальной сети производственной цепочки поставок». Робототехника и компьютерно-интегрированное производство. 22 (3): 239–255. Дои:10.1016 / j.rcim.2005.04.003.
  8. ^ «Спецификация протокола сетевого взаимодействия FIPA с итерационным контрактом». fipa.org. Получено 2019-04-09.
  9. ^ Сандхольм, Туомас; Меньший, Виктор (1995). «Проблемы автоматизированных переговоров и электронной торговли: расширение контрактной сети» (PDF). Труды Первой Международной конференции по многоагентным системам. С. 328–335.

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