東京工業大学 ロボット技術研究会

東京工業大学の公認サークル「ロボット技術研究会」のブログです。 当サークルの日々の活動の様子を皆さんにお伝えしていきます。たくさんの人に気軽に読んでもらえると嬉しいです。
新歓特設ページ        ロボット技術研究会 HP        ロボット技術研究会 twitter公式アカウント

AI研

「ロボット技術研究会」通称「ロ技研」は、その名前の通りロボットの制作や研究はもとより、電子工作や機械工作、プログラミングなどの幅広い分野にわたるものつくり活動を行っています。

カテゴリ一覧: loading

Dynamorphism 〜 Haskellでも動的計画法がしたい! 〜

この記事は rogy Advent Calenderの20日目の記事です
また、この記事の単体のHTMLファイルがあります。
単体のHTMLファイルの方がスタイルが良い感じになっているので、出来ればそちらを読んでください。
続きを読む

簡単・便利な関数

この記事はrogy Advent Calendar 2015の3日目の記事です.
修論シーズン真っ盛りのニックさんです.
AdventCalendarをロ技研でやるみたいなので,ふわっとした記事を書きます.
冷静に俺は修論を書くべき.



突然ですが皆さん,このような経験は無いですか?
ケース1:「ゲームのエフェクトを付ける時の透明度を0から255にして,また0に戻したい!
でもどんな関数にしよう…….」

ケース2:「二足歩行ロボットのモーションを作るぞ!
キーフレームでの姿勢とその間の補間関数はどうしようかな.」

ケース3:「音声を生成するプログラムを作ろう!
音量は最初は大きくて,だんだん減衰するようさせたいけど,どんな関数かな?」


何か数理的な処理の入るものづくりの場合には,必ず「関数」というものが出てきます.
数学的な難しい話ではなく「こういう引数の時こういう値が来る!」程度の話です.
その時どんな関数を使えば良いのかは知っていないとなかなか自分では設計できません.
気合を入れて3次スプライン曲線などを作ってフィッティングさせても良いですが,
それよりも簡単で便利な関数があれば計算コスト的にも実装コスト的にも嬉しいです.

今回の記事の内容は簡単で便利な関数をいくつかご紹介したいと思います.
特に僕自身ゲームを作る人間なので,ゲームでの利用例なんかも合わせて紹介できたらなと思います.
(ここで簡単とはできるだけ次数が小さく,初等関数程度で実装できるものを指します.)



ガウス関数
gauss
$$f(x) = \frac{1}{\sqrt{2\pi\sigma}}e^{-\frac{(x-\mu)^2}{2\sigma}}$$
 理学,工学ともによく使われる関数系です.正規分布なんて呼ばれたりもします.$\mu$を中心に$\sigma^2$程度の分散で山を作る関数です.
ちなみに山を作りたいだけならば頭に付いているいる定数項の$\frac{1}{\sqrt{2\pi\sigma}}$は要りません.定数項が付いていると確率の性質$\int dx f(x)=1$を満たすので,確率的な処理をしたい場合はガウス関数にしましょう.もっともプログラミング言語のライブラリでは正規分布に従った乱数を返す関数が用意されているので,自前の確率計算をするとき以外は使わないかもしれません.
 ゲームでキャラの与えるダメージをぶれさせたり,ぼーっと光る明かりの表現なんかをしたいときにはガウス関数はよくお世話になります.



シグモイド関数
sigmoid$$ f(x) = \frac{1}{1+e^{-ax}} $$
 続いてニューラルネットでの活性化関数としてもよく使われるシグモイド関数です.$f(-\infty)=0,f(\infty)=1$となる関数で,$a$の大きさによってその鋭さが変わってきます.特に$a\gg1$の時には殆どステップ関数($f(x)$が$x>0$の時のみ1という値を持つ関数)となるため,ステップ関数の拡張として考えることも出来ます.普通のステップ関数は$x=0$で微分が出来ないので性質が悪いですが,シグモイド関数はどこでも微分ができるので嬉しいです.
