Протокол Contract Net

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

1. Декомпозиция основной задачи на более мелкие самостоятельные подзадачи.
2. Эффективное распределение подзадач между агентами-исполнителями.
3. Решение каждой отдельной подзадачи.
4. Синтез обобщённого решения исходной задачи.

При этом ни один агент не обладает полным объёмом данных или контролем над всем процессом решения. Задача контрактационной сети — решить второй пункт, а именно — распределить подзадачи между отдельными агентами^[1].

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

• если агент оценивает, что для него оптимальнее разложить задачу на подзадачи (по качеству или стоимости), и делегировать их другим агентам;
• если у агента недостаточно информации для решения задачи.

В таких случаях агент становится менеджером задачи и отправляет всем свободным агентам сообщение о новой задаче. Каждый получатель оценивает, соответствует ли задача его возможностям, и в случае соответствия отправляет менеджеру своё предложение по решению; агент может также проигнорировать это сообщение. Из числа полученных предложений менеджер выбирает оптимальное и поручает выполнение конкретному агенту, который становится исполнителем задачи.

Коммуникацию между агентами обеспечивает Contract Net Protocol — язык и набор правил, разработанный специально для организации распределения, отслеживания задач и ведения переговоров между агентами.

Средство коммуникации между агентами в контрактной сети было предложено Ридом Дж. Смитом в 1980 году. На его основе создана современная версия протокола, утверждённая организацией FIPA в 2002 году^[2]. Это высокоуровневый протокол, который определяет семантику сообщений между агентами. Низкоуровневые вопросы передачи сообщений решаются иными протоколами. Contract Net Protocol не закрепляет за агентами их роли заранее — роль менеджера или исполнителя определяется в реальном времени в зависимости от контекста и задач агентов. Один и тот же агент может одновременно выступать как менеджер и как исполнитель для различных задач^[3].

У каждого агент-менеджера имеется список неиспользуемых (свободных) агентов. Всем потенциальным исполнителям рассылается сообщение о новой задаче. Каждый свободный агент, в свою очередь, обладает списком объявленных, но ещё не назначенных задач. Схема переговорного процесса выглядит так:

1. Неиспользуемый агент просматривает перечень свободных задач и выбирает те, которые ему подходят; остальные отклоняет.
2. На каждую подходящую задачу агент отправляет соответствующему менеджеру сообщение с предложением (обычно включает стоимость выполнения).
3. Менеджер из полученных предложений выбирает наиболее выгодное и назначает задачу выбранному агенту; остальные предложения отклоняет.
4. Агент-исполнитель становится ответственным за выполнение задачи. Далее он может либо сам решить задачу, либо разложить её на подзадачи и передать их другим агентам, став из исполнителя менеджером. Процесс повторяется рекурсивно.

Подобная последовательность приводит к построению иерархии из задач и распределённой ответственности за их решение.

Для иллюстрации приведём пример работы контрактной сети на системе мониторинга трафика (Distributed Sensing System) для построения карты плотности движения в определённой зоне. В сети работают агенты с разными возможностями. Первая группа агентов — это сенсоры, умеющие собирать данные из окружающей среды, но обладающие ограниченными вычислительными ресурсами. Вторая группа — вычислительные агенты, не имеющие доступа к данным напрямую, но способные их обрабатывать. Таким образом, вычислительные агенты становятся менеджерами задач для сенсоров^[4].

Объявление о задаче распространяется с помощью сообщения Task Announcement message. Его структура следующая:

TO: * (сообщение отправляется всем свободным агентам)
FROM: 25 (идентификатор отправителя)
TYPE: Task Announcement (тип сообщения — объявление задачи)
CONTRACT: 22-3-1 (код задачи/контракта)

TASK ABSTRACTION (краткое описание задачи)

TASK TYPE SIGNAL (тип задачи)

POSITION LAT 47N LONG 17E (регион, откуда требуется информация)

ELIGIBILITY SPECIFICATION (условия для исполнителей)

MUST-HAVE SENSOR (требуются агенты с сенсорами)

MUST-HAVE POSITION AREA A (участвовать могут агенты в определённой зоне)

BID SPECIFICATION (какие сведения должен содержать отклик)

POSITION LAT LONG (позиция агента)

EVERY SENSOR NAME TYPE (названия и типы сенсоров)

EXPIRATION TIME (срок окончания приёма откликов)

28 1730Z FEB 1979

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

Агент, выбрав наиболее подходящую задачу, формирует и отправляет конкретное предложение, например:

TO: 25
FROM: 42
TYPE: BID
CONTRACT: 22-3-1

NODE ABSTRACTION

