АЛГОРИТМ ПЛАНИРОВАНИЯ ПУТИ В ДВУХМЕРНОЙ СРЕДЕ С ПОЛИГОНАЛЬНЫМИ ПРЕПЯТСТВИЯМИ НА КЛАССЕ КУСОЧНО-ЛОМАНЫХ ТРАЕКТОРИЙ
Аннотация
Актуальной проблемой, возникающей при разработке алгоритмов автоматического планирования пути, является рост вычислительных затрат при увеличении сложности среды функционирования. Не лишены этого недостатка графовые методы планирования, в частности, метод диаграмм видимости. Он позволяет сформировать в качестве узлов графа вершины полигональных границ каждого препятствия, а ребрами графа являются все те отрезки, соединяющие эти вершины, которые не имеют пересечений с препятст- виями. При увеличении количества препятствий возрастает сложность такого графа, причем этот рост очень быстрый. Поэтому наиболее важной задачей становятся приемы сокращения сложности графа видимости. В данной статье предлагается гибридный алго- ритм, строящийся на методе диаграмм видимости и семействе Bug-алгоритмов. Bug-алгоритм относится к классу локальных, поскольку каждый раз имеет дело с огибани- ем одного препятствия, появляющегося на пути следования робота, и этот алгоритм не может предсказать заранее, какое следующее препятствие придется обходить. Предла- гаемый в данной статье метод планирования траектории движения сочетает графовый алгоритм с Bug-алгоритмами, что позволяет построить специальный граф с узлами в виде характерных точек препятствий. При этом Bug-алгоритм является шагом итерационного процесса оптимизации на графе, позволяющего за конечное число шагов прийти к опти- мальному решению на классе кусочно-ломаных кривых. Предлагаемый метод решает зада- чу глобального поиска пути на классе кусочно-линейных траекторий с полигональными препятствиями; а в отличие от классического методов диаграмм прямой видимости, су- щественно снижает размерность графа за счет специального выбора ограниченного коли- чества характерных точек соответствующих препятствий. В статье проводится разра- ботка и теоретическое обоснование предлагаемого метода. Приводятся расчетные соот- ношения алгоритма, обосновывается оптимальность получаемой траектории. Аналити- ческие соотношения подтверждаются результатами численного моделирования в различ- ных средах, заполненных полигональными препятствиями. При этом эффективность пред- лагаемых алгоритмов подтверждается на примерах среды, заполненной препятствиями до 70–80%. Показано, что для прокладывания пути на сценах лабиринтного типа с одним распространенным видом препятствий рассматриваемый алгоритм на 10% превосходит оптимальный алгоритм Дейкстры.
