Алгоритм позволяет роботам свободно ориентироваться на земле и в воздухе

«Наш алгоритм фактически разрабатывает стратегию, а затем исследует все возможные движения и выбирает лучшее из них с помощью динамического моделирования, например, играя сам с собой во множество симуляторов с участием движущихся роботов», — говорит соавтор работы Сун-Джо Чанг. — «Мы разработали эффективный способ поиска оптимального безопасного движения, который обычные методы оптимизации никогда бы не нашли». Команда назвала метод Spectral Expansion Tree Search (SETS)

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

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

«Вы же не хотите, чтобы конструктору пришлось вручную описывать эти движения и говорить: "Вот дискретный набор движений, которые должен уметь делать робот"», — говорит соавтор работы Джон Лэтроп. — «Чтобы решить эту проблему, мы придумали SETS». SETS использует теорию управления и линейную алгебру для поиска естественных движений, которые максимально используют возможности роботизированной платформы в физических условиях.

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

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

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

Чтобы преодолеть эту проблему, SETS использует компромисс между разведкой и эксплуатаций. «Мы хотим попробовать смоделировать траектории, которые мы еще не исследовали», — говорит Лэтроп. — «И мы хотим продолжать искать пути, которые ранее приносили высокую награду, — это "эксплуатация". Балансируя между разведкой и эксплуатацией, алгоритм быстро сходиться к оптимальному решению среди всех возможных траекторий».

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

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

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

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

Команда студентов и исследователей Калифорнийского технологического института в настоящее время применяет версию алгоритма SETS на автомобиле Indy, который примет участие в соревнованиях Indy Autonomous Challenge на выставке потребительской электроники (CES) в Лас-Вегасе 9 января.