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

Алгоритм исследователей MIT CSAIL Graphs of Convex Sets (GCS) Trajectory Optimization представляет собой масштабируемую систему планирования движения без столкновений для этих роботизированных навигационных нужд.

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

GCS может отображать траектории без столкновений в 14 измерениях (и, возможно, в большем количестве) с целью улучшения совместной работы машин на складах, в библиотеках и в домашних условиях.

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

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

В последующих экспериментах исследователи убрали полки, а роботы поменяли местами баллончики с красками и передали друг другу коробки с сахаром.

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

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

«Роботы превосходно справляются с повторяющимися, заранее запланированными движениями в таких приложениях, как автомобилестроение или сборка электроники, но им сложно генерировать движения в реальном времени в новых средах или задачах.

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

Планирование движения с использованием Graph-of-Convex-Sets (GCS) позволяет роботам легко адаптироваться к различным конфигурациям в заранее рассчитанных выпуклых областях, что позволяет роботу «поворачивать за угол» при составлении планов движения. Таким образом, GCS позволяет роботу быстро и эффективно рассчитывать планы в безопасных регионах, используя выпуклую оптимизацию.

«В этой статье представлен новый подход, который потенциально может значительно повысить скорость и эффективность движений роботов, а также их способность адаптироваться к новым условиям», — говорит Дэвид М.С. Джонсон, соучредитель и генеральный директор Dexai Robotics.

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

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

Сочетая поиск по графу и выпуклую оптимизацию, GCS может находить пути в сложных условиях и одновременно оптимизировать траекторию движения робота.

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

Первоначально GCS была предложена в статье 2021 года как математическая основа для поиска кратчайших путей в графах, где для прохождения ребра требуется решение задачи выпуклой оптимизации.

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

Статья 2023 года была размещена на обложке журнала Science Robotics , а первоначальная работа группы теперь опубликована в журнале по оптимизации Общества промышленной и прикладной математики (SIAM).

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

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