Планирование пути и построение карт: от заливки до SLAM
Вы сможете строить маршрут по известной сетке, перепланировать его при появлении новых препятствий и объяснять, как робот создаёт карту, по которой планирует.
Реактивная навигация позволяет роботу объезжать помещение, не зная своего положения. Возможности быстро заканчиваются: реактивному роботу нельзя сказать иди на кухню, и он будет бесконечно кружить в комнате в форме подковы. Ответом служит планирование, которому нужно то, чего никогда не бывает при реактивном управлении: карта.
Этот путь начинается там, где карта уже имеется. В лабиринте заливка распространяет расстояния от цели наружу, и робот просто движется в сторону уменьшения значения поля расстояний, перепланируя в тот момент, когда обнаруживает стену вместо предполагаемого прохода. Затем мир становится сложнее: A* планирует по сетке занятости, где ячейки имеют стоимость, препятствия необходимо расширять, а эвристика определяет, будет ваш планировщик быстрым или лишь корректным.
Последний узел — честный. Каждый из предыдущих планировщиков предполагает, что карта у вас есть, а реальному роботу приходится строить её в движении на колёсах, которые ему лгут. SLAM возникает, когда процессы построения карты и локализации больше нельзя разделить, а замыкание цикла не даёт карте искривляться из-за дрейфа одометрии. Здесь IMU также заслуживает своего места по той же причине: он непосредственно измеряет поворот, которого не могут измерить проскальзывающие колёса.
Прежде чем начать
Вам нужно уверенно работать с двумерными массивами и обладать базовым алгоритмическим мышлением: умением работать с очередями и представлением о порядке посещения ячеек. Путь по управлению двигателями стоит пройти первым, поскольку каждый планировщик здесь предполагает, что робот может выполнить заданное перемещение и примерно сообщить, какой путь он прошёл.
Чему вы сможете научиться
- Залить сетку расстояниями от цели и пройти по убывающему градиенту.
- Запустить A* с эвристикой, для которой можно доказать отсутствие завышения, и объяснить, почему именно это свойство делает результат кратчайшим.
- Преобразовывать измерения дальности в сетку занятости трассировкой лучей, отдельно обновляя свободные и занятые ячейки.
- Объяснить, почему одна одометрия не может создать пригодную карту за долгое время, и что добавляет SLAM.
Где обычно возникают трудности
Эвристика завышает оценку. A* гарантирует кратчайший путь только тогда, когда эвристика никогда не утверждает, что расстояние больше истинной оставшейся стоимости. Использование евклидова расстояния на сетке с 4-связностью или увеличение эвристики ради ускорения поиска молча возвращает некратчайшие пути.
Планирование для точечного робота. Путь вычисляется по сетке, но робот имеет ширину. Маршрут, задевающий угол, геометрически допустим, но физически приводит к столкновению. Расширьте препятствия на радиус робота до планирования, и проблема исчезнет.
Считать неизвестное свободным. Ячейка, которую никто не наблюдал, не пуста — она не измерена. Если планировать через неё как через свободное пространство, робот уверенно поедет во всё, что осталось невидимым. Неизвестное — третье состояние, и оно должно им оставаться.
Диагональный шаг стоимостью в одну ячейку. На сетке с 8-связностью диагональный шаг проходит √2 ячейки, а не одну. Назначение ему стоимости в одну единицу создаёт пути, предпочитающие лестницу, и просто неверные расстояния.
Предположение, что робот находится там, куда указывает одометрия. Каждый планировщик здесь работает с положением и ориентацией. Одометрия колёс дрейфует без ограничения, поэтому безупречный план выполняется из позиции, которая с каждым шагом всё меньше соответствует действительности. Этот разрыв — вся мотивация последнего узла пути.
Что понадобится
| Что | Зачем это нужно пути | Примечания |
|---|---|---|
| Уверенная работа с 2D-массивами и очередями | Каждый алгоритм здесь — цикл по сетке | Сложная математика не нужна: достаточно очереди и вложенного цикла |
| Робот, выполняющий заданные перемещения | План бессмыслен, если робот не может его проехать | Путь по управлению двигателями подготовит вас |
| Гироскоп или инерциальный измерительный модуль (IMU) | Колёса не могут измерить поворот, при котором они проскользнули | MPU-6050; узлы карты зависят от курса |
| Датчик дальности, желательно сканирующий | Ячейки становятся известными только через измерение | Для грубой сетки достаточно ультразвукового датчика, поворачиваемого сервоприводом |
| Место для визуализации сетки | Отлаживать планировщик, наблюдая за роботом, почти невозможно | Выводите ASCII-символы (текстовую графику) через последовательный порт или используйте лабораторные работы пути |
Обе лабораторные работы полностью выполняются в браузере, поэтому узлы заливки и покрытия можно завершить вообще без оборудования.
Почему путь устроен именно так
Сначала лабиринт, потому что карта уже имеется. В лабиринте микромыши мир по построению является сеткой: размер ячеек известен, стены проходят по их границам, а положение робота всегда задаётся индексом ячейки. Это разом устраняет все задачи восприятия и оставляет только планирование, которому вы здесь учитесь. Заливка в известной сетке — самое чистое введение в принцип «вычисли поле расстояний, затем двигайся в сторону уменьшения его значений».
A* идёт вторым, потому что по одному убирает удобства лабиринта. Теперь у ячеек есть стоимость, а не только стены. Сетка больше, поэтому просматривать её целиком невыгодно и эвристика становится полезной. У робота есть ширина, поэтому препятствия необходимо расширять. А ячейки могут быть неизвестными — это действительно новая идея, которой лабиринту не требовалось.
Сетки занятости идут третьими, потому что здесь карта перестаёт быть заданной. Трассировка лучей превращает одно измерение дальности в данные сразу о многих ячейках: всё вдоль луча вероятнее свободно, конечная точка вероятнее занята. Раздельное обновление этих двух состояний и составляет весь метод.
IMU расположен здесь намеренно. Он появляется ровно в узле, где ошибка курса начинает записываться в карту, поскольку гироскоп непосредственно измеряет поворот, которого не могут измерить проскальзывающие колёса.
SLAM завершает путь, поскольку признаёт, что предыдущие узлы предполагали неверное. Каждый планировщик выше работает с положением и ориентацией, а каждое такое положение получено из одометрии, дрейфующей без ограничения. SLAM возникает, когда вы перестаёте считать, что построение карты и локализация можно решать раздельно.
Покрытие замыкает путь, поскольку это задача, которой карта нужна наиболее очевидно и которую наиболее очевидно нельзя решить реактивно. На вопрос «Я побывал везде?» способна ответить только память.
Контрольные точки: как проверить усвоение этапа
| Этап | Проверка | Признак успешного прохождения |
|---|---|---|
| Заливка | Выведите поле расстояний для небольшого лабиринта | Цель имеет значение 0, значения растут наружу, а стены создают ожидаемые обходы |
| Перепланирование | Откройте стену, которую робот считал проходом | Поле обновляется, и следующий ход робота меняется без повторного исследования |
| Корректность A* | Запустите на сетке, ответ для которой известен вручную | Длина каждый раз совпадает с вычисленной вручную кратчайшей |
| Допустимость | Намеренно увеличьте эвристику в 2× | Поиск ускоряется, а путь удлиняется: теперь вы видите компромисс |
| Стоимость диагонали | Планируйте через открытое пространство на сетке с 8-связностью | Путь — прямая диагональ, а не лестница; диагонали стоят √2 |
| Расширение препятствий | Спланируйте проход за углом с выключенным и включённым расширением | Выключено: путь задевает угол; включено: проходит на радиус робота |
| Сетка занятости | Проведите датчиком через дверной проём и отобразите сетку | Вдоль лучей появляется свободное пространство, в концах — занятые ячейки, за стенами — неизвестные |
| Работа с неизвестными | Попросите планировщик провести маршрут в некартографированную область | Он отказывает или сознательно разрешает проход через них; и то и другое допустимо, догадки — нет |
| Дрейф | Проедьте замкнутый контур и сравните начало и конец карты | Карта не замыкается: этот разрыв и устраняет замыкание цикла |
| Покрытие | Выполните плановое покрытие и случайное блуждание за одинаковое время | Плановое покрытие охватывает намного больше, и вы можете назвать оба процента |
Где заканчивается этот путь
Этот путь планирует в статическом, двумерном мире известного размера. Каждое из этих слов обозначает ограничение, которое стоит назвать.
Статическом. Здесь ничего не учитывает человека, пересекающего маршрут. Для динамических препятствий нужен локальный планировщик, работающий совместно с глобальным и перепланирующий намного быстрее, чем A* на всей сетке.
Двумерном. Сетка свободных и занятых ячеек представляет план этажа. Она не может выразить стол, под который можно проехать, но нельзя проехать сквозь, поэтому серьёзные роботы используют 3D-представления или многослойные карты стоимости.
Сеточном. Планировщики по выборкам, такие как RRT и RRT*, работают в пространствах высокой размерности, например в пространстве суставов роботизированной руки, где сетка бесполезна. Они отказываются от гарантии кратчайшего пути ради способности работать вообще.
Путь также не рассматривает фильтры частиц или локализацию Монте-Карло, с помощью которых робот находит себя на предоставленной карте, а не строит её. Это более простая и гораздо более распространённая задача, и стоит знать о ней до перехода к полноценному SLAM.
Дорожная карта обучения
Путь
Проходите узлы по порядку — каждый открывает следующий, когда вы его выполните. Ваш прогресс сохраняется на этом устройстве.
0 / 9 выполнено
Частые вопросы
Часто задаваемые вопросы
Чем заливка отличается от A* при планировании пути робота?
Заливка вычисляет расстояние от цели до каждой ячейки сетки, поэтому затем робот может двигаться в сторону уменьшения значения поля расстояний от любой точки, где оказался. A* ищет от единственного старта к единственной цели и расширяет только те ячейки, которые эвристика считает перспективными. Заливка — верный выбор в лабиринте микромыши (micromouse), потому что робот постоянно обнаруживает новые стены и должен перепланировать с нового положения каждые несколько ячеек: если расстояния до всех ячеек уже вычислены, это бесплатно. A* — верный выбор на большой сетке, где план строится один раз с известного старта и просматривать всю карту невыгодно.
Почему мой путь A* срезает углы препятствий?
Потому что вы планировали для точки, а робот имеет ширину. Геометрически путь допустим на сетке, но физически приводит к столкновению, поскольку планировщик не знал, что робот занимает больше одной ячейки. Стандартное исправление — перед планированием расширить каждое препятствие на радиус робота, сдвинув занятые ячейки наружу, чтобы любой найденный планировщиком путь автоматически был свободен для реального робота. Это намного проще и надёжнее, чем проверять зазоры во время поиска.
Какая эвристика в A* считается допустимой и почему это важно?
Допустимая эвристика никогда не завышает истинную оставшуюся стоимость до цели. Именно это единственное свойство гарантирует, что A* возвращает кратчайший путь: завышение где-либо позволяет поиску закрепиться за маршрутом, который следовало отвергнуть. Типичные способы нарушить это — использовать евклидово расстояние на сетке с 4-связностью, где истинная стоимость равна манхэттенской и всегда не меньше, а также намеренно увеличить эвристику ради ускорения поиска. Второй приём действительно применяется, но отказывается от гарантии кратчайшего пути, и вы должны сознавать этот компромисс.
Нужен ли SLAM роботу для личных проектов?
Только если во время долгой работы в пространстве без предоставленной карты робот должен знать своё положение. Если карту можно задать, для этого достаточно локализации. Если пространство достаточно мало, чтобы дрейф одометрии оставался допустимым: лабиринт, одна комната, несколько минут движения, — SLAM тоже не нужен. Сложность SLAM оправдана, когда оба условия не выполняются одновременно; это реальный порог, а не значок: множество вполне способных роботов вообще никогда не нуждаются в SLAM.
Почему карта по сетке занятости искривляется при движении робота?
Потому что дрейф одометрии записывается в карту. Каждый скан размещается в предполагаемом положении робота, поэтому медленно ушедшая оценка курса записывает прямой коридор в карту как кривую. В построении карты нет ошибки: оно достоверно фиксирует вымышленное положение. Именно это устраняет замыкание цикла: оно распознаёт возвращение робота в ранее посещённое место и корректирует всю траекторию, чтобы два наблюдения согласовывались.
Почему неизвестные ячейки нельзя считать свободным пространством?
Потому что ячейка, которую никто не наблюдал, не измерена, а не пуста, и это различие определяет, врежется ли робот в предметы, которых он никогда не видел. Считайте неизвестное свободным, и планировщик охотно проведёт маршрут через область, которую ни один датчик не покрыл, а мебель обычно находится именно там, поскольку области, скрытые за препятствиями, и области с препятствиями сильно коррелированы. Сохраняйте неизвестное как отдельное третье состояние наряду со свободным и занятым и сознательно решайте, разрешено ли конкретному планировщику проходить через него.