Прежде чем робот сможет взять посуду с полки и накрыть на стол, он должен убедиться, что его захват и рука ни во что не врежутся и не разобьют прекрасный фарфор. В рамках процесса планирования движения робот обычно запускает алгоритмы «проверки безопасности», которые проверяют, что его траектория не имеет столкновений.
Однако иногда эти алгоритмы генерируют ложные срабатывания, заявляя, что траектория безопасна, хотя робот на самом деле может с чем-то столкнуться. Другие методы, позволяющие избежать ложных срабатываний, обычно слишком медленны для роботов в реальном мире.
Теперь исследователи Массачусетского технологического института разработали метод проверки безопасности, который может со 100-процентной точностью доказать, что траектория робота останется без столкновений (при условии, что модель робота и окружающей среды сама по себе точна). Их метод, настолько точный, что позволяет различать траектории, отличающиеся всего на миллиметры, обеспечивает доказательство всего за несколько секунд.
Но пользователю не нужно верить исследователям на слово — математическое доказательство, полученное с помощью этого метода, можно быстро проверить с помощью относительно простых математических вычислений.
Исследователи достигли этого с помощью специального алгоритмического метода, называемого программированием суммы квадратов, и адаптировали его для эффективного решения проблемы проверки безопасности. Использование программирования суммы квадратов позволяет обобщить их метод на широкий диапазон сложных движений.
Этот метод может быть особенно полезен для роботов, которым необходимо быстро двигаться, избегая столкновений в пространствах, заполненных объектами, например, роботы для приготовления пищи на коммерческой кухне. Он также хорошо подходит для ситуаций, когда столкновения роботов могут привести к травмам, например, домашние медицинские роботы, которые ухаживают за слабыми пациентами.
«Благодаря этой работе мы показали, что некоторые сложные проблемы можно решить с помощью концептуально простых инструментов. Программирование суммы квадратов — это мощная алгоритмическая идея, и, хотя она не решает все проблемы, если вы будете осторожны в ее применении, вы сможете решить некоторые довольно нетривиальные проблемы», — говорит Александр Амис, электротехник и компьютерщик. аспирант естественных наук (EECS) и ведущий автор статьи по этой методике.
К написанию статьи присоединились его коллега-аспирант EECS Питер Вернер и старший автор Расс Тедрейк, профессор Toyota в области EECS, аэронавтики, космонавтики и машиностроения, а также член Лаборатории компьютерных наук и искусственного интеллекта (CSAIL). Работа будет представлена на Международной конференции по роботам и автоматизации.
Сертификация безопасности
Многие существующие методы, которые проверяют, является ли запланированное движение робота свободным от столкновений, делают это путем моделирования траектории и проверки каждые несколько секунд, чтобы увидеть, не столкнется ли робот с чем-нибудь. Но эти статические проверки безопасности не могут определить, столкнется ли робот с чем-то в промежуточные секунды.
Возможно, это не проблема для робота, блуждающего по открытому пространству с небольшим количеством препятствий, но для роботов, выполняющих сложные задачи в небольших помещениях, несколько секунд движения могут иметь огромное значение.
Концептуально, один из способов доказать, что робот не движется к столкновению, — это поднять лист бумаги, который отделяет робота от любых препятствий в окружающей среде. Математически этот лист бумаги называется гиперплоскостью. Многие алгоритмы проверки безопасности работают, генерируя эту гиперплоскость в один момент времени. Однако каждый раз, когда робот движется, для выполнения проверки безопасности необходимо пересчитывать новую гиперплоскость.
Вместо этого этот новый метод генерирует функцию гиперплоскости, которая движется вместе с роботом, поэтому он может доказать, что вся траектория не имеет столкновений, а не работает по одной гиперплоскости за раз.
Исследователи использовали программирование суммы квадратов — набор алгоритмических инструментов, который может эффективно превратить статическую задачу в функцию. Эта функция представляет собой уравнение, которое описывает, где должна находиться гиперплоскость в каждой точке запланированной траектории, чтобы она оставалась без столкновений.
Сумма квадратов может обобщить программу оптимизации и найти семейство гиперплоскостей без столкновений. Часто сумму квадратов считают сложной оптимизацией, подходящей только для автономного использования, но исследователи показали, что для этой задачи она чрезвычайно эффективна и точна.
«Главным здесь было выяснить, как применить сумму квадратов к нашей конкретной проблеме. Самой большой проблемой было придумать первоначальную формулировку. Если я не хочу, чтобы мой робот с чем-то столкнулся, что это означает математически и может ли компьютер дать мне ответ?» — говорит Эмис.
В конце концов, как следует из названия, сумма квадратов создает функцию, которая представляет собой сумму нескольких значений в квадрате. Функция всегда положительна, поскольку квадрат любого числа всегда является положительным значением.
Доверяй, но проверяй
Дважды проверив, что функция гиперплоскости содержит квадратичные значения, человек может легко убедиться, что функция положительна, что означает, что траектория не имеет столкновений, объясняет Эмис.
Хотя метод подтверждает безупречную точность, при этом предполагается, что у пользователя есть точная модель робота и окружающей среды; математический сертификат настолько хорош, насколько хороша модель.
«Одна из действительно хороших особенностей этого подхода заключается в том, что доказательства действительно легко интерпретировать, поэтому вам не нужно верить мне, что я закодировал их правильно, потому что вы можете проверить это сами», — добавляет он.
Они проверили свою технику в моделировании, подтвердив, что сложные планы движения роботов с одной и двумя руками не допускают столкновений. В самом медленном случае их метод требовал всего несколько сотен миллисекунд для создания доказательства, что делало его намного быстрее, чем некоторые альтернативные методы.
«Этот новый результат предполагает новый подход к подтверждению того, что сложная траектория робота-манипулятора не имеет столкновений, элегантно используя инструменты математической оптимизации, превращенные в удивительно быстрое (и общедоступное) программное обеспечение. Хотя этот результат еще не дает полного решения для быстрого планирования траектории в загроможденной среде, он открывает двери для нескольких интригующих направлений дальнейших исследований», — говорит Дэн Гальперин, профессор информатики Тель-Авивского университета, который не участвовал в этом исследовании. .
Хотя их подход достаточно быстр, чтобы его можно было использовать в качестве окончательной проверки безопасности в некоторых реальных ситуациях, он все еще слишком медленный, чтобы его можно было реализовать непосредственно в цикле планирования движения робота, где решения должны приниматься за микросекунды, говорит Амис.
Исследователи планируют ускорить свой процесс, игнорируя ситуации, которые не требуют проверки безопасности, например, когда робот находится далеко от любых объектов, с которыми он может столкнуться. Они также хотят поэкспериментировать со специализированными решателями оптимизации, которые могли бы работать быстрее.
«Роботы часто попадают в неприятности, преодолевая препятствия из-за плохих приближений, которые используются при построении их маршрутов. Эмис, Вернер и Тедрейк пришли на помощь с новым мощным алгоритмом, который быстро гарантирует, что роботы никогда не перейдут свои границы, тщательно используя передовые методы вычислительной алгебраической геометрии», — добавляет Стивен ЛаВель, профессор факультета информационных технологий и электротехники. Инженерное дело в Университете Оулу в Финляндии, и кто не участвовал в этой работе.
Эту работу частично поддержали Amazon и Исследовательская лаборатория ВВС США.