авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 9 | 10 || 12 | 13 |   ...   | 17 |

«Институт проблем управления им. В.А. Трапезникова РАН УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ Специальный выпуск 30.1 ...»

-- [ Страница 11 ] --

2. Базовые понятия. Результаты, на которые опирается данная работа Настоящая работа основывается на модели «структуриро ванная дискретно-событийная система» (СДСС), предложенной в [1]. Разработка СДСС мотивирована двумя особенностями оборудования с точки зрения ДСС-моделирования.

Во-первых, для дискретного оборудования характерно сле дующее разбиение множества событий E. Традиционное для теории ДСС разбиение на Euc и Ec – множества управляемых и неуправляемых событий, и Ew – множество ожидаемых собы тий. События из Ew моделируют состояния (положения) испол нительных механизмов (актуаторов) или компонент объекта.

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

Во-вторых, поведение каждого актуатора Gi моделируется языком L(Gi) из слов над Ei = {Ewi Eci}, а спецификация тре буемого поведения формулируется как язык K из событий Ed = {Ec Euc} – множества событий, моделирующего совокуп ности команд и условий их применения. Учет этих особенно стей позволяет получить ряд преимуществ как в определении ДСС, так и формулировании условий управляемости и синтезе супервизора.

В рамках СДСС моделирование проводиться на двух уров нях. Первый – это компоненты ДСС – актуаторы G = (G1, G2, …, Gn) с множествами Ei событий, каждое из кото рых структурируется на Ei = {Ewi Eci} и множеством Euc – общих неуправляемых событий. Поведение каждой компоненты Gi определяется конечным автоматом-генератором языка L(Gi), Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

задаваемым G i = Qi, E i, d i, Gi, Qm, q0 – множествами состояний, i i событий, функциями переходов и допустимых событий, множе ством обязательно достижимых состояний и начальным состоя нием соответственно. Второй уровень – это спецификация * требуемого поведения СДСС как язык K Ed (где Ed* – множе ство всевозможных слов любой, но конечной длины из событий Ed = Ec Euc). Язык K задается автоматом H = (Qh, Ed, h, Гh, Qmh, q0) как множество строк, определяющих требуемые спецификации. Язык K назван языком директивных спецификаций (язык лент технологических спецификаций).

ДСС с перечисленным структурированием названа ДСС с углуб ленным разделением событий.

Система, состав неуправляемой части которой задан ДСС с углубленным разделением событий, требуемое поведение опре * делено языком спецификаций K Ed (K ), и обеспеченная супервизором S так, что выполняется K, в работе [1] названа структурированной дискретно событийной системой (СДСС). Выполнение K предполагает, что проекция PEd(L(S / G)) = K, т. е. K будет совпадать с проекцией по Ed языка L(S/G), генерируемого S/G – объектом G под контролем супер визора S.

В работе [1] сформулированы свойства СДСС и разработа на процедура, названная алгоритм эксперимента ( s ), которая является основным приемом исследования совместного поведе ния G и H. Результат эксперимента над G строками s K, таки ми, что k(q0, s)!3, имеет два исхода ( s ) {True, False}. Если все эксперименты успешны, то G и H согласованы и супервизор S, с которым выполняется K, существует.

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

Сетецентрическое управление и многоагентные системы событий, а супервизор лишь обеспечивает блокирование тех управляющих событий, появление которых противоречит спе цификации. Для моделирования ДСС с пассивными актуатора ми (а САРВ именно таковыми и являются) в теории ДСС ис пользуется модель с форсируемыми управляемыми событиями [27], в которой управляемые события генерирует (форсирует) супервизор. Существование супервизора для структурирован ных ДСС с форсируемыми событиями исследованы в работе [3].

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

Условия управляемости СДССф – СДСС c форсируемыми управляемыми событиями – определены в теореме управляемо сти.

Теорема управляемости СДССф. Пусть дан G = G1, G 2,..., G n с углубленным разделением событий, у E = {Ew Ec Euc}, которого все Ec форсируемы, Ed = {Ec Euc}, K Ed (K ) и K определяется автоматом * H. Неблокирующий супервизор S, такой что PEd ( L ( S / G )) = K существует, тогда и только тогда, когда для любой s K ( s ) = True (такой, что h(q0, s)!) относительно G = G1, G 2,..., G n и все ветвления в графе переходов H кор ректны.

Первая часть предлагаемой методики – анализ существова ния неблокирующего супервизора S, основывается на проверке сформулированных в теореме условий существования S и опре делении Q = {Q1, Q2, …, Qr} – множество достижимых векто ров-состояний компонент G = G1, G 2,..., G n.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Синтез супервизора основан на анализе допустимых строк в языках L(Gi) и K Ed, заданных автоматами G = G1, G 2,..., G n * и H = (Qh, Ed, h, Гh, Qmh, q0). Специфика промышленных объек тов такова, что логика отдельных компонент объекта довольно прозрачна. Графы переходов, задающие L(Gi) и K Ed, – сла * боветвящиеся и, как правило, задают ограниченное количество циклически выполняемых последовательностей. Поэтому сами строки и их последовательности достаточно просто извлекаются из анализа последовательности ребер графа переходов. Такие последовательности довольно просто описываются на языке ЛСА – логических схем алгоритмов хорошо изученном в рабо тах Лазарева В.Г. и Баранова С.И. [10, 17]. В данной работе мы используем упрощенный вариант ЛСА для описания последова тельности строк событий. В СДСС под логической структурой последовательности строк (ЛСПС) будем понимать представле ние графа переходов конечного автомата в виде строк символов состояний и событий этого графа. Правила перехода от графа переходов к ЛСПС и обратно довольно просты и аналогичны описанным в [10, 17] правилам перехода от граф-схем алгорит мов к ЛСА. Поэтому ограничимся их изложением на концепту альном уровне. Каждая строка ЛСПС соответствует простому пути графа переходов и составляется из имен состояний и собы тий, взвешивающих ребра, в порядке их следования в этом пути.

Следование строк соответствует порядку обхода простых путей в графе переходов и представляется стрелочками с индексами.

Стрелочка вверх с индексом -n – исходящее ребро, заканчи вающее простой путь (после события, взвешивающего это ребро);

стрелочка вниз с индексом n – входящее ребро (перед состоянием, в которое входит помеченное раннее стрелкой исходящее ребро). Индексы стрелок однозначно связывают начало и конец перехода между строками. Если после некоторо го состояния имеет место ветвление (исходящих ребер более одного), то ветвление заканчивает строку, а события, соответст вующие этим ребрам, с верхними стрелочками заключается в Сетецентрическое управление и многоагентные системы фигурные скобки. На рис. 1 представлен граф переходов меха низма G3, стрелочками помечены ребра графа, разрыв которых выделяет простые пути для построения строк ЛСПС. Для графа переходов G3 ЛСПС: 1 q1 e3-1 q2 e3-2 q3 e3-3 4 q4{e3-8 -2, e3-4 -3 };

2 q10 e3-2 q11 e3-9 -1 ;

3 q5 e3-5 q6 e3-6 q7 e3-7 q8 e3-5 q9 e3-3 -4.

Легко прослеживается связь строки ЛСПС и пути на графе:

путь q1 q4 – это первая строка, заканчивающаяся фигурными скобками;

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

Рис. 1. Граф переходов автомата G В работе использованы общепринятые обозначения для се тей Петри (см., например, [18], которые вполне согласуются с классической нотацией из [25]). Сеть Петри (СП) – это пара (S, 0), где S – некоторая сеть, а 0 – некоторая начальная раз метка сети S. Сетью называется тройка S = (P, T, F), где P и T – непустые непересекающиеся конечные множества, называемые местами и переходами;

F ( P T ) (T P ) – бинарное отно шение инцидентности, на основе которого вводится функция инцидентности F : ( P T ) (T P ) ® N, где N – множество натуральных чисел. F для любого элемента x P T определя Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

ет множества его входных и выходных элементов: · x = { y | yFx} и x· = { y | xFy}. Разметкой (маркировкой) сети S = (P, T, F) называется функция m: P N. Если m ( p ) = k N, то говорят, что в месте p P имеется k фишек.

t T Переход допустим на разметке СП (S, 0) "p t : m ( p ) F ( p, t ). Сеть в матричной форме · задается матрицами W размерности (n m) – по числу позиций и переходов. При этом входная F (t j, pi ) и выходная F ( p j, ti ) функции переходов представляются матрицами W+ и W– соот ветственно. Матрица инцидентности W = W+ – W– – целочислен ная матрица wij = F (t j, pi ) - F ( pi, t j ), элементы которой задают то, какие изменения вносит в сеть срабатывание перехода tj.

