Материал: 2426

45

46

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

Задача поиска траектории при этом сводится к поиску пути на линии Вороного, обычно одномерной. Эта линия имеет малое количество точек, в которых пересекаются две, три или большее количество одномерных кривых. Перемещение по линии Вороного не является кратчайшим путем. Найденная таким образом траектория требует дальнейшей оптимизации. В то же время полученные траектории будут располагаться на максимальном расстоянии от препятствий, что в некоторых случаях является требуемым условием безопасности. Недостатки методов, основанных на использовании линии Вороного, состоят в том, что их сложно применять в многомерных пространствах. При их использовании приходится совершать слишком большие обходные маневры, если пространство характеризуется широким размахом. Кроме того, усложнено вычисление линии Вороного в пространстве, характеризующемся сложной формой препятствий [175].

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

Независимо от того, каким из трех способов описывается пространство с препятствиями, на нем возможен поиск при помощи любого из методов информированного поиска.

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

Распространенным подходом к решению задачи выбора пути является использование метода потенциалов (другие названия: «искусственных потенциальных полей» artificial potential fields, «полей виртуальных сил» virtual force field-VFF, «гистограммы векторных сил» vector field histogram-VFH) [210, 251].

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

47

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

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

Элементарные методики поиска могут использовать различные подходы. Они также могут использовать как непрерывное, так и дискретное описание пространства с препятствиями. К элементарным алгоритмам можно отнести алгоритм обхода препятствий по правилу правой (левой) руки, алгоритм «разделяй и властвуй» и др. [74, 175]. Алгоритм «разделяй и властвуй» заключается в следующей последовательности. Проводится прямая линия в пространстве между начальной и конечной точками. Берется точка посередине. Если она попадает внутрь препятствия, ее перемещают по определенному правилу (оно может быть различным) до тех пор, пока точка не выйдет из препятствия. Далее это положение точки устанавливается как конечное для первой части пути и одновременно начальное для второй части пути, и операция разбиения повторяется, т.е. используется иерархический рекурсивный подход, когда исходная задача разбивается на ряд элементарных повторяющихся подзадач. Описанный алгоритм может быть распространен на случай многомерного пространства.

Алгоритм «разделяй и властвуй» неоптимален, т.е. не гарантирует, что найденный путь будет кратчайшим, и может не работать в случае сложной формы препятствий (например, U-образных и с внутренними полостями для двухмерной карты), т.е. не является полным. Он предназначен для поиска в пространстве с простой выпуклой формой препятствий. К достоинствам следует отнести его очень низкую временную и пространственную сложность.

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

48

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

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

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

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

Классификация известных методов и алгоритмов планирования оптимальной траектории по перечисленным выше классификационным признакам приведена на рис. 1.17. Классификация способов дискретизации непрерывного пространства с препятствиями при поиске на графах приведена на рис. 1.18.

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

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

49