Робот учится достигать цели, передвигаясь по малоисследованной среде

Исследователи Массачусетского технологического института разработали метод, который эффективно определяет наилучшие маршруты к месту назначения при движение по малоизученной среде. Ученые создали алгоритм построения дорожных карт в такой среде, который находит компромисс между качеством дорожной карта и эффективностью вычислений. Это позволяет роботу быстро находить проходимый маршрут и минимизировать время в пути. Роботы научились ориентироваться в неизвестном пространстве Этот робот заблудился, потому не знал алгоритма, разработанного МТИ. DALLE-3 Главное преимущество нового алгоритма в том, что он может использовать любую информацию об окружающей среде для построения оптимального пути: плохой спутниковый снимок, рассказы местных жителей и т.д. Алгоритм аккуратно учтет всю имеющуюся информацию и построит кратчайший проходимый маршрут.

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

Построение маршрута

Робот перемещается с одного берега озера на другой. Если мост, скорее всего, проходимый, в дорожную карту следует включить розовый путь, чтобы робот мог проверить проходимость моста, а также два фиолетовых пути, чтобы робот мог пройти через мост, если он проходимый, и обойти озеро, если перейти мост нельзя. Если мост, скорее всего, не проходим, включение этих путей в дорожную карту только увеличивает сложность планирования без существенного улучшения его эффективности. Граф, содержащий только синий путь, все равно приведет к планам с ожидаемыми близкими к оптимальным затратами. Поскольку известно, что и зеленый, и синий пути проходимы, включение более длинного зеленого пути в дорожную карту не имеет смысла. Робот перемещается с одного берега озера на другой. Если мост, скорее всего, проходимый, в дорожную карту следует включить розовый путь, чтобы робот мог проверить проходимость моста, а также два фиолетовых пути, чтобы робот мог пройти через мост, если он проходимый, и обойти озеро, если перейти мост нельзя. Если мост, скорее всего, не проходим, включение этих путей в дорожную карту только увеличивает сложность планирования без существенного улучшения его эффективности. Граф, содержащий только синий путь, все равно приведет к планам с ожидаемыми близкими к оптимальным затратами. Поскольку известно, что и зеленый, и синий пути проходимы, включение более длинного зеленого пути в дорожную карту не имеет смысла.https://groups.csail.mit.edu/rrg/papers/veys_icra_24.pdf

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

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

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

Создание дорожного графа

Пример случайно сгенерированной среды. Область в центре проходима, поэтому кратчайший путь от начала до цели — прямая линия (синий). Но робот этого еще не знает. По мере увеличения масштаба (к — бесконечно для пути который наверняка проходим, но возможно неоптимален). Потом в граф добавляется все больше кратчайших путей, и длина предсказанного пути (красный) приближается к оптимальной. Пример случайно сгенерированной среды. Область в центре проходима, поэтому кратчайший путь от начала до цели — прямая линия (синий). Но робот этого еще не знает. По мере увеличения масштаба (к — бесконечно для пути который наверняка проходим, но возможно неоптимален). Потом в граф добавляется все больше кратчайших путей, и длина предсказанного пути (красный) приближается к оптимальной.https://groups.csail.mit.edu/rrg/papers/veys_icra_24.pdf

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

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

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

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

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

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

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

Выбор кратчайшего пути

(a) Спутниковый снимок кампуса MIT, полученный из Google Earth. (b) Многоугольники районов полученные из OpenStreetMap. (c) Онлайн-путь, по которому движется робот, пересекая кампус (синий). Робот выбирает более короткий путь через открытый проход, обведенный зеленым, чтобы не обходить все здания, а затем проверяет проходимость прохода, обведенного красным, и выбирает кратчайший путь по свободному пространству от прохода до цели. (d) Три прохода обеспечивают потенциальные кратчайшие пути через здания. Первый и третий — непроходимы, а второй — проходимый. Когда робот замечает непроходимый проход, он выбирает кратчайший путь к следующему местоположению, используя свободное пространство и ребра восстановления. (a) Спутниковый снимок кампуса MIT, полученный из Google Earth. (b) Многоугольники районов полученные из OpenStreetMap. (c) Онлайн-путь, по которому движется робот, пересекая кампус (синий). Робот выбирает более короткий путь через открытый проход, обведенный зеленым, чтобы не обходить все здания, а затем проверяет проходимость прохода, обведенного красным, и выбирает кратчайший путь по свободному пространству от прохода до цели. (d) Три прохода обеспечивают потенциальные кратчайшие пути через здания. Первый и третий — непроходимы, а второй — проходимый. Когда робот замечает непроходимый проход, он выбирает кратчайший путь к следующему местоположению, используя свободное пространство и ребра восстановления.https://groups.csail.mit.edu/rrg/papers/veys_icra_24.pdf

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

Навигация роботов widget-interest

DeepMind разработала RoboCat, чтобы он гулял сам по себе

 

Роботы используют людей как сенсоры при движении в толпе

 

Навигация у роботов-пылесосов

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

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

Источник
Комментарии 0
Оцените статью
WARHEAD.SU
Добавить комментарий