Материал: Оптимизация и моделирование в автоматизированных системах

охранник, то нарушителя считаем обезвреженным, если хотя бы один робот оказался в данной ячейке в следующий момент времени tk+1, то есть одному из роботов достаточно остаться в данной ячейке для нейтрализации нарушителя.

Пусть общее число роботов меньше числа ячеек M<XY, в противном случае имеется тривиальное решение для защиты территории Z без затрат на перемещение роя: нужно разместить хотя бы по одному роботу в каждом квадрате охраняемой территории.

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

d (mx1 y1 , mx2 y2 )= x1 − x2 + y1 − y2 .

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

d(mx1 y1 ,mx2 y2 )= (x1 − x2 )2 + (y1 − y2 )2

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

ся эллиптическими метриками

d(mx1 y1 ,mx2 y2 )= a2 (x1 − x2 )2 + b2 (y1 − y2 )2 ,

d(mx1 y1 z1 ,mx2 y2 z2 )= a2 (x1 − x2 )2 + b2 (y1 − y2 )2 + c2 (z1 − z2 )2 .

Возможно также введение метрики без аксиом симметрии d(A,B)=d(B,A)

и\или отделимости

d(A,B)=0 ↔ A=B.

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

Общие затраты S(a(tk),q(tk)) на ликвидацию атаки a(tk) в момент tk определим суммой затрат на перемещение роя роботов из квадратов его размещения q(tk) в момент tk в квадраты c нарушителями. Так как M ≥ N , то задача нейтрализации нарушителей выполнима всегда, но в зависимости от назначения робо- там-охранникам тех или иных целей-нарушителей суммарная стоимость реализации будет различной. Минимизируем её:

S(a(tk),q(tk))→min.

Исходя из методики, описанной в [5], возможно рассчитать расстояние для перемещения робота из ячейки, в которой он находится в момент tk, в ячейку, в которой он должен оказаться в момент tk+1.

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

130

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

a(t1)=(m12,m23,m33), q(t1)=(m11,m12,m21).

Один из её нескольких оптимальных планов:

– робот в клетке m12 остаётся на месте для нейтрализации нарушителя в своей ячейке;

– робот из клетки m11 нейтрализует нарушителя в клетке m23;

– робот из клетки m21 нейтрализует нарушителя в клетке m33;

– суммарные затраты S(a(t1),q(t1))=6.

Таким образом, найден один из элементов матрицы переходов автомата

K(A,Q):

q((m11,m12,m21),(m12,m23,m33),t2)=(m23,m12,m33).

Представление конечного автомата каноническим уравнением

q(qk,ak)=qk+1,

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

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

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

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

ни tk→tk+1. Возникающая многокритериальная оптимизационная задача (минимум затрат на нейтрализацию нарушителей за 2-3-… такта времени с учётом минимума ущерба от нарушителей, просуществовавших до нейтрализации лишние такты времени) заметно усложняет исследование. Она сводится к однокритериальной введением метрики расстояний между клетками области Z, учитывающей вероятность ущерба от прорыва нарушителей при недостатке робо- тов-охранников.

Построение совершенной дизъюнктивной нормальной формы, обеспечивающей переход роя из состояния qk в состояние qk+1 в соответствии с решени-

131

ем, предложенным транспортной задачей линейного программирования, завершает определение искомого конечного автомата K(A,Q).

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

Предложенная модель обобщается на случай произвольной области Z с помощью формализации задачи графом с соответствующей метрикой расстояний между вершинами [1,2].

Алгоритм расчёта кратчайших расстояний между вершинами. Для произвольного орграфа с размеченными дугами дадим следующий матричный алгоритм расчёта парных кратчайших расстояний между вершинами графа G. Предположим отсутствие в орграфе циклов отрицательной длины [1].

Пусть n – матрица меток дуг графа G с петлями неотрицательной

i, j=1

цены ωii ≥ 0 . Несмежность вершин xi и xj оценим бесконечностью. В программной

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

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

Найдём кратчайшие расстояния от вершины x1 до всех остальных вершин. Для этого применим следующие преобразования 1-4 матрицы Ω.

1. Начнём с матрицы

2. Поэлементно прибавим правый столбец окаймления по очереди ко всем остальным столбцам:

3. Заменим нижнюю строку окаймления минимумом элементов соответствующего столбца, включая соответствующий элемент нижней строки окаймления:

132

4. Если нижняя строка окаймления совпала с правым столбцом окаймления, то наименьшие суммарные длины путей найдены. В противном случае заменим правый столбец окаймления матрицы Ω1 транспонированной нижней строкой:

и перейдём к шагу 2.

Будем повторять шаги 2 -4 до тех пор, пока окаймление не перестанет изменяться. На этом алгоритм нахождения кратчайших расстояний от вершины x1 до всех остальных вершин графа G свою работу завершает.

Аналогично применяем алгоритм для расчёта наименьших суммарных цен путей от оставшихся вершин x2, x3, …, xn до остальных. Например, для нахождения наименьших суммарных цен путей от вершины x2 в п.1 рассмотрим матрицу

и так далее.

Бесконечные значения кратчайших расстояний означают отсутствие пути, соединяющего вершину x1 с соответствующей вершиной. Аналогично применяем алгоритм для расчёта наименьших суммарных цен путей от оставшихся вершин x2, x3, …, xn до остальных. При этом нулевое начальное значение на шаге 1 размещается в соответственно 2-й, 3-й и т.д. строке.

Привлечение алгоритма решения транспортной задачи линейного программирования позволяет построить кратчайшие расстояния на булеане 2V множества V вершин графа G(V,R).

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

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

133

ственного кластера с центром в полученной вершине на множестве вершин графа G.

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

Продолжая наращивать число кластеров, переберём все варианты разбиения n-элементного множества вершин графа G на кластеры.

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

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

Оптимизация производится в том числе с учётом неоднородности роя ро- ботов-охранников и роя нарушителей. Разрешимы случаи различной мощности этих роёв. Учитываются разные критерии оптимальности альтернативного решения задачи:

–минимальное число тактов времени нейтрализации;

–максимальная вероятность полного уничтожения нарушителей;

–минимизация ущерба при многотактовой нейтрализации;

–минимизация суммарных затрат на транспортные затраты роя роботовохранников;

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

Литература

1.Котенко, А.П. Матричный алгоритм Беллмана–Мура / А.П. Котенко // Управление организационно-экономическими системами. Сборник научных статей. Вып. 10. Самара: СГАУ, 2013. С. 33-37.

2.Котенко, А.П. Индуцирование метрики на булеане вершин графа со взвешенными рёбрами / А.П. Котенко, Е.Д. Шикина // Интеллектуальные информационные системы: труды Всероссийской конференции (2017, Воронеж), ч.1. – Воронеж: Издательство ВГТУ, 2017. – С. 124-127.

3.Котенко, А.П. Матричная реализация алгоритма подбора числа кластеров размеченного графа / А.П. Котенко, М.С. Щербаков // Информационные технологии и нанотехнологии: материалы Международной конференции (2016, Самара). Самара: Издательство Самарского научного центра РАН, 2016. С.

877-879.

134