POSITION LAT 62N LONG 9W

SENSOR NAME S1 TYPE S

SENSOR NAME S2 TYPE S

SENSOR NAME T1 TYPE T

Фрагмент NODE ABSTRACTION содержит данные об агенте, требуемые заказчиком; при необходимости включает и запрос дополнительных сведений, если объявленная задача описана недостаточно ясно.

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

Агенту, чьё предложение признано лучшим, отправляется сообщение о назначении:

TO: 42
FROM: 24
TYPE: AWARD
CONTRACT: 22-3-1

TASK SPECIFICATION

SENSOR NAME S1

SENSOR NAME S2

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

Первый тип — информационное сообщение — предназначен для общего обмена сведениями по задаче; использование зависит от конкретной реализации контрактной сети.

Второй тип — отчёт о ходе выполнения задачи, который может быть:

• промежуточным (позволяет контролировать и корректировать порядок выполнения задач, приостанавливать процесс до поступления промежуточных данных и т. п.);
• заключительным (отражает итог результата после завершения работы).

Иногда агент-исполнитель может получить сразу несколько назначений (выиграв несколько тендеров одновременно). Такое возможно, если он подал заявки по нескольким подходящим задачам, и более одной заявки стала победной. В таком случае задачи выполняются по порядку их поступления. Альтернатива — сразу после назначения первой задачи агент уведомляет остальных заказчиков об отказе по их задачам. Выбор подходящего подхода зависит от соотношения между затратами на коммуникацию и стоимостью выполнения; в обширных распределённых системах избыточная переписка для отказа от задач может перегрузить сеть и замедлить работу. Эти параметры учитываются при проектировании системы.

Такая ситуация возможна, если в системе нет свободных агентов (все заняты), объявленная задача оценена как невыгодная или ни один потенциальный исполнитель не соответствует условиям задачи.

В первых двух случаях проблему можно решить повторным объявлением задачи до тех пор, пока не найдётся подходящий агент. В третьей ситуации повторные публикации не помогут. Для этого предусмотрен механизм Immediate response, который гарантирует, что заказчик получит отклик, даже если ни один агент не может выполнить задачу. Так заказчик узнаёт причину отсутствия исполнителя. Как и в предыдущих случаях, дополнительная коммуникация повышает нагрузку на сеть и может замедлять систему при большом числе агентов.

Если, например, заказчик на основании прошлого опыта выполнения похожей задачи знает, какой исполнитель для него оптимален, он может напрямую обратиться к этому агенту, либо сразу назначить его, минуя процедуру конкурса. Это сокращает нагрузку на сеть и ускоряет процесс (нет необходимости ожидать завершения сбора предложений).

Если все агенты заняты текущими задачами, публикация новых задач теряет смысл и лишь перегружает сеть. Для этого предназначен специальный тип сообщения node available: агент-исполнитель оповещает о своей доступности и прикладывает сведения о своих возможностях; сообщение может рассылаться всем агентам-заказчикам. Менеджеры сравнивают параметры объявившегося агента с требованиями невыполненных задач и, если они совпадают, могут напрямую направить ему предложение.

В период с 2003 по 2012 год протокол Contract Net получил значительное развитие. Исследования были сосредоточены на его адаптации для новых прикладных областей, создании специализированных расширений и интеграции с другими технологиями.

Управление энергетическими системами

Протокол активно применялся для создания мультиагентных систем по управлению распределёнными энергетическими ресурсами и для регулирования напряжения в электросетях^[5]. Агенты, управляющие генераторами и контролирующие узлы сети, использовали CNP для координации своих действий с целью стабилизации напряжения. Координирующий агент (модератор) с помощью протокола определял вклад каждого генератора на основе его состояния и производительности системы^[5]. В некоторых реализациях для связи между агентами применялись веб-сервисы (на базе Microsoft.Net) и язык FIPA^[6].

Облачные вычисления и распределение ресурсов

Contract Net стал основой для систем динамического выделения ресурсов в облачных средах^[7]. Он использовался для создания автономных агентных систем, которые распределяли ресурсы от нескольких поставщиков облачных услуг на основе почасовых тарифов, что позволяло эффективно управлять выполнением параллельных задач (англ. Bag-of-Tasks) в нескольких облаках одновременно^[7].

Робототехника и беспилотные летательные аппараты

Протокол был адаптирован для распределения ролей в группах беспилотников (БПЛА)^[8]. В частности, были разработаны решения для миссий с участием нескольких БПЛА, например, для обнаружения и тушения лесных пожаров^[8].

Расширения протокола

В течение этого десятилетия были предложены различные расширения классического протокола для повышения его эффективности:

