Mathesis Wiki

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Verkehrssimulation ======

Ein Mathesis-Projekt aus dem Sommersemester 2024 \\ von Leonard Jungk, Lina Goethe, Luis Jasper und Manou Lüders

===== Kurzbeschreibung/Grundidee =====
Das Ziel unserer Gruppe war es, den Autoverkehr in einem Straßennetz zu simulieren.
In der Simulation bewegen sich Autos über mehrere Straßen von ihrem Startpunkt zu ihrer Zielkreuzung. Dabei wählen die Autos den kürzesten Weg zu ihrem Ziel und passen ihre Geschwindigkeit an das Verhalten der anderen Autos und Ampeln an. 

===== Funktionsweise =====

==== Grundlegender Aufbau ====

{{ :ss2024:bild_auto_strasse_kreuzungen.png?nolink&250| Ein Auto auf einer Straße zwischen zwei Kreuzungen.}}

Die Grundlage der Simulation stellen drei Arten von Objekten dar:
  * //Straßen//, die als Strecken in einem zweidimensionalen Koordinatensystem existieren.
  * //Kreuzungen//, die als Punkte in dem gleichen Koordinatensystem liegen, Straßen miteinander verbinden und damit Anfangs- und Endpunkte der Straßen sind.
   * //Autos//, die sich als die Agenten in der Simulationswelt auf den Straßen und Kreuzungen bewegen.



Bei der Simulation von Autos gibt es zwei grobe Ansätze: Bei dem makroskopischen Ansatz werden die Autos als Gesamtheit analog zu Fluidsystemen beschrieben. Dagegen werden bei dem mikroskopischen Ansatz die individuellen Autos betrachtet. <sup>[1]</sup> \\
Bei dieser Simulation wird ein makroskopisches Modell, das //Intelligent Driver Model// (IDM) von Treiber, Hennecke und Helbing verwendet.<sup>[1]</sup> Ein Auto beschleunigt und bremst dabei abhängig vom Verhalten des vorderen Autos und die Autos folgen einander, ohne einander zu überholen. \\
Die Autos haben in der Simulation eine Start- und eine Zielkreuzung. Bei Start der Simulation bestimmt jedes Auto seine Route anhand der Kreuzungen, die zur Zielkreuzung führen. Anschließend starten die Autos auf der Straße von der ersten Kreuzung zur zweiten Kreuzung der Route. Sie fahren bis zum Ende dieser Straße und biegen über die Kreuzung auf die nächste Straße ab. Das wird so lange wiederholt, bis die Zielkreuzung erreicht ist.

Die Straßen besitzen ein inneres, eindimensionales Koordinatensystem auf dem die Koordinate eines Autos den Abstand zum Anfang der Straße darstellt. Sie liegt dabei zwischen Null und der Länge der Straße. Autos können sich auf Straßen nur in eine Richtung vom Anfangs- zum Endpunkt bewegen. Die Straßen in der Simulation kann man sich damit als einzelne Straßenspuren in der Realität vorstellen.

Die Kreuzungen liegen als Punkte im zweidimensionalen Koordinatensystem vor und haben zusätzlich einen Radius, wobei Autos, die sich innerhalb von diesem befinden, als auf der Kreuzung fahrend gezählt werden. Die Kreuzungen sind vereinfacht als Kreise dargestellt. Ein Auto folgt beim Abbiegen auf einer Kreuzung einer bestimmten Kurve innerhalb des Kreuzungsradius, die bei der vorherigen befahrenen Straße beginnt und bei der nächsten, durch die Route bestimmten, Straße endet.

Die Simulation wurde in der Programmiersprache Python realisiert und mithilfe des Moduls Pygame visualisiert. Sie erfordert pygame 2.6.0 und numpy 2.0.1 als Module um funktionsfähig zu sein.

==== Programmstruktur ====

Der Programmcode besteht aus folgenden Dateien:
    * ''main.py''
    * ''Karte.py''
    * ''Auto.py''
    * ''Kreuzung.py''
    * ''Strasse.py''
    * ''Parkplatz.py''

In den Dateien ''Auto.py'', ''Kreuzung.py'' und ''Strasse.py'' sind die Klassen der jeweiligen Objekte enthalten. In ''Parkplatz.py'' ist die Klasse ''Parkplatz'' enthalten, die, das Verhalten von Autos regelt, die ihr Ziel erreicht haben. In ''main.py'' befindet sich der Kern des Programms und ''karte.py'' steuert die Visualisierung und verknüpft die Objekte.

Daneben werden für das Programm noch die Datei ''Auto_B.png'', das Bild der Autos und ''ARIAL.TTF'' zum Anzeigen Schrift im gleichen Ordner benötigt.

== main ==

Durch Ausführen der Datei ''main.py'' wird das Programm gestartet. Die Datei importiert alle Bestandteile von "Karte" und das Modul Pygame. Zu Beginn werden einige Einstellungen für Pygame festgelegt, anschließend werden die einzelnen Objekte erschaffen.\\
Für das Straßennetz wird zuerst ein leeres Dictionary ''strassenbuch'' benötigt, dass alle Straßen-Objekte enthalten wird. Danach werden alle Kreuzungen erschaffen und zu einer Liste ''kreuzungen'' hinzugefügt. Im nächsten Schritt werden über das Aufrufen der Methode ''connect'' auf den Kreuzungen, die Kreuzungen verbunden und Straßen erschaffen. \\
In der Datei sind bereits drei verschiedene Straßennetze als Kommentare angelegt, das aktive ist nicht auskommentiert. Dabei ist Straßennetz 1 das einfachste, Straßennetz 2 ein komplizierteres und STraßennetz 3 dient dem Testen von Kreuzungen. \\ 

Danach werden für jede Kreuzung die Ampeln erschaffen und zum Schluss werden die Autos erstellt und zu der Liste ''autos'' hinzugefügt.
Diese Reihenfolge ist wichtig, da die Objekte jeweils die Existenz von anderen Objekten voraussetzen. \\
Im nächsten Abschnitt wird das Fenster initialisiert, und das Straßennetz, sowie gegebenenfalls der Parkplatz für die Visualisierung erschaffen. Danach werden Straßennetz, Ampeln, Autos und gegebenenfalls der Parkplatz angezeigt.

