知能ロボティクス特論

自律型ロボット

第２講
諸岡
健一
Kyushu Univ. Intelligent Robots & Vision System
知能ロボティクス特論
ロボットはどのようにして自らの作業動作を決定するのか?
 行動の満たすべき条件: 合目的、環境適応

方法
1. 人間が教える: 産業用ロボットで実用化もっと楽に教えたい
2. ロボットが計画する：ただし、計画アルゴリズムは人間が作る
3. ロボットが学習する：教師付き・教師なし
4. 環境とロボットとのインタラクションの中で発現: センサ⼊⼒
に対する反射⾏動

動作生成法の評価
 人間の負担
 環境の変化・変動に対する頑健さ
 合目的性(最適性)
知能ロボットの行動
Kyushu Univ. Intelligent Robots & Vision System


使いやすいロボットを創りあげるために
自ら合目的行動を計画（計画知能）し、
環境の変化にも適応して、確実に目標を達成する（実行知能）。
計画知能
行動の決定要因＝目的 + 環境 + 行動主体の構造や機能
ロボット（多自由度行動系）の動作計画
（幾何モデルに基づくアプローチ）

ある物体が初期位置姿勢から目標位置姿勢まで動作可能な経路を
目標コンフィグレーション
計画する
?
Kyushu Univ. Intelligent Robots & Vision System

動作計画
目標位置姿勢
?
初期位置姿勢
?
初期コンフィグレーション
物体同士の衝突を避けながらどのように位置と姿勢を変えるか
移動ロボットの
コンフィギュレーション空間表現

移動ロボットの
コンフィギュレーション空間表現
コンフィギュレーション空間（C空間）
＝ある物体を構成する全ての点の位置を特定する
独立したパラメータの組
コンピュータ内部での手続き

目標コンフィグレーション
Kyushu Univ. Intelligent Robots & Vision System
Kyushu Univ. Intelligent Robots & Vision System
θ
(x,y,θ)
Yo
(x,y)
Xo
0
y
Y
θ
0g
x
Xg
X
(a) ２次元平面内の剛体ロボット
(b) 剛体ロボットのコンフィ
ギュレーション空間表現
(xi yi θi)
 状態の離散化：コンピュータは連続量を扱えない
 少し動かしては、衝突があるかないか調べる。
また目標状態になったかどうか調べる。
y
障害物
障害物の
コンフィギュレーション空間表現
Θ3
代表点
障害物
Xg
(a)実空間におけるロボットと障害物
0
X
(b)コンフィギュレーション
障害物
Kyushu Univ. Intelligent Robots & Vision System
Kyushu Univ. Intelligent Robots & Vision System
(xg yg θg)
Y Yg 0g
?
初期位置姿勢
移動ロボットの形態に応じて障害物を拡大する
ロボット
Y0
X0 θ ?
初期コンフィグレーション
コンフィギュレーション障害物

目標状態
初期状態
Θ
Yg 目標位置姿勢
?
0
Θ2
x
0
2次元平面内の障害物
Θ1
障害物のコンフィギュレーション
空間表現
コンフィギュレーション空間を使った
動作計画
人工知能が扱う問題：
→状態空間での探索という手続きで解決をはかる
 問題を状態空間で表現する。
 初期状態、目標状態
 状態を遷移させるオペレータ
：
中間状態
 状態間の遷移を繰り返して、目標にいたる道筋を求める。
→ グラフ探索に帰着

グラフ探索：系統的な探索
 無限ループに陥らないようにする。
（closedリスト: これまでに何を調べたか？）
 見落としが無いように系統的に探索する。
（openリスト：次に何を調べるか？）
（ポインタ：道筋の記憶）

各関節ごとに関節角度を離散量子化する。
（θ1 θ2 θ3 θ4 θ5 θ6） → （n1 n2 n3 n4 n5 n6）
Kyushu Univ. Intelligent Robots & Vision System
Kyushu Univ. Intelligent Robots & Vision System

ロボットのコンフィギュレーション空間
の離散量子化

例えば、各関節を128等分すると、その状態総数は
1286 ＝ 4.4 1012

