ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2012, № 3, с. 55-75
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 519.687.1/4
САМООРГАНИЗАЦИЯ И МНОГОАГЕНТНЫЕ СИСТЕМЫ. II. ПРИЛОЖЕНИЯ И ТЕХНОЛОГИЯ РАЗРАБОТКИ © 2012 г. В. И. Городецкий
Санкт-Петербург, Санкт-Петербургский ин-т информатики и автоматизации РАН Поступила в редакцию 07.12.10 г., после доработки 23.11.11 г.
Основные тенденции развития современных информационных технологий во многом определяются наиболее актуальными практически важными задачами, которые возникают в экономике, экологии, обеспечении безопасности общества и отдельного человека, а также в других прикладных областях. Несмотря на большое содержательное разнообразие перечисленных задач, а также требований к их программной реализации, они обладают множеством общих особенностей, которые главным образом и определяют наиболее жесткие требования к современным информационным технологиям. Эти особенности приложений были проанализированы в первой части данной статьи. Приведенный там анализ показал, что в настоящее время новым требованиям к модели и программной реализации задач упомянутого выше типа в наилучшей мере отвечает модель многоагентной самоорганизующейся системы. В данной статье приводятся конкретные примеры ее использования в различных приложениях, описываются их архитектуры и программные реализации, в частности, описываются модели многоагентной самоорганизации в системах предсказания наводнений, планирования и оперативного управления производством. Новые возможности многоагентных самоорганизующихся систем демонстрируются на примере самообучающейся системы распределенного обнаружения вторжений в компьютерные сети, в которой фактически решается задача самоконфигурирования оверлейной сети. Возможности самоорганизующейся многоагентной системы для решения крупномасштабных задач управления в реальном времени демонстрируются на примере задачи адаптивного управления дорожным движением в мегаполисах. Для программной реализация самоорганизующихся многоагентных систем необходимо использовать специализированные инструментальные средства, отличные от существующих, поскольку для них обычная парадигма разработки программного обеспечения по схеме "сверху—вниз" не подходит. Причина этого заключается в том, что глобальное поведение самоорганизующейся многоагентной системы возникает за счет локальных взаимодействий, а потому его невозможно предсказать заранее. Поэтом разработка самоорганизующихся мно-гоагентных систем должна вестись "снизу—вверх". В статье дается краткий обзор предложенных для этих целей моделей и подходов. Более детально описывается один из перспективных подходов, основанный на использовании так называемых стандартных паттернов самоорганизации. Обсуждаются ее результаты и оцениваются перспективы практического применения технологии самоорганизующихся многоагентных систем.
Введение. Основные тенденции развития современных информационных технологий во многом определяются наиболее актуальными практически важными задачами. Такие задачи возникают в экономике, экологии, обеспечении безопасности общества и отдельного человека, а также в других прикладных областях. Модели и программные прототипы, решающие некоторые из таких задач, в частности, те из них, которые необходимы для обеспечения функционирования компьютерных сетей и распределенных интеллектуальных приложений, были рассмотрены в первой части данной работы. Однако ими область приложения самоорганизующихся много-агентных систем (МАС) далеко не ограничивается. К настоящему времени разработано большое количество прикладных моделей и программных прототипов самоорганизующихся МАС, которые используют различные механизмы самоорганизации, различные архитектуры многоагент-ной реализации и относятся к разным предметным областям. Первой целью данной работы является описание типичных представителей всего множества разнообразных моделей, архитектур и программных реализаций самоорганизующихся МАС. Вторая цель работы состоит в том, чтобы дать общее представление о технологии разработки самоорганизующихся МАС и о тех модельных решениях повторного использования, которые имеются к настоящему времени. Следует отметить, что исследования и разработки в области технологии самоорганизующихся МАС в настоящее время находятся пока еще на начальной стадии, и чтобы получить зрелую технологию и инструментальные средства ее поддержки, предстоит приложить еще много усилий.
Рис. 1. Двухуровневая архитектура самоорганизующейся системы предсказания наводнений (STAFF)
1. Примеры приложений самоорганизующихся многоагентных систем. 1.1. Самоорганизующаяся система предсказания наводнений. Одним из характерных примеров мно-гоагентной самоорганизующейся системы является система STAFF, предназначенная для предсказания наводнений в бассейне реки Гарона (Франция) [1, 2]. Она включает в себя несколько станций, установленных по течению реки, которые предсказывают локальные изменения ее уровня.
Программная система, установленная на станции, имеет двухуровневую многоагентную архитектуру (рис. 1). В ней на нижнем уровне находятся сенсоры, фиксирующие изменение уровня воды за один час, причем они могут содержать ошибки. Одна станция использует данные тысяч сенсоров. Агент, установленный на сенсоре, воспринимает изменение уровня воды S^t) (i — индекс агента i-го сенсора), измеряемое сенсором. Он ответственен за вычисление веса &i(tk_i), с которым величина Si(tk_l) в момент tk-1 будет учитываться в функции прогноза, вычисляемого агентом верхнего уровня Aj, j = 1,..., 4, в текущий момент t = tk_1 для предсказания Fjnp0T(tk) изменения уровня воды на час вперед, т.е. на момент времени tk:
Fjnp0F(tk) = X ®i(tk-i)S(tk-i). (1.1)
Vi: ai > 0
Таким образом, прогноз вычисляется как взвешенная сумма (обычно весьма грубых) измерений сенсоров в момент tk-1, причем в сумме учитываются только те из них, которые имеют положительные веса. Полагается, что если вес, приписанный некоторому сенсору в текущем интервале времени, имеет отрицательное значение, то его измерение в этот период ошибочно и потому не принимается во внимание. Итоговый прогноз изменения уровня воды за некоторый интервал времени [t0, tk ] вычисляется как сумма приращений уровня воды на этом интервале.
Самоорганизация на уровне агентов-сенсоров состоит в уточнении весов (ai(tk), причем необходимость такого уточнения детектируется с помощью агентов верхнего уровня. Эта кооперация имеет целью определить, когда и как нужно уточнять веса, присутствующие в формуле (1.1). Для этого агент использует результаты собственных измерений, аналогичные результаты других агентов, а также информацию об ошибках предсказания уровня воды, получаемую с помощью обратной связи.
Моменты запуска процесса самоорганизации в пределах каждой МАС станции системы STAFF определяются следующим образом.
1. Каждый агент Aj верхнего уровня в момент времени tk имеет возможность оценить качество своего предыдущего (измеренного на час раньше) предсказания изменения уровня воды Fjnp°T(tk), используя обратную связь в виде реального его значения, зафиксированного станцией на этот момент. Пусть, для примера, j = 1. Наличие заметного расхождения этих значений свидетельствует, возможно, о плохом качестве предсказания агента верхнего уровня A1, что влечет необходимость коррекции весов, с которыми он суммирует измерения сенсоров (механизм этой коррекции рассматривается далее). Авторами системы такая ситуация для этого агента называется конфликтом. Она влечет запуск механизма самоорганизации на множестве агентов нижнего уровня той МАС, в которой агент A1 играет роль агента верхнего уровня (содержание этого процесса описывания далее). Получив новые значения весов, агент A1 вычисляет новый прогноз приращения уровня воды на момент времени tr+1.
2. Агент A2 верхнего уровня, дающий в этот момент прогноз на тот же момент времени tk+1, сравнивает свой прогноз с тем новым прогнозом, который получен агентом A1 для момента времени tk+1. Если это отличие по модулю больше заданного порога, то агент A2 запускает механизм самоорганизации на множестве своих агентов нижнего уровня.
Далее эти процессы выполняются в цикле агентами A3 и A4 внутри своих МАС, установленных на станции. На рис. 1 этот процесс кооперации между агентами верхнего уровня указан стрелками. В итоге все агенты метауровня могут быть таким образом вовлечены в процессы самоорганизации.
Поясним теперь существо процесса самоорганизации, который выполняется каждой МАС станции на множестве своих агентов нижнего уровня. Пусть Si есть измерение /-го сенсора станции; ю, — текущий вес, с которым измерение этого сенсора подается на вход агента верхнего уровня. Заметим, что этот вес не может быть отрицательным, а если в процессе вычислений значение веса ю1 становится отрицательным, то он полагается равным нулю (см. формулу (1.1)). В этом случае полагают, что соответствующее измерение по той или иной причине не вполне адекватно ситуации. Пусть далее А ю есть модуль изменения веса ю1, которое может быть использовано на любом шаге для его модификации. Возможное изменение веса ю1 по модулю за один шаг является постоянным для всех сенсоров, а само изменение может быть положительным или отрицательным, или это изменение равно нулю. В конфликтных ситуациях того или иного вида (авторы системы STAFF называют их некооперативными ситуациями) модификация весов выполняется по-разному.
Авторы системы STAFF различают три вида некооперативных ситуаций. Рассмотрим их и покажем, каким образом в каждой из них выполняется модификация веса ю1 /-го сенсора.
Ситуация 1. Если значение ю, положительно, а результат S((), полученный агентом от сенсора, противоречит сигналу обратной связи (имеет отрицательную корреляцию с ним), то тогда Дю отрицательно. В этом случае ю, := ю, - Дю. Это имеет место, например, тогда, когда измерение сенсора показывает увеличение (уменьшение) уровня воды, а сигнал обратной связи свидетельствует о его уменьшении (увеличении). Обычно это характерно для случаев, когда система работает только на начальной стадии. Заметим, что именно за счет
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.