Пусть y(ti) – вектор размерности m, у которого в позиции y(i) = 1, а в остальных 0. Тогда выражение m = m’ + W·yT(ti) в матричной форме представляет изменения маркировки сети, вызванные срабатыванием перехода t1. По последовательности срабатывания переходов s := t1, t2, …, tk построим вектор (раз мерности m) срабатывания (вектор Париха) y. Позиции y пред ставляют число срабатываний каждого перехода в последова тельности s. Тогда в векторной форме маркировка mk, достижимая после s, выглядит следующим образом:

mk = m0 + W·yT. При моделировании ДСС переходы взвешивают ся именами событий.

Р-инвариантом (инвариантом позиций) называют целочис ленный вектор X = {xi}, i = 1, 2, …, n, являющийся решением линейной системы: X·W = 0. T-инвариантом (инвариантом переходов) называется целочисленный вектор Y = {yi}, i = 1, 2, …, m, если он является решением линейной системы:

W·Y T = 0.

Сетецентрическое управление и многоагентные системы 3. Методика сквозного проектирования супервизорного управления На первом этапе проектирования супервизора для ДСС в работе предлагается провести СДСС-моделирование объекта управления и спецификации его требуемого поведения.

Мотивацию этого решения автор видит в следующем. Фор мализация структуры и поведения на первых этапах моделиро вания сложного объекта обычно основывается на сложившейся практике (традиции, опыте) разработчиков (проектантов) объек та и технологии. Базовым понятием технологических данных является технологическая операция, базовой компонентой стру ктуры чаще всего является исполнительный механизм (актуа тор), а различного рода диаграммы, циклограммы и/или блок схемы описывают требуемое (допустимое, востребованное) по ведение. Технологическая операция характеризуется событием (командой на исполнение), изменением состояния объекта и соответствующими откликами (реагированием). При моделиро вании ДСС на сетях Петри, характеризующихся очень бедным набором базовых средств (позиция и переход), возникают объ ективные методологические трудности. Одна из них: как техно логическую операцию представить (моделировать) позициями и переходами. На наш взгляд, целесообразно на этапе первичной формализации использовать модель конечный автомат, по скольку состояния, условия (события) их завершения и функции переходов и выходов достаточно прозрачно корреспондируются с упомянутыми выше традиционными для технологов инстру ментами (диаграммы, циклограммы и/или блок-схемы).

3.1. МОДЕЛИРОВАНИЕ СТРУКТУРЫ ОБЪЕКТА И ФУНКЦИОНАЛЬНОСТИ КОМПОНЕНТ КАК ДСС, ПРЕДСТАВЕННОЙ НАБОРОМ КОНЕЧНЫХ АВТОМАТОВ Структуризация объекта начинается с выделения всех ак туаторов (приводов и исполнительных механизмов);

пусть это будет G = G1, G 2,..., G n. Для каждого Gi определяются: мно Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

Общий алфавит для Gi – Ei = {Ewi Eci Euci}. Взаимосвязь команд (Eci), ожидаемых реакций и внешних условий (если это требуется) на практике представляется в виде диаграмм (цикло грамм), что достаточно прозрачно формализуется конечным автоматом Gi = Qi, Ei, i, Гi, Qmi, q0i. Здесь и далее такие авто маты будем называть компонентными конечными автоматами (ККА). В итоге анализа объекта определяются: состав СДСС G = G1, G 2,..., G n, множества Ei событий, каждое из которых структурируется на Ei = {Eiw Eic Eiuc}, и множество Euc – общих неуправляемых событий. Пример графа переходов ККА модели такого механизма представлен на рис. 2а).

Следующим этапом построения СДСС является определе ние востребованного поведения набора компонент. Поведение представляется как последовательность команд из Ec = n=1 Eci, i заданной строками в языке K Ed*. При этом в спецификацию входят только строки, соответствующие множеству путей на графе переходов конечного автомата H = (Qh, Ed, h, Гh, Qmh, q0).

В примере на рис. 2 представлен ККА первого механизма, а второй в точности до обозначений событий (индекс начинается с 2) опущен. Спецификация их востребованного поведения представлена на рис. 2б).

e1-5 e2- 2 3 2 e1-1 e1-2 e1-1 e1- 1 e2- 4 1 e1- e1- e1- 6 а б Рис 2. а) ККА – модель механизма G1;

б) автомат спецификации H Сетецентрическое управление и многоагентные системы Завершающим этапом СДСС-моделирования является про верка управляемости на основе алгоритма эксперимента (s), который является основным инструментом при изучении совме стного поведения G и H. Результатом эксперимента над стро ками s K (все строки допустимы для начального состояния q0) может быть (s) = True | False. Если после всех действий над символами s все компоненты G успешно осуществили свои переходы, то (s) = True;

если во время эксперимента новый символ s(i) не «сработал» в соответствующей компоненте, тогда (s) = False. В последнем случае подразумевается, что H не согласован с G и спецификация требуемого поведения (автомат H = (Qh, Ed, h, Гh, Qmh, q0)) должна быть изменена. В завершение анализа определим Q = {Q1, Q2, …, Qr} – множество достижи мых векторов-состояний компонент G = G1, G 2,..., G n, где Q j := q1j1, q 22,..., q n и каждое Qj Q соотносится с qj Qh.

j jn 3.2. СПЕЦИФИЦИРОВАНИЕ КОМПОНЕНТНЫХ КОНЕЧНЫХ АВТОМАТОВ ЛОГИЧЕСКИМИ СХЕМАМИ ПОСЛЕДОВАТЕЛЬНОСТИ СТРОК Для систем промышленной автоматизации довольно ти пичны простые механизмы, функциональность которых заклю чается в выполнении по циклу операций. В соответствии с правилами, изложенными в разделе 2, для графов переходов моделей таких механизмов формируем ЛСПС. Для G1(см.

рис. 2а) ЛСПС: 1 q1 e1-1 q2 e1-5 q3 e1-2 q4 e1-3 q5 e1-5 q6 e1-4 -1.

Построение ЛСПС по графу спецификации аналогично.

Иллюстрируем это примером двух механизмов G1 и G2. Пусть G2 устроен аналогично G1 и только индексы событий имеют префикс 2, тогда ЛСПС G2 имеет вид: 1 q1 e2-1 q2 e2-5 q3 e2-2 q4 e2- q5 e2-5 q6 e2-4 -1. Пусть требуется, чтобы циклически последова тельно выполнялись операции механизмов G1 и G2: вначале первые – e1-1, e2-1, а затем вторые – e1-3, e2-3. Граф переходов автомата H в СДСС-модели имеет вид, представленный на Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

рис. 2б). Напомним, что в автомате H не используются ожидае мые события. Тогда ЛСПС автомата H – LSH имеет следующий вид: 1 q1 e1-1 q2 e2-1 q3 e1-3 q4 e2-3 -1.

3.3. СИНТЕЗ СЕТИ ПЕТРИ, МОДЕЛИРУЮЩЕЙ ТЕХНОЛОГИЧЕСКИЙ ОБЪЕКТ УПРАВЛЕНИЯ Моделирование объекта как СДСС включает все события, представляющие детально его поведение. Каждая операция механизма представляется строкой, начинающейся с управляе мого события – команды, и последовательности всех после дующих ожидаемых событий. Так, например, для G1 операция «зажим детали» представляется строкой: e1-1 q2 e1-5 q3 e1-2 q4.

Вместе с тем для моделирования этой операции сетью Петри достаточно после события – команды e1-1 перейти в позицию выполнения операции, а по событию e1-2 перейти в позицию, соответствующую ее завершению. Это преобразование сформу лируем как правило редукции строк ЛСПС.

3.3.1. ПРАВИЛО РЕДУКЦИИ СТРОК ЛСПС Подстрока из 4-х символов типа: состояние i1, собы тие j1, состояние i2, событие j2, в которой все события относятся к типу ожидаемых, редуцируется в подстроку: со стояние i2, событие j2.

Применим правило редукции к ЛСПС G1:

q1 e1-1 q2 e1-5 q3 e1-2 q4 e1-3 q5 e1-5 q6 e1-4 -1.

Подстрока из 4 символов, например q2 e1-5 q3 e1-2 q2 e1-5 q3 e1-2 q3 e1-2.

В соответствии с правилом редукции строка ЛСПС G1 по следовательно преобразуется 1 q1 e1-1 q2 e1-5 q3 e1-2 q4 e1-3 q5 e1-5 q6 e1-4 - 1 q1 e1-1 q3 e1-2 q4 e1-3 q6 e1-4 -1.

Сетецентрическое управление и многоагентные системы 3.3.2. КОНСТРУИРОВАНИЕ СЕТИ ПЕТРИ После редукции ЛСПС синтез СП заключается в замене символов состояний символами позиций, сопоставлении собы тиям переходов и в построении по строкам ЛСПС (в соответст вии со следованием в них символов) сети Петри. Введем ряд обозначений. Далее ЛСПС автомата Gi, для краткости, будем обозначать LSi. Если подстрока h встречается в ЛСПС LSi, то это будем обозначать hLSi.

Задача этапа конструирование СП для механизмов состоит в преобразовании LSi.

