Определение оптимального пути в Евклидовом трехмерном пространстве

Размещено на http://www.allbest.ru/

Введение

В ряде приложений, имеется проблема определения оптимального пути. Это может быть нахождение самого быстрого пути в сети для определения самого безопасного пути для робота, блуждающего по поверхности Марса. В этом контексте, мы ограничим нашу область рассмотрения частным случаем нахождения путей в Евклидовом трехмерном пространстве. Даже больше, мы ограничим себя перемещениями по поверхностям, которые заданы двухмерной сеткой. Более конктерно, мы рассмотрим случай нахождения оптимального пути для транспортного средства, перемещающегося по поверхности нашей земли (1.2) как представляется в сегодняшних географических информационных (1.1) системах.

географический информационный алгоритм программирование

1. Оцифрованые карты

Представление традиционной картографической информации (например различные виды карт как на рисунке 1) на компьюторе представляет ряд возможностей и проблем.

Большой размер информации, которая представлена, требует эффективных методов хранения, при решении проблемы быстродействия для быстрого поиска и методов индексации. Это - проблема связанная с базами данных, и далее не будет рассматриваться в этой работе. Принято, что мы можем эффективно отыскать данные для части карты, представляющей интерес.

Рисунок 1 - Пример оцифрованой карты центра Стокгольма

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

Введение в оцифрованые карты и компьютерную картографию может быть найдено в [CLAR90].

2. Растровые данные

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

Рисунок 2 - Пример высот, представленных в виде растра высоты

Мы в основном заинтересованы в двух типах растровых данных:

Базирующийся, например, на спутниковых изображениях вместе с наземной проверкой правильности, возможно создать классификацию из доминирующего типа местности. Совершенно подобно традиционным картам использования земли. Данные, используемые для примеров, представленных в этой работе назначают каждый растровый пиксел к одному из 16 классов местности; например одиночный камень, вода, болота, и так далее. Данные имеют разрешение пиксела (интервал сетки) как 25 метров.

Высота земной поверхности над уровнем моря могут быть измерена при помощи воздушного радара или другим способом. Данные, используемые для примеров, представленных в этой работе имеют разрешение пиксела 50м и вертикальное разрешение 1м.

Геометрические данные, часто упоминаемые как 'векторные' данные, состоят из списков дискретных точек (координаты поверхности) и связанные с этим значения, интерпретируемые, для того чтобы определить формы линий, кривых или других геометрических объектов, которые могли бы быть полезны.

Данные, используемые для примеров, представленных в этой статье имеют три класса векторов пути - малые, средние или большие пути, определенных как цепочки многоугольников.

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

Стимул для этого проекта состоял в том, чтобы найти, в военном имитаторе, эффективный способ автономного нахождения самого быстрого пути для транспортного средства до заданного адресата. Не должно быть сложно для читателя, чтобы вообразить несколько других возможных применений 'оптимального поиска пути'. Задача, которая в этой работе рассматривается формулируется таким образом:

Заданны данные как описано в 1.1, надо найти самый быстрый путь для транспортного средства, чтобы переместиться между двумя пунктами, здесь названными как источник и адресат. Препятствий вдоль пути нужно конечно избежать. Может необязательно иметься один или большее количество 'врагов', размещенных на местности, которых также необходимо, всякий раз, когда возможно, избегать. Быстродействие транспортного средства - функция класса местности или пути выраженное от наклона. Врагов избегают, оставаясь вне их области наблюдения. Использование памяти должно быть ограничено так, чтобы было возможно выполнить алгоритм на стандартном персональном компьютере, даже с размером растра порядка миллиона пикселов на карте. Для достаточно малых карт и статических вражеских позиций, такие расчеты должны быть доступны в реальном масштабе времени.

Эта работа представлена как часть тезисов основного проекта авторов. Цель проекта - исследование, разработка, реализация, и тестирование решение для проблемы как определено в (1.2). Эта статья представляет обобщение найденных результатов, и алгоритмы, используемые во время работы.

В разделе 2 представлен короткий обзор нескольких различных подходов к решению связанных с этой задачей проблем. В разделе 3 приведен метод, который аппроксимирует проблему, сводя по существу поиск 'самого короткого пути' к проблеме с графами. Эффективность и быстродействие представления графом также обсуждена здесь же. Раздел 4 занимается проблемой поиска оптимального пути в графе. Процедура для того чтобы получить приблизительные решения при уменьшении использования памяти на очень больших графах, использующих прогрессивную схему обсуждена здесь же. Раздел 5 представляет ряд тестовых примеров. Статья заканчивается кратким заключением и идеями для будущих областей исследований.

