読者です 読者をやめる 読者になる 読者になる

人工知能に関する断創録

人工知能、認知科学、心理学、ロボティクス、生物学などに興味を持っています。このブログでは人工知能のさまざまな分野について調査したことをまとめています。最近は、機械学習・Deep Learningに関する記事が多いです。



L-system入門

複雑系 人工生命

今回は、植物の成長をモデル化したLindenmayer system、略してL-systemの実験をしてみます。ライフゲームと同じく非常に単純な規則から複雑な形状が発生する複雑系の興味深い例です。

L-system

L-systemは、初期文字列と書き換え規則から構成されます。たとえば、

初期文字列:b
書き換え規則1:a -> ab
書き換え規則2 : b -> a

書き換え規則は、->の左側を右側に書き換えろという意味です。すごく簡単でしょ?この書き換え規則を初期文字列に適用します。この例の場合、

b -> a -> ab -> aba -> abaab -> abaababa -> ...

のような感じで書き換えていきます。ポイントは、現在の文字列のすべての文字に対して書き換え規則を適用することです。書き換え規則の左側が必ず1文字(文脈自由)でかつ決定論的に書き換えていくL-systemをDeterministic Context Free (DOL) Systemsと呼びます。

Turtle Graphics

L-systemを画像として描画する方法がTurtle Graphicsです。L-systemの各文字に描画コマンドを割当て、前の文字から順番に「亀」を動かしていくことでさまざまな模様を描けます。何で亀なんだ・・・という感じがしますが、元となったLogo言語に由来するようです。具体例で見てみるとすごく簡単です。

たとえば、

初期文字列: F-F-F-F
書き換え規則: F -> F-F+F+FF-F-F+F

のようなL-systemを考えます。使われている文字は、F、-、+の三種類です。これらの各文字に対して次のような描画コマンドを割り当てます(fは後で使います)。

F : 亀の通り道に線を描きながら前方に距離dだけ移動させる
f : 線を描かずに亀を前方に距離dだけ移動させる
+ : 亀の向きを左にδ度だけ回転させる
- : 亀の向きを右にδ度だけ回転させる

ここで、dとδはパラメータで自由に設定できます。たとえば、dを1マス、δを90度として、FFF-FF-F-F+F+FF-F-FFFという文字列を描画すると下のような形になります。

f:id:aidiary:20131125213432p:plain
(The Algorithmic Beauty of Plants, p.7より引用)

砂浜の上の亀のように亀が通った道筋で絵を描くわけですね。というわけでいろいろな例を試してみたいと思います!

コッホ曲線

f:id:aidiary:20131125213648p:plain

後述するNetLogoのプログラムを実行した様子を表しています。initial-stringが初期文字列を表します。rule1とrule2が書き換え規則です。2つまで指定できますが、1つの場合は片方を空にしておきます。step-sizeが移動距離d、angle-incrementが回転角度δのパラメータです。(initial-x, initial-y)は亀の初期位置です。初期状態では亀は上方向(0度)を向いていると仮定しています。画像の上にあるticksは書き換え規則を適用した回数を表しています。この形は有名なフラクタルコッホ曲線(Koch Curve)です。

f:id:aidiary:20131125214015p:plain

これはコッホ島(Koch island)です。

同一初期文字列からのさまざまな派生

書き換え規則を変えることで同一の初期文字列からさまざまな形状へ派生していきます。下の4枚はすべて初期文字列がF-F-F-Fですが、まったく違う図形へ成長していきます。

f:id:aidiary:20131125214347p:plain
f:id:aidiary:20131125214351p:plain
f:id:aidiary:20131125214355p:plain
f:id:aidiary:20131125214358p:plain

ドラゴン曲線

文字列や規則は複数指定することもできます。下の例では、A、Bという二つの文字を導入しています。ただ、どちらの文字もFと同じ意味で「描画しながら前へ進め」というコマンドです。

f:id:aidiary:20131125214502p:plain

この図形はドラゴン曲線(Dragon curve)と呼ばれるフラクタルです。

f:id:aidiary:20131125214906p:plain

これもドラゴン曲線ですが、さっきのと少し違いますね。ここで、XとYは「何もしないコマンド」です。

シェルピンスキーのギャスケット

最後にもう一つ有名なフラクタル、シェルピンスキーのギャスケット(Sierpinski gasket)です。

f:id:aidiary:20131125215348p:plain

NetLogoプログラム

上のNetLogoプログラムです。NetLogoをインストールして、下のファイルをダブルクリックするだけでGUIが立ち上がります。Mac版のNetLogoだと日本語コメントが使えたのですが、Windows版は日本語が使えませんでした。もしかしたら文字化けするかもしれません。

L-system.nlogo

NetLogoはTurtle Graphicsに基づいているため、L-systemはわりと簡単に書けます。ただ、構文が独特なので慣れないとかなり戸惑いますね。NetLogoは、Complexity Explorer(2013/10/21)でも紹介したので興味があったら読んでください。

植物はどうなった・・・

L-systemでいろんなフラクタルが描けるのは面白いですね!ただ実はこれだけでは肝心の植物を描くことができません。植物を描くには、新たにスタックへのプッシュとポップを表す記号を導入する必要があります(上のプログラムではすでに入ってますが・・・)。というわけでL-systemで植物を描く方法は次回(2013/11/26)取り上げたいと思います。

参考文献