Почему RRT иногда не находит путь там, где A* находит?

Узкие коридоры требуют, чтобы случайная точка попала **внутрь** щели до того, как дерево «войдёт»; при малом бюджете итераций или большом шаге вероятность мала. Уменьшите **шаг**, увеличьте **max nodes** или **bias** к цели, когда дерево уже близко — та же «узкая проходная» проблема, из-за которой придумали **RRT*** и **Informed RRT**.

Оптимален ли жёлтый путь RRT?

Нет — базовый RRT возвращает **любой** допустимый геометрический путь. **A*** на решётке оптимален **для этой дискретной модели**, но не может свободно резать клетки, поэтому стоимости напрямую не сравнимы.

Как устроена проверка столкновений?

Отрезок дискретизуется с шагом меньше клетки; каждая точка отображается в клетку по **floor**; попадание в **стену** отклоняет ребро. Это быстрый учебный тест, а не движок с «раздутыми» препятствиями.

Обновляется ли A* при переносе S/G?

Кнопка считает **текущее** состояние карты и концов. После перемещения маркеров нажмите **Compare A*** снова.

Планировщик RRT (сетка)

Та же карта стен 40×28: случайные образцы, ближайший узел, шаг с проверкой столкновений, смещение выборки к цели; кнопка сравнения с A* (Манхэттен, 4-связность).

Планировщик RRT

Инструмент

Шаг steer (клетки)0.85

Смещение выборки к цели0.08

Радиус захвата цели0.42

Макс. узлов дерева4500

Итераций RRT за кадр220

Seed выборки1

Пресет карты

Размер дерева1

Цель достигнутанет

Длина пути RRT—cells

A* (4-связность, та же карта)—

RRT исследует случайные направления; A* на тех же стенах минимизирует суммарную стоимость по клеткам (×5 на «дорогих» клетках, если они есть в сетке — здесь по умолчанию только стены).

Горячие клавиши

Клик: стена / ластик; Move S / G — перенос концов.
Compare A* — Манхэттен A* на той же карте; полный набор эвристик — на странице **engineering/astar-dijkstra-grid**.

Измеренные величины

Ростнет

О модели

Страница строит учебный RRT (быстро исследующее случайное дерево) на той же сетке стен 40×28, что и engineering/astar-dijkstra-grid, но с непрерывными координатами узлов в «клеточных» единицах — путь может срезать углы между узлами решётки. На каждой итерации берётся случайная свободная точка (с смещением выборки к цели), ищется ближайший узел дерева, делается шаг ограниченной длины вдоль хорды, и рёбро принимается только если плотная проверка отрезка не пересекает клетки-стены. Новая вершина внутри радиуса захвата цели вокруг центра G завершает поиск; жёлтая линия — обратный проход по родителям к S. RRT вероятностно полон, но не оптимален: длина пути часто больше, чем у дискретного **A* с манхэттенской эвристикой на тех же стенах; кнопка Compare A* запускает такой A* (4-соседство, дорогие клетки ×5, если они есть в сетке). Настройте шаг, bias и итерации за кадр**, чтобы увидеть компромисс между зондированием пространства и проходом в узких коридорах.

Для кого: Студенты, уже поигравшиеся с A* на сетке и желающие увидеть сэмплинговое планирование до RRT*, PRM и кинодинамических версий.

Ключевые понятия

RRT
Сэмплинговое планирование
Ближайший сосед
Функция шага (steer)
Проверка столкновений
Вероятностная полнота
Смещение к цели
Препятствия на сетке

Как это работает

RRT: случайная точка → ближайший узел дерева → шаг к ней с проверкой стен сетки; bias к цели ускоряет конец; A* на той же карте — дискретный ориентир стоимости и числа раскрытий.

Часто задаваемые вопросы

Почему RRT иногда не находит путь там, где A* находит?: Узкие коридоры требуют, чтобы случайная точка попала внутрь щели до того, как дерево «войдёт»; при малом бюджете итераций или большом шаге вероятность мала. Уменьшите шаг, увеличьте max nodes или bias к цели, когда дерево уже близко — та же «узкая проходная» проблема, из-за которой придумали RRT* и Informed RRT.
Оптимален ли жёлтый путь RRT?: Нет — базовый RRT возвращает любой допустимый геометрический путь. A* на решётке оптимален для этой дискретной модели, но не может свободно резать клетки, поэтому стоимости напрямую не сравнимы.
Как устроена проверка столкновений?: Отрезок дискретизуется с шагом меньше клетки; каждая точка отображается в клетку по floor; попадание в стену отклоняет ребро. Это быстрый учебный тест, а не движок с «раздутыми» препятствиями.
Обновляется ли A* при переносе S/G?: Кнопка считает текущее состояние карты и концов. После перемещения маркеров нажмите Compare A* снова.

Другие симуляторы в этой категории — или все 48.

Вся категория →

НовоеШкольные

Одометрия дифференциального привода

Запустить симулятор

ω_L, ω_R → v, ω по кинематике двух колёс; интегрирование позы и рост ошибки мёртвой привязки из-за смещения радиусов/колеи и шума измерений скоростей вращения.

НовоеУниверситет / научные

MPC голономного ховеркрафта (2D, MPPI)

Запустить симулятор

Плоский двойной интегратор с ограничением ‖u‖₂: сэмплинговый MPPI ведёт к перетаскиваемой цели и мягко штрафует круговые препятствия — веер rollout и лучший прогноз пути на канве.

НовоеУниверситет / научные

3-Link 3D Arm Inverse Kinematics (CCD)

Запустить симулятор

Continuation of two-link-arm-ik into 3D: 3 revolute joints (yaw + 2 pitches) solved with constrained Cyclic Coordinate Descent. Drag target in 3D or follow a helix / lemniscate / figure-8 trajectory.

НовоеУниверситет / научные

Bicycle Model & Stanley Controller

Запустить симулятор

Kinematic bicycle (rear-axle): δ = θ_e + atan2(k_e·e, v) Stanley path-following law. Pick oval, race-track, lemniscate, sine-road or S-curve and tune k_e, v, L; live cross-track e(t) and steering δ(t).

НовоеШкольные

Диаграмма напряжение–деформация и закон Гука

Запустить симулятор

Качественная кривая σ–ε: упругая область Гука, текучесть, упрочнение, образование шейки и разрушение. Изменяйте деформацию и настраивайте E, σ_y, σ_u.

НовоеШкольные

Квадрокоптер 2D (Тангаж)

Запустить симулятор

Вид сбоку: два ротора, ПД-регулятор на разности тяги и тангаже — срез квадрокоптера на доске.

Планировщик RRT (сетка)

О модели

Как это работает

Часто задаваемые вопросы

Ещё из «Инженерия»

Одометрия дифференциального привода

MPC голономного ховеркрафта (2D, MPPI)

3-Link 3D Arm Inverse Kinematics (CCD)

Bicycle Model & Stanley Controller

Диаграмма напряжение–деформация и закон Гука

Квадрокоптер 2D (Тангаж)

Планировщик RRT (сетка)

О модели

Как это работает

Часто задаваемые вопросы