3. Обзор методов поиска пути

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

Методы пересечения линий

Это - общий подход к проблеме, когда данные состоят из геометрических объектов, и мы имеем непрерывный тип местности. То есть все объекты - абсолютные препятствия в смысле, что через них нельзя пройти, а вся местность, не занятая объектом, рассматривается свободной, без изменения в скорости транспортного средства или других параметров. В этом случае, Евклидово расстояние самый короткий путь - также самый быстрый путь. Основная идея в следующем: сначала создайте выпуклую оболочку из всех объектов. Углы всех многоугольников оболочки определяют набор вершин. Соедините все вершины гранями. Затем сделайте некоторую более или менее разумную фильтрацию этих граней, и в заключение найдите самый короткий допустимый путь между источником и адресатом по ряду граней, используя стандартные алгоритмы графа. Основное различие между методами в этом классе алгоритмов поиска пути - как сделать фильтрацию. Цель фильтрации удаление линий, которые возможно не принадлежат самому короткому пути и поэтому резко уменьшают число путей которые необходимо исследовать. На первом шаге надо обычно удалить грани, которые (геометрически) пересекают любую другую оболочку, то есть те грани, которые прошли бы через препятствие. Затем различные правила основанные на 'норме расстояния' применяются, чтобы удалить слишком далеко идущие пути. В заключение, много алгоритмов используют некоторую эвристику, чтобы удалить дополнительные маловероятные грани, часто игнорируя требование о нахождении точных решений в каждом случае и получении взамен большого уменьшения в числе граней. Некоторые реализации методов пересечения линий могут быть найдены в [ELGR92], [MONT87] и [HOLM92].

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

Методы на взвешенном графе

Хотя они подобны методам пересечения линий используют конечный характер поиска на графе, эти методы используют радикально другой метод, и в смысле подхода к построению графа поиска. Основная идея состоит в том, чтобы разделить пространство на дискретные области, называемые ячейками, и ограничить перемещения от заданной ячейки до 'соседей'. Соседние ячейки это те, которые могут быть непосредственно достигнуты из заданной ячейки. Направленный граф создается, принимая ячейки как вершины графа и возможные перемещения к соседним ячейкам как направленные грани между вершинами. Функция веса определена назначением стоимости к каждой грани, соответствуя 'стоимости' перемещения по грани определенной при постановки задачи (время, длина, или любая функция соответствующая для проблемы). Деление пространства, определение соседей и функции стоимости граней могут отличаться между различными методами в этом классе. Один метод, основанный на этом подходе детализирован в следующих разделах, так как этот подход, также выбранный для этой статьи. Выбор деления пространства так, чтобы это совпало с растровым характером наших данных делает очень гибкой и эффективной эту модель. Некоторые примеры могут быть найдены в [STEF95], [WOOD97], [LONN96] и [PATE97].

Разные люди пробовали несколько подходов более математического характера. Например, [KIMM95] использует двумерную функцию, чтобы проследить эволюцию 'равно расположенных кривых' на поверхности, и из этого получить схему, нахождения самых коротких путей на многих поверхностях.

Другая идея состоит в том, чтобы определить некоторый сорт 'поверхности стоимости ' и следовать за локальным направлением градиента, то есть 'самого метод крутого спуска'. Однако, хотя основная идея абсолютна проста, обрабатать случай локального минимума - не так просто. Рассмотрим например реку, которая естественно течет в направлении отрицательного градиента высоты местности. В природе, это создает озера и водоемы вокруг локального минимума. Методы для обнаружения и обработки таких частных случаев могли бы возможно быть разработаны и использоваться в практическом поиске пути, но далее не описаны в этой статье.

Различные эвристические подходы также были предложены. См. например crash-and-turn алгоритм [LONN96, перевод ANIS98]. Практически эти методы сами по себе ведут себя далеко не оптимально на не очень простой местности, имеющие склоность иметь ситуации 'блокирования', и нельзя часто гарантировать, что путь будет найден вообще! Однако, эвристика может быть очень хорошей идеей для ускорения более 'исчерпывающих' методов типа тех в 2.1 и 2.2; особенно, если требование полной гарантии оптимальности может быть опущенно.

Построение графа

Проблема поставленая в (1.2) сводиться к составлению взвешенного графа. Явная функция стоимости грани разработана так, чтобы учитывать все желательные параметры. Теоретический обоснование предствалено в 3.1. Это - гибкая модель, которая может легко применяться для других проблем, где необходимо найти путь. Эффективное представление графа и подробности относительно типовой реализации затем представлены в 3.2.

