Software & Systems

Начальный этап в развитии информатики в пожарной охране можно отнести к середине 70-х годов минувшего века, когда во многих странах, в первую очередь в США, расходы на содержание пожарной охраны стали стремительно падать. Общий кризис экономики привел к тому, что муниципалитеты многих крупных городов мира не могли больше выделять субсидии для пожарной охраны в таких же объемах, как и в предшествующие годы. В пожарной охране, а также и в полиции ряда стран начались кризисные явления, в том числе сокращение штатной численности, а это, в свою очередь, означает уменьшение уровня защиты населения от пожаров и преступности. Все это сопровождалось достаточно мощным забастовочным движением в пожарной охране и полиции. Но сокращение штатной численности и числа пожарных депо все равно оказалось неизбежным. Тогда было решено обратиться к ученым известного RAND-института для разрешения проблемы. В результате была поставлена задача об оптимальном размещении заданного числа сил и средств для достижения максимального уровня защиты. Одновременно аналогичные работы начались и в нашей стране, причем по качест- ву разработки и детализации проблема- тики эти работы велись на весьма высоком уровне [1].

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

Поскольку сформулированная задача имела большую практическую ценность, был предпринят ряд шагов, позволяющих прийти к решению другим (не геометрическим) путем. И первый из них – дискретизация постановки. Действительно, рассматриваемая область представляет собой множество точек города, в которых можно поместить пожарную часть. С практической точки зрения вполне допустимо заменить непрерывную область на ее достаточно плотную e-сеть, а окрестность каждой точки этой сети на дискретный набор точек сети, попадающих в эту окрестность. Формулировка задачи теперь не меняется, рассмотрению подлежат конечные множества. Разумеется, следует делать эту e-сеть достаточно мелкой, чтобы область в топологическом смысле оставалась связной (это не очень существенно для предложенного решения, но имеет очевидный прикладной смысл). Поскольку теперь рассматриваемое множество конечное, то и всего окрестностей тоже конечное число. Остается выбрать минимальное подпокрытие. Но как раз именно это делает задачу труднорешаемой [3]. Последний термин означает, что порядок количества вычислений, необходимых для получения точного решения, растет экспоненциально, а показателем экспоненты служит мощность рассматриваемого множества. По существу, в [3] показано, что ряд задач, к числу которых относится и рассматриваемая нами, решаются полным перебором. Для преодоления этой трудности был предложен второй шаг – отход от целочисленности в самой постановке задачи. Можно считать обслуживающее устройство (пожарную часть) как единичную массу, расположенную в некоторой точке области. Для сохранения надлежащего уровня пожарной защиты необходимо так расположить эти единичные массы на области, чтобы “расстояние” от каждой точки города, в которой может произойти пожар, не превышало заданного нормативного времени. Рассматривая пожарное депо как единичную массу, сосредоточенную в точке, приходим к требованию, чтобы в окрестности точки вызова находилась единичная масса. Необходимо найти минимальное число пожарных депо, удовлетворяющих сформулированному требованию. Если же допустить, чтобы порции массы, представляющие размещенные по плану города пожарные депо, не были дискретно размещены по схеме, а представляли собой непрерывно размещенную массу («размазанную» по плану города), то приходим к континуальной постановке вопроса.

Задача. Предположим, что для каждой точки x плоской компактной области G определена замкнутая окрестность Dx. Найти такое неотрицательное распределение m на G, чтобы:

а) для любой точки xÎG выполнялось неравенство:

                                                             (1)

б) величина

M =                                                                 (2)

имела наименьшее возможное значение.

Существование решения такой задачи устанавливается с помощью теории меры. Решение аналогичной задачи в дискретной постановке существует по очевидным соображениям, поскольку она представляет собой специальный случай общей задачи линейного программирования: неравенства (1) составляются для каждого узла e-сети, а подлежащий минимизации функционал (2) представляет собой просто сумму масс, сосредоточенных в узлах этой сети. К сожалению, решение дискретного варианта задачи невозможно осуществить методами, общепринятыми в линейном программировании. Для некоторых узлов сети в оптимальном решении размещенная в них масса равна нулю. Это следует из топологических соображений, если определить понятие замкнутой точки сети, и, соответственно, замыкания незамкнутой точки. Оказывается, без ущерба для решения можно переносить массу из незамкнутой точки сети в любую замкнутую точку из его замыкания. С учетом всего сказанного для решения сформулированной задачи (в дискретном варианте) были использованы градиентные методы. Было также установлено, что при измельчении e-сети решение дискретной задачи стремится к решению задачи в наиболее общей постановке.

