知能ロボット設計論 担当：平田 健太郎 第6回 （5/19） １．グラフとネットワークにおける数理 ・ 最短経路問題とダイクストラ法 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 カーマーカー特許とソフトウェア ―数学は特許になるか 中公新書 今野 浩 (著) Karmarkar法: 対数障壁関数を用いたポテンシャル関 数の値で最適解からの誤差を測り, 射影変換 を用いて 探索方向を決定. 射影変換法 アフィン変換法 60年代に先行研究(ディキン(ロシア)) AT&Tの特許戦略: 制約領域の内部を通るものなら どんなものであれ特許侵害とみなす 主双対内点法 Design of Intelligent Robot 対抗ソフト OB1 (5万ドル) 登場 3 Design of Intelligent Robot 4 既に前章でも触れたスタンフォー ド大学グループの研究は、 α と D を適当に決めてやると、フィアッコ ＝マコーミックの障壁関数法が得 られることを示したものである。 Design of Intelligent Robot 5 バリア関数（ペナルティ）法 制約条件： バリア関数： − log(− f i ( x)) 制約領域 の境界 − f i (x) 制約領域の内側 Design of Intelligent Robot 6 バリア関数と（線形）評価関数を合成 バリア関数の値 合成した値 バリア関数の 等高線 Design of Intelligent Robot 7 バリア関数（ペナルティ）法 原問題 (制約つき） 制約なし問題 （等価） バリア関数 対数バリア関数（微分可能） 制約なし問題 （近似） 制約なし非線形最適化 Design of Intelligent Robot 8 非線形方程式の求解 f ( x) = 0 Newton法 Bisection法 (二分法） f (x) f (x) f ′( x1 ) x2 x1 x2 x1 xM = ( x1 + x2 ) / 2 x2 xM Design of Intelligent Robot 9 最短経路問題とダイクストラ法 Design of Intelligent Robot 10 最短経路問題 ライントレース ロボット（LEGO Mindstorms） start goal 最短時間でゴールできるルートを選んで走行せよ！ Design of Intelligent Robot 11 最短経路問題とダイクストラ法 節点1から5への最短経路を求めよ． 15 数字は枝の長さ 4 2 30 50 20 10 1 80 3 5 15 列挙せよ Design of Intelligent Robot 12 Extremely elephant approach 2 15 4 30 50 20 1 80 10 3 5 15 1. 7本の辺それぞれを通る/通らないとして，経路パターンを 27 生成 2. 1から出発して5に到達できるかチェック, 到達できるなら経路長を記録 3. すべての実行可能解のうち, 経路長が最小のものを出力 明らかに指数時間アルゴリズム Design of Intelligent Robot 13 Be a little bit wiser 50 1 80 2 4 20 10 3 30 5 15 容量制約を外し, 距離をコストとする最小費用流問題とすれば, 全流量がある経路（最短経路）に集中するはず (ソースとシンクのみ非零のbiを設定) ⇒線形計画問題として解く Design of Intelligent Robot 14 15 2 50 20 1 80 4 30 5 10 3 15 ソースとシンクのみ非零のbiを設定, 容量制約を外し, 距離をコストとする 最小費用流問題 Design of Intelligent Robot 15 2 50 15 20 1 80 4 30 5 10 3 Design of Intelligent Robot 15 実行可能基底解が退化 （0解が7-5より多い） ⇒注意が必要 16 頭の体操： 数値は格子点間の距離を表す．左方向，下方向以外には 進めないとき，スタートからゴールまでの最小ルートの長さを求めよ． 1 2 3 1 1 2 1 1 2 3 1 1 3 3 2 start 2 3 3 1 3 1 2 2 1 1 1 1 2 3 2 2 goal Design of Intelligent Robot 17 最適性の原理 s r t 節点s から t への最短経路が得られているとき，その経路上の任 意の節点 r から t (またはs)への最短経路は元の経路と一致する. Design of Intelligent Robot 18 最適性の原理 「最適政策は, 最初の状態および最初の決定が何であっても, 残り の決定列は最初の決定から生じた状態に関して最適政策を構成 するという性質をもつ」. Design of Intelligent Robot 19 記号の準備 Design of Intelligent Robot 20 ダイクストラ法のalgorithm Design of Intelligent Robot 21 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 22 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 23 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 24
© Copyright 2024 ExpyDoc