Подход, принятый в этой работе должен упростить проблему, по существу в проблему поиска во взвешенном графе. Многие из основных идей, если возможно не подробнocти, были вдохновлены работой, предстваленной в [STEF95], и несколькими ранними работами. Подобные, часто более простые версии методик были использованы программистами компьютерных игр как метод для того чтобы перемещать модули в намного меньших картах, используются в различных стратегиях и других компьютерных играх. См. например [WOOD97]. Для введения в графы и их теорию, см. [BUCK90], [CORM90] или любой другой хороший учебник по теории графов.

Первый шаг в нашем упрощении ограничение числа возможных размещений и числа возможных перемещений между этими размещениями.

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

Как найти минимальный размер этой области, которую надо определить без априорного знания относительно фактического оптимального пути? Если не имеется никаких непроходимых препятствий, 'стоимость' пути по 'прямой линии' между источником и адресатом могла бы возможно использоваться как верхняя граница 'стоимости' путей, которые мы должны рассмотреть. Эта 'наибольшая стоимость' могла бы затем использоваться, как способ, чтобы ограничить область поиска. Однако, это - намного проще сказать, чем сделать, особенно при практической реализации. Кроме того, этот способ будет однако терпеть неудачу, если имеются непроходимые области заранее неизвестной протяженности (например, длинная река, пересекающая вектор движения между источником и адресатом).

При таком подходе может даже оказаться, что не имеется никакого возможного пути, но это неизвестно, пока мы фактически не пробовали, и не сумели найти этот путь. Таким образом, необходимо прибегнуть к использованию некоторой эвристики, чтобы определить подходящий размер области. Это знание применительно к заданому приложению будет очень полезно иметь. Например, протяженность самого большого препятствия, которое мы ожидаем, которое мы будем хотеть обойти вокруг, могла бы быть хорошой исходной точкой для руководства к действию. Плюс расстояние между источником и адресатом. Практические тесты показали, что в небольших областях, первое из этих двух рассмотреных расстояний является намного более важным, в то время как при больших масштабах второе доминирует. Простая эвристика для компромисса может быть создана как b=a+(1+c)*d. Где b - длина диагонали ограничивающего прямоугольника ( от источника и до адресата), d - расстояние между источником и адресатом, c - константа масштабирования ( в большинстве случаев c=1/3, кажется, работает хорошо). В заключение, a - приблизительный размер самого большого препятствия.

В некоторых приложениях, можно взамен дать возможность конечному пользователю, вручную определить область поиска и таким образом уходить от проблемы полностью (насколько мы заинтересованы). И последние замечание, всегда возможно увеличить область поиска и повторить поиск пути в случае, если мы не преуспели в нахождение пути в выбранной области поиска.

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

Рисунок 3 - Регулярная квадратная плоская сетка

Рисунок 4 - Регулярная гексоганальная плоская сетка

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

Как упомянуто в 3.1 мы сведем нашу проблему к задаче взвешенного графа. Теперь мы определим вершины графа, как 'центральные точки' ячеек.

Следующий шаг должен ограничить число возможных перемещений из данной ячейки. Если возможно идти от одной вершины до другой без того, чтобы пройти через другую точку вершины, мы будем говорить, что они соединены (направленной) гранью. Вершина, из которой грань идет, называется источником. Вершина на другом конец называется адресатом. Тривиально, всегда имеется грань от заданной ячейки до самой себя; мы будем пренебрегать этим случаем в дальнейшем как пребывание в одной точке - не очень полезный сегмент 'оптимального пути'. Ячейки или вершины, которые являются адресатами всех граней данной ячейки, называются соседями. Какие ячейки рассматривать как соседей данной ячейки, надо решить. Идеально, все ячейки должны быть соседями всех других ячеек (так называемый 'полный' граф). Однако, это означало бы наличие невероятного числа граней. Поскольку для каждой ячейки требовалось бы, определить так много граней сколько имеется других ячеек, мы например получили бы 10¹²/2 граней для графа с одним миллионом ячеек. Мы будем позже использовать оптимизированые алгоритмы на графе, их практическое быстродействие очень сильно зависит от числа граней, так что ясно что это недопустимо. Взамен мы будем идти к другому экстремальному случаю и будем только определять 'физически' смежные ячейки такие как соседи данной ячейки. В случае нашей квадратной сетки, каждая ячейка (которая не размещена на границе области поиска) имеет раскладку как отмечено на рисунке 5. Можно выбрать или четыре или восемь смежных ячеек как соседей. Так как мы хотим максимальную точность, и выбор восьми лучше чем четырех и не будет представлять большой сложности; мы выберем восемь ячеек в качестве соседей, показанных нормально-серым на рисунке 5. Мы позже увидим, что это позволит нам использовать высоко эффективное представление графа. Мы будем добиваться точности при меньшей сложности и лучшего быстродействия. Однако, это очень благоприятно, см. далее 3.1.2.6 и 6.2.2. Число граней теперь линейно зависит от числа вершины (8*n ).

