Lektion 10: Trafiksimulering#

Moment: Objektorienterad design och implementation. Simulering. Flera samverkande klasser.

Uppskattad arbetstid: 12 timmar

Redovisning: Obligatorisk redovisning enligt anvisningar på kurssidan.

Simuleringar#

Ett stort användningsområde för datorer är simuleringar, dvs. att man skapar en datormodell av någon process (i vid bemärkelse) som man vill studera. Det kan röra sig om en modell för vädret eller klimatet, för hur snödrivor bildas kring olika byggnader, för trafikflödet i ett gatunät eller för en värld med sköldpaddor som föds, äter, lever och dör.

Meningen med modellen är att man skall kunna göra förutsägelser om vad som händer om man ändrar olika parametrar (släpper ut mer koldioxid, ändrar byggnadens form, gör en rondell eller ger sköldpaddorna mer mat…).

Det är i regel väsentligt billigare att experimentera med en datormodell än att göra det i verkligheten (bygga en eller flera olika rondeller) eller att göra det med fysiska modeller (bygga modellhus och blåsa potatismjöl på dem i en vindtunnel).

När man bygger modeller så måste man i regel förenkla och bortse från många detaljer som man inte tror har någon stor effekt.

Ett sätt att göra simuleringar är att dela upp tiden i ett antal diskreta tidssteg. Man utgår från ett starttillstånd och stegar sig sedan fram i tiden och noterar vad som händer i varje tidssteg:

# skapa komponenterna
time = 0
while time < final_time:
    time = time + 1
    # uppdatera alla komponenter
    # presentera tillståndet (eventuellt)

Ibland kan man veta exakt vad som sker i varje steg men oftast har man bara approximationer. Dessutom kan det finnas ett visst mått av slump som man får approximera med någon sannolikhet. Man vet till exempel sällan exakt vid vilka tidpunkter ett fordon anländer till en rondell men man kan ha mätt upp en intensitet så att man har en sannolikhet för att ett fordon skall anlända ett visst tidssteg.

Problembeskrivning#

Programmet ska simulera trafikflödet i olika typer av trafiksystem. Ett trafiksystem består, i vårt fall, av körfält (oftast kallat filer), trafiksignaler och köer. Vägar byggs upp av filer men vi kommer inte ha några vägobjekt.

Exempel 1#

En väg med en trafiksignal:

../../_images/system1.png

Exempel 2#

En väg med en svängfil och två ljussignaler:

../../_images/system2.png

Datormodell#

Ett trafiksystem ska byggas upp av två generella komponenter: trafikljus (klassen Light) och körfält (klassen Lane). Det innehåller också ett varierande antal fordonsobjekt (klassen Vehicle). Vi kommer också behöva köer men sådana representeras enkelt med listor. Vidare används klassen DestinationGenerator för att simulera ankomster av fordon till systemet. Denna sista klass får du färdig i övningen. Filen trafficComponents.py innehåller skal till klasserna Vehicle, Lane och Light. Du kan kopiera filen och fylla på med kod där det behövs. Se avsnittet ”Lämplig arbetsgång” nedan.

Klassen Vehicle#

Klassen Vehicle är mycket simpel. Dess uppgift är bara att hålla reda på när fordonet skapades och vart det ska. För detta räcker det med två instansvariabler, t.ex. benämnda destination och borntime.

Ett fordon behöver alltså inte veta var det är, inte titta på signaler och inte kunna se andra fordon. Fordonen kan betraktas som pjäser som flyttas av ”någon annan”.

Det behövs således bara en konstruktor som tar emot destination och födelsetid. Om man vill kan man lägga till en __str__-metod.

Klassen DestinationGenerator#

Denna klass används för att simulera ankomster av nya fordon till trafiksystemet. Varje anrop till dess step-metod returnerar antingen None, som anger att inget fordon kom detta steg, eller en destination ('W' eller 'S').

Klassen skulle kunna baseras på uppmätta eller uppskattade intensiteter vid olika tidpunkter på dygnet, men i vårt fall returnerar den en förutbestämd sekvens. Detta gör det enklare att förutsäga resultatet och därmed också kontrollera att programmet är korrekt.

Klassen är helt given och behöver inte ändras. Den kan hämtas här.

Klassen Light#

Klassen används för att representera trafiksignaler. Se diskussion och specifikation av klassen.

Klassen Lane#

En fil är en struktur som innehåller ett antal fordon och ett antal tomrum. Fordonen kan bara komma in i början och lämna i slutet av filen dvs. filen är som ett ”rör”:

../../_images/lane0.png

Se diskussion och specifikation av klassen.

Anmärkning: I fortsättningen använder vi ordet fil eller fil-objekt för att beteckna ett körfält och datafil eller Python-fil för att beteckna filer i datorns filsystem.

Klassen TrafficSystem#

Denna klass definierar ett specifikt trafiksystem. Den håller reda på vilka filer och vilka signaler som ingår och hur fordonen ska flyttas genom systemet.

