Большинство видео с роботами, проходящими полосу препятствий демонстрируют периоды “размышления” машин перед каждым следующим шагом - алгоритму планирования передвижения требуется время. Такие “размышления”, как правило, связаны с высокой нагрузкой на процессор.

Исследователи из Университета Дьюка, США, представили технологию, способную ускорить расчеты примерно в 3 раза и затратить на них почти в 20 раз меньше энергии.

Вместо того, чтобы использовать центральный и графический процессоры робота, ученые разработали специализированный процессор, который может оценивать шансы столкновения на каждом участке 3D-сетки одновременно!

Действия робота, построенного по такой схеме, выглядят практически “отрепетированными”, однако это не так - планирование траектории осуществляется в реальном времени, вот только теперь оно занимает миллисекунду! В публикации разработчиков представлены изображения, иллюстрирующие “вероятностную дорожную карту”, PRM робота - т.е. график, объединяющий совокупность точек в плоском или трехмерном пространстве, через которые может пройти машина, не столкнувшись с препятствием. Планирование траектории сводится ко введению в эту модель начальной и конечной точек движения, и последующей оценке наиболее эффективного маршрута между ними.

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

Следует отметить, что на практике нередко возникают проблемы, связанные с тем, что в ситуации, когда важная деталь робота должна попасть в определенную точку (например, манипулятор или элемент полезной нагрузки), менее важный элемент конструкции (например, оставшаяся часть “руки” робота) мешает процессу, встречая на пути преграду. Так возникает еще один показатель - “рабочий объем” (на изображении ниже):

Это проблемное место многих алгоритмов - роботу необходимо удостовериться, что “рабочий объем” не пересечется с преградой. Как правило, машина сверяет геометрическую модель объема с моделью окружающих объектов (каждый раз начиная с нуля), на что уходит 99% времени всех расчетов.

В Университете Дьюка решили использовать два нововведения. Первый подразумевает разовую генерацию порядка 150 тысяч “углов” вероятностной дорожной карты  потенциальных движений робота, исключающих столкновение с самим собой или объектами, неизбежно находящимися рядом (что особенно актуально для промышленных роботов). Второй - это использование отдельного процессора. Полученную “карту” уплотняют и оптимизируют, сводя к конкретным сценариям (порядка 10 тысяч расчетов). В рамках этих сценариев, из 150 тысяч “углов” отсеиваются те, которые система использует редко. В итоге остается порядка тысячи “углов”, что достаточно для того, чтобы робот мог решить поставленную перед ним задачу!

Изображения выше иллюстрируют алгоритм действий робота. Разработчики формируют описание робота (a), создают модель PRM (b),  фиксируют “достижимое рабочее пространство” и выделяют в нем соответствующий рабочий объем (с), формируют логическое выражение, с координатами в качестве входных данных и выдает “Истину” если движение возможно (d).  На следующем (e) этапе, выражение оптимизируется и превращается в алгоритм поиска. Когда робот формирует план движения, он анализирует окружение, определяет то, какие участки “картины окружающего мира” являются препятствиями и использует их координаты для расчета угрозы столкновения (f). Из всех расчетов сохраняются только те, которые исключают столкновения.

Далее в дело вступает новый процессор. Робот использует ПЛИС для реализации параллельных расчетов пространства движений. Устройство включает схемы обнаружения потенциальных преград, каждая из отдельных схем отвечает за один из углов модели PRM. Каждая схема получают на вход 3D-изображение в виде цветовой карты “глубин”, выдавая на выход ответ о том, приведет ли тот или иной маршрут к столкновению. Если преграда будет обнаружена, маршрут отсеивается, оставляя PRM из “свободных траекторий”, из которых устройству остается выбрать кратчайшую.

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