В результате решения задачи мы получали некоторое непрерывное распределение массы, отвечающее условию (1). Однако нашей первоначальной целью было решение задачи об оптимальном размещении пожарных депо (обслуживающих устройств). Разумеется, единичная масса, соответствующая пожарному депо, не должна быть непрерывно размазана по некоторой области. С этой целью было необходимо из полученного оптимального непрерывного решения сконструировать целочисленное. При этом ясно, что минимум выражения (2) дает точную нижнюю грань количества обслуживающих устройств, размещенных на области G. Этот результат был получен впервые. Иная его формулировка – оценка для нижней грани мощности минимального покрытия компактной области в метрическом пространстве.

Для получения целочисленного решения задачи из непрерывного можно воспользоваться рядом алгоритмов, стягивающих непрерывно распределенную массу в единичные, дискретно размещенные, но тем не менее удовлетворяющие усло- вию (1). В качестве критерия, позволяющего судить о мере отклонения непрерывного распределения на конечной e-сети {xi} от целочисленного, можно использовать функционал типа энтропии: F(m) = –.

Многочисленные числовые эксперименты, проведенные с областями различного вида, показали эффективность предлагаемого подхода. Был решен ряд практических задач. В частности, разработанные схемы оптимального размещения пожарных депо были использованы для районов г. Ленинграда новой жилищной застройки. На Московском нефтеперерабатывающем заводе была решена задача об оптимальном размещении минимального числа датчиков газоанализаторов. Заметим, что в формулировке задачи область G не обязана быть плоской, трехмерной или вообще принадлежать какому-либо евклидовому пространству конечной размерности. Поэтому такая постановка применима, например, и к оптимальному размещению минимального числа обслуживающих приборов (спутников), окрестности которых охватывают без пробелов заданную трехмерную область.

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

Более интересным является другое направление. Оно пока не связано непосредственно с практическими задачами, но находится очень близко к ним. Речь идет о визуализации объектов, которые принципиально не могут принадлежать трехмерному пространству – неориентируемые поверхности (типа бутылки Кляйна), многомерные многогранники, многообразия, фрактальные множества (многие из которых появляются естественным образом при решении задач многомерной оптимизации, если решение этих задач не является единственным) и т.п. В настоящее время нет пока никаких общепризнанных разработок в этом направлении. Поэтому решение задач проектирования многомерных объектов в трехмерное пространство является интересной, многообещающей и интригующей проблемой, начальным этапом решения которой является задача визуализации четырехмерного куба.

Проблемы восприятия геометрических объектов размерности больше 3 широко известны. Они возникают при изучении курсов геометрии, линейной алгебры, дифференциальной геомет- рии и др. Рассмотрим задачу визуализации многообразий четырехмерного пространства, задаваемых в полигональной форме. В настоящее время достаточно детально разработаны методы приближения многообразий линейными примитивами, в частности n-мерными кубами, и алгоритмы их сшивания (сплайны и др.). Отсюда следует, что для визуализации четырехмерных многообразий необходимо в первую очередь решить задачу визуализации четырехмерного куба. Попытки представления четырехмерного куба на двухмерной плоскости не могут привести к успеху, так как разность между размерностью проектируемого объекта и размерностью проекции равна 2, что не позволяет использовать накопленный опыт представления на плоскости трехмерных образований, где соответствующая разность равна 1. Естественно, возникает задача построения проекции куба в трехмерное пространство. Попытки построить такие проекции наталкиваются на трудности физического описания пересечения проекций, например, трехмерных граней куба.

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

Упомянутые выше проекции четырехмерного куба в трехмерное пространство невозможно осуществить напрямую. Возможны несколько аналогов этих проекций. Так, аналогом центральной проекции можно считать следующую конструкцию: в R4 выбирается точка A (центр проекции), другая точка B и плоскость π. Через точки A, B и C объекта проводится двухмерная плоскость σ. Хорошо известно, что в общем случае пересечением двух двухмерных плоскостей π и σ в R4 является точка D, которую и будем считать проекцией точки C из центра A на плоскость π. Еще одной из причин невозможности прямого проецирования является более сложная структура группы ортогональных вращений четырехмерного пространства. Известно [4], что группа SO(4) гладко диффеоморфна прямому произведению двух других групп SO(4) ≈ S3 × SO(3). При этом первый сомножитель S3 можно рассматривать как подгруппу в SO(4) кватернионов h, по модулю равных единице. Второй сомножитель SO(3) при этом естественным образом трактуется как группа вращений касательной трехмерной гиперплоскости к S3 в точке, соответствующей выделенному кватерниону h.