衝突しているかどうかのチェック計算
状態 → 関節角度 → ロボットの各部の位置姿勢計算
→ ロボット各部と周囲物体との干渉チェック
仮に１点につき１マイクロ秒ですんだとしても
4.4 106秒＝ 51日
グラフ

Graph ＝節点(node) と枝(edge)
 有向グラフと無向グラフ
 ni と nj はそれらを結ぶ枝があれば隣接
 木(tree)は閉路のない連結グラフ
状態空間のグラフ表現
 問題の状態を節点
 初期状態を出発節点(start node)
 目標状態に対応する節点を目標節点(goal node)
 ２つの状態の一方から他方へオペレータを作用させて変換すること
ができれば、それに対応する節点を有向枝で結ぶ
 開節点（オープンノード）と閉節点（クローズドノード）

擬似コード
Procedure Search
1. 初期節点をリスト open に入れる
2. LOOP: if open = 空 then exit(fail)
Kyushu Univ. Intelligent Robots & Vision System
Kyushu Univ. Intelligent Robots & Vision System

探索アルゴリズム
3. n := first(open)
//リストの先頭にある節点を取り出す
4. if goal(n) then exit(n)
// 節点 n が目標点であるなら終了
5. remove(n, open)
// 節点 n をopenから削除
6. open の更新
7. go to LOOP
縦型探索（深さ優先探索）
縦型探索（深さ優先探索）

初期節点から離れた節点を優先的に調べる
Procedure Search
1. 初期節点を open に入れる
Kyushu Univ. Intelligent Robots & Vision System
3. n := first(open)
4. if goal(n) then exit(n)
5. remove(n, open)
6. open の更新
nを展開し、すべての子節点をopenの先頭に入れ、
子節点から n へのポインタをつける
7. go to LOOP
Kyushu Univ. Intelligent Robots & Vision System
2. LOOP: if open = 空 then exit(fail)
メモリ量小
計算量
縦型探索（深さ優先探索）

d(b-1)+1 d:探索深さ、b: 各ノードの分岐数
（平均分岐）
O(bd)
横型探索（幅優先探索）
Open list の変化
(S)

初期節点に近い節点を優先的に調べる最短経路（一番浅いところにあ
る目標点）が必ず見つかる
(A1 A2 A3 A4)
(A111 A112 A113 A114 A12 A13 A14 A2 A3 A4)
(A1111 A1112 A1113 A1114 A112 A113 A114 A12 A13 A14 A2 A3 A4)
(A1112 A1113 A1114 A112 A113 A114 A12 A13 A14 A2 A3 A4)
(A1113 A1114 A112 A113 A114 A12 A13 A14 A2 A3 A4)
(A1114 A112 A113 A114 A12 A13 A14 A2 A3 A4)
(A112 A113 A114 A12 A13 A14 A2 A3 A4)
(A1121 A11122 A1123 A1124 A113 A114 A12 A13 A14 A2 A3 A4)
………..
Kyushu Univ. Intelligent Robots & Vision System
Kyushu Univ. Intelligent Robots & Vision System
(A11 A12 A13 A14 A2 A3 A4)
メモリ量大
計算量
O(bd-1)
O(bd)
探索法
知識を用いない探索
1. 縦型探索：初期節点から離れた節点を優先的に調べる。
 メモリ量小 d(b-1)+1 d : 探索深さ、b : 各ノードの平均分岐数
 計算量
O(bd)
II.
2. 横型探索：初期節点に近い節点を優先的に調べる
 最短経路（一番浅い目標点）が必ず見つかる
 メモリ量大 O(bd-1)
 計算量
O(bd)
III.
3. 反復深化探索
 深さ探索の制限を徐々に増やし、目標状態の深さになるまで反復
 各反復では深さ優先探索の順序で調べ、各ノードを初めて調べる
順序は幅優先探索と同じ順序
 記憶量は縦型と同じ、計算量は縦型、横型とほぼ同じ
 縦型は探索空間が有限でないとき、初期節点に近い解でも