n G = G1, G 2,..., G n S p = S i, при этом каждый i = Gi = Qi, Ei, i, Гi, Qmi, q0i преобразуется в Si = {Pi, Ti, Fi, 0} следующим образом: P i = { pk qk LS i } ;

T i = {tk - l ek -l LS i }.

Структура переходов определяется через входные и выходные функции переходов и соответствующие подстроки LSi:

· · tk -l = { p j q j ek -l LS i } ;

tk -l = { p j ek -l q j LS i }. Вектор начальной маркировки 0i содержит метку в позиции, соответствующей q0i.

Для механизмов G1 и G2 сеть имеет вид, представленный на рис. 3.

Рис. 3 Сеть Петри процесса для G1 и G Конструируем по автомату H соответствующую ЛСПС LSH и сделаем ее расширение: каждый переход ti, соответствующий Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

событию – команде, заменим парой titk, где tk переход, завер шающий операцию ti в соответствующем Si. ЛСПС автомата H – LSH имеет следующий вид: 1 q1 e1-1 e1-2 q2 e2-1 e2-2 q3 e1-3 e1-4 q4 e2- e2-4 -1.

3.4. СИНТЕЗ УПРАВЛЯЮЩЕЙ СЕТИ ПО SP И СПЕЦИФИКАЦИИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ КОМАНД Основная идея предлагаемого нами метода основывается на следующем свойстве циклических реактивных систем с форси руемыми событиями: каждая следующая операция объекта выполняются по событию завершения предшествующей опера ции (подобно падению выставленных вертикально костяшек домино) и/или внешнему событию (например, при пуске или выборе). В этом случае задача супервизорного управления – организовать передачу активности (управления) от механизма к механизму по завершению их операций. Метод синтеза управ ляющей сети Петри мы назвали методом домино.

Введем необходимые понятия и отметим ряд свойств сети процесса, которые в принципе доказуемы, но ограниченный объем статьи не позволяет это изложить. Исключим из строк, входящих в LSH, символы состояний. Далее в тексте все события ei–j заменим именами переходов tk и перенумеруем сплошной нумерацией по мере их следование в Sp, например, как это показано на рис 3. Тогда строка LSH примет вид 1 t1t2t5t6t3t4t7t8 -1.

Несвязанные пары переходов. Переход tj ti сети Sp называ ется несвязанной парой (н-парой), если tj ti LSH и в сети Sp не существует позиции pk такой, что tj ·pk, а ti pk·.

Свойство 1. При преобразовании сети Sp в Sp. путем рас ширения Sp звеном tj pc ti (далее просто tj pc ti) P-инва рианты сети Sp сохраняются в сети Sp (преобразование иллюст рирует звено на рис. 3, выделенное пунктиром). Однако множество достижимых состояний, несомненно, изменится.

Более того, ограниченная сеть Sp преобразуется в неограничен Сетецентрическое управление и многоагентные системы ную Sp., поскольку в позиции pc возможен неограниченный рост числа меток при бесконечном цикле в первой сети.

Свойство 2. Для всякой н-пары tj ti скалярное произведе ние векторов – столбцов (W(ti), W(tj)) = 0. Следует из факта отсутствия связующих их позиции.

Свойство 3. Пусть расширение сети Sp осуществляется множеством звеньев, сконструированных для всех н-пар из последовательности срабатывания u, соответствующей LSH. При этом вектор Париха Y(LSH), соответствующий u, является T-инвариантом сети Sp, поскольку LSH задает циклический процесс, а G = (G1, G2, …, Gn) и H = (Qh, Ed, h, Гh, Qmh, q0) со гласованы. Тогда существует изоморфное отображение Q = {Q1, Q2, …, Qr} – множества достижимых векторов-состоя ний компонент G = G1, G 2,..., G n (где Q j := q1j1, q 22,..., q n ), на j jn M – множество достижимых маркировок сети Sp. Кроме того, P-инварианты сети Sp сохраняются в Sp и Y(LSH) является T-инварианты сети Sp.

Из сформулированных свойств следует, что если для всех возможных последовательностей строк, задаваемых, например, ЛСПС, выявить все н-пары tj ti и каждую пару в сети процесса обеспечить звеном tj pc ti передачи управления (активности), то, во-первых, все структурные свойства исходной сети процесса сохраняются;

во-вторых, все требуемые последовательности операций, определяемые спецификацией, будут выполняться.

В этом разделе мы ограничимся разработкой ядра метода ограничивающего LSH бесповторной4 ЛСПС, содержащей одну последовательность. Это ограничение далее будет снято.

Опишем процедуру проектирования управляющей сети Sc из СПУ tj pc ti для ЛСПС, содержащей одну бесповторную по следовательность срабатывания переходов (управляющую сеть Sc иногда называют сеть контроллера).

В бесповторной последовательности срабатывания каждый пере ход упоминается не более 1 раза.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Процедура построения управляющей сети Sc.

Обозначения, используемые в тексте процедуры: Sintez – имя процедуры;

W, Pc, n, u, r – формальные параметры;

u := t1 t2 t3 …tr–1 tr – строка ЛСПС, обрабатываемая процедурой (в u стрелочки заменены именами переходов, на которые эти стрелочки указывают в ЛСПС);

r – длина строки u;

W(n m) – матрица инцидентности сети процесса Sp;

W(k, ~) = 0 означает присвоение всем элементам строки k матрицы W значение 0;

u(i) i-ый символ строки u. W(u(i)), W(u(i + 1)) – векторы-столбцы матрицы W, SProdct(W(u(i)), W(u(i + 1))) – скалярное произведе ние векторов. Текст процедуры:

Sintez (W, Pc, n, u, r) i= While i (r – 1) do Begin If Sprodct (W(u(i)), W(u(i + 1))) 0 go to M1;

n = n + 1;

W(n, ~) = 0;

W(n, u(i)) = +1;

W(n, u(i + 1)) = -1;

Pc = {Pc} {pn};

M1: i = i + End.

Применим процедуру Sintez к сети Sp (см. рис. 3) для двух механизмов G1 и G2. Матрица инцидентности W этой сети пред ставлена в таблице 1. В матрице W имена событий заменены именами соответствующих переходов следующим образом:

(e1-1 ® t1) …( e2-4 ® t8). Обрабатываемая строка u := t1 t2 t5 t6 t3 t4 t7 t8 t1;

r = 9.

Результатом работы процедуры Sintez является построение сети Sc из четрырех управляющих позиций (pc1, …, pc4). Объеди ненная сеть Sp и Sc представлена на рис. 4.

Сетецентрическое управление и многоагентные системы Вычисление m0. Вектор начальной маркировки T T T T 0 = [0P 0C ] состоит из начальной разметки 0P сети процес са Sp и начальной разметки 0CT сети контроллера Sc.

Первая часть 0PT определяется при построении Sp и соот ветствует начальным состояниям ЛСПС (в позициях вектора 0PT, соответствующих начальным состояниям в определении ЛСПС присваивается 1, а остальным 0).

Правило для начальной разметки 0CT. Поскольку вектор Y является T-инвариантом (задает цикл), то если из него исклю чить срабатывание последних в цикле переходов, то матричная операция W с модифицированным Y определит начальную разметку для Sc.

Таблица 1. Матрица инцидентности W для СП механизмов G1 и G t1 t2 t3 t4 t5 t6 t7 t P1 –1 00 10 00 P2 1 –1 0 0 0 0 0 P3 0 1 –1 0 0 0 0 P4 0 0 1 –1 0 0 0 P5 0 0 0 0 –1 0 0 P6 0 0 0 0 1 –1 0 P7 0 0 0 0 0 1 –1 P8 0 0 0 0 0 0 1 – Pc1 0 +1 0 0 –1 0 0 Pc2 0 0 –1 0 0 +1 0 Pc3 0 0 0 +1 0 0 –1 Pc4 –1 0 0 0 0 0 0 + Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Рис. 4. Сеть Петри с управляющими позициям, реализующими управление, так, что выполняется последовательность u := t1 t2 t5 t6 t3 t4 t7 t8 t 3.5. УЛУЧШЕНИЕ SC ПУТЕМ МИНИМИЗАЦИИ КАНАЛОВ УПРАВЛЕНИЯ Процедура Sintez вводит позицию, передающую управле ние, для каждой н-пары подобно каналу связи. Эти каналы «работают» только в момент активности соответствующей н пары и после передачи управления в следующие переходы не участвуют в процессе активизации других переходов, пока в следующем цикле они не будут вновь востребованы. Из чего следует, что формирование для каждой н-пары нового канала в сети во многих случаях избыточно. Прозрачно определяются отношение совместимости каналов (по отсутствию пересечения предшественников и последователей) и соответствующие пра вила. Эти правила подобны правилам совместимости состояний для конечного автомата. Применив эти правила и проделав традиционные преобразования, для нашего примера удалось сократить число позиций в два раза. Результат представлен на рис 5.

