edX ColumbiaXのAI（CSMM.101x） Week2のまとめですPythonコーディングの課題、なかなかの分量がありそうです。。。
日本語訳にあたっては、下記を参照しました。これもエージェントアプローチ人工知能 第2版をテキストとしており、購入したいところですが、いかんせん高すぎます。。。
知的エージェント
http://www2c.comm.eng.osaka-u.ac.jp/~babaguchi/aibook/agent.pdf
2.1 Intelligent Agents
最初にAgentの定義が述べられています。
An agent is anything that can be viewed as:
- perceiving its environment through sensors and
- acting upon that environment through actuators
「センサーを通し置かれた環境を知覚し、その結果に基づき行動をおこすものをエージェントとする」といったところでしょうか。
Environment (環境のタイプ)
Deterministic (vs. stochastic)
Episodic (vs. sequential)
Static (vs. dynamic)
Discrete (vs. continuous)
Single agent (vs. multi-agent)
Known (vs. Unknown)
エージェントのタイプ
Simle reflex agents (単純反射エージェント)
- select an action based on the current state only ignoring the percept history
- are simple but limited
- can only work if the environment is fully observable, that is the correct action is based on the current percept only
Model-based reflex agents (記憶をもつ反射エージェント)
- handle partial observability by keeping track of the part of the world it can't see now
- have internal state depending on the percept history (best guess)
- have model of the world based on (1) how the world evolves independently from the agent and (2) how the agent actions affects the world
Goal-based agents (ゴール主導エージェント)
- are knowing the current state of the environment is not enough. The agent needs some goal information.
- combine the goal information with the environment model to choose the actions that achieve that goal.
- consider the future with "What will happen if I do A ?"
- are flexible as knowledge supporting the decision is explicitly represented and can be modified.
Utility-based agents (効率主導エージェント)
- sometimes achieving the desired goal is not enough. We may look for quicker, safer, cheaper trip to reach a destination.
- agent happiness should be taken into consideration. We call it utility.
- a utility function is the agent's performance measure
- because of the uncertainty in the world, a utility agent choses the action that maximizes the expected utility.
2.2 Search Agents
サーチエージェントを用いることによって、現実世界での問題解決を行うことができるものがある。例：カーナビ
State spaceとsearch spaceの違い
State space: a physical configuration
Search space: an abstract configuration represented by a search tree or graph of possible solutions
探索木
- Root: initial state
- Branches: actions
- Nodes: results from actions. A node has: parent, children, depth, path cost, associated state in the state space.
探索空間は下記の三つに分類できる
1. Explored (a.k.a. Closed List, Visited Set) 探索済み
2. Frontier (a.k.a. Open List, the Fringe) 次に探索するもの
3. Unexplored: 未探索
Search strategies
* A strategy is defined by picking the order of node expansion
* Strategies are evaluated along the following dimensions:
- Completeness: Does it always find a solution if one exists ?
- Time complexity: Number of nodes generated / expanded
- Space complexity: Maximum number of nodes in memory
- Optimality: Does it always find a least-cost solution ?
* Time and space complexity are measured in terms of:
-
b: maximum branching factor of the search tree (actions per state)
-
d: depth of the solution
-
m: maximum depth of the state space (may be infinite ) (also noted sometimes
D).
2.3 Uninformed Search
1. Breadth-first search (BFS): Expand shallowest node
2. Depth-first search (DFS): Expand deepest node
3. Depth-limited search (DLS): Depth first with depth limit
4. Iterative-deepening search (IDS): DLS with increasing limit
5. Uniform-cost search (UCS): Expand least cost node
2.4 Uninformed Search Examples
BFS, DFS, UCSを用いて、どのように問題解決を行うのか、具体例とともに説明されている。
Week 2 Quiz: Uninformed Search
Uninformed Searchは知識なしの探索、知識を用いない探索と訳されるようです。
無知識探索だとニュアスンが異なるので、訳語として使用されていないんでしょうか。
AI agentの定義や、各探索アルゴリズムの特徴、探索アルゴリズムを用いた場合のグラフの読み解き等の設問がweek 2のQuizです。
DFS, BFS, UCSに関する設問は基本的特徴を答えるもので、難しくはありません。
与えられたグラフからポイントAからBに至るまでの道筋を、DFS, BFS, UCSを使用して回答する問題に関しては、実際に手を動かしながら回答するため、難しくはないものの手間がかかりました。
Week 2 Project: Search Algorithms
n-パズルゲームを解くコードをPythonで実装します。デットラインまで時間があるので、時間があるときにコーディングしてみます。
Week2: Discussion Questions
DQ1:
ダイクストラ法(DA)とUCSの違いについて説明されています。
なお、このアーティクルの筆者としてはUCSがほとんどの局面でDAより優れているので、DAを大学等で教えるのはもう止めては、と提言されています。
http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4017/4357
DQ2:
お掃除ロボットがどのように機能しているかを学ぶために、下記の記事が紹介されています。
http://electronics.howstuffworks.com/gadgets/home/robotic-vacuum.htm
Roomba Redにどのようなセンサーがあるのか、そのセンサーを通し環境をどのように知覚し、お掃除を行っているのかの説明がされています。
https://blog.niallconnaughton.com/2016/01/25/roomba-algorithms-and-visualization/
http://robotics.stackexchange.com/questions/628/what-algorithm-should-i-implement-to-program-a-room-cleaning-robot
こちらの二つの記事はお掃除ロボットが最適なパスを見つけるためのアルゴリズムについて議論がされています。牛耕式 boustrophedon（日本語の発音ブストロフェドン）って言葉、日本語／英語ともに初めて知りました。
