Главная

Исследовательские группы

Научно-практический журнал
Хвойные бореальной зоны
(в перечне ВАК)

Такие опасные явления, как лесные пожары, требуют оперативного принятия решений о назначении маршрутов доставки средств борьбы с ними к очагам пожара, определения оптимальных траекторий их локализации. Задача маршрутизации значительно усложняется при учете рельефа местности и проходимости по маршруту в условиях неопределенности и стохастичности данных.
Разработка специального математического и программного обеспечения информационной системы поддержки принятия решений, в контексте задач управления борьбой с лесными пожарами, является актуальным направлением в связи со значительным экологическим и материальным ущербом от лесных пожаров природной среде, а также угрозы для жизни людей, оказавшихся в зоне их действия. Величина ущерба возрастает в результате неверного прогноза развития пожара, недооценки действия сопутствующих факторов (например, задымленности территории), ошибки в тактике борьбы с огнем и выборе маршрутов выхода из зоны действия пожара. Это ведет к слишком позднему осознанию опасности и как следствие, недостатку времени для оперативных мероприятий.
Внедрение в практику борьбы с лесными пожарами современных средств обнаружения, методов прогнозирования их распространения и развития, дает возможность планирования и применения новых тактических приемов борьбы с лесными пожарами с учетом различных возможных ситуаций развития.
Нами рассматриваются следующие задачи: задача расчета областей достижимости, задача построения траекторий оптимальной локализации лесного пожара, задача расчета оптимальных маршрутов доставки противопожарных сил и средств с учетом рельефа местности и визуализация результатов на трехмерной сцене.
Универсальность задач оптимизации и управления связана с возможностью описания математических моделей процессов в виде дифференциальных уравнений баланса сил, действующих на систему, либо в виде вариационных принципов, из которого эти уравнения следуют. Теория оптимального локализационного управления описана в работах [2, 7].
Прямые методы решения вариационных задач Эйлера, Ритца и другие, требуют выполнения большого объема вычислений и вызывают существенные трудности при реализации на специальных вычислительных структурах. В.В. Васильев [1] разработал метод приближенного решения задач оптимального управления, основанный на сведении исходной оптимизационной задачи к задаче определения кратчайшего пути на графе-решетке, покрывающей область определения функционала. Область Q определения функционала покрывается решеткой некоторой заданной конфигурации. Границы области Q изображаются некоторым подмножеством узлов решетки. Решение вариационной задачи с заданными граничными условиями сводится к нахождению оптимального (например, кратчайшего) пути на решетке с заданными весами ребер между узлами, а длина оптимального пути соответствует значению функционала для полученной аппроксимации.
Если рассмотреть систему управления, объектом которой является процесс распространения лесного пожара (ЛП), а субъектом – силы и средства борьбы с ним, то качество системы управления можно определить функционалом, который характеризует обобщенные затраты на борьбу с ЛП и учитывает затраты, обусловленные продолжительностью локализации (PT), площадью ПР (PS) и длинной заградительного барьера (локализующей кривой) (PL).

J = PT + PS + PL ,

(1)

где ;

;

;

X(t) = (X1(t), X2(t))T – координаты подвижного конца заградительного барьера в момент времени t;
X0 = (X01, X02)T – координаты места возникновения очага ЛП; Сi(X,t);
 - функции затрат на единицу времени локализации, единицу площади ЛП, единицу длины создаваемого заградительного барьера;
t0, tk – время начала и окончания процесса локализации;
А - коэффициент, определяющий направление локализации относительно Х0 (А = 1 при локализации по часовой стрелке, А = -1 при локализации против часовой стрелки).
Система ограничений учитывает предельную скорость локализации

,             ,

(2)

направление локализации относительно центра ЛП

,

(3)

минимальное расстояние от заградительного барьера до кромки ПР в момент локализации t

X(t) = {x(t) : F(t, x(t), h) ? 0},

(4)

