V Международная студенческая научная конференция Студенческий научный форум - 2013

Введение

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

Основная идея способа представления модели – отражение её свойств и компонентов с различных точек зрения. В нашем случае мы имеем дело с распределённой агентной платформой на базе дискретно-событийного моделирования. Это, в свою очередь, приводит к тому, что потребуется рассмотреть модель как минимум с трёх различных аспектов: с точки зрения агентного подхода (модель как совокупность взаимосвязанных агентов), с точки зрения классического дискретно-событийного моделирования (модель как набор логических процессов) и с точки зрения параллельных вычислений (модель как множество узлов вычислительной сети).

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

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

Существующие работы и состояние области исследования

В целом, данной области исследования посвящено немало работ, преимущественно зарубежных. Также существует множество готовых программных продуктов и реализаций. К ним, например, относят как инструменты для организации агентного моделирования (Swarm, NetLogo, RePast, Mason, Cougar, JAMES, AnyLogic) [1, 2 7], так и средства создания мультиагентных систем (Jade, MACE3J) [2].

Если рассматривать сферу распределённого моделирования, то к настоящему времени специалисты выделяют два подхода к организации параллельных средств машинной имитации [4]:

• монолитные системы, в которых моделирование сводится к взаимодействию совокупности логических процессов;

• программные компоненты, которые позволяют объединить существующие средства имитации в одну общую сеть для реализации параллельного моделирования.

К последним относят технологию HLA (High Level Architecture), которая де-факто объявлена стандартом распределённого моделирования в США. К агентным системам, поддерживающим HLA, относят “HLA-AGENT” и “SIMAGENT TOOLKIT” [2].

Также существует множество работ, предлагающих особые алгоритмы и методики для реализации систем моделирования. К таковым относят, например, применение модели акторов для уменьшения накладных расходов коммуникации агентов [9], модель Штрассбургера [2], использующая эффективные алгоритмы синхронизации и вычисления GVT, распределённая система “Мера” [8], отечественная разработка для распределённого моделирования многопроцессорных ВС “Triad”[3-5].

Описание системы распределённого агентного моделирования

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

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

Общий цикл работы с точки зрения исследователя выглядит следующим образом:

• описание модели;

• настройка конфигурации сети;

• задание параметров модели;

• запуск;

• получение статистики (и, возможно, дальнейшая постобработка).

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

Основная задача исследователя – описать структуру и поведение агентов. Суть агентного моделирования состоит в том, что локальное поведение агентов, работающих по своим собственным правилам, формирует глобальное поведение системы в целом (концепция проектирования «снизу-вверх»). Это отличается от традиционных подходов типа «сверху-вниз», когда заданы глобальные законы функционирования системы, на базе которых работают её элементы.

Например, в системной динамике исследователь указывает интенсивность потока заявок, задержки при работе обслуживающих устройств и т.п. в виде математических формул (например, в виде стационарного пуассоновского потока, распределение которого выражается в виде Pt=λtkk!e-λx). Подобные предположения и допущения, несомненно, ухудшают качество модели.

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

Представление модели. Общие сведения

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

Идея агентного подхода получила широкое распространение лишь в середине 90-х, но совсем не в силу своей новизны и «революционности», а благодаря развитию вычислительных мощностей компьютера (а также методов искусственного интеллекта). Дело в том, что масштабирование модели, скажем, супермаркета, выполненной в классической парадигме («сверху-вниз»), до размеров миллионного города не сильно скажется на производительности. Агентный же подход предполагает вычисление каждого агента в отдельности, поэтому масштабирование с супермаркета до миллионного города пропорционально увеличит число агентов и экспоненциально – суммарное число связей между ними.

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

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

Ещё одной проблемой при переходе к распределённым вычислениям является нарушение так называемой «локальной каузальности». Суть проблемы кроется непосредственно в природе дискретно-событийного моделирования. Дело в том, что логические процессы в ходе своей работы изымают события из списков событий и обрабатывают их, изменяя при этом состояния связанных с ними объектов (в нашем случае агентов). При этом могут порождаться новые события как для собственного, так и для других логических процессов. Если событие планируется для соседнего процесса, ему отправляется сообщение с соответствующей временнóй меткой.

