СИСТЕМА ДЛЯ ВЫБОРА КРАТЧАЙШЕГО БЕЗОПАСНОГО МАРШРУТА СПАСЕНИЯ ЛЮДЕЙ ИЗ ГОРЯЩЕГО ЗДАНИЯ НА ТЕРРИТОРИИ МОРСКОГО ПОРТА
Авторы:
1.
Военный учебно-научный центр Военно-Морского Флота «Военно-морская академия»
2.
Калининградский государственный технический университет
(доцент секции защиты в чрезвычайных ситуациях кафедры техносферной безопасности)
Россия
Россия
Тип:
Статья
Страницы:
с 144
по 152
Статус:
Опубликован
Получено:
05.04.2013
Одобрено:
25.04.2013
Опубликовано:
25.04.2013
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 656.6.08: 004.9
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ББК 60.822я73, 32.81
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 656.6.08: 004.9
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ББК 60.822я73, 32.81
Язык материала:
русский
Ключевые слова:
спасение людей, кратчайший безопасный маршрут, теория графов, алгоритм Флойда – Уоршелла
Аннотация (русский):
Предложена система для выбора кратчайшего безопасного пути спасения людей из горящего здания в морском порту. Система предназначена для руководителя тушения пожара, принимающего решения в сложной обстановке. Для решения задачи выбора оптимального пути спасения людей обоснована целесообразность применения элементов теории графов. В процессе разработки системы на основе алгоритма Флойда – Уоршелла создана математическая модель выбора кратчайшего безопасного пути с учетом динамики развития пожара. Создана база данных, обеспечивающая их эффективное хранение и использование. Оценены результаты выбора оптимального пути спасения людей из горящего здания.
Предложена система для выбора кратчайшего безопасного пути спасения людей из горящего здания в морском порту. Система предназначена для руководителя тушения пожара, принимающего решения в сложной обстановке. Для решения задачи выбора оптимального пути спасения людей обоснована целесообразность применения элементов теории графов. В процессе разработки системы на основе алгоритма Флойда – Уоршелла создана математическая модель выбора кратчайшего безопасного пути с учетом динамики развития пожара. Создана база данных, обеспечивающая их эффективное хранение и использование. Оценены результаты выбора оптимального пути спасения людей из горящего здания.
Ключевые слова:
спасение людей, кратчайший безопасный маршрут, теория графов, алгоритм Флойда – Уоршелла
спасение людей, кратчайший безопасный маршрут, теория графов, алгоритм Флойда – Уоршелла
Введение Известно, что тушение пожара на территории морского порта (МП) представляет собой комплекс управленческих решений по обеспечению безопасности людей, животных, спасению материальных ценностей, локализации и ликвидации горения [1]. При этом в комплексе решаемых задач защита людей является определяющей. К способам защиты людей, находящихся в зоне воздействия опасных поражающих факторов пожара, относится спасение их из горящего здания. Для этого руководитель тушения пожара (РТП) должен выбрать маршрут движения по оптимальному пути исходя из условий обеспечения безопасности спасаемых и самих пожарных, а также минимизации временных затрат. Как правило, на формирование РТП ясного и однозначного решения в данной чрезвычайной ситуации влияют: - личностные факторы, определяемые своеобразием психических процессов, состояний и качеств РТП; - ситуационные факторы – конкретные обстоятельства, в которых принимается управленческое решение, влияющее на разработку, оценивание, выбор и реализацию альтернатив. К основным ситуационным факторам следует отнести [2]: - недостаток достоверной информации о динамике развития пожара и действиях расчётов; - недостаток времени для всестороннего анализа обстановки; - отсутствие достоверного прогноза развития пожара; - высокую ответственность за последствия принимаемых решений; - значительную скорость изменения параметров чрезвычайной ситуации; - недостаток информации о горящем объекте и др. Кроме того, развитие технократического общества привело к усложнению структуры портов, увеличению плотности застройки, в том числе и нетиповой, что существенно снижает эффективность борьбы с пожаром и спасения людей. В указанных условиях выбор оптимального пути движения является крайне сложным процессом, и вероятность принятия руководителем ошибочного решения существенна. Ошибочно выбранный маршрут нередко становится причиной травмирования и гибели как спасаемых, так и пожарных, приводит к увеличению времени спасательных работ, замедляет процесс тушения пожара и становится причиной дополнительного ущерба. На основании вышеизложенного можно констатировать, что в экстремальной ситуации повышение достоверности выбора РТП пути спасения людей из горящего здания является актуальной научной задачей. Для ее решения была разработана и лицензирована компьютерная система выбора пути спасения людей на территории Калининградского морского торгового порта (свидетельство о государственной регистрации программы для ЭВМ № 2013610641). Данная система была интегрирована в интеллектуальную систему поддержки принятия решений (СППР) на базе нечетких нейронных сетей Sugeno и ANFIS (свидетельство о государственной регистрации программы для ЭВМ № 2013610686), определяющую ранг пожара [3]; прогноз развития огня и теплового излучения как наиболее опасных факторов пожара. Основные задачи, решаемые при разработке СППР для выбора оптимального пути спасения людей Система поддержки принятия решения – это система, предоставляющая руководителю данные, знания, выводы и (или) рекомендации для принятия обоснованного управленческого решения. Для разработки СППР необходимо последовательное решение следующих основных задач: 1) выбор метода для определения оптимального пути спасения людей; 2) определение структуры СППР; 3) разработка алгоритма выбора оптимального маршрута спасения; 4) запись алгоритма решения в виде программного кода на языке программирования; 5) формирование базы данных системы; 6) проектирование пользовательского интерфейса с последующим тестированием и отладкой; 7) тестирования СППР с последующей отладкой. Выбор метода для определения оптимального пути спасения людей В ходе решения первой задачи разработки СППР выполнен анализ рационального программно-алгоритмического обеспечения данных систем. В ходе выполнения анализа была исследована методологическая база в предметной области исследования. Установлено, что лучшие результаты удается получить при использовании методов теории графов. Ее применение позволяет при минимальных временных и материальных затратах получать достаточно точные результаты и визуализировать их. Определение кратчайшего пути спасения представляет собой решение задачи выбора оптимального маршрута в некоторой сети с предварительно заданной топологией. При решении задачи под топологией понимается конфигурация графа, под вершинами – узлы развязки сети, под ребрами – направления движения расчетов. Согласно [4], в практике при решении задач определения оптимального пути наиболее широкое применение нашли три алгоритма: алгоритм Дейкстры; алгоритм Флойда – Уоршелла; алгоритм Беллмана – Форда. Алгоритм Дейкстры предназначен для определения кратчайших путей из одной вершины взвешенного ориентированного графа G = (V, E), где V – множество графа вершин; E – множество дуг графа, с исходной вершиной s, в котором веса всех рёбер неотрицательны [5]. Суть алгоритма Дейкстры заключена в поэтапном наращивании дерева кратчайших маршрутов от исходного узла. В процессе работы метода требуется обязательное выполнение условия: после добавления на каждом этапе линии связи и узла обновленный маршрут должен быть минимальным по всем оконечным узлам, еще не вошедшим в дерево. В ходе построения дерева кратчайших путей определяются векторы весов маршрутов, а также корректируются векторы начальных компонент путей. Алгоритм Флойда – Уоршелла позволяет находить кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа [5]. Данный алгоритм основан на том факте, что в графе, не имеющем отрицательных ребер, всякий неэлементарный кратчайший путь состоит из совокупности элементарных кратчайших путей. Алгоритм Флойда – Уоршелла является более общим по сравнению с алгоритмом Дейкстры, поскольку он позволяет находить кратчайшие пути между любыми двумя вершинами графа. Алгоритм содержит три вложенных цикла, т. е. имеет кубическую сложность. Алгоритм Беллмана – Форда – алгоритм поиска кратчайшего пути во взвешенном графе. Алгоритм находит кратчайшие пути от одной вершины графа до всех остальных [5]. Для подсчета кратчайшего пути с его использованием требуется провести всего циклов. Однако в практической работе данный алгоритм можно использовать и для отслеживания отрицательных циклов, проведя ровно n циклов. С целью выбора алгоритма, обеспечивающего наилучшие результаты при решении данной задачи, была выполнена их сравнительная оценка (табл.). Оценка целесообразности алгоритмов для выбора оптимального пути Критерий оценки Алгоритм Дейкстры Алгоритм Флойда – Уоршелла Алгоритм Беллмана – Форда Возможность получения маршрутной информации – + – Простота программной реализации алгоритма + + + Допустимая оперативность получения результата + + – Приемлемая точность результатов + + + На основании вышеизложенного можно заключить, что условиям решения поставленной задачи больше соответствует алгоритм Флойда – Уоршелла. Именно он позволяет не только найти кратчайшее расстояние между маркерами (точками, определяющими начало маршрута и конечные элементы распространения), но и получить маршрутную информацию сразу для всех узлов сети. Определение структуры СППР для выбора кратчайшего безопасного маршрута движения При реализации второго этапа – определении структуры СППР – обосновано, что обязательными компонентами системы являются подсистема данных, подсистема моделей и подсистема программного обеспечения. Взаимосвязи и содержание блоков предложенной к реализации СППР представлены в виде концептуальной модели системы (рис. 1). Рис. 1. Концептуальная модель СППР Разработка алгоритма для решения задачи выбора кратчайшего безопасного маршрута спасения В ходе реализации алгоритма была создана база графов, отображающая пожароопасные объекты Калининградского морского торгового порта (ОАО «КМТП»). Они созданы из условий обеспечения возможности для выбора маршрута движения людей в трехмерном пространстве. Отметим, что если определённый маршрут не будет соответствовать требованиям безопасности, то исходный граф можно корректировать с учётом обязательного выполнения условий спасения людей: 1) время движения людей в горящем здании должно быть минимальным; 2) маршрут должен быть проложен вне зоны, подверженной опасному воздействию огня и теплового излучения. В основу разработки базы графов положен алгоритм Флойда – Уоршелла. Для учета воздействия факторов пожара дополнительно разработана математическая модель, корректирующая маршрут спасения с учётом прогноза развития пожара, определяемого СППР на базе сетей Sugeno и ANFIS [3]. Блок-схема соответствующего алгоритма определения оптимального пути спасения изображена на рис. 2. В нем представлены последовательность и содержание операций, необходимых для расчёта: 1. Ввод исходных данных: прогнозируемой площади пожара; номера здания; номера этажа в здании; координаты начальной точки движения и точного (прогнозируемого) места нахождения людей; границы очага горения. 2. Корректировка базы данных с учётом прогноза развития пожара, осуществляемая программой автоматически. Прогнозируемая площадь пожара определяется с помощью элементов искусственного интеллекта – гибридной сети ANFIS [3]. 2.1. Для определения границ распространения пожара выполняется сравнение его прогнозируемой площади с площадью помещения, в котором находится очаг горения: , (1) где – прогнозируемая площадь пожара, м2; – площадь помещения, в котором находится очаг горения, м2. 2.2. Если условие (1) выполняется, то данное помещение объявляется опасным для движения и соответствующая ему вершина графа удаляется из множества вершин . В этом случае процедура определения опасных для прокладки маршрута движения людей считается завершённой. 2.3. В случае невыполнения условия (1) необходимо определить все иные помещения, опасные для перемещения по ним людей. Для этого определяется разница , м2, между площадями S и s1: . 2.4. Полученная разность площадей сравнивается с площадью , м2, смежного помещения, в которое, согласно прогнозу, распространится пожар: , (2) где – количество циклов проверки. 2.5. Если условие (2) выполняется, то смежное помещение (помещения) объявляется опасным, данная вершина удаляется из множества вершин и расчет считается завершённым. 2.6. Если условие (2) не выполняется, то по формуле (3) определяется модуль разницы между данными величинами и цикл повторяется вновь: . (3) 2.7. Выходные параметры: – скорректированная база графов; – число циклов. Рис. 2. Алгоритм определения кратчайшего безопасного пути спасения людей при пожаре 3. Выполнение первого этапа алгоритма Флойда – Уоршелла – определение начальных сведений о графе: начальной матрицы расстояний и матрицы последовательности узлов для выбранного графа. Предполагается, что значение шага =1. 4. Определение возможности применения треугольного оператора алгоритма Флойда – Уоршелла ко всем элементам матрицы . Для этого рассматривается возможность выполнения неравенства , (4) где – длина (вес) ребра ; – длина (вес) ребра ; – длина (вес) ребра ; – вершины графа; – количество вершин ориентированного взвешенного графа. 5. Выполнение неравенства (4) обусловливает возможность применения треугольного оператора ко всем элементам матрицы . В таком случае создаются две матрицы для последующего их использования при определении кратчайшего пути: матрица и матрица . Матрица реализуется путём замены в матрице элемента на сумму , а матрица – путём замены в матрице элемента на . 6. Определение с использованием матриц и кратчайшего пути между узлами и после реализации шагов алгоритма. При выполнении данной операции учитываются следующие правила: расстояние между узлами и равно элементу в матрице ; промежуточные узлы пути от узла к узлу определяются из матрицы . 7. Определение всех промежуточных узлов пути от узла к узлу . Эта операция выполняется следующим образом: предполагается, что в матрице длина ребра , тогда путь ; если длина ребра и длина ребра , то считается, что весь путь определён, поскольку найдены все промежуточные узлы. 8. При невыполнении равенств и повторяется описанная выше процедура для путей от узла к узлу и от узла к узлу . 9. Вывод полученного результата – матрицы последовательности узлов определённого маршрута спасения. Реализация СППР для выбора кратчайшего безопасного пути спасения людей при пожаре Моделирование процессов принятия решения РТП (запись алгоритма решения в виде программного кода; формирование базы данных системы; проектирование пользовательского интерфейса с последующим тестированием и отладкой) выполнено в среде Matlab R2010b с использованием Graph Theory Toolbox [6]. При реализации СППР для выбора пути спасения из горящего здания на территории ОАО «КМТП» разработаны: 1) база данных о зданиях и сооружениях на территории ОАО «КМТП»; 2) m-функция для выбора пути между каждой парой вершин орграфа с минимальным общим весом дуг на основе алгоритма Флойда – Уоршолла [6]; 3) m-функция для корректировки маршрута с учётом развития пожара; 4) пользовательский интерфейс. Пользовательский интерфейс прост в обращении и не требует предварительной подготовки пользователя. Он позволяет вводить основные показатели, выводить результаты и выполнять необходимые настройки системы. Для реализации СППР рекомендуется использовать портативный персональный компьютер с необходимой вычислительной производительностью. Заранее известные сведения, такие как № здания и этаж, где произошёл пожар; координаты начала пути спасения, предполагаемые или точные места нахождения людей в здании; границы очага пожара, лучше ввести во время следования к объекту. По прибытии к месту пожара руководителю или начальнику штаба рекомендовано ввести в СППР данные, уточненные в ходе разведки. После этого запускается программа, в результате функционирования которой выводится схема оптимального пути и маршрутная информация. Проверка достоверности результатов функционирования СППР производились на выборке из 47 пожарных ситуаций. При этом было установлено, что: 1) в относительно простых случаях неверный выбор РТП пути спасения людей составляет 27 % при среднем времени принятия решения 46 с; 2) в сложных ситуациях количество ошибок РТП возрастает до 46 %, а время принятия решения – до 105 с; 3) ошибочный выбор СППР пути спасения людей составил 4,7 % при среднем времени принятия решения (с учетом временных затрат на ввод данных в систему) 40 с. В качестве примера рассмотрен случай функционирования СППР при пожаре в здании ОАО «КМТП», характеризующийся следующими условиями: - пожар возник на первом этаже административно-бытового здания, корпус № 29; - в помещении на третьем этаже блокированы люди. Выбранный СППР путь спасения людей изображен на рис. 3–5, где 45 – начало движения; 4 – место нахождения людей; 45, 41, 42, 26, 27, 11, 10, 9, 8, 4 – точки расчётного маршрута движения к блокированным людям; 4, 8, 9, 10, 11, 27, 26, 42, 41, 45 – точки маршрута спасения людей. Таким образом, разработанная СППР позволяет РТП определять маршруты движения пожарных при спасении людей с существенно большей достоверностью и за более короткий промежуток времени, визуализирует полученные результаты и обеспечивает руководителя необходимой информацией из базы данных (планы этажей, маршруты подъездов к зданию и т. п.). Рис. 3. Кратчайший безопасный путь спасения (1 этаж): – площадь пожара при t = 10 мин; – приращение площади при t = 13 мин; – приращение площади при t = 11 мин; – маршрут движения к людям Рис. 4. Кратчайший безопасный путь спасения (2 этаж): – маршрут движения к людям Рис. 5. Кратчайший безопасный путь спасения (3 этаж): – маршрут движения к людям Для зданий с относительно простой планировкой РТП может использовать разработанную систему для получения прогноза развития пожара, а для строений со сложной планировкой – как для прогнозирования динамики пожара, так и для выбора пути спасения людей. В ходе исследования осуществлена попытка сравнения разработанной СППР с аналогичными отечественными и зарубежными разработками. Однако в отечественной и зарубежной печати сведений о разработке подобных систем найдено не было. Таким образом, разработанная СППР впервые дает возможность поддержать РТП при решении такой сложной задачи в области оперативного управления. Дальнейшие направления развития системы СППР: расширение базы данных системы для предоставления пользователю полезных сведений обо всех важных объектах и коммуникациях порта, а также силах и средствах близлежащих пожарных частей города; интеграция разработанной системы с сетью Интернет. Заключение Обоснована актуальность решаемой задачи и целесообразность использования методов теории графов для выбора пути спасения людей при пожаре. Разработана математическая модель определения пути спасения людей, учитывающая динамику развития пожара и позволяющая корректировать маршрут с учётом обеспечения безопасности людей. Создана база данных для эффективного их хранения и применения в процессе функционирования системы. С использованием теории графов разработана СППР, позволяющая выбирать кратчайший и наиболее безопасный путь спасения людей при пожаре в зданиях, расположенных на территории ОАО «КМТП». Оценена достоверность результатов выбора оптимального пути спасения. В известных аналогичных отечественных и зарубежных компьютерных программах решение данной задачи не предусмотрено. Таким образом, предложенная СППР впервые позволяет РТП оперативно принимать достоверные решения, касающиеся спасения людей из горящего здания.
1. Теребнев В. В. Справочник руководителя тушения пожара. Тактические возможности пожарных подразделений / В. В. Теребнев. - М.: Пожкнига, 2004. - 256 с.
2. Мешалкин Е. А. К вопросу автоматизации информационной поддержки действий должностных лиц на пожаре / Е. А. Мешалкин, А. Г. Крылов, В. Т. Олейников, А. П. Абрамов // Материалы 11 Междунар. конф. «Системы безопасности» - СБ-2002. - М.: Академия ГПС МЧС России, 2002. - С. 11-13.
3. Кипер А. В. Разработка системы поддержки принятия решений руководителя тушения пожара на базе нечеткой нейронной сети ANFIS при пожаре на территории морского порта / А. В. Кипер., Т. С. Станкевич // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. - 2013. - № 1. - С. 38-46.
4. Березницкий В. В. Исследование и разработка алгоритма нахождения алгоритма кратчайшего пути на графе / В. В. Березницкий, Н. В. Лукьянова // Молодежный техн. вестн. - 2012. - № 3. - С. 6: http://sntbul.bmstu.ru.
5. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: МЦНМО, 2002. - 960 с.
6. Иглин С. П. Теория графов: http://iglin.exponenta.ru/gr.html.