Anschließend beginnt in der Hauptschleife die Simulation, die so lange weiter läuft, bis das Programm gestoppt wird. In ihr wird geprüft, ob die Simulation durch Drücken der Leertaste gestoppt wird, und wenn das nicht der Fall ist, werden folgende Schritte wiederholt ausgeführt:

    * Straßennetz anzeigen
    * Ampeln schalten und anzeigen
    * Autos bewegen und anzeigen
    * ggf. Parkplatz anzeigen.
Der Parkplatz ist ein optionales Feature.

== Karte ==

Die Datei ''Karte.py'' ist für die Darstellung der Objekte auf dem Fenster zuständig und regelt die einzelnen Simluationsschritte der Objekte. Sie enthält die Funktionen ''transformiere'', ''schalte_ampeln'', ''bewege_autos'' und ''karte_zeichnen''.

''karte_zeichnen'' erstellt ein Objekt vom Typ Pygame.Surface. Auf dieses wird das skalierte Straßennetz gezeichnet. Da das Straßennetz so auf einer eigenen Oberfläche ist, muss in der Hauptschleife in jedem Durchlauf nur diese Oberfläche auf dem Fenster befestigt und das Straßennetz nicht neu generiert werden.
Dabei werden zuerst die Straßen als breite Linien von Mittelpunkt der Anfangs- zu dem der Endkreuzung gezeichnet, wobei sie aus Sicht der Straße nach rechts versetzt werden. Anschließend werden die Kreuzungen als Kreise um ihre Mittelpunkte gezeichnet.
In der Funktion wird ebenfalls die Umrechnung vom internen Koordinatensystem in das der Visualisierung festgelegt. Die Karte-Oberfläche wird an ''main.py'' zurückgegeben. \\
''schalte_ampeln'' wird in jedem Durchlauf der Hauptschleife aufgerufen und schaltet die Ampeln, wie im [[ss2024:verkehrssimulation#Ampeln|Teil zu den Ampeln]] erklärt. Die Ampeln werden dann je nach Ampelphase in der Farbe rot oder grün ans Ende ihrer Straße gezeichnet. \\
''bewege_autos'' geht alle Autos durch, ruft auf ihnen die Funktion ''fahren'' auf, nimmt die zurückgegebene Position entgegen und befestigt das Bild der Autos an der richtigen Position im Winkel des Autos auf dem Fenster. \\
''transformiere'' ist eine Hilfsfunktion, die das interne zweidimensionale Koordinatensystem in das Koordinatensystem der Visualisierung umrechnet.

== Auto ==
Die Datei ''Auto.py'' mit der Klasse "Auto" ist für die internen Prozesse der Autos zuständig und regelt unter anderem das Fahren und die Wegfindung. Die Wegfindung haben wir in den einzelnen Bestandteilen geregelt. Beim muss das Auto unterscheiden, ob es auf einer Kreuzung oder Straße fährt. Dementsprechend holt es die Maximalgeschwindigkeit und seine Trajektorie sowie Informationen über andere Autos auf diesem Objekt. Basierend darauf berechnet es seine Beschleunigung mit dem intelligent driver model und bewegt sich. Wenn es ans Ende seiner aktuellen Straße oder Kreuzung kommmt, setzt es sich zudem noch auf das nächste Objekt weiter. 

== Kreuzung ==
Die Klasse "Kreuzung" in ''Auto.py'' umfasst Methoden um die Kreuzungen mit Straßen zu verbinden, die später erläuterte Abbiegekurvenparametrisierung zu errechnen sowie den Autos auf der Kreuzung Informationen über Position und Geschwindigkeit anderer auf der Kreuzung befindlichen Autos zu liefern und beinhaltet die Klasse Ampel, die wiederum die Ampeln regelt.

== Strasse ==
Die Elemente der Klasse "Strasse" verbinden Kreuzungen und bieten den Autos auf ihnen Methoden zum Informationsabruf von Position und Geschwindigkeit anderer auf der Straße befindlichen Autos.

== Parkplatz ==

Die Aufgabe der Klasse ''Parkplatz'' in der Datei ''Parkplatz.py'' ist es die Autos anzuzeigen, die ihr Ziel bereits erreicht haben. Dafür gibt es innerhalb der Klasse die Pygame-Oberfläche ''parkplatz'', deren Größe von der Größe des Bildes für die Autos abhängig ist, und die während der Simulation als graues Rechteck am rechten Rand angezeigt wird. Wenn ein Auto seine Zielkreuzung erreicht hat, wird seine Variable ''strasse'' auf ''"parkplatz"'' gesetzt. Durch die Methode ''parke'' der Parkplatz-Klasse werden ein Bild des Autos, Start- und Zielkreuzung, Dauer bis zum Erreichen des Ziels und Durchschnittsgeschwindigkeit zu der Oberfläche ''parkplatz'' hinzugefügt. Autos auf der Straße ''"parkplatz"'' werden im weiteren Verlauf des Programms ignoriert.
Durch aufrufen der Methode ''geparkte_autos'' wird die Parkplatz-Oberfläche mit den Details zu den Autos, und einem Zähler für die vergangene Zeit auf dem Fenster angezeigt.

==== Einzelne Elemente ====


=== Intelligent Driver Model ===


Die Beschleunigung zu jedem Tick wird für jedes Auto folgendermaßen errechnet:

\begin{equation}
    a = \alpha \left(1-\left(\frac{v}{v_0}\right)^\delta - \left( \cfrac{s_0 + vT + \cfrac{v \cdot \Delta v }{2\sqrt{\alpha b}}}{s} \right)^2 \right)
\end{equation}

$v $  ist die Momentangeschwindigkeit. \\
$v_0 $  ist die Maximalgeschwindigkeit mit meist $v_0 = 15 m/s. $\\
$\Delta v $ ist die Annäherungsrate, also die Geschwindigkeitsdifferenz zum vorderen Auto.\\
$s $ ist die Entfernung zum nächsten Auto, also die Position des vorderen Autos minus eigene Position minus 5 Meter Autolänge.\\
$T = 1,5s$ ist die Sicherheitsabstandszeit. \\
$\alpha = 0,73 m/s^2$ ist die Maximalbeschleunigung. \\
$b = 1,67 m/s^2 $ ist die angenehme Entschleunigung (/Bremsung). \\
$ \delta = 4 $ ist der Gewichtungsexponent für die Nähe zur Maximalgeschwindigkeit $v_0$ . \\
$ s_0 = 2m $ ist der Mindestabstand.

Der Term $\left(\frac{v}{v_0}\right)^\delta$ wird durch den großen Exponenten schnell groß, wenn die Geschwindigkeitsbegrenzung überschritten wird und schnell klein wenn sie unterschritten ist.
Der Term $\cfrac{s_0 + vT + \cfrac{v \cdot \Delta v }{2\sqrt{\alpha b}}}{s} $ bildet ein Verhältnes aus gewünschtem und aktuellem Abstand zum vorderen Auto. Der gewünschte Abstand setzt sich dabei aus der Summe von Mindestabstand $s_0$, der Entfernung die das Auto in den nächsten $T = 1,5s$ zurücklegen würde und einem Sicherheitsabstand, der mit wachsender Eigengeschwindigkeit sowie wachsender Annäherungsrate steigt. Er bremst auch das Auto wenn es zu nahe an das nächste Fahrzeug kommt.

Dies ist folgendermaßen implementiert:
<code python>
        a =  self.a_max*(1-(self.v/v_max)**self.delta - ((self.s_min + self.v * self.T + (self.v*(self.v-vorder_v))/(2*math.sqrt(self.a_max*self.b)))/(vorder_pos-self.pos-self.l))**2)
</code>


=== Wegfindungsalgorithmus ===

Zur Wegfindung nutzt das Auto den Dijkstra-Algorithmus. Dafür braucht es eine Liste an Kreuzungen und Straßen. Jeder Straße wird ein Wert zugewiesen, der zeigt, wie lange das Auto von ihrem Anfang zu ihrem Ende braucht, in unserem Fall ist dies ihre Länge. Beginnend mit der Anfangskreuzung geht das Auto alle Kreuzungen, die über eine Straße direkt mit ihr verbunden sind, durch. Dabei wird jeder Kreuzung zugeordnet, wie lange das Auto bis zu ihr braucht (im ersten Schritt also einfach wie lang der Weg von der Anfangskreuzung aus ist) und von welcher Kreuzung der schnellste Weg kam. 
 
Aus allen Kreuzungen, die so erreicht wurden, wird mit der Kreuzung weitergemacht, die am schnellsten erreicht wurde. Von dieser werden wieder alle angrenzenden Kreuzungen überprüft. Wird eine Kreuzung, zu der bereits ein Weg führt, gefunden, werden beide verglichen und der schnellere gespeichert. Danach wird der selbe Schritt mit der Kreuzung wiederholt, die von allen verbleibenden den kürzesten Weg von der Anfangskreuzung zu sich hat.

Sobald alle Kreuzungen auf diesem Weg kontrolliert wurden, kann man den schnellsten Weg zur Zielkreuzung rekonstruieren, indem man so lange verfolgt, von welcher Kreuzung der schnellste Weg kam, bis man bei der Anfangskreuzung ist. 

Im Code wurde das so Umgesetzt:

<code python>
        done = []
        todo = [start]
        speed = {}
        woher = {}
</code>

Wobei ''done'' die Liste der abgesuchten Kreuzungen, ''todo'' die Liste der gefundenen Kreuzungen, und ''speed'' den Wert des bisher schnellsten Wegs jeder Kreuzung und ''woher'' den letzten Schritt dieses Wegs speichert. 
<code python> 
while len(done) < len(kreuzungen): 
   j = self.s_todo(todo,speed):
   for i in j.ausgaenge:
      l = self.strassenbuch[j.name + '_' + i.name].laenge
      if i in done or i in todo:
            if speed[j.name]+l < speed[i.name]:
                  speed[i.name] = speed[j.name]+l  
                  woher[i.name] = j.name
            else :   
                  speed[i.name] = speed[j.name]+l 
                  todo = todo + [i]
   todo.remove(j)
   done = done + [j]  
</code> 
''s_todo'' ist eine Funktion, die aus der ''todo''-Liste die Kreuzung mit dem kürzesten Weg zur Startkreuzung sucht und im ''strassenbuch'' kann man auf jede Straße über ihren Namen zugreifen. Dann wird in allen Ausgängen dieser Funktion überprüft, ob sie schon gefunden wurden und ggf. der Weg verglichen. Falls die Kreuzung zum ersten Mal gefunden wird, wird sie außerdem zu ''todo'' hinzugefügt. Anschließend wird die von ''s_todo'' gefundene Funktion in die Liste der abgesuchten Kreuzungen hinzugefügt. 

=== Verhalten auf Kreuzungen ===

== Kurven ==

Damit die Autos sich nicht über die Kreuzungen teleportieren, werden Kreisbahnen parametrisiert, die ankommende und abgehende Straßen knickfrei verbinden. Für die erfolgreiche Parametrisierung der Bahn werden 3 Elemente benötigt: der Drehwinkel, der Radius und der Mittelpunkt des Kreises. Um außerdem eine eindeutige Bahn zu haben, braucht man noch den Punkt, an dem die Straße in die Kreuzungen übergeht.
 
Den Winkel findet man zwischen den Vektoren, die von der Kreuzungsmitte zu den Kreuzungen zeigen, von der das Auto kommt, bzw. zu der das Auto abbiegt, mithilfe des Arcustangens. $\beta$ ist hier der Winkel, um den wir später drehen wollen.  

{{formel.png ?280}}{{ Winkel_berechnen2.png ?390}}

Für den Radius des Kreisbogens schauen wir uns den Schnittpunkt zwischen Kreisbogen und Kreuzungsgrenze an. Zusammen mit dem Mittelpunkt des Kreisbogens (den wir hier noch nicht kennen, aber auch nicht weiter verwenden) und dem Mittelpunkt der Kreuzung, formt dieser ein rechtwinkliges Dreieck. Der hier in rot markierte Winkel ist genau halb so groß wie der vorhin berechnete Schnittwinkel. Mit dieser Information und der Länge des Kreuzungsradius, lässt sich der Kreisbogenradius mit dem Tangens berechnen. 

{{bildschirmfoto_2024-09-25_um_14.29.44.png ?250}} {{ Radius_Kreisbahn_berechnen.png?390}}

Hier ist $M$ der Mittelpunkt der Kreuzung, m der Kreisbogenmittelpunkt und $S$ der Punkt, wo das Auto von der Straße auf die Kreuzung fährt. 

Um den Mittelpunkt zu ermitteln führen wir eine Fallunterscheidung durch. Wird im mathematisch positiven Sinn gedreht, so folgt der Mittelpunkt so:
<code python>
a = self.Winkel_diff(an, ab) 
d =  (radius/math.cos(a/2))
m1 = self.gridpos[0] + d * math.cos(self.Winkel_Ankunft(an) - a/2 )
m2 = self.gridpos[1] + d * math.sin(self.Winkel_Ankunft(an) - a/2 )
</code>
Wobei m1 die x-Koordinate und m2 die y-Koordinate des Mittelpunkts ist. 

Im anderen Fall erfolgt sie so: 
<code python> 
a = self.Winkel_diff(an, ab) 
d =  (radius/math.cos(a/2))
m1 = self.gridpos[0] + d * math.cos(self.Winkel_Ankunft(an) + a/2 )
m2 = self.gridpos[1] + d * math.sin(self.Winkel_Ankunft(an) + a/2 )
</code>

Dieser Unterschied folgt aus der Funktion ''winkel_ankunft''. Wird anders herum gedreht, ändert sich nämlich die Richtung des Vektors, der in der Funktion mit der x-Achse geschnitten wird und somit auch der Winkel. Hier nochmal ein Beispiel: 

{{drehrichtung1.png ?310}}{{ drehrichtung2.png?310}}

Obwohl die beiden Fälle nur an der y-Achse gespiegelt sind, ändert sich der Ankunftswinkel und muss daher anders in die Formel eingehen. 

Um aus diesen drei Punkten die Parametrisierung zu machen, wird zu erst berechnet, wie weit auf dem Kreisbogen das Auto schon gefahren ist. Als Maß hierfür wird der Winkel genommen. Dann wird der Vektor zwischen Endpunkt der Straße und Mittelpunkt des Kreisbogens berechnet. Dieser wird dann mithilfe einer Drehmatrix um den Winkel gedreht, den das Auto schon gefahren ist und somit der neue Standort des Autos berechnet.

\begin{equation}
    b := \frac{Position}{Radius} \\
    \begin{pmatrix}
        x_0 \\
        x_1
    \end{pmatrix}
     = 
    \begin{pmatrix}
        \cos (b) & - \sin  (b)  \\
        \sin (b) & \cos (b)
    \end{pmatrix} 
    \cdot
    \begin{pmatrix}
        v_0 \\
        v_1
    \end{pmatrix}
\end{equation}


== IDM auf Kreuzungen ==

Die Beschleunigung der Autos wird auch auf den Kreuzungen über das IDM berechnet, es werden also die Position und Geschwindigkeit des vorderen Autos benötigt.
Im Gegensatz zu dem Fahren auf Straßen, ist es hier nicht eindeutig, welches Auto das "vordere" ist.
Um Kollisionen auf den Kreuzungen zu vermeiden werden alle anderen Autos auf der entsprechenden Kreuzung betrachtet, die sich im einem "Sichtfeld" des Autos befinden.
Das Sichtfeld ist vergleichbar mit einem Lichtkegel und wird über zwei Winkel, einen von der Fahrtrichtung des Autos nach links und einen nach rechts, festgelegt.
Im folgenden Bild ist dargestellt, wie in der Methode ''vorderes_auto'' der Klasse ''Kreuzung'' bestimmt wird, ob sich ein Auto im Sichtfeld befindet.

{{ :ss2024:kreuzung_vorderes.png?nolink&300 |}}

Es wird das Auto $A$ betrachtet, das den Abstand zu Auto $B$ prüft, $v_A$ ist dessen Geschwindigkeitsvektor. Dieser ist im Auto-Objekt über den Betrag der Geschwindigkeit und den Winkel des Autos zur x-Achse gespeichert. Der Winkel zur x-Achse $\varphi_A$ ist im Bild in rot zu sehen. Zwischen den Mittelpunkten beider Autos gibt es eine Abstandgerade, im Bild schwarz. Durch die Abstände der Punkte der beiden Autos in x- und y-Richtung wird über den Arcustangens der Winkel$\varphi_{Abstand}$ der Verbindungsgeraden zur x-Achse bestimmt. Wenn die Differenz von $\varphi_A$ und $\varphi_{Abstand}$ kleiner ist, als der Winkel des Sichtfeldes, wird der Abstand der beiden Autos als Betrag des Vektors vom Mittelpunkt von $A$ zum Mittelpunkt von $B$ berechnet. Ist dieser Betrag kleiner als der bisher gespeicherte kleinste Abstand, wird stattdessen dieser als neuer kleinster Abstand, und das Auto $B$ als vorderes Autos gespeichert. Nachdem alle Autos auf der Kreuzung so überprüft wurden, werden das ""vordere" Auto und der kleinste Abstand zurückgegeben.

Die Position des vorderen Autos für die Formel des IDM wird aus dem zurückgegebenen Abstand und Position des Autos bestimmt. Falls sich keine weiteren Autos auf der Kreuzung befinden und die Route des betrachteten Autos nicht an der Kreuzung endet, wird als Position die Position des letzten Autos in der nächsten Straße zurückgegeben, falls dort kein Auto vorhanden ist, die Länge der nächsten Straße.

Bei der Geschwindigkeit des vorderen Autos für das IDM wird ebenfalls das vordere Auto durch die Methode ''vorderes_auto'' bestimmt. Die Geschwindigkeit, die in das IDM eingesetzt wird, ist der Anteil der Geschwindigkeit in Richtung des betrachteten Autos. Das ist im folgenden Bild verdeutlicht.

{{ :ss2024:kreuzung_vorder_v.png?nolink&250 |}}

Das betrachtete, rote Auto ist $A$, das "vordere", blaue Auto ist $B$.
Es wird zunächst Winkel $\psi_{Abstand}$ zwischen dem Abstandvektor von $B$ zu $A$ und der x-Achse mithilfe der beiden Punkte der Autos über den Arcustangens bestimmt. Die Differenz zwischen $\psi_{Abstand}$ und $\psi_B$, den Winkel des Autos $B$ ergibt den Winkel $\theta$.
Der Anteil der Geschwindigkeit von Auto $B$ in Richtung von Auto $A$ wird nun berechnet über $v_{B -> A} = -v_B \cos(\theta)$. Dabei sorgt das negative Vorzeichen dafür, dass die übergebene Geschwindigkeit von $B$ positiv ist, wenn $B$ von $A$ weg fährt und negativ, wenn $B$ auf $A$ zu fährt, wie es auch auf den Straßen der Fall ist.

=== Umrechnung der Koordinatensysteme ===

Da bei der Simulation insgesamt drei verschiedene Koordinatensysteme verwendet werden, müssen Koordinaten auch zwischen diesen umgerechnet werden.
Die Koordinatensysteme sind:
    * Das eindimensionale Koordinatensystem innerhalb einer Straße mit der Einheit Meter
    * Das zweidimensionale interne Koordinatensystem mit der **Einheit**
    * Das Koordinatensystem der Visualisierung mit der Einheit Pixel

== Straßenkoordinatensystem zum internen Koordinatensystem ==

{{ :ss2024:koordinatensystem_strasse.png?nolink&300|}}

Das einfachste Koordinatensystem ist das einer Straße, das nur eine Achse besitzt. Wie schon erwähnt wird eine Position auf einer Straße wird durch eine Koordinate dargestellt, die den Abstand vom Anfang der Straße angibt. Die Umrechnung in das interne zweidimensionale Koordinatensystem erfolgt wie rechts zu sehen:\\
$A$ ist die Anfangs- und $B$ die Endkreuzung einer Straße der Länge $S$, $pos$ die Koordinate auf der Straße. Die Straße bildet mit $\Delta x$ und $\Delta y$ ein rechtwinkliges Dreieck. Der Winkel $\varphi$ wird im Programmcode berechnet über
<code python>
phi = numpy.arctan2(delta_y, delta_x)
</code>
Wichtig ist, dass hier die Funktion ''arctan2'' des Modul numpy verwendet wird, da hier der zurückgegebene Winkel je nach Argumenten zwischen $-\pi$ und $\pi$ liegt, also insgesamt einen ganzen Kreis umfassen kann, während der Funktionswert des Arcustangens ansonsten zwischen $-\frac{\pi}{2}$ und $\frac{\pi}{2}$ liegt. \\
Die x- und y-Koordinaten ''xpos'' und ''ypos'' im zweidimensionalen Koordinatensystem werden berechnet über
<code python>
xpos = self.anfang_gridpos[0] + pos * math.cos(phi) + offset*math.sin(phi)
ypos = self.anfang_gridpos[1] + pos * math.sin(phi) - offset*math.cos(phi)
</code>
''self.anfang_gridpos[0]'' und ''self.anfang_gridpos[1]'' sind für eine Straße x- und y-Koordinate der Anfangskreuzung, im Bild $A$.
''offset'' wird auf 3 gesetzt und so fahren die Autos nicht direkt zwischen den Mittelpunkten der Kreuzungen, sondern sind aus ihrer Sicht etwas nach rechts versetzt, damit die Straßenspuren getrennt voneinander verlaufen.

== Internes Koordinatensystem zur Visualisierung ==

Zum Skalieren der Karte in der Funktion ''karte_zeichnen'' der Datei ''karte.py'' werden zuerst alle Kreuzungen durchgegangen, um die größten und kleinsten vorkommenden Werte der x- und y-Koordinaten im internen Koordinatensystem zu finden. Über die Differenz von größtem und kleinstem Wert erhält man die Spannweite der Werte in x- bzw y-Richtung. Im nächsten Schritt wird die Breite des Fensters abzüglich eines kleinen Randes durch die Spannweite in x-Richtung geteilt, das Ergebnis ist die Hilfsvariable ''LE_x''. Dann wird die Höhe des Fensters abzüglich des Randes durch die Spannweite in y-Richtung geteilt um ''LE_y'' zu erhalten. Der kleinere Wert von ''LE_x'' und ''LE_y'' wird nun als ''LE'' bezeichnet. ''LE'' ist der Faktor, der beschreibt, wie viele Pixel auf dem Bildschirm einem Meter im inneren Koordinatensystem entsprechen, und ist damit für die Umrechnung der Koordinatensysteme zentral.
Ebenfalls wichtig sind der Mittelpunkt des internen Koordinatensystems in x-Richtung ''center_x'' und in y-Richtung ''center_y'', also jeweils die Hälfte der Spannweite in x- bzw. y-Richtung.

Diese drei Variablen werden bei der Koordinatentransformation über der Funktion ''transformiere''  in ''Karte.py'' verwendet. Die Transformation von den inneren Koordinaten zu denen der Visualisierung ist im Code folgendermaßen implementiert und weiter unten grafisch dargestellt:

<code python>
new_x = int( window_width/2 + LE*(x-center_x) )
new_y = int( window_height/2 + LE*(-1*(y-center_y)) )
</code>

Dabei sind ''x'' und ''y'' die Koordinaten des Punktes im internen Koordinatensystem und ''new_x'' und ''new_y'' die Koordinaten in dem der Visualisierung. ''window_width'' ist die Breite und ''window_height'' die Höhe des Fensters in Pixeln.
Bei der y-Koordinate wird mit –1 multipliziert, da in Pygame die y-Achse nach unten zeigt, während im internen Koordinatensystem die y-Achse nach oben zeigt.
Die neuen Werte werden zu ganzen Zahlen gerundet, weil sie Pixeln auf dem Bildschirm entsprechen.

{{ :ss2024:transformation_koordinatensystem.png?nolink&650 |}}

=== Ampeln ===

Ampeln besitzen nur die Ampelphasen //rot// und //grün// und die Grünphase jeder Ampel ist unabhängig von der Kreuzung gleich lang.
Der Grund für diese vereinfachten Ampeln ist zum Einen, dass sie von Beginn an nicht im Fokus des Projektes standen.
Zum Anderen sind in der Realität das Vorhandensein und die Taktung von Ampeln von dem konkreten Straßennetz und dem Verkehr abhängig. Um eine effektive Ampelschaltung zu entwerfen, werden Faktoren wie die Länge der Straßen, die Geschwindigkeiten der Autos, die Hauptverkehrsrichtung zu bestimmten Tageszeiten und die angrenzenden Ampeln berücksichtigt. Unsere Simulation sollte aber für verschiedene Straßennetze funktionieren.

''Ampel'' ist eine innere Klasse, innerhalb der Klasse ''Kreuzung''. Die Kreuzungen besitzen eine Liste aller ihrer Ampeln, wobei jede Ampel einer eingehenden Straße zugeordnet ist.
Die Ampeln bringen die Autos zum Anhalten, indem sie sich selbst zum Ende der Liste ''autos'' der ihr zugeordneten Straße hinzufügen. Da die Objekte eine Position auf der Straße, kurz vor Beginn der Kreuzung und eine Geschwindigkeit von Null besitzen, werden sie von den Autos auf der Straße wie ein vorderes Autos behandelt, ein Auto bremst also ab, wenn es sich der Ampel nähert. Wenn die Phase der Ampeln sich auf grün ändert, entfernt sich die Ampel aus der ''autos''-Liste ihrer Straße, wodurch das vorderste Autos wieder beschleunigen kann. Die Schaltung der Ampeln erfolgt über die Methode ''schalte'' der Klasse ''Ampel''.

In der Realität werden in der Regel bei einer Kreuzung mit vier Eingängen die Ampeln von gegenüberliegenden Straßen gleichzeitig grün. In der Simulation wird dieses Verhalten für eine beliebige Anzahl an Eingängen verallgemeinert, indem die Eingänge einer Kreuzung jeweils Paare bilden.
In der Methode ''baue_ampeln'' der Klasse ''Kreuzung'', die im Hauptprogramm nach Erschaffen der Straßen für jedes Objekt vom Typ Kreuzung aufgerufen wird, werden dazu die Eingänge der Kreuzungen zunächst nach ihrem Winkel sortiert.
Danach wird aus der sortierten Liste jedem Eingang der ersten Hälfte der entsprechende Eingang der zweiten Hälfte der Liste zugeordnet. Für beide Straßen wird nun eine Ampel erschaffen, eine Liste aus beiden Ampeln bildet ein Ampelpaar. Bei einer ungeraden Anzahl von Eingängen bleibt eine Ampel ohne Gegenstück, zählt jedoch auch als Ampelpaar.
Diese Ampelpaar-Listen werden zu einer übergeordneten Liste hinzugefügt, welche die Liste ''ampeln'' der Kreuzungsobjektes ist. Anschließen wird das erste Ampelpaar auf grün geschaltet.

Bei Start der Hauptschleife wird in jedem Durchlauf über die Funktion ''schalte_ampeln'' für jedes Kreuzungsobjekt die Methode ''ampeltick'' aufgerufen. In dieser Methode die Variable ''ampelzaehler'' um Eins erhöht, sodass ''ampelzaehler'' die vergangenen Ticks seit der letzten Schaltung zählt. Nach einer in der Kreuzung-Datei festgelegten Anzahl von Ticks wird der Ampelzähler auf Null zurückgesetzt und aus der Variablen ''ampelpaar'', die den Index des grünen Ampelpaars in der Liste ''ampeln'' speichert, der Index des nächsten grünen Ampelpaares bestimmt. Das grüne Ampelpaar wird geändert, indem bei dem alten und dem neuen Ampelpaar die Methode ''schalte'' aufgerufen wird.

Im Folgenden sieht man zum Vergleich die Ampelphasen für eine klassische Kreuzung mit vier Eingängen, und eine für eine Kreuzung mit unregelmäßigen Eingängen. Die Straßenpaare sind dabei farbig markiert.

{{ :ss2024:ampeln_kreuzung_4.gif?nolink&600 | Ampeln an Kreuzungen mit vier Eingängen.}} {{ :ss2024:kreuzung_5.gif?nolink&600 | Ampeln an Kreuzung mit fünf unregelmäßigen Eingängen.}}



===== Projektplanung =====
===Projektziele===
Mit der wachsender Bevölkerung in urbanen Zentren steigt auch die Wichtigkeit, bestehende Straßen und Verkehrsnetze möglichst effizient zu nutzen. Unsere Simulation hat als Zielsetzung, eine Grundlage zu bieten die zum Austesten verschiedener Möglichkeiten auf den Individualverkehr einzuwirken genutzt werden kann. Idee war, sowohl das Fahrverhalten als auch den Straßenplan inklusive Ampeln und Geschwindigkeitsregulierungen unabhängig voneinander veränderlich zu machen und somit die Auswirkungen einzelner Faktoren auf Staus, Durchschnittsgeschwindigkeit und Unfallraten abschätzen zu können. Stück für Stück wollten wir in die Simulation mehr Facetten einbauen und sie realitätsnäher werden lassen, um irgendwann auch echte Straßennetze zu simulieren. 

===Projektverlauf===

Nachdem sich die Gruppe gefunden und auf ein Thema geeinigt hatte, legten wir erstmal die grundlegende Struktur fest, Straßen, Autos und Kreuzungen. Anschließend teilten wir uns in zwei Teams, die jeweils an ihren eigenen Funktionen arbeiteten. Zuerst haben wir uns auf simple Dinge wie das Fahren und Beschleunigen der Autos konzentriert. Dann wurde Abbiegen, aber ohne dabei auf die Kreuzung zu fahren, hinzugefügt. Außerdem verbesserten wir unsere Methode, die Geschwindigkeit der Autos anzupassen mit dem Intelligent Driver Model. Danach arbeiteten wir an immer komplexeren Teilen der Simulation, wie der Kurvenberechnung, Parametrisierung und den Ampeln. Viel Zeit wurde natürlich auch mit Bugfixing verbracht. 

=== Bekannte Probleme ===

Die Simulation funktioniert noch nicht vollkommen fehlerfrei, es gibt noch einzelne Probleme beim Verhalten der Autos.
Die zwei Probleme treten in Bezug auf Kreuzungen auf. Zum Einen gibt es noch keine funktionierende Möglichkeit für die Autos, von einer Straße aus den Abstand zu Autos in der nächsten Kreuzung zu prüfen. Das führt dazu, dass sich zum Teil sehr schnell auf Kreuzungen zu bewegen und sehr plötzlich abbremsen, sobald sie auf die Kreuzung fahren. Dabei überlappen sich die Autos auch häufig. \\
Ein anderes Problem ist das Auftreten sogenannter //Deadlocks//. In unserer Simulation bedeutet dass, das mehrere Autos sich gegenseitig blockieren, und so alle beteiligten Autos stehen bleiben.Es wurde versucht das Sichtfeld anzupassen, und eine "rechts-vor-links"-Regel einzubauen, indem der Winkel des Sichtfeldes nach links auf einen kleinen Winkel, wie $\frac{\pi}{8}$ und der des Sichtfeldes nach rechts auf einen größeren, wie $\frac{\pi}{4}$, gesetzt wird. Dadurch blockieren Sich die Autos zwar seltener, aber es gibt immer noch Situationen, in denen das vorkommt. \\
Das Problem śolcher Deadlocks ist bei ähnlichen Simulationen bekannt, allerdings fehlte uns die Zeit, dazu Lösungsansätze zu implementieren.

===Perspektiven===

==Unterschiedliche Autos==
Momentan haben alle Autos, die sich in unserer Simulation bewegen, das selbe Fahrverhalten. Allerdings könnten durch kleine Veränderungen unterschiedliche Fahrstile simuliert werden. Beispielsweise könnten einige Autos immer etwas über dem Tempolimit fahren, dichter auf andere aufrücken oder besonders großen Abstand halten. Somit könnte man untersuchen, wie sich der Anteil an aggressiven Fahrer*innen auf den Gesamtverkehrsfluss auswirkt. 

==Dynamische Wegfindung== 
Auf vollen Straßen bilden sich in der Wirklichkeit Staus, die einzelne Fahrer*innen gerne umfahren. Anstatt bei der Wegfindung nur die Länge der Straße zu betrachten, könnte als zusätzlicher Faktor dazu kommen, wie ausgelastet sie ist. Würde ab einer bestimmten Autozahl die Länge der Straße in der Wegfindung zu z.B. 150% gewichtet werden, dann führen die Autos eventuell Umwege, um sie zu vermeiden. Genau so könnte man auch verschiedene Höchstgeschwindigkeiten auf unterschiedlichen Straßen etablieren.

==Mehrspurige Straßen==
Die jetzigen Straßen-Objekte sind alle einspurig, das bedeutet Autos können einander nicht überholen und auf jede Straße passen auf den gleichen Längenabschnitt immer die gleiche Menge an Autos. Man könnte, um mehrspurige Straßen zu simulieren, mehrere Straßen-Objekte mit der gleichen Anfangs- und Endkreuzung parallel zueinander platzieren. Dazu müsste man das Modell so erweitern, dass die Autos auf die parallelen Straßenobjekte wechseln können. So könnte man auch Straßen mit unterschiedlicher Breite simulieren, und untersuchen, welchen Effekt zusätzliche Spuren auf den Verkehr haben.

==== Fazit / Reflexion ====

===Reflexion===
Wir hatten alle viel Spaß bei dem Projekt und haben vieles dazu gelernt in Sachen Simulationsdarstellung und Programmierung. Auch möchten wir – nicht ohne stolz – vermerken, dass unsere Gruppe bis zum Schluss durchgehalten hat und keine Mitglieder verloren gegangen sind. Es ist auch positiv zu vermerken, dass die Autos fahren und das grundlegende Modell funktioniert – auch wenn verschiedenste Spielereien leider nicht umgesetzt werden konnten. Auch die Ampeln funktionieren und das Modell wäre für  weitere Modifikationen und Simulationen zu gebrauchen. 
 

Der Kenntnisstand zum Programmieren war in unserer Gruppe sehr unterschiedlich. Dennoch haben wir es geschafft, gut zusammenzuarbeiten und jeden zu inkludieren. Auch die Aufteilung in ein Visualisierungsteam und ein Systemteam war sinnvoll und effektiv.  So war es uns möglich an beidem gleichzeitig zu arbeiten. Wir haben es außerdem geschafft respektvoll Meinungsverschiedenheiten zu klären und uns gegenseitig zuzuhören und den Ideen den Raum zu geben, den sie zum Wachsen brauchten. 
Es gab aber auch Dinge, die wir hätten besser machen können.


Gerade zu Beginn haben wir sehr lange Diskussionen geführt, die man definitiv hätte kürzer halten können. Das hat uns teilweise sehr viel Zeit gekostet, insbesondere, da es bei den Diskussionen meist um weniger wichtige Details ging. Allgemein hätte innerhalb der Gruppe mehr und effizienter kommuniziert werden können. Es gab Situationen, in denen unklar war, was jetzt wo abgespeichert war und in denen nicht klar war, wer was macht. Da die Gruppe in zwei Teile (einen für die Visualisierung und einen fürs System da hinter) aufgeteilt war kam es so teilweise zu der Situation, dass sich Menschen gegenseitig beim Arbeiten am selben Dokument blockiert haben. 


Auch gab es immer wieder das Phänomen, dass es Bugs gab, an denen einzelne Gruppenmitglieder sehr lange herum getüftelt haben und sehr lange gebraucht haben, bis sie sich zum Fragen der Projektleitung durchringen konnten. Das hat viel Zeit in Anspruch genommen, die an anderer Stelle besser investiert hätte werden können. Dies hätte von Seiten dieser Mitglieder besser laufen können. Auch wäre eine bessere Kommunikation außerhalb der Projektzeiten gut gewesen.


Wir haben sehr lange an der Kreuzungskurve gearbeitet, die man einfacher hätte lösen können. Dies hat Zeit gekostet, die man – rückblickend betrachtet – besser in andere Features hätte stecken können, etwa in die Gelbschaltung der Ampeln, individuelle Fahrer*innen oder Unfälle. 
 
Allgemein haben wir den zeitlichen Aufwand etwas unterschätzt und deshalb viel Zeit mit Gedankenspielereien verbracht. Das hätte mit mehr Erfahrung vermieden werden können.

Es gibt auch Dinge, die nicht gut funktionieren. Zum Beispiel kann es sein, dass sich zwei Autos auf einer Kreuzung gegenseitig blockieren und stehen bleiben. Auch sind die Autos lange Zeit nicht auf der visuellen Straße gefahren, was aber gefixt werden konnte. Auch das lange Arbeiten an Schönheitsfehlern hätte vermieden werden können. 

Um das Projekt zu vervollständigen hätte man noch mehrere Dinge hinzufügen können. So gab es beispielsweise die Idee, sich an realen Verkehrssimulationen zu orientieren. Man könnte auch Verkehrsunfälle oder egoistisches Fahrverhalten einbauen, um das Modell realistischer zu gestalten. Auch das Einbauen von Gelbphasen oder  Stau wäre denkbar. Des Weiteren könnte man diverse Verkehrsregeln implementieren und echte Straßennetze verwenden.

===Fazit===
Allgemein würden wir das Projekt als gelungen beschreiben. Wir haben zwar nicht vollständig das geschafft, was wir vorhatten, aber das grobe Modell funktioniert. Als Ergänzungen wären noch vieles denkbar zum Beispiel Tests auf Fahrerverhalten bei unterschiedlichen Parametern.
Insgesamt sind wir  zufrieden mit unserem Ergebnis. Auf jeden Fall haben wir viel gelernt und würden erkannte Fehler in Zukunft vermeiden.  Wir werden das Projekt vielleicht, wenn wir Lust und Zeit haben, fortsetzen und sind gespannt wie es sich weiterentwickeln wird. Gerne dürfen dies auch auch andere tun :) 
===== Protokolle =====

===22.05.2024===
    * Gruppenfindung
    * Projekt: Verkehrssimulation
    * Grundstruktur überlegt: Autos, Straßen, Kreuzungen
    * Ideenfindung
    * Klärung von Regeln

===29.05.2024===
      * Autos existieren jetzt und können sogar fahren und beschleunigen
      * Straßen:
        - Eigenschaften definiert
        - Methode zum Messen des Abstands
        - Methode: nächstes Auto
      * Pygame-Grundlagen recherchiert und ausprobiert

===05.06.2024===
    * Beschleunigungsmechanismus verändert, damit Autos sich nicht mehr (so oft) rammen
    * Autos messen jetzt den Abstand zum Vorderauto, um ggf. auch auf den nächsten Straßen schauen zu können
    * Ideen zur Wegfindung gesammelt
    * an Visualisierung gearbeitet
    * weiter Pygame ausprobiert
    * erste Gedanken zu Schnittstellen zwischen Visualisierung und Datenstruktur

===12.06.2024===
    * Methode zur Straßengenerierung durch Kreuzungsinitialisierung
    * Klasse Kreuzungen hat jetzt Methode connect (Achtung! Ersetzt alte Liste verbundener Punkte mit neuer, addiert nichts dazu) und Straßenbau
    * Kreuzung braucht nur noch gridpos zur Initialisierung
    * Wegfindungsalgorithmus
    * Visualisierung: Bild für Auto importiert, Straße erstellt, Auto dazu gebracht, auf Straße zu fahren

===19.06.2024 ===
    * Wegfindung getestet (funktioniert, yaay) (bis jetzt aber nur mit allen Straßen mit gleicher Länge)
    * debugging beim gegenseitigen Aufrufen von Straße und Kreuzung
    * Methode, um den Weg aus der Wegfindung in Liste zu verpacken
    * Autographik gedreht, Auto reskaliert
    * Planung Straßennetz
    * Visualisierung verbessert: für Liste von Kreuzungen wird Straßennetz gezeichnet,
      
===26.06.2024===
    * Wegfindung angepasst: jetzt auch mit verschiedenen Straßenlängen
    * Überlegungen zum abbiegen, also Übergabe von Autos von Straße zu Kreuzung zu anderer Straße.
    * (um-)strukturierung des Programmcodes
    * Überlegungen zu intelligenterem Fahrermodell und Implementierung in Auto. 

===03.07.2024===
    * Abbiegeverhalten besprochen
    * die Autos können jetzt die Straße wechseln und fahren, außerdem dabei auf das Auto vor ihnen reagieren
    * Autobild: Hintergrund ist jetzt durchsichtig, Drehen des Bildes funktioniert,  Bild in main eingebunden
    * Programmcode weiter umstrukturiert

===10.07.2024===
    * Formel für Abbiegekurve parametrisiert
    * Darstellungskoordinaten werden jetzt von Straßen/Kreuzungen berechnet
    * Karte wird automatisch skaliert

===26.08.2024===
    * Autos fahren zu einem neuen Ziel, sobald sie ankommen 
    * Class Timer, um Ticks zu messen 
    * Strecken-, Zeit- und Geschwindigkeitsmessung  (wird in einer Liste von Wörterbüchern gespeichert) 
    * Pausieren der Simulation
    * Auto fährt nicht mehr rückwärts

=== 27.08.2024 ===
    * Autos fahren zwischen Kreuzungen entlang
    * Bilder der Autos drehen sich je nach Fahrtrichtung
    * Bilder der Autos werden nach der Größe des Straßennetzes skaliert
    * Autos bleiben auf Straße

===29.08.2024===
    * Kurvenparametrisierung fertig gemacht
    * Mehrere Autos können gespawnt werden
    * Autos blockieren sich nicht mehr an Kreuzung und können sich neue Ziele suchen oder am Ziel parken

===06.09.2024===
    * Methoden vorderpos und vorder_v für die Kreuzungen geschrieben:
      vorderpos gibt Abstand zum nächsten Auto innerhalb eines Sichtfeldes (hier +/-90°) zurück, vorder_v den Anteil der Geschwindigkeit in Richtung des Autos

===07.09.2024===
    * in Strasse vorderpos und vorder_v erweitert: Autos sehen auch andere Autos in der Straße vor ihnen
      
===15.09.2024===
    * Grundfunktion der Ampeln implementiert (wechseln zwischen rot und grün), Verteilung muss noch verbessert werden
    * Fallunterscheidung zum Wechsel zwischen Kreuzungen und Straßen

===17.09.2024===
    * Verteilung der Ampeln: gegenüberliegende Ampeln bilden ein Paar, das gleichzeitig grün wird

===22.09. - 29.09.2024===
    * Dokumentation geschrieben
    * Bugs entfernt
    * kleinere Optimierungen
 


===== Vollständiger Programmcode ====

{{:ss2024:verkehrssimulation.zip| Programmcode}}

===== Quellen =====

[1] M. Treiber, A. Hennecke, D. Helbing, //Congested Traffic States in Empirical Observations and Microscopic Simulations//, II. Institut für Theoretische Physik, Universität Stuttgart, **2000**.

[2] https://en.wikipedia.org/wiki/Intelligent_driver_model
Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Seiten-Werkzeuge
