3章＆4章

エージェントアプローチ
人工知能３章・４章
Ｍ０片渕聡
08/07/02
1
目次
 第３章：探索による問題解決
 第４章：知識による探索手法
2
第３章：探索による問題解決
目次




問題を解決するには
問題の定式化
探索戦略
まとめ
3
第３章：探索による問題解決
目次




問題を解決するには
問題の定式化
探索戦略
まとめ
4
問題を解決するためには
(問題解決エージェント)
１．ゴールの定式化
－現在の状況からゴールを設定
２．問題の定式化(本章で扱う)
－考慮すべき行為と状態を決定
３．探索
－可能な系列の中から有効な解を見つけ出す
5
問題解決エージェント
（例：夏季合宿当日）

ゴールの定式化
－「富士吉田駅に行く」

問題の定式化
－「新宿駅から出発」・「富士急行線を利用」etc

探索
－ルート検索
6
第３章：探索による問題解決
目次




問題を解決するには
問題の定式化
探索戦略
まとめ
7
問題のタイプ
 単一状態問題
単純
 多重状態問題
 偶発的問題
 探査問題
複雑
8
問題のタイプ
問題のタイプ
単一状態問題
（３章，４章）
多重状態問題
（３章，４章）
偶発的問題
（１３章）
探査問題
（２０章）
アクセス可能
行為の影響
がわかる
○
○
×
○
×
△
×
×
9
問題定義の基本的な要素
初期状態
－エージェントの初期状態
 オペレーター
－エージェントが利用可能な行為の集合
 ゴール検査
－ゴール状態
 経路コスト関数
－経路(行為列)に沿った各々のコストの総和

10
問題の定式化
例題：８パズル問題(単一状態問
題)

パネルをスライドさせて右図にする
スタート
ゴール
11
例題：８パズル問題
初期状態
－８つのパネル＋空白の位置を規定して決定
 オペレーター
－空白を{上、左、右、下}方向に動かす
 ゴール検査
－状態が前スライド右図のパネル配置に一致
 経路コスト関数
－空白を動かした回数

12
第３章：探索による問題解決
目次




問題を解決するには
問題の定式化
探索戦略
まとめ
13
探索戦略の評価基準
時間計算量
－探索に要する時間(展開するノード数)
 空間計算量
－探索に要するメモリ量(同時に必要なノード数)
 最適性
－見つけた解が最適(性能尺度が最大)かどうか
 完全性
－解の発見が保証されているかどうか

14
探索木における用語説明

例：幅優先探索
探索木
分枝度b(枝分かれの平均数)：2
解の深さd：1
ノード
深さ0
展開
最大深さm：2
深さ1
時間計算量：2
空間計算量：5
：展開済み
深さ2
：解(未展開)
：未展開
15
探索戦略






幅優先探索
均一コスト探索
深さ優先探索
深さ制限探索
反復深化探索
双方向探索
16
幅優先探索

最も浅いゴールを探索する手法
17
幅優先探索の性質




d
O
(
b
) (指数関数的に増大)
時間計算量：
空間計算量： O(b d ) (指数関数的に増大)
完全性を満たす
経路コストを考慮しない場合に限り最適性を満たす
規模の小さい問題しか解くことができない
18
均一コスト探索

最小コストの解を探索する手法
S
1
A
S
15
B
5
C
S
15
1
A
10
G
B
5
探索の見込みあり
15
1
C
A
10
G
B
最小コストの解
5
5
G
C
19
均一コスト探索の性質




d
O
(
b
) (指数関数的に増大)
時間計算量：
空間計算量： O(b d )
完全性を満たす
最適性を満たす
(指数関数的に増大)
幅優先探索の欠点の一つを解消
20
深さ優先探索

行き止まりになるまでノードを展開する探索手法
行き止まり
行き止まり
21
深さ優先探索の性質




