На прошлой неделе мы разбирались, как устроен алгоритм координации походки легендарного BigDog. Робот еще не был автономным и мог пересекать местность только под управлением оператора.
Большинство читателей в прошлый раз одобрили идею нового перевода — о том, как BigDog научился самостоятельно проходить путь до нужной точки и ориентироваться в пространстве. Ну и, собственно, вот он.
В системе навигации BigDog используется комбинация планарного лазерного сканирования, стереозрения и проприоцептивного восприятия. С ее помощью определяется расположение робота в окружающем мире. Она обнаруживает препятствия и помещает их в двухмерную модель мира. Затем она планирует путь и управляет роботом, чтобы тот следовал по выбранной траектории. Планировщик путей — это вариация классического алгоритма поиска A*. Алгоритм сглаживания обрабатывает полученные результаты и передает их алгоритму следования пути. Тот вычисляет рулевые команды для BigDog.
Описанная система была протестирована в лесной зоне со множеством деревьев, валунов, подлеска. Помимо равнинных территорий, в ней также были склоны (углом до 11 градусов). Всего было выполнено 26 тестов, из которых 88% оказались успешными. Робот «видел» местность в радиусе 130 метров при движении с заданной скоростью и преодолел более 1,1 км.
Аппаратура
1) Проприоцептивные датчики
Используются для управления походкой BigDog и автономной навигации. Каждая из 16 активных и 4 пассивных степеней свободы робота оснащена датчиком. Они предоставляют данные о текущем положении и нагрузке. Эта информация комбинируется с данными IMU, чтобы оценивать состояние контакта с землей, высоту положения корпуса, скорость тела. Кроме того, ряд сенсоров показывает состояние двигательной, вычислительной, гидравлической, тепловой и других систем BigDog.
Датчики BigDog: а) GPS-антенна; b) лидар; c) стереокамера Bumblebee; d) IMU от Honeywell; e) датчики суставов.
2) Экстероцептивные датчики
Робот оснащен четырьмя внешними датчиками: лидаром SICK LMS 291, стереокамерой PointGrey от Bumblebee, GPS-приемником NovAtel и IMU от Honeywell. Данные от них поступают в систему, изображенную на схеме ниже.
3) Компьютеры
Для реализации системы с приведенной схемы используются два компьютера. Главный компьютер BigDog — PC104 с одноядерным процессором Intel Pentium M (1,8 ГГц). Он взаимодействует с проприоцептивными датчиками, контролирует баланс и движения робота, вычисляет актуальную модель окружающей среды и путь через нее, а также осуществляет управление походкой.
Зрение обеспечивается отдельным компьютером на процессоре Intel CoreDuo (1,7 ГГц). Он обменивается данными с парой камер, обнаруживает несоответствия, оценивает показатели визуальной одометрии и поддерживает 3D-карту местности. Этот компьютер передает карту и данные визуальной одометрии главному компьютеру с частотой 15 Гц через бортовую локальную сеть.
Преимущество такой системы — в возможности упростить задачу планирования, разбивая ее на две части. Данные от лидара и сенсоров трехмерны, но мы можем полагаться на самостабилизацию системы управления походкой, чтобы отказаться от более сложного 3D-восприятия и планирования.
Технический подход
В нашем общетехническом подходе мы используем данные от двух датчиков состояния окружающей среды, чтобы распознавать препятствия, просчитывать траекторию движения сквозь или в обход препятствий и командовать системой управления походкой робота для следования заданной траектории.
Весь процесс можно разбить на три этапа. Сначала изображения с лидара и камеры обрабатываются для получения перечня точек, обозначающих препятствия в окружающей среде. Затем эти точки разделяются на непересекающиеся объекты и отслеживаются на протяжении некоторого времени. Далее эти объекты объединяются во временной памяти для составления картограммы. Эта картограмма используется для планирования направления движения к промежуточной цели. Планировщик создан, чтобы контролировать, что траектории движения BigDog находятся на надлежащем расстоянии от препятствий и что траектории стабильны в пространстве при итерациях планировщика. Алгоритм движения по заданной траектории заставляет робота следовать намеченному пути, посылая команды скорости системе управления походкой. Та поочерёдно передвигает конечности робота.
А. Сбор информации
1) Оценка положения
Есть два источника одометрической информации: кинематические датчики в ногах и система искусственного зрения. Полученные от них данные объединяются для оценки расположения робота.
Одометрическая система использует кинематическую информацию, полученную от ног, чтобы рассчитать движения робота. А система визуальной одометрии отслеживает визуальные характеристики для расчёта движения. Оба эти инструмента используют инерциальный измерительный модуль (IMU) как источник информации для пространственной ориентации. Общий расчётчик объединяет выходные данные этих двух одометров, акцентируя внимание на визуальной одометрии на низких скоростях и кинематике на более высоких скоростях. Объединение этих двух показателей устраняет недостатки каждого из расчётчиков: возможный отказ стереосистем, дрейф показаний одометра, расположенного в конечностях, во время бега на месте, а также ошибки этого датчика по вертикальной оси.
Лидар, используемый в роботе BigDog, выдает новое изображение каждые 13 миллисекунд. Каждое изображение трансформируется во внешнюю систему координат с центром в месте расположения робота. При этом используется синхронизированная во времени информация от расчётчика расположения. Полученное 3D-облако точек затем передается на обработку алгоритму сегментации, описанному ниже. Аналогичным образом система стереоскопического зрения собирает карты несоответствий в течение некоторого времени, чтобы создать 3D-карту местности в квадрате 4 х 4 метра, центрированном на роботе. Пространственный фильтр определяет области существенного изменения высоты (т.е. потенциальные препятствия) и передает перечень точек, принадлежащих к этим областям, алгоритму сегментации облака точек.
2) Сегментация облака точек и отслеживание объекта
Из-за неровностей земли и движений робота часть данных лидар-сканера будет включать в себя изображения земли. Отражения от длинных препятствий (например, стен) внешне похожи на отражения от земной поверхности. Для успешной работы система должна интерпретировать эти отражения таким образом, чтобы она могла управлять роботом вблизи стен, а не «бояться» земли. Первый шаг в данном процессе – сегментация точек препятствия, предоставленных лидаром и картой местности, в отдельные объекты. Редкие 3D-облака точек сегментируются в объекты путём слияния отдельных точек, разделенных расстоянием менее 0,5 метра.
Объекты, полученные благодаря алгоритму сегментации, отслеживаются на протяжении некоторого времени. Для выполнения этой задачи мы используем жадный итерационный алгоритм с эвристическими ограничениями. Объект на текущем изображении совпадает с ближайшим объектом последнего изображения, при условии, что объекты разделены расстоянием не более 0,7 метров.
Благодаря тому, что облака точек сегментируются в объекты и отслеживаются на протяжении некоторого времени, робот может адекватно передвигаться в окружающей среде с умеренными неровностями земли и препятствиями различных видов: деревьями, булыжниками, упавшими брёвнами, стенами. Деревья и стены определяются в основном лидар-сканером, а булыжники и брёвна – системой стереоскопического зрения.
Последовательность иллюстраций, показывающих робота (желтый прямоугольник) с: а) данными с лидара (синие точки), записанными за несколько секунд; b) соответствующими им объектами. Высокие коричневые объекты — это деревья. Отражения с земли показаны прозрачными и плоскими. Зеленый цилиндр — это цель; к нему ведет голубая линия рассчитанного пути. c) Вид сверху на картограмму: зеленым обозначены области с минимальным летальным значением, лиловым — области с наибольшим таким значением. Каждому подразделению сетки соответствует 5 метров.
Б. Планирование навигации
Наш подход к решению проблемы навигации является общепринятым в робототехническом сообществе. Точки препятствий (полученные благодаря процессам восприятия) наносятся на картограмму с центром в месторасположении робота. Конечная цель робота проектируется на границу картограммы, и к ней применяется вариант алгоритма A?. Этот процесс повторяется примерно раз в секунду.
1) Память об отслеживаемых препятствиях
Из-за ограниченного поля зрения двух датчиков робота крайне важно, чтобы у робота сохранялась точная память о препятствиях, которые он больше не может видеть. Поскольку список объектов предоставляется системой слежения за объектами, отдельные объекты добавляются, обновляются или удаляются в объектной памяти системы планирования. Размер списка объектов ограничен, поэтому при добавлении в него новых объектов другие должны удаляться.
Обозначив текущий список объектов переменной O, мы можем вычислить два параметризованных подкласса O:
Здесь age(q) – разница между текущим моментом времени и временем последнего измерения объекта q,
norm(q, r)inf – минимальное расстояние между текущим расположением робота и границей объекта q.
Объекты удаляются из О по следующим критериям:
- Множество {P(30) ? Q(15)} вычитается из О. Это объекты старше 30 секунд и расположенные не ближе 15 метров к роботу.
- Множество {P(1800) ? Q(10)} вычитается из О. Это объекты старше получаса и находящиеся не ближе 10 метров к роботу.
- Объекты удаляются из О по мере достижения лимита списка. Приоритет объекта определяется по времени, в течение которого он был успешно отслежен трекером. Другими словами, объекты, на которые робот «смотрел» дольше, дольше сохраняются в памяти.
- Однако не отбрасывается ни один объект, отслеженный в предыдущие 10 секунд.
Такое распределение ресурсов памяти приводит к следующему поведению: по мере того как объекты уходят из поля зрения датчиков робота, тот забывает удаленные объекты и объекты, которые он не видел несколько раз. Объекты, которые находятся в поле зрения или недоступны, но расположены близко к роботу, не забываются.
2) Создание картограммы
Мы используем картограмму, созданную на базе 2D-сетки, чтобы представить окружающую робота среду. Вместо того, чтобы динамически составлять картограмму (по мере того, как робот получает новую информацию об окружающей среде), новая картограмма составляется с каждой итерацией планирования и заполняется объектами из памяти планировщика. Из этого следует, что динамический планировщик маршрутов не может использоваться вместо алгоритма A*. Поскольку мы предполагаем размер объектов ограниченным (что отсутствие тупика в окружающей среде больше чем половина карты), объем задачи планирования и время вычисления пути невелики.
Картограмма заполнена значениями из списка объектов в соответствии со следующим алгоритмом:
Ячейкам, где размещаются объекты, присвоено очень высокое летальное значение. Показатель для ячеек поблизости от объекта задается в соответствии с функцией f, которая учитывает текущее расстояние до этой точки. Для результатов испытаний, представленных здесь, f была просто обратным кубом расстояния.
Эффект этого подхода в том, что от ячеек с очень высоким значением оно уменьшается постепенно по мере отдаления от них (и обозначаемых ими объектов).
3) Устойчивость пути
Чтобы убедиться, что мы не «управляем» BigDog в случайной и бессистемной манере, особое внимание уделяется устойчивости запланированного пути. Он должен быть настолько стабилен, насколько это возможно по итерациям планировщика путей. Это обеспечивается тремя способами.
Во-первых, начальная точка, передаваемая в алгоритм A*, — это не текущее положение робота, а проекция его положения в конечной точке пути, выданной до этого алгоритмом A* (назовем эту точку p). Пока BigDog следует запланированному пути, он может немного отклоняться от него вбок. Проецируя стартовую точку на точку предыдущего вычисления A* алгоритма, мы отфильтровываем колебание позиции робота, и выводимые планировщиком пути становятся более стабильны. Если робот отклоняется от пути больше, чем на установленное значение (по умолчанию это 3 метра), точка p просто переносится в текущее положение робота.
Во-вторых, чтобы убедиться в непрерывности планировщика пути, мы вычисляем q — проекцию позиции робота от 2,5 секунд в прошлом к последней точке, вычисленной алгоритмом A*. Затем отрезок последнего запланированного пути от q к p добавляется к вычислению нового пути. В итоге робот отслеживает небольшое расстояние уже пройденного пути. Благодаря этому алгоритм следования пути лучше показывает себя при существенных нарушениях положения, с которыми часто встречаются роботы на ногах.
В-третьих, в памяти робота сохраняется некоторая история запланированных путей. Эти пути используются для уменьшения значений тех ячеек картограммы, куда робот уже ходил, с одновременным увеличением значения ячеек близлежащей местности. Поэтому, как правило, новый запланированный путь в том же направлении будет повторять уже пройденный роботом путь (но без строгой гарантии этого).
4) Сглаживание пути
Вычисленный путь, поскольку он основывается на регулярной сетке, немного зазубрен. Существенные изменения направления могут вызвать нежелательные команды управления. Чтобы избежать этого, применяется алгоритм сглаживания Де Бура.
Кроме того, планирование путей на основании сетки часто приводит к технически оптимальным, но менее желательным путям к цели. Мы решаем эту проблему, вычисляя сглаженный путь для каждой итерации планировщика. Для последующих итераций ячейкам картограммы, где пролегает сглаженный путь, присваивается меньшее значение. Это обеспечивает более прямой и плавный путь к цели.
С. Контроль походки: подвижность и баланс
Система планирования навигации определяет новый путь примерно раз в секунду. Алгоритм следования пути, который работает на частоте 200 Гц, направляет робота в соответствии с последним запланированным путем. Этот алгоритм создает набор команд в виде желаемых скоростей тела, включая скорость движения вперед, боковую скорость и скорость рыскания тела. Эти скорости передаются в контроллер походки, который управляет движением ног.
На основе расстояния между роботом и путем используется одна из трех стратегий. Если робот находится поблизости от участка пути, он начинает двигаться по диагонали, пока не зайдет на него сбоку, двигаясь на полной скорости. Если робот далеко от пути, он направляетя точно вперед, к нужной точке. В промежуточном положении используется комбинация этих стратегий.
Подробное описание алгоритмов контроля походки вызодит за рамки этой статьи. Однако, как правило, скорости тела действуют как управляющие входы для низкоуровневых контроллеров походки BigDog. Контроллер походки производит команды силы и позиций для каждого сустава для обеспечения стабильности, реагирует на нарушения и обеспечивает нужные скорости тела. Хотя вычисления алгоритма следователя пути могут быть использованы для любой походки BigDog, оптимальной представляется походка рысью благодаря скорости и возможности пересечения грубой местности.
Результаты полевых тестов
Сенсорная и навигационная система, описанная выше, была установлена на BigDog и протестирована за пределами лаборатории. Испытания проводились на местности, где было много деревьев, валунов, подлеска, холмов со склонами до 11 градусов. На рисунке 1 показан примеры ландшафта. На рисунке 2 показаны данные от лидара, обработанные роботом.
Рис. 1. Ландшафт местности, где проводились испытания
Рис. 2. Тестовые испытания, вид сверху. Изображение получено с лидара и стереокамер. Темные области — деревья и другие препятствия. Размер сетки 5 метров.
Система навигации и планировщик разрабатывались в течение 7 месяцев, с регулярными тестами примерно раз в пять недель. Здесь описаны результаты последних испытаний.
Из 26 проведенных тестов 23 закончились успешно: робот достиг цели, не столкнулся ни с одним из препятствий и не был к этому близок. Исходы этих тестов отмечены в сводной таблице как Goal («Цель»). Робот упал в конце только одного теста после того, как наступил на небольшой камень. Обычно система контроля походки справляется с такими ситуациями, но не в этот раз (результат отмечен в таблице как Fall — «Падение»). В трех тестах роботу встретились на пути большие препятствия (шириной больше 20 метров). Робот вычислял, с какой стороны лучше обойти препятствие и не делал продвижений в заданный промежуток времени (20 секунд). Препятствия такого размера выходят за рамки, для которых была разработана автономная система. Результаты этих тестов в таблице обозначены как Live-lock («Блокировка»).
В этих 26 тестах робот был помещен в достаточно однотипные сценарии и лесную местность средней полосы. При усложнении окружающей среды количество исходов Live-lock увеличивается, а робот выбирает менее эффективные пути.
Больше интересного — на robo-hunter.com:
Наш канал на YouTube
a_freeman
<сарказм> зато наш аватар Федор умеет на квадроцикле сидеть.