Kollisionsfreie Bahnplanung mit Rapidly exploring Random Trees (RRTs) bei mehreren Robotern

Um die Klasse rrt nicht auf die Auswertung der t-Koordinate hin zu spezialisieren und damit ihre Unabhängigkeit von den Eigenschaften des verwendeten Zustandsraumes einzuschränken, wurden die Methoden calc_distance und calc_quad_sum der Klasse sr_t_configuration_space angepaßt. Diese Klasse implementiert den um die Zeitachse erweiterten Konfigurationsraum. In rrt::find_nearest wird für alle Knoten des RRT die Methode state_space::calc_quad_sum aufgerufen (calc_quad_sum liefert nur die Quadratsumme der Koordinaten zweier Zustände, da für die Bestimmung, welcher Knoten näher liegt, aus Performance-Gründen die Quadratwurzel ausgelassen werden kann). In sr_t_configuration_space::calc_distance und sr_t_configuration_space::calc_quad_sum wird nun die t-Koordinate beider Zustände ausgewertet und wenn q2 in der Zeit vor q1 liegt, wird als Abstand -1 zurück gegeben. In rrt::find_nearest wird der entsprechende Knoten dann als qnear verworfen und die Suche fortgesetzt. So ist gewährleistet, daß rrt::find_nearest nur einen Knoten liefert, der in der Zeit vor qrand liegt und sich somit der RRT in der Zeit nur vorwärts ausbreitet. Die Methode rrt_planner::get_qnew, die einen neuen Knoten Richtung qrand in Entfernung der Schrittweite s erzeugt, wurde aus der Klasse rrt_planner entfernt und als get_position in die Klasse state_space verlagert. In sr_t_configuration_space::get_position wird wenn aktiviert - die Maximalgeschwindigkeit überprüft. Wird sie überschritten, wird der t-Wert der Zufallsposition qrand so angepaßt, daß die Maximalgeschwindigkeit wieder eingehalten wird. In Abb. 3.37 hätte eine neue Position in Richtung qrand eine zu kleine Steigung in Richtung t gehabt, die zu einer Geschwindigkeitsüberschreitung geführt hätte. Der neue Wert für t führt zu qrand2. Die Bewegung von qnear zur neuen Position qnew hält somit auf jeden Fall die Maximalgeschwindigkeit ein. [...]

Nun sind zwei Extremfälle möglich, die es bei der RRT-Planung zu beachten gilt. r Im Falle von s = 0 findet die Bewegung innerhalb des C nur auf der Zeitachse statt, wie in Abb. 3.35 bei q1 q 2 zu sehen. Die Geschwindigkeit ist dann 0 und der Roboter steht still. Dies ist ein gewünschtes Verhalten, denn nur so kann ein Roboter warten, bis ein anderer den Weg frei gemacht hat. Im Falle von t=0 allerdings, ist die Geschwindigkeit v = ∞ ,was nicht erlaubt ist. Der Roboter würde sich in Abb. 3.35 ohne Zeitverzögerung von q1 zu q3 bewegen. Dieses Verhalten gilt es zu verhindern. [...]

Nun wird die Planung für den Roboter mit der nächst niedrigeren Priorität durchgeführt, in 2 1 diesem Beispiel also R . Der Roboter R stellt nun ein bewegliches Hindernis dar, dessen 1 Position und Ausrichtung zum Zeitpunkt t durch P (t) gegeben ist. Über die Methode get_state_at_t der Klasse rrt, können die Achswerte des Roboters zu einem beliebigen Zeitpunkt min ≤ t ≤ max (gemäß der Normierung der Zeitachse) ermittelt werden. Da der Konfigurationsraum um eine Zeitachse erweitert wurde, besitzt jeder Knoten eines RRTs eine Zeitkoordinate. Die Methode get_state_at_t findet die beiden Knoten, die zeitlich vor und nach dem angegebenen Wert für t liegen und interpoliert die Position dazwischen. Durch die Erweiterung des Konfigurationsraumes um die Zeitachse, stellt sich der Roboter R 1 hier nun als statischer Kollisionsbereich dar, dessen Form durch P bestimmt ist. Der 1 1 Kollisionsbereich des Roboters R im Cx,y wird entlang des Paths P extrudiert und ergibt so den Kollisionsbereich im Cx,y,t. [...]