Into the Boid
Boidと非平衡相転移
鳥などの群れの動きを、単純なアルゴリズムでそれっぽく見せる手法に、Boidというものがあります。鳥を模したエージェント(boid)に、
それだけだと、ふーん綺麗だなあ、で終わってしまうのですが、以下のサイトで、なんとこの系で非平衡相転移現象を見出したという報告が紹介されていました。
Boid にノイズを加えて相転移させた -Swarm of Trials-
これはおもしろい、ということで、今回はboidをいろいろいじくって遊んでみた、というネタを書きたいとおもいます。
Vicsekのモデル
最初にboidの非平衡相転移を報告したのは、
Tamás Vicsek et al. Phys. Rev. Lett. 75, 1226 - 1229 (1995)
Novel Type of Phase Transition in a System of Self-Driven Particles
です。PRLのページはこちら、論文はこちらから入手可能です。
この内容は、上記のSwarm of Trialsさんのサイトで詳しく解説されているのですが、後の説明の関係上、boidの運動に関してのみ図を交えて解説します。
各エージェントの運動は、オリジナルのboidから大きく簡略化したルールにしたがいます。
すなわち、
このルールによる、i番目のエージェントの運動を数式で表すと以下のようになります(オリジナルの論文とは若干表現を変えてあります)
xi(t+Δt)=xi(t)+vi(t)Δt
vi(t+Δt)=RηA(Σj∈D vj(t))
Aはベクトルの大きさをvにするための規格化定数。Rηはベクトルの向きを±η/2の範囲内でランダムに変更する演算を表します(ようするにノイズ)。Dは半径rのディスクをあらわします。
これを図解すると以下のようになります。青い丸で示したエージェントは、速度を周囲半径rに存在する他のエージェント(緑丸)が持つ速度の平均値にしようとします。
やや擬人化して表現すると、このエージェントどもは、周囲の状況に付和雷同しつつ、(ノイズによって)自分の考えをころころ変える、浮き足立ったやつらです。
ノイズがゼロであれば、時間が経てばエージェントの向きは平均化されて、すべてのエージェントが同じ向きを向いて運動します。これを秩序相と呼ぶことにします。ノイズが十分に大きければ(η=2π)、エージェントは完全にばらばらな向きに動きます。これを無秩序相と呼ぶことにします。ノイズの大きさを変化させると、一方の相からもう一方への変化が生じます。Vicsekは、この変化がじつは相転移である、ということを示しました。(秩序変数、臨界点の存在、臨界指数、ゆらぎ・感受率の発散)
さて、この非平衡相転移現象を、伝統的な平衡相転移とのアナロジーで対応させてみます。Vicsekモデルにおけるノイズは、各エージェントの向きをランダムに揺さぶります。平衡相転移において粒子をランダムに揺さぶる働きがあるのは、温度です。すなわち、ノイズを印加することで生じる秩序相から無秩序相への転移は、
(前者は1次転移なので、たぶん2次転移である後者やboidの相転移とは性質が異なりますが。まあ、細かいことは気にしない方針で。)
ところで、相転移を引き起こすことのできるパラメーターは、なにも温度に限りません。氷の例を持ち出せば、氷に圧力をかけると氷は融解して水となります。Vicsekモデルでも、密度による秩序-無秩序相転移が報告されています。しかし、ノイズがゼロだと、密度をいくら変化させようが結局は秩序相になってしまい、相転移は起こりません。なんとかして、ノイズが無くても相転移を起こす方法はないものでしょうか。
競合する相互作用の導入
エージェントの速度を決めるルールを、オリジナルから若干変更します。すなわち、
xi(t+Δt)=xi(t)+vi(t)Δt
vi(t+Δt)=A(Σj∈D vj(t)-Σj∈R vj(t))
Aは規格化定数、Dは半径r2のディスク(下図では薄緑色の領域)、Rは外径r1、内径r2のリング(下図では薄紫色の領域)です。
これを図解すると以下のようになります。青い丸で示したエージェントは、緑丸で示したエージェントの速度の平均値を向こうとしますが、紫色で示したエージェントの速度の逆をも向こうとします。
エージェントの速度の大きさは常に一定、ノイズはゼロとします。このようなルールを課すことで、周囲と同じ方向に進もうとする力と、逆方向に進もうとする力を競合させ、エージェントの運動に変化を生じさせようという目論見です。
ここでも擬人化表現を使いますと、こんどのエージェントは、自分の近くにいるやつらには付和雷同するけれども、それより遠くにいるやつらとは仲が悪くてつねに敵対していないと気が済まないようなやつらです。
このルールに従うエージェントの運動を見てみましょう。エージェントはオリジナルと同じく、L×Lのトーラス上を運動します。また、全エージェント数をNとします。エージェントの速度の絶対値はv、時間刻みはΔtであらわします。
計算の条件は、
v=0.03,L=10,N=400,Δt=1.0,r1=1.0
です。
結果
まずは、オリジナルの論文で秩序変数とされている量、vaの時間変化をみていきましょう。vaの定義は、
va=|Σi vi(t)|/Nv
で、エージェントの向きのそろい方を示す指標です。すべてのエージェントが完全に同じ向きを向いている場合に1となり、向きが完全にばらばらだと0となります。
まずは、r2=1.0(=r1)の場合です。これは、Vicsekモデルでノイズがゼロの場合にあたります。横軸に時間、縦軸にvaをとってみます。初期条件は、位置・速度ともにランダムです。計算は1000ステップまで行っています。すると、vaはすぐに1に収束することがわかります。これは、全エージェントが同じ方向を向いていることを意味しています。Vicsekモデルの意味での秩序相です。
続いて、r2=0.4とした場合を見てみましょう。他の条件はすべて一つ前のものと同じです。
すごく、あばれています。これは一体何を意味しているのでしょう。
この挙動の意味は、エージェントの運動のスクリーンショットを見てみればわかります。
上の図で、左がr2=1.0の場合、右がr2=0.4の場合です。r2=1.0では、全エージェントが巨大なクラスタを形成し、同一方向に運動しています。ところが、r2=0.4では、形成されるクラスタのサイズは、r2=1.0のときよりも小さくなっています。各クラスタに属するエージェントは同一の方向に進むのですが、それぞれのクラスタの進行方向がばらばらなので、vaは大きな値をとることができないのです。さらに、クラスタどうしが衝突しても、合体してサイズの大きいクラスタになることはまずなく、分裂するか回避しあいます。
このような挙動を示す原因は、2種類の相互作用を競合させたことにあります。エージェントは、周囲r2の範囲に存在するエージェントと同じ方向に進みたがります。これはエージェントどうしの引力とみなせます。ところが、r2よりも遠くにいるエージェントとは逆方向を向きたがりますので、これは斥力として働きます。クラスタの直径が大きくなると、同一クラスタ内にいるエージェントに対しても斥力が働いてしまうので、クラスタの直径を増やすということは困難になるのです。
上の例からわかるように、どうもこの系のエージェントの運動は、r2を変えていくと、単一クラスタを形成しやすい状態から、単一クラスタを形成しにくい状態へと、定性的に変化するようです。この変化を定量的に扱うパラメータとして、単一の巨大なクラスタを形成するのに要した時間(あるいは、vaが1になった時間)tsを考えます。単一のクラスタを形成できない場合には、ts=∞となりますが、今回は10000ステップまでしか計算を行っていないので、クラスタを形成しない場合にはts=10000としています。さらに、系が秩序だったときには有限の値をとるパラメータを用いたいというこころがあるので、tsの逆数を、この系を特徴づけるパラメータとして採用します。
次の図は、横軸にr2、縦軸に1/tsをとってプロットを行ったものです。
r2が1に近いときは、1/tsは0.005付近の値をとります。r2を減少させていくと、r2~0.9付近で、1/tsは急激に減少します。r2~0.8付近では、値にばらつきがありますが、1/tsは0.0002以下となります。さらにr2が小さくなると、最終的に巨大なクラスタが形成されるのかどうかすらわかりません。
このように、エージェントの相互作用に競合する要素を入れてやることで、意図的にノイズを加えなくとも、系の運動が秩序だったものから無秩序的なものへと変化する様子が確認できました。
最後に、vaの時間変化をもういちど見てみます。r2=1.0のときは、すぐに巨大なクラスタが形成されます。r2=0.8付近では、vaは大きく振動しながら、巨大なクラスタを形成したりしなかったりします。この巨大な振動は、じつは、系が二つの大きなクラスタに分かれて運動している様子を示しています。クラスタの衝突ごとに、vaが大きく乱高下します。衝突がうまいぐあいにいくと、クラスタの合体がおこりますが、衝突の頻度は低く、かつ適切な角度で衝突しないと合体しませんので、vaはなかなか1に収束しません。r2=0.4では、大きなクラスタが形成されるようなそぶりすらありません。最終的に巨大なクラスタになってしまうのかどうかすらわかりません。
たくさんある問題
Q. つーかこれ、ほんとに相転移なんですか?
A. わかりませんorz
Q. そうだとしたら、秩序変数は?
A. わかりませんorz
Q. これって、密度とか粒子数で挙動変わりますよね
A. たぶん。。。(やってません)
Q. 無秩序相のvaの挙動になにか法則性はあるの?
A. わかりませんorz
Q. つーか、いったいなにがおもしろいの?
A. アレとか、アレとか、そのへんとからみがあったらなぁ、と思って。
Q. 先行研究、あるんじゃないの?
A. 私の探し方が悪いのか、なかなかみつかりません。ご存知の方がいらっしゃれば、マジで教えていただきたいです。
参考文献
Boid にノイズを加えて相転移させた -Swarm of Trials-
今回のネタについて参考にさせていただいたSwarm of Trialsさんの記事。Vicsekモデルについて丁寧な解説があります。
Boids (Flocks, Herds, and Schools: a Distributed Behavioral Model)
Boidの生みの親、Craig Reynoldsさんのサイト。
Novel Type of Phase Transition in a System of Self-Driven Particles
Vicsekモデル。
Spontaneously ordered motion of self-propelled particles
基本的に上と同じですが、揺らぎや感受率にも言及しており、おおっ、相転移っぽいなと思わせます。さらに、XYモデルとの関連も。
Noise-induced transition from translational to rotational motion of swarms
並進運動から回転運動へのノイズ誘起相転移。なんかいろいろとバリエーションがあるようですね。arxivで読めるのはこちら。Google Scholarでぐぐると関連論文がたくさん出てきます。。。
鳥などの群れの動きを、単純なアルゴリズムでそれっぽく見せる手法に、Boidというものがあります。鳥を模したエージェント(boid)に、
- エージェントがたくさんいる方向に向かう
- まわりのエージェントと向きを揃える
- エージェントと近づきすぎたら離れる
それだけだと、ふーん綺麗だなあ、で終わってしまうのですが、以下のサイトで、なんとこの系で非平衡相転移現象を見出したという報告が紹介されていました。
Boid にノイズを加えて相転移させた -Swarm of Trials-
これはおもしろい、ということで、今回はboidをいろいろいじくって遊んでみた、というネタを書きたいとおもいます。
Vicsekのモデル
最初にboidの非平衡相転移を報告したのは、
Tamás Vicsek et al. Phys. Rev. Lett. 75, 1226 - 1229 (1995)
Novel Type of Phase Transition in a System of Self-Driven Particles
です。PRLのページはこちら、論文はこちらから入手可能です。
この内容は、上記のSwarm of Trialsさんのサイトで詳しく解説されているのですが、後の説明の関係上、boidの運動に関してのみ図を交えて解説します。
各エージェントの運動は、オリジナルのboidから大きく簡略化したルールにしたがいます。
すなわち、
- エージェントの速度は周囲の半径rに存在する全エージェントの平均となる
- エージェントの速度の大きさはつねに一定値vである
このルールによる、i番目のエージェントの運動を数式で表すと以下のようになります(オリジナルの論文とは若干表現を変えてあります)
xi(t+Δt)=xi(t)+vi(t)Δt
vi(t+Δt)=RηA(Σj∈D vj(t))
Aはベクトルの大きさをvにするための規格化定数。Rηはベクトルの向きを±η/2の範囲内でランダムに変更する演算を表します(ようするにノイズ)。Dは半径rのディスクをあらわします。
これを図解すると以下のようになります。青い丸で示したエージェントは、速度を周囲半径rに存在する他のエージェント(緑丸)が持つ速度の平均値にしようとします。
やや擬人化して表現すると、このエージェントどもは、周囲の状況に付和雷同しつつ、(ノイズによって)自分の考えをころころ変える、浮き足立ったやつらです。
ノイズがゼロであれば、時間が経てばエージェントの向きは平均化されて、すべてのエージェントが同じ向きを向いて運動します。これを秩序相と呼ぶことにします。ノイズが十分に大きければ(η=2π)、エージェントは完全にばらばらな向きに動きます。これを無秩序相と呼ぶことにします。ノイズの大きさを変化させると、一方の相からもう一方への変化が生じます。Vicsekは、この変化がじつは相転移である、ということを示しました。(秩序変数、臨界点の存在、臨界指数、ゆらぎ・感受率の発散)
さて、この非平衡相転移現象を、伝統的な平衡相転移とのアナロジーで対応させてみます。Vicsekモデルにおけるノイズは、各エージェントの向きをランダムに揺さぶります。平衡相転移において粒子をランダムに揺さぶる働きがあるのは、温度です。すなわち、ノイズを印加することで生じる秩序相から無秩序相への転移は、
- 氷を加熱すると水になる
- 鉄を加熱すると磁石としての機能を失う
(前者は1次転移なので、たぶん2次転移である後者やboidの相転移とは性質が異なりますが。まあ、細かいことは気にしない方針で。)
ところで、相転移を引き起こすことのできるパラメーターは、なにも温度に限りません。氷の例を持ち出せば、氷に圧力をかけると氷は融解して水となります。Vicsekモデルでも、密度による秩序-無秩序相転移が報告されています。しかし、ノイズがゼロだと、密度をいくら変化させようが結局は秩序相になってしまい、相転移は起こりません。なんとかして、ノイズが無くても相転移を起こす方法はないものでしょうか。
競合する相互作用の導入
エージェントの速度を決めるルールを、オリジナルから若干変更します。すなわち、
- エージェントの速度は、周囲の半径r2に存在するエージェントの速度の和から、半径r2以上r1以下のリング領域に存在するエージェントの速度の和を引いたものに比例する。
xi(t+Δt)=xi(t)+vi(t)Δt
vi(t+Δt)=A(Σj∈D vj(t)-Σj∈R vj(t))
Aは規格化定数、Dは半径r2のディスク(下図では薄緑色の領域)、Rは外径r1、内径r2のリング(下図では薄紫色の領域)です。
これを図解すると以下のようになります。青い丸で示したエージェントは、緑丸で示したエージェントの速度の平均値を向こうとしますが、紫色で示したエージェントの速度の逆をも向こうとします。
エージェントの速度の大きさは常に一定、ノイズはゼロとします。このようなルールを課すことで、周囲と同じ方向に進もうとする力と、逆方向に進もうとする力を競合させ、エージェントの運動に変化を生じさせようという目論見です。
ここでも擬人化表現を使いますと、こんどのエージェントは、自分の近くにいるやつらには付和雷同するけれども、それより遠くにいるやつらとは仲が悪くてつねに敵対していないと気が済まないようなやつらです。
このルールに従うエージェントの運動を見てみましょう。エージェントはオリジナルと同じく、L×Lのトーラス上を運動します。また、全エージェント数をNとします。エージェントの速度の絶対値はv、時間刻みはΔtであらわします。
計算の条件は、
v=0.03,L=10,N=400,Δt=1.0,r1=1.0
です。
結果
まずは、オリジナルの論文で秩序変数とされている量、vaの時間変化をみていきましょう。vaの定義は、
va=|Σi vi(t)|/Nv
で、エージェントの向きのそろい方を示す指標です。すべてのエージェントが完全に同じ向きを向いている場合に1となり、向きが完全にばらばらだと0となります。
まずは、r2=1.0(=r1)の場合です。これは、Vicsekモデルでノイズがゼロの場合にあたります。横軸に時間、縦軸にvaをとってみます。初期条件は、位置・速度ともにランダムです。計算は1000ステップまで行っています。すると、vaはすぐに1に収束することがわかります。これは、全エージェントが同じ方向を向いていることを意味しています。Vicsekモデルの意味での秩序相です。
続いて、r2=0.4とした場合を見てみましょう。他の条件はすべて一つ前のものと同じです。
すごく、あばれています。これは一体何を意味しているのでしょう。
この挙動の意味は、エージェントの運動のスクリーンショットを見てみればわかります。
上の図で、左がr2=1.0の場合、右がr2=0.4の場合です。r2=1.0では、全エージェントが巨大なクラスタを形成し、同一方向に運動しています。ところが、r2=0.4では、形成されるクラスタのサイズは、r2=1.0のときよりも小さくなっています。各クラスタに属するエージェントは同一の方向に進むのですが、それぞれのクラスタの進行方向がばらばらなので、vaは大きな値をとることができないのです。さらに、クラスタどうしが衝突しても、合体してサイズの大きいクラスタになることはまずなく、分裂するか回避しあいます。
このような挙動を示す原因は、2種類の相互作用を競合させたことにあります。エージェントは、周囲r2の範囲に存在するエージェントと同じ方向に進みたがります。これはエージェントどうしの引力とみなせます。ところが、r2よりも遠くにいるエージェントとは逆方向を向きたがりますので、これは斥力として働きます。クラスタの直径が大きくなると、同一クラスタ内にいるエージェントに対しても斥力が働いてしまうので、クラスタの直径を増やすということは困難になるのです。
上の例からわかるように、どうもこの系のエージェントの運動は、r2を変えていくと、単一クラスタを形成しやすい状態から、単一クラスタを形成しにくい状態へと、定性的に変化するようです。この変化を定量的に扱うパラメータとして、単一の巨大なクラスタを形成するのに要した時間(あるいは、vaが1になった時間)tsを考えます。単一のクラスタを形成できない場合には、ts=∞となりますが、今回は10000ステップまでしか計算を行っていないので、クラスタを形成しない場合にはts=10000としています。さらに、系が秩序だったときには有限の値をとるパラメータを用いたいというこころがあるので、tsの逆数を、この系を特徴づけるパラメータとして採用します。
次の図は、横軸にr2、縦軸に1/tsをとってプロットを行ったものです。
r2が1に近いときは、1/tsは0.005付近の値をとります。r2を減少させていくと、r2~0.9付近で、1/tsは急激に減少します。r2~0.8付近では、値にばらつきがありますが、1/tsは0.0002以下となります。さらにr2が小さくなると、最終的に巨大なクラスタが形成されるのかどうかすらわかりません。
このように、エージェントの相互作用に競合する要素を入れてやることで、意図的にノイズを加えなくとも、系の運動が秩序だったものから無秩序的なものへと変化する様子が確認できました。
最後に、vaの時間変化をもういちど見てみます。r2=1.0のときは、すぐに巨大なクラスタが形成されます。r2=0.8付近では、vaは大きく振動しながら、巨大なクラスタを形成したりしなかったりします。この巨大な振動は、じつは、系が二つの大きなクラスタに分かれて運動している様子を示しています。クラスタの衝突ごとに、vaが大きく乱高下します。衝突がうまいぐあいにいくと、クラスタの合体がおこりますが、衝突の頻度は低く、かつ適切な角度で衝突しないと合体しませんので、vaはなかなか1に収束しません。r2=0.4では、大きなクラスタが形成されるようなそぶりすらありません。最終的に巨大なクラスタになってしまうのかどうかすらわかりません。
たくさんある問題
Q. つーかこれ、ほんとに相転移なんですか?
A. わかりませんorz
Q. そうだとしたら、秩序変数は?
A. わかりませんorz
Q. これって、密度とか粒子数で挙動変わりますよね
A. たぶん。。。(やってません)
Q. 無秩序相のvaの挙動になにか法則性はあるの?
A. わかりませんorz
Q. つーか、いったいなにがおもしろいの?
A. アレとか、アレとか、そのへんとからみがあったらなぁ、と思って。
Q. 先行研究、あるんじゃないの?
A. 私の探し方が悪いのか、なかなかみつかりません。ご存知の方がいらっしゃれば、マジで教えていただきたいです。
参考文献
Boid にノイズを加えて相転移させた -Swarm of Trials-
今回のネタについて参考にさせていただいたSwarm of Trialsさんの記事。Vicsekモデルについて丁寧な解説があります。
Boids (Flocks, Herds, and Schools: a Distributed Behavioral Model)
Boidの生みの親、Craig Reynoldsさんのサイト。
Novel Type of Phase Transition in a System of Self-Driven Particles
Vicsekモデル。
Spontaneously ordered motion of self-propelled particles
基本的に上と同じですが、揺らぎや感受率にも言及しており、おおっ、相転移っぽいなと思わせます。さらに、XYモデルとの関連も。
Noise-induced transition from translational to rotational motion of swarms
並進運動から回転運動へのノイズ誘起相転移。なんかいろいろとバリエーションがあるようですね。arxivで読めるのはこちら。Google Scholarでぐぐると関連論文がたくさん出てきます。。。
コメントの投稿
No title
はじめまして
面白かったのでコメントさせてください。
Q. これって、密度とか粒子数で挙動変わりますよね
rとの兼ね合いだけで特に意味はないような気がします
空間全体の広さとか障害物等の設置の方が
より挙動が変化しそうです
Q. 先行研究、あるんじゃないの?
アレとかアレに相当するのかもしれませんが
ハトでそういう研究がされていたかもしれません
心理学系の論文を和文で紹介されていたのを読んだ覚えがあります
何らかの評価関数を導入することで
現実の生物の挙動などにこの現象を発見することができるかも
面白かったのでコメントさせてください。
Q. これって、密度とか粒子数で挙動変わりますよね
rとの兼ね合いだけで特に意味はないような気がします
空間全体の広さとか障害物等の設置の方が
より挙動が変化しそうです
Q. 先行研究、あるんじゃないの?
アレとかアレに相当するのかもしれませんが
ハトでそういう研究がされていたかもしれません
心理学系の論文を和文で紹介されていたのを読んだ覚えがあります
何らかの評価関数を導入することで
現実の生物の挙動などにこの現象を発見することができるかも
No title
>戯言さん
コメントありがとうございます。
r2が0.8くらいの微妙な領域では、ふたつのクラスタが"ちょうどいい"角度で衝突
しないと巨大クラスタが形成できません。ですので、密度や粒子数を増やして、
クラスタの数が増える状況をつくってやれば、巨大クラスタが形成されるまでの
時間が大幅に増加するのではないか、と考えています。
ご指摘の通り、空間の大きさを増やすことでも同様の作用があると思います。
(無限時間待ったあとの状態を調べるなら、あまり変化は無いかもしれません)
障害物については、ちゃんと考えてませんでした。
平坦な空間で、どれだけ変な挙動をさせられるかに興味があったので。
心理学系ですか。まったく盲点でした。(物理系のばっかり探してました)
Google Scholarで探してみましたが、該当しそうなものは見つかりませんでした。
また、折を見て探してみることにします。
情報ありがとうございました。
コメントありがとうございます。
r2が0.8くらいの微妙な領域では、ふたつのクラスタが"ちょうどいい"角度で衝突
しないと巨大クラスタが形成できません。ですので、密度や粒子数を増やして、
クラスタの数が増える状況をつくってやれば、巨大クラスタが形成されるまでの
時間が大幅に増加するのではないか、と考えています。
ご指摘の通り、空間の大きさを増やすことでも同様の作用があると思います。
(無限時間待ったあとの状態を調べるなら、あまり変化は無いかもしれません)
障害物については、ちゃんと考えてませんでした。
平坦な空間で、どれだけ変な挙動をさせられるかに興味があったので。
心理学系ですか。まったく盲点でした。(物理系のばっかり探してました)
Google Scholarで探してみましたが、該当しそうなものは見つかりませんでした。
また、折を見て探してみることにします。
情報ありがとうございました。