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

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

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

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

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

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

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

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

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

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

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

Для кого: После A* на сетке: сэмплинговое планирование до RRT*, PRM и кинодинамических версий.

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

RRT
сэмплинговое планирование
ближайший сосед
функция шага
проверка столкновений
вероятностная полнота
смещение к цели
препятствия на сетке

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

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

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

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

Продолжите с близкими темами в этой категории — или все 48 в «Инженерия».

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

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

MPC: голономный аппарат (2D, MPPI)

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

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

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

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

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

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

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

АЦП и ЦАП

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

Непрерывный синус переводится в отсчёты и квантуется, затем ЦАП восстанавливает ступенчатое напряжение (фиксация нулевого порядка). Видны критерий Найквиста и наложение спектров.

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

A* и Дейкстра (сетка)

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

Сетка 40×28: A*, Дейкстра или жадный поиск; эвристики, 4- и 8-связность, стены и дорогие клетки; раскраска открытых и закрытых множеств.

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

Тонкостенный сосуд под давлением

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

Мембранные напряжения в цилиндре и сфере: окружное σθ, продольное σz, эквивалент Мизеса, проверка r/t и запас по текучести.

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

Минимальный остов (Прим и Краскал)

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

Случайные точки на плоскости, полный граф с евклидовыми весами: пошаговый Прим от корня или Краскал с системой непересекающихся множеств; сравнение суммарного веса.

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

О модели

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

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

Похожие симуляторы

MPC: голономный аппарат (2D, MPPI)

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

АЦП и ЦАП

A* и Дейкстра (сетка)

Тонкостенный сосуд под давлением

Минимальный остов (Прим и Краскал)

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

О модели

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

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