Почему 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 в «Инженерия».

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

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

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

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

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

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

Генераторы лабиринтов + A*

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

Идеальные лабиринты на той же сетке 40×28, что и A*: рекурсивный backtracker, Уилсон, Эллер или случайный Прим; решение **A*** (Манхэттен, 4-соседство). Дорисовывайте стены, стирайте проходы, переносите S и G.

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