För att t.ex. representera systemet i exempel 1 behövs två filer och en signal:

../../_images/system1Implementation.png

medan exempel 2 kräver 3 filer och 2 signaler:

../../_images/system2Implementation.png

Se beskrivningen av klassen !

Obligatorisk uppgift: Det första systemet#

Du ska simulera systemet i exempel 1:

../../_images/system1.png

dvs. ett system med två filer och en trafiksignal.

Lämplig arbetsgång#

  1. Kopiera Pythonfilen trafficComponents.py. Den innehåller skal till klasserna Vehicle, Lane och Light. Dessutom innehåller den funktioner som demonstrerar dessa klasser (samma exempelkod som finns i beskrivningarna av klasserna).

  2. Implementera klasserna Vehicle, Lane och Light. Kör demonstrationsmetoderna och kontrollera att du får rätt utskrifter!

  3. Kopiera Pythonfilen destinations.py (om du inte redan gjort det). Den innehåller bara klassen DestinationGenerator. Du behöver inte göra några ändringar i denna klass.

  4. Kopiera Pythonfilen trafficSystem0.py. Denna fil innehåller ett skal till klassen TrafficSystem samt en färdigskriven main-funktion.

  5. Skriv klart klassen TrafficSystem:

    1. Skriv konstruktorn som skapar två filer, en signal och ett DestinationGenerator-objekt.

    2. Skriv snapshot()-metoden. Basera den på __str__-metoderna i de olika komponenterna.

    3. Skriv step-metoden så här:

      1. Ta ut första fordonet från den första (vänstra) filen i figuren.

      2. Stega den första filen med dess step-metod.

      3. Om signalen är grön, flytta då det första fordonet i den andra (högra) filen till den första filen.

      4. Stega ljussignalen med dess step-metod.

      5. Stega den andra filen.

      6. Anropa step-metoden i DestinationGenerator-objektet. Om denna returnerar en destination (dvs. något annat än None) så skapa ett fordon med denna destination och lägg det sist i den andra filen.

  6. Testkör! Nu bör du se hur fordonen glider genom systemet och hur signalen skiftar färg.

  7. Det finns ett problem: Om det redan ligger ett fordon på sista platsen i den andra filen kommer detta att tappas bort när vi lägger ett nytt där. För att undvika det ska du organisera en kö för fordon som väntar på att komma in i filen. Lägg till ytterligare en instansvariabel av listtyp för detta. Kön ska också skrivas ut av snapshot-metoden.

    Tips: Koden blir enklast om man alltid placerar tillkommande fordon i kön och sedan hämtar det första från kön om det är ledigt på sista platsen i filen.

    Se till att du inte skapar fordon med destination None och lägger dem i kön!

Så här kan en körning se ut:


    [.....] (G) [.....]   []
    [.....] (G) [....S]   []
    [.....] (G) [...SS]   []
    [.....] (G) [..SSS]   []
    [.....] (G) [.SSSS]   []
    [.....] (G) [SSSSS]   []
    [....S] (G) [SSSSW]   []
    [...SS] (G) [SSSWS]   []
    [..SSS] (R) [SSWSS]   []
    [.SSS.] (R) [SSWSS]   ['S']
    [SSS..] (G) [SSWSS]   ['S', 'W']
    [SS..S] (G) [SWSSS]   ['W', 'W']
    [S..SS] (G) [WSSSW]   ['W', 'S']
    [..SSW] (G) [SSSWW]   ['S', 'W']
    [.SSWS] (G) [SSWWS]   ['W', 'S']
    [SSWSS] (G) [SWWSW]   ['S', 'S']
    [SWSSS] (G) [WWSWS]   ['S', 'S']
    [WSSSW] (G) [WSWSS]   ['S', 'W']
    [SSSWW] (R) [SWSSS]   ['W', 'S']
    [SSWW.] (R) [SWSSS]   ['W', 'S', 'W']
    [SWW..] (G) [SWSSS]   ['W', 'S', 'W', 'W']
    [WW..S] (G) [WSSSW]   ['S', 'W', 'W', 'S']
    [W..SW] (G) [SSSWS]   ['W', 'W', 'S', 'W']
    [..SWS] (G) [SSWSW]   ['W', 'S', 'W', 'W']
    [.SWSS] (G) [SWSWW]   ['S', 'W', 'W']
    [SWSSS] (G) [WSWWS]   ['W', 'W', 'S']
    [WSSSW] (G) [SWWSW]   ['W', 'S']
    [SSSWS] (G) [WWSWW]   ['S']
    [SSWSW] (R) [WSWWS]   []
    [SWSW.] (R) [WSWWS]   []
    [WSW..] (G) [WSWWS]   ['W']
    [SW..W] (G) [SWWSW]   ['S']
    [W..WS] (G) [WWSWS]   []
    [..WSW] (G) [WSWS.]   []