Итак, проблема локальной каузальности возникает тогда, когда логическому процессу в момент времени t₁ приходит сообщение с временной меткой t₂, и при этом t₁>t₂. В этом случае нарушается естественная хронология обработки событий, в результате чего нарушается смысл моделируемых во времени процессов. Вариантом решения проблемы могут выступать различные алгоритмы по синхронизации времени [1, 2, 5, 6]. При формальном описании модели, несомненно, также стоит учитывать этот момент.

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

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

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

Представление модели. Теоретико-множественное обоснование

В данном разделе мы предложим формальное представление модели, используемой системой агентного моделирования. Для этого сразу положим, что модель содержит 3 составляющие: модель вычислительной сети (CNM), модель логических процессов (LPM), модель концептуального уровня (CLM):

Model=(CNM,LPM,CLM).

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

Модель вычислительной сети (CNM)

Наиболее простой по своей структуре является модель вычислительной сети (ComputingNetworkModel). Она представляется связным неориентированным графом:

CNM=(VC, EC)

Вершинам узлов соответствуют вычислительные узлы, рёбрам – связи между ними. Конфигурация вершин зависит от типа ВС – это могут быть как процессоры в сильносвязанных SMP или MPP-системах, так и отдельные компьютеры в составе кластера. В качестве связей подразумевается установление постоянного логического соединения типа точка-точка (и сопутствующего стека протоколов). Рёбрам графа могут быть приписаны различные характеристики как числового, так и категориального характера (пропускная способность, латентность, таймаут соединения и т.д.) Топология сети может быть произвольной.

Модель вычислительной сети является основой для построения остальных 2 моделей. Исследователю при формализации задачи требуется проработать топологию сети в соответствии с требованиями объёма вычислительных затрат и интенсивности пересылки данных. Очевидно, при интенсивной пересылке больших объёмов данных системы с общей памятью будут иметь преимущество перед теми же кластерами.

Однако, несмотря на необходимость проработки модели вычислительной сети под каждую задачу, в целом подразумевается, что CNM не зависит от задачи и/или предметной области, т.е. предполагается, что она является наиболее абстрактной по сравнению с концептуальной моделью и моделью логических процессов.

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

Модель логических процессов (LPM)

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

Итак, данная модель представляется следующим образом [3]:

LPM=(T, Σ, L, M, Θ),

где

• Т – абстрактное линейно упорядоченное множество с отношением порядка «⪯». Далее под Т будем понимать множество моментов моделируемого времени.

• Σ – Множество событий – функциональное множество, для каждого из элементов которого ставится в соответствие временная метка из T. Вообще говоря, элементы множества представляют собой отображения, при которых меняется состояние логического процесса: Σ=δtδt:State→State.

• L – Множество логических процессов – представляется в виде ориентированного графа L=(VL;EL). Вершины графа – логические процессы, дуги – связи между ними.

• M – множество сообщений, передаваемых между логическими процессами. В общем случае под сообщением будем понимать следующую структуру:

mt=S, D, δt,μ,

где S∈VL – процесс-отправитель,

D∈VL – процесс-получатель,

δt – передаваемое событие с временнóй меткой t,

μ – тип сообщения (метаданные).

О необходимости введения метаданных будет пояснено позже в разделе «Модель концептуального уровня».

• Θ – Механизм передачи сообщений – совокупность алгоритмов, согласно которым производится передача сообщений между логическими процессами и обеспечивается синхронизация времени.

Мы уже описывали суть дискретно-событийного моделирования. Более формально этот процесс описывается следующим образом: логические процессы изымают события из списков событий в соответствии с временной меткой t. Затем выполняется вычисление функции δt, в результате чего логический процесс переходит из одного состояния State в другое. Следует отметить, что новое состояние необязательно является согласованным и непротиворечивым. Существуют специальные алгоритмы разрешения таких ситуаций.

Каждый логический процесс VL обладает, как минимум, тремя составляющими:

1. State – состояние;

2. InputBuffer – буфер для входящих сообщений;

