ビハム・ミドルトン・レヴィン交通モデル
ビハム・ミドルトン・レヴィン交通モデル（ビハム・ミドルトン・レヴィンこうつうモデル、Biham-Middleton-Levine Traffic Model, BML model）は自己組織化セル・オートマトンの交通モデルである。単純なルールでありながら、複雑な振る舞いにより、セルの流れがあたかも交通渋滞のように見える点に特徴がある。
歴史
[編集]このモデルは、1992年にオファー・ビハム, A. アラン・ミドルトン、ドブ・レヴィンにより論文に発表された[1]。ビハムは当時シラキュース大学の助教授だった（2020年現在はヘブライ大学のラカー物理学研究所の准教授）[2]。ビハムらは、交通密度が増加すると、それまで滑らかに安定状態だった流れが突然、完全な渋滞になることを発見した。
2004年、マイクロソフトリサーチのライサ・ド・ソウザは、ある条件では、渋滞と流動が周期的に繰り返される中間的な状態となることを発見した[3]。
ルール
[編集]このモデルでは、平面が細かい格子（セル）に分けられており、初期状態では「青い車」と「赤い車」がセルの中にランダムに配置されている。そして「青い車が動く順番」と「赤い車が動く順番」が交互に訪れる。「青い車が動く順番」では、全ての「青い車」が一斉に、一つ下のセルに移動する。ただし下のセルに「他の車」がいる場合は、そのままその位置に留まる。平面の下は平面の上に繋がっているので、下端の「青い車」は上端に移動する（上端に他の車がいなければ）。「赤い車が動く順番」では、全ての「赤い車」が一斉に、一つ右隣りのセルに移動する。多くの場合、「青の順番」と「赤の順番」をセットで「1回」と数える。
5×5の格子の例で説明する。図2の左図の状態から始まり、次が「青の順番」だった場合、「青1」の下は空いているので、「青1」は下に移動する。「青2」の下には「赤1」がいるので、「青2」は移動しない。「青3」の下には「青4」がいるので移動できない[4]。（「青4」は下に移動できるので「青3」も移動できる、として計算されることもある。）「青5」「青6」も移動できない。「青7」は最下部だが、この下は最上部に繋がっているので、「青7」は一番上に移動する。結果として図2の中央図の状態となる。この次は「赤の順番」となり、「赤4」と「赤5」以外は1つ右に移動でき（「赤2」は一番左に移動する）、結果として図2の右図の状態となる。
自由流動段階と渋滞段階
[編集]モデルがシンプルであるにもかかわらず、この交通モデルでは、全ての車が停止することなく動く「自由流動段階」（free-flowing phase）と、全ての車が停止する「渋滞段階」（jammed phase）という、両極端な段階に到達する場合が多い[1]。正方格子の場合、車の密度が32%を下回ると自由流動段階に、32%を上回ると渋滞段階になりやすい[5]。
図3と図4は同じ200×200の格子であるが、図3は「車」の密度が30%、図4は36%に設定してある。図3は初期にはランダムであるが、だんだんと赤と青の層に分かれていき、やがて全ての車が停止することなく移動する段階、すなわち自由流動段階になる。一方で、図4も初期にはランダムだが、だんだんと渋滞がひどくなって、ついには全ての車が停止した段階、つまり渋滞段階となる。
 |
 |
次の図5と図6は、初期状態から自由流動段階、あるいは渋滞段階になるまでを表した動画である。
中間段階
[編集]中間段階は、自由流動段階と渋滞段階が切り替わる密度に近いところで発生し、部分的に自由流動の部分と渋滞の部分とが混在する。
「中間状態」には2種類ある。1つは、移動する車同士に一定の車間（多くの場合3台分）ができて整然と移動する「周期的状態」(Periodic Intermediate state, PI)である。もう一つは、車間が無秩序に変化する「無秩序状態」（Disordered Intermediate state, DI）である。それに加えて広範囲な渋滞（global jam, GJ）の部分があるので、中間状態はPI, DI, GJの3箇所を含む場合が多い[6]。正方格子が中間状態になる場合、一般には無秩序となりやすいが、2008年には正方格子でも周期的な中間状態となる条件が見つかっている[6]。
 |
 |
 |