Рисунок 5 - ячейка с гранями к восеми соседям

Резюме: мы ограничили число перемещений от каждой вершины до восьми граней (или меньшего количества) и закончили определение представления направленного графа в пространстве.

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

Суть этих 'аппроксимаций длины грани' то, что мы теперь только должны проверить, имеем ли мы осевую или диагональную грань, чтобы определить (приблизительную) длину. Если кроме того ячейки квадратные, только две длины возможны, для осевых и диагональных граней соответственно, см. рисунок 5. В компьютерной реализации, мы можем затем легко предварительно вычислить две константы для каждого выражения, включая длину грани и поместить их в соответствующие таблицы.

Теперь, когда мы создали модель направленного графа для перемещения через пространство, пришло время для моделирования 'стоимости' перемещения сквозь пространство. На стоимость может влиять много различных вещей в зависимости от того, хотим ли мы найти самый короткий путь; самый быстрый путь, или путь с наименьшим риском быть обнаруженным врагами, и так далее. Мы будем решать задачу поиска самых быстрых и наименее опасных путей. Адаптации под другие варианты должны быть очевидны.

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

Чтобы сделать это, значение 'стоимости' назначено на каждую грань. Эти значения могут быть получены через функцию определенную на множестве всех граней, и термин 'функция стоимости ' используется. Путь - это множество 'связанных' граней, между вершинами источника и адресата. Стоимость пути - сумма издержек всех граней в пути. Допустимый путь - путь с определенной суммой стоимости.

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

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

Но как можем мы смоделировать воздействие всех различных параметров, которые мы хотим учесть во время перемещения по грани от одной вершины до другой? И как можем мы смоделировать такие ограничения как враги, препятствия и другие факторы, которые не могут быть явно выражены как время нахождения в пути? 'Основная стоимость грани' основанная на типе местности будет задана, и различные 'модификаторы' будут затем использоваться, чтобы все 'ограничения' принять во внимание. Модификатор определен как функция, которая некоторым способом изменяет основную стоимость грани.

После определения функции стоимости и различных модификаторов, мы завершим упрощение задачи на взвешенном графе. Затем остается 'только' фактически найти оптимальный путь в разделе 4.

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

Рисунок 6 - скорость транспортного средства постоянна внутри каждой ячейки (Пустое поле, лес, вода)

Основная стоимость грани таким образом очень просто вычисляется: cost_edge = (l_e/2)(1/v₁+1/v₂) где v1, v2 0 иначе равны . l_e - длина грани как обсуждалось в 3.1.1.3. v₁ и v₂ - скорости (длина деленная на время), с которыми транспортное средство перемещается через соответственные типы местности. Частный случай тот, если или v₁ или v₂ равны 0, тогда стоимость установлена в , таким образом исключаются любые пути, ведущие через непроходимую местность, например вода для земного транспортного средства (не амфибии).

Перемещение по дорогам вообще значительно быстрее, чем через окружающую их местность. Мы используем модификатор, чтобы изменить издержки для граней между ячейками, которые соединены дорогой более низкой стоимости. Новая стоимость вычислена так же как и основная стоимость грани. Надежней принять, что тип дороги тот же самый и в источнике и в адресате так, чтобы ecost_mod = l_e/v, где v - скорость, с которой мы можем двигаться по заданному типу дороги.

Как мы определим, соединяет ли дорога две ячейки? Ясно, что векторный характер данных представления дороги противоречит нашему способу представления графа, которым были представлены данные местности. Давайте начнем с 'растрезации' данных вектора дороги, то есть трансляции дороги в растровый формат, соответствующий сетке ячеек. Мы будем хранить один растр пути в 'пикселе', соответствующем каждой ячейке. Растеризация может быть выполнена разными способами (например см. [CLAR90] или [FOLE90]). В основном имеются два преобладающих способа: доминирующий пиксел (тонкая линия) растеризации, или пересеченный пиксел (толстая линия) растеризации. Различие и общие принципы должны быть ясны из рисунка 7 и 8 соответственно. Черные линии представляют вектор дороги на рисунках, квадраты представляют растровые пикселы, и серые пикселы - растрезацию дороги. Действительно важная вещь здесь это то, что связность сохраняется, то есть не должно быть никаких 'промежутков' при растрезации дороги.