3. OutputBuffer – буфер для исходящих сообщений.

Далее в разделе «Модель концептуального уровня» понятие логического процесса будет расширено с помощью четвёртого элемента

1. MemoryBuffer – локальная память логического процесса.

Модель логических процессов LPM, очевидно, уже больше зависит от задачи и конкретной предметной области, поскольку она является связующим звеном между моделями CNM и CLM.

Модель концептуального уровня (CLM)

Модель концептуального уровня является наименее абстрактной. Она зависит как от самой задачи, так и от предметной области в целом. Здесь исследователь уже оперирует конкретными субъектами моделирования – агентами.

Итак, модель на концептуальном уровне представляется следующим образом:

CLM=(G,Ω, Ψ),

где G – агентный граф (в общем случае ориентированный мультиграф G=(VA,E1A,E2A,…,EnA));

Ω – среда моделирования (Ω = (R, Φ));

Ψ – онтология предметного уровня.

1) На тип графа G не накладываются ограничений, но предполагается, что он может поддерживать множество типов дуг (мультиграф). Следует понимать, что для моделирования сложных трудноформализуемых задач требуется минимизировать число допущений, накладываемых на структуру графа. Так, например, граф может быть:

• циклическим (допускается наличие циклов),

• несвязным (допускаются наличие вершин без связей),

• псевдографом (допускается наличие дуг типа (Vi,Vi), т.е. дуг со степенью = 1),

• метаграфом (допускаются связи множества вершин с множеством),

• гиперграфом (допускаются наличие дуг типа V1,V2…Vn, т.е. дуг со степенью ≠ 2).

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

2) Среда моделирования Ω представлена двумя множествами:

Ω = (R, Φ).

R – множество ресурсов – конечное множество элементов произвольной природы, потенциально полезных для агентов. Примерами могут послужить товары при моделировании работы супермаркета, материалы на складе при моделировании цепочек поставок и т.д. Для системной динамики аналогом служат уровни.

Φ – множество правил (ограничений и функциональных отображений), определённых для среды моделирования. Для системной динамики аналогом служат потоки, однако множество Φ следует понимать гораздо шире. Упрощённо говоря, Φ характеризует множество глобальных законов, описываемых на некотором языке.

Для этого могут применяться:

• правила на языке исчисления предикатов,

• функции распределения,

• системы алгебраических уравнений,

• системы дифференциальных уравнений,

• дискретно заданные функции,

• булевы функции,

• математические неравенства,

• регулярные выражения,

• характеристические функции,

• рекуррентные соотношения,

• утверждения на языке регулярных грамматик и т.д.

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

3) Ψ – онтология предметного уровня. Вообще говоря, Ψ может включать и предметно-независимые онтологии более верхних уровней (например, для решения целого класса задач). Основное применение онтологий в предлагаемой агентной платформе заключается в следующем:

• для спецификации знаний, используемых интеллектуальными компонентами агентов;

• для интеллектуального управления синхронизацией времени при распределённом моделировании;

• для управления ходом балансировки загрузки.

На определение онтологий в общем случае не накладывается ограничений, поэтому будем понимать Ψ в классической трактовке:

Ψ=(P, N, I),

где P – множество концептов; N – множество связей между ними; I – способы интерпретации концептов из P посредством связей N.

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

Подробнее об идее использования знаний в управлении процессом моделирования см. в работе [1].

Агентный граф G

Агентный граф, будучи основным компонентом агентно-ориентированной платформы, нуждается в более детальном рассмотрении. Одной из основных задач при разработке агентного графа является сокращение так называемого «семантического разрыва» между предметно-зависимыми и независимыми компонентами: исследователь должен иметь возможность удобным образом задать определение графа, используя лишь понятия из предметной области.

Итак, граф G, прежде всего, условно делится на абстрактный и конкретный.

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

GA=VA;EA, EA=E1A,E2A…EnA.

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

GSt=VS(t); ES, ES⊆EA,

причём все вершины конкретного графа связаны с вершинами абстрактного графа отношением «класс-экземпляр»: (∀t ∀g∈VS(t) ∃p∈VA: isInstance(g, p)).

