人工知能の探索アルゴリズム

認知システム論 探索(1)
先を読んで知的な行動を選択するエージェント
探索による問題解決
• 探索問題の定式化
• 探索問題の例
• 探索木とそのデータ構造
• 一般的探索アルゴリズム
探索問題とその解
状態1
B
状態5
B
初期状態
行為A
C
状態3
状態2
C
状態6
C
解=行為列 A C C
経路コスト=3
ゴール
探索問題の定式化
探索問題とは以下の4つの情報の集まりである
初期状態
オペレータ(行為)
ゴール検査(アルゴリズム)
経路コスト
オペレータ(状態遷移関数)
状態
x
オペレータ A
状態
y
y = A(x)
オペレータ B
状態
z
オペレータの集合のかわりに
後続関数 S でもよい
状態
x
状態
y
状態
z
S(x) = {y,z}
状態空間
初期状態から到達可能なすべての状態の集合
初期状態とオペレータの集合から定義される
無限集合であってもよい
A
初期状態
B
A
A
B
B
状態空間
B
A
B
ゴール検査
true, x がゴールのとき
GoalTest( x ) =
false, x がゴールでないとき
経路コスト
A
B
A
3
4
3
経路コスト関数
g
10=3+4+3
探索問題の定式化 (再掲)
探索問題とは以下の4つの情報の集まりである
初期状態
オペレータ
ゴール検査
経路コスト
状態空間
探索問題の例
おもちゃの問題 (toy problem)
8パズル
8クイーン問題
宣教師と人食い人種
現実世界の問題 (real-world
problem)
ルート発見
VLSIレイアウト
ロボットのナビゲーション
アセンブリの順序付け
8パズル
上
5
4
6
1
8
7
3
2
初期状態
5
4
6
1
7
3
5
右
8
2
4
6
1
8
7
3
2
オペレータ = {上, 下, 左, 右}
経路コスト = 各ステップ毎に 1
1
2
8
7
3
4
6
ゴール
5
8クイーン問題
互いにアタックしないように8個のQを置く
Q
Q
Q
Q
Q
Q
Q
Q
8クイーン問題の解
ゴール
(の1つ)
Q
Q
Q
Q
Q
Q
Q
Q
漸増的定式化
アタックされないように
Qを1つずつ置いていく
Q
1
Q
状態 [2] 4
2
1
Q
Q
状態 [2,4]
初期状態
[]
Q
3
4
Q
Q
Q
3
Q
状態 [2,4,1]
完全状態定式化
Q
Q
Q
Q
Q
Q
すべてのQを置き、
配置を修正してい
く
Q
Q
Q
Q
Q
初期状態
[1,4,1,2]
Q
ゴール
Q
Q
Q
Q
Q
Q
Q
Q
状態 [1,4,1,3] 状態 [2,4,1,3]
宣教師と人食い人種
西岸
ボート
2人乗り
東岸
宣教師と人食い人種の定式化
初期状態=[3, 3, 西]
ゴール=[0, 0, 東]
状態=[3, 2, 西]
西岸の宣教師の数 西岸の人食いの数 ボートの位置
宣教師と人食い人種のオペレータ
宣教師1人
人食い1人
宣教師2人
人食い2人
おのおの1人ずつ
をボートで渡す
ルート発見(ナビゲーション)
初期状態
O
Z
経路コスト
N
I
151
A
S
東
南
T
解
F
V
オペレータ
ゴール
R
L
P
H
B
M
D
C
G
U
E
探索アルゴリズム
探索問題
・初期状態
・オペレータ
・ゴール検査
・経路コスト
探索アルゴリズム
解
探索木 (search tree)
親ノード (parent node)
A
S
子ノード
(child node)
T
展開(expand)
子ノードの集合
Z
展開(expand)
A
F
O
O
Z
R
A
S
T
F
R
一般的探索アルゴリズム
(非形式的な記述)
一般的探索 (問題)
探索木を問題の初期状態を表す根ノードで初期化する.
loop
1.
2.
3.
4.
if(未展開のノードがない) return 失敗.
未展開のノードから親ノードを1つ選択する.
if(親ノードがゴール)
return 初期ノードから親ノードまでの経路.
親ノードを展開してすべての子ノードを生成し,探索木
に付加する.
探索アルゴリズムの基本アイディア
A
S
A
F
未展開のノードたち
T
O
S
Z
R
P
未展開のノードたち
から1つ選ぶ
展開(expand)
C
未展開のノードたち
未展開ノードはオープンリストに,
展開済みノードはクローズドリストに入れる.
A
S
必ず先頭から
先頭
取り除く
末尾
F
スタック
Last-In
First-Out
A
T
O
Z
戦略に基づいて
適切な位置に挿入
B
R
キュー
First-In
First-Out
一般的探索アルゴリズム
一般的探索 (初期状態,後続関数,ゴール検査)
OPENに初期状態を表す初期ノードだけを入れておく.
CLOSEDを空にしておく.
loop
1.
2.
3.
4.
5.
if(OPENが空) return null.
OPENの先頭ノードをNODEとし,CLOSEDに移す.
if(ゴール検査(NODE )) return NODE.
子ノード集合←後続関数( NODE ).
for each 子ノード in 子ノード集合 do
5-1. 子ノードとNODEを親子関係を表す辺で結ぶ.
5-2. 子ノードをOPENに挿入する.
ノードのデータ構造
Node
State state
F
Node parent
●
String operator
”南”
int depth
2
int pathCost
23
Node
A
Node
S
東
A
14
S
南 9
F
深さ 2
parentのdepth + 1
parentのpathCost
+operatorのコスト