Model ruchu Bihama-Middletona-Levine'a

Bihama – Middletona – Levine'a jest samoorganizującym się modelem przepływu ruchu automatu komórkowego . Składa się z pewnej liczby samochodów reprezentowanych przez punkty na siatce z losową pozycją początkową, gdzie każdy samochód może należeć do jednego z dwóch typów: tych, które poruszają się tylko w dół (pokazane w tym artykule jako niebieskie) i tych, które poruszają się tylko w kierunku po prawej (pokazane jako czerwone w tym artykule). Dwa rodzaje samochodów poruszają się na zmianę. Podczas każdej tury wszystkie samochody odpowiedniego typu przesuwają się o jeden stopień, jeśli nie są blokowane przez inny samochód. Można go uznać za dwuwymiarowy odpowiednik prostszego art. 184 . Jest to prawdopodobnie najprostszy system wykazujący przejścia fazowe i samoorganizację .

Historia

Model ruchu Biham – Middleton – Levine został po raz pierwszy sformułowany przez Ofera Bihama , A. Alana Middletona i Dova Levine'a w 1992 r. Biham i wsp. stwierdzili, że wraz ze wzrostem gęstości ruchu, stały przepływ ruchu nagle przeszedł od płynnego przepływu do kompletnego dżemu. W 2005 r. Raissa D'Souza odkryła, że dla niektórych zagęszczeń ruchu istnieje faza pośrednia charakteryzująca się okresowymi układami korków i płynnym przepływem. W tym samym roku Angel, Holroyd i Martin jako pierwsi rygorystycznie udowodnili, że dla gęstości bliskich jedności system zawsze się zacina. Później, w 2006 roku, Tim Austin i Itai Benjamini odkryli, że dla kwadratowej kraty o boku N model zawsze samoorganizuje się, aby osiągnąć pełną prędkość, jeśli jest mniej niż N / 2 samochodów.

Przestrzeń kratowa

Podstawowy wielokąt torusa, po którym poruszają się samochody

Samochody są zwykle umieszczane na kwadratowej siatce, która jest topologicznie równoważna torusowi : to znaczy samochody, które zjeżdżają z prawej krawędzi, pojawią się ponownie na lewej krawędzi; a samochody, które zjeżdżają z dolnej krawędzi, pojawią się ponownie na górnej krawędzi.

Prowadzono również badania w sieciach prostokątnych zamiast kwadratowych. W przypadku prostokątów o względnie pierwszych stany pośrednie to samoorganizujące się pasma zatorów i swobodnego przepływu o szczegółowej strukturze geometrycznej, które powtarzają się okresowo w czasie. W prostokątach innych niż względnie pierwsze stany pośrednie są zazwyczaj raczej nieuporządkowane niż okresowe.

Przejścia fazowe

Pomimo prostoty modelu, ma on dwie wyraźnie rozróżnialne fazy – fazę zablokowaną i fazę swobodnego przepływu . W przypadku małej liczby samochodów system zwykle organizuje się sam , aby zapewnić płynny przepływ ruchu. W przeciwieństwie do tego, jeśli jest duża liczba samochodów, system zablokuje się do tego stopnia, że żaden samochód nie ruszy. Zazwyczaj w siatce kwadratowej gęstość przejścia ma miejsce, gdy jest około 32% tylu samochodów, ile jest możliwych miejsc w sieci.

Swobodna faza obserwowana na prostokątnej siatce 144 × 89 przy natężeniu ruchu 28%

Faza globalnego zakleszczenia obserwowana na prostokątnej siatce 144 × 89 przy natężeniu ruchu 60%

Sieć 512×512 o gęstości 27% po 64000 iteracji. Ruch jest w fazie swobodnego przepływu.

Sieć 512×512 o gęstości 29% po 64000 iteracji. Ruch jest w fazie swobodnego przepływu.

Sieć 512×512 o gęstości 38% po 64000 iteracji. Ruch jest w fazie globalnego zatoru.

Mobilność względem czasu dla sieci powyżej sieci. Mobilność definiuje się jako liczbę samochodów, które mogą się poruszać jako ułamek całości. (Punkty znajdują się w lewym górnym rogu obrazu).

Mobilność względem czasu dla sieci powyżej sieci. Mobilność definiuje się jako liczbę samochodów, które mogą się poruszać jako ułamek całości. (Punkty znajdują się po lewej stronie obrazu.)

Faza pośrednia

Faza pośrednia występuje w pobliżu gęstości przejściowej, łącząc cechy zarówno fazy zablokowanej, jak i sypkiej. Istnieją zasadniczo dwie fazy pośrednie – nieuporządkowana (która może być metastabilna ) i okresowa (które są stabilne). W sieciach prostokątnych o względnie pierwszych istnieją tylko orbity okresowe. W 2008 roku okresowe fazy pośrednie obserwowano również w sieciach kwadratowych. Jednak na sieciach kwadratowych nieuporządkowane fazy pośrednie są częściej obserwowane i mają tendencję do dominacji gęstości w pobliżu obszaru przejściowego.

