АЛГОРИТМ ПЛАНИРОВАНИЯ ПУТИ В ДВУХМЕРНОЙ СРЕДЕ С ПОЛИГОНАЛЬНЫМИ ПРЕПЯТСТВИЯМИ НА КЛАССЕ КУСОЧНО-ЛОМАНЫХ ТРАЕКТОРИЙ

Аннотация

Актуальной проблемой, возникающей при разработке алгоритмов автоматического
планирования пути, является рост вычислительных затрат при увеличении сложности
среды функционирования. Не лишены этого недостатка графовые методы планирования, в
частности, метод диаграмм видимости. Он позволяет сформировать в качестве узлов
графа вершины полигональных границ каждого препятствия, а ребрами графа являются
все те отрезки, соединяющие эти вершины, которые не имеют пересечений с препятст-
виями. При увеличении количества препятствий возрастает сложность такого графа,
причем этот рост очень быстрый. Поэтому наиболее важной задачей становятся приемы
сокращения сложности графа видимости. В данной статье предлагается гибридный алго-
ритм, строящийся на методе диаграмм видимости и семействе Bug-алгоритмов.
Bug-алгоритм относится к классу локальных, поскольку каждый раз имеет дело с огибани-
ем одного препятствия, появляющегося на пути следования робота, и этот алгоритм не
может предсказать заранее, какое следующее препятствие придется обходить. Предла-
гаемый в данной статье метод планирования траектории движения сочетает графовый
алгоритм с Bug-алгоритмами, что позволяет построить специальный граф с узлами в виде
характерных точек препятствий. При этом Bug-алгоритм является шагом итерационного
процесса оптимизации на графе, позволяющего за конечное число шагов прийти к опти-
мальному решению на классе кусочно-ломаных кривых. Предлагаемый метод решает зада-
чу глобального поиска пути на классе кусочно-линейных траекторий с полигональными
препятствиями; а в отличие от классического методов диаграмм прямой видимости, су-
щественно снижает размерность графа за счет специального выбора ограниченного коли-
чества характерных точек соответствующих препятствий. В статье проводится разра-
ботка и теоретическое обоснование предлагаемого метода. Приводятся расчетные соот-
ношения алгоритма, обосновывается оптимальность получаемой траектории. Аналити-
ческие соотношения подтверждаются результатами численного моделирования в различ-
ных средах, заполненных полигональными препятствиями. При этом эффективность пред-
лагаемых алгоритмов подтверждается на примерах среды, заполненной препятствиями
до 70–80%. Показано, что для прокладывания пути на сценах лабиринтного типа с одним
распространенным видом препятствий рассматриваемый алгоритм на 10% превосходит
оптимальный алгоритм Дейкстры.