0.4 Часть 0 · Введение · углубление и основы

Оценка состояния и планирование

В уроке 0.3 регулятор знал точное положение руки, а планировщик — карту стен. У настоящего робота так не бывает: датчики шумят, а карты незнакомого дома нет. Прежде чем вести робота к цели, нужно ответить на два вопроса: где он сейчас и каким путём ехать. Классическая робототехника отвечает на них фильтрами, картами и поиском пути. Пройдём их по порядку, от фильтра Калмана до RRT, и найдём, где каждый метод надёжен, а где перестаёт работать. Если тема знакома, урок можно пропустить.

Ада — домашний гуманоидный робот, на котором построены лабораторные работы курса. Подробнее о ней — в уроке 0.1.

≈ 50 минут5 лабораторий и 4 интерактива17 миссий с цельюформулы — в блоках «Под капотом»

КАЛМАНГде Ада в коридоре: подбери шумы фильтра, чтобы ошибка была меньше 4 см, а полоса неуверенности — откалиброванной

ЧАСТИЦЫВ какой комнате Ада: найди место, где фильтр путает две спальни, и реши задачу похищенного робота

КАРТАОткуда взять карту: посмотри, как увод одометрии закрывает на карте дверь в кухню, и исправь карту

ПУТЬКаким путём ехать: заставь A* раскрыть больше 150 клеток и найди узкий проход, где RRT работает медленно

Начать урок ↓

1 Два вопроса

Где Ада и куда ехать

Чтобы вести робота к цели, регулятору нужны два ответа: где робот сейчас и каким путём ехать. В классическом стеке из урока 0.1 их дают два модуля между восприятием и управлением.

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

Планирование отвечает на вопрос «каким путём ехать». По карте строят граф или выборку точек и ищут в нём путь, который не задевает препятствий и по возможности короче.

Синим — классические модули. В этом уроке все методы классические, а в конце урока посмотрим, где их сегодня заменяют или подстраховывают нейросети.

Начнём с оценки состояния в самом простом случае: Ада едет по прямому коридору. Как узнать, где она, если каждый датчик ошибается по-своему?

🔬 Лаборатория 1

Шумный датчик и фильтр Калмана

Ада ездит по коридору к стене и обратно, и у неё два неточных датчика. Колёса считают обороты: на коротком отрезке это точно, но ошибка копится, а на ковре колёса проскальзывают. Дальномер меряет расстояние до стены 10 раз в секунду: ошибка не копится, зато каждый замер гуляет примерно на 10 см.

В уроке 0.2 похожую пару — гироскоп, который копит дрейф, и шумный акселерометр — мы склеивали комплементарным фильтром. Он каждый шаг сдвигает оценку к замеру на постоянную долю $1 - \alpha$ . Вес $\alpha$ подбирают вручную, и он один на все случаи: и на старте, когда оценка ещё грубая, и после того, как датчик замолчал.

Фильтр Калмана сам решает, насколько верить замеру. Вес он считает по шумам датчиков и по тому, насколько уверен в своей оценке сейчас.

Три Ады едут рядом с одними и теми же датчиками. Первая верит только дальномеру, вторая — комплементарному фильтру с тем же $\alpha = 0{,}98$ , третья — фильтру Калмана.

По горизонтали — время, с. По вертикали — ошибка оценки положения, см.

σ модели1 см σ дальномера10 см α комплем.0,98 ковёр дальномер молчит 3 с

Фильтр Калмана хранит два числа: оценку положения и её дисперсию P — насколько он не уверен. Каждый шаг делится на два. Предсказание: сдвигаем оценку на показания колёс, неуверенность растёт на $Q$ . Коррекция: сравниваем оценку с замером и сдвигаемся к нему на долю $K = P/(P + R)$ . Шумный датчик (большое $R$ ) двигает оценку слабо, неуверенный фильтр (большое $P$ ) — сильно. $Q$ и $R$ задаёт инженер, $K$ фильтр считает сам.