• Focused Selection CNP (FSCNP) — для целенаправленного выбора исполнителей;
• Semi-Recursive CNP (SRCNP) — полурекурсивная модификация;
• Information Retrieval CNP (IR-CNP) — версия для задач информационного поиска^[7].

В 2007 году была представлена конкурентная версия протокола (англ. Competitive Contract Net Protocol), которая включала фазы заключения контракта, возможного отказа от обязательств (со штрафами) и завершения контракта. Это позволило агентам демонстрировать оппортунистическое поведение, сохраняя при этом измеримую степень соблюдения обязательств^[9].

Интеграция с другими технологиями

Для повышения эффективности принятия решений в рамках CNP его начали комбинировать с другими методами. Например, в системах управления напряжением использовалась нечёткая логика (англ. Fuzzy Inference System) для управления процессом принятия решений модератором^[5]. Также для разработки и взаимодействия агентов применялись платформы, такие как JADE (англ. Java Agent Development Framework)^[6].

В этот период развитие протокола Contract Net было направлено на преодоление его классических ограничений, таких как высокая коммуникационная нагрузка и недостаточная гибкость. Исследования были сосредоточены на адаптации CNP к новым технологическим вызовам, включая Интернет вещей (IoT), робототехнику и умные энергосистемы, а также на его гибридизации с алгоритмами искусственного интеллекта.

Для повышения гибкости и снижения издержек в 2013 году была предложена модификация «updated-CNP», которая позволила изменять уже распределённые между агентами задачи без необходимости полного перезапуска процесса переговоров. Такой подход способствовал снижению коммуникационной нагрузки за счёт уменьшения количества служебных сообщений.

Значительным трендом стала гибридизация CNP с эвристическими и генетическими алгоритмами для повышения эффективности распределения задач. Например, протокол комбинировали с генетическими алгоритмами для оптимизации распределения задач между роботами в сфере логистики^[10], с меметическими алгоритмами для улучшения решений в логистике с временными окнами^[11], а также с алгоритмом муравьиной колонии. В 2019 году был предложен усовершенствованный протокол ICNP (англ. Improved Contract Net Protocol), который интегрировал динамические пороги отклика и модель потока феромонов, что позволило агентам более разумно принимать решения об участии в торгах^[12].

Помимо гибридизации, разрабатывались и структурные модификации протокола. Была предложена «двухуровневая» архитектура CNP для управления восстановлением в распределённых электросетях, где один уровень агентов контролирует права другого на объявление задач, что помогает избежать конфликтов в сложных асинхронных средах.

Усовершенствованные версии протокола нашли применение в новых областях. Модификации, такие как ICNP, стали использоваться для снижения коммуникационной нагрузки в производственных системах на базе IoT^[13], а гибридные модели с генетическими алгоритмами — для распределения задач между роботами на складах^[10].

В период 2023—2025 годов протокол Contract Net продолжает активно развиваться, при этом акцент смещается с его коренной модификации на интеграцию с новыми технологиями и адаптацию к сложным предметным областям, таким как робототехника, IoT и умное производство.

Интеграция с искусственным интеллектом и машинным обучением

Современные исследования направлены на встраивание интеллектуальных модулей в классическую схему протокола для повышения его адаптивности^[14]. Например, в мультиагентные системы внедряется обучение с подкреплением, что позволяет агентам-участникам динамически формировать более эффективные стратегии назначения ставок^[14]. В 2025 году был представлен «улучшенный протокол Contract Net» для умных цехов, в котором агент-оборудование использует нейронную сеть (многослойный перцептрон) в качестве «ИИ-диспетчера» для анализа состояния производства и генерации оптимальной стратегии распределения задач^[15].

Применение в иерархических системах

Протокол активно применяется в иерархических структурах мультиагентных систем, что позволяет находить баланс между глобальной эффективностью и локальной автономией отдельных агентов^[16]. В 2025 году было отмечено, что CNP был расширен для поддержки многораундовых переговоров, что находит применение в распределённом зондировании и на производстве^[16].

Новые области применения

• Интернет роботизированных вещей (IoRT). Благодаря масштабируемости и децентрализованной природе, CNP используется для распределения задач в гибридных автономных сетях роботов, управляемых через IoT^[17].
• Умное производство и цифровые двойники. Протокол служит механизмом связи в киберфизических архитектурах для динамического планирования производственных заданий, где агенты координируют свои действия с помощью цифровых двойников^[15].
• Финтех. В 2025 году CNP был проанализирован как один из ключевых протоколов для взаимодействия ИИ-агентов в финансовой сфере с целью повышения стабильности и эффективности процессов^[18].