特に$x$の定義域なども無いので,何も考えずにこの関数に突っ込めば,0から1の値を返してくれるので精神的にも安定します(?).
ゲームならば敵AIでプレイヤーとの体力差を$x$として,その時の敵AIの攻撃積極度みたいなのをシグモイドにすると性質が良いかもしれませんね.
 ここで注意ですが,$x=\infty$にしないと$1$を返さない関数なので,モーションの補間などには使わないほうが良いでしょう.そういう場合は後述のease-inout(smoothstep)を使うと良いです.



ease-in,ease-out
ease
$$
  \begin{array}{ll}
    f(x) &= x^2 \\
    f(x) &= x(2-x)
  \end{array}
$$

 大げさな名前が付いていますが,本質はただの2次関数です.それぞれ$x=0,1$の場所で極小極大になるように係数が選ばれています.定義域はどちらも$0\leq x\leq1$です.
 主に使われる場所としては値の補間でしょうか.$x$が0から1で変化するときに,対応する値$y=f(x)$を滑らかに変化させるときに使います.$y=x$にするよりかは滑らかに繋がるので,動き始めや動き終わりの慣性みたいな物を表現できます.
 誰でも思いつきそうな関数ですが,お約束として知っておくと便利かもしれません.ゲームでの例ならば,キーフレームとして与えられているボーンのモーション間での補間で便利です.



ease-inout (smoothstep)
ease-inout$$ f(x) = x^2(3-2x) $$
 今度は3次関数です.動き始めと動き終わりで微分値が0となっている滑らかな形状です.これも$x=0,1$の場所で極小極大となるように係数が選ぶを自然とこの関数形になります.また,GLSLなどのシェーダー言語ではsmoothstep()という名前でこの関数が実装されています.その時は定義域$0\leq x\leq1$外では$f(x)=0,1$というように定数関数で滑らかに繋がるように実装されます.
 0から1までの間を滑らかに微分可能な形状で結ぶため,先ほど紹介したシグモイド関数と似ていますが,こちらは0や1に到達するので補間をするときには便利です.




impulse
inpulse$$ f(x) = kxe^{(1-kx)} $$
 この関数はIngo Quilezさんが自身のサイトで紹介している関数です.Ingo Quilezさんのサイトは凄いサイトなので,気になる方は是非とも参照してください.

 このimpluse関数は$f(1/k)=1$を満たす関数で,$x=1/k$までの間は急激に上昇,$x=1/k$付近でピークを持ち,
それ以降はゆっくりと0へと漸近していきます.最初にドカっと値を与えて,後はそこから緩和!みたいなエフェクトを作るときには重宝しそうです.




almost Identity

