Warum findet RRT manchmal keinen Weg, den A* findet?

Enge Gänge verlangen, dass ein Zufallspunkt **in** den Spalt fällt, bevor der Baum „eintreten“ kann; bei knappem Iterationsbudget oder großem Schritt ist die Wahrscheinlichkeit klein. Den **Schritt** verkleinern, die maximale Knotenzahl erhöhen oder die **Verschiebung** zum Ziel vergrößern, wenn der Baum schon nah ist — dasselbe „enge Durchgangs“-Problem, das **RRT*** und **Informed RRT** motiviert hat.

Ist der gelbe RRT-Pfad optimal?

Nein — das einfache RRT liefert **irgendeinen** zulässigen geometrischen Weg. **A*** auf dem Gitter ist optimal **für dieses diskrete Modell**, kann Zellen aber nicht frei schneiden, daher sind die Kosten nicht direkt vergleichbar.

Wie ist die Kollisionsprüfung aufgebaut?

Die Strecke wird mit einem Schritt kleiner als eine Zelle diskretisiert; jeder Punkt fällt in eine Zelle nach der unteren ganzen Zahl der Koordinaten; ein Treffer in einer **Wand** lehnt die Kante ab. Das ist ein schneller Lehrtest, kein Motor mit „aufgeblasenen“ Hindernissen.

Wird A* neu gerechnet, wenn man S/G versetzt?

Der Vergleich nimmt den **aktuellen** Stand von Karte und Enden. Nach dem Versetzen der Marken den Vergleich mit **A*** erneut starten.

RRT-Pfadplaner (Gitter)

Dieselbe Wandkarte 40×28: zufällige Proben, nächster Knoten, Schritt mit Kollisionsprüfung, Verschiebung der Stichprobe zum Ziel; Taste zum Vergleich mit A*.

RRT-Pfadplaner

Werkzeug

Lenkschritt (Zellen)0.85

Zielverschiebung der Stichprobe0.08

Einfangradius des Ziels0.42

Max. Baumknoten4500

RRT-Iterationen je Bild220

Saat der Stichprobe1

Kartenvorlage

Baumgröße1

Ziel erreichtnein

RRT-Pfadlänge—cells

A* (4-Nachbarschaft, dieselbe Karte)—

RRT erkundet zufällige Richtungen; A* auf denselben Wänden minimiert die Summe der Zellenkosten (×5 auf „teuren“ Zellen, falls sie im Gitter liegen — hier sind standardmäßig nur Wände).

Tastenkürzel

Klick: Wand / Radierer; „S verschieben“ / „G verschieben“ setzt die Enden.
„Mit A* vergleichen“ rechnet Manhattan-A* auf demselben Gitter; den vollen Heuristikensatz finden Sie unter **engineering/astar-dijkstra-grid**.

Gemessene Größen

Wachstumnein

Zum Modell

Ein RRT-Pfadplaner (schnell explorierender Zufallsbaum) wächst durch zufällige Schritte im freien Raum. Das Lehr-RRT steht auf demselben Wandgitter 40×28 wie engineering/astar-dijkstra-grid, aber mit stetigen Knotenkoordinaten in „Zelleneinheiten“ — der Weg kann Ecken zwischen Gitterknoten schneiden. In jeder Iteration wird ein zufälliger freier Punkt genommen (mit Verschiebung der Stichprobe zum Ziel), der nächste Baumknoten gesucht, ein Schritt begrenzter Länge längs der Sehne ausgeführt und die Kante nur angenommen, wenn die dichte Prüfung der Strecke keine Wandzellen trifft. Ein neuer Scheitel innerhalb des Einfangradius um den Mittelpunkt von G beendet die Suche; die gelbe Linie ist der Rückweg über die Eltern nach S. RRT ist probabilistisch vollständig, aber nicht optimal: die Pfadlänge ist oft größer als beim diskreten **A* mit Manhattan-Heuristik auf denselben Wänden; die Vergleichstaste startet einen solchen A* (4-Nachbarschaft, teure Zellen ×5, falls sie im Gitter liegen). Mit Schritt, Verschiebung und Iterationen je Bild** sieht man den Kompromiss zwischen Raumerkundung und Durchgang durch enge Gänge.

Für wen: Nach A* auf dem Gitter: stichprobenbasierte Planung vor RRT*, PRM und kinodynamischen Varianten.

Wichtige Begriffe

