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

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

Получается удивительная аналогия с распространением света в оптически неоднородной среде:

• свет ищет путь минимального времени;

• нарушитель ищет путь минимального риска.

Математика оказывается одной и той же.

От вероятности обнаружения к геометрической оптике

Дизайнерам и художникам эту главу можно пропустить.

Пусть в каждой точке трёхмерного пространства

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

Например, эта вероятность может зависеть от расположения охраны, датчиков движения, освещённости, рельефа местности, подземных ходов и прочего.

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

Вероятность остаться незамеченным на одном таком участке равна

Тогда вероятность пройти весь маршрут без обнаружения определяется произведением

Работать с произведениями неудобно, поэтому перейдём к логарифму:

В пределе получаем интеграл вдоль траектории

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

Наиболее безопасный маршрут соответствует условию

Теперь сравним это выражение с принципом Ферма из геометрической оптики.

Согласно этому принципу луч света распространяется по траектории, минимизирующей оптическую длину пути

где — показатель преломления среды.

Сравнивая оба функционала, получаем естественное соответствие

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

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

Оптимальный маршрут злоумышленника - путь светового луча

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

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

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

Именно эта идея легла в основу дальнейших экспериментов с картами городов и системами видео- и другого (!) наблюдения.

Поиск маршрута: от A* к распространению волны

После построения карты проницаемости метод A* выглядит вполне естественно. Каждому пикселю можно сопоставить стоимость прохождения

где — локальная скорость распространения.

Белые области проходятся быстро, тёмные медленно, абсолютно чёрные - абсолютно непроходимые.

Но соответствует ли это исходной физической модели?

Вся предыдущая конструкция была основана на аналогии с распространением света в неоднородной среде. Свет не ищет путь с помощью A*. Свет распространяется одновременно во всех направлениях.

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

Теперь, читатель, представим горный склон после сильного дождя в штате Орегон.

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

Часть потока пойдёт быстрее.

Часть медленнее.

Где-то вода упрётся в препятствие.

Где-то найдёт обходной путь.

Через некоторое время каждая точка поверхности будет знать минимальное время, за которое до неё может добраться вода. Если вода туда добралась.

Эту идею используем для поиска маршрута.

В стартовой точке создаётся волновой фронт.

Далее он распространяется по карте со скоростью

В результате для каждой точки пространства вычисляется функция

которая показывает время прихода воды (света) в эту точки.

После завершения расчёта никакого маршрута ещё нет.

Есть только поле времён распространения.

На рисунке размером 2048 на 2048 пикселей представить это поле как карту высот.

Низкие значения соответствуют труднодоступным областям.

Высокие значения — областям, до которых волна добирается быстро.

Теперь начинается вторая часть алгоритма.

Чтобы построить обратный маршрут из точки B в точку A, достаточно двигаться в направлении наибольшего уменьшения функции T.

Или, если использовать физическую аналогию, бросить шарик на получившийся рельеф.

Шарик сам скатится в стартовую точку по траектории минимального времени.

Математически это соответствует движению по антиградиенту поля

В результате маршрут появляется автоматически как следствие распространения волны.

Никакого специального алгоритма поиска пути больше не требуется.

Фактически задача поиска маршрута заменяется двумя значительно более физичными этапами:

1. Распространить волновой фронт по всей области.

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

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

Почему Corona SDK (Solar2D)

Несмотря на то, что задача выглядит достаточно математической, для реализации прототипа я использовал не Python и не MATLAB, а игровой движок Solar2D (бывший Corona SDK).

Причин было несколько.

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

Во-вторых, Lua остаётся одним из самых простых языков для быстрого создания подобных экспериментальных моделей.

И вообще, последние 10 лет я пишу игрушки только на Короне и не знаю других инструментов)

В моём прототипе карта хранится как обычное изображение в градациях серого размером 2048×2048 пикселей. После загрузки PNG-файл преобразуется в массив коэффициентов проницаемости

Каждый пиксель становится элементом вычислительной сетки.

Светлые области соответствуют высокой проходимости, тёмные — низкой.

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

После этого выполняются три основных этапа:

1. Построение поля проницаемости среды.

2. Распространение волнового фронта от стартовой точки.

3. Восстановление оптимальной траектории по градиенту поля времени.

С точки зрения программирования наиболее интересен второй этап.

Вместо перебора маршрутов строится поле минимальных времён достижения

После вычисления поля T(x,y) маршрут восстанавливается. Из конечной точки выполняется движение по направлению максимального уменьшения функции времени, то есть по антиградиенту поля.

Отдельный модуль реализует систему расстановки камер, радаров или что там у вас есть в вашей системе ПВО.

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

в котором вклад каждой камеры уменьшается пропорционально квадрату расстояния (
вы можете использовать ИИ для различных вариантов расчетов коэффициентов проницаемости)

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

В результате на одном экране можно одновременно наблюдать:

• карту местности;

• расположение камер;

• зоны наблюдения;

• оптимальный маршрут без учёта наблюдения;

• оптимальный маршрут с учётом наблюдения.

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

Модельные расчеты

Возьмем двухмерную (у трехмерной - гриф СС) картинку без радаров и построим маршрут злоумышленника

Теперь добавим несколько радаров (СБ не лыком шита и знает теперь где перекрыть)

Вы, этакий вы злодей, снова нашли уязвимость? СБ поставит еще несколько камер

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

Выводы

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

(с) Написана ИИ при поддержке автора