Okresowa faza pośrednia obserwowana na prostokątnej siatce 144 × 89 o natężeniu ruchu 38%

Nieuporządkowana faza pośrednia obserwowana na prostokątnej siatce 144 × 89 o natężeniu ruchu 39%

Sieć 512×512 o gęstości 31% po 64000 iteracji. Ruch jest w nieuporządkowanej fazie pośredniej.

Sieć 512×512 o gęstości 33% po 64000 iteracji. Ruch jest w nieuporządkowanej fazie pośredniej.

Sieć 512×512 o gęstości 37% po 64000 iteracji. Ruch jest w nieuporządkowanej fazie pośredniej.

Mobilność względem czasu dla sieci powyżej sieci. Mobilność definiuje się jako liczbę samochodów, które mogą się poruszać jako ułamek całości.

Rygorystyczna analiza

Pomimo prostoty modelu, rygorystyczna analiza jest bardzo nietrywialna. Niemniej jednak istnieją dowody matematyczne dotyczące modelu ruchu Bihama – Middletona – Levine'a. Dotychczasowe dowody ograniczały się do skrajnych wartości natężenia ruchu. W 2005 roku Alexander Holroyd i inni udowodnili, że dla gęstości wystarczająco bliskich jedności w systemie nie będzie samochodów poruszających się nieskończenie często. W 2006 roku Tim Austin i Itai Benjamini udowodnili, że model zawsze osiągnie fazę swobodnego przepływu, jeśli liczba samochodów jest mniejsza niż połowa długości krawędzi kwadratowej siatki.

Powierzchnie nieorientowalne

Model jest zwykle badany na orientowanym torusie , ale możliwe jest zaimplementowanie siatki na butelce Kleina . Kiedy czerwone samochody dotrą do prawej krawędzi, pojawiają się ponownie na lewej krawędzi, z wyjątkiem odwrócenia w pionie; te na dole są teraz na górze i odwrotnie. $in \ lbrace 0, \ ldots,$ $displaystyle (N-1,y)}$ każdego samochodu wyjeżdżającego z serwisu $\$ wszedłby na stronę ${\ Displaystyle (0, Ny-1)}$ . Możliwa jest również implementacja na rzeczywistej płaszczyźnie rzutowej . Oprócz odwracania czerwonych samochodów, $a niebieski$ , $($ opuszczający witrynę wjechałby na witrynę $Displaystyle$

Zachowanie się układu na butelce Kleina jest znacznie bardziej podobne do tego na torusie niż na rzeczywistej płaszczyźnie rzutowej. W przypadku konfiguracji butelki Kleina ruchliwość jako funkcja gęstości zaczyna spadać nieco wcześniej niż w przypadku torusa, chociaż zachowanie jest podobne dla gęstości większych niż punkt krytyczny. Ruchliwość na rzeczywistej płaszczyźnie rzutowej zmniejsza się stopniowo dla gęstości od zera do punktu krytycznego. W rzeczywistej płaszczyźnie rzutowej w rogach sieci mogą tworzyć się lokalne zatory, mimo że reszta sieci jest swobodna.

Randomizacja

Randomizowany wariant modelu ruchu BML, zwany BML-R, był badany w 2010 roku. W okresowych granicach, zamiast aktualizować wszystkie samochody tego samego koloru naraz podczas każdego kroku, model losowy wykonuje L 2 {\ displaystyle ${ 2}}$ aktualizacje (gdzie jest długością boku przypuszczalnie kwadratowej siatki): za każdym razem wybierana jest losowa komórka i, jeśli zawiera samochód, jest przenoszona do następnej komórki, jeśli to $.$ W tym przypadku stan pośredni obserwowany w zwykłym modelu ruchu BML nie istnieje ze względu na niedeterministyczny charakter modelu losowego; zamiast tego przejście z fazy zablokowanej do fazy swobodnego przepływu jest ostre.

$styl wyświetlania \beta }$ otwartej granicy, zamiast samochodów, które zjeżdżają z jednej krawędzi, owijając się po drugiej stronie, nowe samochody są dodawane na lewej i górnej krawędzi z prawdopodobieństwem i usuwane z prawej i dolnej krawędzi $}$ $alpha$ odpowiednio. W takim przypadku liczba samochodów w systemie może zmieniać się w czasie, a lokalne korki mogą powodować, że siatka będzie wyglądać bardzo różnie od zwykłego modelu, na przykład współistnienie korków i obszarów o swobodnym przepływie; zawierające duże puste przestrzenie; lub zawierające głównie samochody jednego typu.

Linki zewnętrzne

Implementacja CUDA autorstwa Daniela Lu
Implementacja WebGL autorstwa Jasona Daviesa
Implementacja JavaScript autorstwa Macieja Barona