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

Lektion 10: Trafiksimulering. Obligatorisk redovisning 5.1 och 5.2.

Moment: Objektorienterad design och implementation. Simulering. Flera samverkande klasser.
Uppskattad arbetstid: 12 timmar ?
Redovisning: Muntligt för lärare/assistent i två steg enligt information på kurssidan.

Förberedelser

Skapa en mapp för denna lektion med namnet lektion10.

Ladda ned följande i mappen:

Filer att ladda ner
Simulation.java Innehåller en main med en tidsstegsloop som driver simuleringen genom anrop till metoder. Den innehåller också en globalt tillgänglig klocka(Simulation.getTime()).
VehicleGenerator.java Skapar fordon med varierande intensitet. Klassen är helt färdig och skall inte ändras.
Vehicle.java Skal till fordonsklassen. Skall fyllas med kod.
Light.java Skal till ljussignalsklassen. Skall fyllas med kod.
Lane.java Skal till klassen som definierar körfiler. Skall fyllas med kod.
TrafficSystem.java Skal till klassen som ska representera ett trafiksystem med körfiler och signaler.

Se också till att du har tillgång till klassen Measurements som tidigare skrivit till exempel genom att kopiera den till denna mapp.

Läs återigen kodningsreglerna och se till att du följer dem när du börjar koda!

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 rondell) 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 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 kunna simulera trafikflödet i olika typer av trafiksystem.

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 avser man att bygga svängfiler för fordon som kommer från E respektive W och som skall vänster i korsningen dvs man vill ha en korsning av detta utseende:

korsning

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

Datormodell

Ett trafiksystem ska byggas upp av två generella komponenter: trafikljus (klassen Light) och körfiler (klassen Lane). Det innehåller också ett varierande antal fordonsobjekt (klassen Vehicle). Vidare används klassen Simulation för att driva simuleringen och klassen VehicleGeneretor för att generera ny fordon till systemet.

Klassen Vehicle

Se diskussion och specifikation.

Klassen Light

Ett trafikljus kan ha två lägen: "grönt" som tillåter passage och "rött" som förbjuder passage. 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":
lane0
Se diskussion och specifikation.

Anmärkning: I fortsättningen använder vi ordet fil eller fil-objekt för att beteckna en körfil och datafil eller Java-fil för att beteckna filer i datasystemet.

Klassen TrafficSystem

Klassen TrafficSystem definierar ett specifikt trafiksystem dvs 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 !

Klassen Simulation

Klassen Simulation innehåller main-metoden som sköter om tidsstegningen som beskrevs inledningsvis:
skapa komponenterna time = 0 while (true) time = time + 1 uppdatera alla komponenter presentera tillståndet
TrafficSystem tf = new TrafficSystem(); time = 0 while (true) { time = time + 1; tf.step(); tf.print(); }

Väsentliga funktionen av main-metoden.

Klassen tillhandahåller också en globalt tillgänglig klocka genom klassmetoden getTime(). Den kan bl. a. användas av konstruktorn för Vehicle och av metoden isGreen() i klassen Light.

Klassen är given och behöver inte ändras.

Klassen VehicleGenerator

Denna klass används för att generera nya fordon med varierande intensitet och destination. Klassen är helt given och ska inte ändras.

Använd den parameterlösa konstruktorn för att skapa objektet. Varje anrop till metoden step() returnerar sedan antingen ett fordon eller null. Se dokumentationen för en mer detaljerad beskrivning av klassen.

Det första systemet

Du ska simulera systemet i exempel 1:
system1

dvs ett system med två filer och trafiksignal.