Рисунок 7 - Доминирующий пиксел растра - тонкие линии



Рисунок 8 - Пересеченный пиксел растра - толстые линии

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

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

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

Препятствия здесь интерпретируются как непроходимые области. Они могут появляться или в форме растровых данных (например, озера) или векторных данных (например, реки). Более широкая интерпретация препятствия позволяет вводить не только 'абсолютные' препятствия, но также и препятствия простого сорта задержки.

Вместо того, чтобы проверять и стоимость перемещения и препятствие, мы просто назначим стоимость на прохождение граней через (абсолютное) препятствие. Позже, в алгоритме поиска (см. раздел 4) будет возможно добавить небольшую проверку для того чтобы непосредственно отбросить любые 'предложенные' пути, которые содержали бы грань со стоимостью .

Растровые данные базирующиеся на препятствиях обработаны очень легко: если препятствие - некоторый тип местности (например, густой лес), то мы только устанавливаем скорость перемещения транспортного средства в равной нулю для этого типа местности. Если мы имеем другие растровые данные с препятствиями (то есть те которые не закодированны в растре местности), то мы можем представлять специальный класс 'препятствия' типа местности с нулевой скоростью транспортного средства, и отображать все эти препятствия в нормальный класс растра местности. Отображение может быть обработано при помощи замены первоначального типа местности - так как тот пиксел 'препятствие', мы никогда не достигнем его и таким образом не имеем никакой потребности в истинном типе местности. Векторно основаные препятствия (например, маленькие реки или заграждающие метки) могут быть аналогично обработаны растрезацией их к растру местности использование того же самого типа местности 'препятствия'. В отличие от растеризации векторов дороги, мы теперь хотим использовать процесс растеризации с толстой линией, так как вариант с тонкой линией вызывает 'промежутки', которые позволили бы путям проходить через препятствие, см. рисунок 9.

Рисунок 9 - Тонкие линии позволяют граням, которые проходят через препятствие

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

Мы можем использовать модификатор, чтобы избежать прохода через вражескую территорию, то есть области, где мы можем быть обнаружены и/или настигнуты врагами. Фиксированная стоимость 'штрафа' добавлена ко всем граням, чей адресат находится на вражеской территории. Таким образом, если мы хотим полностью избегать обнаружения врагами, мы должны добавить . Точно, какой критерий используется, чтобы 'активизировать' модификатор, зависит от типа врага. Этот простой модификатор 'предотвращения' достаточен для наших целей. Возможно более правильная модель взамен добавила бы штраф при перемещении и в ячейку и из ячейки (подобно основной стоимости местности). Эта стоимость могла бы быть пропорциональной времени, пересечения грани (то есть пропорциональный основной стоимости местности плюс модификатор дороги).

Временные изменения игнорируются здесь, то есть враги рассматриваются статическими в течение определения пути. Для обсуждения того, как метод мог бы быть расширен для того чтобы управлять динамическими сценариями, смотри 6.2.1.

В реализации теста, видимость использовалась как критерий того, что транспортное средство обнаружено врагом. Чтобы определить, наблюдается ли врагом транспортное средство используется простая форма трассировки лучей (см. [CLAR90] pp. 228), чтобы проследить 'линию прицела' между наблюдателями (врагами) и объектом (транспортным средством). Рисуйте луч от транспортного средства до каждого наблюдателя и проверьте, если лучи пересекаются местностью. Для этого, мы используем данные растра высоты, чтобы определить наземную высоту. К наземной высоте добавлена специфические 'видимые высоты' различных типов местности (например вода = 0m, редкий лес = 6m, и другие).

Каковы ошибки, свойственные нашему представлению? Позвольте нам рассмотреть различные возможные источники ошибок:

Ошибка Растеризации: Какая ошибка действительно представлена в растровом формате? Это - не тривиальный вопрос. Например, рассмотрите случай с очень длинным и тонким, но очень легко проходимым 'зигзагообразным' путем (как в реальности) как показано на рисунке 10.

Рисунок 10 - Зигзагообразный путь между двумя вершинами

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

Ошибки в данных: различные входные данные могут иметь неустранимые погрешности. Это должно быть обработано вне нашей модели, и мы примем, что все наши входные данные будут точными. Однако, мы можем обратить внимание, что полученный путь - конечная сумма издержек граней. Если функция стоимости грани - кусочная линейная функция входных данных (то есть она позволяет только ограниченные 'переходы') то она тоже дает ошибку.