発見できないことがある
Kyushu Univ. Intelligent Robots & Vision System
Kyushu Univ. Intelligent Robots & Vision System
I.
探索法
Procedure Search
1. 初期節点を open に入れる g(S):=0
2. LOOP: if open = 空 then exit(fail)
3. n := first(open)
4. if goal(n) then exit(n)
5. remove(n, open) & add(n, closed)
6. open の更新
i. nを展開し、全ての子節点を生成する。ただし、子節点のうち、
closed の中にあるものは除く。
ii. 残りの子節点 ni に対して
を計算する。
iii. openに含まれていない節点はopenに入れる。既にopenに含まれ
ている節点は、今計算した
と、 openに入っている
を比較して、小さければopenに入れる。
iv. openに入れられた新しい節点の各々から n へのポインタをつけ、
とする。
v. open内の各節点を g の小さい順に並べる。
7. go to LOOP
知識を用いる探索
 各節点で目標までのコストが予想できる場合がある。
 探索の順序を決めるためなので相対的値が得られれば良い。
1. 最良優先探索
 目標状態に最も近いと思われる状態を優先して調べる。
 ヒューリスティックス関数値 h が最小となる節点を選ぶ
＝目標までのコスト（推定値）
 常に最適解が見つかる保証はないが、大部分の場合役に立つ知識
2. Ａ*アルゴリズム
 f （ノードの評価値）＝ g （スタートから当該ノードまでのコスト）
＋ h （当該ノードからゴールまでの推定コスト）
最適解の探索
Kyushu Univ. Intelligent Robots & Vision System
Kyushu Univ. Intelligent Robots & Vision System
最適解の探索
最適解の探索
グラフの各枝のコストがわかっているとき、全コストを最小にする
道を探す（ダイクストラ法など）。
→ 初期節点からのコストが最小の節点を最初に調べる。
Procedure Search
1. 初期節点を open に入れる g(S):=0
2. ：初期節点から節点
LOOP: if open = 空 then
exit(fail)
n までの最適な道のコスト
3. ：探索途中での最適な道のコスト
n := first(open)
木の探索では
4. if
then niexit(n)
：goal(n)
n を通って
に至る最適な道のコスト
5. remove(n, open) & add(n, closed)
6. open の更新
i. nを展開し、全ての子節点を生成する。ただし、子節点のうち、
closed の中にあるものは除く。
ii. 残りの子節点 ni に対して
を計算する。
iii. openに含まれていない節点はopenに入れる。既にopenに含まれ
ている節点は、今計算した
と、 openに入っている
を比較して、小さければopenに入れる。
iv. openに入れられた新しい節点の各々から n へのポインタをつけ、
とする。
v. open内の各節点を g の小さい順に並べる。
7. go to LOOP
A*アルゴリズム
Procedure Search
1. 初期節点を open に入れる f(S) := h(S)
2. LOOP: if open = 空 then exit(fail)
3. n := first(open)
4. if goal(n) then exit(n)
5. remove(n, open) & add(n, closed)
6. open の更新
i. nを展開し、全ての子節点を生成する。
ii. open あるいは closed の中に含まれていない子節点 ni に対して
と
を計算する。
iii. niをopenに入れる。
iv. open あるいは close の中に含まれている節点について、
と
を比較し、
の方が小さければopenに入れる。
v. openに新しく追加された各節点 ni から n へのポインタをつけ、
とする。
vi. open内の各節点を f の小さい順に並べる。
7. go to LOOP
≨∨≮≩∩ ≦∨≮≩∩
≞
≦∨≮∻≮≩∩
≞
≦∨≮≩∩
≞
≦∨≮∻≮≩∩
Procedure Search
1.
初期節点を
open に入れる
f(S) := h(S)
：節点
n から目的節点
G まで最短距離の推定値
2.
LOOP:
if
open
=
空
then
exit(fail)
：探索途中における、開始節点 S から n の最小コスト
3. n := first(open)
：探索途中における S - n - niの最小コスト
4. if goal(n) then exit(n)
： remove(n,
n を通って
ni に至る最適な道のコスト
5.
open)
& add(n, closed)
≧∨≮∩
≧≞∨≮∻≮≩∩
≞
≦∨≮∻≮≩∩
≨∨≮≩∩ ≦∨≮≩∩
≞
≦∨≮∻≮≩∩
A*アルゴリズム
Kyushu Univ. Intelligent Robots & Vision System
(2) A (4) B
2
(2) D
2 1
(4)
E
2
2
5
3
C (5)
5
B(6,S), C(7,S), A(8,S)
S(0)
C(7,S), E(8,B), A(8,S), D(9,B)
S(0) B(6,S)
E(7,C), A(8,S), D(9,B), F(13,C) S(0) B(6,S) C(7,S)
D(7,E), A(8,S), G(9,E), F(11,E)
S(0) B(6,S) C(7,S)
E(7,C)
A(8,S), G(8,D), F(11,E)
S(0) B(6,S) C(7,S)
E(7,C) D(7,E)
G(8,D), F(11,E)
S(0) B(6,S) C(7,S)
E(7,C) D(7,E) A(8,S)
F (6)
6
G
エッジ：コスト
節点の（＊）：推定値 h(n)
S – C – E- D – G
コスト＝８
Kyushu Univ. Intelligent Robots & Vision System
2
≞
≦∨≮≩∩