Lämplig arbetsgång

  1. Ladda ner Java-filerna om du inte redan gjort det. Programmet (Simulation) går att kompilera och köra direkt även om det inte producerar något av intresse.
  2. Klassen Vehicle kan tills vidare användas som den är given men kom ihåg att den måste kompletteras längre fram.
  3. Implementera metoderna i klassen Lane. Skriv också en main-metod i klassen som visar att metoderna fungerar. Se beskrivningen!
  4. Uppdatera klassen TrafficSystem:
    1. Lägg till instansvariabler för ett fil- och ett fordonsgenerator-objekt.
    2. Skapa filen och och fordonsgeneratorn. Du kan direkt välja en fillängd (10 t ex) och använda den parameterlösa konstruktorn till fordonsgeneratorn.
      (Du behöver inte använda de fördefinierade instansvariablerna för fillängder och signalparametrar - dessa är avsedda för det andra systemet.)
    3. Skriv print-metoden. Den behöver bara skriva ut det som filens toString-metod returnerar.
    4. Skriv stegmetoden så att den börjar med att ta ut första fordonet från filen, därefter stegar filen med dess step-metod och slutligen anropar fordonsgeneratorns stepmetod. Om denna lämnar ifrån sig ett fordon läggs det sist på filen.
    5. Testkör! Nu bör du se hur fordonen glider genom filen.
  5. Implementera klassen Light enligt beskrivningen. Läs specifikationen så att du ser exakt t ex vad dess toString-metod ska returnera!

  6. Uppdatera TrafficSystem med ett trafikljus och en fil till dvs lägg till dessa som instansvariabler och uppdatera konstruktorn och print-metoden.

    Gången i step-metoden blir nu:

    1. Stega den nya filen
    2. Om signalen är grön och det finns ett fordon först på den gamla filen så ska det flyttas från den gamla till den nya.
    3. Stega den gamla filen
    4. Om fordonsgeneratorns step-metod ger ett fordon ut ska det placeras sist på den gamla filen.

    Observera att ordningen i stegningen är viktig. Dock kan det vara snyggare om man börjar med att stega signalen eftersom man då ser att den är grön innan något fordon passerar.

    Nu har det dock uppstått ett problem: Det kan hända att sista platsen på gamla filen inte är ledig när vi vill lägga ett fordon där. Eftersom vi inte får tappa bort fordon organiserar vi en kö med hjälp av ytterligare en instansvariabel ArrayList<Vehicle> queue. Kön ska också skrivas ut av print-metoden. Enklast är att använda arraylistans toString-metod.

    Tips: Enklast kod blir det 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 null-referenser på kön!

  7. Även om det inte behövs för första delen så är det lämpligt att se över klassen Vehicle. Du behöver uppdatera konstruktorn samt get- och toString-metoderna. Du måste också se till att toString-metoden i Lane-klassen använder Vehicle-klassens toString- eller getDestination-metod. Detta är ett måste för del 2 av uppgiften.
  8. Redovisa!

Det andra systemet

Du ska implementera systemet i exempel 2 dvs
korsning

Trafiksystemet ska således bestå av tre filer (lane, laneWest och laneSouth) och ljussignalerna lightWest och lightSouth (tidigare kallade s1 och s2):

korsningsimplementation

Det kan vara snyggt att ha korta körfiler efter signalerna så att man ser hur fordonen passerar.

Vid punkten E finns det en kö (ej utritad) som implementeras med hjälp av en ArrayList.

Instansvariabler för fillängder och signalperioder finns fördefinierade i kodskalet. Använd dessa!

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

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 i ovan.

Observera att klasserna Lane och Light inte behöver ändras - endast TrafficSystem behöver göras om. (I klassen Vehicle behöver toString-metoden modifieras så att den returnerar destinationsbokstaven i stället för X.)

Indata till en simulering

Programmet styrs av följande indata:

De två första värdena (ankomstintensitet och sannolikhet att svänga) varierar med tiden. Detta hanteras av klassen VehicleGenerator. Klassen är helt given och du behöver bara förstå hur den ska användas, inte hur den fungerar.

För de två sista punkterna, dvs längderna på filerna och ljussignalernas karakteristik, finns ett antal fördeklarerade och initierade variabler i TrafficSystem:

private int laneLength = 11; // Length first (rightmost) lane private int laneWSLength = 8; // Length lanes in front of signals private int lightPeriod = 14; // Period for the lights private int lightWestGreen = 6; // Green period westbound light private int lightSouthGreen = 4; // Green period southbaund light
Använd dessa när du skapar Lane- och Light-objekten.

