Observera att detta är en arbetsversion av sidan!
Dölj style3dev.css för att bli av med annoteringarna!

Lektion 10: Trafiksimulering
Denna lektion innehåller Obligatorisk uppgift 5 (OU5)

Moment: Objektorienterad design och implementation. Simulering. Flera samverkande klasser.
Uppskattad arbetstid: Schemalagd handledningstid inkl redovisning: 10 timmar. Utöver det räkna med eget arbete med lika många timmar.
Arbetssätt: Arbeta gärna tillsammans med någon, men skriv egen kod. Diskutera med varandra

Tips: Använd debuggern

Redovisning: Obligatorisk redovisning enligt anvisningar på kurssidan.
Notera att den pythonkod du redovisar skall följa kodningsreglerna

Simuleringar

Ett stort användningsområde för datorer är simuleringar d.v.s. 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 eller åtminstone bara liten 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 True: 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.

Problembeskrivning

Antag att vi skall simulera ett trafikflöde genom en korsning. Exempelvis följande:
Korsningen Kungsängsleden/Valsätravägen och Dag Hammarskölds väg
Trafik kommer från öster (in). Skall vidare västerut (W) eller söderut (S).
Man vet till sällan exakt vid vilka tidpunkter ett fordon anländer till en korsning 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. Flödet av fordon västerut respektive söderut regleras av trafiksignaler.

Program skall skrivas som 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:
system1

Exempel 2

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

Exempel 3

En korsning:
korsning0

Korsningen kontrolleras alltså av de fyra ljussignaler s1, s2, s3 och s4.

Ett problem i denna typ av korsningar är att fordon som kommer från E och vill svänga vänster mot S i korsningen blir blockerade av fordon som kommer från W vilket i sin tur blockerar fordon som vill köra rakt fram.

Exempel 4

För att lösa problemet kan man bygga svängfiler för fordon som kommer från E respektive W och som skall vänster i korsningen d.v.s. man vill ha en korsning av detta utseende:

korsning

Denna korsning har alltså svängfiler kontrollerade av signalerna vid s2 och s5.

En typisk fråga är då hur långa svängfilerna ska göras för att undvika att köerna på dessa växer in i de andra filerna.

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 Destinations för att simulera ankomster av fordon till systemet. Denna sista klass får du färdig i övningen.

Klassen Vehicle

Klassen Vehicle är mycket simpel. Dess uppgift är bara att hålla reda på när fordonet skapades och vart det ska.

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".

Klassen Destinations

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 i 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 d.v.s. filen är som ett "rör":
lane0
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:

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

Se beskrivningen av klassen !

Uppgift 1: Det första systemet

Notera att den pythonkod du redovisar skall följa kodningsreglerna

Ett program skall skrivas som simulerar systemet i exempel 1:

system1

d.v.s. ett system med två filer och en trafiksignal.

Lämplig arbetsgång

  1. Kopiera Pythonfilen trafficComponentsNew.py. Den innehåller de färdiga klasserna Vehicle, Lane och Light. Dessutom innehåller den funktioner som demonstrerar dessa klasser (samma exempelkod som finns i beskrivningarna av klasserna). Testa klasserna genom att köra demonstrationsfunktionerna. Du behöver inte göra några ändringar i dessa klasser.

    Läs igenom koden i respektive klass för att förstå vad de gör.

  2. Kopiera Pythonfilen destinations.py (om du inte redan gjort det). Den innehåller bara klassen Destinations och en funktion som demonstrerar klassen. Kör denna. Du behöver inte göra några ändringar i denna klass.
  3. Kopiera Pythonfilen trafficSystem0.py. Denna fil innehåller ett skal till klassen TrafficSystem samt en färdigskriven main-funktion. Tips: Döp om pythonfilen trafficSystem0.pytill trafficSystem1.py eftersom detta program skall simulera det första systemet. Om du kör programmet upptäcker du att det endast skriver ut tidsstegen 1-100. Programmet skapar ett TrafficSystem-objekt med namnet ts och simulerar därefter 100 tidsteg. I varje tidssteg beräknas hur trafiksystemet ändras (med metoden step) och det görs utskrift (med metoden snapshot).
  4. Skriv klart klassen :
    1. Skriv konstruktorn som skapar två filer, en signal och och ett Destinations-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 så flytta första fordonet på den andra (högra) filen till den första.
      4. Stega signalen med dess step-metod.
      5. Stega den andra filen.
      6. Anropa step-metoden i Destinations-objektet. Om denna returnerar en destination (d.v.s. något annat än None) så skapa ett fordon och lägg det sist på den andra filen.
      Istället för att lösa alla ovan delproblem på en gång, kan det vara bra att lösa ett delproblem itaget och testa detta.
  5. Testkör! Nu bör du se hur fordonen glider genom systemet och hur signalen skiftar färg.
  6. Det finns ett problem: Om det redan ligger ett fordon på sista platsen på 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.

    Se till att du inte lagrar None på 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.] []
Visa och diskutera gärna din lösning för lärare/assistent, innan du går vidare med nästa uppgift!

Uppgift 2: Det andra systemet

Notera att den pythonkod du redovisar skall följa kodningsreglerna

Tips: Börja med göra en kopia av din python-fil trafficSystem1.py (första systemet). Döp kopian till trafficSystem2.py eftersom detta program skall simulera det andra systemet.

korsning

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):

korsningsimplementation

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 (ej utritad).

Vid ett tidssteg kan en eller flera av följande saker hända i denna ordning:

En simulering består alltså av en tidsstegning där ovanstående saker händer. Det är lämpligt att momenten, precis som i verkligheten, utförs i den ordning de står ovan. 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 Vehicle, 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:

De två första värdena varierar vanligen med tiden. Detta hanteras av klassen Destination. 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, d.v.s. 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:
    1. Genomsnittliga, minimala och maximala tider (antal tidssteg) för fordon att passera respektive ljussignal (väst/syd).
    2. 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.
    3. 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 skriv en egen modul med statistik-metoder eller använd pythons standard-modul statistics där finns bl.a. funktionerna min, max, mean och median

    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 systemet med hjälp av 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.

Innan du redovisar

  1. Se till att din pythonkod du redovisar skall följa kodningsreglerna
  2. Kontrollera att all efterfrågad statistik finns med och att resultaten är korrekta!
  3. Se till att programmet producerar utskrifter enligt ovanstående exempel.

Tillbaka