Введение

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

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

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

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

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

В статье [Almeida A. ,  Ramalho G., Santana H.] патрулирование представлено в виде сложной многоагентной задачи. Кроме того, анализируются все подходы для стратегий патрулирования: эвристический, основанный на графах и т.д.

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

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

Предметом исследования является модель ориентированного взвешенного графа, построенного в соответствии с картой г. Петрозаводска.

Объект исследования- комбинаторные методы.

Целью данного исследования является изучение комбинаторной модели патрулирования на нелинейном графе с последующим анализом вероятности выигрышей участников. Для этого были осуществлены следующие задачи:

- построить граф, в котором вершины обозначают банкоматы ПАО «Сбербанк», а рёбрами являются дороги, соединяющие их, в соответствие с картой города Петрозаводска;

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

- определить вероятности поимки атакующего для каждого микрорайона города;

- проанализировать полученные результаты.

Постановка задачи

В данной работе рассматривается вариация задачи о патрулировании.Задана система связанных между собой взвешенных графов, по которой передвигаются два объекта. Первым является патрулирующий, а вторым – атакующий. Точками начала движения для обоих участников действия будем считать пару заданных условием вершин графа. Далее задачей атакующего будет произвести обход в глубину по графу, вершины которого представляют банкоматы ПАО «Сбербанк» города Петрозаводска. Время взлома банкомата (время нахождения атакующего лица в вершине) будем считать периодом игры. Цель патрулирующего – просчитывать кратчайшее расстояние до атакующего на каждом шаге и пытаться достигнуть его для осуществления задержания.

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

Для данного сценария построен граф, в соответствии с картой города Петрозаводска, разделенного на микрорайоны: Центр, Октябрьский, Кукковка, Голиковка, Древлянка, Ключевая. В каждом из них были отобраны банкоматы ПАО «Сбербанк» и занесены на граф в виде его вершин. Дугами являются пути между банкоматами с соответствующими длинами (расстояние от одного банкомата до другого).

На рис. 1 показан фрагмент карты, соответствующий району Голиковка г. Петрозаводска с нанесенными банкоматами.

Рис. 1 Фрагмент района Голиковка г. Петрозаводска

Аналогичным образом были построены графы, соответствующие остальным районам.

На рис. 2 приведен пример графа, соответствующего также району Голиковка.

Рис. 2. Фрагмент района Голиковка г. Петрозаводска в виде графа

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

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

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

Рассматривается сценарий для графа, определяющего одну из областей города Петрозаводска – район Голиковка. Зелёным цветом на рисунке обозначена точка начала для атакующей стороны, синим – точка начала движения патрулирующего. Первым действием атакующего будем считать начало взлома в точке A. В этот момент из точки H выдвигается патрулирующий. За первые 10 временных единиц (период игры) исполнения сценария атакующий взламывает банкомат в первой точке и выдвигается во вторую. Второй точкой для него может стать либо точка B, либо вершина H. В своей второй посещенной вершине он также производит взлом, на который он тратит 10 минут.

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

Программный комплекс покажет пройденные атакой и патрулём вершины и выведет сообщение о победившей стороне.

Табл.1 Результат работы программного комплекса для района Голиковка

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

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

В таблице 2 представлены итоговые результаты по каждому из районов.

Табл. 2 Итог работы программного комплекса

Итогом исследования являются следующие выводы:

1. Был построен граф, в котором вершины обозначают банкоматы ПАО «Сбербанк», а рёбрами являются дороги, соединяющие их, в соответствие с картой города Петрозаводска. 
2. Реализован на языке программирования Python алгоритм обхода графа в глубину. 
3. Реализован на языке программирования Python алгоритм Дейкстры поиска кратчайших. 
4. Были просчитаны вероятности поимки атакующего для каждого микрорайона города. 
5. Полученные результаты были благополучно проанализированы, результат анализа приводится в заключении работы.

Заключение

С помощью известных алгоритмов удалось получить достаточно интересные результаты для задачи патрулирования на нелинейном графе. Исходя из проведенного анализа можно заключить, что в районах Кукковка, Древлянка, Голиковка и Ключевая необходимо усилить качество патрулирования. К примеру, использовать второго патрулирующего. В районах Центр и Октябрьский уровень взломанных банкоматов гораздо ниже. Эти области города наиболее безопасные в сценарии задачи. Важно отметить, что задача имеет прикладной аспект, что, в свою очередь, дает возможность к дальнейшим фундаментальным исследованиям в этом направлении. Решение на нелинейном графе является относительно сложным. С помощью программного комплекса на языке Python были получены вероятности выигрышей между атакующей и патрулирующей сторонами.

Список литературы

Воробьев В. В. Система моделирования для задач коллективного патрулирования роботов. Москва, 2016. 1 c. Росреестр 28.10.2016 № 2016663799.

Гусев В. В. Теоретико-игровые модели поиска и патрулирования на графах : автореферат соискание ученой степени кандидата физико-математических наук. Петрозаводск, 2017. 16 с.

Киселев Л. В., Медведев А. В. Траекторное обследование границ морских акваторий группой автономных подводных роботов // Известия Южного федерального университета. Серия «Технические науки». 2018. № 3 (197). С. 185—197.

Решение задачи нахождения оптимального маршрута патрулирования действующих лесных пожаров в заданном районе // Научно-аналитический журнал Вестник Санкт-Петербургского университета Государственной противопожарной службы МЧС. 2021. № 3. С. 90–98.

Almeida A., Ramalho G., Santana H., [etc]. Recent advances on multi-agent patrolling // Brazilian Symposium on Artificial Intelligence - SBIA 2004 Brazil, September 29 - October 1. 2004. P. 474—483.