Konstruktorn i den givna koden för TrafficSystem börjar med att försöka läsa en datafil med andra värden för fillängder och signalparametrar men om filen inte finns så behålls de givna värdena. Om du vill kan du kopiera filen properties.txt och lägga den bland dina java-filer.

Orsaken till att man vill definiera dessa egenskaper på en indatafil är att man lätt vill kunna experimentera med olika uppsättningar av värden.

Resultat av en körning

  1. Initial utskrift av simuleringsparametrarna genom metoden printSetup. Exempel:
    Simulation parameters: laneLength : 11 laneWSLength : 8 lightPeriod : 14 lightSouthGreen: 4 lightWestGreen : 6
  2. Statistik innehållande
    1. Genomsnittliga, minimala och maximala tider (antal tidssteg) för fordon att passera ljussignalen lightWest respektive lightSouth.
    2. Andel tidssteg som delningspunkten X varit blockerad. Med blockerad menas att det inte går flytta ett fordon från file lane på grund av att sista platsen i dess destinationsfil är upptagen.
    3. Andel tidssteg som det funnits fordon i kön vid entrypunkten (E).

    Samla tiderna för fordon som lämnar systemet i två Measurements-objekt (nätlektion 7), ett för vardera utgång, och använd dessa för att ta fram statistiken till punkt a). (Komplettera klassen Measurements med en metod för att returnera maxvärdet om du inte redan har gjort det.)

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

    Statistics after 400 timesteps Arrived at E : 164 Total left : 143 Number in the system : 21 Exit west Number: 69 Mean : 30.1 Min : 24 Max : 48 Exit south Number: 74 Mean : 37.5 Min : 24 Max : 59 Percent time step with block: 11.0 Percent time step with queue: 2.3
  3. En enkel ögonblicksbild av systemet vid ett visst tidssteg. Exempel:
    (G) <WW..W..W> <SSW.S..WWS.> Queue: [] (R) <SSSS.SS.>
    Denna utskrift skall göras av metoden print som anropas varje tidssteg från Simulation. Ögonblicksbilder av systemet vid de tre följande tidsstegen. Exempel:
    (G) <W..W..W.> <SW.S..WWS.S> Queue: [] (R) <SSSSSS.S> (R) <..W..W..> <W.S..WWS.SS> Queue: [] (R) <SSSSSSSS> (R) <.W..W..W> <.S..WWS.S.W> Queue: [] (R) <SSSSSSSS>
    Så här kan det se ut om det uppstått en kö:
    (R) <W..WWW..> <SWWWWSSSSWW> Queue: [S, W, W, S] (R) <SSSSSSSS>

Innan du redovisar

Se till att
  1. Koden följer kodningsreglerna!
  2. Klasserna uppfyller dessa specifikationer. Kom ihåg att specifikationerna är heliga! Klasser och metoder ska exakt angivna namn, funktion och parametrar!
  3. Att all efterfrågad statistik finns med.
  4. Metoden print producerar utskrifter enligt ovanstående exempel.

