Глобальное планирование маршрута мобильного робота на основе графовых методов

Рассматривается проблема глобального планирования маршрута мобильного робота между двумя заданными точками на известной территории со статическими препятствиями. Для решения проблемы по-строения маршрута на территории с большим количеством препятствий сложной формы предлагается комплексный подход на основе методов теории графов, который включает в себя применение диаграммы Вороного, графа видимости и алгоритма Дейкстры. На первом этапе исследуемая территория представляется в виде многоугольного объекта, пространство вне объекта рассматривается в качестве препятствий. Далее для обеспечения безопасного расстояния от препятствий строится внутренний буфер многоугольного объекта с помощью разности Минковского. Затем производится уплотнение вершин многоугольника, по полученным вершинам строятся полигоны Вороного. Из полигонов Вороного рассчитывается срединная ось многоугольника, к которой затем применяется алгоритм Дейкстры для расчета кратчайшего пути. Полученный путь используется для построения графа видимости, к полученному графу повторно применяется алгоритм Дейкстры. Предложенный подход позволяет построить маршрут, оптимальный с точки зрения длины и расстояния до препятствий, при этом значительно снижает вычислительную сложность построения графа видимости. Подход был реализован в свободно распространяемой геоинформационной системе QGIS для планирования маршрута мобильного робота в водной среде. Результаты эксперимента показали, что диаграмма Вороного сократила количество вершин, необходимых для построения графа видимости, в 8,3 раза, при этом граф видимости улучшил путь, полученный из диаграммы Вороного, на 8 %. Предлагаемый подход может использоваться для глобального планирования маршрутов мобильных роботов в различных средах.