Добраться до центра

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

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

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

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

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

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

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

$[\mathbf r=(x,y,z)]$

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

$[p(\mathbf r)]$

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

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

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

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

$[P_{safe}(\Gamma)=\prod_i (1-p_i)]$

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

$[-\ln P_{safe}(\Gamma)=-\sum_i \ln(1-p_i)]$

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

$[R(\Gamma)=\int_\Gamma-\ln(1-p(\mathbf r))ds]$

Функционал $(R(\Gamma))$ можно интерпретировать как накопленный риск обнаружения.

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

$[R(\Gamma)\rightarrow \min]$

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

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

$[\int_\Gamma n(\mathbf r)ds ]$

где $(n(\mathbf r))$ — показатель преломления среды.

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

$[n(\mathbf r)=-\ln(1-p(\mathbf r))]$

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

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

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

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

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

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

$[n(\mathbf r)=-\ln(1-p(\mathbf r))]$

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

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

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

$[cost=\frac{ds}{v(\mathbf r)}]$

где $(v(\mathbf r))$ — локальная скорость распространения.

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

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

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

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

Представим горный склон после сильного дождя.

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

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

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

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

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

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

Именно эту идею мы используем для поиска маршрута.

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

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

$[v(\mathbf r)]$

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

$[T(\mathbf r)]$

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

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

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

На рисунке ниже его удобно представить как карту высот.

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

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

Теперь начинается самая интересная часть.

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

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

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

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

$[\frac{d\mathbf r}{ds}=-\nabla T(\mathbf r)]$

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

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

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

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

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

Почему Corona SDK (Solar2D)

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

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

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

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

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

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

$[v(x,y)\in[0,1]]$

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

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

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

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

Построение поля проницаемости среды.
Распространение волнового фронта от стартовой точки.
Восстановление оптимальной траектории по градиенту поля времени.

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

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

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

Отдельный модуль реализует систему видеонаблюдения.

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

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

$[C(r)\sim \frac{1}{r^2}]$

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

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

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

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

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

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

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

Вы снова нашли уязвимость? Поставим еще несколько камер

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

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

Злоумышленник не сдается - нашел новый путь

Выводы

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

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

推荐订阅源

Все публикации подряд на Хабре