Команда Robotics от Duke ускоряет планирование движения в реальном времени по коэффициенту 10000
Исследователи из Университета Дьюка значительно улучшили планирование движения роботов в сложных условиях.
Планирование движения в приложениях робототехники
Роботы изготавливаются для широкого спектра применений. В некоторых из этих приложений, таких как конвейер фабрики, робот работает в известной и статической среде. Поскольку объекты вокруг робота известны и исправлены, мы можем запрограммировать робота для перемещения, не сталкиваясь ни с чем.
С другой стороны, есть приложения, в которых среда изменяется со временем. Поисковый робот, например, обычно не сталкивается с фиксированной и известной средой. В этих приложениях роботу требуется планирование движения, чтобы избежать столкновения с объектами в окружающей среде.
По словам Даниэля Сорина, профессора электротехники и вычислительной техники и компьютерных наук Герцога, до сих пор роботы всегда либо ограничивались предопределенным набором движений, либо обременены массовыми расчетами поиска путей. Робот должен учитывать все возможные движения и определять, приводит ли движение к столкновению с окружающей средой. Это вычислительно трудоемкий процесс даже для современных мощных процессоров.
Задачи планирования движения
Планирование движения не является новой проблемой, и проводится огромное количество исследований для поиска алгоритмов, которые не позволяют роботам столкнуться. Однако эти алгоритмы слишком тяжелы для использования в приложениях реального времени.
Как правило, с мощным графическим процессором (GPU) требуется сотни миллисекунд для планирования движения в сложной среде. Более того, энергопотребление этих конструкций настолько велико, что делает их нецелесообразными даже во многих промышленных применениях.
Планирование движения является одним из основных препятствий, препятствующих тому, чтобы роботы были доступны в нашей повседневной жизни. По словам Джорджа Конидариса, доцента по информатике и электротехнике и вычислительной технике Университета Дьюка, планирование движения не является проблемой 3D. Если роботизированная рука имеет 7 суставов, планирование движения будет 7-мерной проблемой. Это связано с тем, что робот должен найти последовательность совместных позиций для каждого сустава в руке.
Новое оборудование для задачи
Из-за ограничений мощности и скорости предыдущих проектов команда Сорина решила найти практическое решение проблемы поиска путей. Результатом является схема, специально разработанная для выполнения алгоритма планирования движения. Он настолько специализирован в своей цели, что он не делает ничего, кроме планирования движения.
Новый чип, который ускоряет планирование движения почти в 10000 раз и уменьшает мощность в 15 раз, был протестирован на роботизированной руке. Будущие применения этого исследования включают автономные автомобили, промышленные приложения и многое другое.
По словам Мюррея, аспиранта, участвующего в этом проекте, новый дизайн привлек большое внимание со стороны промышленных и коммерческих групп, включая Honda, Dyson, DoraBot и Mitsubishi.
В оставшейся части этой статьи мы кратко рассмотрим последние методы, принятые командой робототехники в Университете Дьюка.
Планирование движения по вероятностной дорожной карте
Вероятностная дорожная карта (PRM) является одним из наиболее широко используемых решений проблемы планирования движения. Перейдем к примеру.
На следующем рисунке показан пример построения PRM, который помогает роботу найти его путь от позиции q0 до положения G:
Рисунок (1) Выбор пробного пространства вокруг робота для выбора безопасного пути. Изображение предоставлено Университетом Дьюка (PDF)
Чтобы найти решение, пробоотборное пространство, которое не перекрывается с препятствиями. Эти образцы показаны узлами на изображении.
Если прямое движение от одного узла к другому не приводит к столкновению, мы можем решить подключить эти два узла. Такое соединение (называемое «краем») показывает, что прямое перемещение между этими двумя узлами разрешено и без конфликтов.
Затем нам нужно найти путь от q0 до G, используя линии (или ребра) достигнутого графика. Обнаружение столкновений (определение того, является ли соединение между двумя узлами причиной столкновения или нет) является наиболее трудоемкой частью метода PRM. Почти 99% вычислений в планировании движения обычно связаны с обнаружением столкновения.
Как показано на рисунке (2), когда движется робот, его путь движения можно рассматривать как охваченный объем.
Рисунок (2) Путь движения можно рассматривать как объемный объем. Изображение предоставлено Университетом Дьюка (PDF)
Обнаружение столкновений исследует этот охваченный объем вместе с препятствиями для достижения модели, которая предсказывает столкновения.
В отличие от некоторых предыдущих проектов, которые полагаются просто на использование многоядерного характера GPU, робототехника Герцога использует два метода для ускорения планирования движения: предварительные вычисления и параллелизм. В сочетании, эти методы способны ускорить планирование движения в 10000 раз. Под предварительным вычислением мы подразумеваем, что значительная часть вычислений выполняется только один раз, на стадии проектирования. Используя результаты этапа предварительного вычисления, разработана некоторая схема, которая использует метод параллелизма для дальнейшего ускорения процесса.
Предварительное вычисление наряду с параллелизмом
Большой общий PRM рассматривает как постоянные препятствия в окружающей среде, так и структуру робота. В конкретном приложении вместо этого используется обрезанная версия этого PRM. Поэтому нам необходимо, чтобы первоначальный PRM был достаточно большим, чтобы было очень сложно содержать решения для различных задач планирования движения.
Затем пространство вокруг робота дискретизируется на небольшие элементы объема, называемые вокселями. Каждому вокселю назначается 15-битный двоичный номер. Каждый край PRM, который соответствует определенному объему проката, проверяется и перечислены все вокселы, перекрывающиеся с этим конкретным краем.
Затем проектируется оптимизированная схема (которая связана с рассмотренным краем). Эта схема принимает 15-битный код для вокселей и выводит истинное значение для перекрывающихся вокселей.
Визуализация вокселей вокруг области, в которой может работать роботизированная рука. Изображение предоставлено Университетом Дьюка
Вышеприведенные расчеты выполняются один раз во время первоначального проектирования.
Другими словами, мы исследуем фиксированную среду и структуру робота, прежде чем робот начнет решать проблему.
Мы определяем большое количество небольших движений (т. Е. Ребер общего PRM выше), скажем 1024. Мы определяем их для робота таким образом, что конкретный подмножество этих движений будет решением проблемы из набора наших практических задач планирования движения.
Затем мы рассмотрим все эти 1024 движения и перечислим вокселы, которые перекрываются с каждым движением.
Основываясь на наших выводах, мы разработали схему для каждого движения (края), которое принимает код воксела и сообщает нам, существует ли перекрытие. Поскольку мы создаем такую схему обнаружения столкновения (CDC) для каждого возможного движения, CDC способны работать одновременно.
Поэтому у нас есть 1024 CDC, которые могут одновременно принимать воксел и отмечать все движения, которые перекрываются с этим конкретным вокселем. Опять же, все эти действия выполняются на этапе проектирования - прежде чем робот начнет решать проблему. Это значительно снижает вычислительную нагрузку робота во время выполнения.
В Runtime
Предварительные вычисления значительно упрощают время выполнения. Во время выполнения нам нужно только сканировать среду и отправлять двоичный код вокселей, которые заняты препятствиями для CDC.
Воксолы отправляются по одному, и все ребра проверяются одновременно для этого конкретного воксела. Если обнаружено столкновение, соответствующий край (движение) исключается из общего PRM. Таким образом, все движения, которые приводят к столкновению, устраняются, и робот может найти свой путь от обрезанного PRM.
Вышеупомянутые методы более подробно рассматриваются в Robotics 2016; Науки и систем в Мичиганском университете.
На видео ниже показана роботизированная рука с потрясающими результатами новых методов планирования движения. Обратите внимание, что без новых методов следующее видео было бы похоже на последовательность небольших движений и пауз в несколько сотен миллисекунд, тогда как новая конструкция уменьшает время паузы до почти 1 миллисекунды.
Видео предоставлено EurekAlert
Konidaris и его команда начали выделение компании Realtime Robotics, чтобы помочь коммерциализировать новые технологии. Эта коммерциализация может помочь ускорить развитие этой технологии, то есть мы могли бы увидеть роботизацию планирования движения в реальном времени в приложении раньше, чем считалось ранее.