Ошибка дискретизации ячейки: Какова величина ошибки вытекающая из ограничения перемещения по пути между ячейками только через вершины? Давайте рассмотрим частный случай однородной стоимости перемещения. Начальная и конечная точка должны каждая относиться к ячейке. Перемещение по 'позициям' ограничено вершинами в центрах ячейки, см. рисунок 11. Следовательно, мы имеем абсолютный верхний предел для ошибки как максимум расстояний между всеми возможными позициями внутри ячейки и центр. Ясно, что это половина длины диагонали. Следовательно, предел в ошибки дискретизации ячейки - длина диагонали одной ячейки. Для более сложного случая с переменной стоимостью перемещения, мы можем умножать на самую высокую стоимость перемещения вдоль граней пути для опытной (а-постеори) верхней границы. Мы затем должны знать оптимальный путь, чтобы найти самую высокую стоимость по нему. Мы могли бы использовать самую высокую стоимость на всем графе взамен для априорной оценки, но если мы имеем препятствия, то она - , которая не делает очень полезной оценки.

Истинный и ограничивающий путь

Рисунок 11 - ошибка дискретизации ячейки ограниченна диагональной длиной

Ошибка ограничения грани: Какая величина ошибки получается, когда мы ограничиваем перемещение между ячейками только к соседним ячейкам? Снова при рассмотрении однородного случая стоимости перемещения получаемая ошибка иллюстрируется рисунком 12

Рисунок 12 - ошибка ограничения грани в однородной местности

В самом плохом случае - очевидно, когда общая длина диагональных граней равняется общей длине осевых граней. Поскольку соотношение между длиной диагонали и осевой грани - 2, то есть иррациональное число, то самый плохой случай может происходит в 'пределе' бесконечно длинного пути. Если истинный путь имеет длину l_t, и наш ограниченный путь имеет длину l_r, мы получаем из простой геометрии:



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

Ошибки функции стоимости: модель реального мира базируется на ряде попыток определения величины различных свойств мира. Неправильная модель порождает ошибки. Попытки точно измерить эти ошибки очень трудны из-за запутанного характера мира. Здесь не сделано никаких попыток, так как это очень зависит от множества 'нюансов'. Подобно детальной спецификаций транспортных средств, классификации типов местности, и так далее и тому подобное. Возможно единственый действительно удовлетворительный способ измерения этих ошибок, фактически выполнить тесты и сравнить их с вычисленными результатами.

В заключение, отметим, что трудно говорить о абсолютном пределе погрешности (особенно априорной границы). С другой стороны мы имеем причины верить, что сделанные аппроксимации обладают малыми 'усреднеными' ошибками. Так как аппроксимации, носят по большей части 'усредненный' характер, то устойчивость также стабильна.

4. Эффективное представление графа

Давайте рассмотрим традиционное 'обобщенное' представление графа. Каждая ячейка имеет восемь направленных граней идущих от нее к восьми соседним ячейкам. Для каждой грани мы нуждались бы по крайней мере в 4 байтах, чтобы явно сохранить стоимость грани и по крайней мере 2 байта, чтобы сохранить индекс к ячейке адресата. Из этого следует что надо минимум 48 байт на ячейку. Мы хотим применить наш алгоритм на картах с количеством ячеек порядка миллиона. Это потребует по крайней мере 48Мбайт только для сохранения графа. Под это уйдет вся память, необходимая для фактического пути, найденного алгоритмом, не говоря уже о памяти для приложении для этой работы, являющегося частью намного большей программы. Ясно, что традиционное обобщенное представление графа просто требует в десять раз больше памяти, чем возможно для нашего алгоритма, выполняющегося на стандартном PC сегодня. Только для построения такого (относительно) огромного графа будет тратиться значительное вычислительное время. Конечно, в с течением лет, память и компьютерная технология, доступная сейчас на стандартном PC, очень вероятно, будем прогрессировать. Однако, мы не имеем роскоши, чтобы ждать, когда этот день придет, мы будем способны решать даже более большие проблемы, если мы сможем найти способ делать это практически сегодня! Таким образом, я здесь буду представлять способ неявного представления специального графа, необходимого для нашей проблемы при затратах 3 байта на ячейку.

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

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

Все ячейки/вершины теперь имеют точно ту же самую структуру, если обеспечено, что никогда не совершается 'переход' по грани с бесконечной стоимостью грани. Мы знаем то, какие грани имеются, без необходимости явно кодировать это для каждой ячейки (см. рисунок 5). Ячейки сами по себе не представляют никакого интереса; они представлены только стоимостью грани, о которой мы заботимся при определении общей стоимости пути. Однако, мы видели в предыдущих разделах, что все модификаторы стоимости грани - функции свойств грани ячеек источника и адресата. Давайте называть эти свойства для ячейки 'атрибутами', сохранять их в структуре CellAttr и определим массив, где мы сохраняем все атрибуты ячейки, по одному атрибуту для каждой вершины ячейки.