性質
 必ず最適解を見つける
 よりよいヒューリスティック関数 h をつかえば、展開する節点は
より少なくなる。

効率：展開する節点の数

オフラインアルゴリズム（縦型、横型、Ａ*など）
 目標までの動作の系列をあらかじめ決定してから実行する。
 問題空間の全体が既知である。（地図がつかえる）
Closed
S(0)
2
≞
≦∨≮∻≮≩∩
A*アルゴリズム
Open
S
6
≧≞∨≮∻≮≩∩ ∽ ≧∨≮∩ ∫ ≣∨≮∻≮≩∩
≞ ∽ ≧≞∨≮∻≮≩∩ ∫ ≨∨≮≩∩
≦∨≮∻≮≩∩
6. open の更新
i. nを展開し、全ての子節点を生成する。
ii. open あるいは closed の中に含まれていない子節点 ni に対して
と
を計算する。
iii. niをopenに入れる。
iv. open あるいは close の中に含まれている節点について、
と
を比較し、
の方が小さければopenに入れる。
v. openに新しく追加された各節点 ni から n へのポインタをつけ、
とする。
vi. open内の各節点を f の小さい順に並べる。
7. go to LOOP
Kyushu Univ. Intelligent Robots & Vision System
Kyushu Univ. Intelligent Robots & Vision System
A*アルゴリズム
展開する回数
しかし、環境が動的に変化している場合には、経路（動作系列）が
求められたときには環境が変化してしまい、使えなくなってしまう。
また，環境地図がなく，ロボットがその周囲の局所的範囲しか観測
できないが，移動に伴い観測範囲が拡大する場合に適用できる．
系統的探索ができないくらい
探索空間が大きい場合
ヒューリスティックによる動作計画
空間特性の違いによる分割探索

狭隘空間での空間の広がりの様子をしらべる
→ 可能性の高い方から先に探索

Kyushu Univ. Intelligent Robots & Vision System
Kyushu Univ. Intelligent Robots & Vision System

ポテンシャルに基づく方法
 ポテンシャル＝目標への引力＋周囲の障害物からの斥力（反発力）
 ポテンシャル場の勾配方向にロボットを移動
配置空間
ポテンシャル場
勾配法による探索
系統的探索ができないくらい
探索空間が大きい場合
Kyushu Univ. Intelligent Robots & Vision System

ポテンシャルに基づく方法
 停留問題：引力と反発力の釣り合った点で動けなくなる
 解決策→ 中間ゴール
ランダムな動作による脱出
 コンフィギュレーション空間で極小値のないポテンシャル
→無理
 三次元実空間でポテンシャル場を生成
→ コンフィギュレーション空間で局所的ポテンシャルを生成
極小値ではランダム動作による脱出
配置空間
ポテンシャル場
勾配法による探索
知能ロボティクス特論
第２講終了
諸岡
健一

Download Report