m
O
(
b
)
時間計算量：
(指数関数的に増大)
空間計算量： bm
(大幅に減少)
完全性を満たさない (無限ループに陥る可能性あり)
最適性を満たさない (最適解でない可能性あり)
最大深さの大きい探索木に不向き
22
深さ制限探索

深さの限界を課した深さ優先探索
深さ限界 l=3の場合
Depth=3
深さの限界
23
深さ制限探索の性質




l
O
(
b
)
時間計算量：
(指数関数的に増大)
空間計算量： bl
(大幅に減少)
l≧dの時完全性を満たす
最適性を満たさない
計算量、最適性の向上
24
反復深化探索

可能な限りの深さ限界を試す深さ制限探索
l=0
l=1
l=2
25
反復深化探索の性質




d
O
(
b
)
時間計算量：
空間計算量： bd
完全性を満たす
最適性を満たす
(指数関数的に増大)
(大幅に減少)
探索空間が大きい時により好まれる
26
双方向探索

スタートとゴール双方から行う探索手法
27
双方向探索の性質




d /2
O
(
b
)
時間計算量：
空間計算量： O(b d / 2 )
完全性を満たす
最適性を満たす
(大幅に減少)
(大幅に減少)
現時点で理想的な探索
適用する際には注意が必要
28
双方向探索における注意点
次のような場合においては適用しにくい
 反転不可能なオペレータがある
－例：オペレータに「吸う」があって「吐く」がない場合
・ゴールからの探索が不可能

可能なゴールが複数ある場合
－例：チェスのチェックメイト
・可能ではあるが非常に扱いづらい
29
探索戦略の比較
時間
空間
完全性
最適性
O(b d )
O(b d )
○
○
均一コスト O(b d )
O(b d )
○
○
深さ優先
O(b m )
O (bm )
×
×
深さ制限
O(bl )
O(bl )
l≧d
×
反復深化
O(b d )
O(bd )
○
○
双方向
O(b d / 2 ) O(b d / 2 )
○
○
幅優先
b：分枝度 d：解の深さ m：探索木の最大深さ l：深さ限界
30
第３章：探索による問題解決
目次




問題を解決するには
問題の定式化
探索戦略
まとめ
31
まとめ

ゴールの定式化問題の定式化探索解決

初期状態、オペレータ、ゴール、経路コスト

時間計算量重視なら双方向探索

空間計算量重視なら反復深化探索
32
ここまで３章です

経路コストを考慮しなくても最適性をみたすのか

ここから４章
33
第４章：知識による探索手法
目次




最良優先探索
メモリ限定探索
反復改良アルゴリズム
まとめ
34
第４章：知識による探索手法
目次




最良優先探索
メモリ限定探索
反復改良アルゴリズム
まとめ
35
最良優先探索

次に展開するノードをある基準を元に決定
－最良とは限らない
評価関数(ヒューリスティック関数etc)


欲張り探索
A＊探索
36
ヒューリスティック関数

コストを見積もるために用いられる関数
(h(n)=ノードnからゴールまでの最短の道の道のりコスト)
－時間計算量は評価関数の質に依存
質の良い評価関数の作成が必要
本章ではこの知識に基づく探索戦略を紹介
37
ヒューリスティック関数

なんとなくの例
ヒューリスティック関数
横浜
直線距離
武蔵小杉
距離が短い方が
なんとなく
電車賃も
安いよね
あざみ野
溝の口
とりあえずこっちを選択
38
欲張り探索

ノードnからゴールまでの直線距離が最短のノードを展開
－h(n)= nからゴールまでの直線距離
ゴールまでの
直線距離
A:15
B:10
C:13
S
A
B
C
※直線距離≠直接的なコスト
S
A
B
C
39
欲張り探索の性質





m
O
(
b
)
時間計算量：
(指数関数的に増大)
空間計算量： O(b m ) (指数関数的に増大)
ヒューリスティック関数次第で計算量の減少が可能
完全性を満たさない
最適性を満たさない
40
A＊探索