Lämplig arbetsgång och tips

  1. Ladda ner alla filerna enligt lektionssidan. Då finns ett embryo till alla klasser som skall vara med. Koden går att kompilera och det går att köra main-metoden i klassen Simulation men den producerar inte några intressanta utskrifter.
  2. Klassen Vehicle kan, till att börja med, användas precis som den är given.
  3. Klassen Light är enkel och oberoende av alla andra klasser. Skriv och testa den direkt! Kontrollera att du följer specifikationen!
  4. Implementera klassen Lane:
    1. Instansvariabeln Vehicle[] theLane är given. Inga andra instansvariabler behövs.
    2. Skriv en toString-metod. En tom plats (dvs när theLane[i] == null) skall representeras av en punkt medan en plats som har ett fordon används fordonets toString-metod. Så här kan det se ut:
      <X.XX...X..X...X.>
      (toString-metoden i den nedladdade Vehicle-klassen returnerar X.) Använd tecknen < och > för att avgränsa filen.
    3. Metoden step går från vänster till höger och flyttar fram alla fordon utom det första ett steg, under förutsättning att platsen framför är ledig. Resultatet efter ett steg med exemplet ovan blir:
      <XXX...X..X...X..>
      Observera att denna metod inte tar bort fordon från första eller lägger till fordon på sista platsen!
    4. Skriv metoderna getFirst, removeFirst och lastFree enligt specifikationen. De är alla mycket enkla.
    5. Skriv metoden putLast som också är enkel. Metoden ska förhindra att någon lägger ett fordon sist om den platsen är upptagen. Detta är nämligen ett besvärligt fel som gör att fordon tappas bort och statistiken blir felaktig. Det bästa sättet att göra det är att kasta ett undantag som beskrivs i lektion 8. För enkelhetens skull utnyttjar vi den existerande undantagsklassen RuntimeException genom att skriva
      throw new RuntimeException("Last position occupied");
      om sista positionen är upptagen. Programmet avbryts med felutskrift om detta är fallet.
    6. Skriv en main-metod som demonstrerar att metoderna fungerar. Se till att den steppar så långt att ett fordon kommer genom hela filen.

  5. Nu är det dags för att börja med klassen TrafficSystem. Gör först ett system bestående av en fil och en arraylist för att köa fordon som inte går att lägga in på filen. Tag också med fordonsgeneratorn från början.

    Du behöver alltså följande instansvariabler:

    private Lane lane; private VehicleGenerator vg; private ArrayList<Vehicle> queue;

    Dessa måste ges värden i kontruktorn:

    this.loadProperties("properties.txt"); this.vg = new VehicleGenerator("probabilities.txt"); this.lane = new Lane(this.laneLength); this.queue = new ArrayList<Vehicle>();
    (Vi passade här på att ladda in filen properties.txt som ger värden åt de fördefinierade instansvariablerna för fillängder och signalkaraktäristik. Vi utnyttjade också en av dessa instansvariabler för att definiera längden på filen.)

    Innan du kan köra måste du göra några saker i step-metoden. Minimalt är

    lane.step(); Vehicle v = vg.step(); lane.putLast(v);

    Lägg in System.out.println(lane); i print-metoden och kör Simulation!

    Eftersom det inte finns någon mekanism som tar bort fordon från filen kommer den bli full och leda till ett RuntimeException.

    Det är nu lämpligt att använda kön i som ska ta hand om bilar som inte kommer in på filen. Enklast är att alltid lägga v på kön i stället för på filen (kontrollera först att v inte är null!). Om det sedan finns plats på filen och kön inte är tom hämtar man det som ligger först på kön och lägger det på filen.

    Testkör igen!

  6. Lägg sedan övriga komponenter (filer och signaler) en i taget, uppdatera konstruktorn samt step- och print-metoderna.
  7. Se till att step-metoden gör sakerna i denna ordning:
    1. Ta fordon förbi signalerna om de är gröna.
    2. Stega filerna omedelbart framför signalerna.
    3. Behandla fordonet vid delningspunkten X.
    4. Stega den första (högra) filen.
    5. Anropa fordonsgeneratorn enligt beskrivningen ovan.
    6. Stega signalerna.
    Gör man på detta vis kommer man se att fordonen passerar alla positioner och att signalerna hinner bli gröna innan fordon kör förbi dem.
  8. Samla tiderna för fordon som lämnar systemet i två Measurements-objekt (ett för varje utgång) och se till att printStatistics skriver den efterfrågade statistiken. Kontrollera att statistiken är rimlig!

Innan du redovisar

Se till att
  1. Koden följer kodningsreglerna!
  2. Klasserna uppfyller dessa specifikationer.
  3. Att all efterfrågad statistik finns med.
  4. Metoden print producerar utskrifter enligt ovanstående exempel.

Tillbaka

Valid CSS!