2辺が互いに素の場合
[編集]このモデルでは、右から出た車が左に、下から出た車が上に移動するため、これが交通の流れに影響する。領域の2辺の格子数が「互いに素」の場合に中間状態となると、周期的部分が多く渋滞部分が少ない状態になりやすい。逆に、2辺の格子数が共通の約数を持つ場合、渋滞が生じやすく、結果として無秩序部分が多くなる[3]。
境界条件の影響
[編集]このモデルは、右辺と左辺、上辺と下辺がまっすぐ繋がった状態について解析されることが多いが、捩じって接続した場合についても研究されている。
2009年、セビリア大学のカンポーラらは、このモデルの境界条件を、
(a) 「トーラス構造」。つまり、本来のルール通り。
(b) 「クラインの壺構造」。青い車が下端の下に移動する場合、上端の左右が反対の位置に出現させる。例えば前記の図2の左図で説明するなら、「青7」の車は1行目5列目ではなく、1行目1列目の位置に出現させる。赤い車の動きは本来のルール通りとする。
(c) 「 実射影平面構造」。(b)に加えて、赤い車が右端から右に移動する場合に左端の上下が反対の位置に出現させる。
の3つで、横軸を密度、縦軸を車の移動度で表したグラフの減少速度について検討した。
その結果、「クラインの壺構造」では「トーラス構造」よりも移動度の減少速度がわずかに速く、「 実射影平面構造」では「トーラス構造」よりも移動度の減少速度がわずかに遅いことが明らかになった[7]。
乱数化
[編集]2010年、中国科学技術大学の丁中俊らは、下辺と右辺から出ていく車はそのまま削除し、新しい車を上辺と左辺のランダムな位置に追加していく場合についての研究を行った[8]。このルール変更が与える影響は大きく、(a) 渋滞となる領域が右下の矩形部分に集中し、その外側は自由流動となる、(b) 渋滞部分が複雑な構造とならず、「青い車の領域」と「赤い車の領域」が、ほぼ1つに纏まってしまう、という特徴がある[8]。
数学的証明
[編集]このモデルは単純だが、厳密な解析は非常に困難である[5]。このモデルに対する数学的証明は、これまでのところ、パラメーターが極端な値の場合に限定されて行われている。
2005年4月、ブリティッシュコロンビア大学のエンジェルらは、密度が1に近い場合、常に渋滞が発生することを厳密に証明した[9]。
2006年、カリフォルニア大学ロサンゼルス校のティム・オースティンらは、N×Nの正方格子の場合、車の数がN/2以下であれば、常に全ての車が停止することなく移動できる状態になることを発見した[10]。
参考文献
[編集]- ^ a b Biham, Ofer; Middleton, A. Alan; Levine, Dov (November 1992). “Self-organization and a dynamical transition in traffic-flow models”. Phys. Rev. A (American Physical Society) 46 (10): R6124–R6127. arXiv:cond-mat/9206001. Bibcode: 1992PhRvA..46.6124B. doi:10.1103/PhysRevA.46.R6124. ISSN 1050-2947. PMID 9907993. オリジナルの2013-02-24時点におけるアーカイブ。 14 December 2012閲覧。.
- ^ “Curriculum Vitae”. 2020年12月3日閲覧。
- ^ a b D'Souza, Raissa M. (2005). “Coexisting phases and lattice dependence of a cellular automaton model for traffic flow”. Phys. Rev. E (The American Physical Society) 71 (6): 066112. Bibcode: 2005PhRvE..71f6112D. doi:10.1103/PhysRevE.71.066112. PMID 16089825. オリジナルの24 February 2013時点におけるアーカイブ。 14 December 2012閲覧。.
- ^ オリジナルの論文Biham, Ofer et al. (November 1992)には「移動先に車がいたら移動できない」と書かれているだけだが、D'Souza, Raissa M. (2005)のFig.8にこのルールが図示されている。
- ^ a b Holroyd, Alexander E.. “The Biham–Middleton–Levine Traffic Model”. 14 December 2012閲覧。
- ^ a b Linesch, Nicholas J.; D'Souza, Raissa M. (15 October 2008). “Periodic states, local effects and coexistence in the BML traffic jam model”. Physica A 387 (24): 6170–6176. arXiv:0709.3604. Bibcode: 2008PhyA..387.6170L. doi:10.1016/j.physa.2008.06.052. ISSN 0378-4371.
- ^ Cámpora, Daniel; de La Torre, Jaime; García Vázquez, Juan Carlos; Caparrini, Fernando Sancho (August 2010). “BML model on non-orientable surfaces.”. Physica A 389 (16): 3290–3298. Bibcode: 2010PhyA..389.3290C. doi:10.1016/j.physa.2010.03.037.
- ^ a b Ding, Zhong-Jun; Jiang, Rui; Wang, Bing-Hong (2011). “Traffic flow in the Biham–Middleton–Levine model with random update rule”. Physical Review E 83 (4): 047101. Bibcode: 2011PhRvE..83d7101D. doi:10.1103/PhysRevE.83.047101.
- ^ Angel, Omer; Holroyd, Alexander E.; Martin, James B. (12 August 2005). “The Jammed Phase of the Biham–Middleton–Levine Traffic Model”. Electronic Communications in Probability 10: 167–178. arXiv:math/0504001. doi:10.1214/ECP.v10-1148. ISSN 1083-589X. オリジナルの2016-03-04時点におけるアーカイブ。 14 December 2012閲覧。.
- ^ Austin, Tim; Benjamini, Itai (2006). "For what number of cars must self organization occur in the Biham–Middleton–Levine traffic model from any possible starting configuration?". arXiv:math/0607759。
外部リンク
[編集]
- WebGL implementation WebGLを利用したウェブページであり、密度と格子数を指定するだけでBML交通モデルのテストが可能 by Jason Davies
- CUDA implementation CUDAを使ったC++のプログラム例 by Daniel Lu