rrt
stichprobenbasierte planung
nächster nachbar
schrittfunktion
kollisionsprüfung
probabilistische vollständigkeit
zielverschiebung der stichprobe
gitterhindernisse

So funktioniert es

RRT: Zufallspunkt → nächster Baumknoten → Schritt dorthin mit Prüfung der Wände des Gitters; die Verschiebung zum Ziel beschleunigt das Ende; A* auf derselben Karte ist der diskrete Maßstab für Kosten und Zahl der Expansionen.

Häufige Fragen

Warum findet RRT manchmal keinen Weg, den A* findet?: Enge Gänge verlangen, dass ein Zufallspunkt in den Spalt fällt, bevor der Baum „eintreten“ kann; bei knappem Iterationsbudget oder großem Schritt ist die Wahrscheinlichkeit klein. Den Schritt verkleinern, die maximale Knotenzahl erhöhen oder die Verschiebung zum Ziel vergrößern, wenn der Baum schon nah ist — dasselbe „enge Durchgangs“-Problem, das RRT* und Informed RRT motiviert hat.
Ist der gelbe RRT-Pfad optimal?: Nein — das einfache RRT liefert irgendeinen zulässigen geometrischen Weg. A* auf dem Gitter ist optimal für dieses diskrete Modell, kann Zellen aber nicht frei schneiden, daher sind die Kosten nicht direkt vergleichbar.
Wie ist die Kollisionsprüfung aufgebaut?: Die Strecke wird mit einem Schritt kleiner als eine Zelle diskretisiert; jeder Punkt fällt in eine Zelle nach der unteren ganzen Zahl der Koordinaten; ein Treffer in einer Wand lehnt die Kante ab. Das ist ein schneller Lehrtest, kein Motor mit „aufgeblasenen“ Hindernissen.
Wird A* neu gerechnet, wenn man S/G versetzt?: Der Vergleich nimmt den aktuellen Stand von Karte und Enden. Nach dem Versetzen der Marken den Vergleich mit A* erneut starten.

Machen Sie mit verwandten Themen in dieser Kategorie weiter — oder alle 48 in „Ingenieurwesen“.

Ganze Kategorie →

NeuHochschule / Forschung

MPC: holonomes Fahrzeug (2D, MPPI)

Simulation starten

Ebener Doppelintegrator mit Schranke ‖u‖₂: stichprobenbasiertes MPPI führt zum verschiebbaren Ziel und bestraft kreisförmige Hindernisse weich — Fächer der Vorhersagen und bester Pfad.

NeuSchule

Labyrinthe und A*

Simulation starten

Ideale Labyrinthe auf dem Gitter 40×28: rekursiver Rückverfolger, Wilson, Eller oder zufälliger Prim; Lösung mit A* (Manhattan, 4-Nachbarschaft). Wände nachzeichnen und Start sowie Ziel versetzen.

NeuHochschule / Forschung

ADC und DAC

Simulation starten

Ein kontinuierlicher Sinus wird abgetastet und quantisiert, danach stellt der DAC eine treppenförmige Spannung wieder her (Halteglied 0. Ordnung). Nyquist-Kriterium und Aliasing werden sichtbar.

NeuSchule

A* und Dijkstra (Gitter)

Simulation starten

Gitter 40×28: A*, Dijkstra oder gierige Suche; Heuristiken, 4- und 8-Nachbarschaft, Wände und teure Zellen; Färbung der offenen und geschlossenen Menge.

NeuSchule

Dünnwandiger Druckbehälter

Simulation starten

Membranspannungen in Zylinder und Kugel: Umfangsspannung σθ, Längsspannung σz, Vergleichsspannung nach von Mises, Prüfung r/t und Sicherheit gegen Fließen.

NeuSchule

Minimaler Spannbaum (Prim und Kruskal)

Simulation starten

Zufällige Punkte in der Ebene, vollständiger Graph mit euklidischen Gewichten: Prim schrittweise von der Wurzel oder Kruskal mit Union-Find; Vergleich der Gesamtgewichte.

RRT-Pfadplaner (Gitter)

Zum Modell

So funktioniert es

Häufige Fragen

Ähnliche Simulationen

MPC: holonomes Fahrzeug (2D, MPPI)

Labyrinthe und A*

ADC und DAC

A* und Dijkstra (Gitter)

Dünnwandiger Druckbehälter

Minimaler Spannbaum (Prim und Kruskal)

RRT-Pfadplaner (Gitter)

Zum Modell

So funktioniert es

Häufige Fragen