Модель руху Бігама — Міддлтона — Левіна
Модель руху Бігама-Міддлтона-Левіна — це самоорганізований клітинний автомат. Вона складається з ряду автомобілів представлених точками на решітці з випадковою початковою позицією, де автомобіль може бути одного з двох типів: ті, що рухатися тільки вниз (показано синім), і ті, які рухаються тільки вправо (показано червоним). Два типи машин рухаються по черзі. Під час кожного ходу, всі автомобілі відповідного типу роблять один крок, якщо вони не заблоковані іншою машиною. Це можна вважати двовимірним аналогом простішої моделі правила 184. Це можливо найпростіша система експонування фазових переходів і самоорганізації.[1]
Історія
Модель руху Бігама-Міддлтона-Левіна вперше сформулювали Офер Бігам, А. Алан Міддлтон і Дов Левін в 1992 році.[2] Бігам і співавт. виявили, що зі збільшенням щільності руху, стаціонарний потік руху раптово перейшов з плавного потоку до повного затору. У 2005 році Шаблон:Нп виявила, що за деякої інтенсивності руху, є проміжний етап, що характеризується періодичним чергуванням заторів і плавного потоку.[3] У тому ж році, Ангел, Холройд і Мартін були першими, хто строго довів, що для щільності близької до одиниці, система буде постійно переходити у затор.[4] Пізніше, в 2006 році, Тім Остін і Ітаї Бенджаміні визначили, що для квадратної решітки зі стороною N, модель буде завжди самоорганізуватися, щоб досягти повної швидкості, якщо на ній є менше, ніж N/2 автомобілів.[5]
Решітчастий простір
Автомобілі, як правило, розміщуються на квадратній решітці, яка топологічно еквівалентна торусу: тобто, автомобілі, які рухаються вправо будуть заново з'являтися з лівого краю; і автомобілі, які рухаються за нижню межу будуть з'являтися на верхній грані.
Проводилися також дослідження, в прямокутних решітках замість квадратних. Для прямокутників з взаємно простими розмірностями, проміжні стани є самоорганізованими групами заторів і вільного руху з детальною геометричною структурою, які періодично повторюються в часі.[3] У не взаємно простих прямокутниках, проміжні стани, як правило, невпорядковані, а не періодичні.[3]
Фазові переходи
Незважаючи на простоту моделі, вона має дві дуже помітні фази — фаза затору, і фаза вільного руху.[2] Для малої кількості автомобілів, система, як правило, організовує себе для досягнення плавного потоку руху. У випадку ж великої кількість машин, система стане заповненою до такої міри, що жоден автомобіль не зможе продовжувати рух. Як правило, в квадратній решітці, фаза змінюється, коли кількість автомобілів досягає 32 % від всіх можливих місць на сітці.[6]
| Файл:Biham-Middleton-Levine traffic model self-organized to a free flowing phase.ogv | Файл:Biham-Middleton-Levine traffic model self-organized to a globally jammed phase.ogv |
 |
 |
 |
 |
 |
 |
Проміжна фаза
Проміжна фаза поєднує в собі риси як вільної фази, так і фази затору. Є дві проміжні фази — невпорядкована (яка може бути мета-стабільною) і періодична (яка доказово стабільна).[3] На прямокутній решітці з взаємно простими розмірностями, існують тільки періодичні орбіти.[3] У 2008 році періодичні проміжні фази було виявлено також у квадратних решітках.[7] Тим не менш, на квадратних решітках невпорядковані проміжні фази спостерігаються частіше і схильні домінувати щільність близько до перехідної області.
| Файл:Biham-Middleton-Levine traffic model self-organized to a periodic intermediate phase.ogv | Файл:Biham-Middleton-Levine traffic model self-organized to a disordered intermediate phase.ogv |
 |
 |
 |
 |
 |
 |
Ретельний аналіз
Незважаючи на простоту моделі, строгий аналіз є вельми нетривіальним.[6] Тим не менш, є математичні доведення, що стосуються моделі руху Бігама-Міддлтона-Левіна. Доведення досі були обмежені до крайності щільності руху. У 2005 році Олександр Холройд і співавт. довели, що для щільності досить близької до одиниці, система не буде мати автомобілів, що рухаються нескінченно часто.[4] У 2006, Тім Остін і Ітаї Бенджаміні доведели, що модель буде завжди доходити до фази вільного руху, якщо кількість автомобілів не перевищує половини довжини кромки для квадратної решітки.[5]
Неорієнтовані поверхні
Модель зазвичай вивчається на орієнтованому торусі, але решітку можна також реалізувати на пляшці Клейна.[8] Коли червоні машини досягають правого краю, вони знову з'являються на лівому краю, крім дзеркального відображення по вертикалі; ті, що внизу, тепер нагорі, і навпаки. Більш формально, для кожного червоний автомобіль, що покинув сторону , зайде зі сторони . Можна також реалізувати на дійсній проективній площині.[8] На додаток до розвертання червоних машин, те ж саме робиться для синіх: кожен синій автомобіль, що проїхав сторону , заїде зі сторони .
Поведінка системи на пляшці Клейна більш схожа на торус, ніж на дійсній проективній площині.[8] Для пляшки Клейна, мобільність як функція щільності починає зменшуватися трохи раніше, ніж у другому випадку, хоча поведінка є аналогічною при щільності більшій за критичні точки. Мобільність на дійсній проективній площині зменшується більш поступово для густин від нуля до критичної точки. На дійсній проективній площині, місцеві затори можуть утворюватися в кутах решітки, навіть якщо інша частина решітки є вільною.[8]
Рандомізація
Рандомізований варіант моделі Бігама-Міддлтона-Левіна (BML), називається BML-R, почав вивчатись у 2010 році.[9] Замість оновлення всіх автомобілів одного кольору водночас протягом кожного кроку, рандомізована модель виконує оновлень (де — довжина сторони квадратної решітки): кожен раз, випадкову клітинку і, якщо вона містить машину, переміщають в наступну комірку, якщо це можливо. У цьому випадку проміжний стан, що спостерігається в звичайній моделі BML, не існує, через невизначений характер рандомізованих моделей; замість того, перехід від фази затору до фази вільного руху відбувається різко.
При відкритих граничних умовах, замість того, щоб автомобілі, які виїдуть з одного краю з'являлись з іншого боку, нові автомобілі будуть додані на лівий і верхній кордони з імовірністю і видалені з правого і нижнього країв відповідно. У цьому випадку, кількість автомобілів в системі, може змінюватися з плином часу, і місцеві затори можуть приводити решітку у зовсім інший стан, ніж звичайна модель, наприклад формувати співіснування заторів та зон вільного руху, появу великих порожніх зон або появу зон, що в основному складаються з автомобілів одного типу.[9]