Теперь исследователи из Массачусетского технологического института разработали метод проверки безопасности, который со 100% точностью демонстрирует, что траектория робота останется без столкновений (при условии точности моделей робота и окружающей среды). Их метод, настолько точный, что может различать траектории, отличающиеся всего на несколько миллиметров, предоставляет доказательство всего за несколько секунд.

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

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

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

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

Амис работал над статьей совместно с Питером Вернером, еще одним студентом факультета электротехники и информатики, и с Рассом Тедрейком, профессором аэронавтики, космонавтики и машиностроения факультета электротехники и информатики имени Тойоты, а также членом Лаборатории компьютерных наук и искусственного интеллекта (CSAIL). Работа будет представлена ​​на Международной конференции по робототехнике и автоматизации.

Подтвердить безопасность

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

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

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

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

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

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

«Ключевым моментом здесь было понять, как применить сумму квадратов к нашей конкретной задаче. Самой большой проблемой было придумать первоначальную формулировку. Если я не хочу, чтобы мой робот во что-либо врезался, что это означает с математической точки зрения, и может ли компьютер дать мне ответ?» — говорит Амис.

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

Доверяй, но проверяй

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

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

«Главное преимущество этого метода в том, что тесты очень легко интерпретировать, поэтому вам не нужно полагаться на то, что я правильно напишу код, потому что вы можете проверить его сами», — добавляет он.

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

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

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

Данная работа частично финансировалась компанией Amazon и Исследовательской лабораторией ВВС США.