Так работают настоящие роботы. У шагающих роботов MIT фильтр Калмана оценивает положение и скорость корпуса по IMU и углам ног 500–1000 раз в секунду. Автопилот дронов PX4 по умолчанию делает предсказание расширенного фильтра Калмана 100 раз в секунду и вливает в него GPS, барометр, магнитометр и другие датчики, когда приходят их замеры.

Под капотом: формулы, комплементарный фильтр и нелинейные версии

Предсказание:

x^- = x + u\,\Delta t, \qquad P^- = P + Q.

Коррекция:

\begin{aligned} K &= \frac{P^-}{P^- + R}, \\ x &= x^- + K\,(z - x^-), \\ P &= (1 - K)\,P^-. \end{aligned}

$u$ — скорость по колёсам, $z$ — замер дальномера, $\Delta t = 0{,}1$ с. Ручки задают не дисперсии, а $\sigma$ : $Q$ — квадрат $\sigma$ модели, $R$ — квадрат $\sigma$ дальномера. Пока замеров нет, фильтр делает только предсказание, и $P$ растёт на $Q$ каждый шаг.

В лаборатории колёса завышают скорость на 4 % и шумят с $\sigma = 6$ см/с, на ковре (от 2,5 до 3,5 м) завышают ещё на 30 %. Шум дальномера — 10 см. Все три оценки стартуют с первого замера дальномера, Калман — с $P = R$ . Случайность задана зерном, поэтому каждый запуск повторяется в точности.

Комплементарный фильтр — частный случай. Его формула $x = \alpha\,(x + u\,\Delta t) + (1 - \alpha)\,z$ совпадает с шагом Калмана, если взять постоянное $K = 1 - \alpha$ . Калман отличается тем, что считает $K$ сам по $Q$ , $R$ и текущей неуверенности, поэтому быстро сходится в начале и после провала замеров. В установившемся режиме $K$ перестаёт меняться, и Калман работает как комплементарный фильтр с лучшим для этих шумов $\alpha$ .

Многомерный случай. Состояние — вектор (например, положение и скорость), $P$ и $Q$ — матрицы ковариаций, модель — матрицы $A$ и $H$ :

\begin{aligned} x^- &= A x + B u, \\ P^- &= A P A^{\mathsf T} + Q, \\ K &= P^- H^{\mathsf T} \bigl(H P^- H^{\mathsf T} + R\bigr)^{-1}. \end{aligned}

Фильтр оптимален для линейной модели с гауссовым шумом. Для нелинейных моделей есть расширенный фильтр (EKF): он линеаризует модель якобианом в текущей оценке. Сигма-точечный фильтр (UKF) прогоняет через нелинейность несколько специально выбранных точек и обходится без якобианов.

Калман ошибается в среднем на 3,2 см, комплементарный фильтр — на 7,5 см, дальномер — на 10 см. Калман сам выбирает вес замера и показывает свою неуверенность: пока замеров нет, полоса растёт. Но шумы Q и R задаёт инженер, и Q приходится брать с запасом.

Пока Ада примерно знает, где она, одной оценки с полосой неуверенности хватает. А если она включилась и не знает даже, в какой из двух одинаковых спален стоит?

🔬 Лаборатория 2

Где Ада: фильтр частиц

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

Почему Калман не справится? Он держит одну гипотезу — колокол вокруг одного места. Ему пришлось бы выбрать одну спальню и уверенно ошибаться.

Фильтр частиц хранит сотни гипотез сразу. Каждая частица — «Ада здесь и смотрит туда». Шаг фильтра: сдвинуть все частицы по одометрии, для каждой сравнить ожидаемый скан лидара с настоящим, размножить похожие и убрать непохожие.

Карта дома у Ады есть, лидар — 24 луча на 2,5 м. Две спальни слева нарочно одинаковые. Посмотрим, как фильтр находит Аду, где путается и что будет, если Аду незаметно перенести.

