Nagel-Schreckenberg-Simulation

3 Minuten zum Lesen

Das Modell

Das Nagel-Schreckenberg-Modell ist eine minimalistische Abbildung der Bewegung von Fahrzeugen, das aber einige wesentliche Aspekte des Straßenverkehrs erfasst.

Die Fahrzeugbewegung wird von wenigen Grundregeln bestimmt.

  1. Versuche zu beschleunigen bis die Maximalgeschwindigkeit erreicht ist.
  2. Vermeide Kollisionen mit dem vorausfahrenden Fahrzeug.
  3. Nutze die mögliche Geschwindigkeit nicht optimal (zufälliges Trödeln).

In Julia lässt sich das mit zwei Datentypen und zwei Update-Funktionen in wenigen Code-Zeilen abbilden.

Datenstrukturen

Der Typ Vehicle ist veränderlich und speichert Position und Geschwindigkeit. Der Typ Circuit nimmt die Fahrzeuge auf und ist bestimmt durch eine Länge. Es gelten zyklische Randbedingungen, d.h. die Fahrstrecke ist geschlossen, so dass das letzte Fahrzeug das vorausfahrende Fahrzeug des ersten Fahrzeugs ist.

Für Vehicle wird ein Konstruktor zur Verfügung gestellt, der ein stehendes Fahrzeug an der angegebenen Position erzeugt, sowie ein weiterer, der ein Fahrzeug in einem bestimmten Abstand von einem weiteren Fahrzeug erzeugt. Im Konstruktor von Circuit findet sich eine sogenannte Comprehension. Sie ist ein sehr vielseitiges Sprachelement und ist eine Erzeugungsvorschrift für einen Array (Feld). Der Container vehicles wird mit Fahrzeugen im Abstand von deltax aufgefüllt.

mutable struct Vehicle
    pos::Int
    vel::Int
end

Vehicle(pos) = Vehicle(pos, 0)

function Vehicle(veh::Vehicle, offset::Int)
    Vehicle(veh.pos + offset, veh.vel)
end

struct Circuit
    vehicles::Vector{Vehicle}
    circuitlength::Int
end

"""
    Circuit(circuitlength::Int; deltax::Int = 2)

Set up a circuit with vehicles. `circuitlength`: number of cells. 
`deltax` distance between two consecutive vehicles.
"""
function Circuit(circuitlength::Int; deltax::Int = 2)
    vehicles = [Vehicle(pos) for pos in 1:deltax:circuitlength]
    Circuit(vehicles, circuitlength)
end

Fortbewegung der Fahrzeuge

Es gibt zwei Methoden zur Funktion update!, je nachdem, ob ein einzelnes Fahrzeug oder alle Fahrzeuge in einem Kurs bewegt werden sollen.

# update the position and velocity of a vehicle
function update!(veh::Vehicle,
                 delta::Int;
                 velmax::Int = 5,
                 sdp::AbstractFloat = 0.1)
    # set new velocity
    veh.vel = min(veh.vel + 1, velmax, delta - 1)
    rand() < sdp && veh.vel > 0 && (veh.vel -= 1)
    # set new position
    veh.pos += veh.vel
    return veh.pos, veh.vel
end

""" 
    update!(circuit, vmax, sdp)

update vehicle positions

`circuit`: container with vehicles
`velmax`: maximum velocity, e.g. [2..deltax]
`sdp`   slow down probability, e.g. 0.2
"""
function update!(circuit::Circuit,
                 velmax::Int,
                 sdp::AbstractFloat)
    # The last vehicle in `cont` is a copy of the first element as the vehicles
    # move in a closed circle
    clength = circuit.circuitlength
    nveh = length(circuit.vehicles)
    for i in 1:nveh - 1
        delta = circuit.vehicles[i + 1].pos - circuit.vehicles[i].pos
        update!(circuit.vehicles[i], delta, velmax = velmax, sdp = sdp)
    end
    circuit.vehicles[end] = Vehicle(circuit.vehicles[1], clength)
