Роботов научили искать путь в сто раз быстрее

Учёные МФТИ и Уфимского университета придумали, как ускорить поиск маршрута для роботов, причём не за счёт более мощных компьютеров, а за счёт новой математики. Обычно алгоритмы проверяют возможные пути один за другим: берут отрезок, смотрят, не упирается ли он в препятствие, потом берут следующий. Новый метод делает это иначе: он проверяет сразу все возможные отрезки одновременно, с помощью так называемого графа видимости, где точки это углы препятствий, а линии между ними показывают, что путь свободен. За один проход компьютер считает, какие отрезки «видят» друг друга, и сразу исключает те, что пересекают препятствия.

Учёные также научили алгоритм упрощать контуры препятствий, убирая лишние точки на почти прямых стенах. Это ускорило построение карты маршрутов больше чем в 200 раз. В итоге на картах с десятком препятствий путь строится за 30 миллисекунд, в 100 раз быстрее, чем у конкурентов, и при этом точнее. А если стартовая или конечная точка меняется, пересчитывать всю карту не нужно: обновление занимает те же десятки миллисекунд. Работа уже опубликована в научном журнале и встроена в популярную программную платформу для роботов ROS, то есть ей можно пользоваться уже сейчас.

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

Подписывайтесь на канал MT-GROUP, чтобы узнавать больше новостей из быстроразвивающегося мира робототехники!

Подписаться на канал
Подписаться в MAX