На каждую ячейку ссылаются двумерным индексом, CellRef, в этом массиве. Все, что необходимо знать для того чтобы пройти по грани от любой ячейки до другой - то, как этот как (двумерный) индекс должен быть изменен. Давайте определим номер грани по направлению по часовой стрелке от 0 до 7 (0 - Север, 1 - Северо-Восток, 2 - Восток, 3 - Юго-Восток, и так далее). Затем просто вычислим изменение индекса и сохраним это в справочной таблице, crWalkEdgeDelta[8]. Для прохода по грани, с направлением ed, все, что мы должны cделать затем 'добавлять' crWalkEdgeDelta[ed] к CellRef исходной ячейки.

Мы не будем явно хранить стоимости всех граней, мы будем выражать их как функцию атрибутов источника и адресата грани ячейки. Мы используем эту функцию, чтобы вычислить любую стоимость грани когда необходимо. В разделе 4 мы увидем, что мы фактически только нуждаемся в вычислении стоимости некоторой грани один раз, так что никакая двойная работа не будет выполняться по сравнению с превычислением всех стоимостей граней. Лучше еще если, очень большой процент стоимостей граней никогда не будет обычно вычисляться вообще. Если все атрибуты для вершины могут быть сохранены в приблизительно том же самом объеме памяти как стоимость грани, тогда много памяти может быть сохранено при помощи сохранения атрибутов вместо явных стоимостей грани. Это так поскольку число вершин только одна восьмая часть числа граней.

32 битное целое число без знака должно быть достаточно, чтобы сохранить любой путь и стоимость грани в формате с фиксированной запятой. Специальное значение, бесконечность, используется, чтобы представить . Оно равно половине максимального значения типа данных так, чтобы ее можно было безопасно добавлять к любому значению стоимости без любого риска переполнения и так, чтобы мы могли фиксировать бесконечность снова. Это соответствует алгебраической операции +x = x{}

Основная стоимость местности легко находиться при использовании заранее вычисленной справочной таблицы как: dwCost = TerrainLut[ed & 1][t₁] + TerrainLut[ed & 1][t₂]. TerrainLut[i & 1][j] определяет стоимость для пересечения половины грани в направлении i по местности типа j. Так как направления граней были пронумерованы по часовой стрелке от 0 до 7, мы имеем ed & 1 равным 0 для осевых граней и 1 для диагональных граней. В реализации теста имеются 16 классов местности, так что мы нуждаемся в 4 битах для того чтобы сохранить их как атрибут, cTerrainType, для каждой вершины.

Желательно вычислить растеризацию всех путей только один раз и единый растр дорог используется, для представления всех дорог на карте. Мы будем сохранять пикселы дороги как атрибут, cRoadType, для каждой вершины и пусть этот аттрибут, содержит значение или 'класс' дороги или специальное значение noroad (нет дороги). В реализации теста, имеются только три класса дороги: узкая, средняя или широкая, поэтому только 2 бита необходимы, чтобы сохранить эту информацию. Возьмем грань, если источник и адресат оба имеют пикселы растра дороги, отличающиеся от значения noroad, то принимается, что имеется дорога, соединяющая их. Это вызывает проблему, если имеются пути, которые являются настолько близкими друг к другу, что их растрезационное представление 'смешивается'. При размере 25 м пикселов/ячеекпроблемы не будет. Даже если это происходит (например, в городских узлах транспортного движения), очень вероятно, что имеются фактическое соединения между дорогами, поэтому воздействие нахождения оптимального пути было бы незначительно. Однако, чтобы уменьшить вероятное воздействие таких путаниц, растеризация 'тонкой строкой' предпочтительна (см. рисунок 7). Для алгоритма растеризации выбран классический алгоритм Брезенхама для рисования строки (см. [FOLE90] ). Это хороший быстрый алгоритм, использует только целочисленные операции, и получается в результате доминирующий пиксел (тонкая строка).

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

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

