Если вы когда-нибудь наблюдали за тем, как работают демо-версии роботов, то наверняка замечали, что робот может надолго «зависать», прежде чем продолжить движение. Можно подумать, что таким образом робот размышляет над тем, в какой момент и по какой траектории двигаться. Это предположение недалеко от истины: в этот момент процессор обрабатывает операции планирования движения, что зачастую отнимает много времени.

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

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

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

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

Рабочий объем — пространство, в котором робот меняет свое положение из одной позиции в другую.

Результаты исследования показали, что на обнаружение препятствий уходит более 99% процентов вычислительного времени. Предварительные вычисления производятся тогда, когда робот настроен. Вы создаете одну карту, которая состоит примерно из 150 тысяч ребер, описывающих возможные траектории движения робота, избегая при этом само-столкновений и столкновений с вещами, которые не изменяют своего положения, например, полом.

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

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

Ограничить количество ребер на карте до какого-то приемлемого значения очень важно, поскольку ограничены возможности процессора, который обрабатывает операции планирования. В данном случае процессор – программируемая логическая интегральная схема (ПЛИС) – запрограммирован с массивом схем обнаружения столкновений, каждая из которых соответствует одном ребру на карте. Таким образом размер карты ограничен количеством таких схем, которые могут поместиться на ПЛИС – максимум несколько тысяч.

Технология ученых из университета Дьюка работает путем разбивки рабочего пространства на тысячи вокселей. Затем алгоритм определяет, заложена ли в одном из вокселей заранее запрограммированная траектория движения объекта. Благодаря ПЛИС технология проверяет тысячи маршрутов одновременно, а затем сшивает кратчайший путь, используя оставшиеся безопасные варианты. Роботу остается только исполнить его.

На выходе ученые получили значительное ускорение: независимо от того, сколько ребер на карте, скорость обработки всей карты у ПЛИС составила 50 наносекунд на один пиксель. В одном особенно сложном примере обработка заняла чуть больше 0,6 мс. Планировщик, который работал на основе четырехъядерного процессора Intel Xeon с тактовой частотой 3,5 гигагерц справился с этой задачей за 2,738 мс. Обычные процессоры потребляют около 200–300 Вт электроэнергии во время планировки движения, а разработка ученых из университета Дьюка – менее 10 Вт.

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

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

Динеш Маноча, профессор университета Северной Каролины в Чапел-Хилл, который работает над планировщиком движения в режиме реального времени на графических процессорах согласен с тем, что ПЛИС обладает серьезным потенциалом увеличить эффективность планирования движения. Он уверен, что разработка ученых найдет свое практическое применение в ближайшем будущем: роботы все чаще используются в новых, неопределенных условиях, роль планирования движения со временем будет только увеличиваться.

Стартап Realtime Robotics будет коммерциализировать технологию ученых. В рамках этого проекта ПЛИС заменят на специализированные интегральные схемы (ASIC), которые могут объединить более 100 тысяч ребер. Такой апгрейд позволит роботам работать в самых разнообразных средах.