$$
  f(x) = \left\{ \begin{array}{ll}
    (2n-m)\big(\frac{x}{m}\big)^3 + (2m-3n)\big(\frac{x}{m}\big)^2 + n & (0\leq x \leq m) \\
    x & (m \le x)
  \end{array} \right.
$$

almostIdentity おなじくIngo Quilezさんが紹介している関数の1つがalmost Identityです.式は一見複雑に見えますが,実際は3次関数と1回の比較演算から成り立っています.
 $f(0)=n,f(m)=m$という関係を満たしていて,バイアスとして$n$,補間する範囲を決定する$m$という2つのパラメータを持ちます.
この関数は殆ど$y=x+n$ですが,原点付近で3次関数で滑らかに接続されている微分可能な関数です.

線形な補間をするときに立ち上がりのカクつきを減らしたい!って時には便利なのではないでしょうか?




レナード-ジョーンズ・ポテンシャル

LJ$$ U(r) = 4\epsilon\Big[ \Big(\frac{\sigma}{r}\Big)^p - \Big(\frac{\sigma}{r}\Big)^q \Big] $$
 ゲーム開発者の為のAI入門でも解説されていたポテンシャルです.元はと言えば分子動力学などで使われている原子間の相互作用ポテンシャルの経験的なモデルだそうです.ポテンシャルなので$F(r)=-\frac{dU}{dr}$をオブジェクトに働く力として与えてあげると,極小値$r=r_{\rm min}$付近へと近づいていく動きを実現出来ます.
$\epsilon$はポテンシャルの谷の深さを表すパラメータで,$p,q$は引力と斥力の次数,$\sigma$は距離のスケールです.
 よく使われる次数としては$(p,q)=(12,6)$でしょうか.目的に応じてパラメータチューニングされます.$r\rightarrow 0$に向かうと$U(r)\rightarrow\infty$となるので,「物体間の距離が0にはならない」という衝突を回避する動きができます.逆に物体が極端に遠いと$U(\infty)=0$より殆ど互いに力を与えること無く相関0となります.丁度良いスケールでオブジェクトが存在しているならばゲームのホーミング弾や,目的位置へのポテンシャルとして利用しても良いかもしれません.

レナード-ジョーンズ・ポテンシャルは優秀なポテンシャルに見えるのですが,明らかな欠点が2つほどあります.

  • チューニングすべきパラメータが多く,直感的で無い.
  • $r\rightarrow 0$のとき$U(r)\rightarrow\infty$となるので,値が発散する可能性がある.
これらの問題を解決できてレナード-ジョーンズ・ポテンシャルの代替として使えるポテンシャルが,
モース・ポテンシャルです(後述).




モース・ポテンシャル

morse$$ U(r) = \epsilon\Big[\Big(1- e^{-a(r-r_0)}\Big)^2 -1 \Big] $$
 モース・ポテンシャルも元は分子動力学で使われる近似的な分子間力のモデルです.$\epsilon$はポテンシャルの谷の深さ,$r_0$は極小値,$a$は谷の幅を表します.極小値や谷の幅などのパラメータが直感的で,使う側としてはチューニングがしやすいです.
 レナード-ジョーンズ・ポテンシャルとの大きな違いとしては$U(0)$が発散しない有限の値となることが挙げられます.これは距離0でも状態が許されるということを意味していて,シミュレーションの時間刻み幅が大雑把な場合でもオブジェクト間の距離が発散することを防げます.ゲームなどにおいては物理的な厳密な特性はあまり重要ではないので,良い性質ではないでしょうか?

またレナード-ジョーンズ・ポテンシャルに比べて緩やかで丸みを持った形状なので,柔らかな挙動をします.
僕の最近のオススメポテンシャルです.




フォンミーゼス分布

VM$$ f(\theta) = \frac{e^{\beta\cos{(\theta-\mu)}}}{2\pi I_0(\beta)} $$
 最後にとてもニッチな関数をご紹介します.フォンミーゼス分布は「円周上でのガウス関数」と言えるものです.
定義域は$0\leq \theta \leq 2\pi$で,$\mu$がピークの中心位置,$\beta$がピークの幅を表します.分母の$I_0(\beta)$は0次の第一種変形ベッセル関数と呼ばれる特殊関数です.
 こんな難しい関数を出してしまうと当初の主旨であった「簡単な関数」の範疇から外れてしまいますが,実用上は分母の$2\pi I_0(\beta)$の項は適当な係数で決めてもらって大丈夫かと思います.
 使い所としては,ゲームならば「敵が特定の方向を中心にある程度ランダムに登場させる」といった,
方向の絡んだ乱択処理の重みに使うと便利なのでは無いでしょうか?



------------------
今回ご紹介する関数は以上です.できるだけ簡単で使いやすいものを紹介したつもりです.
「三角関数とか$e$とか使ってて」全然簡単じゃないじゃん!って思うかもしれませんが,
今どきの計算機は早いのでゲーム内でリアルタイムに使っても問題ないと思います.
自作のオレオレスーパー関数を考える前に,初めに既存の関数を適当にフィットさせると時間的にも精神的にも良いプロトタイピングができるので,是非とも皆さん使って行きましょう.

新歓展示のお知らせ(と蔵本モデルシミュレーター)

花の落ちてしまった桜、まだ制服に着られている新入生―

もう4月ですね。就活真っ最中のニックさんです。
さて、4月といえば新入生シーズンなわけですが、ロボット技術研究会では新入生のための活動をいろいろやるそうです。
詳しくは上記リンクの新歓特設サイトを見てくださいね。

特に4/8(水)13:30 ~16:304/10(金)16:30~18:00にはS516の教室で新入生のためのロ技研展示会(新歓展示)を行う予定です。
もの作りサークルに興味があるな~って新入生の方は見学に行くと良いのではないでしょうか?



さて、新入生歓迎ムードのロ技研ですが、その裏では新歓展示の為に修羅場る部員が見られます。
僕も毎年なんか展示しているのですが、今年は就活ということもあって少し展示に足踏みしていました。
しかし、学生最後の新歓展示という事もあって、1週間程度で作品を作ってみました。偉い!
蔵本モデルシミュレーター


モダンでフロントエンドな事をやってみたいなぁ~って思ったのでjade,less,JS(CoffeeScript)とかを使って作りました。
vue.jsとcreate.js,underscore.jsあたりを使っています。モダンですね。

蔵本モデルの詳しい話はシミュレーターのページに書いてあるので、興味のある方はご覧になってください。
新歓展示当日は僕は展示場所にいるかはわかりませんが、いなければ13ざくろくんが彼の展示物と一緒に展示してくれているはずです。

それでは皆さんぜひお暇ならロ技研新歓展示に足を運んでみてくださいね。

SNSで知る複雑ネットワーク

皆さん、就活や研究は進んでいますか?
僕は進んでいません。ニックさんです。
そんな日々の鬱憤を晴らすために、今日は複雑ネットワークについて勉強したいと思います。



複雑ネットワークとは現実に存在するネットワークがどのような構造となっているかを研究する学問分野です。
ロボット技術研究会とは無縁(?)に思える領域かもしれませんが、
実はロボット技術研究会に深い意味を持つ学術領域でもあります。
何故かと言うと……Twitter_logo_blue
そう、Twitter



実はロボット技術研究会の部員の半数以上はTwitterなどに代表されるSNSを利用しています。

今や我々の生活を語る上で欠かせないSNSによるコミュニケーション。
その裏に潜む数理をロボット技術研究会のTwitterネットワークを例に勉強してみましょう!


1,ロ技研のTwitterネットワークを見てみよう!
まずはロボット技術研究会に所属している部員達が織りなす、Twitter上でのフォロー・フォロワー関係を
グラフを用いて図示してみましょう。
graph
なんなんだこれは………
(ちなみにこのデータの取得には、部員の13ざくろ君にスクリプトをぶん回してもらいました。感謝!)
グラフの青い円は個人のTwitterアカウントを表していて、矢印はフォロー・フォロワー関係を表しています。
が、全くわかりません。

何故かと言うと、個人のTwitterアカウントに対してその結合が密すぎるからです。
図示以外にネットワークを測る為の物理量として、クラスタ係数平均最短経路長などがあります。
大雑把に説明すると、
  • クラスタ係数:「友達の友達が友達であるか?」の度合い。密度。
  • 平均最短経路長:グラフの直径
となります。
実際にロボット技術研究会の織りなすネットワークのクラスタ係数と平均最短経路長を調べてみると……?
  • クラスタ係数 :  0.71
  • 平均最短経路長 :  1.61
となっていました。
大雑把にロ技研ネットワークを考察すると、
比較的密に結合していて」「任意の部員に1.61人経由でたどり着ける」と言えます。
こういったネットワークをスモールワールド・ネットワークなんて呼んだりもするそうです。

結論:ロ技研は仲良し






2,パクツイはどのように広まっていくか?
ロボット技術研究会の仲の良さを再確認したところで、
このネットワーク上で面白そうな現象の数理モデルを構築してみましょう。

まずはこの画像を御覧ください。
wakarukigasuru
他の人が投稿したツイートと同じツイートを短い期間で何度も投稿する……
これが悪名高きパクツイと呼ばれる文化です。

ロボット技術研究会のタイムラインでは(内輪ネタとも言うべき)気持ち悪いパクツイを行う風潮があります。
しかしながら、いつでもパクツイになるかどうかは非自明であり、
どのようにパクツイの連鎖が生まれるのかは明らかになっていません。

そこで、パクツイが生まれる現象を数理モデル化してみましょう!

wakarumodel

上の図がパクツイの数理モデルの図示です。
いわゆるSIRモデルを変形したようなモデルとなっています。
まずはじめにパクツイの元となるツイートを行った人物をInfectedとしましょう。
Infectedをフォローしている人がそのツイートを見て、確率pでパクツイを行います。
パクツイを行った人物もまたInfectedとなり、次々と連鎖的にパクツイが行われるわけです。害悪ですね。
また、一度Infectedになった人物はRemovedとなって隔離されます。

このような簡単なモデルを用いて、一人の人物からパクツイが広がるかどうかを
実際のロ技研のTwitterネットワーク上で数値シミュレーションを行ってみました!
その結果がこちら。

wakaru2

横軸がパクツイの感染確率pで、縦軸mはネットワーク全体にパクツイが広がったかどうかの度合いです。

眺めてみるとp=0.01までは全くパクツイが広がっていませんが、
p>0.01付近から一気にパクツイが爆発的に広がっている用に思われます。
この爆発的な立ち上がりこそロ技研TLのパクツイの害悪さの全ての根源であるようにも思えますね。

このように「一気に値が立ち上がる現象」はTwitterでのパクツイだけではなく、
様々な身の回りの現象に見られるのですが、その話は難しいのとツッコミの激しくなりそうなので割愛します。

結論:ロ技研のTwitterでの害悪さを数値的に確認できた!




みなさんもSNSの使い方には気をつけましょう。

モンテカルロ法で2048AI

 AI研所属14のいしづです。このたびは記事を書かせていただくことになりました。なぜかAI研カテゴリ初の投稿となっており、おっかなびっくりしてます。

さて私が取り組んでいるお題は「2048を自動で解くAI」です。
みなさんは2048というゲームをご存知でしょうか。

言葉で説明するよりも公式サイト(http://gabrielecirulli.github.io/2048/)にいって
実際にやってみるのがいいと思います。簡単に説明すると、
タイルを移動して同じ数字を足し合わせて数を大きくしていくゲームです。


まず初めに本家のソースコードに手を加えて、自動で動かせるようにしました。

ここからはAIを作るという一番のキモなわけですが、今回は強化学習のモンテカルロ法を用いました。

マサカリを恐れずに言うと、
テキトーに行動して結果によって行動を評価する
 のがモンテカルロ法です。

今回の2048AIにおいては
・ゲームオーバーまで上下左右動かしていって
・「最終スコアをもとに
・出す手を決める
とい う流れになっています。

そんな感じで実装していくと、こんな風にそこそこ強いAIが出来上がります。
モンテカルロ法の利点はスコアを計算するだけなので、
 自分で評価関数を考えなくても良い点にあります。

これはつまり2048の解き方やコツを知らずとも2048solverが作れるということです。
なかなか面白い話ですね。プログラムさんは試行錯誤の結果を出して
いるだけで本当に2048の解くコツというものはわかっていないわけです。
少し哲学じみていますね。

話が脱線してしまいました(汗)今回はモンテカルロ法をつかって2048のAIを作ってみました。
しかし、スコアは人間に及ぶものではないので、
人間と同程度のスコアをだすAIが作れたらいいなと思います。2048AI
ギャラリー
  • たのしいロボット帝国 製作物紹介
  • たのしいロボット帝国 製作物紹介
  • たのしいロボット帝国 製作物紹介
  • NHK学生ロボコンチームMaquinistaの紹介(2017)
  • NHK学生ロボコンチームMaquinistaの紹介(2017)
  • 関東春ロボコン 準優勝!!
  • 関東春ロボコン 準優勝!!
  • 関東春ロボコン 準優勝!!
  • 関東春ロボコン 準優勝!!
記事検索
最新コメント