Мы хотим провести линию видимости между транспортным средством и каждой вершиной, где находится враг, чтобы решить обнаружил нас враг или нет. Чтобы избежать эффекта откровенной 'дискретизации' ('зазубренности'), будем нуждаться в суб-пиксельном точном алгоритме трассировки лучей. Таким образом, трехмерная версия алгоритма Брезенхама рисования линии не используется для растрезации векторов дороги. С фиксированной точкой (DDA) алгоритм рисования линии взамен используется. Он очень прост; позиция в трехмерном пространстве сохраняется как число с фиксированной запятой и используется другая фиксированная точка трехмерный 'инкрементор' (шаг увеличения) для того чтобы пройти маленькими шагами по линии. На каждом шаге, выполняется проверка на видимость, выше мы или ниже видимого уровня местности в этой точке. Уровень местности вычисляется, используя билинейную интерполяцию из четырех соседних высот и пикселов растра местности как иллюстрируется на рисунке 13. Для лучшей точности, длина шага должна быть выбрана такой же как, или меньше, чем размер пиксела.

Рисунок 13 - Пример билинейной интерполяции поверхности на сетке 4x4-вершины

Это вычисление может быть отнимает большего всего времени в этом алгоритме. Следовательно, мы не хотим делать это, если это не абсолютно необходимо. Таким образом, мы не делаем вычисление пока необходимо и используем флаг атрибута, bHaveVisCalc, для того чтобы проверить, вычислили ли мы предварительно это для данной вершины. Если нет, то мы вычисляем это и сохраняем результат в другом атрибуте флага, bVisible. Эта 'ленивая' оценка может быть отмечена, как форма запоминания см. [CORM90] стр.312.

Наземная высота сохраняется в другом атрибуте, wHeight. 16 битное значение должно быть достаточно для нашей планеты (гора Эверест на 8848 м выше уровня моря). К наземной высоте добавлены специфические 'визуальные' высоты в зависимости от типа местности (выполненные через таблицу, конечно). Тип местности был уже сохранен в cTerrainType атрибуте.

Просмотрите снова разделы 3.2.2 и отметьте все используемые атрибуты, мы придумали следующий набор атрибутов вершины для реализации теста:

typedef struct {

BYTE cTerrainType: 4;// Класс местности, 4 бита

BYTE cRoadType: 2;// Класс дороги, вкл. нет-дороги, 2 бита

BYTE bVisible: 1;// Видимость, 1 бит

BYTE bHaveVisCalc: 1;// Вычеслена ли bVisible?, 1 бит

SWORD wHeight;// Высота над уровнем моря, 16 бит

} CellAttr;

В целом, мы имеем три байта на ячейку. Если детектирование врага и наклона, не нужно, мы могли бы пропустить атрибут высоты и суметь обойтись одним байтом на вершину! Если мы нуждались в большем количестве классов местности и/или классов дороги, дополнительный байт мог бы быть необходим.

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

DWORD SearchGraph::EdgeCost(

// Вычисление функции стоимости

CellRef &crDst, // Выход: ячейка адресат для грани

CellRef crSrc, // Вход: ячейка источник

EdgeDir ed// Вход: направление грани

)

{

// Переход по индексу на ячейку адресат

crDst = crSrc + crWalkEdgeDelta[ed];// 2d индекс + опреатор

// Модификатор для определения края карты, возвращает бесконечность

// если адресат вне графа

if (IsCellRefValid(crDst)) return infinity;

CellAttr&caSrc = AttributesFor(crSrc);

CellAttr&caDst = AttributesFor(crDst);

DWORDdwCost;

// Применение модификатора дороги

if ((caSrc.cRoadType != noroad) && (caDst.cRoadType != noroad)) {

dwCost = dwRoadEdgeCost[ed&1][caSrc.cRoadType];

} else {

// иначе применение модификатора наклона

if (abs(caSrc.wHeight-caDst.wHeight)

> dwMaxHeightDiff[ed&1])

return infinity;

// иначе вычисление просто стоимости местности

dwCost = dwTerrainHalfEdgeCost[ed&1][caSrc.cTerrainType] +

 dwTerrainHalfEdgeCost[ed&1][caDst.cTerrainType]; 

}

// Применение модификатора врага

if (!caDst.bHaveVisCalc) { // ленивое определение видимости

// Использование DDA трассировки алг.

caDst.bVisible = IsObserved(crDst);

caDst.bHaveVisCalc = true;

}

if (caDst.bVisible) {

dwCost += dwVisibilityCost;

if (dwCost > MAXCOST) dwCost = MAXCOST;

}

// Все

return dwCost;

}

Правила if else данного кода, исполняемые при вызове EdgeCost(), очень короткие. Реальное замедление быстродействия происходит при вызове IsObserved(), то есть определение, может ли враг обнаружить нас в ячейке адресата или нет. Таким образом, если вражеское детектирование не нужно, мы можем сохранить много времени при вычислении.

...