5. Algorithmen zur Berechnung des Fahrverhaltens eines Teilnehmers

Betrachten wir einen Teilnehmer, der ein Stück Fahrbahn vor sich sieht. Jeder Teilnehmer ist daran interessiert, möglichst selten wieder auf die Fahrbahn blicken zu müssen (möglichst selten sein Fahrverhalten wieder überdenken zu müssen), damit er häufig Zeit für sich selbst hat (häufig über den Bildschirm bewegen werden kann), denn das Festlegen der Trajektorie ist zeitaufwendig.

Er bestimmt also zuerst den Punkt, wo er das nächste Mal bestimmt anhalten muss. Dafür ignoriert er noch alle Teilnehmer, die sich vor ihm befinden könnten. Hat er einen solchen Punkt gefunden, so berechnet er sich seine optimale Trajektorie bis zu diesem Punkt, indem er allfällige Geschwindigkeitsbegrenzungen auf dem Weg dorthin berücksichtigt. Aber nicht immer gibt es einen solchen Punkt, und es ist auch nicht gesagt, dass er wirklich dort anhalten muss, wenn er bis an das Hindernis gefahren ist. Das Hindernis wird meist eine Ampel sein, die auf Rot oder auf Grün stehen kann, und so wird er sicher die Trajektorie befolgen, bis er an den Punkt gelangt, wo er bremsen müsste, wenn die Ampel rot wäre – wo er aber seine Trajektorie neu zu berechnen hätte, wenn die Ampel auf Grün stünde. Folglich wird er die Trajektorie als sicher bis zum Bremspunkt deklarieren und als fraglich den anschliessenden Bremsvorgang. Das ist in der nächsten Abbildung gezeigt.

Wir haben uns zu einem Zeit-Geschwindigkeits-Diagramm entschlossen und nicht zu einem Weg-Zeit-Diagramm, wie man das vielleicht erwartet hätte. Das ist darum geschehen, weil wir unmittelbar die Geschwindigkeit aus dem Diagramm ablesen können möchten, der zurückgelegte Weg entspricht der Fläche unter der Kurve bis zu einem betrachteten Zeitpunkt. Warum wir sie so dringend brauchen, werden wir in Kürze sehen, denn der Algorithmus ist so leichter erklärbar. Natürlich könnten wir auch ein Weg-Zeit-Diagramm benützen (einen "graphischen Fahrplan"), wo dann die Geschwindigkeit der Steigung der Kurve entspräche.

Aber nicht nur Ampeln können einen Teilnehmer zum Bremsen bewegen, sondern auch Verzweigungen und Zusammenführungen von Strassen. Grundsätzlich ist eine vorausberechnete Trajektorie nur bis zur nächsten Weiche gültig, denn an diesem Punkt entscheidet es sich, ob sie auch wirklich richtig steht, oder ob der Teilnehmer mit einem anderen Teilnehmer kollidiert.

Bei einer Verzweigung muss sichergestellt werden, dass der Teilnehmer in jedem Fall, wie die Weiche auch steht, noch rechtzeitig hinter dem Vordermann zum Stehen kommen kann. Bei einer Zusammenführung von Strassen ist das Vorausberechnen des Fahrverhaltens etwas schwieriger; entweder können die Verkehrsflüsse wie ein "Reissverschluss" zusammenkommen, oder aber es besteht eine Vortrittsregelung.

Angenommen, wir haben alle Abklärungen getroffen, wie die Trajektorie wohl weitergehen wird, dann kennen wir auch die Ampel am Schluss der Trajektorie. Wir kennen aber auch weiter denjenigen Teilnehmer, der unmittelbar vor dem betrachteten fährt; ihn nennen wir den Anführer der kleinen Kolonne, den betrachteten Teilnehmer selbst, den Folger. Möchte nun der Folger seine Trajektorie optimal legen (wobei "optimal" bedeuten soll, dass er in kürzester Zeit zum Anführer aufschliessen möchte), dann ergibt sich daraus ein Rendez-vous-Problem mit den folgenden Parametern:

Zur Lösung dieser Aufgabe werden wir nun einen Algorithmus kennenlernen.

5.1 Legen der optimalen Trajektorie