Сетецентрическое управление и многоагентные системы Рис. 5. Преобразованная сеть Петри, выполняющая последовательность u := t1 t2 t5 t6 t3 t4 t7 t8 t 3.6. СИНТЕЗ УПРАВЛЯЮЩЕЙ СЕТИ ПО ЛСПС, ПОСТРОЕННОЙ ПО СПЕЦИФИКАЦИИ СДСС БЕЗ ОГРАНИЧЕНИЙ НА БЕСПОВТОРНОСТЬ И НАЛИЧИЕ ВЕТВЛЕНИЙ В настоящем разделе мы ограничимся изложением основ ных положений развития процедуры синтеза Sc в направлении отказа от ограничений на бесповторность и количество строк в LS.

В спецификации требуемого поведения в общем случае до пустимы многократные срабатывания механизмов и многовари антное поведение, регулируемое предшествующими срабатыва ниями механизмов в уже отработанных последовательностях или внешними (неуправляемыми) событиями. Последнее пред ставляется ветвлениями в графе переходов автомата H = (Qh, Ed, h, Гh, Qmh, q0), которые в ЛСПС представляются ветвителями.

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

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Замечание 1. Совпадение первого события в различных н парах. Наличие в LS двух или более н-пар с совпадающими первыми символами означает, что одно и то же событие, напри мер ti, в различных частях последовательности – спецификации – влечет различные последствия: ti – tk и ti – tr. Следовательно, необходимо в структуре звена передачи управления привлечь дополнительную информацию (другие события или их последо вательности, которые различают н-пары ti – tk и ti – tr).

Замечание 2. Совпадение второго события. Наличие двух или более н-пар типа ti – tk, tj – tk, …, tn – tk означает, что переход tk срабатывает всякий раз, когда срабатывает один из переходов ti, tj, …, tn. Таким образом, в структуре звена передачи управле ния должна производиться сборка по функции «ИЛИ». Для этого в процедуре конструирования звена передачи управления всякая н-пара, например ti – tk, будет анализироваться на воз можность «повтора 2-го символа». При обнаружении такой н пары, например tj – tk, в звене вводится позиция, в которой осуществляется сборка передачи управления в общий для всех н-пар переход tk, в который из позиции-сборки вводится ребро por – tk.

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

Отметим одну из особенностей процедуры Sintez: позиция сети Sc вводится, как только обнаруживается н-пара, вне зави симости от предшествующих и последующих событий в строке.

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

Легко видеть справедливость следующего утверждения.

Утверждение. Сложность выполнения процедуры Sintez пропорциональна суммарной длине строк в LS.

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

Методология основана на использовании структурирован ной дискретно-событийной системы (СДСС) для анализа функ циональности и согласованности модели. Разработан метод синтеза по СДСС-модели сети Петри Sp, моделирующей процес сы в объекте, разработана техника анализа Sp и метод синтеза управляющей сети супервизора – Sc, обеспечивающей совмест но с сетью Sp выполнение исходных спецификаций. Метод синтеза управляющей сети Sc основан на анализе ЛСПС – ком пактной модели последовательности срабатывания переходов в сети процесса. Предложенная модель СДСС и процедуры рабо ты с ней максимально учитывают особенности систем автома тизации, работающих в реальном масштабе времени, отмечен ные во введении. Есть основание полагать (утверждение в разделе 3.6), что в предложенном методе, основанном на линей ном просмотре всех простых строк из ЛСПС, удается избежать «взрыва состояний» при синтезе супервизора.

Важным свойством управляющей сети Петри, синтезиро ванной по предложенной методике, является то, что в ее струк туре сохранена Sp – СП-модель актуаторов (исполнительных механизмов нижнего уровня). Сеть Петри Sc, управляющая Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

интеграцией компонент нижнего уровня (супервизор), синтези рована как отдельная компонента, взаимодействующая с сетями нижнего уровня. Важно отметить, что сети Sc нет в структуре исходных данных. Напротив – эта сеть есть результат синтеза обратных связей в Sp на основе анализа возможностей модели процессов в объекте – Sp и требований спецификации LS. Таким образом, предложенный метод синтезирует двухуровневую управляющую систему, отвечающую требования сетецентриче ской интеграции, сформулированным во введении.

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

При этом строки из команд (директив на выполнение вариантов бизнес-процессов) языка супервизора K можно интерпретиро вать как различные варианты достижения цели функционирова ния. Синтезированный супервизор – сценарий заданный сетью Петри;

изменение сценария – смена матрицы, а в реальной организационной системе смена текущего плана мероприятий.

Литература 1. АМБАРЦУМЯН А.А. Супервизорное управление в дискрет но событийных системах // Автоматика и телемеханика. – 2009. – №8. – С. 156–166.

2. АМБАРЦУМЯН А.А. ПРАНГИШВИЛИ И.В., ПОЛЕТЫ КИН А.Г. Анализ состояния и предложения по повышению уровня автоматизации энергетических объектов // Про блемы управления. – 2003. – №2. – С. 37–57.

3. АМБАРЦУМЯН А.А., ТОМИЛИН Е.Е. Метод прямого синтеза супервизора для структурированной дискретно динамической системы // Автоматика и телемеханика. – 2010. – №8. – С. 168–188.

4. АМБАРЦУМЯН А.А. Эквивалентные преобразования управляющих автоматов, генерируемых по описанию пове Сетецентрическое управление и многоагентные системы дения объекта управления // Тезисы докладов Первой Меж дународной конференции молодых ученых «Проблемы про ектирования и применения дискретных систем в управле нии», Минск: ИТК АН БССР, 1977. – С. 77–78.

5. АМБАРЦУМЯН А.А., ГРИГОРЯН А.К. О соотношениях управляющих автоматов, порождаемых по их описанию на первичном языке // Автоматика и телемеханика. – 1978. – №12. – С. 130–138.

6. ЗАКРЕВСКИЙ А.Д., ПОТТОСИН Ю.В., ЧЕРЕМИСИНО ВА Л.Д. Логические основы проектирования дискретных устройств. – М.: Физматлит, 2007 – 588 с.

7. ЗАЦАРИННЫЙ А.А., ПРИСЯЖНЮК С.П., ИОНЕН КОВ Ю.С. Тенденции развития современных инфокоммуни кационных технологий с учетом концепции сетецентриче ских войн // Информация и космос. – 2006. – №4. – С. 85–93.

– URL: http://elibrary.ru/contents.asp?issueid=644974.

8. ИВАНОВ Н.Н., МИХАЙЛОВ Г.И., РУДНЕВ В.В.

ТАЛЬ А.А. Конечные автоматы: эквивалентность и пове дение. – М.: Наука, 1984. – 192 с.

9. ИВЛЕВ А.А. Основы теории Бойда. Направления развития, применения и реализации. Москва, 2008. – 64 с. – URL:

http://old.vko.ru/pdf/2008/library/08_05_23_02.pdf.

10. ЛАЗАРЕВ В.Г., ПИЙЛЬ Е.И. Синтез управляющих авто матов. – М.: Энергоатомиздат, 1989.

11. РУДНЕВ В.В. Конечный автомат как объект управления // Автоматика и телемеханика. – 1978 – №9. – С. 126–135.

12. ТАЛЬ А.А., ЮДИЦКИЙ С.А. Иерархия и параллелизм в сетях Петри // Автоматика и телемеханика – 1982. – I: №7.

– С. 121-139;

II: №8, – С. 111–128.

13. ЮДИЦКИЙ С.А. К вопросу описания и синтеза дискрет ных систем промышленной автоматики // Техническая ки бернетика. – 1976. – №1. – С. 131–141.

14. AKESSON K., FLORDAL H., FABIAN M. Exploiting modula rity for synthesis and verification of supervisors // Proc. of the IFAC World Congress, Barcelona, Spain, July. 2002. – P. 1444–1449.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

15. AMBARTSUMYAN A.A., KAZANSKY D.L. Complex auto mation of technological processes with involving event model in feedback control scheme // Proceedings of 17th IFAC World Congress, Seoul, Korea, 2008. – P. 28–33.

16. AMBARTSUMYAN A.A., KAZANSKY D.L. An approach to technological process control systems based on model with technological coalitions // Proceedings of 12th International con ference on systems engineering (ICSEng08), Las Vegas, USA, 2008. – P. 219–224.

17. BARANOV S. Logic and System Design of Digital Systems. – Toronto: Published jointly Tallinn University of Technology Press and SIB Publishers, 2008. – P. 266.

18. CASSANDRAS C.G., LAFORTUNE S. Introduction to discrete event systems. – Dordrecht: Kluwer Academic Publishers, 2008.

– P. 848.

19. DE QUEIROZ M.H., CURY J.E.R. Modular supervisory control of large scale discrete event systems // Discrete Event Systems:

Analysis and Control, Proc. WODES'00, 2000. – P. 103–110.

