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

Построение маршрута движения является важной задачей при создании СОАСЗИ. Основной проблемой в поиске пути является обход препятствия. Наипростейшим подходом к решению проблемы является игнорирование препятствия до столкновения с ним.

Этот подход прост, так как он не предъявляет больших требований. Все, что необходимо знать - это относительное положение СОАСЗИ и его цели, и признак блокирования препятствием.

Рассмотрим подробнее различные алгоритмы обхода препятствий [182-186].

Перемещение в случайном направлении

Если препятствие выпуклое и небольшого размера, то СОАСЗИ может обойти его путем небольшого смещения в сторону до тех пор, пока не достигнет цели.

Рисунок 4.1 показывает, как реализовывается данный алгоритм.

162

Рисунок 4.1 - Перемещение СОАСЗИ в случайном направлении: зеленый кружок - СОАСЗИ; красный кружок - заданная цель

Проблемы при работе данного алгоритма возникают, если препятствия большие или вогнутые, как показано на рисунке 4.2. В этом случае СОАСЗИ может потерять много времени для нахождения обходного пути данного препятствия.

Рисунок 4.2 - Перемещение СОАСЗИ в случайном направлении: зеленый кружок - СОАСЗИ; красный кружок - заданная цель

Перемещение вокруг препятствия

Существуют другие алгоритмы обхода препятствий. Если препятствие большое, то необходимо следовать контуру препятствия, пока оно не будет обойдено. На рисунке 4.3 показано, как этот алгоритм работает с большими препятствиями. Проблема с данным алгоритмом состоит в принятии решения о времени прекращения трассировки.

Типичным алгоритмом работы может быть остановка трассировки при передвижении в направлении, которое является желаемым в начале трассировки.

Рисунок 4.3 - Перемещение вдоль контура препятствия: зеленый кружок -

СОАСЗИ; красный кружок - заданная цель

Надежная трассировка

Более надежный алгоритм используется в мобильных роботах: «При блокировании вычислить уравнение линии из текущей позиции к цели. Трассировать

до тех пор, пока эта линия не пересечена снова. Прервать работу, если линия попала в начальную позицию».

Этот метод гарантирует нахождение пути вокруг препятствия, если он существует (рисунок 4.4).

Рисунок 4.4 - Перемещение с использованием надежной трассировки: зеленый кружок - СОАСЗИ; красный кружок - заданная цель

Алгоритмы поиска пути на графе

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

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

Автономное выдвижение СОАСЗИ с учетом особенностей пересеченной местности целесообразно рассматривать как поисковую задачу в рамках теории

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

1 этап. Генерация полного множества решений.

2 этап. Выбор подмножества оптимальных решений по заданным критериям.

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

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

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

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

На рисунке 4.5 показан пример графа состояний, используемый данным алгоритмом.

j

Рисунок 4.5 - Граф состояний

Отсутствие информации о предпочтениях выбора текущего состояния приводит к непродуктивным шагам поиска.

На рисунке 4.6 видно, что при перемещении СОАСЗИ с использованием данного алгоритма, система может путаться и тратить время на бессмысленные пути.

Рисунок 4.6 - Перемещение с использованием алгоритма поиска пути на графе: зеленый кружок - СОАСЗИ; красный кружок - заданная цель

Алгоритм Дийкстры

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

На рисунке 4.7 показан пример использования алгоритма Дийкстры. Однако, данный алгоритм имеет недостаток игнорирования направления к цели.

Рисунок 4.7 - Перемещение с использованием алгоритма Дийкстры: зеленый кружок - СОАСЗИ; красный кружок - заданная цель

Алгоритм «лучший-первый»

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

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

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

Рисунок 4.8 - Перемещение с использованием алгоритма «Лучший-первый»: зеленый кружок - СОАСЗИ; красный кружок - заданная цель

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

Рисунок 4.9 - Перемещение с использованием алгоритма «Лучший-первый»: зеленый кружок - СОАСЗИ; красный кружок - заданная цель

Непрерывное пространство

Все приведенные выше алгоритмы движения СОАСЗИ к цели предполагают, что пространство разбито на квадратные или шестиугольные ячейки, однако существуют другие способы дискретизации пространства.

- Ячейки. Простым подходом является нанесение ячеистой сетки на поверхность пространства поиска (рисунок 4.10А).

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

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

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

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

4.10 F).

Рисунок 4.10 - Способы дискретизации пространства

4.3.