Кватернионы можно трактовать как векторы размерности четыре. В дополнение тому, что они складываются по векторному закону (правило параллелограмма), кватернионы можно перемножать, так что они образуют некоммутативную алгебру с делением (точнее, алгебру, в которой для каждого ненулевого элемента существует обратный элемент относительно умножения). Аналогичными свойствами обладают векторы размерности два, соответствующие комплексным числам, и векторы размерности восемь – числа Кэли, образующие некоммутативную и неассоциативную алгебру с делением, в которой для каждого элемента существуют как правый, так и левый обратные. Доказано [5], что для векторов, размерность которых не совпадает с 2, 4 или 8, такого умножения не существует (конечномерные алгебры с делением над полем действительных чисел существуют только для указанных размерностей).

Для использования кватернионов в задачах визуализации четырехмерных объектов необходима информация о локальном строении группы S3 в окрестности единичного элемента. Эта информация позволяет правильно и исчерпывающим образом задавать малые вращения. В работе [6] показано, что любое вращение в четырехмерном пространстве можно представить в виде последовательной композиции двух вращений: умножения на некоторый кватернион, по модулю равный единице, с последующим вращением в трехмерной гиперплоскости, нормальной к выбранному кватерниону – первому сомножителю.

После этих предварительных замечаний рассмотрим алгоритм визуализации четырехмерного куба. При составлении алгоритма программы мы придерживались двух основных положений. Во-первых, для организации вращения использовался только первый сомножитель S3 группы SO(4). Это означает, что для «облета» куба в четырехмерном пространстве брались не все специальные ортогональные преобразования R4, а только те, которые реализованы умножением на кватернионы, по модулю равными единице. Во-вторых, проектирование четырехмерного куба проводилось в два этапа: сначала на специальным образом выбранную трехмерную гиперплоскость, затем аналогичным образом на двухмерную. Перейдем теперь к краткому изложению алгоритма.

Выбираем стандартный четырехмерный куб C4 Î R4 с центром D в начале координат и вершинами в точках (±1, ±1, ±1, ±1). В его состав входят: 16 нульмерных граней (вершины), 32 одномерные грани (ребра), 24 двухмерные грани, 8 трехмерных граней и, наконец, сам четырехмерный куб (как четырехмерная клетка). Какую бы точку обзора A (вне куба) в четырехмерном пространстве мы ни выбрали, основным является вопрос "какая из вершин куба C4 видна из точки A, а какая является невидимой?". Получив ответ на этот вопрос, несложно определить, какая из граней видна из точки A (если одна из вершин этой грани невидима, то и вся грань невидима). Грань является видимой, если видны все ее вершины. Критерием видимости вершины V из точки можно считать следующее высказывание: пусть E – точка на отрезке VA, отстоящая на долю a (где a находится в диапазоне от 0,001 до 0,0001) от вершины V; если точки E и D лежат по одну сторону всех 8 трехмерных граней куба, то V видна из A, в противном случае – нет. Этот критерий очевиден и не нуждается в доказательстве. Величина a выбирается из соображений нормальной работы программы. Опыт эксплуатации программы показывает, что выбор a в указанном диапазоне позволяет достаточно быстро обновлять картинку и реально отображать геометрическую ситуацию.

Изображение получается следующим образом. Вершины куба, которые видны из точки A, обозначаются на плоскости монитора маленьким черным кружком, а вершины, которые не видны, – таким же кружком с белой серединой. Далее, если некоторое ребро является видимым из точки A (иначе говоря, если обе его вершины видны), оно изображается непрерывной чертой, а если оно невидимо, – штриховкой. Для изображения перспективы используется закраска двухмерных граней. Проекции двумерных граней четырехмерного куба на двухмерную плоскость накладываются друг на друга. Поэтому, если считать, что каждая грань прозрачна и закрашена цветом небольшой интенсивности, то пересечения изображения граней обладают следующим свойством: чем больше изображений граней накладывается, тем более интенсивным является цвет их общего пересечения. В программе это делается так: находятся все пересечения изображений всех граней двухмерных граней проекции четырехмерного куба на двухмерную плоскость, причем для каждой проекции определяется индекс наложения – число граней, определяющих данную область; затем каждая область пересечения закрашивается цветом такой интенсивности, которую определяет индекс пересечения.