20. DIDEBAN A., ALLA H. Reduction of Constraints for Control ler Synthesis based on Safe Petri Nets // Automatica. – 2008. – No. 44(7). – P. 1697–1706.

21. GAUDIN B., MARCHAND H. Modular supervisory control of asynchronous and hierarchical finite state machines // In Euro pean Control Conference, Cambridge, 2003. – P. 133–138.

22. GOLASZESKI C.H., RAMADGE P.J. Control of discrete event processes with forced events // Proc. 28th Conference on Deci sion and Control, Los Angeles, 1987. – P. 247–251.

23. HOLLOWAY L.E., KROGH В.Н. Synthesis of feedback logic for a class of controlled Petri nets // IEEE Trans. Autom. Con trol. – 1990. – P. 514–523.

24. RAMADGE J.G., WONHAM W.M. Supervisory control of a class of discrete event processes // SIAM Journal of Control and Optimization. – 1987. – No. 25. – P. 206–230.

25. PETERSON J.L. Petri Net theory and the modeling of systems.

– Englewood Cliffs, N.J: Prentice-Hall, Inc., 1981.

Сетецентрическое управление и многоагентные системы 26. WONHAM W.M., RAMADGE J.G. Modular supervisory control of discrete event systems // Math Control Signals and Systems. – 1988. – No. 1. – P. 13–30.

27. YAMALIDOU K., MOODY J.O., LEMMON M.D., ANTSAKLIS P.J. Feedback control of Petri nets based on place invariants // IEEE Transaction on Robotics and Automation. – 1996. – No. 32(1). – P. 15–28.

28. YOO T.-S., LAFORTUNE S. A general architecture for decen tralized supervisory control of discrete event systems // Discrete Event Dynamic Systems: Theory & Applications. – 2002. – No. 12(3). – P. 335–337.

NETWORK-CENTRIC CONTROL ON PETRI NETS FOR STRUCTURED DISCRETE EVENT SYSTEM Alexander A. Ambartsumyan, Institute of Control Sciences, Russian Academy of Science(s), Moscow, Russia;

(tel.: +7-495-334-87-89, e-mail: ambar@ipu.ru) Abstract: The paper deals with the methodology of control Petri net synthesis developed for real-time automation systems. The method ology is based on the model called a structured discrete event system (SDES) applied to analysis functionality and consistency. In the paper, SDES structure is defined, the technique of SDES con trollability analysis is proposed. Developed are the method (based on SDES model) of Petri net synthesis for process modeling, the technique of process net analysis and the synthetic method of super visor control net providing, jointly with the process net, the fulfill ment of initial specifications.

Keywords: logical control, control system, network-centric sys tem, supervisor, discrete event systems, event model, Petri net.

Статья представлена к публикации членом редакционной коллегии М. В. Губко Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

УДК 551.46.077+629. ББК 05.22. ОБ ОДНОМ АЛГОРИТМЕ ПОИСКА ИСТОЧНИКА ПОДВОДНОГО ШЛЕЙФА, ОСНОВАННОМ НА ИСПОЛЬЗОВАНИИ ГРУППЫ АНПА Бабак Л. Н.1, (Дальневосточный государственный технический университет им. В.В.Куйбышева, Владивосток), Щербатюк А. Ф.2, (Институт проблем морских технологий Дальневосточное отделение РАН, Владивосток) Рассмотрен алгоритм поиска источника шлейфа, основанный на аппроксимации границы шлейфа. При оценивании местопо ложения источника наибольшими весами обладают наиболее близкие оценки местоположения источника, полученные от дельными автономными необитаемыми подводными аппара тами. Приведены некоторые результаты моделирования ра боты группы из четырех подводных аппаратов по определе нию местоположения источника шлейфа.

Ключевые слова: поиск источника шлейфа, группа автоном ных необитаемых подводных аппаратов, траектории движе ния.

1. Введение В последние годы все большее развитие получают исследо вания, связанные с изучением состояния морских акваторий и влияния на них антропогенных воздействий. Для этих целей проводятся специальные исследования с применением различ ных технических средств. Особое внимание привлекают процес Лариса Николаевна Бабак, доцент.

Александр Федорович Щербатюк, чл.-корр. РАН, д.т.н., зав. лаб.

(scherba@marine.febras.ru) Сетецентрическое управление и многоагентные системы сы распространения примесей в воде, связанные с регулярной бытовой и промышленной деятельностью, а также с засорением морской среды единичными источниками загрязнений. Одним из примеров неоднородностей водной среды является шлейф, который образуется в результате сброса технологических отхо дов из трубы или от расположенного на дне источника раство ренного вещества под воздействием имеющихся в данном рай оне течений. Задачами обследования могут быть локализация (оконтуривание) образовавшегося района с повышенной кон центрацией примеси и определение местоположения источника растворенного вещества.

Такие платформы, как автономные необитаемые подводные аппараты /АНПА/, способны адаптивно исследовать процессы в зависимости от времени и на значительных дистанциях. Сеть интерактивных подводных аппаратов является распределением мобильных управляемых сенсоров с регулируемым пространст венным разрешением и программируемым поведением для из мерения пространственных градиентов параметров среды. В по следние годы необитаемые подводные аппараты все шире ис пользуются для мониторинга водных акваторий [1-8]. В [7] опи сан эксперимент с применением АНПА MARES по обследова нию состояния залива Aveiro на португальском побережье, в ко торый сбрасываются сточные воды. В статье [6] приведены ре зультаты исследования с использованием АНПА REMUS по изучению распространения загрязнения от точечного источника при наличии течений, где в качестве источника шлейфа исполь зовался родаминовый краситель. Результаты использования АНПА REMUS для оценки 3-х мерного распределения концен трации растворенных органических веществ в заливе Penobscot описаны в [8]. В статье [4] рассмотрен эксперимент с использо ванием автономного водного аппарата (autonomous surface vehi cle – ASV) по отслеживанию теплового потока, источником ко торого является ядерный реактор в Calvert Cliffs, США. Осенью 2008 и 2009 года ИПМТ выполнил исследования с использова нием АНПА ММТ-3000, связанные с оценкой распространения шлейфа пресной воды от реки Безымянная, впадающей в бухту Воевода в районе острова Русский вблизи г. Владивостока [1].

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Оценка выполнялась на основе измерений солености и темпера туры.

Опыт одновременного использования нескольких АНПА SAUVII для оценивания параметров водной среды рассмотрен в [5]. Еще одним примером использования групп АНПА являются исследования, проводимые в SANDIA National Laboratories (США) с применением малогабаритных подводных аппаратов Ranger (Nekton Research) [3]. В [9] описано использование под водных аппаратов Ranger для локализация источника шлейфа и съемки движения фронта солености в устье реки Нью-Порт на побережье Северной Каролины. Поиск источника шлейфа вы полнялся тремя подводными аппаратами, которые запускались из трех разных точек и двигались к эпицентру шлейфа на основе расчета градиента концентрации, выполняя зигзагообразные траектории по высоте. Оценка распространения фронта солено сти выполнялась четырьмя АНПА, которые двигались парал лельными зигзагообразными траекториями в вертикальной плоскости.

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

2. Описание алгоритма Рассмотрим задачу оконтуривания границ шлейфа и опре деления местоположения точечного источника шлейфа. Разра батываемый алгоритм предназначен для организации движения группы АНПА к месту нахождения точечного источника шлей фа. Допустим, что имеется плоское придонное течение, в кото Сетецентрическое управление и многоагентные системы ром расположен источник растворенного вещества. Вещество попадает в водный поток и образует шлейф, который расширя ется по мере удаления от источника. Предполагается, что:

- плотность воды с примесью выше плотности морской воды и поэтому загрязненная вода локализуется вблизи дна и в вертикальной плоскости имеет вид слоя определенной тол щины;

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

Рис. 1. Шлейф и его кусочно-трапециевидная аппроксимация Для локализации местоположения источника шлейфа для каждого АНПА формируется траектория, направленная на пере сечение шлейфа. Пересечению границы шлейфа соответствует ситуация, когда показания датчика концентрации растворенного вещества превышают заданный порог в течении нескольких из мерений. Траектория движения АНПА формируется в виде ме андра, пересекающего шлейф параллельными прямолинейными галсами, длина которых уменьшается по мере сужения ширины шлейфа. Границы шлейфа аппроксимируются прямыми линия Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

ми Line1 (y = k1x + b1) и Line2 (y = k2x + b2) путем минимизации невязок:

(1) min ( yi - kxi - b) 2.

k,b i Параметры линий Line1 и Line2 определяются на основе МНК, в соответствии с выражениями:

( yi - kxi - b ) xi = 0, i (2) ( yi - kxi - b ) = 0, i где (xi, yi) – координаты точек пересечения правой границы шлейфа для линии Line1 или левой границы шлейфа для линии Line2.

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

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

