Design of Intelligent Robot

知能ロボット設計論
担当：平田健太郎
第7回（5/26）
１．グラフとネットワークにおける数理
・（続）最短経路問題とダイクストラ法
Design of Intelligent Robot
1
Schedule
4/14 １．グラフとネットワークにおける数理
・輸送問題とLP
4/21
・シンプレックス法（１）
4/28
・シンプレックス法（２）, 最大流/最小費用流問題
5/8
・双対問題
5/12
・多項式時間アルゴリズム, 内点法
5/19
5/26
6/2
・最短経路問題, ダイクストラ法 (1)
・ダイクストラ法 (2)
・組合せ最適化
Design of Intelligent Robot
2
 記号の準備
Design of Intelligent Robot
3
ダイクストラ法のalgorithm
Design of Intelligent Robot
4
Apply the Dijkstra method to
15
4
2
30
50
20
10
1
80
3
5
15
大規模な実行例：上智大管理工学講座
http://www.me.sophia.ac.jp/or/lab/ishizuka/OC/spath_01.html
Design of Intelligent Robot
5
15
4
2
30
50
20
1
3
80
5
10
15
15
4
2
30
50
20
1
80
Design of Intelligent Robot
5
10
3
15
6
15
4
2
30
50
20
1
3
80
5
10
15
15
4
2
30
50
20
1
80
Design of Intelligent Robot
5
10
3
15
7
Dijkstra法の計算量
50
S
2
20
1
80
2
50
S
20
1
80
50
2
S
20
1
80
15
4
10
3
15
15
4
10
3
15
15
4
10
3
15
Design of Intelligent Robot
Sの要素を一つずつ
増やす：n反復
30
5
30
5
高々n個のd（i）を比較
⇒ O（n2）
オーダー
（最高次のみ
係数は無視）
Sから外に出るエッジについて
d（i）の更新
高々m回の処理 ⇒ O（m）
※ ループ内の処理に見えるが…
エッジの本数は最大でもm＝n（n－1）／2
（n個のノードをすべて相互につなぐとき）
30
↓
5
m<n2より，全体はO（n2）
8
初期化
ノードv を探す
(n個の比較)
d(j) の付け替え
n回のループ
毎回処理するわけで
はない.
都合何回あるか？
終了判定
Design of Intelligent Robot
9
4
2
5
1
3
4
2
5
1
3
4
2
∴ d(j) の付け替えは各ノードに
入ってくる矢印の数だけ行われる.
（行われない場合もある.)
最大でも辺の総数だけ
5
1
3
4
2
5
1
3
Design of Intelligent Robot
10
(0,3
(1,3
(2,3
(3,3
(4,3
(5,3
(0,2
(1,2
(2,2
(3,2
(4,2
(5,2
(0,1
(1,1
(2,1
(3,1
(4,1
(5,1
(0,0
(1,0
(2,0
(3,0
(4,0
(5,0
Design of Intelligent Robot
11
ダイクストラ法に関する証明
Claim:
であることを帰納法により示す．
Design of Intelligent Robot
12
言い換えると, i が S に含まれるか否かによらず, d(i) には s から
S に含まれる節点のみを経由して i に至る最短路の長さが格納
されている. (i が S に含まれていないときには, i の直前の節点
までは S 内に留まる.)
i が S に含まれているときには, その d(i) が (どこを通るという
制約なしの）真の最短路の長さになっている.
Design of Intelligent Robot
13
Design of Intelligent Robot
14
S
v
S
d (v)
u d (u )
Claim:
Design of Intelligent Robot
15
S+
j
v
S
k
S+
d ( j)
Claim:
Design of Intelligent Robot
16
離散過程に対する多段階決定問題（ダイナミックプログラミング）

Design of Intelligent Robot
17
N段決定過程の最小和
N-1段決定過程
の最小和
Design of Intelligent Robot
18
 最適制御問題
状態方程式
終端条件の重み関数
Design of Intelligent Robot
状態，制御入力の重み関数
20
動的計画法に基づく最適条件の導出
最適コスト関数
積分区間を分割
最適性の原理から
Design of Intelligent Robot
21
Design of Intelligent Robot
22
最適であるための必要条件 (十分性もいえる)
Design of Intelligent Robot
23
一般に, 非線形偏微分方程式であるHJ方程式を
解析的に解くことは困難 ⇒ 線形システムに限定
Design of Intelligent Robot
24
平方完成
右辺を最小化する
Design of Intelligent Robot
25
-1 ×
T→∞ （定常解）⇒ 代数リカッチ方程式
Design of Intelligent Robot
26

Download Report