Российские ученые из МФТИ и Уфимского университета разработали алгоритм навигации, который находит кратчайший путь для роботов в сто раз быстрее аналогов, а перестроение маршрута при изменении условий занимает менее 40 миллисекунд.
Предложенный метод направлен на решение задачи поиска кратчайшего и безопасного пути в условиях статического окружения с большим количеством препятствий. Традиционные алгоритмы, используемые в навигации, сталкиваются с высокими вычислительными затратами, поскольку требуют последовательной проверки множества потенциальных отрезков маршрута на пересечение с границами объектов.
Разработка основана на использовании графов видимости — структур, где вершинами являются углы препятствий, а ребрами — прямые линии между ними при условии отсутствия преград. Вместо поочередной обработки каждого возможного отрезка, авторы реализовали полную векторизацию операций пересечений. Это позволяет системе обрабатывать все потенциальные ребра графа одновременно с помощью матричных вычислений. В результате за один проход формируется логическая маска, которая мгновенно отсекает варианты, пересекающиеся с препятствиями.
Для повышения эффективности вычислений ученые применили алгоритм упрощения полигональных контуров Дугласа—Пекера. Он уменьшает количество вершин, описывающих форму препятствий, исключая незначительные изломы на прямых участках. Это позволило сократить время построения графа более чем в 200 раз, при этом форма объектов и оптимальность траектории сохраняются.
Экспериментальная проверка проводилась на картах различного масштаба. В сценариях с 10–12 препятствиями новый метод строил маршрут в среднем за 30 миллисекунд, что до 100 раз быстрее по сравнению с классическими сеточными и вероятностными планировщиками (такими как A*, RRT, PRM и другими), при этом отклонение от идеального кратчайшего пути отсутствовало. На крупных картах с сотнями препятствий время построения составляло около 4 секунд, что примерно в 5 раз быстрее аналогов. На тестовой городской карте, содержащей тысячи вершин, отклонение от оптимальной траектории не превысило 0,07%, что является существенным показателем для быстрых вероятностных алгоритмов.
Одной из главных особенностей архитектуры является возможность быстрого перепланирования. При изменении стартовой или конечной точки маршрута системе не требуется пересчитывать всю карту: новые точки интегрируются в уже существующую структуру графа, а обновленный путь находится за 34–37 миллисекунд. Это делает разработку применимой для навигации в условиях, где условия или задачи могут оперативно меняться, например, на складах, в курьерской доставке или в беспилотном транспорте.
Представленный метод уже интегрирован в среду Robot Operating System (ROS) и прошел тестирование в качестве навигационного модуля. В планах разработчиков — адаптация системы для работы в полностью динамических средах с движущимися объектами, что позволит использовать алгоритм в системах реального времени для беспилотных автомобилей и роботов-курьеров.
Читайте также: «Росатом» и Watts Battery разработают резервное питание для многоквартирных домов.