Приведенный механизм определяет изображение начального положения четырехмерного куба на плоскости монитора. Управление вращением куба, точнее, управление картинкой, изображающей проекцию куба на двухмерную плоскость, осуществляется с помощью группы кватернионов. В работе [6] установлено, что каждый кватернион, по модулю равный единице, может быть представлен в виде произведения трех кватернионов, каждый из которых отвечает повороту вокруг одной из мнимых осей. В соответствии с этим для управления вращением выделяются три группы кнопок на клавиатуре (каждая пара – для вращения в положительную и отрицательную сторону по соответствующей координате). Для управления вращением можно использовать джойстик.

Уже разработана также программа визуализации проволочного каркаса четырехмерного куба в цветном стереорежиме. Существенно используются только вершины и ребра (в проволочной модели грани не нужны). Для визуализации используется параллельное проектирование (с источником света, размещенном на бесконечном расстоянии) на плоскость зрения. Размеры четырехмерного куба фиксированы. Куб можно перемещать вдоль любой из осей четырехмерного пространства и вращать вокруг оси трехмерного пространства, которое связывается с кубом. Для каждой отображаемой точки (все вершины и внутренние точки ребер) задается ее расстояние от точки зрения. В зависимости от расстояния цвет точки меняется от более яркого до более тусклого (можно задать любой оттенок). Визуализация выполняется в стереорежиме на экране персонального компьютера, оснащенного средствами для управления стереоочками. Для каждого глаза изображение формируется на отдельной графической странице. Из-за необходимости постоянно переключать графические страницы программа представляет собой систему реального времени, которая работает синхронно с процессом регенерации изображения на экране дисплея. Параллельно работает процесс, который определяет момент обратного хода луча в электронно-лучевой трубке. Процесс выставляет флаг, сигнализирующий об обратном ходе луча. В этот момент переключаются графические страницы, переключаются очки и, если это необходимо, начинается генерация изображения. Частота переключения составляет 60, 72 и 80 Гц. Следующий этап исследования заключается в разработке программно-аппаратного комплекса, реализующего процесс синтеза изображений и вывода его на экраны коллективного пользования в компьютерном стереорежиме.

Очевидно, визуальное изучение топологии таких сложных образований, как проекции четырехмерных многообразий в трехмерное пространство, даже на экране 21-24-дюймовых мониторов будет затруднено именно из-за малых размеров доступного глазу изображения. Наиболее перспективным представляется генерация изображения на экранах размером не менее 1,5 м по диагонали или вывод изображения на шлем виртуальной реальности с качеством SVGA. Переход от визуализации проекции куба к визуализации проекции любого четырехмерного многообразия, построенного через его линейную аппроксимацию, приводит к проблеме выбора соответствующей вычислительной техники. Решение такой задачи потребует сверхвысокой производительности ЭВМ, больших объемов памяти, высоких скоростей обмена данными. Таким образом, речь идет о вычислительной технике суперЭВМ. Привести оценки необходимой производительности суперЭВМ в настоящее время достаточно сложно, они во многом будут зависеть от конкретно выбранного многообразия и методов его линейной аппроксимации.

В настоящее время в научной и педагогической деятельности пожарной охраны используется весьма обширный набор компьютерных средств – имитационное моделирование (на уровне построения программ, моделирующих как процессы эвакуации людей из подземных и туннельных сооружений во время пожара, так и оперативную деятельность гарнизонов), физическое компьютерное моделирование реальных процессов (ANSYS), статистические расчеты (SPSS) и многое другое. Во всей этой деятельности достаточно велико участие Центра визуализации и спутниковых информационных технологий ИМВС РАН.

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

1.   Брушлинский Н.Н., Пранов Б.М., Туркин Б.Ф. Проблема автоматизации управления пожарной безопасности / Итоги науки и техники: Пожарная охрана // Сб. научн. тр. - М.: ВИНИТИ, 1989. - № 9. - С.40-103.

2.   Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве - М.: ИЛ, 1958. - 468 с.

3.   Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи - М.: Мир, 1982. – 412 с.

4.   Хьюзмоллер Д. Расслоенные пространства - М.: Мир. – 1970.

5.   Милнор Дж., Сташеф Дж. Характеристические классы. - М.: Мир. – 1979.

6.   Еременко Г.В., Пранов Б.М., Решетников В.Н. Задача визуализации четырехмерных многообразий // Информационные технологии и вычислительные системы. - 2000. - №1. - С. 13-18.

7.   Пранов Б.М., Решетников В.Н. Визуализация геометрических образов // Тез. докл. 3 междунар. конф.: Инф. технологии и телекоммуникации в образовании. -М., 2001. - С. 73-75.