подмешивать случайные частицы, когда скан перестал совпадать с картой Частиц600

Под капотом: Monte Carlo localization

Фильтр частиц для локализации называют Monte Carlo localization (MCL). Один шаг:

для каждой частицы

i

сдвинуть по одометрии с шумом:

x_i \leftarrow \text{движение}(x_i, u) + \text{шум}

взвесить по скану:

w_i \leftarrow p(z \mid x_i, \text{карта})

нормировать веса; если частиц с заметным весом меньше половины:

пересэмплировать — новые частицы выбираются с вероятностью

w_i

Правдоподобие скана. Для частицы считаем, какие расстояния увидели бы 24 луча, если бы Ада стояла там. Расхождение по каждому лучу оцениваем гауссом с $\sigma = 25$ см плюс 20 % равномерной добавки на случай чужих предметов, лучи считаем независимыми. Произведение по лучам слишком резкое, поэтому его логарифм умножаем на 0,35 — обычный приём, чтобы фильтр не становился уверенным слишком рано. Частицы внутри стен получают нулевой вес.

Шум движения — 10 % от пути плюс 0,6 см и 10 % от поворота плюс 2° за шаг (0,25 с). Пересэмплирование — с низкой дисперсией: одна случайная точка и равный шаг по сумме весов.

Подмешивание случайных частиц (Augmented MCL из книги «Probabilistic Robotics»). Фильтр следит за средним правдоподобием скана двумя скользящими средними: быстрым (коэффициент 0,5) и медленным (0,05). Если быстрое упало ниже медленного, скан вдруг перестал совпадать с ожиданием, и доля случайных частиц $\max(0,\ 1 - \text{быстрое}/\text{медленное})$ , но не больше половины, разбрасывается по свободному месту дома. Пока всё совпадает, случайных частиц нет.

Число частиц тоже можно менять на лету: KLD-sampling берёт много частиц, пока облако широкое, и мало, когда оно собралось. При глобальной локализации ему хватало около 3000 частиц там, где фильтру с постоянным числом нужно было 50 000. В первой работе о MCL (Dellaert и др., 1999) для глобальной локализации брали 20 000 частиц, для слежения — 5000, и робот за 75 минут проехал по Смитсоновскому музею больше 2,2 км, ни разу не потеряв себя. В навигационном стеке ROS 2 (Nav2) локализацию по умолчанию делает такой же адаптивный фильтр частиц, AMCL.

Фильтр частиц держит обе спальни сразу и выбирает верную, когда лидар заглядывает в дверь. Пока Ада стоит, одинаковые места не различить: помогает только движение. После похищения фильтр спасают случайные частицы: без них через 10 с ошибка 2,7 м, с ними Ада найдена за 1,25 с.

Всё это время у фильтра была готовая карта дома: с ней он сравнивал каждый скан. Откуда взять карту, если Ада попала в дом впервые?

🔬 Лаборатория 3

Карта по лидару и SLAM

Ада впервые в доме, и карты у неё нет. Без карты фильтру частиц не с чем сравнивать скан.

Значит, карту надо построить лидаром. Ада объезжает дом и отмечает лучи: вдоль луча пусто, в конце — препятствие. Так получается сетка занятости: клетки по 5 см, каждая хранит, насколько она похожа на стену.

Почему это трудно? Чтобы нанести луч на карту, надо знать, откуда Ада смотрела. А чтобы знать, где Ада, нужна карта. Делать оба дела сразу — задача SLAM, одновременной локализации и построения карты.

Сначала дадим построению настоящую позу Ады, потом позу по колёсам, а потом научим Аду поправлять позу по самой карте.

Увод курса1°/м сопоставлять скан с картой

Под капотом: лог-шансы, сопоставление сканов и замыкание петель