Сетецентрическое управление и многоагентные системы После определения всеми АНПА координат источника шлейфа (решений) оценивается результирующее местоположе ние источника шлейфа. При этом для каждого полученного ме стоположения источника находится ближайшее соседнее реше ние и определяется дальность до него Dk. в соответствии с соот ношением:

2 2 0. min[( xi - xk ) + ( yi - yk ) ], если Dk D, (3) Dk = i.

D, если Dk D.

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

Координаты предполагаемого местоположения источника шлейфа (х, у) вычисляются в соответствии с выражениями:

N [ x - xk ] / Dk = 0, k = (4), N [ y - yk ] / Dk = 0, k = где k = 1, …, N – номер АНПА и соответствующего решения, N – число участвующих в эксперименте АНПА.

3. Некоторые результаты моделирования Для моделирования работы алгоритма был разработан ком плекс программ на языке С. В процессе моделирования задава лись начальные местоположения АНПА и исходные параметры их движения. Система работает с некоторым заданным перио дом времени Т, который в натурных условиях определяется временем измерения концентрации примеси в воде бортовым датчиком.

Границы шлейфа моделировались двумя параболами. Зна чение концентрации растворенного вещества в точке (x, y) опре делялось из условия, что масса вещества, проходящего через любой вертикальный разрез, перпендикулярный оси шлейфа, является величиной постоянной и равна A. В соответствии с экспериментальными данными, приведенными в [1], концентра ция примеси в центре шлейфа максимальна и убывает к его гра Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

A y 1 -, (x e, y ax ),, K ( x, y ) = ax ax (5) 0, для всех остальных ( x, y ), где ось Ох направлена вдоль оси локального трапециевидного фрагмента шлейфа (рис. 2).

Рис. 2. Вид функции концентрации для локального трапециевидного участка шлейфа Для моделирования концентрации растворенного в воде вещества в виде зашумленного процесса, значения концентра ции, полученные в соответствии с выражением (5) складывались с равномерно распределенным на заданном интервале шумом.

На начальном этапе работы все АНПА движутся заданными курсами до тех пор, пока не будет обнаружен шлейф и получена аппроксимация границ фрагмента шлейфа. Затем организуется движение всех АНПА к предполагаемой оси шлейфа. На основе измерений, полученных всеми подводными аппаратами, уточня Сетецентрическое управление и многоагентные системы ется форма шлейфа. В процессе моделирования предполагалось, что комплексированная навигационная система АНПА обеспе чивает необходимую точность определения местоположения АНПА [2].


Процесс моделирования движения четырех АНПА к шлей фу из заданных начальных местоположений показан на рис. 3.

Рис. 3. Моделирование работы четырех АНПА для локализации шлейфа и поиска источника шлейфа Направление шлейфа и местоположение его источника в начальный момент времени неизвестны. Эллипсами отмечены стартовые положения АНПА 1-4. На данном рисунке показан модельный эксперимент, когда на начальном этапе траектории подводных аппаратов были направлены вправо. После того, как АНПА 1 обнаружил шлейф, выполнил траекторию в виде меан дра и передал информацию о положении осевой линии шлейфа другим АНПА, они скорректировали свои траектории и стали двигаться к рассчитанной центральной оси шлейфа.

В процессе моделирования работы, второй АНПА попадает в шлейф и выполняет процедуру определения осевой линии то Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

Рис. 4. Блок-схема алгоритма поиска источника шлейфа на основе использования группы АНПА Сетецентрическое управление и многоагентные системы В процессе моделирования работа алгоритма исследовалась при разных значениях уровня шумов в измерениях концентра ции растворенного вещества. Для получения статистических характеристик работы алгоритма использовался метод Монте Карло. При этом для каждого набора параметров выполнялось по 30 прогонов программы, соответствующих разным случай ным выборкам измерений.

Е, м 1, 1, 0, 0, 0, 0, 0, 0,000 0,200 0,400 0,600 0, а), м 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0,000 0,200 0,400 0,600 0, б) Рис. 5. Среднее значение (а) и дисперсия (б) ошибки определения положения источника шлейфа, в зависимости от уровня шумов в измерениях Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

На рис. 5 (а) показан график зависимости среднего значения ошибки определения местоположения источника шлейфа для реализаций при уровне шумов в измерениях от 0 до 80% от мак симального значения концентрации, а на рис. 5 (б) показан гра фик зависимости дисперсии ошибки определения местоположе ния источника шлейфа. Из результатов моделирования следует, что ошибка в определении местоположения источника шлейфа, вызванная шумом в измерениях, не превышают единицы мет ров. Полученная ошибка сравнима с ошибкой высокоточной навигационной системы АНПА. Данная точность достаточна для визуального обнаружения источника шлейфа при достиже нии подводным аппаратом предполагаемого местоположения источника, так как дальность видения под водой может состав лять 8-15 метров.

4. Заключение Рассмотренный в работе алгоритм поиска источника шлей фа основан на кусочно-линейной аппроксимации границ шлей фа. Для этого используется набор данных, собранный группой АНПА. Одним из достоинств алгоритма является то, что для поиска источника шлейфа используются не мгновенные значе ния градиентов концентрации, которые в реальной ситуации зашумлены из-за неоднородности и неравномерности движения воды в шлейфе, а данные, полученные из модельной аппрокси мации границ шлейфа, в которой все выбросы сглаживаются из за обработки исходных измерений с помощью МНК.

Использование группы АНПА позволяет повысить скорость локализации шлейфа, а также точность и надежность обнаруже ния источника шлейфа. Результаты моделирования подтвер ждают работоспособность и эффективность алгоритма. Данная работа выполнена при поддержке гранта РФФИ 100800249а.

Литература 1. БАБАК Л.Н., ЩЕРБАТЮК А.Ф. Некоторые методы оцени вания состояния водных акваторий с использованием авто Сетецентрическое управление и многоагентные системы номных необитаемых подводных аппаратов // Мехатроника, автоматизация и управление. - 2010 (в печати).

2. ВАУЛИН Ю.В., МАТВИЕНКО Ю.В., ЩЕРБАТЮК А.Ф.

Навигационное обеспечение автономного необитаемого подводного аппарата ММТ-3000 // Материалы XIV между народной конференции по интегрированным навигацион ным системам. - Санкт-Петербург, 2007. – С. 251-256.

3. BYRNE R. Algorithms and Analysis for Underwater Vehicle Plume Tracing / BYRNE R., ESKRIDGE S., HURTADO J. et al. / /SANDIA National Laboratories report. - 2004.

4. CANNELL Ch. J., GADRE A. S., STILWELL D. J. Boundary tracking and rapid mapping of a thermal plume using an auto nomous vehicle // Proceedings of the OCEANS 2006 MTS/IEEE Conference, September 18-21, 2006, Boston, USA, ISBN CD ROM: 1-4244-0115-1.

5. CHAPPELL S., KOMERSKA R., BLIDBERG D. at al. Recent Field Experience Using Multiple Cooperating SAUVs. // Pro ceedings of 15th International Symposium on Unmanned Unte thered Submersible Technology (UUST07), August 19-22, 2007, Durham, New Hampshire, USA.

6. FARRELL J.A. at al. Chemical Plume Tracing Experimental Results with a REMUS AUV. // Proceedings of the OCEANS 2003 MTS/IEEE Conference, September 22-26, 2003, San Di ego, USA, p.p. 962-968.

7. RAMOS P., MONEGO M., CARVALHO S. Spatial Distribution of a Sewage Outfall Plume Observed with an AUV. // Proceed ings of the OCEANS 2008 MTS/IEEE Conference, September 15-18, 2008, Quebec, Canada.

8. ROBBINS I. C., MOLINE M. A. Autonomous CDOM plume mapping in Penobscot bay, Maine: Remus operation and modu larity. // Proceedings of 15th International Symposium on Un manned Untethered Submersible Technology (UUST07), August 19-22, 2007, Durham, New Hampshire, USA.

9. SCHULZ B., HOBSON B. at al. Field results of multi-UUV missions using ranger micro-UUVs. // Proceedings of the OCEANS 2003 MTS/IEEE Conference, September 22-26, 2003, San Diego, USA, p.p. 956-961.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

ABOUT ONE ALGORITHM FOR UNDERWATER PLUME SOURCE LOCALIZATION BASED ON MULTI AUTONOMOUS UNDERWATER VEHICLES USAGE Larisa Babak, Far East State Technical University, assistant profes sor (lightsome@yandex.ru).

Аlexander Scherbatyuk, IMTP FEB RAS, PhD, head of laboratory (scherba@marine.febras.ru).

Abstract: The algorithm of underwater plume source localization based on approximation of plume boundary is considered in the pa per. More close decisions from different autonomous underwater vehicles have bigger weights for plume source position estimation.

Some modeling results of plume source localization for group of four autonomous underwater vehicles are supplemented.

Keywords: plume source localization, group of autonomous un derwater vehicles, motion trajectory.

