Роботу нелегко найти выход из лабиринта. Представьте себе машины, пытающиеся пройти через детскую игровую комнату, чтобы добраться до кухни, с разными игрушками, разбросанными по полу, и мебелью, блокирующей некоторые потенциальные пути. Этот запутанный лабиринт требует от робота расчета наиболее оптимального пути к месту назначения, не врезаясь ни в какие препятствия. Что делать боту?
Алгоритм «Оптимизация траектории графиков выпуклых множеств (GCS)» исследователей Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института (CSAIL) представляет собой масштабируемую систему планирования движения без столкновений для этих роботизированных навигационных нужд. Этот подход сочетает в себе поиск по графу (метод поиска дискретных путей в сети) и выпуклую оптимизацию (эффективный метод оптимизации непрерывных переменных с целью минимизации заданной стоимости) и позволяет быстро находить пути в средах, похожих на лабиринт, одновременно оптимизируя траектория движения робота. GCS может отображать траектории без столкновений в 14 измерениях (а возможно, и в большем количестве) с целью улучшения совместной работы машин на складах, в библиотеках и в домашних условиях.
Проект под руководством CSAIL последовательно находит более короткие пути за меньшее время, чем аналогичные планировщики, демонстрируя способность GCS эффективно планировать в сложных средах. В демонстрациях система умело направляла две роботизированные руки, держащие кружку, вокруг полки, оптимизируя при этом кратчайшее время и путь. Синхронные движения дуэта напоминали парный танец: они покачивались по краям книжного шкафа, не роняя предметы. В последующих экспериментах исследователи убрали полки, а роботы поменяли местами баллончики с красками и передали друг другу коробки с сахаром.
Успех этих реальных испытаний показывает, что алгоритм может помочь в таких областях, как производство, где две роботизированные руки, работающие в тандеме, могут снять товар с полки. Точно так же этот дуэт может помочь убрать книги в доме или библиотеке, избегая других предметов поблизости. В то время как проблемы такого рода ранее решались с помощью алгоритмов на основе выборки, которые могут с трудом справляться с многомерными пространствами, GCS использует быструю выпуклую оптимизацию и может эффективно координировать работу нескольких роботов.
«Роботы превосходно справляются с повторяющимися, заранее запланированными движениями в таких приложениях, как автомобилестроение или сборка электроники, но им трудно генерировать движения в реальном времени в новых средах или задачах. Предыдущие современные методы планирования движения использовали подход «ступица и спица», используя предварительно рассчитанные графики конечного числа фиксированных конфигураций, которые, как известно, безопасны. Во время работы робот должен строго придерживаться этой дорожной карты, что часто приводит к неэффективным движениям робота. Планирование движения с использованием графика выпуклых множеств (GCS) позволяет роботам легко адаптироваться к различным конфигурациям в заранее рассчитанных выпуклых областях. — позволяя роботу «заворачивать за угол», строя планы движения. Таким образом, GCS позволяет роботу быстро и эффективно рассчитывать планы в безопасных регионах, используя выпуклую оптимизацию. В этой статье представлен новый подход, который потенциально может значительно повысить скорость и эффективность движений роботов, а также их способность адаптироваться к новым условиям», — говорит Дэвид М.С. Джонсон, соучредитель и генеральный директор Dexai Robotics.
GCS также преуспела в демонстрациях моделирования, где команда рассматривала, как квадрокоптер может пролетать сквозь здание, не врезаясь в деревья и не попадая в двери и окна под правильным углом. Алгоритм оптимизировал путь вокруг препятствий, одновременно учитывая богатую динамику квадрокоптера.
Рецепт успеха команды Массачусетского технологического института включает в себя сочетание двух ключевых ингредиентов: поиска по графам и выпуклой оптимизации. Первый элемент GCS ищет графы, исследуя их узлы, вычисляя различные свойства каждого из них, чтобы найти скрытые закономерности и определить кратчайший путь для достижения цели. Подобно алгоритмам поиска по графу, используемым для расчета расстояния в Картах Google, GCS создает различные траектории для достижения каждой точки на своем пути к месту назначения.
Сочетая поиск по графу и выпуклую оптимизацию, GCS может находить пути в сложных условиях и одновременно оптимизировать траекторию движения робота. GCS достигает этой цели, отображая на графике различные точки в окрестностях, а затем рассчитывая, как добраться до каждой из них на пути к конечному пункту назначения. Эта траектория учитывает разные углы, чтобы робот избегал столкновений с краями препятствий. Полученный в результате план движения позволяет машинам обходить потенциальные препятствия, точно маневрируя на каждом повороте так же, как водитель избегает аварий на узкой улице.
Первоначально GCS была предложена в статье 2021 года как математическая основа для поиска кратчайших путей в графах, где для прохождения ребра требуется решение задачи выпуклой оптимизации. Перемещаясь точно по каждой вершине в больших графах и многомерных пространствах, GCS имел явный потенциал в планировании движения роботов. В последующей статье аспирант шестого курса Массачусетского технологического института Тобиа Маркуччи и его команда разработали алгоритм, применяя свою структуру для решения сложных задач планирования для роботов, движущихся в многомерных пространствах. Статья 2023 года появилась на обложке журнала. Научная робототехника На прошлой неделе первоначальная работа группы была принята к публикации в Обществе промышленной и прикладной математики (SIAM). Журнал по оптимизации.
Хотя алгоритм превосходно справляется с перемещением в ограниченном пространстве без столкновений, ему еще есть куда расти. Команда CSAIL отмечает, что GCS в конечном итоге может помочь в решении более сложных проблем, когда роботам приходится вступать в контакт с окружающей средой, например, отталкивать или сдвигать объекты с дороги. Команда также изучает возможности применения оптимизации траектории GCS для решения задач робота и планирования движения.
«Я очень воодушевлен применением GCS для планирования движений. Но это только начало. Эта структура тесно связана со многими основными результатами в области оптимизации, управления и машинного обучения, что дает нам новые возможности для решения проблем, которые одновременно являются непрерывными и комбинаторными», — говорит Расс Тедрейк, профессор Массачусетского технологического института, главный исследователь CSAIL и соавтор нового исследования. документ о работе. «Есть еще много работы!»
Маркуччи и Тедрейк написали статью вместе с бывшим научным сотрудником выпускника CSAIL Марком Петерсеном; MIT по электротехнике и информатике (EECS), CSAIL и аспирант по аэронавтике и космонавтике Дэвид фон Врангель SB ’23. Более общая структура Graph of Convex Sets была разработана Маркуччи и Тедрейком в сотрудничестве с Джеком Уменбергером, бывшим постдоком MIT CSAIL, и Пабло Паррило, профессором EECS в MIT. Работу группы частично поддерживали Amazon.com Services, Программа стипендий для выпускников Национальной оборонной науки и техники Министерства обороны, Национальный научный фонд и Управление военно-морских исследований.