Сетка занятости. Клетка хранит лог-шансы $l = \ln\dfrac{p}{1 - p}$ : 0 — «не знаю», плюс — «скорее стена», минус — «скорее пусто». Каждый луч добавляет −0,4 всем клеткам, через которые прошёл, и +0,85 клетке, где упёрся в препятствие. Значения ограничены ±4. Сложение лог-шансов — тот же байесовский апдейт, что в фильтрах, только для каждой клетки отдельно и в предположении, что клетки независимы.

Лидар и одометрия. 90 лучей на 3,5 м с шумом 1,5 см, 4 скана в секунду, Ада едет 0,5 м/с по маршруту длиной 27 м через все комнаты. Одометрия завышает путь на 1 %, шумит и уводит курс на заданное число градусов на метр пути.

Сопоставление скана с картой. Предсказываем позу по одометрии, потом перебираем сдвиги до ±12 см и повороты до ±6° и выбираем позу, при которой концы лучей сильнее всего попадают в уже известные стены. Сначала грубо, с шагом 4 см и 2°, потом точнее. Карта для сравнения слегка размыта, чтобы оценка менялась плавно. Это простой SLAM: он не даёт ошибке копиться, пока Ада видит знакомые стены.

Чего здесь нет. В большом здании маленькая ошибка всё равно копится. Когда робот возвращается в знакомое место, настоящий SLAM замечает это (замыкание петли) и поправляет всю траекторию сразу: позы — вершины графа, сопоставления — рёбра-пружины, оптимизация растягивает граф. Так работают, например, Cartographer для лидаров и ORB-SLAM для камер.

С точной позой карта чистая. Одометрия, которая уводит курс всего на 1° за метр, раздваивает стены и закрывает на карте дверь в кухню. Если прикладывать каждый скан к уже построенной карте, ошибка позы не копится, и по карте снова можно проехать.

Теперь у Ады есть карта, и она знает, где стоит. Каким путём ехать из спальни в кухню?

🔬 Лаборатория 4

Дейкстра и A* на одной карте

Нужен путь из спальни в кухню: кратчайший и такой, чтобы не задеть стен и мебели.

Путь ищут по графу. Сетка из клеток по 20 см — это граф: соседние свободные клетки связаны рёбрами длиной 1 по прямой и $\sqrt{2}$ по диагонали. Алгоритм Дейкстры раскрывает клетки по возрастанию пройденного пути $g$ , волной во все стороны. A* раскрывает их по $g + h$ , где $h$ — расстояние до цели без учёта стен.

Слева Дейкстра, справа A*, задача одна: из верхней спальни в кухню.

Дейкстрараскрывает по пройденному пути g

A*раскрывает по

g + h

Вес эвристики ε1,0

Под капотом: почему A* находит кратчайший путь

открытый список

\leftarrow \{\text{старт}\}

g(\text{старт}) = 0

пока список не пуст:

взять вершину

v

с наименьшим

f = g(v) + \varepsilon\, h(v)

если

v

— цель: путь найден

для каждого соседа

u

: если

g(v) + \text{длина}(v, u) < g(u)

— обновить

g(u)

, запомнить родителя

При $\varepsilon = 0$ это алгоритм Дейкстры. Эвристика $h$ допустимая, если никогда не переоценивает оставшийся путь. Тогда A* находит кратчайший путь. Если вдобавок $h$ монотонна ( $h(v) \le \text{длина}(v, u) + h(u)$ ), каждая вершина раскрывается не больше одного раза. В лаборатории $h$ — расстояние по сетке без стен с диагоналями $\sqrt{2}$ : оно допустимое и монотонное. Ходить по диагонали мимо угла стены нельзя. При равных $f$ первой раскрывается вершина с большим $g$ — так A* реже переключается между равноценными клетками.

При $\varepsilon > 1$ эвристика уже переоценивает путь, и гарантия слабеет: путь получается длиннее кратчайшего не более чем в $\varepsilon$ раз, зато раскрытых вершин обычно меньше. Это взвешенный A*.