Статья представлена к публикации членом редакционной коллегии О. П. Кузнецовым Сетецентрическое управление и многоагентные системы УДК 519. ББК 32.811. МУЛЬТИАГЕНТНАЯ СИСТЕМА ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАКАЗОВ Граничина Н. О. (Санкт-Петербургский государственный университет, Санкт-Петербург) Описывается сетевая математическая модель мультиагент ной системы для распределения заказов. Приводится пример для небольшой компании, занимающейся пассажирскими пере возками.

Ключевые слова: мультиагентная система, мультиагентное управление, план перевозки, оптимальный план перевозки.

1. Введение Открытый характер современного информационного об щества и глобальной рыночной экономики приводит к ускоре нию научно-технического прогресса и обострению конкуренции на рынках. Это заставляет предприятия искать новые методы и средства организации и управления, направленные на более качественное и эффективное удовлетворение индивидуальных запросов потребителей. Большинство современных систем характеризуются отсутствием средств своевременной иденти фикации новых потребностей и возможностей в среде, позво ляющих предприятию оперативно принимать эффективные решения по реконфигурации производственных, кадровых, финансовых и других ресурсов. Типичными примерами собы тий, вызывающих необходимость заново идентифицировать Граничина Наталья Олеговна, аспирант, Санкт-Петербургский государственный университет, (ngranichina@mail.ru).

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

Для решения подобных проблем применяются мультиа гентные технологии, в основе которых лежит понятие «агента».

Характерными особенностями агентов являются [2]:

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

– автономность, т. е. способность самостоятельно решать локальные задачи;

– активность, т. е. способность к активным действиям ради достижения общих и локальных целей;

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

– адаптивность, т. е. способность автоматически приспо сабливаться к неопределённым условиям в динамической среде.

Эти возможности кардинально отличают мультиагентные системы (MAC) от существующих «жестко» организованных систем.

Применение мультиагентных инструментальных средств позволяет решить ряд сложных задач производственной и транспортной логистики. Примером такого использования служит система, которая была разработана для одной из круп нейших в мире компаний корпоративного такси Addison Lee (Лондон). Система позволила распределять и планировать примерно 13 тысяч заказов в день при наличии нескольких Сетецентрическое управление и многоагентные системы тысяч собственных машин (из них до 800 постоянно на линии), оснащенных средствами GPS-навигации. При появлении нового заказа система автоматически находит наилучшую машину, получая сведения о координатах ближайших машин на элек тронной карте Лондона, и предварительно бронирует заказ.


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

Внедрение такой системы дало возможность роста ком пании за счет повышения управляемости. Существенно уве личилась эффективность автопарка (10–15%) благодаря опти мальному распределению заказов за счет минимизации «холо стого» пробега и времени простоя автомобилей. Также сокра тилось количество опозданий и время обслуживания заявок.

Но при всем многообразии реализаций MAC до сих пор не достаточно методологически разработаны математические модели и алгоритмы взаимодействия агентов, позволяющие вскрыть и проанализировать присущие им возможности к адап тации и самоорганизации. В статье будет обсуждаться построе ние соответствующих сетевых математических моделей и ал горитмов управления в MAC, а также приведен пример такой математической модели, что позволит формализовать новые Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

2. Математическая модель Система. Будем рассматривать абстрактную открытую сис тему, состоящую из n взаимодействующих агентов a1, a2, …, an, обрабатывающую поступающие в нее абстрактные заказы и выдающую результаты их обработки (рис. 1). Агенты взаимо действуют между собой в соответствии с графом потенциаль ных сетевых взаимодействий.

Рис. 1. Мультиагентная система обработки заказов Структура системы может меняться в процессе функциони рования. Для примера в дальнейшем будет рассматриваться система организации перевозок пассажиров и грузов.

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

Каждому агенту соответствуют такие ментальные кате гории как убеждения, желания и намерения (beliefs, desires and intentions – BDI) [7]:

- убеждения – представления о текущем состоянии среды;

Сетецентрическое управление и многоагентные системы - желания – состояния среды, в которые агент стремится сре ду перевести;

- намерения – множество избранных, совместимых и до стижимых желаний.

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

Обозначим A = {ai }i =1 – множество всех агентов.

n Можно выделить три аспекта, характеризующие агентов:

они содержат знания, они ощущают окружающую среду, они выполняют действия.

Обозначим R = {ri }i =1 – множество всевозможных раз q личных навыков, присущих агентам из множества A (ресурсы).

Для каждого агента зададим функцию ira(a): A 2q, кото рая определяет граф сетевых связей агентов с ресурсами. Учет этих, заранее заданных связей позволит сократить объем вычис лений при численном решении класса поставленных задач.

Будем рассматривать функционирование системы на неко тором интервале времени [0, T]. Физическая реализуемость агентов накладывает естественные ограничения сверху на воз можный объем задействованных в конкретный момент времени t s [0,T], ресурсов:

(1) xi (t ) Vi (a), где xi(t) – задействованный в момент времени t объем i- го ре сурса, Vi(t)- максимальный объем i-го ресурса для агента a (например, максимальное количество людей, которое может перевезти автомобиль).

Использование ресурсов естественно приводит к затратам, определяемым продолжительностью и объемом задей ствованного ресурса. Для каждого из ресурсов "i ira (a) про Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

изведенные на интервале времени [0, T] затраты естественно определять функционалом T (2) Li (a ) = li ( xi (t ), a ) dt, где li – некоторая функция, определяемая типом ресурса t, в ти пичных случаях li = 0 при x = 0 и li = 1 или li = x в остальных случаях.

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

Заказы. В систему поступает множество заказов разных ти пов. Обозначим z = { zi }i =1 – множество всевозможных типов m заказов.

Предположение. Будем считать, что для "z Z существует агент или группа агентов, которые в совокупности обладают объемом ресурсов, необходимым для его выполнения.

Пусть функция irzZ: Z 2q определяет набор ресурсов, ко торый необходим для выполнения заказа z и {vi ( z ), di ( z ) : i irz ( z )} – набор объемов ресурсов и длитель ностей их задействования при выполнении единичного объема заказа. Каждый заказ характеризуется временем поступления заказа, максимально допустимым временем выполнения, объе мом и максимальным временем на обработку заказов:

z = z(tcall, tmax, V, tfind), где tcall – время поступления заказа, tmax – максимальное время выполнения заказа в системе, V – объем заказа, tfind – максимальное время на обработку заказа.

Объем заказа определяется по формуле:

(3) V = vi ( z )d i ( z ).

iirz ( z ) Сетецентрическое управление и многоагентные системы Каждому заказу соответствует определенная группа аген тов, которая может его выполнять. Таким образом накладывает ся следующее ограничение:

n (4) "a A xiVi (a ) Vmin, iirz ( z ) где Vmin – минимальный объем ресурсов, необходимый для выполнения заказа z, а xi – объем i-го ресурса.

За выполнение каждого типового заказа определены та рифы. Считаем, что размер оплаты клиентом заказа прямо пропорционален тарифу и объему. Обозначим Si – сумма оплаты i-го заказа.

У каждого агента есть свои функции стоимости за поль зование тем или иным ресурсом, а у каждого заказа есть своя максимальная стоимость. Также определяется стоимость вза имодействия агентов между собой.

3. Постановка задачи В такой системе можно рассматривать несколько задач [4]:

- Нахождение допустимого плана перевозки.

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

m n f = Si - Li (a ) ® max.

(5) i =1 aA iira ( a ) Обычно решение задач оптимального управления трудно вычисляемо и часто бывает неустойчивым. На практике доста точно ставить задачу о почти оптимальном управлении и даже лучше о достижении заданного уровня рентабельности.

Обозначим:

m (6) C := Si, i = n (7) D := Li (a).

aA iira ( a ) Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

- Достижение заданного уровня рентабельности. Уровень рентабельности определяется отношением доходов к затратам.

C (8) P = 100% p fix.

D Решение последней задачи обычно обладает большей ус тойчивостью, и такого рода постановки целесообразнее исполь зовать при адаптивном выборе стратегии управления мультиа гентной системой [7].

- Достижение максимального уровня рентабельности.

C (9) P = 100% ® max.

D 4. Пример В качестве простого примера мультиагентной системы об работки заказов рассмотрим небольшую компанию, которая занимается транспортными перевозками. Исходные параметры системы:

· общее количество машин – 9: эконом-класс – 3, бизнес класс – 4, минивен (6 мест) – 1, автобус (20 мест) – 1;

· заказы поступают диспетчеру;

· диспетчер распределяет заказы по автомобилям;

· водитель получает 55% от суммы выполненного заказа, диспетчер – 10%;

· водители работают на собственных автомобилях, и бензин оплачивают сами;

· заказы могут выполняться только автомобилями из соб ственного автопарка компании;

