Робототехника
Path Planning
Amazon складской робот Kiva проезжает 20 км в день, планируя маршрут каждые секунды в динамическом складе с сотнями других роботов. Boston Dynamics Atlas делает паркур: прыгает через ящики, backflip - каждое движение спланировано trajectory optimizer за миллисекунды. Tesla FSD планирует 8-секундную траекторию 10 раз в секунду. Path planning - это фундамент любой автономной системы.
- **Amazon Kiva/Proteus** - PRM для multi-robot path planning; centralized roadmap для всего склада; conflict resolution через приоритетную очередь; тысячи маршрутов планируются одновременно
- **Boston Dynamics Atlas** - trajectory optimization (CHOMP/STOMP) + model predictive control; 3D jumping и backflip: 1kHz loop; state estimation через IMU + stereo SLAM
- **Surgical Robots (da Vinci)** - RRT* в joint space + trajectory smoothing; constraints: не двигать быстрее 5mm/sec рядом с тканями; surgeon teleoperation с motion scaling
RRT: Rapidly-exploring Random Trees
Boston Dynamics Spot нужно пройти от точки A до B в офисе с мебелью. Пространство конфигураций (configuration space) 12-мерное (6 ног x 2 сустава). Полный перебор невозможен. RRT (1998, LaValle) - случайное построение дерева исследования пространства, работает в любой размерности.
**RRT**: начинаем с корня (start), итерируем: (1) случайная точка q_rand в C-space, (2) ближайший узел дерева q_near, (3) extend: шаг от q_near к q_rand на расстояние epsilon, если без коллизий - добавить q_new в дерево. Заканчиваем когда q_new близко к goal. **RRT***: asymptotically optimal - со временем улучшает путь до оптимального.
Почему RRT добавляет biased sampling (5% случаев - goal-directed) к случайному исследованию?
PRM: Probabilistic Roadmap Method
RRT строит дерево для одного запроса. Если нужно планировать тысячи путей в одном пространстве (склад с роботами, 3D принтер), выгоднее один раз построить граф (roadmap) и отвечать на запросы быстро. Это идея PRM - метода дорожных карт.
**PRM**: Фаза 1 (Learning): N случайных конфигураций без коллизий -> граф G. Соединить близкие узлы (k-NN или radius r) если соединение без коллизий. Фаза 2 (Query): подключить start/goal к графу, найти путь через Dijkstra/A*. Отлично для **multi-query** сред. Недостаток: плохо работает в узких проходах (narrow passages).
Когда PRM предпочтительнее RRT?
Potential Fields
Простой робот-пылесос Roomba не использует SLAM и RRT. Он следует простому правилу: двигаться к цели (притяжение) и уходить от препятствий (отталкивание). Это метод потенциальных полей - простой и быстрый, но с известной проблемой локальных минимумов.
**Potential Field Method**: суммарный потенциал U(q) = U_att(q) + U_rep(q). Притяжение к цели: U_att = 0.5 * k_att * ||q - q_goal||^2. Отталкивание от препятствий: U_rep = 0.5 * k_rep * (1/d - 1/d_0)^2 если d < d_0, иначе 0. Движение вдоль антиградиента: dq/dt = -grad(U). Быстро вычисляется, работает в реальном времени.
В чём главный недостаток метода потенциальных полей и как его преодолеть?
Motion Planning в практике
Реальные системы не используют один алгоритм. MoveIt (ROS) - стандартный planning framework: выбор алгоритма (OMPL: RRT, RRT*, PRM, STOMP), collision detection (FCL), trajectory execution. Tesla FSD совмещает cost-function optimization с learned прогнозом траектории.
**Trajectory Optimization**: вместо geometric path находят trajectory с динамическими ограничениями. **CHOMP** (Covariant Hamiltonian Optimization for Motion Planning): optimize коефициенты trajectory (waypoints) минимизируя jerk + collision cost. **STOMP** (Stochastic Trajectory Optimization): случайные возмущения + rollouts. Используется для smooth motion роботов-манипуляторов.
Для navigation мобильного робота достаточно A* на grid-карте
A* на grid работает для 2D holonomic robots (Roomba). Для non-holonomic (автомобиль, который не может ехать боком), high-DOF манипуляторов, динамических сред нужны: kinodynamic planning (RRT с учётом динамики), trajectory optimization (CHOMP), reactive control (DWA, MPC).
Grid A* игнорирует: кинематические ограничения (автомобиль не может повернуть на месте), динамику (нельзя мгновенно остановиться), неопределённость (позиция робота неточная). Для UR5 (6DOF) A* на 6D grid 10^6 ячеек/измерение = 10^36 состояний - вычислительно невозможно.
Зачем нужна trajectory parametrization после нахождения geometric path алгоритмом RRT?
Ключевые идеи
- **RRT**: случайное дерево исследования C-space; biased sampling 5% к goal; работает в высоких размерностях; RRT* asymptotically optimal
- **PRM**: roadmap строится один раз для multi-query; random sampling + k-NN + collision check + Dijkstra; слаб в узких проходах
- **Potential Fields**: притяжение к цели + отталкивание от препятствий; real-time реакция; проблема локальных минимумов
- **Production stack**: RRT/PRM для geometric path + time-optimal trajectory parametrization + local planner (DWA/MPC) для execution
Связанные темы
Path planning строится на карте из SLAM и решает задачу перемещения:
- SLAM — Карта из SLAM - C-space для планировщика; без карты нет пространства для планирования
- Управление (Control) — После планирования пути нужен controller для следования траектории (PID, MPC)
Вопросы для размышления
- Amazon склад: 500 роботов Kiva в одном пространстве. Каждый планирует маршрут независимо через PRM, но пути пересекаются. Как решить конфликты - centralised vs decentralised подход и trade-offs?
- RRT находит путь, но не оптимальный. Как RRT* улучшает найденный путь со временем - что именно происходит в each iteration по сравнению с обычным RRT?
- Tesla FSD планирует траекторию 10 раз в секунду с горизонтом 8 секунд. Среда динамическая (другие машины, пешеходы движутся). Почему простой RRT недостаточен и что использует Tesla вместо него?