欲張り探索+均一コスト探索
－f(n)=h(n)+g(n)
ゴールまでの
直線距離
f(n)=g(n)+h(n)
A:10+15=25
B:8+10=18
C:3+13=16
S
10
A B
3
8
C
S
A
B
A:15
B:10
C:13
C
41
A＊探索の性質





時間計算量：基本的には指数関数的に増大
空間計算量：基本的には指数関数的に増大
ヒューリスティック関数次第で指数的爆発は起きない
完全性を満たす
最適性を満たす
42
第４章：知識による探索手法
目次




最良優先探索
メモリ限定探索
反復改良アルゴリズム
まとめ
43
メモリ限定探索

探索の際には本質的にメモリの確保は必須
－今までの戦略の空間計算量はほとんど指数オーダ


反復深化A＊探索(IDA＊)
SMA＊探索
44
反復深化A＊探索

A＊探索＋反復深化探索
－深さ制限ではなくコストfの制限
f-limit=0
0
f-limit=2
f-limit=1
0
0
0
1
制限コストf-limitよりコストの少ない全てのノードを展開
3
45
SMA*探索

保持するノードを制限することでメモリを節約
－使用しないノードを一旦破棄
－必要に応じてノードを再生成
(詳細は省かせていただきます)
46
第４章：知識による探索手法
目次




最良優先探索
メモリ限定探索
反復改良アルゴリズム
まとめ
47
反復改良アルゴリズム

探索木の代わりに状態空間を用いた探索手法
－使用メモリ量をさらに節約
(現在の状態と次の状態)
現在の状態
評
価
値
状態
48
山登り法

常に評価値の高い状態(最良の手)に遷移
ゴール状態
現在の状態
評
価
値
状態
49
山登り法の欠点



局所的最大－最適解と勘違いしてしまう
高原－平坦なのでランダムに動くしかない
峰－峰のトップに着いてから傾斜がゆるくなる
峰
局所的最大
評
価
値
状態
高原
50
焼きなまし法

最良の手ではなくランダムに手を選択
－現在の評価値より高ければ採用
－高くなくても確率によっては採用
－確率は評価値の下がり具合で変動
局所的最大から脱出が可能
51
制約充足問題(CSP)

状態を変数、ゴールを制約の集合で表現可能
－制約に違反している行為列の探索を行わない
計算量を抑えることが可能

反復改良アルゴリズムの適用が可能
－規模の大きい問題を非常に高速に解決可能
52
第４章：知識による探索手法
目次




最良優先探索
メモリ限定探索
反復改良アルゴリズム
まとめ
53
まとめ

知識(ヒューリスティック関数)を用いた探索
－最良優先探索(欲張り探索・A*探索)
－メモリ限定探索(IDA*探索・SMA*探索)
－反復改良アルゴリズム(山登り・焼きなまし法)
54
質問

山登り法における「峰」の意味
55
SMA*探索(前提)

メモリが保持できるノードは３つまでと仮定
A
B
C
４つ以上同時に
保持できない
D
56
SMA*探索

ノードAを展開(横にある数字はfコスト)
A
12
15
13
B
C
57
SMA*探索

fコストの少ないCを展開、Bを破棄
A
13(15)
15
13
B
C
F
AのコストをCのコストに更新
また、AはBのコストも保持
58
SMA*探索

ゴールに着く前にノードを使い切ったら破棄
A
13(15)
13
C
F
18∞
Fのコストを∞に更新
59
SMA*探索

ゴールに着いても探索を終えない
A
13(15)
Cのコストを更新
1324
C
24
G
最適解でないかもしれない
60
SMA*探索

今度はノードBを展開(Aのコストを更新)
A
15
15
B
25∞
D
ゴールでないので∞に更新
61
SMA*探索

見込みがなくなったらゴールを決めて探索終了
1520
A
A・Bのコストを更新
1520
B
20
ゴールをEに決定
E
もちろんこの解が最適解とは限らない
62

Download Report