С двоичной кучей Дейкстра работает за $O(E \log V)$ , где $V$ — число вершин, $E$ — число рёбер. A* в худшем случае не лучше: если эвристика ничего не подсказывает (ловушки, тупики), он раскрывает почти всё.

На открытой карте A* раскрывает 24 клетки вместо 314 у Дейкстры, а путь находит тот же. В ловушке эвристика заводит его в тупик, и выигрыш сжимается до двух раз: 160 клеток против 332. Взвешенный A* раскрывает меньше, но его путь может быть длиннее кратчайшего.

Сетка хорошо подходит Аде на колёсах: у неё всего два-три измерения. Годится ли сетка для руки, у которой шесть-семь суставов?

2 Размерность

Почему сетка не годится для руки

Для руки сетку строят не по полу, а по углам суставов. Для планировщика робот — точка в пространстве конфигураций: у Ады на колёсах это x, y и курс, у руки из урока 0.3 — два угла. На главной странице есть интерактив, где A* ищет путь такой руки по сетке 96 × 96 на плоскости двух углов.

У настоящей руки 6–7 суставов, и каждый добавляет сетке ещё одну ось. Посчитай, сколько клеток будет у сетки тогда.

Степеней свободы2 Клеток на ось50

Логарифмическая шкала: каждое деление — в 1000 раз больше предыдущего.

Каждый новый сустав умножает число клеток во столько раз, сколько клеток на оси: при 50 клетках на ось — в 50 раз. Учебник Lynch и Park «Modern Robotics» прямо пишет, что сеточные методы годятся только для пространств малой размерности: при 100 клетках на ось у руки с семью суставами 10¹⁴ клеток.

Выход — не покрывать всё пространство клетками, а бросать в него случайные точки и соединять те, между которыми можно проехать. Так работают планировщики на случайных выборках. PRM (вероятностная дорожная карта, 1996) строит такой граф заранее для многих запросов. RRT (1998) растит дерево от старта под один запрос.

Случайные точки покрывают пространство не целиком. Найдёт ли случайное дерево путь и насколько коротким он будет?

🔬 Лаборатория 5

RRT и RRT*: случайные деревья

На сетке A* с допустимой эвристикой гарантированно находит кратчайший путь. У случайного дерева таких гарантий нет: заранее неясно, найдёт ли оно путь, за сколько итераций и насколько коротким он будет.

RRT растит дерево от старта: берёт случайную точку, находит ближайшую вершину дерева и делает к точке шаг в 30 см, если по дороге нет препятствия. Каждая двадцатая точка — сама цель. RRT* делает то же, но новой вершине выбирает лучшего родителя среди соседей и перепривязывает соседей, если через новую вершину им короче.

Чтобы деревья было видно, растим их на плане гостиной, а не в пространстве углов руки: алгоритм там тот же. Оба дерева получают одни и те же случайные точки. Гостиную делит перегородка из двух сдвижных створок.

RRTшаг к случайной точке

RRT*плюс выбор родителя и перепривязка

По горизонтали — итерации. По вертикали — длина лучшего найденного пути, м.

Под капотом: RRT, RRT* и что значит «вероятностно полный»

RRT:

x_{\text{rand}} \leftarrow

случайная точка (с вероятностью 5 % — цель)

x_{\text{near}} \leftarrow

ближайшая вершина дерева

x_{\text{new}} \leftarrow

шаг 30 см от

x_{\text{near}}

x_{\text{rand}}

если отрезок

x_{\text{near}} \to x_{\text{new}}

свободен: добавить

x_{\text{new}}

с родителем

x_{\text{near}}

RRT*: то же, но

родитель

x_{\text{new}}

— сосед с наименьшей длиной пути до

x_{\text{new}}

;

соседям, которым через

x_{\text{new}}

короче, родителем становится

x_{\text{new}}