end

Die Struktur NaSchModell fasst einen Kurs und die Parameter der Fahrzeugbewegung zusammen:

"""
    NaSchModel(circuit::Circuit, velmax::Int, sdp::AbstractFloat)

set up a NaSch model 

# Arguments
`circuit`: circuit with vehicles
`velmax` maximum velocity
`sdp`: slow down probalility
`nstep: number of update steps
"""
mutable struct NaSchModel
    circuit::Circuit
    velmax::Int
    sdp::AbstractFloat
end

Die Funktion run! bewegt die Fahrzeuge in mehreren Runden.

"""
    run!(m::NaSchModel, nstep::Int)

forward the state of `m` by `nstep` steps, return arrays containing the vehicle
positions and the number of the update step
"""
function run!(m::NaSchModel, nstep::Int)
    vpos = Vector{Int}()
    vy = Vector{Int}()
    nveh = lastindex(m.circuit.vehicles)
    for i = 1:nstep
        update!(m.circuit, m.velmax, m.sdp)
        append!(vy, fill(i, nveh))
        append!(vpos, [v.pos for v in m.circuit.vehicles])
    end
    vpos, vy
end

Simulationslauf

Ein Objekt vom Typ Circuit wird erzeugt und die Fahrzeuge werden in 80 Simulationsschritten fortbewegt.

c = NaSch.Circuit(200, deltax = 5)

# Modell, vmax = 5, Wahrscheinlichkeit der Verzögerung = 0.2
m = NaSch.NaSchModel(c, 5, 0.2)

(vx, vy) = NaSch.run!(m, 80)

Weg-Zeit-Diagramm

using PyPlot; Pm = PyPlot

po = Pm.scatter(vx, vy, s = 0.8)
Pm.title("Weg-Zeit-Diagramm")
Pm.xlabel("Positionen")
Pm.ylabel("Durchlauf (Zeit)");

nasch-ts-plot

Die zunächst gleichmäßig verteilten Fahrzeuge verdichten in unterschiedlichen Bereichen der Strecke. Schließlich bilden sich einige wenige Staubereiche heraus, die sich entgegen der Fahrtrichtung auf der Strecke verschieben.

Modell als iterierbares Objekt

Julia umfasst eine Schnittstelle, mit der sich Strukturen leicht zu iterierbaren Objekten erweitern lassen. Dazu müssen lediglich zwei neue neue Methoden für die Funktion Base.iterate definiert werden. Die erste Methode erwartet ein Argument und dient dazu, das jeweilige Objekt für die Iteration zu initialisieren. Die zweite Methode erwartet zwei Argumente: An erster Stelle wieder das Objekt, dessen Elemente oder Zustände durchlaufen werden sollen, und an zweiter Stelle eine Variable, die diese Zustände kennzeichnet. Wenn das Ende der Iteration erreicht ist, liefert die Methode nothing zurück.

""" 
    Base.iterate(m::NaSchModel)

move the vehicle queue to the beginning of `m.circuit`
"""
function Base.iterate(m::NaSchModel)
    # place the first vehicle in `m.circuit` at 1;
    # keep distances of the following vehicles
    move = -m.circuit.vehicles[1].pos + 1
    for v in m.circuit.vehicles
        v.pos += move
    end
    return(m, 1)
end

""" 
    Base.iterate(m::NaSchModel, step)

move the vehicle queue one step forward
"""
function Base.iterate(m::NaSchModel, step)
    step <= m.nstep || return nothing
    update!(m.circuit, m.velmax, m.sdp)
    return(m, step + 1)
end

Eine Graphik wie oben erreicht man dann durch eine sehr übersichtliche Schleife:

julia> vy = similar(NaSch.pos(m));

julia> for p in enumerate(m)
          fill!(vy, p[1])
          scatter(NaSch.pos(p[2]), vy, s=0.8)
	   end

Julia Version: 1.0.1

Startseite