Агентами в такой системе являются автомобили с води телями и диспетчеры A = {a1, a2, …, a10}, где a1 – агент-диспетчер, a2, …, a4 – агенты-водители автомобилей эконом-класса, a2, …, a4 – агенты-водители автомобилей бизнес-класса, a9 – агент-водитель минивена, a10 – агент-водитель автобуса.

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

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

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

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

Для диспетчера убеждениями будут знания о текущих зака зах, знания о предстоящих заказах, представления о ме сторасположении агентов-водителей, желаниями – получение Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

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

r1 – перевозка;

r2 – связь по телефону;

r3 – обработка заказа.

Тогда (10) ira (a1 ) = {r2, r3 } (11) ira ( ai : i = 2,...,10) = {r1, r2, r3 } Для каждого агента рассматриваемой системы определя ются ограничения на задействование ресурсов в каждый момент времени:

(12) "a A x2 (t ) (13) "a {a2,..., a8 } : x1 (t ) (14) a9 : x1 (t ) (15) a10 : x1 (t ) 21.

Для каждого агента определяются затраты на использо вание ресурсов в данной системе. Затраты на расход топлива при перевозке людей и порожнем рейсе определяются по фор муле:

T (16) L1 ( a ) = l1 ( x, a )dt.

Считаем, что количество пассажиров x не влияет на расход бензина. Тогда l1(x, a) = cp · ckm · vmid, если x 0 и l1(x, a) = 0, если x = 0 (автомобиль стоит на месте);

cp – стоимость бензина;

ckm – расход топлива на 1 км;

vmid – средняя скорость движения авто мобиля по городу.

В таблице 1 приведены параметры автомобилей с соот ветствующим расчетом функции l1(x, a). Считаем, что стоимость бензина составляет 21 руб. за 1 л.

Сетецентрическое управление и многоагентные системы Таблица 1. Параметры автомобилей Средняя Тип Расход Тариф скорость автомоби- l (x, a), при топлива на движения по 1 (r), ля / Кол-во x 1 км (ckm), л городу (Vmid), руб/км мест (m) км/ч Эконом- 0,1 50 105 класс/ Бизнес- 0,17 45 160,65 класс/ Мини- 0,2 45 189 вен/ Авто- 0,25 40 210 бус/ Расходы на пользование телефонной связью определяются по формуле:

T (17) L2 ( a ) = l2 ( x, a )dt.

где l2(x, a) = cconv, если x 0, и l2(x, a) = 0, если x = 0 (никто никому не звонит);

cconv – стоимость минуты разговора.

Заказом в рассматриваемой системе является запрос на пе ревозку людей: z – перевезти пассажиров. Тогда (18) irz ( z ) = {r1}..

Каждый заказ в системе характеризуется временем поступ ления заказа в систему и объемом заказа: z = z(tcall, V). Объем заказа включает в себя: время заказа, количество пассажиров, место отправления, место назначения. На таблице 2 показан пример поступления заказов в систему в течение половины рабочего дня. Координаты места отправления и назначения Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

попадают в квадрат 60 60, но чаще всего поездки происходят по центру города.

Таблица 2. Поступление заказов в систему Время Кол-во Конечная № по- Начальная Время пас- точка зака- ступ- точка мар заказа сажиров маршрута за ления шрута (x1, y1) q (x2, y2) заказа 1 8,14 10,11 12 (33,39;

30,81) (31,38;

38,1) 2 8,17 8,17 3 (24;

21,04) (34,77;

35,83) 3 8,68 9,86 4 (29,65;

30,19) (21,76;

25,13) 4 8,80 9,92 2 (26,02;

18,36) (27,56;

34,39) 5 8,94 9,48 2 (37,59;

35,53) (27,68;

25,2) 6 9,21 9,23 3 (32,07;

21,28) (41,91;

29,06) 7 9,42 9,83 1(6) (28,73;

23,16) (34,15;

24,59) 8 10,17 10,75 2 (21,88;

36,34) (37,8;

30,18) 9 10,20 10,70 4(6) (31,83;

27,43) (27,37;

32,15) 10 10,47 10,60 6 (28,37;

34,16) (31,51;

29,17) 11 10,65 11,32 2 (29,9;

28,11) (31,83;

30,3) 12 10,87 13,91 1 (20,78;

25,05) (40,53;

38,69) 13 11,64 11,66 3 (21,47;

29,14) (36;

38,73) 14 11,81 11,96 1 (19,25;

45,4) (25,96;

44,25) 15 12,12 12,89 2 (30,09;

34,23) (10,69;

33,71) 16 12,21 12,71 1 (20;

25,42) (13,64;

34,25) 17 12,38 13,51 1 (30,93;

30,49) (39,95;

30,96) 18 12,57 12,57 1 (21,79;

32,84) (25,16;

33,21) 19 12,62 13,87 1(6) (26,94;

24,15) (31,05;

42,54) 20 12,65 13,24 1 (25,57;

28,55) (15,4;

40,52) 21 12,87 13,09 2 (34,36;

33,7) (31,33;

38,03) 22 13,00 13,12 2(6) (23,62;

26,03) (30,75;

26,51) 23 13,70 14,01 1 (34,25;

25,52) (22,7;

30,03) Сетецентрическое управление и многоагентные системы Время Кол-во Конечная № по- Начальная Время пас- точка зака- ступ- точка мар заказа сажиров маршрута за ления шрута (x1, y1) q (x2, y2) заказа 24 14,26 14,35 3 (19,47;

30) (35,76;

22,51) 25 14,34 16,72 2(6) (26,88;

34,53) (39,34;

25,32) 26 14,35 15,47 5 (33,8;

32,13) (29,07;

30,06) 27 14,36 15,70 2 (30,6;

25,46) (41,6;

34,96) 28 14,87 15,66 1 (32,26;

33,52) (38,36;

30,26) 29 15,21 15,94 2 (32,29;

40,33) (31,36;

28,23) 30 15,21 16,43 1(6) (39,53;

21,46) (32,24;

25,65) Алгоритм выбора автомобиля реализуется следующим об разом:

1. Оценить количество пассажиров q:

· если q 4 и заказ на автомобиль бизнес-класса, то вы брать множество автомобилей K = {ai }i =5 ;

· если q 4 и заказ на автомобиль бизнес-класса, то заказ не может быть выполнен (так как в автопарке есть только легковые автомобили бизнес-класса);

· если q 21, то заказ не может быть выполнен;

· если q 21, то выбрать множество автомобилей K = {ai }i =1 : mi q.

2. Из множества K выбрать тот автомобиль, который находит ся ближе всего к заказу.

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

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

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

5. Если это время превышает максимальное время ожидания, то вернуться к п. 2 и выбрать автомобиль, средняя скорость движения которого выше выбранного ранее.

· если такого автомобиля нет в множестве K, то заказ не может быть выполнен;

· если такой автомобиль есть, то выполнить п. 3 и п. 4.

Рассмотрим систему оплаты. У каждого автомобиля есть свой тариф за 1 км езды – r. Также есть фиксированная сумма за посадку. Она для всех автомобилей рассматриваемой системы одинаковая – 150 руб. Дальность маршрута d i-го заказа рассчи тывается по формуле:

(19) d i = ( x1i - x2i ) 2 + ( y1i - y2i ) 2.

Первый заказ – заказ на перевозку 12 пассажиров. Если на него поедет автобус (20 мест), то стоимость поездки будет рас считываться как: Cz1 = d1 ra10 = 150 + 7,56 150 = 1284,3. Зарабо ток диспетчера в этом случае составит 128,43 руб. (10% от стоимости заказа). Чтобы рассчитать заработок водителя, необ ходимо сначала оценить, сколько он потратил бензина. Для этого нужно также рассчитать, какой расстояние ему по требовалось проехать до заказа. Точка отправления всех ав томобилей (место стационарной парковки) – (35;

32). Так как это первый заказ, то автобус двигался из начальной точки в точку (33,39;

30,81). Расстояние, которое проехал водитель складывается из расстояния до заказа – 2 км и дальности мар шрута на заказе – 7,56 км. Тогда расходы на бензин составляют – 50,21 руб., а заработок водителя за первый заказ – 656,16 руб.

Прибыль компании – 439,51 руб. (При расчете прибыли компа нии учитываются также расходы на телефонную связь, считая, что на обработку каждого заказа диспетчеру нужно 10 минут, а стоимость разговора – 1 руб./мин). Распределение заказов по автомобилям, а также расчет стоимости поездки и прибыли по каждому заказу приведен в таблице 3.

Из таблицы также видно, что на заказы, время до которых меньше 15-20 минут, ни одна машина доехать не успевает.

Сетецентрическое управление и многоагентные системы Итоговая оценка прибыли диспетчера, водителей и ком пании указана в таблице 4.

Таблица 3. Распределение заказов по автомобилям диспетчера, руб.

Расстояние до водителя, руб.

Прибыль, руб.

бензин, руб.

Автомобиль Расходы на заказа, руб.



Pages:     | 1 |   ...   | 9 | 10 || 12 | 13 |   ...   | 17 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.