где ;
u(t) = (u1(t), u2(t))T – скорость процесса локализации;
U(X,t) – максимально возможное значение скорости локализации;
F(t, x(t), h) = 0 – уравнение, определяющее множество точек x(t), отстоящих на расстоянии h от кромки ЛП.
Условию F(t, x, 0) ? 0 соответствует область ЛП в момент времени t (определяется моделями процесса распространения). Оптимальные траектории локализации ЛП определяются решением краевой задачи для нелинейных дифференциальных уравнений. Их аналитическое решение возможно для сравнительно простых частных случаев [7].
В общем случае численное решение задачи (1) – (4) может быть получено алгоритмом кратчайшего пути на графе-решетке, покрывающей область определения функционала (1). Неоднозначность области и другие ограничения геометрического характера на вид искомого решения отображаются соответствующей структурой решетки. Ребрам решетки приписываются веса, пропорциональные значениям вариационного интеграла, взятого вдоль соответствующих ребер.
Для решения поставленных задач управления разработаны алгоритмы МАФВ (модифицированный алгоритм фронта волны), ДМВА (двухволновой модификации волнового алгоритма) [3-6]. Алгоритм МАФВ основан на алгоритме фронта волны или алгоритме Ли. В алгоритме фронта волны точка старта становится центром серии концентрических квадратных волн со стороной m, где m = 2n + 1, n возрастает от 1 и до тех пор, пока все точки на стороне внешней волны не будут касаться границ рассматриваемой решетки.
Каждая из образованных концентрических волн является траекторией для лево- или право- стороннего обхода, в ходе которого поочередно для каждой из точек, входящих в контур, анализируются состояния соседних точек в соответствии с выбранным шаблоном. На основании анализа, из множества альтернативных точек выбирается та, для которой стоимость перехода из нее в текущую точку контура будет минимальной. Вычисленная стоимость перехода закрепляется за этой точкой для последующего использования. Затем размер стороны квадратной волны увеличивается, и процесс повторяется до тех пор, пока не будут осмотрены все точки решетки.
После завершения процесса распространения волн, строится итоговый маршрут. Для этого циклически перебираются возможные точки движения, начиная с точки финиша и по направлению убывания вычисленных стоимостей перехода. Движение происходит до тех пор, пока не будет встречена точка старта.
Наиболее простой и в то же время достаточно эффективный способ решения задач локализационного управления заключается в рассечении пространства карты некоторым лучом, исходящим из центра очага ЛП и проходящим через начальную точку локализирующей кривой. Проведя растрезацию луча на поле карты, и объявив попавшие в него ячейки, как абсолютное препятствие, независимо от первоначального типа ячеек, получаем естественное, с точки зрения волнового процесса, ограничение на движение в заданном направлении. Задаем точки начала и окончания локализирующей кривой на минимальном расстоянии по разные стороны от проведенного луча. Решая полученную задачу локализационного управления волновым алгоритмом, получим необходимую замкнутую кривую локализации процесса распространения, которая соответствует минимизации функционала (1) решаемой задачи [3, 6].
Алгоритм МАФВ показал хорошие результаты при расчетах оптимальных траекторий локализации на картах пересеченной местности. Однако вычислительные эксперименты показали существенное снижение быстродействия алгоритма МАФВ при расчете областей достижимости при наличии протяженных непроходимых препятствий и сильном изгибе итоговой траектории оптимального маршрута. Причина низкого быстродействия – большое число повторных вычислений в блоке уточнения результатов расчета при выполнении итераций.
В значительной степени отмеченные недостатки устранены в разработанной двухволновой модификации волнового алгоритма ДМВА. При работе алгоритма ДМВА топографическая карта покрывается матрицей ячеек. Создается два списка координат ячеек. Первоначально первый список содержит координаты точки старта (или точек области старта), второй список пуст. Затем перебираются ячейки из первого списка и для каждой из них просматриваются соседние ячейки в соответствии с заданным шаблоном связей. После перебора всех ячеек с координатами из первого списка – первый и второй списки меняются местами, и процесс повторяется, до тех пор, пока не будет рассчитано значение функционала во всех ячейках.
Вычислительные эксперименты показали, что с увеличением числа узлов решетки, эффективность алгоритма ДМВА возрастает по сравнению с алгоритмом МАФВ. Сравнительные характеристики алгоритмов МАФВ и ДМВА представлены в таблице 1.