Соседи — вершины в радиусе $r = \min\bigl(75\ \text{см},\ \gamma\sqrt{\ln n / n}\bigr)$ , где $n$ — число вершин. Так радиус убывает в работе Karaman и Frazzoli (2011): на плоскости по закону $\sqrt{\ln n / n}$ , в пространстве размерности $d$ — как $(\ln n / n)^{1/d}$ . С таким радиусом RRT* асимптотически оптимален, а соседей у новой вершины остаётся немного. В лаборатории $\gamma = 650$ см. Ада — точка, препятствия раздуты на её радиус 15 см.

Свойства. RRT вероятностно полон: если путь существует, вероятность найти его стремится к единице с ростом числа итераций. Сколько итераций понадобится, не гарантируется: в узком проходе — очень много. RRT почти наверняка сходится к неоптимальному пути. RRT* асимптотически оптимален: длина его пути стремится к кратчайшей. Вершины у них одинаковые, а поиск соседей и перепривязка, как показали Karaman и Frazzoli, делают RRT* дороже RRT лишь на постоянный множитель.

Деревья с двух сторон, RRT-Connect, — планировщик по умолчанию в MoveIt, библиотеке планирования движений манипуляторов для ROS: она берёт его из библиотеки OMPL. Для мобильных роботов чаще хватает сетки: в Nav2 путь по умолчанию ищет волновой алгоритм Дейкстры.

Узкие проходы — известная слабость случайных выборок: точка попадает в проход с вероятностью, равной доле его площади. Помогают выборка у самых препятствий (Gaussian sampling: из двух близких точек берут свободную, если вторая задела препятствие), «мостик» (bridge test: обе точки в препятствиях, а середина между ними свободна — это и есть проход) и деревья с двух сторон, RRT-Connect. Короткий путь в лаборатории для сравнения считается точно — по графу видимости между углами препятствий.

Оба дерева находят первый путь на одной и той же итерации. Если растить их дальше, RRT* выпрямляет путь почти до кратчайшего, а путь RRT так и остаётся на 18 % длиннее. В узком проходе первого пути приходится ждать долго: случайная точка попадает в проход редко.

Все методы урока опираются на модели, которые написал человек: шумы датчиков, карту, форму препятствий. Где такие модели перестают работать и что тогда делают?

3 Классика рядом с нейросетями

Как эти методы живут сегодня

Модели, написанные человеком, работают в известном, неизменном мире. Там фильтры и планировщики дают гарантии, оценку неуверенности и объяснимые ошибки. В открытом мире такие модели не напишешь: какой пол мокрый, формулой не задать.

Классику редко выбрасывают целиком. Обучаемые части встраивают в неё или ставят рядом. Выбери систему и посмотри, что в ней учится, а что осталось классикой.

🧩 Задача

Какой метод для какой задачи

Разложи задачи по методам: перетащи карточку или нажми её, а потом корзину. Последняя корзина — для задач, где классический модуль не написать и нужна обученная модель.

4 Проверь себя

Восемь вопросов о типичных заблуждениях

5 Итог

Итоги урока

Робот хранит не точку, а распределение, и обновляет его в цикле «предсказание по модели → коррекция по замеру».
Фильтр Калмана сам выбирает вес замера по шумам Q и R. Q прячет всё, чего модель не знает, поэтому его подбирают с запасом и проверяют, откалибрована ли полоса неуверенности.
Фильтр частиц держит много гипотез и переживает неоднозначность. После похищения его спасают только случайные частицы.
Карта и поза зависят друг от друга. Без коррекции позы стены раздваиваются — поэтому SLAM.
A* с допустимой эвристикой находит кратчайший путь и обычно раскрывает меньше Дейкстры, но в ловушках почти столько же.
В многомерных пространствах сетка не помещается в память, и работают случайные выборки: RRT находит путь, RRT* со временем его выпрямляет. Узкие проходы для них трудны.
Классика опирается на модели, которые пишет человек. Где мир так не описать, её дополняют обученными моделями.

Открытые вопросы

Почему в дронах и автомобилях положение до сих пор оценивает фильтр Калмана, хотя нейросети лучше видят?

Фильтру нужно мало вычислений, он работает с частотой датчиков и выдаёт оценку вместе с её неуверенностью, которую понимают остальные модули. Его ошибки объяснимы, а поведение при отказе датчика предсказуемо. Нейросети чаще ставят на вход фильтра: они дают замеры или их неуверенность, например оценивают смещение по IMU, а склеивает всё фильтр.

В квартире каждый день переставляют стулья. Что первым перестанет работать в классическом стеке и чем это подстраховать?

Карта: на ней появятся стулья, которых уже нет, а новых не будет. Локализацию это почти не задевает, пока видны стены, — лишние препятствия фильтр частиц переживает за счёт равномерной добавки в модели скана. Планировщик будет объезжать призраков. Помогают забывание старых наблюдений на карте, отдельный слой для подвижных объектов и частое перепланирование по свежему скану.

Почему пылесосу хватает A* по сетке, а для руки с семью суставами берут RRT?

У пылесоса пространство конфигураций двух- или трёхмерное: сетка в тысячи клеток считается мгновенно. У руки семь измерений: даже при 50 клетках на ось сетка — почти $10^{12}$ клеток. Случайные деревья не покрывают пространство целиком, а исследуют его выборкой, поэтому их стоимость почти не зависит от размерности напрямую.

Гид по источникам

S. Thrun, W. Burgard, D. Fox, «Probabilistic Robotics», MIT Press, 2005.

Читать внимательноГлавы 2–4: байесовский фильтр, фильтры Калмана (с EKF и UKF) и частиц. Глава 8: локализация методом Монте-Карло, Augmented MCL — таблица 8.3. Глава 9: сетка занятости.
Можно пропуститьГлавы 11–16: GraphSLAM, разреженные информационные фильтры, POMDP. К ним стоит вернуться, когда понадобится SLAM в больших зданиях или планирование с неопределённостью.
Вопрос по ходуПочему модель скана в MCL делают нарочно грубее, чем настоящий лидар?

S. LaValle, «Rapidly-Exploring Random Trees: A New Tool for Path Planning», технический отчёт 98-11, Iowa State University, 1998.

Читать внимательноСам алгоритм и картинку, как дерево растёт в неисследованные области.
Вопрос по ходуПочему вершины на краю дерева расширяются чаще, чем в середине?

Материалы

How a Kalman filter works, in picturesT. Babb — фильтр Калмана на картинках, без тяжёлой математики. Перевод на Хабре
Kalman and Bayesian Filters in PythonR. Labbe — бесплатная книга в тетрадках Jupyter, от g-h-фильтра до UKF и фильтра частиц
Introduction to the A* AlgorithmRed Blob Games — интерактивное объяснение поиска на сетке: волна, Дейкстра, жадный поиск, A*
Planning AlgorithmsS. LaValle, 2006 — бесплатная книга о планировании, в том числе о случайных выборках
SLAM CourseC. Stachniss — лекции о фильтрах, сетках занятости и SLAM на YouTube
Мобильные роботыК. Кринкин, CS-клуб ПОМИ, 2019 — курс по SLAM на русском
PythonRoboticsКороткие реализации фильтров, SLAM и планировщиков на Python

➡️

Дальше: учимся по примерам. Классика сильна в известном мире, где шум, карту и препятствия можно описать. В открытом мире правила не пишутся: что такое «мокрый пол» или «сложенная футболка», формулой не задать. Если правило не написать, нужное поведение можно показать: оператор проводит робота, а сеть учится повторять. С этого начинается основной путь курса — урок 1.1 «Behavior Cloning».

Урок пригодился? Скажи спасибо — так автор узнает, что курс читают.