Ein Teilnehmer sucht zuerst das nächste unbewegliche Hindernis auf seiner Fahrstrecke, welches ihn zum Anhalten zwingen könnte. Das sind Ampel-Marken, aber auch Weichen, da der Teilnehmer gewöhnlich nicht hinter eine Weiche blickt, wenn er noch weit von ihr entfernt ist. Senken müssen etwas gesondert behandelt werden, denn wohl wird bei ihnen die Trajektorie aufhören, doch wird der Teilnehmer nicht anhalten. Bewegliche Hindernisse ignoriert er bislang; um ihren Einfluss wird er die optimale Trajektorie anschliessend korrigieren müssen.

Jede Linie (zwischen Punkten oder Ecken) hat eine zugelassene Maximalgeschwindigkeit. Diese müssen nun gesammelt werden, und sie dienen der optimalen Trajektorie als Rahmen. Der Teilnehmer beginnt seine Geschwindigkeit erst in dem Moment anzupassen, da er die Linie zu befahren beginnt. Er blickt also nicht voraus.

Folgende Situationen bedürfen einer genaueren Betrachtung:

Diese drei Fälle wollen wir nun noch algebraisch behandeln:

Ausgehend von der aktuellen Geschwindigkeit kann der Bremsweg berechnet werden. Ist er kürzer als die augenblickliche Distanz bis zum Haltepunkt, darf er bis höchstens zur Maximalgeschwindigkeit beschleunigen. Sind die Distanz, um auf die Maximalgeschwindigkeit zu beschleunigen, plus der anschliessende Bremsweg grösser als der augenblickliche Abstand zum Haltepunkt, darf der Teilnehmer nicht bis zur Höchstgeschwindigkeit beschleunigen. Er muss die höchstmögliche erreichbare Geschwindigkeit vm berechnen. Dafür wird die Strecke, die zur Verfügung steht, in die Abschnitte s1 und s2 aufgeteilt. Für beide können wir s durch vm aufdrücken. Aufgelöst nach vm erhalten wir das gewünschte Resultat.

,

,

mit abe als Beschleunigung, abe > 0

abr als Brems-Beschleunigung, abr < 0

Der Teilnehmer berechnet die Distanz, welche ihm für die neue, höhere Geschwindigkeit zur Verfügung steht. Ist sie grösser als die Distanz, welche er zum Beschleunigen benötigt, beschleunigt er bis zur zugelassenen Höchstgeschwindigkeit und fährt anschliessend konstant schnell weiter. Ist sie kleiner, beschleunigt er während der verfügbaren Distanz. Ist die folgende Geschwindigkeit allerdings höher, dann darf er weiter beschleunigen.

Analog zum gerade erwähnten Fall berechnet der Teilnehmer die Distanz, welche ihm für die neue, nun niedrigere Geschwindigkeit zur Verfügung steht. Ist sie grösser als die Distanz, welche er zum Bremsen benötigt, bremst er bis zur zugelassenen Höchstgeschwindigkeit und fährt anschliessend konstant schnell weiter. Ist sie kleiner, bremst er während der verfügbaren Distanz. Ist die folgende Geschwindigkeit nochmals niedriger, dann muss er weiter bremsen.

5.2 Struktur des Algorithmus für das Rendez-vous-Problem

Der Algorithmus zerfällt in die Teilgebiete "Bestimmung des Schiebepunktes" und "Bewegen des Schiebepunktes":

Im ersten Schritt wird versucht, den Folger so weit zu bremsen, dass seine Trajektorie die Trajektorie des Anführers schneidet; oder aber die Trajektorie des Folgers muss so weit beschleunigt werden, bis sie diejenige des Anführers erreicht. Die Fläche zwischen der so entstandenen Trajektorie und der Trajektorie des Anführers entspricht der Distanz, um welche der Gegenseitige Abstand der beiden Fahrzeuge verändert wird, ist der Folger schneller, wird er verkleinert, ist er langsamer, vergrössert. Muss der Folger gebremst werden, so kann es zu einer Auffahrkollision kommen, wenn die Fläche grösser als der Abstand d0 ist.

Im zweiten Schritt nun muss der Schiebepunkt so lange verschoben werden, bis die Fläche, welche die Verbindungsgerade der Trajektorie dabei überstreicht, gleich der restlichen Distanz zum Anführer geworden ist.

Konventionen für die folgenden algebraischen Herleitungen sind: