Biham–Middleton–Levine trafikmodell

Biham –Middleton–Levine-trafikmodellen är en självorganiserande mobilautomatisk trafikflödesmodell . Den består av ett antal bilar representerade av punkter på ett galler med en slumpmässig startposition, där varje bil kan vara en av två typer: de som bara rör sig nedåt (visas som blå i den här artikeln), och de som bara rör sig mot höger (visas som röd i den här artikeln). De två typerna av bilar turas om att röra sig. Under varje sväng avancerar alla bilar för motsvarande typ ett steg om de inte blockeras av en annan bil. Det kan anses vara den tvådimensionella analogen till den enklare Rule 184- modellen. Det är möjligen det enklaste systemet som uppvisar fasövergångar och självorganisering .

Historia

Biham–Middleton–Levine-trafikmodellen formulerades först av Ofer Biham , A. Alan Middleton och Dov Levine 1992. Biham et al fann att när trafiktätheten ökade, gick det stabila trafikflödet plötsligt från jämnt flöde till en fullständig sylt. 2005 Raissa D'Souza att för vissa trafiktätheter finns det en mellanfas som kännetecknas av periodiska arrangemang av köer och jämnt flöde. Samma år var Angel, Holroyd och Martin de första som rigoröst bevisade att för densiteter nära en, kommer systemet alltid att fastna. Senare, 2006, fann Tim Austin och Itai Benjamini att för ett kvadratiskt galler på sidan N kommer modellen alltid att självorganisera sig för att nå full fart om det finns färre än N /2 bilar.

Gallerutrymme

Den grundläggande polygonen i torus, på vilken bilarna rör sig

Bilarna är vanligtvis placerade på ett kvadratiskt galler som är topologiskt ekvivalent med en torus : det vill säga bilar som rör sig från högerkanten skulle dyka upp igen på vänsterkanten; och bilar som rör sig utanför underkanten skulle dyka upp igen på överkanten.

Det har också forskats på rektangulära galler istället för kvadratiska. För rektanglar med coprime -dimensioner är de mellanliggande tillstånden självorganiserade band av sylt och fritt flöde med detaljerad geometrisk struktur, som upprepas med jämna mellanrum. I icke-coprime rektanglar är de mellanliggande tillstånden typiskt oordnade snarare än periodiska.

Fasövergångar

Trots modellens enkelhet har den två mycket urskiljbara faser – den fastade fasen och den fritt flytande fasen . För låga antal bilar kommer systemet vanligtvis att organisera sig för att uppnå ett smidigt trafikflöde. Om det däremot finns ett stort antal bilar, kommer systemet att fastna i den utsträckningen att ingen enskild bil kommer att röra sig. Vanligtvis i ett kvadratiskt galler är övergångstätheten när det finns cirka 32 % så många bilar som det finns möjliga utrymmen i gallret.

En friflytande fas observerad på ett 144×89 rektangulärt gitter med en trafiktäthet på 28 %

En globalt blockerad fas observerad på ett 144×89 rektangulärt gitter med en trafiktäthet på 60 %

Ett 512×512 gitter med en densitet på 27% efter 64000 iterationer. Trafiken är i ett fritt flöde.

Ett 512×512 gitter med en densitet på 29% efter 64000 iterationer. Trafiken är i ett fritt flöde.

Ett 512×512 gitter med en densitet på 38% efter 64000 iterationer. Trafiken befinner sig i ett globalt blockerat skede.

Rörlighet med avseende på tid för ovanstående galler. Rörlighet definieras som antalet bilar som kan röra sig som en bråkdel av det totala antalet. (Punkten finns i det övre vänstra hörnet av bilden.)

Rörlighet med avseende på tid för ovanstående galler. Rörlighet definieras som antalet bilar som kan röra sig som en bråkdel av det totala antalet. (Punkten finns på vänster sida av bilden.)

Mellanfasen

Den mellanliggande fasen inträffar nära övergångstätheten, och kombinerar egenskaper från både den fastade och friflytande fasen. Det finns i princip två mellanfaser – oordnade (som kan vara metastabila ) och periodiska (som bevisligen är stabila). På rektangulära gitter med coprime -dimensioner existerar endast periodiska banor. Under 2008 observerades även periodiska mellanfaser i kvadratiska gitter. Ändå, på kvadratiska gitter observeras oordnade mellanfaser oftare och tenderar att dominera tätheter nära övergångsregionen.

