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

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

Этот алгоритм может найти применение во многих областях. Например, помочь роботу спланировать, как быстрее всего и безопаснее добраться до далекого кратера по неровной поверхности Марса. Или помочь поисково-спасательному дрону найти кратчайший путь к человеку, оказавшемуся на отдаленном склоне горы.

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

Чтобы изучить планирование движения, исследователи часто думают об окружающей среде как о графе, где последовательность «ребер» представляет собой возможные пути между начальной точкой и целью.

Вейс и ее коллеги использовали графическое представление под названием «Проблема канадского путешественника» (ПКП). Алгоритм получил свое название от разочарованных канадских автомобилистов, которые должны повернуть назад и найти новый маршрут, если дорога впереди завалена снегом.

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

«Если мы перемещаемся в окружающей среде, возможно, у нас есть некоторая информация, поэтому мы не просто идем вслепую. Хотя это не подробный план навигации, он дает нам представление о том, с чем мы работаем. Суть этой работы — попытаться отразить это на графе ПКП», — говорит соавтор работы Стадлер Курц.

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

Каждой области приписывается вероятность того, что робот сможет ее пересечь. Например, сухопутный робот с большей вероятностью сможет передвигаться по полю, чем по озеру, поэтому вероятность появления поля в его маршруте будет выше.

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

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

После тестирования алгоритма в более чем 100 смоделированных экспериментах во все более сложных средах исследователи обнаружили, что он может постоянно превосходить базовые методы, не учитывающие вероятность проходимости. Ученые протестировали алгоритм, используя спутниковую карту кампуса Массачусетского технологического института, чтобы показать, что алгоритм может быть эффективным в реальных городских условиях.

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