Новый алгоритм помогает роботам прокладывать путь по незнакомой местности

Итак, команда Массачусетского технологического института создала метод для эффективного планирования пути в условиях неопределённости. Алгоритм строит «дорожные карты» для малоизученных сред, балансируя между качеством маршрута и вычислительными затратами. Результат — робот или дрон может быстро найти, куда ему можно ступить, и минимизировать время в пути. Звучит как магия, но это чистая математика.

Как строится маршрут в неизвестности

Алгоритм начинает с осторожности. Он берёт за основу только те пути, которые наверняка безопасны. А уже потом, как опытный следопыт, начинает искать среди них кратчайшие варианты, осторожно добавляя новые «тропинки».

Где это пригодится? Да где угодно! Например, марсоходу, которому нужно добраться до отдалённого кратера по пересечённой местности. Или поисково-спасательному дрону, спешащему к альпинисту на горном склоне. «Нереально точно знать каждую кочку на огромной территории, — говорит соавтор работы Ясмин Вейс. — Но если у нас есть хоть какая-то информация о среде, мы можем превратить её в качественную дорожную карту».

Создание графа: математика для канадских путешественников

Для планирования пути исследователи часто представляют среду в виде графа — сети точек и связей между ними. Здесь каждая связь («ребро») — это возможный отрезок пути. Команда использовала концепцию под названием «Проблема канадского путешественника». Название говорит само за себя: представьте канадца, который едет по заснеженной дороге, натыкается на занос и вынужден искать объезд.

В этой модели каждому ребру графа присваивается два параметра: примерное время прохождения и вероятность того, что этот путь вообще проходим. Цель — минимизировать общее время до цели. Задача учёных была в том, чтобы автоматически создавать такой граф для среды с неполными данными.

«Мы не движемся вслепую, у нас всегда есть какая-то информация, пусть и неполная, — объясняет соавтор Стадлер Курц. — Эта работа как раз о том, как отразить эту информацию в графе».

Допустим, у нас есть спутниковый снимок. Алгоритм разбивает его на регионы: вот лес, вот поле, а вот что-то, похожее на водоём. Каждому региону присваивается вероятность проходимости. Для наземного робота поле — отличный вариант, а озеро — тупик. Алгоритм строит изначально консервативный, но стопроцентно проходимый граф. А потом, используя специальную метрику, решает, какие «короткие» рёбра через неопределённые зоны стоит добавить, чтобы сократить общее время.

Искусство выбирать кратчайший путь

Ключевой момент — добавление только тех кратчайших путей, которые имеют шанс быть пройденными. Это предотвращает бессмысленное усложнение графа. «Качество плана напрямую зависит от качества графа, — подчёркивает Ясмин Вейс. — Если в графе нет хороших путей, никакой алгоритм не выдаст вам гениальный маршрут».

После более чем 100 тестов в симуляциях разной сложности алгоритм стабильно превосходил базовые методы, которые игнорировали вероятность проходимости. Учёные даже проверили его на спутниковой карте кампуса MIT, доказав эффективность в условиях, приближённых к городским. Что дальше? Планируется расширить алгоритм для работы в трёх измерениях, что откроет двери для более сложных роботизированных миссий. И, конечно, исследователи хотят лучше понять, как граф, эта математическая абстракция, соотносится с реальным, непредсказуемым миром. Ведь карта — это ещё не территория, верно?