En periodisk mellanfas observerad på ett 144×89 rektangulärt gitter med en trafiktäthet på 38 %

En oordnad mellanfas observerad på ett 144×89 rektangulärt gitter med en trafiktäthet på 39 %

Ett 512×512 gitter med en densitet på 31% efter 64000 iterationer. Trafiken befinner sig i en oordnad mellanfas.

Ett 512×512 gitter med densitet på 33% efter 64000 iterationer. Trafiken befinner sig i en oordnad mellanfas.

Ett 512×512 gitter med en densitet på 37% efter 64000 iterationer. Trafiken befinner sig i en oordnad mellanfas.

Rörlighet med avseende på tid för ovanstående galler. Rörlighet definieras som antalet bilar som kan röra sig som en bråkdel av det totala antalet.

Rigorös analys

Trots modellens enkelhet är noggrann analys mycket icke-trivial. Ändå har det funnits matematiska bevis angående Biham–Middleton–Levine-trafikmodellen. Bevis hittills har begränsats till extrema trafiktätheter. År 2005 bevisade Alexander Holroyd et al att för tätheter som är tillräckligt nära en, kommer systemet att ha inga bilar som rör sig oändligt ofta. 2006 bevisade Tim Austin och Itai Benjamini att modellen alltid kommer att nå den fritt flytande fasen om antalet bilar är mindre än halva kantlängden för ett kvadratiskt galler.

Ej orienterbara ytor

Modellen studeras vanligtvis på den orienterbara torusen , men det är möjligt att implementera gallret på en Klein-flaska . När de röda bilarna når högerkanten dyker de upp igen på vänsterkanten förutom att de vänds vertikalt; de längst ner är nu överst, och vice versa. Mer formellt, för varje $y\in \lbrace 0,\ldots ,N-1\rbrace$ , en röd bil som lämnar platsen ${\ displaystyle (N-1,y)}$ skulle komma in på webbplatsen $\displaystyle (0,Ny-1)}$ . Det är också möjligt att implementera det på det verkliga projektiva planet . Förutom att vända de röda bilarna, görs samma sak för de blå bilarna: för varje ${\displaystyle x\in \lbrace 0,\ldots ,N-1\rbrace } ,$ a blå bil som $(Nx-1,0)$ platsen $(x,N-1)$ skulle komma in på platsen .

Beteendet hos systemet på Klein-flaskan är mycket mer likt det på torus än det på det verkliga projektiva planet. För Klein-flaskuppställningen börjar rörligheten som funktion av densiteten minska något tidigare än i torusfallet, även om beteendet är liknande för densiteter större än den kritiska punkten. Rörligheten på det verkliga projektiva planet minskar mer gradvis för densiteter från noll till den kritiska punkten. I det verkliga projektiva planet kan lokala stopp bildas i hörnen av gallret även om resten av gallret är fritt flytande.

Randomisering

En randomiserad variant av BML-trafikmodellen, kallad BML-R, studerades 2010. Under periodiska gränser, istället för att uppdatera alla bilar av samma färg på en gång under varje steg, utför den randomiserade modellen L 2 {\displaystyle ${ 2}}$ uppdateringar (där $L$ är sidolängden på det förmodligen kvadratiska gittret): varje gång väljs en slumpmässig cell och, om den innehåller en bil, flyttas den till nästa cell om möjligt. I detta fall existerar inte det mellanliggande tillståndet som observeras i den vanliga BML-trafikmodellen, på grund av den randomiserade modellens icke-deterministiska natur; istället är övergången från den fastade fasen till den fritt flytande fasen skarp.

Under öppna gränsförhållanden, istället för att ha bilar som kör av ena kanten lindade runt den andra sidan, läggs nya bilar till på vänster och övre kant med sannolikheten α {\displaystyle \alpha } $tas$ bort från höger- och underkanten ${\ displaystyle \beta }$ respektive. I det här fallet kan antalet bilar i systemet förändras över tiden, och lokala stopp kan göra att gallret ser väldigt annorlunda ut från den vanliga modellen, som att det finns samexistens av stopp och fritt flytande områden; som innehåller stora tomma utrymmen; eller innehåller mestadels bilar av en typ.

externa länkar

CUDA-implementering av Daniel Lu
WebGL-implementering av Jason Davies
JavaScript-implementering av Maciej Baron