Таблица 1 – Сравнительная характеристика алгоритмов МАФВ и ДМВА

Размер карты	Время работы МАФВ, T1,с.	Время работы ДМВА, Т2,с.	Т1/Т2
100 х 100	2,5	2,5	1,00
500 х 500	7,0	4,0	1,75
1000 х 1000	26,0	11,0	2,36

Алгоритм ДМВА имеет преимущество в скорости работы на больших картах; позволяет одновременно моделировать несколько процессов распространения на одной и той же карте; автоматически обрабатывать ситуации взаимного пересечения фронтов различных процессов распространения [6].
На базе алгоритмов МАФВ и ДМВА в среде DELPHI реализована система поддержки принятия решений Раннер [4], защищенная 3 свидетельствами об официальной регистрации программы для ЭВМ (№ 2006611299, 2006611353, 2006612749). У пользователя системы имеются возможности изменения скорости движения по конкретным дорогам, задания дополнительных областей с пониженной или повышенной проходимостью, определения областей достижимости на определенный момент времени.
Система позволяет моделировать ситуации «А что если…?». Что будет, если в определенном районе пройдет дождь? Что будет, если, начав движение по определенному маршруту, неожиданно обнаружится препятствие? Как повлияет изменение погодных условий на проходимость выбранных дорог? И т.д.
Использование трехмерной графики, для представления результатов расчетов маршрутов движения позволяет более адекватно оценивать особенности предполагаемого маршрута движения на местности с различным рельефом наиболее естественным для человека способом, что важно при принятии управленческих решений [4].
Модуль трехмерной визуализации обеспечивает отображение результатов расчетов на трехмерной карте местности. Поддерживается масштабирование изображения для детализации отдельных участков или охвата всей карты целиком. Свободное управление камерой позволяет оценить маршрут с любого удобного ракурса.

Библиографический список

• Васильев, В.В. Моделирование задач оптимизации и дифференциальных игр / В.В. Васильев, В.Л. Баранов. – Киев: Наук. думка, 1989. – 296 с.
• Доррер, Г.А. Математическое моделирование процессов распространения лесных пожаров и борьбы с ними / Г.А. Доррер, С.В. Ушанов, Н.Г. Бархатов // Изв. вуз. Лесной журнал. - 2000. - № 2. - С. 31 – 36.
• Ушанов, С.В. Математическое моделирование систем локализации процессов распространения / С.В. Ушанов, О.В. Фадеенков // Вестник КрасГАУ. – 2006. - № 12. -С. 40-42
• Ушанов, С.В. Компьютерная система поддержки принятия решений в задачах оптимальной маршрутизации / С.В. Ушанов, О.В. Фадеенков // Вестник КрасГАУ. – 2006. - № 13. - С. 104-107
• Ушанов, С.В. Применение метода «бегущей волны» для решения задач маршрутизации и локализационного управления процессами распространения / С.В. Ушанов, О.В. Фадеенков, В.М. Груманс // Лесоэксплуатация. - 2004. - Вып. 5. - С. 181 – 184.
• Фадеенков, О.В. Оптимальная маршрутизация при управлении борьбой с лесными пожарами: автореф. дис. …канд. техн. наук / О.В. Фадеенков. – Красноярск, 2006. – 20 с.
• Dorrer, G.A. Mathematical Modelling Optimization of forest fire localization Processes/ G.A. Dorrer, S.V. Ushanov // Fire in Econsistems of Boreal Eurasis. – London. - 1997. - Р. 303-313.