Главная идея абстрактного агентного графа – декларативно описать виды агентов и связи между ними. Конкретный же агентный граф служит математической абстракцией состояния модели в ходе имитационного прогона (и строится лишь в динамике).

Примером GA в случае супермаркета может послужить следующий граф:

GA=VA; E1,E2,E3,

где VA=Покупатель, Кассир, Товаровед, Фасовщик, Администратор, Охранник;

E1=Обращение покупателя к фасовщику;

E2=Обращение покупателя к кассиру;

E3=Производственные отношения между работниками зала;

Тогда конкретным агентным графом будут реальные экземпляры покупателей и работников зала, вступающие в одно или несколько отношений E1,E2,E3 . Причём этих экземпляров может быть как один (охранник), так и много (покупатель).

Понятие агента

В вершинах агентного графа находятся агенты (далее под агентами будем понимать агентов-прототипов). Так как в области имитационного моделирования и МАС не устоялось чётко определённого понимания сущности агента, существует масса определений и трактовок.

Одно из наиболее кратких определений: агент – это аппаратная или программная сущность, способная действовать в интересах достижения целей, поставленных перед ним пользователем. Более подробно об определениях агента см в [7], а мы дадим собственное понимание в контексте того, что интеллектуальность не присуща программным объектам априори. Так, агент представлен следующим образом:

vA=Q, F, λ,Z,

где Q – состояние агента (в простейшем случае ассоциативный массив);

F – функции, преобразующие состояние агента (F:Q→Q);

λ – функции высшего порядка, преобразующие функции (λ:Q×F→F);

Z – локальная память агента (также можно полагать ассоциативным массивом).

Для системной динамики аналогом F служат вентили.

Данный подход, нетрудно заметить, не даёт никакого упоминания об интеллектуальности и обучаемости агентов. Цели и убеждения скрываются во множестве Q, а методы принятия решений – в F. Способность к обучению – т.е. трансформации текущих правил вывода – закладываются в λ и Z. Также следует иметь в виду наличие «внеагентных» параметров – множества правил Φ, скрытое в окружающей среде, и онтологические знания Ψ, существующие обособленно как от агентов, так и среды.

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

В Таблица представлены все 3 модели в обобщённом виде.

Таблица . Модели различного уровня

CNM – модель вычислительной сети	LPM – модель логических процессов	CLM – концептуальная модель
VC – множество выч. узлов	T – множество моментов времени	G=GAEA – агентный граф
EC – множество связей	Σ – множество событий	Ω=R,Φ – окружающая среда
	L=VLEL – граф лог. процессов	Ψ=P,N, I – онтология
	M – множество сообщений
	Θ – механизм передачи сообщений

Взаимодействие моделей

Общая схема взаимодействия субмоделей изображена на рис. 1. Напомним, что модель представляет собой иерархическую совокупность трёх составляющих:

M=CNM, LPM,CLM

Рис. . Взаимодействие моделей

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

Прежде всего, введём операцию “наложения” моделей [3]. Под наложением будем понимать бинарную операцию, операндами которой является модель (субмодель), а результатом – также модель, задаваемая взаимно однозначным отображением

A: Model×Model⟶Model.

Далее данную операцию будем обозначать знаком «↔».

Связь модели вычислительной сети и модели логических процессов

Наложение моделей CNM↔LPM не вызывает особых затруднений. В простейшем варианте вычислительные узлы связаны с логическими процессами посредством агрегации. Основные свойства наложения моделей перечислены ниже:

• на одном узле могут выполняться несколько логических процессов;

• логические процессы могут быть связаны лишь в одном из 2-х случаев:

  • Они находятся на 1-м узле;

  • Существует связь между узлами в CNM;

• связи между логическими процессами направленные;

• граф должен оставаться связным.

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

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

Для каждого ребра из графа CNM ставится в соответствие 1 дуга (либо 2 взаимно противоположно направленные дуги) из графа LPM.

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

Рис. . Наложение модели логических процессов на модель вычислительной сети

Задачи, возникающие при наложении CNM↔LPM

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

Код для цитирования: Скопировать