Может ли беспилотный автомобиль ехать по городу без карты? Как управлять сотней коптеров одновременно? Как искусственный интеллект выбирает оптимальный маршрут? Рассказывает кандидат физико-математических наук Константин Яковлев.
Автономная навигация мобильных роботов — одна из ключевых задач в мобильной робототехнике: мобильный робот по определению должен перемещаться в окружающем пространстве. Разработчикам, исследователям и пользователям этих роботов хочется, чтобы навигация происходила в автоматическом режиме. Конечно, это требуется не всегда: если речь идет о точечной фото- или видеосъемке с помощью дрона, есть оператор, который полностью управляет его движением. Но можно представить ситуацию, когда без автономной навигации невозможно обойтись. Например, если речь идет о масштабной поисково-спасательной операции, когда работают десятки или даже сотни дронов. Найти сотню квалифицированных специалистов, которые могут в режиме реального времени управлять ими одновременно, проблематично, если не невозможно.
Половина работ по робототехнике связана именно с вопросами навигации. Иногда может показаться, что вопрос не имеет к этому отношения, но на самом деле имеет. Классический пример — распознавание пешеходов на видео. Беспилотным автомобилям нужно распознавать пешеходов по видеопотоку. При чем здесь навигация? Если подумать на шаг вперед, становится очевидно: после того как мы распознали пешехода, нам нужно внести коррективы в навигационный алгоритм. Мы должны либо экстренно затормозить, либо изменить траекторию, перепланировать маршрут. Проблемы навигации действительно сложны и с научной, и с инженерной точки зрения. Постоянно появляются новые датчики, новые робототехнические системы — хватит и на наш век, и на следующий.
Можно выделить четыре основных класса навигационных задач: локализация, картирование, планирование и следование по траектории. Локализация — это задача, которая формулируется следующим образом: у нас есть мобильный робот, известна карта окружающего пространства, но неизвестно, где он находится. При этом у мобильного робота есть датчики: радары, лазерные дальномеры, видеокамеры. С помощью информации, получаемой в реальном времени с этих датчиков, робот должен определить, где он находится, сопоставив наблюдения с имеющейся картой. Если эту задачу решать не один раз, а в течение какого-то времени, то получится след точек — траектория движения.
Обратная задача — это картирование. Наоборот, мы знаем свое точное положение в мировой системе координат. Например, у беспилотного автомобиля есть GPS-датчик, и он точно знает координаты точки, в которой находится. Локализацию делать не нужно, но мы ничего не знаем о мире вокруг нас, карты у нас нет. Нужно с помощью тех же датчиков построить модель мира, нанести на карту окружающие объекты — дома, дороги, — все правильно разметить, и, если дом левее дерева, на карте он должен быть левее. Желательно соблюсти масштаб в абсолютных единицах, чтобы мы знали размеры: до этого дома пять метров, а до дерева — семь с половиной. Это тоже сложная задача.
Еще сложнее, когда эти задачи объединяются. Бывают ситуации, когда у нас нет ни точного положения, ни карты. Например, коптер, который ведет поисково-спасательную операцию, и ему нужно найти выживших в полуразрушенном здании. Он летит до здания по открытой местности, карта есть, GPS ловит, мы все понимаем. Но как только он влетает в здание, GPS пропадает, и мы точно не знаем своего положения, потому что нет карты «внутренностей» здания, а даже если она была, то уже неактуальна из-за разрушений. Задачу навигации в такой постановке можно решать достаточно простыми алгоритмами. Есть класс алгоритмов — реактивные. В этом случае мы не берем во внимание отсутствие карты и координат, а просто летим по прямой и уклоняемся от препятствий, используя локальные простые алгоритмы из серии «обойди препятствие слева». Такой способ будет не очень эффективен, поэтому нам нужны локализация, картирование и планирование. Получается, нужно решать задачу одновременного картирования и локализации — по-английски это simultaneous localization and mapping (SLAM). Если вы спросите специалиста по робототехнике, чем он занимается, то с высокой степенью вероятности среди прочих проблем будут эти четыре буквы — SLAM.
Наиболее актуальной сейчас является постановка SLAM-задачи в контексте видеопотока. Она так и называется — visual-based simultaneous localization and mapping — одновременное картирование и локализация по видеопотоку, когда у нас из датчиков доступны только камеры, по которым мы должны восстановить модель мира, понять, где мы находимся и как двигаемся. Многие роботы могут быть оснащены только видеокамерами. На беспилотный автомобиль можно навесить много разных датчиков, поскольку он большой и выдержит приличный вес. На маленький коптер мощный лазерный дальномер уже не поставишь, зато камеры маленькие, потребляют мало энергии, и ими оснащают многие робототехнические системы. Вторая причина, почему эта задача интересна, чисто исследовательская: человек много информации воспринимает с помощью зрения, и хочется похожие принципы перенести на искусственные устройства.
Допустим, у нас есть карта, есть понимание, в какой точке мы находимся, и нам нужно теперь перемещаться в другую точку. Это следующий класс задач — задача планирования траектории. Смотрим сверху на карту. Там заштрихованы препятствия. Все остальное — это чистый лист, то есть проходимые области, свободное пространство. Нам нужно просто нарисовать линию, соединяющую точки А и Б. Здесь обычно задача сводится к задаче поиска пути на графике. Непрерывное свободное пространство содержит бесконечное число точек. Сначала мы строим его дискретную модель: накидываем опорные точки. Их уже конечное количество. Потом какие-то из этих точек по определенным алгоритмам соединяем линиями так, чтобы они не задевали заштрихованные области. Получается граф вариантов, как добираться из одной точки в другую. Наша задача — найти маршрут, который подходит больше всего, например самый короткий. Обычно это решается именно как поиск пути на графе. Используются различные эвристики — знания, которые позволяют сократить перебор вариантов и фокусируются на нашей цели.
Алгоритмы усложняются в зависимости от постановки. Сейчас мы рассмотрели простой, плоский случай. Постановка может быть трехмерной, среда неизвестной, а помимо статических могут попадаться динамические препятствия.
После того как мы начертили линию, нужно, чтобы мобильный робот по ней ехал, летел или полз. Четвертый блок задач — следование по траектории. Когда мы планировали траекторию, мы не задумывались о том, как эта линия должна выглядеть, — например, могли начертить поворот под углом 90 градусов. Это нестрашно для коптера, который может долететь до точки, повернуться на месте и полететь дальше, а вот автомобиль с места на 90 градусов не поедет. Либо нужно учитывать это на этапе планирования и усложнять задачу, либо на этапе следования возникает задача пройти вдоль построенной траектории не точно, но достаточно близко, минимизируя отклонения. Задача следования по траектории решается с помощью методов теории автоматического управления, различные регуляторы и позволяют не отклониться сильно от траектории, и учитывают кинематические и динамические ограничения конкретного объекта. Если это коптер, он не может мгновенно остановиться, ему нужно время, чтобы замедлиться.
Важна связка следования по траектории и планирования. Все эти методы связаны между собой, эта связка особенно важна, потому что, если мы очень сильно отклоняемся от траектории, нужно посылать запрос на перепланирование и заново запускать цикл. При этом какие-то задачи могут остаться на уровне следования по траектории: если резко возникло динамическое препятствие, мы можем без тщательного перепланирования быстро сделать локальный маневр. Как человек, если на него едет велосипедист, инстинктивно отходит либо влево, либо вправо, либо замирает на месте — здесь то же самое. Контроллер может принять решение и сделать локальный маневр.
Эти основные задачи в общем виде не решены. Для каких-то отдельных постановок есть хороший прогресс, но я думаю, что хватит и нам, и будущим поколениям, чтобы совершать новые открытия, разрабатывать новые методы и алгоритмы.