Innan du redovisar#

  1. Se till att koden följer stilguiden!

  2. Se till att programmet producerar utskrifter enligt ovanstående exempel.

Frivillig uppgift: Det andra systemet#

Implementera systemet i exempel 2, dvs. följande:

../../_images/forenkladKorsning.png

Trafiksystemet ska således bestå av tre filer (lane, lane_west och lane_south) och ljussignalerna light_west och light_south (tidigare kallade s1 och s2):

../../_images/korsningImplementation.png

Det kan vara snyggt att ha korta körfiler efter (till vänster om) signalerna så att man ser hur fordonen passerar.

Vid punkten E finns det en kö (ej utritad).

Vid ett tidssteg sker följande saker, i denna ordning:

  • De första fordonen i lane_west och lane_south passerar sina signaler (om signalen är grön och det finns något fordon på första plats i filen).

  • Filerna lane_west och lane_south stegas.

  • Ett fordon omedelbart till höger om X flyttas till lane_west eller lane_south beroende på dess destination (W eller S). Om platsen på destinationsfilen inte är ledig står fordonet kvar och delningspunkten räknas som blockerad.

  • Filen lane stegas.

  • Ett fordon anländer till systemet vid punkten E och ställs i kön.

  • Om sista platsen i lane är ledig och det finns fordon i kön tas första från kön till sista platsen i lane.

  • Ljussignalerna stegas.

En simulering består alltså av en tidsstegning där ovanstående saker händer. Det kan vara praktiskt att låta din step-metod i sin tur anropa olika metoder du själv introducerar för att ta hand om olika delar. Det kan minska mängden upprepad kod i step och göra den mer överskådlig.

Observera att klasserna Lane och Light inte ska behöva ändras - endast TrafficSystem behöver göras om.

Indata till en simulering#

Programmet styrs av följande indata:

  • takten som fordon anländer till E,

  • andelen fordon som skall svänga, dvs. ha S som destination,

  • längderna på filerna och

  • ljussignalernas karakteristik (period och grönperiod).

De två första värdena varierar vanligen med tiden. Detta hanteras av klassen DestinationGenerator. I verkliga simuleringar skulle klassen producera fordon enligt uppmätta intensiteter men, för att ni ska få kontrollerbara resultat, ger denna version samma sekvens varje gång.

Värdena i de två sista punkterna, dvs. längderna på filerna och ljussignalernas karakteristik, får du bestämma själv. Prova dock nedanstående och jämför med den statistik som visas längre ner.

lane_length = 11  # Length first (rightmost) lane
lanews_length = 8  # Length lanes in front of signals
light_period = 14  # Period for the lights
west_green = 6  # Green period westbound light
south_green = 4  # Green period southbound light

Resultat av en körning#

  1. Statistik innehållande:

    • Genomsnittliga, minimala och maximala tider (antal tidssteg) för fordon att passera respektive ljussignal (väst/syd).

    • Andel tidssteg som delningspunkten X varit blockerad. Med blockerad menas att det inte går flytta ett fordon från filen lane på grund av att sista platsen i dess destinationsfil är upptagen.

    • Andel tidssteg som det funnits fordon i kön vid startpunkten (E).

    Samla tiderna för fordon som lämnar systemet i två list-objekt, ett för vardera utgång, och använd dessa för att ta fram statistiken. Använd antingen en egen modul med statistik-metoder eller standard-modulen statistics.

    Statistiken skall skrivas ut av metoden print_statistics i TrafficSystem. Metoden skall kunna anropas när som helst under simuleringen. Exempel på utskrift:

    
Statistics after 100 timesteps:

Created vehicles:   48
In system       :    8

At exit         West        South
Vehicles out:    21          19
Minimal time:    20          21
Maximal time:    38          53
Mean time   :    27.6        39.3
Median time :    27.0        43.0

Blocked     : 18.0%
Queue       : 14.0%

  2. Ögonblicksbilder av systemet som skrivs ut av metoden snapshot.

    Exempel på en sekvens av ögonblicksbilder:

    
(G) [.....W..] [SWWSWSSSWSW]  []
(R) [SSSSS.SS]

(R) [....W...] [WWSWSSSWSWW]  []
(R) [SSSSSSSS]

(R) [...W...W] [WSWSSSWSWWS]  []
(R) [SSSSSSSS]

(R) [..W...WW] [SWSSSWSWWSW]  []
(R) [SSSSSSSS]

(R) [.W...WW.]*[SWSSSWSWWSW]  ['W']
(R) [SSSSSSSS]

(R) [W...WW..]*[SWSSSWSWWSW]  ['W']
(R) [SSSSSSSS]

(R) [W..WW...]*[SWSSSWSWWSW]  ['W', 'S']
(R) [SSSSSSSS]

    I de tre sista stegen är delningspunkten blockerad (indikeras av *-tecknet) och dessutom finns det först ett och sedan två fordon i kön.