＜前文＞
一週間早過ぎます。
AIについてとか、データサイエンスについての勉強をどうするのか、この一週間で考えて決めようと思っていたのですが、何も考える間もなく一週間経ってしまいました。少しは何か考えた事はあるだろうと思って頭を絞ってみましたが、何も思いつきません。
ただ私の中の結論はもう出ています。データサイエンスやAIを勉強したからと言って成功出来る確率はかなり低いと言う事です。はっきり言えばポケモン並みの人気のあるゲームをゼロから作成する方が確率的に高いと思っています。ので、もうデータサイエンスやAIについてあまり言うのは止めてどうすれば、ポケモン並みの人気のあるゲームを作成出来るのかについて考えたいと思います。
と言っても今週は何も考えていないので来週から考えます。
それでは、勉強を始めます。
＜本文＞
今週もRPGの作成は一端お休みしてAIについて勉強します。
＜Unreal Engine 4 Tutorial – AIの勉強＞
先々週からやるやる言って全く勉強出来なかったUnreal Engine 4 Tutorial – AIをまず、勉強します。
1. Unreal Engine 4 Tutorial - AI - Part 1 The Behavior Tree
まず、新しいプロジェクトを作成しました。名前はAIStudy2です。BPで作成しました。チュートリアルでは何も言っていませんが、BPを選択しているように見えます。
今回は、このマップ上をうろつくNPCを作成するそうです。
CharacterBPからNPCと言う名前のクラスを作成します。MeshにはSK_Mannequin、Animクラスには、ThirdPersonAnim_BPを選択します。
AIController、Behavior TreeそしてBlackBoardを作成します。
NPCのAI Controller ClassにNPC_AIを選択します。
AI Controller ClassであるNPC_AIを開いて、event graphに以下に示したノードを作成します。
次にBehavior TreeであるNPC_BTを開き、Blackboard AssetにNPC_BBがセットされているのを確認します。
ここまでは、基本通りですね。
NavMeshBoundsVolumeとNPCをレベル内に追加します。
Behavior Treeを以下に示すように作成します。
カスタムTaskであるFindRandomLocationを以下の様に作成します。
BlackboardにVectorタイプであるTargetLocation変数を作成します。
テストします。
NPCがあたりを走り回ります。
ここまでは、今までの知識で知っている範囲ですが、後13回もチュートリアルが残っています。一体何をこれ以上勉強するのでしょうか？
2. Unreal Engine 4 Tutorial - AI - Part 2 AI Perception
Perceptionとありますね。AIが何かを知覚する方法があるのでしょうか？楽しみです。
軽く終わる内容じゃなかったです。
まず、Behavior Treeは以下のようになりました。
新たに追加された部分ですが、FindPlayerLocationは
こんな感じです。
ここまでは何となく今までの知識で理解出来るのですが、この次です。
NPC_AIにAIPerceptionを追加します。
え、何これ？と思っている間に
次々にAIPerceptionの設定をしていきます。
次にThirdPersonCharacterBP内でAIPerceptionSimuliSourceを追加します。
更に、NPC_AIに戻って以下のノードを作成します。
テストすると追いかけて来ますが、AIPerceptionの使い方が全く分かりません。
チュートリアルは一端中断してAIPerceptionを勉強します。
3. AIPerception
まず、最初に見つけたのが、このサイトです。
- AIのフレームワーク内で知覚上のデータを提供する道具がAI Perception Systemです。
- これは、Pawnが環境からのデータ、例えば音が聞こえてくる方向、AIが何かによってダメージを受ける、AIが何かを見るなど、を受け取れるようにします。
- これらは、刺激受容体として働くAI Perception Componentによって達成されます。
と説明されていました。つまりNPC_AIに作成した
がそれらを司っていると言う事ですね。
Unreal Engine 4 Tutorial - AI - Part 2 AI PerceptionでAIPerceptionのdetailの設定をいじっていましたが、それについても以下に示すように説明されていました。
- AI Perception ComponentはAI PerceptionやSenses Configセクション下にある知覚を追加出来ます。
- 知覚の種類によって、違うpropertyが用意されています。
なるほど。これでチュートリアルでは以下に示すようにAI Sight configを選択したんですね。
サイトの方に思いっきりAI Sightについての説明がありました。
- AI Sight configはAIのキャラクターが見る事を可能にするパラメーターを定義する事を可能にします。
- 例えば、Sight RadiusにActorが入ったら、AI Perception Systemがアップデートのシグナルを出します。
- 更に見たactorをパスします。
とありました。
見たアクターをパスするとは、どういう事でしょうか？
多分これを指しているのでしょう。Actorがパラメーターとしてパスされています。
確か、この部分だけ設定を変えたはずなので、これが何なのかだけ調べます。
サイトの説明です。
敵か、中立か、味方がこの近くをトリガー(trigger)したのかを特定します。
あれ？
関係なくない。
記憶違いかもしれませんね。
次にThirdPerson_BPに仕掛けたAIPerceptionStimuliSourceについて知りたいです。
Stimuliは知らない単語ですね。sti·myuh·laiと発音するそうです。このオンライン辞書によると
と説明されています。反応を引き起こすための刺激と解釈してよさそうですね。
あ。もう理解出来ました。NPCの視界にプレイヤーがコントロールするThirdPerson_BPが入ってきたらstimuliするわけですね。
このサイトの説明でもそのように解説してますね。
メンドクサイので訳なし。
うーん。AIPerceptionStimuliSourceのdetailの以下の部分ですが、この設定をチュートリアルでしたのか覚えていません。
見た感じこの部分の設定は必要にみえますが？
最後に残った部分がこれです。
サイトの説明は以下のようになっていました。
このイベントはPerception Systemがアップデートを受け取った時、発生します．．．
そういう事ですね。
大体理解出来ました。
一個分からないのは、
で、敵、味方、中立と判断しているのに、ターゲットになるアクターがAIPerceptionStimuliSourceをコンポーネントとして保持していないといけないのはどういう事なのかと言う事ですね。
こういう時、ブループリントは不便ですね。中のコードが見れるともっと情報が得られるのですが、完全にブラックボックス化してしまってますね。
4. Unreal Engine 4 Tutorial - AI - Part 2 AI Perception もう一度
AIPerceptionを大体理解したので、もう一度チュートリアルの２を勉強します。
Behavior treeのselectorはBlakboardのCanSeePlayerブーリアン変数の値で決定されます。
このBlakboardのCanSeePlayerブーリアン変数に値を代入するためにAIPerceptionが使用されるはずです。
AIControllerクラスから作成したNPC_AIにAIPerceptionを追加します。
更に、AIPerceptionを選択してdetailsのAIPerceptionのSenses Configの1 Array elementsの＋をクリックしてelementを一個作成します。
その作成したelementにAI Sight configを選択します。
その後で、Detection by AffiliationのDetect Enemies, Detect Neutrals, Detect Friendliesにチェックを入れます。
やっぱりチェック入れてますね。チュートリアルで理由を説明していますが、何か良く分からないですね。どうやってプレイヤーがコントロールするキャラクターが敵か味方か判断するんでしょうね。
ThirdPersonCharacterBPに
を追加します。
更に、Auto Register as Sourceにチェックを入れてAlSense_Sightを選択します。
前回、この部分の記憶は全く残ってなかったです。
NPC_AIに戻って以下のコードをノードを使用して作成します。
これでBlakboardのCanSeePlayerブーリアン変数の値をAI_Perceptionを使用して決定する事が出来ました。
2回目は意味が良く分かりました。
5.Unreal Engine 4 Tutorial - AI - Part 3 Chasing the Player
今度は、何が追加されるのでしょうか？チュートリアルだと、part2のNPCの追いかけ方が余りにも間抜けだからそれを直すと言っています。あんまり追いかけ方が間抜けとは思わなかったので、どう直すのかも分かりません。
取りあえずやって行きます。
分かりました。追いかけている間はいいんですが、一端NPCがキャラクターを見失うと、適当な方向にずっと走って行ってしまいます。この事を間抜けと呼んでいます。なるほど確かに間抜けですわ。
まず、Behavior TreeのCan’t see playerを選択します。
Flow ControlのObserver abortsをSelfに変更します。
チュートリアルによると、
- None：結果が変化した瞬間にGo Random Locationの一連の動作を中止して、直ちにChase Playerの動作を開始します。
- Self：結果が変化した瞬間にGo Random Locationの一連の動作を中止して、selectorまで一端戻り、もう一度判断してから動作を開始します。
- Lower Priority：Can’t see playerより下ならk.と説明していました。何がo.k.なのか全然分かりません。
と説明されていましたが、良く分かりませんね。
良く見たら、behavior treeに色分けされていました。
Selfだとこんな感じです。
しかも丁寧に色分けされたノードについての説明がされていました。
なるほど、これだと、Go to random locationの一連の動作の何処でも動作を放棄してSelectorまで帰って、selectorからやり直すわけですね。
でもそれだと、noneの説明と矛盾しますね。
中止するノードがないわけですから、Go to random locationの一連の動作を終了してから停止するのが、noneになるんじゃないでしょうか？
もう一度、noneの説明を聞き返してみたんですが、noneの意味は、の後で、we want が挟まっていて、noneの説明をしているのか、自分がしたい事の説明をしているのか分からない構成になってました。
まあ、後で考えます。
この後、チュートリアルでは、bothにセットして、テストしてます。NPCが走っている途中で、キャラクターを見たら、走っているのを中止してキャラクターを追いかけるそうですが、映像を見る限りそんな風には見えません。
試してみます。
良く分かりませんね。
Waitの時間を50秒にしてみました。
今度は、待っている時間がキャンセルされてSelectorに戻っているのが分かります。
うーん。この実験を厳しくやれば、none、self、lower priority とbothの違いが分かりそうですが、今は止めておきます。
今度は、MoveToタスクを作り替えます。
新しいタスク、ChasePlayerを作成し以下のようなコードを組みます。
Behavior treeであるNPC_BTも作り替えます。
テストします。
スクリーンショットでは分かりませんが、滅茶苦茶カクカクしてます。
直すそうです。
Decorator、Cooldownを追加します。
全くカクカクしなくなりました。
チュートリアルによると、今度はNPCが進行方向を変える時に、一瞬で変えてしまうのでそれがオカシイといっています。
正直、私には分かりません。
それを直すそうです。
まず、NPCのUse Controller Rotation Yawのチェックを外します。
今度は、CharacterMovementを選択して
Orient rotation to Movementにチェックを入れます。
こっちの方がスムーズなのでこっちにするそうです。
私には違いが全く分かりません。
これでPart 3 Chasing the Playerは終わりでした。
うん。なんていうか、part3 はAI の勉強じゃないですね。
こんな内容ならこのチュートリアルをここでやる必要はないですね。一人で時間がある時にやればいいですね。
6. Unreal Engine 4 Tutorial - AI - Part 4 Patrolling NPC
これ以降は、感想だけ書く事にします。もしAI的に何か特別な事があったらその時は特別に詳しく説明します。
特にAI的に特質して書かなければならない事はないと思います。
UE4BPの使用方法で、Actorにvectorの配列を保持させてました。そのvectorの配列の要素をレベル内に表示させるために
Show 3D Widgetをチェックするのはどこかで役に立ちそうな豆知識でした。
後、PatrolPath クラスを作成してNPCが探索する個所を保持させて、NPCにはPatrolPathから作成した変数を持たせる所は、C++におけるゲームデザインのComponentの概念を正しく再現していると思いました。
Blueprintでプログラムを書いたとしてもソフトウェアデザインの基本からは逃れられないので、正しいBPプログラミングと正しくないBPプログラミングがあるはずです。
7. Unreal Engine 4 Tutorial - AI - Part 5 Patrolling NPC Continued
前回、作成したAIは決められたポイントを辿るだけでした。ポイントの最後に達すると、NPCは動きを止めてしまいます。今回は、最後のポイントにNPCが到達したら、最初のポイントに戻る場合と、逆ルートで最初のポイントまでさかのぼる場合の二つを作成します。
滅茶苦茶基本のIf節の条件が間違えて作成されていてループしません。
自分で直しましたが、これ以上このチュートリアルを勉強する意味はないように思えます。
ここで、このチュートリアルの勉強は、一端終了とします。
＜Artificial Intelligence: A Modern Approachの勉強＞
まあ、大体、先週の勉強で理解したのですが、世間で言われているような革命的な事態はAIには起きていませんね。データサイエンスでも言えると思いますが、AI、AIと騒ぎまくる連中は扇動して人々を不安に落とすのが目的で、実際にコツコツAIの研究をしている人とは一線を画してますね。
で、この本はそのコツコツ勉強している人たち向けの教科書です。
まあ、勉強する価値がある内容ではあるので、軽く読んでおく事にします。
先週、3章ほど読んだので、1週間に3章ほど読むペースで読みます。忙しい時は、サマリーだけ読みます。簡単なまとめをこのブログのおまけに載せる事にします。
1. 第4章 古典的な探索を超えて (Beyond Classical Search)
今週は忙しかったのでサマリーの内容だけまとめます。以下にサマリーの内容を記します。
この章では、observable, deterministic, そしてdiscreteな環境下でのゴールまでの最短距離を見つける古典的なケースを超えた問題のための探索アルゴリズムを調べました。
- 丘登り(hill climbing)のような局所的な探索(Local search)のメソッドは、メモリーに少ない数のノードを保持する事のみで、Complete-state formulationsで作動します。Simulated annealingを含む幾つかのStochasticなアルゴリズムが開発されました。Simulated annealingは、適切なcooling scheduleを与えられたときに、最適な解答を返します。
- 沢山の局所的な探索(local search)は、continuous spacesな問題にも適用されます。Linear programming やconvex optimization問題は、State spaceの形状、とobjective 関数の性質などの幾つかの束縛に従います。そして実用に関して大変有効であるPolynomial-timeなアルゴリズムを受け入れます。
- Genetic algorithmは、沢山のpopulationの状態が維持されるStochasticな丘登り(hill climbing)の探索です。MutationとPopulationから状態のペアを組み合わせるcrossoverによって新しい状態が生成されます。
- Non Deterministicな環境では、agentはContingent計画を生成するためにAND-OR探索を適用します。Contingent計画は、実行中にどのような結果が起ころうともゴールに達成します。
- 環境が部分的にobservableな時、そのBelief 状態はそのagentが入るかもしれない一連の可能な状態を示します。
- Standard探索アルゴリズムは、Sensor less問題を解くために、直接belief-state空間に適用されます。そして、belief-state AND-OR探索は、一般的な部分的なobservableな問題が解けます。Belief state内でState-by-Stateな解答を構築するIncrementalなアルゴリズムはしばしばもっと効果的です。
- Agentがその環境の状態とactionについて全く分からないとexploration問題が起きます。例えば、安全なexplorableな環境で、online探索のagentsは地図を作成し、もしゴールが存在するならば、ゴールを見つける事が出来きます。経験から導かれるHeuristicな推測を更新する事で、局所的な最小(local minima)から脱出するための効果的なメソッドを提供します。
それでは、解析していきます。
まず、observable, deterministic, discreteの定義が分かりません。
そう言えば、先週の3章でobservableとdeterministicについては調べました。
ただ、先週、3章を読んでいて、この定義よりきちんとした説明があったような気がします。
そう言えば、observableとdiscreteの一般的な意味は知っていますが、deterministicの意味は知りません。
Google先生によると
と説明されています。
人生は予め運命的な物で決まっていて、個人の意思や努力は人生の成功や失敗とは関係ないと言う考えの事みたいですね。うん。なるほど。
そう言えば、中学生の時、知らないおばちゃんから「君は、外国で長く生活するようになる。」と言われた事がありました。その時、私、英語の勉強が大っ嫌いだったので「何このおばちゃん！」と警戒して走って逃げたのを覚えています。Deterministicな考え方をするなら「やっぱり、私が外国で生活する運命は決まっていたのか…」と考えるのでしょうね。
よし感覚的には、理解したと思ったら、4章はそれ以上の場合を勉強するんですね。
では、最初のサマリーから読んでいきます。
hill climbingをまず調べます。
Hill Climbing - Georgia Tech - Machine Learningの説明が分かり易かったです。
要するに、ある点をランダムに選んでその点から非常に近い点を右と左から選びそれらの点の内で最も優れた点を選んでいくと言うアルゴリズムでした。元の点が最も優れてた場合はそこで終わりです。この方法では局所的な最高点は見つかりますが、その点が全体から見ても最も優れた点であるかどうかは分かりません。（つまりそれが局所的な探索(Local search)なんですね。）
何か昔勉強したNewton-Raphson methodの劣化版みたいな手段ですね。
次にComplete-state formulationsを調べます。
載っていない。Googleの検索に引っかからないとはどう事。専門用語じゃないの？
一応、教科書の220ページに以下の説明がありました。
＊いつもなら、教科書のスクリーンショットも一緒に挙げるのですが、この本、Kindleにコピーの機能があるにも関わらず、中の文章を全くコピーさせてくれません。著作権にうるさい人かも知れないので、この本のスクリーンショットは上げない事にします。
Complete-state formulation:
- 初期状態においてそれぞれの変数に値を割り当てます。
- そしてこの探索では、一回において一つの変数の値のみを変更します。
(p.220)より
とありました。ある種のアルゴリズムの様ですが。
これが本当ならGoogleの検索に引っかかっていいと思いますが、何で引っかからないでしょうね。とは言え、一応は言葉の意味は理解出来たので次に行きます。
Simulated annealingを調べてます。
この用語の意味の前にannealの意味が不明です。それから調べてます。
Google先生によるとannealの意味は以下の様です。
こんな技術初めて知りました。これはYouTube先生に実践している映像を見せてもらうしかありません。
Annealing Metalにありました。
ふーん。冷やした後で金属が柔らかくなるんですね。何か日本刀かなんかを作るときは、熱いうちに加工しているイメージがあったんですが、それとは違うみたいですね。
脱線しますが、日本の伝統的な製鉄技法にこのannealingが存在するのか調べたんですが、見つからなかったですね。
まあ。実際のannealingはもういいです。Simulated annealingを調べます。
simulated annealingの説明が分かり易かったです。
一応、アルゴリズムは理解したのですが、これっていつでも局所的でない全体の最大値を見つけられるのでしょうか？何か運もあるような気がします。
それはともかく、この人のチャンネルは分かり易いです。
AI、保存しときます。
Stochasticを調べます。
以下にGoogle先生の説明を示します。
この説明ではあまりピンと来ませんが、stochasticとdeterministicを対比させて説明しているサイトがありました。つまり結果は決まっていないと言う考え方みたいですね。と言っても、意思や努力で結果が変わると言う意味ではなく、deterministicはニュートン力学的な意味で結果が決まっているのに対して、stochasticは統計力学もしくは量子力学的な意味で結果はランダムになると言う意味みたいですね。
それを踏まえてこの説明をもう一度読むと言っている意味が分かりますね。例えば二重スリット実験における一個の電子についての説明と考えれば意味が通じます。一個の電子が何処に飛ぶのかは予測する事は出来ませんが、沢山の電子を飛ばしたら、どこにどれくらい到達するのかは確率的に説明出来ますからね。
そういう波動と粒子の両方の性質を持っていて分布を確率的にしか説明できない場合をstochasticと言うみたいです。
ここまで理解して、もう一度、最初のサマリーを読み直してみます。
- 丘登り(hill climbing)のような局所的な探索(Local search)のメソッドは、メモリーに少ない数のノードを保持する事のみで、Complete-state formulationsで作動します。
この部分は、分かりました。としかいいようがないですね。まあ、意味が分かるようになったので、O.K.としましょう。
- Simulated annealingを含む幾つかのStochasticなアルゴリズムが開発されました。Simulated annealingは、適切なcooling scheduleを与えられたときに、最適な解答を返します。
まず、Simulated annealingは温度による分子の励起のばらつきをアルゴリズムに使用しているので、当然Stochasticになります。これが忠実にボルツマン分布に乗っ取って計算しているのかどうかは分かりませんが。適切なcooling scheduleは温度の冷め方を言っているのでしょう。何が適切かが分からない以上、最適も糞もないと思いますが、結果的に局所的な最高点でなく、全体の最高点が得られれば、この場合は最適な解答というのでしょう。
このペースでは、とても3章は読めませんね。一週間で一章が限界みたいです。
次のサマリーを読みます。
- 沢山の局所的な探索(local search)は、continuous spacesな問題にも適用されます。Linear programming やconvex optimization問題は、State spaceの形状、とobjective 関数の性質などの幾つかの束縛に従います。そして実用に関して大変有効であるPolynomial-timeなアルゴリズムを受け入れます。
continuous spacesから調べますか。
これは単に連続した空間内と理解していいみたいですね。連続した空間では使用出来ない探索もいっぱいあるみたいですね。
Linear programming
このビデオの説明が分かり易かったです。コメントがオフになっているのが少し心配ですが、大体は合っているのでしょう。
convex optimization problem
まず、このビデオが分かり易かったです。
でもコメント欄にこんな事書かれていました。
まあでも、そこまで細かい事を知りたい訳ではないので、と思いつつももう少し調べました。
まず、Wikipediaですが、
おい。
簡単に書くと、間違っていると言われ、専門的に書くと難しすぎると言われ、一体何なんでしょうか？
convex optimization problemを理解出来ると何か変わるんでしょうか？
大金でもかかっているのでしょうか。
このビデオはもう少し詳しく説明されています。
それ以外だともう、Convex optimizationというスタンフォード大学の18回分の講義になりますね。
何で、スタンフォード大学はAIの講義のビデオは残さないでその中のたった一個の専門用語の講義は18回分もYouTubeに残しているのでしょうね。
Linear programmingとconvex optimization problemはこんなアルゴリズムもあります。くらいの理解で止めておきます。
State space
教科書の67ページに以下のような内容の説明が一寸だけありました。
初期状態から、アクションの連続によって到達できる全ての状態のセット。
(p.67)
でもそうすると、何でState spaceの形状と言っているんでしょうね。原文でも、
On the shape of the state space
といっていますし。WikipediaのState-space representationには、
と説明されていました。
となると単なるグラフの形状を言っているのかもしれませんね。そうすると後ろのobjective 関数の性質とも意味が繋がりますしね。
Polynomial-time
このサイトによると
と説明されていました。O(n^K)は流石に私でも覚えていましたが、これをPolynomial-timeと呼ぶ事はすっかり忘れていました。
これで、全部の用語は調べ終わりましたね。もう一度、2番目のサマリーを見てみましょう。
- 沢山の局所的な探索(local search)は、continuous spacesな問題にも適用されます。
まず、最初の一文は、特別オカシイ事はありませんね。今までdiscrete な環境で行っていた事を、4章では、それ以上の条件にも応用すると言っているのですから。Continuousな環境に沢山の局所的な探索(local search)を適用する事は4章の目的に合致しています。
- Linear programming やconvex optimization問題は、State spaceの形状、とobjective 関数の性質などの幾つかの束縛に従います。
Linear programming やconvex optimization問題とは、continuous spacesな問題にも適用出来る局所的な探索(local search)をするアルゴリズムの事を指しています。具体的なやり方については、ここでは勉強しません。それらのアルゴリズムを使用するためには、State spaceの形状、とobjective 関数の性質などのいくつかの制約があります。
ここまでは、一応意味が通る内容になりました。
この後が、分かりません。
- そして実用に関して大変有効であるPolynomial-timeなアルゴリズムを受け入れます。
そしては、Linear programming やconvex optimization問題を指しているはずです。これらはcontinuous spacesな問題にも適用出来る局所的な探索(local search)をするアルゴリズムの事を指していると結論づけました。
うーん。一寸おかしな表現ですね。
それの意味が、Linear programming やconvex optimization問題がO(n^K)と成りうると解釈します。
Linear programming やconvex optimization問題の実際のアルゴリズムは沢山あるようなので、その中の一部もしくは大部分がO(n^K)であるならば、そういう表現も可能かもしれません。
でも、O(n^K)で一番効率の悪いアルゴリズムなはずです。なんでそれを、実用に関して大変有効であると形容しているのでしょうか？
うーん。学生だったらここからクラスメートに聞きまくるんですが、今は出来ませんから。ここまでで取りあえず終了ですね。
では、3番目のサマリーを読んでいきます。
- Genetic algorithmは、沢山のpopulationの状態が維持されるStochasticな丘登り(hill climbing)の探索です。MutationとPopulationから状態のペアを組み合わせるcrossoverによって新しい状態が生成されます。
これ原文では、a genetic algorithmとなっていて、genetic algorithmの一例として、と言う意味で残りの文が続いていました。
となるとgenetic algorithmの定義があるはずなので、それから調べます。
思いっきり教科書に定義が書かれていました。
Genetic algorithmはStochastic beam searchの異形体です。
一つの状態を部分修正する事ではなく、二つの親状態を合体させることで後継の状態は作成されます。
自然淘汰と類似してるのはStochastic beam 探索と同じですが、無性生殖でなく有性生殖で取り組んでいる点が違います。
(p.126)
となると、
- Genetic algorithmの一例は、沢山のpopulationの状態が維持されるStochasticな丘登り(hill climbing)の探索です。MutationとPopulationから状態のペアを組み合わせるcrossoverによって新しい状態が生成されます。
が正しい訳になりますね。populationの状態とは何を指しているのかと思ったら、それもしっかり教科書に書かれていました。もっと理解したかったら教科書を読んでねと言う事ですね。
4番目のサマリーを読みます。
- Non Deterministicな環境では、agentはContingent計画を生成するためにAND-OR探索を適用します。Contingent計画は、実行中にどのような結果が起ころうともゴールに達成します。
これは、意味自体は分かりますね。具体的なAND-OR探索が何なのかは不明ですが。もう一つContingent計画とはどういうものかも不明ですね。
でもこんだけ分かれば十分ですので、次に行きます。
5番目のサマリーを読みます。
- 環境が部分的にobservableな時、そのBelief 状態はそのagentが入るかもしれない一連の可能な状態を示します。
これは、Belief 状態についての説明ですね。環境が部分的にobservableな時の意味は分かりますし、その後にBelief 状態についての説明がある事も分かりますが、そのagentが入るかもしれない一連の可能な状態とは、正直何をいっているのか分かりません。
教科書の4.4がまるまる説明しているみたいです。それを読めば理解できるのでしょう。
これで十分です。
次に行きます。
6番目のサマリーを読みます。
- Standard探索アルゴリズムは、Sensor less問題を解くために、直接belief-state空間に適用されます。そして、belief-state AND-OR探索は、一般的な部分的なobservableな問題が解けます。Belief state内でState-by-Stateな解答を構築するIncrementalなアルゴリズムはしばしばもっと効果的です。
Standard探索アルゴリズム
これ、探したけど見つからなかったです。ひょっとして単に標準的な探索アルゴリズムを指しているのかもしれません。
Sensor less問題
教科書に定義がありました。
Agentの知覚が全く情報を得る事が出来ない時の事
(p.138)
Agentがなんの情報もない状態を指すのですね。
belief-state空間
まず、教科書のbelief-stateの定義です。
現状において、Agentが入っている事が可能な物理的な状態であるとagentが信じている事を表している。
(p.138)
要するに、agentが今いる場所がどこなのか分からないので、取りあえず今いる場所がここであると言う事を信じていると言う事みたいです。
これだけ分かると、6番目のサマリーが言いたい意味は分かりますね。
ここには、３つのアルゴリズムが紹介されています。Standard探索アルゴリズム、belief-state AND-OR探索、そしてIncrementalなアルゴリズムです。
- Standard探索アルゴリズムは、直接belief-state空間を適用する事でSensor less問題を解く事が出来ます。（全部のSensor less問題が解けるのかそれとも一部のSensor less問題しか解けないのかは不明。）
- belief-state AND-OR探索は、一般的な部分的なobservableな問題が解けます。
- Incrementalなアルゴリズムはもっと効果的に解けます。
と言う事ですね。
最後のサマリーを読みます。
- Agentがその環境の状態とactionについて全く分からないとexploration問題が起きます。例えば、安全なexplorableな環境で、online探索のagentsは地図を作成し、もしゴールが存在するならば、ゴールを見つける事が出来きます。経験から導かれるHeuristicな推測を更新する事で、局所的な最小(local minima)から脱出するための効果的なメソッドを提供します。
exploration問題
良く分からない。周りの状況が不明な事をそう呼んでいるようにも見える。教科書にも説明は載っていなかった。
online探索
教科書に定義が載っていました。
最初にやって見る。次に環境を観察する。そして次の行動を決める。
(p. 147)
Heuristicな推測
Googleで調べた色々なサイトの説明を読んでいるうちに、何となく理解したのですが、まさしく今、私が行った方法をAIにやらせて正解を導かせる方法の事をHeuristicな推測という様です。
この3つの用語が理解出来たら、この文章の意味は大体は分かりました。
Agentがその環境の状態とactionについて全く分からないとexploration問題が起きます
まず、最初の文ですが、exploration問題が周りの状況が不明な事だと意味がオカシクなってしまいますね。でもexploration問題の定義が分からない以上これ以上解明は出来ませんね。
例えば、安全なexplorableな環境で、online探索のagentsは地図を作成し、もしゴールが存在するならば、ゴールを見つける事が出来きます。
Online探索のアルゴリズムについては分かったので、まあ、Online探索のアルゴリズムを正しく運用すればここに書かれている事が出来るでしょう。
経験から導かれるHeuristicな推測を更新する事で、局所的な最小(local minima)から脱出するための効果的なメソッドを提供します。
この文の意味は分からなかったです。経験から導かれるHeuristicな推測とは要するに、Heuristicな推測そのものです。局所的な最小(local minima)から脱出すると言うのは、局所的な最大値から脱すると同じ意味で、全体の中での最大値、もしくは最小値が得られる事を言い替えているだけです。
要するに、今までの方法は局所的な最高値を見つける事は出来ましたが、全体での最高値かどうかはわかりませんでした。それがこのHeuristicな推測をする事で全体での最高値が得られるようになったと言っているわけです。
2. Artificial Intelligence: A Modern Approach第4章の感想とまとめ
やっと終わりました。
3章なんてとても読めませんね。
1章が限界でした。
折角ここまで理解したので、やっぱり第4章は読む事にします。
＜Millington, Ian. AI for Games, Third Edition＞
もうどうやってもこの本の勉強する時間は今週は取れないので、この本の勉強は今週は中止します。
