目次
1. Q 学習による未知環境下の経路探索 -多目的な問題への適用例-,
飯土井 修一, 五十嵐 治一, 田中 一基 (近畿大学) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2. Cooperative behavior based on a subjective map with shared information in a dynamic environment ,Noriaki Mitsunaga, Taku Izumi, and Minoru Asada (Osaka University) . . . . . . . . . . . . . .

7

3. 小型マルチロボットプラットフォームのための天井カメラを用いた疑似ローカルビジョンシステ
ム,
升谷 保博, 田中 志尚, 重田 智也, 宮崎 文夫 (大阪大学大学院) . . . . . . . . . . . . . . . . . . . . . 13

4. 2 台の非同期カメラによる仮想高速ビジョンシステムの実現 ,清水 彰一 [1], 西 貴行 [1], 藤吉 弘亘 [1], 長坂 保典 [1], 高橋 友一 [2] (1:中部大学, 2:名城大学) . . . 19

5. エンターテイメント向けサッカーログフォーマット 2goOZ 形式の検討,
鹿田 和之進, 西野 順二 (電気通信大学). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

6. 人間プレイヤのポジションカバー行動の発現 ,戸田 英治, 西野 順二, 鹿田 和之進, 本多 中二 (電気通信大学). . . . . . . . . . . . . . . . . . . . 29

7. A hiearchical multi-module learning system based on self-interpretation of instructions by coach ,Yasutake Takahashi, Koichi Hikita, and Minoru Asada (Osaka University). . . . . . . . . . . . 33

8. Reinforcement learning of parameters for humanoid rhythmic walking based on
visual information ,Masaki Ogino, Yutaka Katoh, Minoru Asada, and Koh Hosoda (Osaka University) . . . . . . . . 41
9. ロボカップ小型リーグにおける協調プレー実現の一手法について ,村上 和人, 日比野 晋也, 児玉 幸治, 加藤 恭佑, 鈴木 英之, 山本 浩司, 成瀬 正 (愛知県立大学) . . . 47

10. An architecture that unifies virtual and real environment ,Kentaro Oda, Takeshi Kato, Toshiyuki Ishimura, and Takeshi Ohashi (Kyushu Institute of Technology) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
11. An open robot simulation environment ,Toshiyuki Ishimura, Takeshi Kato, Kentaro Oda, and Takeshi Ohashi (Kyushu Institute of Technology) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
12. 並列シナリオ記述を用いた RoboCup-Rescue Civilian の動作記述 ,篠田 孝祐 [1,2] 野田 五十樹 [1,2,3] 國藤 進 [2] (1:サイバーアシスト研究センタ, 産業技術総合研究所, 2:北陸先端科学技術大学院大学, 3:さきがけ研究 21, 科学技術振興事業団) . . . . . . . . . . . . 61

13. ヒューマノイドロボットの動的起き上がり運動の理解と実現 ,大賀 淳一郎, 荻野 正樹, 細田 耕, 浅田 稔 (大阪大学大学院). . . . . . . . . . . . . . . . . . . . . 67

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑1 (5/2)

Ｑ学習による未知環境下の経路探索－多目的な問題への適用例－
Path search in an unknown environment by Q-learning- Application to a multi-purpose problem -飯土井修一，五十嵐治一*, 田中一基
Shuichi Iidoi, Harukazu Igarashi, Kazumoto Tanaka
近畿大学工学部（広島県東広島市）
School of Engineering, Kinki University* igarashi@ hiro.kindai.ac.jp

Abstract

2 Q 学習In this paper, Q-learning was applied to a cliff walking problem,
which is a typical example of path searching in an unknown
environment. In order to test whether Q-learning is effective to
multi-purpose problems, we added two constraints on safety
walking and the goal time to the original cliff walking problem.
Our experimental results shows that Q-learning can learn an
optimal path for the multiple purposes.

2.1 強化学習とは
本章では強化学習（Reinforcement Learning）の概要について，文献 [Sutton&Barto, 1998][新田,2001]に従って述べる．図 1 は強化学習の枠組みを示している．この図でエージェント（agent）は，ロボットのように自律的に行動する主体である．環境（environment）は，エージェントがおかれた周囲の状況である．エージェントのとりうる行動（action）の集合を A とし，観測の結果エージェント
が環境内でとりうる状態（state）の集合を S とする．

1 はじめに
自律移動型ロボットの経路探索問題に関しては，様々な方法が提案されてきた[藤村,1993][Kortenkamp et al,1998][Hwang&Ahuja,1992][Latombe,1991]．しかし，環境地図が得られない場合には，ポテンシャル法，スケルトン法，空間分割法といった伝統的手法は使えない．そこで，有力なアプローチの一つとして，強化学習のような学習手法を用いる方式がある．
強化学習の中においては，
方策価値関数 Q(s,a)の学習を行うＱ学習が有名である．実際，Ｑ学習を，未知環境下の経路探索問題の一種である「崖歩き問題」に適用した実験結果も報告されている[Sutton&Barto, 1998]．しかし，現実世界における経路探索問題は多目的多制約の探索問
題となるのが一般的である．
本論文では，この「崖歩き問題」に対して，なるべく短い時間でゴールへ到達したいという最短性の目的のほかに，崖からの距離を保つという安全性の制約と，ゴー
ルまでの到達時間に関する時間窓制約という２つの制約を持たせた．これは多目的多制約条件を有する未知環境
下での行動学習問題の一つと考えることができる．
この例題に対して，報酬関数の与え方を工夫し，Ｑ学
習の手法を用いるとどの程度の解を得ることができるか，
シミュレーションにより解析した結果を本稿で報告する．

エージェントにはテレビカメラやマイク，温度計などの「センサ」がついており，自分がおかれた環境を観測することができる．エージェントは時刻 t において，観測された環境内の状態 s t ∈ S に基づき，ルールベースを参照して，次にとるべき行動 a t ∈ A を選択する．適用できるルールが複数あるときには，何かの手段でルールを選択し，次に行う行動を決定する．選択された行動を実行した結果，環境におけるエージェントの状態が s t から

s t +1 に遷移する．
エージェントが当初の目標の状態を達成すると，環境から報酬（reward）
r を受ける．
これによりエージェントは，
エージェント

報酬
学習器
環

強化

境

センサ

ルール集合
行動の選択

参照

行動の実行

図１ 強化学習の枠組み

1Eπ { } は，エージェントが方策πに従うとしたときのπ期待値を表す．関数V を方策πに対する状態価値関数

自分がとった行動が適切だったことを知り，目標に達するために用いたルールの評価を高くする（ルールを強化する）．このようなルールの強化の結果，環境状態から次に選択すべき行動への写像が求まる．この写像を方策（policy）という．

（state-value function）と呼ぶ．
同様に，方策πの下で状態 s において行動 a を取ることの価値を Q

2.2 マルコフ決定過程

π(s, a ) で表し，状態 s で行動 a を取り，その後に方策πに従った期待報酬を次の式で定義する．

Qπ ( s, a ) ≡ Eπ {Rt | st = s, at = a}状態と報酬値の個数は有限であると仮定する．いま，
時刻 t における環境状態を s とし，エージェントが行動(4)

a t を選択し実行した結果，時刻 t + 1 において，状態は s ′に遷移し，エージェントは環境から報酬 r を受け取ると∞= Eπ  ∑ γ k rt + k +1 | st = s, at = a  k =0

する．これはエージェントの行動に対する環境の応答とQ π を方策πに対する行動価値関数（action-value

見なすことができる．

function），または Q 値と呼ぶ．

この場合， t + 1 における環境の応答が，t における状全ての状態 s∈S に対して，状態価値関数がV π (s ) ≥ V π ′ (s ) であるなら，方策π はπ ′ より優れてい態 s t と行動 a t のみに依存する場合には，次の確率

Psas′ ≡ Pr {s t +1 = s ′ | st = s, at = a}(5)るという．マルコフ決定過程では，他のどの方策よりも(1)

優れているか，またはそれに等しい方策が少なくとも 1を指定することで環境のダイナミクスを定義することがつ存在する．これを最適方策（optimal policy）という．

できる．また，報酬の期待値 Rss′ や方策π ( a; s ) も現在
a2.4 Q 学習における学習則の状態や行動だけに依存し，過去の履歴には依存しないaということを前提とする場合が多い．このとき，環境とQ 学習（Q-learning）は状態遷移確率 Pss′ と期待報酬

強化学習タスクをマルコフ決定過程（Markov decision

Rsas′ とが未知の場合に，環境の各状態 s ∈ S において，V (s ) を最大にするような最適方策を決めることを目的

process：MDP）と呼ぶ．

とする．Q 学習における学習アルゴリズムを以下に示す．

タスクもマルコフ性を持つと言い，マルコフ性を満たす

2.3 価値関数[Q 学習のアルゴリズム]

エージェントが受け取る報酬の総和を収益 Rt という．

1)すべての状態 s と行動 a に対して Q(s, a ) の値を 0

一般に，時間の経過とともに報酬を割引率（discountに初期化する．

rate）γ（ 0 ≤ γ < 1 ）で割引いて合計した次の値で定2)状態 s にあるとき，特定の戦略で行動 a を選択し，そ義される．

れを実行する．

3)環境から報酬 r (s, a ) を受け取る．

∞

Rt ≡ rt +1 + γ ⋅ rt + 2 + γ 2 ⋅ rt +3 + " = ∑ γ k rt + k +1 (2)4)遷移先の状態 s ′ を観測し，以下の式で Q(s, a ) の値

k =0を更新する．

エージェントが将来受け取ると期待される報酬は，エージェントがどのような行動を取るかに依存する．したQ(s, a ) ← (1 − α ) ⋅ Q( s, a) + α ⋅ (r ( s, a) + γ ⋅ max a′ Q( s ′, a ′)) (6)がって，エージェントが現在の状態にいることがどれだ

5) s ′ を s として， 2)へ．

け良いのかを表す価値関数は，特定の方策に依存する．
エ－ジェントが方策πをとるとき，時刻 t 以降の収益 Rt
の期待値V

π

α （ 0 < α ≤ 1 ）は学習率とよばれ，Q 値更新の強さを(s ) は，時刻 t で状態 s にあり，それ以降方制御するパラメータである．
Q 学習のアルゴリズムのステップ 2)においては，次の行動をランダムに選択することができる．しかし，Q 値が収束していない途中の段階でも多くの報酬が得られるよ
うにするため，次の行動選択戦略が提案されている:(i)ε-greedy 選択：εの確率でランダムに行動を選択し，そ策πに従ったときの期待値となる．すなわち，マルコフ決定過程におけるVπ(s ) の定義は次のようになる．

∞V π ( s ) ≡ Eπ {Rt | st = s} = Eπ  ∑ γ k rt + k +1 | st = s  (3) k =02

れ以外では Q 値が最大となる行動を選択する，(ii)ボル
ツマン選択：行動 a を exp(Q(s,a)/T)に比例して選択する．
T の値は時間が経つにつれて 0 に近づける．
次章では，Q 学習における行動選択として，ε-greedy 法を用いた．

a4
a2

a1

最短経路α

a3

3 崖歩き問題への適用についてS

3.1 崖歩き問題とは

崖

-100

G

例題として，図 2 に示すような 2 次元平面内をロボッ
ト（エージェント）が移動する“崖歩き問題”（Cliff

図２ 崖歩き問題

Walking Problem）を考える．ロボットは周囲の 4 方向に(0,11)

移動することができ（行動 a1 ~ a 4 ），ロボットが環境か(11,11)らぬけ出る方向に移動しようとする場合には，その状態にとどまるとする．このロボットの目的はスタート地点
からゴール地点へたどりつくことである．ただし，環境
内には「崖」が存在し，落ちてしまうとスタート地点に

Y

戻される．

a4

文献[Sutton&Barto, 1998]では，最短経路を学習すること

a2を目的として，エージェントは，(i)崖に落ちた場合のペa1a3

ナルティとして報酬値-100 を得る, (ii)1step 移動ごとにペナルティとして報酬値-1 を得る, (iii)ゴール到達時の報酬

S

は 0 とする, という報酬の与え方を採用し，行動の選択に

崖

-100

(0,0)

は，ε＝0.1 のε-greedy を用いて， Q 学習アルゴリズムを適用した．その結果，崖に沿って移動するという最短

A=4
G(11,0)

X
図３ 実験で用いた問題

経路（図 2 のα）を得ている．

3.2 報酬の設定

1

前節では最短経路を求めることを学習の目的としていた．しかし，現実世界における経路探索問題は多目的多制約の問題となるのが一般的である．本研究では，崖歩0き問題に対して，安全性の考慮やゴール到達時の時間窓

α

γ

β

δ

図４ 報酬関数で用いた台形状の関数

制約（ゴール到達時刻の範囲指定）を設定した．
エージェントの位置と，スタート地点からのステップ

トがゴール地点に到達したことに与えられる報酬値を表

数とを，エージェントの状態 s とする．ただし，Q 値は位している．また，式（7）の右辺のパラメータ c1 , c 2 , c3 は，置と行動の対の上で定義し，Q(s,a)と記す．状態 s に対する報酬を R (s ) として，R (s ) を以下のように定義する．

各項目の重要度を表現している．これらの値は，ユーザ

R(s ) ≡ c1 Rstep (s ) + c 2 Rdist (s ) + c3 R goal (s ) (7)

今回， Rstep (s ) と Rdist (s ) としては，図 4 のような台の要求に応じて設定する．

形状の関数を用いた．図 4 の横軸は， Rstep (s ) の場合は

ここで，Rstep (s ) はゴール地点到達時に得られる報酬で，[到達時刻 t end ， Rdist (s ) の場合は崖からの距離 A である．

]

到達時刻 t end が時間窓制約（ t end ∈ t A , t r ：下限 t A ，上なお， Rgoal (s ) は，以下のように定義する．

限 t r ）の満足している度合いに応じて与えられる．

1
Rgoal (s ) ≡ 0Rdist (s ) はエージェントの状態 s の安全性を表しており，崖からの距離に基づき計算する． Rgoal (s ) はエージェン

3

ifsがgoal地点

else

(8)

4 実験
4.1 実験条件
実験に用いたフィールドマップを図 3 に示す．フィールドの大きさは縦，横それぞれ12マスに設定した．
なお，
エージェントから崖までの距離 A は，状態 s における位置座標を ( x, y ) とすると， A ≡ y で定義する．したがって，図 3 のエージェントの状態 s におけるエージェントの崖までの距離は， A = 4 である．
行動の選択には，ε＝0.1 のε-greedy を用いた．行動
ステップは 1000 ステップを限界とし，そのステップ数内にエピソードの終端状態（ゴールに到達する，または崖図５ 実験１の結果に落ちる）に達しない場合に，そのエピソードは強制的に終了し，スタート地点に戻される．以下に示すような 3つの場合（実験１～実験３）を設定し，実験を行った．

4.2 実験１：最短性を目的とする従来法3.1 で述べた報酬を与える．また，Q 値の初期値はすべて 0 とし，割引率γ＝0.1，学習率α＝0.1 として，5000
回のエピソードを学習する実験を 5 回（Case1～Case5）
行った．1 エピソードの報酬値の結果を図 5 に示す．この
図では，5000回のエピソードを，50回毎の区間に区切り，各区間での平均値がグラフに描かれている．
実験の結果，5 回とも図２に示すような崖のふちに沿
図６ 実験２の結果って右方向に移動するような最短経路を最適経路として学習した．しかし，行動選択にε-greedy を利用している

Q 値の初期値はすべて 0 とし，上記の条件下で，割引ために，崖から落ちるような事態がときどき起こり，必率γ＝0.1，学習率α＝0.1 として，5000 回のエピソード

ずしも最適経路（報酬値-12）を毎回通ることはない．実を学習する実験を 10 回（Case1～Case10）行った．1 エピ

際，図５の Case1～Case 5 でも，報酬値は-12 とはなってソードの報酬値の結果を図 6 に示す．この図では，5000

おらず，-40 前後で推移している．

回のエピソードを，50 回毎の区間に区切り，各区間での平均値がグラフに描かれている．図 6 のグラフの推移は

4.3 実験２：時間窓制約

大きく次の 3 タイプ(1)-(3)に分けられる．

(7)の報酬関数において， c1 = 1, c 2 = 0, c3 = 0 として，時間窓制約のみを設定した．最短経路の行動ステッ（１）Type 1：Case 4 のように，初期の過渡期を経た
後，高い水準（～-8）で推移するタイプ（例：Case 2，
Case 4，Case 5，Case 7，Case9）．
Case4 では，1 エピソードの報酬値が，高い値（～-8）
で推移している．これは，Q 値から得られた最適経路が，崖から一定の距離を保っており，ε-greedy による行動選択を行っても崖から落ちるような事態が起こりにくいためと推測される．

プ数が 13 であることを考えて，関数 Rstep (s ) の各パラメ

ータ値はそれぞれ，α = 15, β = 20, γ = 25, δ = 30 とした．つまり，ゴール到達時刻 t end が，20～25 ステップであることが最も望ましく，最短経路( t end = 13 )は適切でないと要求していることになる．
したがって，実験 2 における報酬の与え方をまとめる

図７は学習後の Q(s, a ) を視覚的に表している．各格と以下のようになる：(i)崖に落ちた場合のペナルティとして報酬値-100 を与える，(ii)1step 移動ごとのペナル

子内に描かれている矢印は，各状態 s における 4 つのQ(s, a ) の値を矢印の長さで表現している．矢印の長さティはない，(iii)ゴール到達時の報酬は，行動ステップ数に応じて， Rstep (s ) のみで与えられる．

4

(7)において， c1 = 10, c 2 = 0.00001, c3 = 0.1 とおき，時間窓制約と安全性の制約とを設定した．c1 , c 2 , c3
それぞれの係数が大きく異なるのは，報酬の与えられる
頻度が大きく異なることを考慮したためである．つまり，
1 エピソード内において，それぞれの報酬が与えられる回数は，1step 毎に与えられる Rdist (s ) が，最大で 1000 回与えられるのに対して， R goal (s ) はたかだか 1 回，

Rstep (s ) においては R goal (s ) よりも制約が厳しいので，更に減少する．これらの発生頻度の違いを係数で調整し，学習における各報酬項の影響を平準化しようと上記のよ
うに c1 , c 2 , c3 を設定した．

時間窓制約である Rstep (s ) の各パラメータ値は，
実験 2と同様にした．また，安全性の制約である関数 Rdist (s ) の各パラメータ値は，α = 0, β = 5, γ = δ = 12 とした．

図７ 実験２の case4 で得られたＱ値と最適経路

つまり，これは崖から距離 A ≥ 5 が最も望ましいことをLength(s, ai ) は式（9）に従って正規化してある．
Length(s, ai ) =表している．

Q( s, ai ) − min Q( s, a j )
1
j
(9)
⋅
2 max Q( s, a j ) − min Q( s, a j )j

したがって，実験 3 における実験条件をまとめると以下のようになる：(i)崖に落ちた場合のペナルティとしてj

報酬値-100 を得る，(ii)1step 移動ごとの報酬値はRdist (s ) により与える，(iii)ゴール到達時の報酬はR goal (s ) とゴール時の行動ステップ数に応じて Rstep (s )ただし，すべての方向で Q ( s, ai ) = 0 となる場合は，値を定義できないので描画していない．また，図 7 の太い矢印は，学習の結果得られた最適方策（常に Q 値を maxとにより与える．

にする行動を選択）に従って，スタートからゴールまで

上記の条件下で，Q 値の初期値はすべて 0 とし，割引移動して得られた経路（最適経路）を表している．
（２）Type 1’ ：Case 1 のように，初期の過渡期を経た後，報酬値が低い水準（～-20）で推移するタイプ（例：Case 1，Case 3，Case 6，Case 10）．
Q 値から得られた最適経路は，4.2 で行った実験 1 と同様に，崖のふちを右方向に移動して行く経路である．しかし，ε-greedy による確率的な行動選択では崖から落ちるような事態がときどき起こっているため報酬値が低い
水準にとどまると考えられる．したがって， Type1’の解は，最短性という目的だけを満足した一種の局所解であると考えられる．
（３）Type 2：Case 8 のように，報酬値がほとんど変化しない（～-70）タイプ． Case8 では，1 エピソードの報酬値が，初期の低い水準のまま推移している．これは，Q 値が学習できていない（したがって，最適経路も学習できていない）ためである．この実験では行動ステップの上限を 1000 ステップとして，移動を打ち切っている．
そのため Case8 では，ゴールに到達し，報酬が得られるエピソードが極端に少なかったと推測される．

率γ＝0.1，学習率α＝0.1 として，5000 回のエピソードを学習する実験を 10 回（Case1～Case10）行った．1 エピ
ソードの報酬値の結果を図 8 に示す．この図では，5000
回のエピソードを，50 回毎の区間に区切り，各区間での平均値がグラフに描かれている．
図 8 でのグラフの推移からはわかりにくいが，大きく次の二つのタイプ(1),(2)に分けられる．
（１）Type 1：Case 8 のように，グラフの最大値が 0 を超えるタイプ（例：Case 6，Case 7，Case 8，Case 9）．
図 9 は，Case 8 の学習後の Q 値とそれから得られた最適経路を表している． Case 8 では，1 エピソードの報酬
値が，初期の過渡期を経た後，およそ-5～0 の間で推移しているが，次に述べる Type2 の Case 5 とは違い，最大値
が 0 を越えるエピソードも出現している．これは，安全性を確保した上に，時間窓制約の条件をも満たしたステ
ップ数の経路を経てゴールする回数が多かったためと考えられる．実際，図 9 から，安全性の条件 A ≥ 5 を満足しつつ，望ましいステップ数（20～25）の最適経路を Case
8 では学習できたことがわかる．

4.4 実験３：時間窓制約と安全性の制約

5

るが，崖のふちを歩く経路のため，常にマイナスの報酬(-100)を得るリスクを負う．
実験２では，経路の最短性に加え時間窓制約を考慮した報酬を与えた．その結果は，(i)Type1:時間窓制約を満足する経路を最適経路と学習する，(ii)Type1’：実験１と同じく最短経路を最適経路と学習する，(iii)Type2：
最適経路を全く学習できない，という３つの場合に分かれた．Type2 の場合が生ずるのは，ゴールに到達するエピ
ソードが殆ど無かったためである．
実験３では，経路の最短性，時間窓制約のほかに，さらに，安全性の制約を報酬関数に加えた．その結果，実験 2 での Type 1，Type 2 の 2 つだけが出現し，Type 1’のような局所解は出現しなかった．これは，実験 2 の条
件に安全性の制約を加えたことで，実験 2 の Type 1’ のような崖のふちを通る危険な経路は不適切であると学習したためだと考えられる．しかし，安全性の制約を考慮したために，
崖から遠く離れて，経路を学習できない Type
2 のケースが増えてしまう現象も見られた．

図８ 実験３の結果

6 おわりに“未知環境”の下で行う移動ロボットの多目的多制約な経路探索問題の例題として崖歩き問題を取り上げ，ユーザの要求を満足する経路をＱ学習により求めた．この際，報酬関数の与え方について，一つの方法を示した．
今回は，報酬関数の各項の重みパラメータ c1 , c 2 , c3 の値を試行錯誤的に決定したが，これらのパラメータ値を，適切に決定する方法が必要である．また，今回は崖歩き問題を例題として取り上げたが，本アプローチの他の行

図９ 実験３の case8 で得られた Q 値と最適経路

動決定問題への適用も，今後検討していく予定である．
（２）Type 2：Case 5 のように，グラフの最大値が 0 付
近のタイプ（例：Case 1，Case 2，Case 3，Case 4，Case
5，Case 10）．

参考文献[藤村,1993] 藤村希久雄：”行動ストラテジーとアルゴリ
ズム”，日本ロボット学会誌，Vol.11, No.8, pp.1124-1129,
1993.
[Kortenkamp et al, 1998] D.Kortenkamp, R.P.Bonasso, andR.Murphy(eds.): Aritificial Intelligence and Mobile Robots,
AAAI Press/The MIT Press, 1998.
[Hwang&Ahuja,1992] Y.K. Hwang and N.Ahuja: "Gross
Motion Planning -A Survey," ACM Computing Surveys,
Vol.24, No. 3, pp.219-292, 1992.
[Latombe,1991]J.Latombe, Robot Motion Planning, Kluwer
Academic Publishers, 1991.
[Sutton&Barto, 1998] Sutton, R.S, and Barto, A.G.: :Reinforcement Learning, MIT Press, 1998. (三上・皆川訳：
強化学習，森北出版，2000)[新田,2001] 新田克巳：人工知能概論，培風館，pp.144-148,
2001.

Case 5 では，1 エピソードの報酬値が，初期の過渡期を経た後， -5～0 の間で推移し，最大値が 0 でとどまっている．これは，実験 2 の Case 8 と同様で， Q 値が学習できていない（したがって，最適経路も学習できていない）ためである．実際，エージェントの行動範囲を調べてみると，殆ど崖から距離が 5 以上離れた領域にとどまり，ゴールに向かう行動の出現頻度が殆ど見られず，学習が失敗していることがわかった．

5

実験のまとめと考察

実験１では，経路の最短性だけを報酬としたために，崖のふちに沿って右方向に移動する最短経路を最適経路とする方策を発見した．しかし，この経路は最短ではあ6人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑2 (5/2)

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

Cooperative Behavior based on a Subjective Map with Shared
Information in a Dynamic Environment
Noriaki Mitsunaga∗† , Taku Izumi∗ , and Minoru Asada∗†∗Dept. of Adaptive Machine Systems, † HANDAI Frontier Research Center,
Graduate School of Engineering, Osaka University{mitchy, asada}@ams.eng.osaka-u.ac.jp izumi@er.ams.eng.osaka-u.ac.jp

Abstractshare the environment map. The errors of self-locations
are minimized so that shared observations conform togeometric constraints. To observe several robots at one
time, they used omnidirectional cameras rather thannormal cameras with limited view angles. However, incase of robots with the latter cameras, there will be many
situations that they will not be able to observe others.
Then it becomes difficult to use such methods.
Although the representation of self-location by probabilistic form and use of beliefs are proposed andcommonly used in order to handle the error of selflocalization, it is difficult to obtain the accurate model
to merge the maps by two or more robots and to maintain the shared map. Simple weighted average of information by robots may work when the errors are small.
However when one of the robots has a large error on its
self-localization it will affect the shared map used by allother robots. Designing weights or accuracy mesuarements to prevent such a case is difficult because there
are always errors that is unknown to the designer and inmany situations errors are not detectable by the robot itself. Then, we propose a subjective map based approachrather than shared map based one. A subjective map isfor a multiagent system to make decisions in a dynamic,
hostile environment. A typical situation can be found in
RoboCup legged league competition [1]. The subjective
map is maintained by each robot regardless of the objective consistency of representations among other agents.
Owing to its subjectivity, the method is not affected byother agent’s information which may include not negligible errors due to dynamic changes in the environment
caused by accidents. A potential field is defined on thesubjective map in terms of subtasks such as ball reachingand shooting, and is dynamically updated to make a decision to act. The methods is compared with no sharing
and conventional sharing methods, and the future issues
are given with discussion.

This paper proposes a subjective map for a
multiagent system to make decisions in a dynamic, hostile environment. A typical situation
can be found in RoboCup legged league competition [1]. The subjective map is a map of theenvironment that each agent maintains regardless of the objective consistency of the representation among agents. Owing to its subjectivity, the method is not affected by other agent’s
information which may include not negligible
errors due to dynamic changes in the environment caused by accidents such as falling downor being picked up and brought to other placesby the referee. A potential field is defined on
the subjective map in terms of subtasks such asball reaching and shooting, and is dynamically
updated to make a decision to act. The methods is compared with a conventional sharing
and no sharing methods, and the future issues
are given with discussion.

1

Introduction

In a multi robot system, it is expected that communications or information sharing between robots help aquiring the knowledge about thier environment. When multirobots communicate with each other, they seem to need arefference coordinate system to exchange their information about the environment. In case of mobile robots,
the world coordinate or the coordinate fixed to the environment are often used. To convert the observation
to the world coordinate, each robot localizes itself. Assuming that localization errors are small or neglectable,
information exchange between robots are proposed for
self-localization [2]. However, localization errors often
become too large to ignore.
Methods to localize itself and to acquire knowledge
about environment by shared information from otherrobots are proposed [3, 4]. They use geometric constraints between several robots which are commonly observed from each other, calculates their positions, and2

A subjective map generation

Let us assume that there are two robots (robot A androbot B) and one object (a ball) in an environment.
These robots have localized themselves and they are

7

x
x

objectrobotAx
contradiction
mean placeyyyrobotB

Figure 1: There are two robots watching at a ball.
(a) with assumption of no localization error

watching at the ball but they cannot observe each otherdue to their limited view angles (Figure 1). If we ignore
the localization errors and put information on a map,
there will be contradiction about the ball position asshown in Figure 2(a).
If we use the weighted average of the ball location x̂,σ x + A σA x,
Aσ + B σ

x

ˆQ
Ax
ˆ
Ax

B

=

A

xA ,

=

A

xball ,=

B(c) the subjective mapof robot A

xB + ( xball − xball ).

(d) the subjective
map of robot B

Figure 2: Constructed map with assumption of no localization error, with averaged locations, and subjective
map of robots A and B

and decisions by subjective maps in a robot soccer environment with four legged robots. Robots determine theiractions from potential field calculated from a shared map
or its own subjective one.

3

A potential field for decision making

We define a potential field which depends on a subjective
map of a robot. Each robot calculates the field fromthe map and decide its action according to the field.
A robot has four actions, move forward, turn left, turnright and shoot a ball. It takes such an action that climbs
the potential field if the ball is far and shoot it to the
opponent goal as it approaches close.
The potential field V (x, y) of robot i consists of threepotentials. One is VF which is the function of the position of a teammate j, i P j = (i xRj ,i yRj ). The secondis VO which is the function of the position of an opponent k, i Rk = (i xk ,i yk ). The last one is VB which isthe function of the ball position i Q = (i xQ ,i yQ ). All
the positions are derived from its subjective map. In thefollowing, we give example potentials based on the setup
shown in Figure 3.
Potentials by a teammate VF and opponent VO arecalculated by,

(3)
B

y
data correction

(1)

(2)
A

data correction

data correctionywhere A x, B x, A σ, B σ are the ball positions and theirdeviations estimated by robots A and B, respectively,
assuming Gaussian distributions. Then we have a map
shown in Figure 2(b). There is no contradiction in thismap. However, this is not the true ball position in
the world coordinate system. When robot A has correct estimation while robot B has incorrect one, robot
A’s estimation become worse because of the information sharing. Also there are cases the relative position to the robot itself is more important than the absolute position in the world coordinate system. Further, it becomes more complex when the robots can observe each other. If we can assume the simultaneous
observations from several robots are available then we
could use geometrical constraints and reduce errors [3,4]. In case of robots with limited view angle cameras
and they are moving, we cannot assume it.
Here, we propose that each robot constructs its subjective map and determines its action based on it. For
example, robot A believes its observation for the ball andcalculate position of robot B from the relative position
between the ball and robot B as,ˆAAxxdata correction

B A

x̂ =

(b) with averaged
locations(4)

Figures 2 (c) and (d) show the subjective maps of robots
A and B. With these subjective maps, although reduction of localization error is not achieved, robot A is
not affected by the localization error of robot B and
can use the information from robot B. The subjective
map method is expected to work for such a task andthe environment that the relative positions is important
rather than absolute ones, localization errors sometimes
become large, and geometrical constraints are hard touse. In the following experiments, we compare the action
decisions by shared map with average position method

VF (x, y) = −Xf (i P j ),(5)

j(j6=i)VO (x, y) = −Xk8f (i Rk ),

(6)

x
ball

y

opponent robot
robotBO
robotA

Figure 3: True object locations(a) VF of robot A(b) VO of robot A

ball positionball position(c) VB of robot
A, it is highest at
support position(d) VB of robot
B, it is highest on
the ball(e) final potentialof robot A(f) final potentialof robot B

where,³¡ y−ȳ ¢2 ´
2− 21 · ( x−x̄1σx ) +σyf (P (x̄, ȳ, σx , σy )) =e
. (7)2πσx σy
These potentialls are to avoid robots in the field. Figure 4 shows the VF and VO of robot A in the example
setup.
The potential from the ball is defined so that the robot
closer to the ball will reach ball while others will go to theposition where it can back up the shoot. The potentialfunction of robot i is switched depending on if i is theclosest to the ball or not,
½ i
f ( Q) (i is the closest to the ball ),VB (x, y) =(8)f (i Q0 ) (otherwise),0

where i Q is the position of the ball, and i Q¡ is the ¢support position. i Q0 is defined as, i Q0 = i Q + G /2,
where G is the position of target goal. The example potentials of robots A and B are shown in Figures 4 (c)and (d). Final potential fields are shown in Figures 4 (e)and (f).

4

The experiments

We used the field and the robots for RoboCup SONY
Legged Robot League 2002 (Figure 5) for the experimental setup. In the environment there are six landmark
poles and two goals that can be used for self-localization,and one ball. The task is to shoot the ball into the goal.
Due to the inadequate lightning condition, it was notpossible for robots to stably detect each other in their local vision system. Our self-localization program is basedon Carnegie Melon University’s CM-Pack’01 [5]. Its approach is a Kalman-filter based self location tracking
with multi hypothesis which start from different points
in the field. For the verification of the method, we put acolor marker on the back of each robot and an overheadcamera to measure the position of robots and the ballexternally.
In the experiments we used two robots A and B andcompared the decision of robot A to the deicision withcorrect positions from overhead camera for three methods,

Figure 4: Potential fields of robots.

With this condition we can see whether a method makes
a wrong decision in spite of information sharing. Robots
A and B localize themselves by local vision and large
errors were added to robot B depending on the experimental conditions. We compared the results with therate of the time when the decision of robot A matchedwith the decision with the overhead camera. Each trial
ended when two minutes elapsed or the ball is kicked
into the goal.
We show the experimental results with three initialconditions. Figure 6(a) shows the initial condition ofcase 1. Robot B localizes itself by local vision. In thiscase robot A cannot observe the ball but robot B observes it. Due to large errors on observation of a robot,
robot A uses the robot B’s position that robot B tells
even when it adopts a subjective map. Then, in thiscase, methods (b) and (c) have the same map which balland robot B’s positions are transfered from robot B.
Figures 6 (b) and (c) show the initial conditions ofcases 2 and 3. Both robots observe the ball. In thesecases, we experimented with two conditions, 1) robot B
localizes itself by local vision and 2) robot B localizes(a) robots do not share information.
(b) robot B sends information to robot A and robot A
uses the shared map made by taking average,(c) robot B sends information to robot A and robot A
uses its subjective map (proposed).

9

robotA

robotA

robotB ballrobotB:unknown
ball:unknown(a) robot(b) field(a) without
sharing

Figure 5: The robot and the field for the RoboCup 2002
SONY legged robot league.

target goaltarget goaltarget goal

information(b) subjective map

Figure 7: Robot A’s potential field and positions of objects in its map at the initiall condition in case 1. Without information sharing (left) and based on subjectivemap (right).

ballrobotA

robotA

robotBrobotA

robotBball(a) case 1

ball(b) case 2

robotB(c) case 3

Figure 6: The initail conditions of experiments.

itself but large errors are always added to its positionand direction.
Table 1 shows the rate of time that the robot A’s decision matched with the decision by the overhead camera.
We experimented ten trials for case 2 and 3 for each condition. We can see that with averaged shared map, when
the large errors are introduced, the rate is worse thanthe one without information sharing. However, with thesubjective map, in all conditions, the rate is better thanthe one without infomation sharing and the one withaveraged shared map. This indicates the validty of thesubjective map approach.
Figures 7 (a) and (b) show the potential field andthe positions of objects with its non-shared map andTable 1: The rate of time that the robot A’s decision
matched with the decision with overhead camera
rate of matched timeerror and methodmeanvariance
no share
0.48
0.02
normal averaged
0.64
0.01
subjective
0.69
0.01
no share
0.48
0.02
large
averaged
0.39
0.01
subjective
0.59
0.02

the subjective map in case 1. Without information
sharing, robot A did not know the location of the ball
(Figure 7(a)) and could not move to the support position. With subjective map, robot A showed the expectedmovements as shown in Figure 8.
In case 2, without information sharing, robots bumped
into each other because they did not know where theother robot was, but they were initially placed at nearlysame distance from the ball. With information sharing
under normal localization errors, they showed cooperative movements. Figure 9 shows such movements.
In case 3, the matched time rate of averaged map
showed small difference to no infomration sharing. Whileunder conditions that robot B had large localization errors, the result of averaged map and subjective map
showed a big diffrence. Figures 10 (a) and (b) show thepotential field of robot A and the positions of objects in
its averaged map and its subjective map at the initial
position. Due to the robot B’s large localization errors,
robot A also became to have large errors with the averaged map and made wrong decisions. However, as shownin Figure 10(b), with the subjective map, robot B’s error did not affect robot A and the rate increased withinformation sharing. Figure 12 shows the robots’ movements with subjective map. We can see that robot A
apropreately moved to the supporting position.

5

Discussions and Conclusions

We proposed to use a subjective map in a multi robot
system under dynamically changing environment. Our
experiments with a robot soccer task showed that evenunder large error situations, where a shared averaged
map method lost the merit of information sharing, theproposed subjective map works effectively. Further investigation for a larger scale of multi robot systems andcomparison with other information sharing methods are
our future work.

10Figure 8: A sequence of robots’ movements with subjective map in case 1.

Figure 9: A sequence of robots’ movemens using subjective map in case 2 under nomal localization error

robot Aball

robot A

ceedings of the 2002 IEEE/RSJ International Conferenceon Intelligent Robots and Systems, pages 447–453, 2002.

ball
robot Brobot B(a) averaged map(b) subjective map

Figure 10: Robot A’s potential field and positions ofobjects in its map at the initiall condition in case 3 withrobot B’s large errors. Based on the averaged map (left)
and the subjective map (right).

Acknowledgment[3] K. Kato, H. Ishiguro, and M. Barth. Identifying and localizing robots in a multi-robot system environment. In
Proceedings of the 1999 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 966–971,
1999.
[4] T. Nakamura, A. Ebina, M. Imai, T. Ogasawara, and
H. Ishiguro. Real-time estimating spatial configuration
between multiple robots by triangle and enumeration constraints. In Proceedings of the 2000 IEEE/RSJ International Conference on Intelligent Robots and Systems,
pages 2048–2054, 2000.
[5] William Uther, Scott Lenser, James Bruce, Martin Hock,and Manuela Veloso. CM-Pack’01: Fast legged robot
waking, robust localization, and team behaviors. In Andreas Birk, Silvia Coradeschi, and Satoshi Tadokoro, editors, RoboCup 2001: Robot Soccer World Cup V, pages
693–696. Springer, Lecture Note in Artificail Intelligence(2377), 2002.

We used the codes shared among the teams involevedin RoboCup SONY Legged robot league. We thankCarnegie Melon University for their self-localization
codes, the United Team of Kyushu for their motion andwalking codes, and the University of New South Walesfor their walking codes.
pReferences[1] Manuela Veloso, William Uther, Masahiro Fujita, Minoru
Asada, and Hiroaki Kitano. Playing soccer with legged
robots. In Proceedings of the 1998 IEEE/RSJ International Conference on Intelligent Robots and Systems, volume 1, pages 437–442, 1998.
[2] Ashley Stroupe and Tucker Balch. Collaborative probabilistic constraint-based landmark localization. In Pro-

11

Figure 11: A sequence of robots’ movements using averaged map in case 3 with large error on robot B.

Figure 12: A sequence of robots’ movements using subjective map in case 3 with large error on robot B.

12

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑3 (5/2)

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

小型マルチロボットプラットフォームのための
天井カメラを用いた疑似ローカルビジョンシステム
Pseudo-Local Vision System Using Ceiling Camera for Small Multi-Robot Platform升谷 保博
Yasuhiro Masutani

田中 志尚

重田 智也

Yukihisa Tanaka

宮崎 文夫

Tomoya Shigeta

Fumio Miyazaki

大阪大学大学院基礎工学研究科
Graduate School of Engineering Science, Osaka University
masutani@me.es.osaka-u.ac.jp

Abstract

Ethernet LAN

HUB

Main
Computer
Units

Pseudo-local vision system, which simulates
visual information derived from an on-board[mori@moa ~]$[mori@swift ~]$[mori@pigeon ~]$[mori@moa ~]$[mori@starling ~]$

Radio
Links

camera of mobile robot based on a ceiling camera image, is proposed. It consists of a vision server and a client module which communicate with each other in the SoccerServer-

Robot
Units

like protocol. An image processing module forthe on-board camera in the control program is
replaced with this system. The simulated visual information is not a two-dimensional im-

Figure 1: System of the Team OMNI in 2001 (real local
vision)age data but a one-dimensional array which
represents the nearest edge in each direction

HUBof essential information of the on-board camera image. This concept was implemented for

Main
ComputerUnits

our robot system for the RoboCup Small-Size
League. The server can transmit the edge data

[mori@moa ~]$[mori@swift ~]$[mori@pigeon ~]$Ethernet LAN[mori@moa ~]$[mori@starling ~]$

Radio
Links

to 10 clients 30 times per 1 second. The timelag between grabbing image on the server and

Robot
Units

extracting visual information on the client isabout 10ms.

はじめに

Ceiling Camera[mori@swift ~]$Vision Server

around the robot. However, it contains much

1

Soccer Field

Onboard Camera

Soccer Field

Figure 2: System of the Team OMNI in 2002 (pseudolocal vision)

視覚を有する複数のロボットの協調は大変興味深い研究
テーマであるが，RoboCup の中型リーグのように，ロボッに対して，我々は，ロボットに搭載したカメラ (ローカル

ルド外の PC に伝送し処理を行なっている (Figure 1 とFigure 3 左 [Sekimori, 2002b])．このため，混信などの映ビジョン) を用いるプラットフォームを開発し，RoboCup

像伝送の不具合に非常に弱く，RoboCup2001 においては小型リーグに参加してきた．しかし，CPU の処理能力等

研究成果を十分に発揮できなかった．

トが大きくなりがちで，広い実験環境が必要である．それのために，全てのシステムをロボット上に搭載することはそこで，天井カメラの映像を用いて，擬似的に搭載カ

容易ではない．そこで，搭載カメラの映像を電波でフィーメラから得られる情報を生成し，搭載カメラ用の画像処

13

blue
goal

yellowgoal

other robots
robot A
directionball

distance

Figure 3: Robots in 2001 (L) and 2002 (R)Figure 4: Concept of the nearest edge
理モジュールを置き換える「疑似ローカルビジョンシス

120テム」を開発した．これは，サーバクライアントシステ
100

ムであり，天井カメラの映像を取得したサーバが，ネットワークを介してそれぞれのロボットの制御を担当するクDistance [pixel]

80

ライアント群に情報を送る．我々は，このシステムの初期のバージョンを使って，実際に RoboCup2002 に参加した(Figure 2 と Figure 3 右[Masutani, 2003])．

6040

このようなシステムにおいて，天井カメラの情報から搭
20

載カメラの情報を生成するにはいくつかの方法が考えられる．しかし，2 次元データである画像を最大 10 台のク

0ライアントに 1 秒間に 30 枚送るというのは，ネットワー

0

60

120

180
Direction [deg]

240

300

360

クや PC に対してかなり負担が大きい．そこで，本論文
yellow goal etc.

では，各ロボットを中心とする各方向の最近接エッジのyellow robot

blue goal blue robot

情報をサーバがクライアントに送るという方法を提案すFigure 5: Pseudo local vision information

る．最近接エッジとは，ロボットを始点としてある方向に
床面上を辿った際に始めてぶつかるものとの交点であり，各方向のエッジデータをまとめて 1 次元の配列を成してに必要とされる機能に関して議論する．次に，第 3 節でいる．一例として，Figure 4 には，フィールド上の robot

システムの構成を説明し，第 4 節で開発したシステムのA の最近接エッジを示す．それを 1 次元データとして表現したものを Figure 5 に示す．本論文では，この 1 次元の評価する．最後に第 5 節で今後を展望について述べる．

2

必要な機能に関する検討

れは，本当の画像ではないが，搭載カメラの画像から得

2.1

要件

られる本質的な情報を多く含んでいる．例えば，物体の疑似ローカルビジョンシステムに求められる要件につい

隠れや重なりという現象を模擬できる．このシステムは，て考える．

エッジデータを「疑似ローカルビジョン情報」と呼ぶ．こ

RoboCup に限らず，自律分散型の移動ロボットの研究プ
ラットフォームとして有用である．
既報では，サーバとクライアントの間の通信量を減らす
ために，SoccerServer のプロトコルと同じように，サーバから極座標の位置情報を送って，クライアント側で最近接エッジの計算を行なっていた[田中, 2002a][田中, 2002b]．
その後，サーバ側で最近接エッジを計算しそれをクライアントに送る方法を試したところ，十分な性能が得られたので，本論文ではその方法を前提として，疑似ローカル
ビジョンシステムの提案をまとめる．
以下では，第 2 節で，疑似ローカルビジョンシステム

使いやすいプラットフォームとしては，以下のような項目が必要である．

• 搭載カメラから得られる情報を模擬できること．
• 搭載カメラ用のプログラムのコードをできるだけそのまま使えること．
• 天井カメラ以外に特別な追加のデバイスや装置を必要としないこと．
• 複数のロボットに，1 秒間に 30 回データを提供できること．
さらに，RoboCup の競技用の枠組みとしては，以下の14

3開発したシステム• 全てのチームが公平にデータを共有できること．

3.1

全体構成

• 最大 10 台のロボットに，1 秒間に 30 回，少ない伝達
遅れでデータを提供できること．

擬似ローカルビジョンシステムはサーバクライアントモ• わかりやすいプロトコルを利用すること．

制御プログラムの一部である「クライアントモジュール」

ような項目が必要である．

デルを使用しており，「ビジョンサーバ」と各ロボット用のから成る (Figure 6)．両者は，ネットワークを介して接続

2.2

視覚情報の模擬されている．1 つのサーバを同時に 2 つのチームが使うことを考慮して，最大 10 クライアントまで接続することを天井カメラから得られるのは床面の 2 次元的な情報なの想定している．

で，その像を直接変換して，床面上に存在する 3 次元的な物体の画像を作ることは不可能である．つまり，天井カメラで得られた位置情報と物体の 3 次元の幾何モデルか
ら，画像情報を再構築する必要がある．最近の高性能なビジョンサーバは天井カメラから得られる画像を処理し，各ロボットとボールの位置・姿勢を認識し，接続されている全てのクライアントに対応するロボットの近接エッジ配列を計算し 33ms 間隔でそれを送信する．

プロセッサを使えば，幾何モデルに基づいて，リアリティの高い CG 画像を高速に作ることができるかもしれない．
しかし，10 台分を 1 秒間に 30 枚となると，かなりの能力が要求される．

2.3

データの伝送クライアントモジュールは，サーバと通信し，送られてきたエッジデータを上位のルーチンで使えるように変換する．これは，搭載カメラ用のプログラムの画像処理モ
ジュールと置き換えられる．

3.2

プロトコル

きれば，画像の取り込みのハードウェアも含めたシステム

通信のプロトコルは，UDP/IP 上で SoccerServer[SoccerServer, -]に似たものを用いる．接続の初期化は，Soc-の検証が可能であり，我々のチームにとってはソフトウェ

cerSover と同じである．つまり，最初にクライアントからサーバが，CG 画像をアナログのビデオ信号として出力でアの置き換えを一切しなくてもよい．しかし，搭載カメラ

サーバへ (init) メッセージを送り，その後，サーバからのシステムを持っていないチームにとっては，余分なハー指定のポートへ視覚情報が送られる．サッカーサーバとドウェアが必要である．

異なるのは，クライアントの方からチーム色と背番号をサーバが，画像をデジタルのまま非圧縮で送る場合，8bit/pixel, 640 × 480，30frame/s を 10 台分とすると，703Mbps である．現在の標準的なイーサネットで送るには厳しい．ギガビットイーサネットや IEEE1394 を使えば解決するかもしれない．

指定することである．
視覚情報は，画像取得時刻，エッジ情報，ボール情報
よりなる．ボールを別にしているのは，他の物体に比べてボールが小さいからである．視覚情報のメッセージのフォーマットを以下に示す．

(see Time ((edge) EdgeSstring) ((ball)
2.4

提案する方法全方位カメラを搭載したロボットを使って RoboCup 小型

Distance Direction Size))
Time 画像をキャプチャした時刻．その日の深夜 0 時からリーグに出場してきた経験からすると，搭載カメラの情の経過秒数．後述するように，サーバとクライアン

報でもっとも重要なのはロボットの周囲の移動可能な床領

トで 1ms 以下の精度で時刻の同期を合わせることに域とその先にあるオブジェクトの種類であり，また，周囲よって伝達遅れの掌握が可能．

のオブジェクトの情報を獲得するにあたって，オブジェク
ト同士の重なりや隠れが大きな問題になる．そこで，我々

EdgeString 最近接エッジのデータを表す文字列．3 文字

は，2 次元の画像の代わりに，ロボットを中心とした各方
向の床面上の最近接なエッジという 1 次元の配列を擬似的で 1 方向をあらわす．1 文字目がエッジの種類．2〜
3 文字目が画面上での距離 (画素単位) を 16 進数で表な画像情報として使うことを提案する．この情報を「疑似したもの．エッジの種類のうちロボットの表現方法

ローカルビジョン情報」と呼ぶ．一例として，Figure 4 のについては 3 つの選択肢がある．

ようなフィールド配置における robot A の最近接エッジ情• 全てのロボットが同じ．
• チームの区別ができる．

報を太線で示す．また，これをロボットのローカル座標における角度に対する分布として変換したものを Figure 5• ロボット番号の区別までできる．

に示す．Figure 5 の上段は最近接エッジまでの画像上の距離，下段は最近接オブジェクトの種類を示している．

Distance ボールまでの画像上の距離 (画素単位)．

15SoccerServer-likeprotocolframe
grabbercolor extracting

coordinatetransformation

computingnearest edge

coordinatetransformation

computingnearest edge

Pseudo-local vision
informationclientmoduleclientlocalization
prediction
planning etc.

labeling
objectidentificationclientcameravision serverLAN

A: server side

B: network

C: clientside

Figure 6: Information flow in pseudo-local vision system
ここで，r はロボット中心からの床面上の距離，R は画像

Direction ボールまでの方向 (度単位)．
Size ボールの画像上で大きさ．周方向の幅 (度単位)．

中心からの画像上の距離，A, B, C は定数，int() は整数化の関数である．現在は，これらの設定は全て固定されているが，次のバージョンでは可変にする予定である．また，視覚情報の一例を以下に示す．

時々画像が取得できなかったり，画像が乱れたりという現(see 20306.148 ((edge) r59r5ar5av3e· · ·) ((ball) 61 121 3))

象を模擬することもできる．実際，自己位置推定の処理のロバスト性を検証するためにそのような処理を実装している．

サーバは天井カメラの画像が取得されるたびに，つまり，33ms 間隔で，これらのメッセージを全てのクライア
ントに送信する．メッセージを送信する順は毎回ランダムに決める．

3.3

以上の処理を最大 10 台のクライアントに対して行なう．
全てのクライアントの最近接エッジを計算した後に，ランダムな順番でクライアントに前節のプロトコルで情報を送る．

ビジョンサーバ

3.4

クライアントにおける処理

ビジョンサーバは天井カメラの映像に基づいて，ロボット

サーバから送られてくるエッジデータを用いて，搭載カに取り付けられたマーカで個体の識別を行い，位置と姿

メラ画像に基づく情報を置き換える．我々の搭載カメラ勢を算出し，さらにボールの位置を測定する．画像の取用のシステムではマルチスレッドライブラリを使ってプロり込みには安価なキャプチャーカードを使っている．色領域の抽出には，CMVision[Bruce, 2000]を改良したものをグラムを記述しており，その中で，最下位の画像処理 (画像のキャプチャ，色抽出，ラベリング，テンプレート画像

用いている．また，情報の質を向上するために，カルマンとの AND 処理) を 1 つのスレッドで受け持っている．そフィルタを使っている．

こで，そのスレッドを疑似ローカルビジョン用のものに置

その後の処理は，接続しているクライアント毎に別々に行なう．全ての物体の座標を着目しているロボットの座標き換える．他のスレッドは全く変更なしに使うことができている．

系に変換する．ロボット座標系において，原点を通る各方

我々の実装では，そのスレッドで，床領域の外周点の抽向の直線と物体の交点を求めて，最近接エッジを求める．

出の模擬，ボール領域と 2 つのゴール領域の重心計算の模ロボットとボールは円として表現する．次に，その距離を擬，床領域とテンプレート画像の AND 処理の模擬を行っ

画像上の距離に変換し，整数化する．

ている．それらの情報を使って，上位のスレッドでは，移現在の実装では，視野角は 360 度 (全方位視覚)，方向の量子化は 1 度刻み，床面の距離と画像上の距離の関係

動可能領域の検出，自己位置推定，ボール位置推定などを行っている[Sekimori, 2002a]．

は我々の使っている全方位カメラの双曲面ミラーに合わせ

3.5ている．その変換式は，以下のように表現される．

R = int(f −1 (r))
f (R) =R√
A − B C + R2

サーバとクライアント間の時刻の同期

動的な物体の画像を扱うには，画像を取得した時刻を正(1)確に知る必要がある．このシステムでは，画像を取得するビジョンサーバとそれを使うクライアントは別のマシ(2)ンであるので，2 つの間で時刻の同期を取る必要がある．

16

Real on-board camera image
Figure 7: Example of ceiling camera image
Linux のシステムクロックと NTP を使う方法では，この目的のためには不十分であることがわかった．そこで，
clockspeed[Bernstein, -]を参考にして，Pentium CPU の

RDTSC を使った時間計測と時間同期の方法を開発した．
ビジョンサーバは，時間サーバの役割もしている．クライ
アントは，接続前にビジョンサーバと時刻の同期を取る．
この方法によって，1ms 以下の精度で時刻が計測できるようになった．これを使って，システムの性能評価や伝達遅れを考慮した制御を行なう．

4

Made from pseudo-local vision information

評価

Figure 8: Examples of on-board camera image

我々はこのようなシステムを Linux 上に実装した．実験ではビジョンサーバは CPU が PentiumIV 2GHz の PC で，

BT878 を使ったビデオ取り込みボードを用いて天井カメているわけではない．

ラの画像を解像度 640×480 で処理している．このサーバに 10 台のクライアントを接続する．クライアントとなる

PC は様々で，1 台の PC 上で 2 つ以上のクライアントプ
ログラムが動作している場合もある．ここで評価データを取得したクライアントは，CPU が Pentium III 500MHzの PC 上で 1 つだけで動作している．サーバ PC とクライ

4.2

サーバでは画像の取り込みと処理を並行して行っており，
画像から 10 台のロボットと 1 つのボールの位置姿勢を算出して 10 台のクライアント毎にデータを変換して送り出す処理を 33ms の周期で繰り返すことができている．

アント PC は 100BaseTX のイーサネットで接続している．

4.1

処理例

処理周期，伝達遅れ

Figure 9 に 1 フレーム分の画像がメモリに格納されてから情報が抽出されるまでの所要時間を時間推移を示す．

ビジョンサーバが処理する天井カメラの画像の一例を Fig-

擬似ローカルビジョンの所要時間の内訳である A,B,C は

ure 7 に示す．これは，Figure 4 の配置に対応している．
この画像をもとに計算した robot A の最近接エッジデータ

Figure 6 に示した処理の流れに相当する部分を意味する．
多少ばらつきはあるものの，合計の所要時間は約 10ms でが Figure 5 である．さらに，これを全方位画像の座標系ある．撮像されてからの経過時間はさらにフレームキャプ

上に描いたのが Figure 8 の下である．このロボットには，

チャに必要な時間 33ms が加わる．

全方位カメラも搭載しており，その画像は Figure 8 の上

我々の 搭 載 カ メ ラ 用 の プ ロ グ ラ ム を Pentium IIIである．両者を比較すると，疑似ローカルビジョン情報で500MHz の PC 上実行した場合，カメラ画像を 320×240で取り込んでから情報が抽出されるまでの所要時間は約

は，最近接エッジより遠い物体は全て隠されている．しかし，それ以外は，実際の画像に含まれる多くの情報を表現できていることがわかる．なお，Figure 8 の下の画像

23ms であった．サーバに高速な PC を導入することで，10 台分の処理をさせても，我々の搭載カメラシステムよは，人間の理解を助けるものであって，実際の処理に使っりもむしろ少ない所要時間で処理が行われている．

17

参考文献

0.014
0.012

[Bernstein, -] D. J. Bernstein: clockspeed,
http://cr.yp.to/clockspeed.html

C: client sidetime lag [sec]0.01
B: network[Bruce, 2000] J. Bruce et al.: Fast and Inexpensive Color

0.008

Image Segmentation for Interactive Robots, Proceedings of the 2000 IEEE/RSJ Int. Conf. on In-

0.006
A: server side
0.004

telligent Robots and Systems(IROS2000), pp. 2061–
2066, 2000.

0.002
0

0

2

4

6

8

10

time [sec][Masutani, 2003] Y. Masutani et al.: Team OMNI in
2002 — Pseudo Local Vision Approach —, RoboCup
2002: Robot Soccer World Cup VI, Springer 2003.

Figure 9: Time delay in vision processing[Sekimori, 2002a] D. Sekimori et al: High-Speed Ob4.3

stacle Avoidance and Self-Localization for Mobile
Robots Based on Omni-Directional Imaging of Floor

解像度，ボールの隠れ解像度 640×480 である天井カメラを用いた場合，フィール

Region, Robocup 2001: Robot Soccer World Cup V,
pp. 204–213, Springer, 2002.

ド全域において分解能はほぼ一様で，1pixel は 6mm×6mmにあたる．一方，搭載カメラを用いた場合，我々のロボットの全方位画像では解像度 320×240 であり，最も解像度[Sekimori, 2002b] D. Sekimori et al.: The Team Description of the Team OMNI, Robocup 2001: Robot Soccer World Cup V, pp. 599–602, Springer, 2002.

が高くなったとき，1pixel は 4.4mm×4.4mm にあたり，ロボットからの距離が 220mm となったとき天井カメラと分解能がほぼ一致し，それよりも遠くなると搭載カメラの[SoccerServer, -] SoccerServer web site

分解能が劣る．このデータは一例であり，カメラの解像度や視野角によって天井カメラの分解能がより不足する場合も考えられる．さらに，天井カメラを用いた場合，ロボット近傍のボールがロボットの影に隠れることで見えhttp://sserver.sourceforge.net/[田中, 2002a] 田中 志尚 他: ロボカップ小型リーグの天井
カメラ画像を用いた疑似ローカルビジョンシステムの開発, 日本機械学会ロボティクスメカトロニクス講演

なくなる場合があり，現時点では，近傍はむしろ見やすい会’02 (ROBOMEC’02) 講演論文集, 1P1-C08, 2002.

という搭載カメラの特性を完全には摸擬できてはいない．
この問題を解消するために，複数の天井カメラを用いる[田中, 2002b] 田中 志尚 他: ロボカップ小型リーグ用のことが今後の課題である．

疑似ローカルビジョンシステムの評価，第 3 回計測

5(SI2002) 論文集, Vol. II, pp. 183–184, 2002.

自動制御学会システムインテグレーション部門講演会

おわりに

本論文では，マルチロボットプラットフォームのために，
天井カメラの情報を用いて搭載カメラの情報を疑似的に生成する簡便な方法を提案した．模擬される搭載カメラの情報は簡単なものであるが，隠れや重なりなど，移動ロ
ボットの搭載カメラ画像における本質的な問題をいくつも表現している．できあがったシステムを評価したとこ
ろ，処理の周期や伝達遅れは十分に小さく，十分実用になることがわかった．また，我々は，提案したシステムの初期のバージョンで RoboCup2002 に参加した．
近いうちにサーバのソースコードを公開するつもりである．また，この枠組みを使って，「疑似ローカルビジョンリーグ」を実現したいと考えている．これは，RoboCup
におけるシミュレーションリーグと実機リーグの橋渡しにもなるはずである．

18

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑4 (5/2)

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence¾ 台の非同期カメラによる仮想高速ビジョンシステムの実現        
清水彰一 Ý 

西 貴行 Ý

藤吉弘亘 Ý

長坂保典 Ý

高橋友一 ÝÝ

               
Ý 中部大学ÝÝ 名城大学  ! " !
 



 



のカメラを用いたダブルバッファリングによる高速処理を行うものである．この場合，カメラと専用のフレームグラ

                           

 



バが高価であるという問題がある．



本報告では，通常のカメラ ,   

より，ビジュアルフィードバックのサイクルを高速化する                   

 !                

ことを目的とする．このとき，複数のカメラを効果的に  

配置することで，オクルージョン領域の減少，画像の高                

解像度化等に対して大きな効果がある．このような複数

 





          

カメラ群のシステムの取り組みとして分散協調視覚プロ
ジェクトが挙げられる$松山 "--.(．中でも分散協調型対象追跡システムでは，多数の自律したエージェント間のコ    

# を複数用いることにミュニケーションにより対象の追跡を実現している$中澤  

'"(．しかし ，これらの多くは処理サイクルの高速化に

 はじめについてはまだ検討されていない．

ロボットが行動するためには，視覚センサによる環境認

ローチとして，通常の非同期カメラ , 

識・理解技術による情報を基に行動プランニングを行いロ

仮想高速ビジョンシステムについて提案する．' 台のカメ

ボットを制御するビジュアルフィードバック機構が必要でラは，" 台の  に接続されており，それぞれある．ロボットを迅速かつ正確に制御するためには，この理される．それぞれのカメラの処理結果を統合することビジュアルフィードバックのサイクルを高速に行う必要がで擬似的に我々は，分散協調型ロボットビジョンシステムの一アプ#' 台を用いた

で処以上の結果を得ることが可能となる．

あり，特に，カメラから得られる画像から有用な情報を得

本報告では，' 台の非同期カメラによる高速ビジョンシるための高速なビジョンシステムが不可欠となる．そのステムを提案し，物体の運動を予測する実験により，対象際には，ロボット等の対象とする物体の位置をより正確

物の位置を高速カメラと同等のスピード で得ることができ，その位置の精度は " 台のビジョンシステムよりも良に検出する必要がある．

いことを述べる．

これまでにビジョンシステムの高速化として，"# 画像
処理のハード ウェア化による手法$%&  '(，'# 高速な画像処理アルゴ リズムの提案$) '(， #台の非同期カメラによるビジョンシス
テムの高速カメラを用いる手法$*+% '' 加藤 ' ( が提案されている．"#，'# の手法は，カラー解析や領域検出

高速なビジュアルフィードバック機構を必要とするタスク

等の画像処理アルゴ リズムをハード ウェア化や最適化すとして，/  小型リーグにおけるグローバルビジョ

ることによる処理の高速化である．これらは，ビジュアルンシステムが挙げられる$/   ' (．グローバルビ

フィードバックにおけるビジョン処理にかかる時間を短か

ジョンシステムは，サッカーフィールド 上の設置されたカ

くするものであり， メラ映像からロボットの位置，姿勢，* とボールの位置をのカメラを用いた場合それ以上のサイクルの高速化は期待できない． # の手法は，

抽出し行動を決定するものである．本研究では，/ 

19

[外部パラメータ]
平行移動ベクトル T
回転ベクトル R[内部パラメータ]
焦点距離 f
画像座標の中心 O(uc,vc)
レンズ歪み係数 k1,k2
画像座標の縦横比 Sprocess1
process2
c

c

0

1

UDP

v

Cx

u

z y

(xv, yv, zv)
X

p
O

f
I

Y

T

process3zW

ObjectP(obj)xWO

yW

  "0 ビジョンシステムの概略 

0 視線交差によるフィールド 上の位置推定

本システムでは，1  の手法で求めたカメラの内部・外部パラメータから， 次元空間の光線情報に基づく位置推定を行う．  に示すようなカメラ中心とカメラ画像
上の座標を通る世界座標空間における直線を求め，その直(a) c0からの映像(b) c1からの映像  '0 ' 台のカメラ画像

小型リーグのグローバルビジョンシステムにおけるボールの運動復元を対象とする．
 と  を用いたビジョンシステ

' 台の非同期カメラ 

線がフィールドの面に交差する点を対象物の位置として計算する．これにより，カメラ画像の座標 ,  # に対応した
フィールド 上の世界座標 ,   # を求めることが可能である．このとき我々のシステムでは，世界座標 ,     #とカメラ座標 , # の関係は次式で表される．

列の回転行列， は平行移動ベクトル ,  

 


 
3

ムの概略を   " に示す．各々のカメラは，両ゴ ールの上部高さ '.$( にサッカーフィールド 全体が視野






,




に入るように固定されている．サッカーフィールド の大きさは，縦横約 ' ×$( である．カメラから,"#

 % 画面平面    上の点 ,   # を次式から求める．,   # は画像座標の中心である．

域を検出し ，その中心に対応するフィールド 上の位置を 3 

求める．

#$%

#

める手法を示す．

る．  ' に各々のカメラ画像を示す．本ビジョンシス
テムの処理は，各カメラ画像内のオレンジ色のボール領は 行# である．

以下に画像座標 ,  # より，世界座標 ,     # を求の映像信号は，" 台の  にインストールされた ' 枚のフレームグラバに入力され ，それぞれの画像が取り込まれ



 

 3 

,'#

 # レンズ歪みを修正した点 ,   # を次式から求め

位置推定

ロボットを制御するシステムにおいて，その制御領域はる． は画像中心からの距離であり， は画像座標の縦横次元である．画像処理の結果から得られたデータは ' 次比，   はレンズ歪み係数である．

元であり，その ' 次元情報からロボット等の， 次元情報を求める必要がある．これにより，行動計画を 次元で考えることができるため，制御システムを実空間に合わせて容易に作成することができる．
/ 

小型リーグでは，ロボットやボール位置を推定する手法に，カメラパラメータを用いる手法や，ホモグラフィを用いる手法$/ '"(が提案されている．カ3 ," 4   4   #3

 ," 4   4   #, # &   において，カメラ座標の原点から画像上の任意点  を通過する視線ベクトル ,     # は次式となる． はカメラ座標における焦点距離とする．







3

メラパラメータを用いる手法では，ピンホールカメラに基づく幾何学キャリブレーションを必要とする．単一のカ

メラに関する内部・外部パラメータを推定する手法として
1  のキャリブレーション手法$1   "-.2(が多く用いら ' 視線ベクトルを

れている．

20




   


,5#



次元空間上の直線式で表すと，

次式となる．

2000








 3   
 4

,6#

 ( ここでフィールド 面が    平面に平行であり，

 3  であると仮定すると，直線が平面と交わるときの を決定できる．

e0(obj)1500

5p0(obj)p1(obj)

1000

4.5

500


3


4

,#

e1(obj)3.5 )  の値を式 ,6# に代入することで，画像座標点 , #

0
0

500

1000

に対応した世界座標点 ,    # を求めることができる．
 3

   4  

3

本手法では，7 6 における

 4




#$#

1500

2000

2500

3000

World X coordinate [mm]  50 ボールの移動軌跡と位置推定誤差,2# の値として，ロボット

uImage coordinate

World coordinatev

やボールの高さを与えることにより，高さの異なる各対象
物体の

5.5

Estimation error of obj’s positioni e [mm]World Y coordinate [mm]

6(ui,vi-1)次元位置を正確に求めることができる．

zw(ui-1,vi)

位置推定の誤差xw(ui,vi) (ui+1,vi)

yw
d(ui,vi+1)

前節の手法でカメラ校正時に用いたフィールド 上の特徴点, 3 -. 点， 3 -6 点# の位置を推定した結果，その位置推定誤差は平均 5$(，最大誤差は "2.$( であった．

  60 推定誤差の計算法

フィールド 上のオブジェクト  の位置をカメラ  の画, ##

最初の特徴は，同じ 領域を異なる方向から複数のカメとする．ボールを片方のゴ ールからもう一方のゴ ールまラで捉えることで，オクルージョン領域を減らすことがで約可能となる．

像を用いて算出したものを，, # 3 , , #

'6$8 ( の速度で移動した際の軌跡を   5 に示す．  5 の横軸と縦軸はフィールドのサイド ライン' 台のカメラを用いて位置推定した際の誤差がガウス分を示す．白丸はカメラ ，黒丸はカメラ " より検出された布であり，互いに相関がないと仮定すると，静止した対象

ボールの位置を推定した結果である．カメラ校正時に用い物体  の位置

たフィールド 上の特徴点における位置推定誤差を求める

れる．

, # とその誤差  は次式により計算さことはできるが，それ 以外の点に関しては対応する世界

座標の真値が分からないため，誤差を求めることができ, #

3

ない．本報告では，  6 のように，画像座標 ,  # が



3

,



3

"

5 近傍に " 画素ずれた際の対応するフィールド 上の世界座

標点 ,   # 間のユークリッド 距離を推定誤差とする．
  5 における三角形は，各カメラにおいてボールの位置を推定した際の誤差

 , # 3 , , #  , ## を表している．位置推定誤差は， 6$( から $( の範囲で各カメラから離れるほど 増加していることが分かる．
これにより，本システムでは，あらかじめ各カメラの画像

 4 

 4 
¾

, # 4



#





 4 
, # ,.#   4 ,  4  #     ,-#

合成した誤差  は，それぞれのカメラの位置推定誤差
 と  より小さくなる．   は，同時刻における各カメラのボール位置推定誤差を式 ,-# により合成した結果を示す．

座標における世界座標での誤差を計算できるため，位置

上記の二つの特徴は複数のカメラを用いた特徴としてに応じた誤差を行動プラニングの際に不確定要素の大きよく知られているものである．本報告では，三つ目の特さとして扱うことが可能である．

徴であるビジョン処理の高速化に関する手法について提#$& # 台のカメラシステムの特徴

案する．通常のカメラシステムでは

で画像を取り込

むため，ビジョン処理された結果は

を超えることは' 台のカメラを用いたビジョンシステムの特徴は，,# オ

ない．

クルージョン領域の減少，, # 各々カメラの位置推定結果

そこで，本システムでは ' 台のカメラの結果を統合すを合成することによる誤差の減少，,# ビジョンの高速化

ることでビジョンの高速化を行う．本システムは，' 枚のの三つが挙げられる．

フレームグラバを " 台の  上に挿入したものでカメラ

21

Estimation error of obj’s positioni e [mm]vision processtransmittion process

6

1/30 = 0.033 [sec]5.5

process-1

e0
5
1

δ12

(a)

e

δ 21

δv

process-2

4.5

0.00

0.01

0.02

0.03

0.04

4

0.05

0.06

0.07

0.08

0.05

0.06

0.07

0.08

time [sec]3.5

process-1
3

e

δ12

(b)

δ 21

2.5
0

500

1000

1500

2000

2500

process-2

World X coordinate [mm]
0.00

0.01

0.02

0.03

0.04

time [sec]  0 合成誤差
  20

9" 

9' のタイミングチャート

間の同期機構を持たない．  5 におけるカメラ  による結果 ,白丸# とカメラ " の結果 ,黒丸# は交互にプロッする．  2 における ,# の場合は，' 台のカメラのトされており，これは " 台のカメラシステムよりも早い

キャプチャタイミングがほぼ等間隔 ,Æ

周期でボールの等速直線運動を捉えていることを意味す

異なった例である．, # の場合は，キャプチャタイミング

る．特別なカメラ同期機構を持たないでより高速な処理が近い例 , Æ  Æ    # である．本システムは，*

結果を得ることが，' 台のカメラを用いる三つ目の特徴であり，本報告で提案する仮想高速ビジョンシステムの特徴 Æ   # に

 ; の  上に実装され ，ビジョンプロセスに ' 秒，:* 通信に ". 秒を費やしている．
本システムでは，Æ と Æ を等間隔 ,Æ 3 Æ # にすである．

るためのカメラの外部同期機構を持たない．従って，タイ

高速な動き予測

ミングはそれぞれのカメラのシャッタータイミングに依存' 台のカメラは外部同期を使用しない場合，それぞれのキャプチャタイミングは異なる．本報告では，この異なりしている．本システムでは，画像のキャプチャとビジョンプロセス Æ が Æ と Æ よりも短い時間で処理を行う必における ' 台の非同期カメラによる仮想高速ビジョンシ要がある．この処理時間が満足されないと，二つのカメラ

ステムの特徴について検討する．

シャッターは同期した状態に近くなり，' で述べた特徴&$%, # の合成による位置精度の向上のみに使用されることに位置データの統合  " における



なる．
9" と



9' はそれぞれのカメラからの画像を "8  秒毎に処理する．各プ ロセスは，
カメラ  の処理結果である物体の位置, # と，その処理した画像のキャプチャ終了時刻を :* 通信により


9に送信する． 

9" と



9' は，" 台の 上で実装されているため，それぞれのプロセスからキャプチャ終了時に参照する時刻のずれは生じない． では， 

9" と



9

&$#

線形予測による動き推定

ロボットを正確に制御するためには，対象物の動きを予測して制御する必要がある．得られた最新のボール位置
から次の予測位置

式は，カメラ  の画像から計算された位置が最新の場合である．

9' から送信された結果をキャプ

 , #チャ終了時刻で整合し ，その情報を基にロボットを制御

3! , # 3 ,する．
' 台のカメラのキャプチャタイミングが同じである場合，

 , # を求める式を以下に示す．次

予測位置



! , #, # 4  ,Æ #, #,"# , ##Æ , # は，現在と一つ前の結果より物体 ! , # を求め，次の位置を線形に予測するもであ  5 におけるカメラ  による結果 ,白丸# とカメラ " のの速度

結果 ,黒丸# は重なる． る．カメラ " の結果が最新の場合は，上記の式の添字が9" と9' の時間間隔

が通常のビデオレートの半分 ,"8 秒# の場合， 9は "8 秒毎に位置データを交互に受け取ることができる．

入れ替わる．

9" と

9' のタイミングチャー&$&

トを示す．ここで，Æ を



9" から

9' まで

等速円運動における動き予測の実験として，  . に示の時間間隔，Æ を

9' から次の9" までとすようにターンテーブルとボールを用いた．長さ "$(  2 に









22

実験

2000

p0(obj)World Y coordinate [mm]p1(obj)
1800

1600

2
1
0

O

1400

1200

1000

800
200

400

600

800

1000

1200

1400

1600

World X coordinate [mm](a) Equally separated  .0 ターンテーブルを用いた実験の様子

2000

p0(obj)p1(obj)
1800

World Y coordinate [mm]の物差しの端にボールを固定し ，ターンテーブルを回転させることで半径 6$( の等速円運動となる．ターン
テーブルの回転数は 56$ ( であるため，ボールの回転速度は 
 ' 3 52.$8 (，また，速度は "' 2$8 (
となる．

&$&$%

等速円運動の復元

1600

2
1
0
1400

θ

O

Pi

1200

1000

  - にボールの等速円運動における検出した結果

800
200

の軌跡を示す．各プロット点は，時系列の順に  "  と

400

600

800

1000

1200

1400

1600

World X coordinate [mm]ラベル付けされている．白丸 ,奇数# はカメラ  のボール(b) Not Equally separatedの位置推定結果，黒丸 ,偶数# はカメラ " の結果を示す．
  -0 等速円運動の復元の高速カメラを用いたビジョンシステムの場合，ボールが一周するには "

秒かかるため，"   .

点のデータが得られることになる．  - は一周の実験

ムよりも ' 台のカメラシステムの方が平均予測誤差が小結果であり，. 個のデータがプロットされている．これよさいことが分かる．1

り，本ビジョンシステムのサイクルは高速カメラ ,である場合を %，そうでない場合を ) としたときの予測#

 " にカメラの時間間隔が等間隔と同等のスピード を実現できていることを示している．

誤差の平均と分散を示す．平均は時間間隔に関係なくほぼで処理した場合，連続した ' 点  と   の回同じであった．しかし，分散は等間隔の方が小さく，' 台転角度   !  の理論値は 2.6$( となる． 
" は，回転角度  !  の分布である．' 台のカメラの時間間隔が等間隔 ,Æ



まとめで処理した際の理論値に近いことが分かる．角速度は，  !  Æ で求められ
 の場合 52$8 (，ÆÆ Æ
 の場合 56$8 ( であった．その際の分散
は前者が "，後者が "6' であり，間隔が Æ Æ  

い予測が可能であるといえる．

 Æ   # の場合，回転角度の平均は 2. $( であり 
る．角速度の平均は，Æのカメラシャッターが "8 秒ずれているとより精度のよ

本報告では，ロボットを迅速にかつ正確に制御するために，通常の非同期カメラ , #' 台を用いた仮想高速ビ

ジョンシステムについて提案した．' 台のカメラは，" 台の  に接続されており，それぞれ

で処理される．

と等間隔である場合，より精度のよい円運動の復元が可能であるといえる．

&$&$#

1

 "0 予測誤差 $(

動き予測 

等速円運動するボールにおける次の予測位置を式 ,"#より求めた．その際の予測誤差を   "" に示す．予測%

誤差は，予測した次の位置と実際に観測された位置とのユークリッド 距離である．グラフ中の＋は，' 台のカメラ)

システムによる予測誤差，<は " 台のカメラシステムによる予測誤差である．  "" より，" 台のカメラシステ

23  


"

%

-5

' .

''.

=

' '

"2

"5

%

"'

'''

'".

=

5'

"

5

0.16

Rotation Angle [rad]  /     equally separated
not equally separated

0.14

 /!79' > 

'

0.12

0 *   $*+% ''( / *+%

0.1

   088   8Ave
0.0783 [rad]

0.08

0.06

$加藤 ' ( 加藤恭佑，日比野晋也，児玉幸司，村上和

0.04

人，成瀬正0 情報処理学会研究報告 =  =A9" 

0.02

B"

""69"'' ' 

0
0

10

20

30

40

50

60

70

80

$! '"( 太田紘高，遠藤龍矢，山本和彦，加藤邦人，

Pi (points in time sequence)

神成敦司0 画像処理と戦略の協調による /  小  "0 回転角度の分布

講演論文集

45

estimation error averageby single
estimation error averageby twosingletwo

40

35

Estimation Error [mm]型システム システムインテグレーション部門学術
6-9 '"

$1   "-.2( / C 1  0%       1 D  @ 9%

30

9

* A  = 925

 A  :  !E997  1= 

20

 ?   FFF >  /    %9  =  /%9  B5

15' 9 55 %  "-.2

10$/ '"( / )  > * > * 0

5

7

0
0

10

20

30

40

50

60

70

80

time sequence number(a) Equally separated
45

35

Estimation Error [mm]". / ?

         7  estimation error averageby single
estimation error averageby twosingletwo40

  %  

%'2 9'. '"$/   ' ( /  0  088  830$松山 "--.( 松山隆司025

分散協調視覚G視覚・行動・コミュ

ニケーションの機能統合による知能の開発 画像の20

15

認識・理解シンポジウム ,A/: +-.#

10

"--.

9 5 G 6'

5$中澤 '"( 中澤篤志 加藤博一 日浦慎作 井口征士0

0
0

10

20

30

40

50

60

70

散視覚エージェントを用いた複数人物追跡システム
情報処理学会論文誌 = 5' B ""'"  ""0 予測誤差

それぞれの処理結果を融合することで擬似的に以上の結果を得ることが可能となる．対象物の次の位置を予測する際に，' 台のカメラシャッターが約 "8 秒ずれているとより精度のよい予測が可能であることが分かった．

参考文献$%&  '( > %& 0 / 91    *  7 9
 :    ?7  @ 97  A  = 9

7  

      "'.9" 6 '$) '( > ) 1 )  A =  0分

80time sequence number(b) Not Equally separated  

      7   924'--G'2"

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑5 (5/2)

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

エンターテイメント 向けサッカーログフォーマット

2goOZ 形式の検討
2goOZ : A compression format of soccer game log to see

鹿田和之進、西野順二
Kazunoshin Shikada, Junji Nishino
電気通信大学 システム工学科
Dept. systems engineering, UEC
shika@fs.se.uec.ac.jp, nishino@se.uec.ac.jp

Abstract
Recently, multi agent games such as RoboCup
soccer have grown and made great progressso that their games become very close to human games. In this paper, we introduce
an compression method on multi agent gamelogs for XML data format. Combinationof linear-predictor(LP) and vector quantization(VQ) shows good performance in both compressing rate and errors for this purpose. This
result indicates that teams use cooperative formation play style.

1 はじめには、市場の要求から広範な研究がなされており [2, 3] 、ほぼ完了していると言っても過言ではない。
いっぽうでサッカーのような多人数ゲームの行動記録について、効率的に圧縮する方法についての検討はほとんどみられない。
本研究は、多人数ゲームの行動記録を圧縮に基づいたXML フォーマットで記録することを目指している。これまでに人による観賞を主たる目的とした圧縮について、基礎的な圧縮方式について検討し [4] 線形予測とベクトル量
子化をあわせた方法を提案した。本論文ではこの方式について検討する。

2 Soccer Log の観賞
2.1

ログの質の向上

RoboCup サッカーシミュレーションリーグ [1] では、11
対 11 の人工プレイヤがそれぞれ個別のプログラムで作成

本論文は、RoboCup サッカーに代表されるマルチエージェ

され、ネットワークを介してバーチャルサッカー場であるントゲームの記録方式について、ユーザによる娯楽的観

サッカーサーバに接続し、サッカーの試合を行う。このと賞を目的とした、符号化と圧縮表現の方法について検討することを目的とする。

きボールと各プレイヤの行動、すなわち試合の全体像は

PDA など携帯情報端末の処理速度や記憶容量に制限のサッカーサーバによってログとして記録されている。

ある環境下では、提示データの圧縮保存が必要である。いっり、試合のログを見ているかぎりでは、人間の行っている

ぽう、サッカーに代表される多人数ゲームのより臨場感の近年、人工プレイヤの行動判断のレベルが上昇しておサッカープレイとみまごうばかりと言われている [5] 。単ある再生には、鳥瞰やボール周辺だけを自由に表示でき

純にサッカーの試合のリプレイとしての観賞にも耐えるるスケーラビリティが必要である。計算機的には、各プレものとなっている。

イヤやボールの位置情報を、時間経過にともなってコーディングすれば良いことになるが、その容量は、プレイ

2.2

ヤ数とゲーム時間に比例して巨大なものとなる。行動分

さらに、より高度な戦略を目指し、システム、アルゴリ

析など学術目的のための符号化では可逆性が不可欠だが、ズムの更新を行なうため、チェスプログラムの開発同様、人による観賞を目的とすればそれに応じた非可逆的な圧サッカーの専門家による評価のフィードバックも有効と考縮の可能性がある。

えられる。このとき評価の記述と実際の行動を時間軸に一般に、あるデータに対して最適な情報圧縮の手法はXML による注釈付きログ

沿って対応させ記録する必要がある。

目的に応じて異なるものである。可逆なデータ圧縮と、静XML など構造化された記述形式を援用することが望ま

止画像、動画像および音声に関する非可逆圧縮について

しいが、行動記録のサイズがあまり大きくては、実装にお25

<?xml version="1.0"?><RCG SOME-Properties>..
<2goOZCodeBook><Code name="c00">..vector</Code><Code name="c01">..vector</Code>..
</2goOZCodeBook><ShowInfo time="1"><2goOZCode>..Code(c01)..</2goOZCode><Comment>
Comments at this timeby human</Comment></ShowInfo><ShowInfo time="2">..
</RCG>

Figure 1: XML ログフォーマット (一部)
いて非現実的となる。PDA の記憶サイズ (10M 程度) で数試合分の試合ログと、コメントログを同時に保存できることが目標である。

RoboCup サッカーログに関しては、公式配布されているサッカーサーバ rcssserver Ver. 9.* に、XML フォー
マットログ生成機能が実装されている。これは 2003 年 4月の段階では、実験的なものである。ログとして保存された全ての情報を圧縮無く時系列に保存している。このため 1 ステップあたり 10Kbyte 程度の文字量で、6000 ス
テップの試合全体では 60Mbyte 、gzip による単純圧縮によっても 5.5Mbyte の容量となる。

コメントの追加を想定すると、圧縮済データの容量と3.1 サッカー試合情報のモデル化
サッカーの試合内容を再現する情報は、全てのプレイヤとボールの動きが主体である。このほかに、プレイヤの手や姿勢、首の向き、表情、といった詳細情報や、風の状
態、芝の状態、照明、天候の状態といった外乱要因情報もある。しかしこれらは、ボールを取り合うゲームとして見たサッカー試合の情報の再生においては、さして重要ではない。

プレイヤは試合開始 t = 0 から終了時刻 t = T までの間、一連の移動を行なっており、これがゲームの本質である。よってプレイヤ i の試合全体での行動は、時間をパラメータとする平面座標の関数 Pi (t) = (xi (t); yi (t)) で表される。22 人のプレイヤとボールも同様に含め次の 23 点さらに x,y 軸に分け、46 次元のベクトル関数となる。

( ) = (P0 (t)P t

1 1 1 P22(t))

ただし、0  t  T 、i = 0 はボール、i = 1〜11 はチーム

L のプレイヤ、i = 12〜22 はチーム R のプレイヤを表す。
一般に P (t) は連続な関数となるが、実際上は、適当なΔ t でサンプリングし、センサシステムによる量子化が行なわれる。ここでも P (t) は離散化された時系列データと
して扱う。

3.2

基礎的なサイズ見積

RoboCup 公式サッカーサーバが生成するサッカーシミュ
レーションの行動ログには、管理情報など行動情報以外のデータが含まれており、おおむね 10Mbyte〜30Mbyteというサイズである。これは不要に大きい。
ここでは、再生に必要な情報に限定したうえで、必要容量の見積りを行なう。

RoboCup サッカーは 2 チーム合計 22 プレイヤエージェ

ントにより行なわれる。試合時間は 600 秒間で、サンプ

リングタイムは 0.1 秒となっており、ロスタイムを除いて試合全体は 6000 ステップとなる。人間サイズにモデル化

して、１ゲームあたり 10〜100Kbyte(0.1Mbyte) 程度が望されたエージェントとサッカーフィールド のサイズから、ましい。

賞に必要な精度としては、0.1m 刻み程度の解像度で十分

本稿で検討するベクトル量子化に基づいた圧縮データ
は、コードブックとコード本体からなる。コード本体の生成を各時間ステップ毎に行なうことで、XML データ中での時間とコメントの対応が可能となる。
以下では、図 1 に示したような、rcssserver の XML ロ

その位置情報を表現するに必要なビット数を考える。観である。フィールド サイズは 100m に収まるので、位置情報は log2 (100=0:1)  10 bit となる。

以上の仮定から、基本的なデータサイズを見積もると次のようになる。
size

グを改変したフォーマットを想定する。

3 サッカーとしての圧縮

3.3= (10 + 10) 23 6000 = 345K B:
2

2

圧縮システム本論文で扱うサッカー試合のデータの主たる用途は、人間が観賞することにある。このため、ユーザの感性にとっここでは、対象となるサッカーの試合が持つ情報量につて違和感のない範囲での、非可逆な圧縮が可能な対象でいて、そのモデル化と見積もりを行なう。

ある。

26

Table 1: 手法の比較
手法

サイズ1467 KB
361 KB
205 KB
134 KB
58 KB
50 KB

オリジナルデータ

gzip のみ

１次線形予測再量子化
ベクトル量子化
線形予測＋ベクトル量子化

圧縮率

0％
75 ％
86 ％
91 ％
96 ％
97 ％

平均誤差

0
0
0
0.24
4.69
0.62

一般に、このような情報源符号化の場合、1) サンプ リング、2) 非可逆圧縮 (量子化) 、3) 可逆圧縮を順に行なう。

最大誤差

0
0
0
0.5
25.9
2.1

いほど優秀な手法が実用化されている。
そこで、本研究では圧縮システムのうち非可逆な圧縮のみを対象とし、可逆圧縮には一貫して gzip を用いるこある。

3.4 LP+VQ によるログの圧縮
圧縮法として、線形予測とベクトル量子化を組み合わせた方式が、多少の静止位置での誤差を含むものの良好であった [4] 。ここでは本手法の基礎となる方式とそれらの比較を行なう。
１次線形予測 (LP)

線形予測モデルを用いて残差情報のみ圧縮する方法で、音声の圧縮等に用いられる。

予測関数を f (t) = 1:0 2 P (t 0 1) で表される１次線形

平均 0.5m の誤差

46 次元の状態を直接コーデ ィング
停止点近傍で摂動する^ ( ) = P^ (t 1) + E^ (t)P t0

ここでの残差ベクトルの分布は、コードブックを作成したときの残差ベクトルの分布と多少異なっており、最適性には疑問が残るものの、現実的に大きな問題はない。

この方式でのサイズは 49.5Kbytes(96.6 ％) で、図 3 にととする。以降の圧縮データ量は、提案した手法で量子化し作成したテキストデータを、gzip で圧縮したもので可逆圧縮

ただし、伸長予測値は次の式で与える。

可逆圧縮はハフマン符号化や LZ アルゴリズムに代表される、lossless 圧縮である。すでに原理上改善の余地が無

備考

示す。

4 性能評価
各手法の圧縮サイズと誤差を表 1 にまとめる。

1 次線形予測モデルを用いた圧縮は、可逆圧縮でありな
がら、比較的高いパフォーマンスをあげている。gzip が実質的には統計的圧縮を非常に高い精度で行なっている

ものの、時刻 t-1 との差相関には予測モデルを使わなければ対応できないことを示している。この時点で 200KB 程度であるが、試合に対するコメントが 10〜50KB である
ことと比較すると、まだ大きすぎると言える。

関数とした。すなわち予測誤差ベクトルは前時刻との差

刻み幅を単純に大きくした再量子化は、アルゴリズムと等しくなり、E (t) = P (t) 0 P (t 0 1) となる。この E (t)が単純であるという利点がある。いっぽうで量子化刻みを後段の可逆圧縮の対象とした。

が、逆にそのまま誤差に現れる。また、今回の観賞用デー

ベクト ル量子化 (VQ)

各時刻での 46 次元位置状態ベク

タの圧縮という目的にはやや圧縮率が低い。

トル、(P0 (t) 1 1 1 P22 (t)) を、ベクトル量子化してコーディ

ベクトル量子化 (VQ) は、非可逆圧縮の手法としては古ングした。コードブックの生成には、自己組織化マップに典的であるものの、一般的に行なうには計算時間がかか

よる学習を用いた。コードブックとして 16x16 の２次元マップを用いた。

3.5 2goOZ フォーマット ：１次予測＋ベクト ル量子化提案した 2goOZ フォーマットは、LP と VQ を融合したるという難点がある。そのため通常はベクトルの要素数
が 2〜5 程度で用られる。

本研究で用いた、自己組織化マップによって圧縮用コー

ドブックを作成する手法は、46 次元という多次元ベクトルを効率的に扱える方法である。また、その圧縮パフォー

マンスも 96 ％と非常に高いものとなっている。しかし、方式である。

図 2 にシステム構成を示す。

１次予測残差、(E0 (t) 1 1 1 E45 (t)) について、ベクトル量

6000 点を 256 種の辞書でそのまま表現することで、大きな誤差が発生しており、再生には適さない。

提案した、１次線形予測誤差に対して、VQ を適用す

子化を行なった。

^ を積算することによる累積誤差を
なお、歪みのある E排除するため、各時点の残差を源情報と伸長予測値の残差を量子化したものである。次の式で計算する。

^ = C odeBook (P (t) P^ (t 1))E00

る、LP+VQ 方式は、全域で誤差が少なく、平均誤差も小さくなっている。全域では誤差が少ないものの、図 3 中の拡大部に示すように、誤差により停止点近傍での実在しない摂動が発生する現象が問題である。

27

SOM/dictionary
makingError
E(t)Codingwith code book

VQ dict
book

outputCodeCompressed
Log

Linear Predictor
Second ErrorE’(t)Source Log

Linear Predictor

Figure 2: LP+VQ 圧縮システム
圧縮率と精度のバランスを考慮すると、今回対象とし

40ている、サッカー型マルチエージェントゲームの試合ログ

30

20の圧縮に有効であると言える。

10

5 おわりに

0

-10

-20

従来は、音響や画像情報にのみ用いられてきた非可逆圧縮-30

手法を、人間の観賞を対象とした、サッカーの試合記録の

-40
-60

情報圧縮に適用した。１次線形予測とベクトル量子化の両方を利用した手法が、圧縮度では満足のいくものであっ

-50

-40

-30

-20

-10

0

10

20

30

40

(全体)

10

た。また、ベクトル量子化の結果各時点でのコードを元にXML フォーマットを構成することができた。いっぽう停5止点付近での摂動は、観賞には適さない誤差であるため、その改善は必要である。

0

サッカーの試合におけるフィールド 全体での定型的な-5

動きの冗長度を捉えていると言える。特に、１次線形予測を用いたモデルでの、ベクトル量子化が高圧縮率であっ

-10
-10

たのは、全体での並行移動が多々みられたからにほかなであった。チームワークの存在を考えると、時間とプレイに基づき、協調行動を表す小さな知的予測モデルが構成できれば、より効率の良い圧縮が可能となる。

参考文献[1] A. Birk, S. Coradeschi, and S. Tadokoro, editors.
Robocup 2001 : Robot Soccer World Cup V, volume
2377 of LNAI. Springer, 2002.

5

10

Figure 3: 予測＋ベクトル量子化

今回は時間方向については、１次線形予測のみの対応が存在すると考えられる。これらのチームワークの存在

0(停止点付近拡大図)

らない。

ヤの両軸に広がったより高次元ベクトルでの情報冗長度-5[3] 情報理論とその応用学会, editor. 情報源符号化 歪みのあるデータ圧縮. 培風館, 2000.
[4] 西野順二. サッカーシミュレーションログデータの圧縮フォーマット . 情報処理学会ゲーム情報学研究報告, 2002-GI-9(35):7{12, 3 2003.
[5] 野田五十樹. ロボカップシミュレーションリーグ . In
第７回ゲームプログラミングワークショップ講演論文集, pages 22{27. 情報処理学会, 2002.

[2] 情報理論とその応用学会, editor. 情報源符号化 無歪
みデータ圧縮. 培風館, 1998.
28

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人間プレ イヤのポジションカバー行動の発現

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑6 (5/2)

           
戸田英治、西野順二、鹿田和之進、本多中ニ        

電気通信大学 システム工学科

     !  !  "    #$        

UDP/IP network
OZ-RP system                                                     !                              
        
 "        

Soccer Server

Ctrl Log
Game Log
Intelligent
Multiplexer system
Interface
Screen + PAD
Human (Real) Players
Artificial Players(Opponent team)&"  '(  システムの構成：動作サポートは 

 はじめにローカルサーバで実現する

本論文は、シミュレーションサッカーにおけるバーチャル 計測の方法

環境下での、人間の協調的行動について計測、分析するこ% & '()* システムとを目的としている。さらに、この観測から得られた協調#)* +* ,%は 、人工プレ イヤど うしでおこなわれる  サッカーシミュレーションリーグ #'%の試合に 、行動モデルを 、協調環境にある人工システムに活かすことを目指している。
分散環境下におかれたロボットやエージェントシステ
ムの協調においては互いの情報伝達が重要な役割を持つ。

人間が参加するためのシステムであり、すでに様々なバー

ジョンを構築し実験を進めている#-%。

システム構成の概念図を図 ' に 、操作端末の例を図 )しかしながら電波や光、音声などの無線通信には、情報の欠落や不完全性、不規則な雑音が含まれ 、疎な伝達しかにそれぞれ示す。   システムは、ボール追従、行なえない。人間は、サッカーの試合での協調的プレイを目的位置へのパス、目的位置への移動というマクロレベ

頻繁に行なっている。その情報通路は単音節程度の簡易

ルの指令を与えることができる端末である。人間に対しな音声や、簡単なジェスチャーといった疎な伝達のみで 、て得られる情報も、各人が担当するプレ イヤの視界に制高度な協調行動を実行している。

限され 、なおかつノイズを含んだものとなっている。これ  サッカーシミュレーションに、人間が参加でらの制約を満たすことで 、人工プレ イヤとフェアな条件

きるようにするユーザインタフェースシステム  シ

で試合ができるように設計したものである。

ステムを用いて、人工チームとのシミュレーションサッ
カーの試合を行う。これまで、フォワードプレ イヤについ% % 実験試合

イヤ相互のカバー行動について分析する。

のキャンプで対戦実験を行なった。'' プレ イヤ中、フォて統計的な指標に基づき分析した#$%。本論文では 、プレ)..) 年 '. 月に名古屋工業大学で行なわれた   秋

29  '( 分析に用いた試合  0    )..)
対戦チーム

        
!4561!4561!4561!4561&"  )(    システム：ユーザ端末の一例

  " 0 
 76 .) 76  )..)  " 0 
 76 .) 76  )..)

結果

.'
'-.
)$.
-.
.'
,3.
,,.
)-.

+ & フォーメーションの時間変化
人間行動における適応的変化を対象とするため、平均座標の時間変化を比較する。
一試合 -... ステップを $.. ステップずつの時間帯セグ

メントに ') 分割し 、おのおのの位置座標時間平均を算出

T(NO 11)(NO 8)した。図 + に 、人間チームが強いチーム / " 2 と戦った試合での、前半冒頭、後半 , セグ メント目の二つの時点でのフォーメーションを示す。
相手のチームが強いチームであることを 、時間経過とS(NO 10)(NO 6)

ともに把握し 、フォワードプレ イヤが１名中盤に移動していることがわかる。さらに、その空いたフォワード のス
ペースを埋めるために 、残り２名のフォワードプレ イヤ(NO 7)

Aがバランス良い位置に移動している。

(NO 9)

これは互いに無言のまま創発した行動で 、音声その他の方法で当座に相談して行なったのではなく、また事前の打ち合せがあったわけでもない。このようなアプ リオリ
な行動シナリオをサッカーを知る人は持っており、暗黙の&"  ,(    のフォーメーション

協調が生まれることを確認できた。また、この変化は常識的な観点で適切なものであったと言える。

ワード , 名を人間パイロット /0 、1 、 と呼ぶことにする2 が操作し 、残り 3 名を人工プレ イヤが補助して ' チームとした。補助人工プレイヤには、東京工業大学秋山氏作成によるチーム !4561 のエージェントを採用した。試

合中の人間プレ イヤの位置を図 , に示す。

同じ 相手に対する人工プレ イヤのみのチームの試合の様子を図 $ に示す。いずれの時点でも、フォーメーションが変化していないことが分かる。

+ % 人間の適応行動

実験中行なった試合から、チーム !4561 が行なった

次に 、人間プレ イヤがフォーメーションを変化させた様

試合を中心にして分析用にいくつか選択した。これは、本テップずつの時間帯セグ メントに -. 分割し 、おのおののチームの守備に充当されている人工プレ イヤ !4561 との比較をすれば 、人間３名以外の条件をそろえて比較ができるためである。選択した試合の一覧を表 ' に示す。

子をより詳しくみるため、一試合 -... ステップを '.. ス

8 方向の位置座標時間平均を算出した。さらに 、人間プ
レ イヤの 8 方向の平均座標 8/2 の移動平均 9/2 を式 'を用いて算出した。

/2 : ; ; /  2

人間フォワード の行動の特徴実験した試合結果それぞれに対し 、フォワードプレ イヤのフォーメーションの適応性を調べた。

ここで

30

 : .3 とする。





/'2

(1) 1 - 500(1) 1 - 500
ball
OZRP
TsinghuAeolus

-30

A
-20

ball
HELIOS
TsinghuAeolus

-30

-20

-10

-10

S
0

0

10

10

T
20

20

30

30
-40

-20

0

20

40

-40

-20

(9) 4001 - 4500

0

20

40

(9) 4001 - 4500
ball
OZRP
TsinghuAeolus

-30

ball
HELIOS
TsinghuAeolus

-30

A
-20

-20

S

-10

-10

0

0

T
10

10

20

20

30

30
-40

-20

0

20

40

&"  +( 人間のフォーメーションの時間変化

-40

-20

0

20

40

&"  $( ロボットプレ イヤ /!45612 のフォーメーショ
ンの時間変化

図 - に、人間フォワードプレ イヤの 8 方向の移動平均の時間変化を示す。
強い相手 /りから 1 と " 2 との試合では、). セグ メントあた

範囲の一部を補うために 1 のポジションのほうへと移動したと考えることができる。
これは、人間が決められた環境のみだけではなく、状況は少しずつ位置が上方へと移動していることがわかる。また、0 は他の試合に比べて少し中央によってはいるが 、試合の中では大きな変化ない。

の変化に応じて適切な行動をとることが出来ることを示している。

ポジションを移動したプレ イヤ 0 とフォワード に残っ

まとめた２名 /1 、 2 のプレイヤとの 8 方向の平均座標の差を求め、式 ' と同様に移動平均を算出した。これにより、ボーシミュレーションサッカー環境における人間プレイヤの行

ルの移動による全体の運動を除き、相対的なフォーメー動について、観測した記録にもとづいて分析した。フォーを図 < 、図 3 に示す。

ない協調行動の発現が観測された。人間がもつサッカーションを示すことになる。1 、 と 0 との 8 方向の距離
人間プレ イヤの２名と 0 との距離は、弱いチームとの試合では時間の経過ととも大きな変化はみられない。それに対して、強いチーム / " 2 との試合では 、0 との距離が時間の経過とともに減少していることがわかる。
強いチームとの試合では 、0 は本来のフォワード のポ

ジションから中盤ヘと移動している。そのため、0 がいな

くなり空いてし まった範囲を補うために、1 は 0 の範囲も補うことができるような位置へと移動した。しかし 、1が移動したことで、1 の担当していた範囲を十分にカバーすることが出来なくなってし まう。そのため、 は 1 のメーションの時間変化からは 、あらかじめ準備されていにおけるシナリオ・チャンクの存在を示している。時間変動など 統計的指標でも、ある程度の人間行動の特徴把握ができることが分かった。今回の知験をもとに、カバー行
動に関する追加実験を行い、発現のプロセスをモデル化することが課題である。

参考文献#'%  1 *  = *   > ?@* 
        *  ).'A   1 "* )..'
31

vs TsinghuAeolus

vs TsinghuAeolus (S)
25

A
S
T

30
20

S

20

10
15

0
-10

10

-20
5

-30

0

0

10

20

30

40

50

10

60

20

30

40

vs NITsoccer02
A
S
T

20

60

vs TsinghuAeolus (T)
40

30

50

T

35

30

10
0

25

-10
20

-20

0

-30
0

10

20

30

40

50

60

10

20

30

40

50

60

&"  <( 強い相手との試合でのプレ イヤ 0 に対する 8方向の距離の時間変化&"  -( 8 方向の平均座標の時間変化
vs NITsoccer02 (S)#)% 秋田純一* 西野順二* 久保長徳* 下羅弘樹*   藤墳到  シミュレーション リーグ 人間参戦システム
@ の提案 6  チャレンジ 研究会第  回資料*
" ),B)3 人工知能学会* )..'

35

S

30

25

#,% 西野順二 ド リームチーム @ と人間チーム @ の挑戦 日本ロボット 学会誌* )./'2(,A B +.* )..)

20#+% 西野順二* 久保長徳* 秋田純一*   下羅弘樹 @150

システムを用いたバーチャルサッカーでの人間協調行
動の観測 6 第  回インテリジェントシステムシン

10

20

30

40

50

60

vs NITsoccer02 (T)ポジウム講演論文集* " '+AB'$)* )..'

50#$% 西野順二* 戸田英治* 鹿田和之進*   本多中二 バー
チャルサッカーにおける人間  の特徴分析 情報処理学会ゲーム情報学研究報告* )..,>6A/,$2('B-* )..,

T

45

40

#-% 島涼平* 西野順二*   本多中二 @ における協調行動の分析 情報処理学会ゲーム情報学研究報告*)..)>6</)<2(AB'-* , )..)

35

30
0

10

20

30

40

50

60

&"  3( 弱い相手との試合でのプレ イヤ 0 に対する 8方向の距離の時間変化

32

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑7 (5/2)

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

A Hierarchical Multi-Module Learning System based on
Self-Interpretation of Instructions by Coach
12
Yasutake Takahashi, Koichi Hikita1, and Minoru Asada1 2
1;

Dept. of Adaptive Machine Systems,
Handai Frontier Research Center,
Graduate School of Engineering, Osaka University
fyasutake,khikita,asadag@er.ams.eng.osaka-u.ac.jp;

2

Abstract
We propose a hierarchical multi-module leaningsystem based on self-interpretation of instructions given by coach. The proposed method
enables a robot (i) to decompose a long termtask which needs various kinds of information
into a sequence of short term subtasks which
need much less information through its selfinterpretation process for the instructions given
by coach, (ii) to select sensory informationneeded to each subtask, and (iii) to integrate
the learned behaviors to accomplish the given
long term task. We show a preliminary resultof a simple soccer situation in the context of
RoboCup [1].
1 Introduction
Reinforcement learning (hereafter, RL) is a fascinating
method for robot behavior acquisition with little or noa priori knowledge and higher capability of reactive andadaptive behaviors [2]. However, RL seems dicult tobe applied to real robot tasks because the learning system needs a huge monolithic state/action space which
consists of all kinds of sensory information and actuator commands, and such a big exploration space leads
to scale the learning time exponentially. Therefore, it
is hard to realize such learning systems from a practical
viewpoint.
Fortunately, a long time-scale behavior might be often decomposed into a sequence of simple behaviors ingeneral, and therefore, the searching space is expected
to be able to be divided into some smaller ones. Connell and Mahadevan [3] decomposed the whole behavior into sub-behaviors each of which can be independently learned. However, task decomposition and behavior switching procedure are given by the designers. Morimoto and Doya [4] applied a hierarchical
RL method by which an appropriate sequence of subgoals for the task is learned in the upper level while
behaviors to achieve the subgoals are acquired in thelower level. In their system, the human designer has
to de ne the subtasks based on their own experiences
and insights. Doya et al. [5] have proposed MOdular Selection And Identi cation for Control (MOSAIC),
which is a modular RL architecture for non-linear, nonstationary control tasks. However, the all learning modules share the same state space. Takahashi and Asada [6,7] proposed a multi-layered RL system. The modules in
the lower networks are organized as experts to move into
di erent categories of sensor output regions and learn
lower level behaviors using motor commands. In themeantime, the modules in the higher networks are organized as experts which learn higher level behaviors using
lower modules. However, this system tends to produce
not only purposive behavior learning modules but also
many non-purposive ones, and as a result, to requirelarge computational resources.
When we develop a real robot which learns various
behaviors in its life, it seems reasonable that a human
instructs or shows some example behaviors to the robot
in order to accelerate the learning before it starts tolearn. Whitehead [8] showed that instructions given bycoach signi cantly encourages the learning and reduces
the learning time. This method, called LBW (Learning By Watching), reduces the exploration space andmakes learner have experiences to reach the goal frequently. Asada et al. [9] proposed a method, called LEM(Learning from Easy Mission). This basic idea is that alearning scheduling such as a robot starts to learn in easy
situations to accomplish a given task at the early stage
and learns in more dicult situations at the later stage
accelerates the learning the purposive behavior. They
applied this idea to a monolithic learning module. In
order to cope with more complicated tasks, this idea canbe extended to a multi-module learning system. That is,
the robot learns basic short term behaviors at the earlystage and learns complicated long term behavior at thelater stage based on instructions given by coach.
In this paper, we propose a behavior acquisition
method based on hierarchical multi-module leaning system with self-interpretation of coach instructions. The
proposed method enables a robot to33

1. decompose a long term task into a set of short term
subtasks,
2. select sensory information needed to the current
subtask,
3. acquire a basic behavior to each subtask, and
4. integrate the learned behaviors to a sequence of the
behaviors to accomplish the given long term task.
We show a preliminary result applied to a simple soccer
situation in the context of RoboCup [1].
2 Basic Idea

stage 1acquired learning modules

a new herarchical structure for task1

L.M.u1
L.M.1

L.M.2

stock new learning modules

stage 2acquired learning modules

a new herarchical structure for task2
L.M.u2
L.M.s1

L.M.1

L.M.s1

L.M.1

L.M.2

L.M.u1

L.M.3

L.M.1

L.M.2

reuse available acquiredlearning modules

stock new learning modules

stage 3Coachacquired learning modules

a new herarchical structure for task3
L.M.3

L.M.u3

L.M.s2

L.M.s1

L.M.1

L.M.2

L.M.u2

L.M.s2

?

L.M.3

L.M.4
L.M.s1

L.M.1

L.M.3

reuse available acquiredlearning modules
Learner !!

Figure 2: The perspective of of development of the learning system with staged instructions

Figure 1: Basic concept: A coach gives instructions to
Hierarchical Multi-Module Learninga learner. The learner follows the instruction and nd 3 System
basic behaviors by itself.
3.1 Architecture

There are a learner and a coach in a simple soccer situation (Figure 1). The coach has a priori knowledge oftasks to be played by the learner. The learner does nothave any knowledge on tasks and just follows the instructions. After some instructions, the learner segments thewhole task into a sequence of subtasks, acquire a behavior for each subtask, nd the purpose of the instructed
task, and acquire a sequence of the behaviors to accomplish the task by itself. It is reasonable to assume thatthe coach will give instructions for easier tasks at theearly stage and give ones for complicated tasks at thelater stage although it does not have any a priori knowledge about the learning system on the agent.
Figure 2 shows the perspective of development of thelearning system through instructions given by coach atthree stages. When the coach gives new instructions,the learner reuses the learning modules for familiar subtasks, generates new learning modules for unfamiliar
subtasks at lower level and a new module for a sequenceof behaviors of the whole instructed task at the upper
level. After the learning at one stage, the learner adds
newly acquired learning modules to the learning module
database. The learning system iterates this procedurefrom easy tasks to more complicated ones.

The basic idea of multi-layered learning system is similar to [6, 7]. The details of the architecture has been
extended. The robot prepares learning modules of one
kind, makes a layer with these modules, and constructs
a hierarchy between the layers. The hierarchy of thelearning module's layers can be regarded as a role of task
decomposition. Each module has a forward model (predictor) which represents the state transition model, anda behavior learner (policy planner) which estimates thestate-action value function based on the forward modelin an RL manner (Figure 3(b)). The state and the action are constructed using sensory information and motor command, respectively at the bottom level.
The input and output to/from the higher level are thegoal state activation and the behavior command, respectively, as shown in Figure 3. The goal state activation g
is a normalized state value , and g = 1 when the situation is the goal state. When the module receives the
behavior command b from the higher modules, it calculates the optimal policy for its own goal, and sends actioncommands to the lower module. The action command at
the bottom level is translated to an actual motor com1

1 The state value function estimates the sum of the discounted
reward received over time when the robot takes the optimal policy,
and is obtained by Q learning.

34

3.3 Availability Evaluation
Learning
Moduleupper layer
state

actiong 1 ... gn

b 1 ... bn

an existing learning module is available
new learning modules are needed

Learning
Module n

Learning
Module 1(s 11, ... ,s1m )lower layer(s n1, ... ,snm )1nstate 1_

actionstate nQ
sensor

_
Qth

motor

World

(a) A whole system

ignoret
Goal State Activation

Figure 4: Availability identi cation during the given
sample behavior

Behavior Command

PlanneraPss’ R s

Predictor

The learner needs to evaluate the availability oflearnedbehaviors which help to accomplish the task(b) A module
by itself because the coach neither knows what kind of
behavior the learner has already acquired directly norshows perfect example behavior from the learner's viewFigure 3: A multi-layered learning system
point. The learner should evaluate a module valid if it
accomplishes the subtask even if the greedy policy seems
from the example behavior. Now, we introduce
mand, then the robot takes an action in the environment. Qdi inerentorder
to evaluate how suitable the module's policy
An approximated state-action value function Q(s; a) is to the subtask
as follows:
for a state action pair (s; a) is given by
X P^ hR^ + max Q(s ; a )i ; (1)Q(s; a) =Q(s; a ) 0 min Q(s; a ); (2)Q(s; a ) =max Q(s; a ) 0 min Q(s; a )where P^ and R^ are the state-transition probabilities and expected rewards, respectively, and the is thewhere a indicates the action taken in the instructed exdiscount rate.
ample behavior. Q becomes larger if a leads to the
3.2 A Learning Proceduregoal state of the module while it becomes smaller if
a leaves the goal state. Then, we prepare a threshThe steps of the learning procedure are as follows:
old Q , and the learner evaluates the module valid for a
1. Coach instructs some example behaviors to accom- period if Q > Q . If there are modules whose Q exceeds
plish a task.
the threshold Q simultaneously, the learner selects themodule which keeps Q > Q for longest period among
2. Learner evaluates the availability of learned behav- themodules (see Figure 4).
iors to accomplish the task by watching the examples.
3. The learner segments the task into subtasks, and 3.4 Generating new learning modules
produces new learning modules at the lower layer if
needed, and learns the behavior for each.
If there is no module which has Q > Q for a period,
4. The learner produces a learning module at the thecreates a new module which will be assigned
higher layer and learns the whole behavior to ac- to thelearner
not-learned-yet
subtask for the period. In order tocomplish the task.
assign a new module to such a subtask, the learner iden5. Go to step 1.
ti es the state space and the goal state. The followingshows the steps brie y.
State

a
ss0

s

0

a
ss0

Action

a
ss0

0

0

a0

e

e

0

a0

a
ss0

0

a0

0

a0

e

e

e

th

th

th

th

th

35

1. Prepare a set of state spaces S and, set their priorities as S : i = 1; 2; 1 1 1.
2. For each state space S ,(a) Estimate a goal state space G in the state space
S based on the instructed example behaviors.
(b) If the estimated goal state space G covers all of
the state space S , increment i and goto step (a).
(c) Construct a learning module and calculate Q values.
(d) Check the performance of the learned behavior
for the subtask. If the success rate is low, increment i and go to step (a).
3. Add a new module based on the state space S andthe goal state space G.
4. Check the availability of modules over the giventask. If there is a period where there is no available module, go to step 1.
5. Exit.

subtask (see Figure 5).
2. Higher priority is assigned to the state space which
has smaller average of entropy H (s; a) (see equation
3) of the state transition probability P for theexperienced transition.
X P (s; a; s )log P (s; a; s ) (3)H (s; a) = 0

i

i

a
ss0

i

s0 2S

i

a
ss0

0

a

2 ss0

0

The reason is that the learning module acquiresa more purposive behavior with more stable statetransition probability which has lower entropy.
3.4.2 Goal State Space Selectioni

x3 sequences ofexample behaviors

x2

3.4.1 State Variables Selection

If the number of state variables which construct thestate space is large, the number of state scales up exponentially. We adopt heuristics, that is, only a few statevariables are needed for all subtasks even if large number of state variables are necessary for the whole task:
We limits the number of variables to only three in thisstudy.

goal statex1(a) goal state is speci ed by all
variables x1 ; x2 ; x3

sequences ofx3 example behaviorsQ_

new learning modules are neededs(value of state variable)

goal state

x2

x1

t

(b) goal state doesn't care aboutvariable x2∆s∆t

Figure 6: De nition of goal statetFigure 5: Gradient of a state variable
The system produces state spaces of all combinationsof state variables and check their validities, however, thisprocedure takes much time. We introduce other heuristics and set priorities to the set of state spaces as follows:
1. Higher priority is assigned to the state variablewhich changes largely from the start to the end
during the example behaviors because it can be regarded as an important variable to accomplish the

It is hard to specify the goal state of the subtask withlimited number of experiences of example behaviors. We
need other heuristics here.
 A state variable of the goal state tends to be themaximum, the minimum, or the medium.
 If the value of a variable has no consistent one at
the terminate state of the example behavior, thevariable is independent of the goal state.
The system produce a reward model based on theseheuristics.
36

3.4.3 Performance Evaluation

Even if we got a module with a proper policy basedon the state transition model and reward one, there is
no assurance that the module acquired a sucient performance to the subtask. Before the system adds a newmodule to the available module database, it checks the
success rate of the module. If the success rate is low, thesystem discards the module.

Ball
Opponent agent

Learning agent

3.5 Learning behavior coordination(a) A real robot
and a ball(b) Top view of the
eld

g

3

goal

start

LM 3

LM 1

g

2

(c) Simulated camera
image with a omnidirectional mirror

LM 2

g1

Figure 7: An example state transition on upper layer
state space

Figure 8: Real robot and simulation environment

After the procedures mentioned above, there shouldbe necessary and sucient modules at the lower layer,then the learning system puts a new learning module
at the upper layer, and the module learns to coordinate
the lower modules. The upper module has a state spaceconstructed with the goal state activations of the lower
modules. A set of actions consists of the commands tothe lower modules. For example, there are three modules at lower level (say LM , LM , and LM ), then theupper module has a state space based on their goal state
activations (say g , g , and g ). Figure 7 shows an example state transition on the upper layer state space. At
the initial situation, all lower modules activate low. The
system sends a command to the module LM , then thegoal state activation of LM , that is g , goes up. After LM nishes its own task, the upper module sends
a command to the module LM , and accomplishes thewhole task by activating LM at last.
4 Experiments

The following state variables are prepared in advance:A
area of object i on the image
angle to object i from the center of image
Adi erence of areas between objects i and jdi erence of angles between objects i and j
These variables are normalized to [0 : 1]. The area andthe angle are quantized into 30 levels and 12 ones, respectively. The action space is constructed in terms of
two torque values to be sent to two motors corresponding
to two wheels.

1

1

2

2

3

3

1

1

1

1

2

3

4.1 Setting

Figure 8 (a) shows a mobile robot we have designed andbuilt. The robot has an omni-directional camera system. A simple color image processing (Hitachi IP5000)
is applied to detect the ball area and an opponent one
in the image in real-time (every 33ms). Figure 8 (b)shows a situation with which the learning agent can encounter and Figure 8 (c) shows the simulated image ofthe camera with the omni-directional mirror mounted
on the robot. The larger and smaller boxes indicate theopponent and the ball, respectively. The robot has adriving mechanism, a PWS (Power Wheeled Steering)system.

i

i

ij

ij

4.2 Learning Scheduling and Experiments

The robot receives instructions for the tasks in the order
as follows:
Task 1: ball chasing
Task 2: ball shooting into a goal without obstacles
Task 3: ball shooting into a goal with an obstacle
4.2.1 Task 1: ball chasingFirst of all, the coach gives some instructions for theball chasing task. There are the learner, a ball, the own
goal, and the opponent goal in the environment. Figure
9 shows instructed behaviors for this task. According to
the learning procedure mentioned in 3, the system produce one module LM [S(A ;  ) : G(Max ; Front )], where
S (A ;  ) indicates that the state space consists of areaof ball A and angle of the ball  from the center ofthe image, and G(Max ; Front ) indicates that the goalstate is one where A is the maximum value and  isthe front of the robot. So this module acquired the behavior of ball chasing. Figure 10 shows the constructedsystem for this task 1.
b

b

b

b

b

37

b

b

b

trajectory of robot
trajectory of balll

trajectory of robot
trajectory of balll

trajectory of robot
trajectory of balll

Figure 9: Example behaviors for task 1

trajectory of robot
trajectory of balll

Figure 11: Learned behaviors for task 1
trajectory of robot
trajectory of ball

trajectory of robot
trajectory of ballLM [ (Ab , θb ) : (M ax, F ront)]

state

sensoractionmotor

Figure 12: Example behaviors for task 2

World

Figure 10: Acquired hierarchical structure (task 1)

ule LM [S(A ;  ;  ):G(M ax; Don t care; M ax)],
where S(A ;  ;  ) indicates that the state spaceconsists of the area of opponent A , the angle of the
opponent from the center of the image  , and the difference between the angle of the opponent and the goal, and G(M ax; Don t care; M ax) indicates that thegoal state is one where A is the maximum value, is \Don't care", and  is the maximum value. Then
this module acquired the behavior of going to the intersection between the opponent and the goal avoiding
the collision. Figure 19 shows the constructed system
for this task 3. The upper module enables the robot toshoot a ball into the goal avoiding the opponent. Figure 20 shows the acquired behaviors for the task, andFigure 21 shows the transitions of goal state activations
and the selected learning module during the task accomplishment.
5 Conclusion
We proposed a hierarchical multi-module leaning system based on self-interpretation of instructions given bycoach. We applied the proposed method to our robot
and showed results of a simple soccer situation in thecontext of RoboCup.
Acknowledgment
This research was partially supported by the Japan Science and Technology Corporation, in Research for the
the Core Research for the Evolutional Science and Technology Program (CREST) titled Robot Brain Project in
the research area "Creating a brain."
References[1] M. Asada, H. Kitano, I. Noda, and M. Veloso.
Robocup: Today and tomorrow { what we haveop4.2.2 Task 2: ball shooting into a goal without
obstacles

At the second stage, the coach gives some instructions for the shooting task. Figure 12 shows example
behaviors for this task, and Figures 13 and 14 show
Qs of the learning modules during the example behavior performance before and after the addition of newmodule, respectively. The arrows on the top of eachseries indicate the behavior of the instruction given
by coach. There is no valid module during the timefrom 1.7 to 2.8 seconds. The learner produces anothermodule LM [S(A ;  ;  ) : G(Max ; Don t care; Min )]during the period, where S(A ;  ;  ) indicates thatthe state space consists of area of ball, angle of theball from the center of the image, and di erence between the angle of the ball and one of the goal, andG(Max ; Don t care ; Min ) indicates that the goal state is
one where A is the maximum value,  is \Don't care",and  is the minimum value. This means that themodule has a policy of going around the ball until the
directions to the ball and the goal become same. Figure 15 shows the constructed hierarchical system for thistask 2. The upper module coordinates these two modules to accomplish the shooting task. Figure 16 shows
the acquired behaviors for the task, and Figure 17 shows
the transitions of goal state activations and the selected
learning module during the behavior performance.
b

b

0

bog

b

b

bog

0

b

b

bog

4.2.3 Task 3: ball shooting into a goal with an
obstacle

At the last stage, the coach gives some instructions for the shooting task with obstacle avoidance. Figure 18 shows example behaviors forthis task. The learner produces another mod-

op

op

op

0

ogop

ogop

op

op

ogop

0

op

ogop

38

op

LM [shoot]LM[S(Ab,Tb):G(Max,Front)]
Qth

Learning
Module1upper layer
state

action0.6

g 1, g 2

b1,b 2

Q

0.8

0.4

0.2

LM [ (Ab , θb , θbog ): (M ax, Don t care, M in)]LM [ (Ab , θb ): (M ax, F ront)]

0

lower layer

0

1

2

3

4

5

6

state 1t [s]state 2

actionthe longest period in which new learning modules are needed

Figure 13: Availability evaluation : before the addition(Task 2)

sensor

motor
World

Figure 15: Acquired hierarchical structure (task 2)

LM[S(Ab,Tb):G(Max,Front)]
LM[S(Ab,Tb,Tbog):G(Max,All,Min)]
Qth

trajectory of robot
trajectory of ball1

trajectory of robot
trajectory of ball

0.8

Q

0.6

0.4

0.2

0

0

1

2

3

4

5

6

t [s]

Figure 14: Availability evaluation : after the addition(Task 2)

Figure 16: Learned behaviors for task 2
tional Conference on Multisensor Fusion and Inte-learned. Arti cial Intelligence, pages 193{214, 1999.
gration for Intelligent Systems (MFI2001), pages 7{
12, 2001.
[2] Jonalthan H. Connell and Sridhar Mahadevan.
[8] Steven D. Whitehead. Complexity and cooperation
ROBOT LEARNING. Kluwer Academic Publishers,
1993.
in q-learning. In Proceedings Eighth International
Workshop on Machine Learning (ML91), pages 363{
[3] Jonalthan H. Connell and Sridhar
367, 1991.
Mahadevan. ROBOT LEARNING, chapter RAPIDTASK LEARNING FOR REAL ROBOTS. Kluwer [9] M. Asada, S. Noda, S. Tawaratsumida, andAcademic Publishers, 1993.
K. Hosoda. Vision-based reinforcement learning for
purposive behavior acquisition. In Proc. of IEEE Int.
[4] Morimoto J. and Doya K. Hierarchical reinforceConf. on Robotics and Automation, pages 146{153,ment learning of low-dimensional subgoals and high1995.
dimensional trajectories. In The 5th International
Conference on Neural Information Processing, volume 2, pages 850{853, 1998.
[5] Kenji Doya, Kazuyuki Samejima, Ken ichi Katagiri,
and Mitsuo Kawato. Multiple model-based reinforcement learning. Technical report, Kawato Dynamic
Brain Project Technical Report, KDB-TR-08, Japan
Science and Technology Corporatio, June 2000.
[6] Y. Takahashi and M. Asada. Vision-guided behavior
acquisition of a mobile robot by multi-layered reinforcement learning. In IEEE/RSJ International Conference on Intelligent Robots and Systems, volume 1,
pages 395{402, 2000.
[7] Y. Takahashi and M. Asada. Multi-controller fusion
in multi-layered reinforcement learning. In Interna39

Selected learning module
LM[S(Ab,Tb,Tbog):G(Max,All,Min)]LM[S(Ab,Tb):G(Max,Front)]
LM[S(Ab,Tb):G(Max,Front)]
LM[S(Ab,Tb,Tbog):G(Max,All,Min)]

goal state activation

1

0.8

0.6

0.4
0.2

0
1

0

2

3

4

5

6

t [s]

Figure 17: Transitions of goal state activations and theselected learning module (task2)
trajectory of robot
trajectory of ball

trajectory of robot
trajectory of ballFigure 18: Example behaviors for task 3

Selected learning moduleLM[shoot]
LM[S(Aop,Top,Togop):G(Max,All,Max)]LM[shoot]
LM[S(Aop,Top,Togop):G(Max,All,Max)]

goal state activation

1

Learning
Module

0.8

0.6

0.4

0.2

upper layer
state

actiong 1, g 2

b1,b 200LM [shoot]state

actiong 1, g 2

b1,b 2lower layer

state 1

lower
layer

actionstate 2

sensorstate 3

motor
World

Figure 19: Acquired hierarchical structure (task 3)
trajectory of robot
trajectory of ball

6

8

10

12

Figure 21: Transitions of goal state activations and theselected learning module (task 3)

upper
layer

LM [ (Ab , θb , θbog ): (M ax, Don t care, M in)]LM [ (Ab , θb ): (M ax, F ront)]

4

t [s]

LM [ (Aop , θop , θogop ): (M ax, Don t care, M ax)]

Learning
Module2

trajectory of robot
trajectory of ballFigure 20: Learned behaviors for task 340

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑8 (5/2)

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

Reinforcement Learning of Parameters for Humanoid Rhythmic
Walking based on Visual Information
Masaki Ogino1 , Yutaka Katoh1 , Minoru Asada1,2 and Koh Hosoda1,2
1
Dept. of Adaptive Machine Systems, 2 HANDAI Frontier Research Center,
Graduate School of Engineering, Osaka University{ogino, yutaka}@er.ams.eng.osaka-u.ac.jp, {asada, hosoda}@ams.eng.osaka-u.ac.jp

Abstract
This paper presents a method for learning theparameters of rhythmic walking to generate apurposive motion. The controller consists ofthe two layers. Rhythmic walking is realized
by the lower layer controller which adjusts the
speed of the phase on the desired trajectory depending on the sensor information. The upper
layer controller learns (1) the feasible parameter sets that enable a stable walking for a robot,(2) the causal relationship between the walking parameters to be given to the lower layer
controller and the change of the sensor information, and (3) the feasible rhythmic walking
parameters by reinforcement learning so that a
robot can reach to the goal based on the visual information. The method was examinedin the real robot, and it learns to reach the balland to shoot it into the goal in the context of
RoboCupSoccer competition.

1

Introduction

Recently, a number of humanoid projects have started
and various kinds of humanoid platforms have been developed. The typical method for real robot adopted
in those platforms is planning the desired trajectoryof each joint based on Zero Moment Point [3, 14]. In
that method, the ZMP trajectory for not falling downis planned and the trajectory of each joint is calculated
based on the ZMP trajectory. This method needs very
precise dynamics parameters for the robot and much calculation time for planning.
The other method to realize bipedal walking isrhythmic-walking-based approach. This method doesn
not use the precise structural parameters of a robot. Instead, the controller adjusts its inherent frequency depending on the sensor information so that the entrainment between dynamics of the controller and those of environment takes place. Taga et al. proposed the model of
CPG (Central Pattern Generator) system [2] for humanwalking based on the nonlinear dynamics equations [11].
The network system changes its frequency depending on
the sensor information. In the simulation experiment,
this model realizes the stable walking under the various
kinds of disturbances [6]. In the original Taga’s CPG
model, the output value of each neuron is used as a reference of torque applied to a corresponding joint. Whilealmost all of the currently existing humanoid robots are
driven by high gain PD controllers, instead of torquecontrol. Therefore, it is difficult to apply Taga’s CPG
model to real robots directly. However, even such a robot
with high gain PD controllers can realize the stable walking with a controller which utilizes sensor information
properly. Pratt [9] realizes the energy efficient walking
in real robot with a controller which consists of statemachines. The state transition of the controller occurs
when the swing leg touches the ground. Tsuchiya et al.
[13] realized stable walking based on a method in whicha trajectory controller determines the shape of the trajectory, and a phase controller changes the speed of thedesired angle on the trajectory. In this controller thephase speed is adjusted by the sensor information.
In rhythmic walking, the control parameters are foundheuristically, not by planning as ZMP approach. This
makes it difficult to construct the upper layer controller
to control the movement of a robot because the walking parameters such as walking step are not found until
the robot interacts with the real world. Taga [12] andFukuoka et al. [4] constructs the upper layer controller
which gives the control parameters to the lower CPG
controller depending the visual information so that the
robot can avoid obstacles or climb over a step. In thesemethods, the adjusting parameters were given by the designer in advance. However, for making a more adaptive
robot to the dynamic situations, it is necessary that therelationship between the parameters of the lower rhythmic walking controller and the resultant change of theenvironment should be learned.
In this paper, the layered controller is introduced,
in which the lower controller realizes rhythmic walking
based on the controller proposed by Tsuchiya et al. [13]and the upper controller learns the parameters of the41

controller of the lower layer based on the visual information. There are three points in learning of the upper
layer controller. (1) In the first stage, it learns the feasible parameters of the lower layer controller which enables
a robot to walk. (2) To accelerate a learning process, theupper layer controller learns the model of the world : therelationship between the control parameters given to thelower rhythmic walking controller and the change of thevisual sensor information. (3) The upper layer controller
learns what parameters should be given to reach a goalby the reinforcement learning.
The rest of this paper is organized as follows. First,
the lower controller which enables a rhythmic walk is introduced. Next, we describe the upper layer controller inwhich the parameters of the lower controller is learned byreinforcement learning. Then, the suggested controller isapplied to the RoboCupSoccer task [8], ”approaching toa ball”, and experimental results are shown. Finally,
conclusions are given.

2

Rhythmic walking controller

2.1

Biped robot modelFig. 1 shows a biped robot model used in the experiment
which has one-link torso, two four-link arms, and two sixlink legs. All joints are single DOF rotation ones. Eachfoot has four FSRs to detect reaction force from the floor
and a CCD camera with a fish-eye lens is attached at the
top of the torso.
2.2

desired trajectory of joint 1 is determined by the amplitude of the oscillation, α. The desired trajectories are
summarized as following functions,
θ1
θ2
θi
θ6

2.2.1 Trajectory controller
The trajectory controller calculates the desired trajectory of each joint depending on the phase given by thecorresponding oscillator in the phase controller.
Here, the trajectory of each joint is characterized byfour parameters as shown in Fig. 3. For joints 3, 4 and
5, of which axes coincide with pitch axis, the desired
trajectory is determined so that in the swing phase thefoot trajectory draws a ellipse that has the radiuses, h invertical direction and β in horizontal direction, respectively. For joints 2 and 4, of which axes coincide withroll axis, the desired trajectory is determined so that theleg tilts from −W to W relative to the vertical axis. The

α sin(φ)
W sin(φ)
fi (φ, h, β)−W sin(φ).

(i = 3, 4, 5)

(1)
(2)
(3)
(4)

The detail of fi is explained in Appendix. Among
four parameters described above, α, which determines
the walking step length, and β, which determines thewalking direction are selected as rhythmic parametersof walking. Although these parameters characterize approximate direction and step length, resultant walking is
not as precisely determined by those parameters becauseof the slips between the support leg and the ground.
These parameters are learned in the upper layer learning module, explained in 3.
2.2.2 Phase controller
The phase which determines the desired value of eachjoint is given by the phase controller. The phase controller consists of two oscillators, φR for right leg and φLfor left leg. The dynamics of each oscillator is determinedby basic frequency, ω, the interaction term between two
oscillators, and the feedback signal from sensor information,

Rhythmic walking controller based on
CPG principle

Here, we build a lower-layer controller based on the controller proposed by Tuchiya et al. [13]. The proposed
controller consists of two sub-controllers: a trajectory
controller and a phase controller (Fig. 2). The trajectory controller outputs the desired trajectory of eachlimb depending on the phase which is given by the phase
controller. The phase controller consists of four oscillators, each of which is responsible for movement of eachlimb (Fig. 4). Each oscillator changes its speed depending on the touch sensor signal, and the effects reflectedon the oscillator in each limb. As a result, the desired
trajectory of each joint is adjusted so that global entrainment between dynamics of the robot and those of
the environment is realized. In the following, the detailsof each controller are explained.

=
=
=
=

φ̇L
φ̇R

=
=

ω − K(φL − φR − π) + gL
ω − K(φR − φL − π) + gR .

(5)
(6)

The second term of RHS in above equations keeps thephases of two oscillators in opposite. The third term,
feedback signal from sensor information, is given as follows:½ 0
K F eedi(0 < φ < φC )gi =(7)
−ω(1 − F eedi ) (φC ≤ φ < 2π)i = {R, L},
where K 0 , φC and F eedi denote feedback gain, the phasewhen the swing leg contacts with the ground, and thefeedback sensor signal, respectively. F eedi returns 1 if
the FSR sensor value of the corresponding leg exceeds
the certain threshold value, otherwise 0. The third term
enables that the mode switching between the free leg
phase and the support one happens appropriately according to the ground contact information from the FSR
sensors. In this paper, the value of each parameter is set
as follows; φC = π, ω = 5.23[rad/sec], K = 15.7, K 0 = 1.

3

Reinforcement learning withrhythmic walking parameters

3.1

Principle of reinforcement learning

Reinforcement learning has recently been receiving increased attention as a method for robot learning withlittle or no a priori knowledge and higher capability of42

reactive and adaptive behaviors. Fig. 5 shows the basic model of robot-environment interaction [10], wherea robot and environment are modelled by two synchronized finite state automatons interacting in a discrete
time cyclical processes. The robot senses the current
state st ∈ S of the environment and selects an actionat ∈ A. Based on the state and action, the environment
makes a transition to a new state st+1 ∈ S and generates
a reward rt that is passed back to the robot. Throughthese interactions, the robot learns a purposive behavior to achieve a given goal. In order for the learning toconverge correctly, the environment should satisfy theMarkovian assumption that the state transition depends
on only the current state and the taken action. The statetransition is modelled by a stochastic function T whichmaps a pair of the current state and the action to taketo the next state (T : S × A → S). Using T , the statetransition probability Pst ,st+1 (at ) is given by

CCD camera
Arm 1

Arm 2

Joint 1
Leg 1

Leg 2

Joint 2

Joint 3

Joint 4
Joint 5

Joint 6

Fsr sensor

Figure 1: Model of biped locomotion robot
Trajectory control system
Motor command
generator

Phase control system

phase
Oscillators

reference valueof PD control
Arm

Leg

FSR sensor
signalPst ,st+1 (at ) = P rob(T (st , at ) = st+1 ).

Figure 2: Walking control system

Joint 2

Joint 1

joint 3−α

joint 5hbβThe immediate reward rt is given by the reward function in terms of the current state by R(st ), that isa
rt = R(st ). Generally, Pst ,st+1 (at ) (hereafter Pss0 ) and
R(st ) (hereafter Rass0 ) are unknown.
The aim of the reinforcement learner is to maximize
the accumulated summation of the given rewards (called
return) given byαW

joint 4(8)

return(t) =∞X

γ n rt+n ,

(9)

n=0

Joint 6

b

(a)
Joint
angles aroundpitch axis

(b)
Joint
angles aroundroll axis

(c)
Joint
angle aroundyaw axis

Figure 3: Joint angles
Right arm
oscillator

where γ (0 ≤ γ ≤ 1) denotes a discounting factor to givethe temporal weight to the reward.
If the state transition probability is known, the optimal policy which maximize the expected return is given
by finding the optimal value function V ∗ (s) or the optimal action value function Q∗ (s, a) as follows. The derivation of them can be found elsewhere [10].
V ∗ (s) =max E{rt+1 + γV ∗ (st+1 )|st = s, at = a}
a
h
i
X
∗ 0
a
a
= max
P̂ss
(10)
0 R̂ss0 + γV (s )Left arm
oscillator
arm
φ2

arm

φ1

a

Right leg
oscillator

Left leg
oscillator
leg
φ2

leg

φ1

FSR

Q∗ (s, a)FSR= E{rt+1 + γ max
Q∗ (st+1 , a0 )|st = s, at = a}
a0
h
i
X
a
a
∗ 0 0
=
P̂ss
(11)
0 R̂ss0 + γ max Q (s , a )0s0Figure 4: Phase control system
st+1 : Next state

Environment

st : StateAgentrt : Reward

at : Action

Figure 5: Basic model of agent-environment interaction

3.2

s0

a

Construction of action space based onrhythmic parameters

The learning process has two stages. The first one is toconstruct the action space consisting of feasible combinations of two rhythmic walking parameters (α, β). To dothat, we prepared the three-dimensional posture space
sp in terms of the forward length β (quantized into four
lengths: 0, 10, 35 60 [mm]), the turning angle α (quantized into three angles: -10, 0, 10 [deg]) both of whichmean the previous action command, and the leg side43

(left or right). Therefore, we have 24 kinds of postures.
Firstly, we have constructed the action space of the feasible combinations of (α, β) excluding the infeasible ones
which cause collisions with its own body. Then, various
combinations of actions are examined for stable walking in the real robot. Fig. 6 shows the feasible actions(empty boxes) for each leg corresponding to the previous actions. Due to the differences in physical properties
between two legs, the constructed action space was not
symmetric although it should be theoretically.

X

X

Y

Y

(a) State space ofball(b) State space ofgoal

β [mm]

β [mm]

β [mm]

β [mm]

β [mm]

β [mm]

β [mm]

β [mm]

β [mm]

β [mm]

β [mm]

α [deg]α [deg]α [deg]α [deg]α [deg]α [deg]α [deg]α [deg]α [deg]β in previous action [mm]β [mm]

β [mm]

β [mm]
β [mm]

α [deg]α [deg]α [deg]α [deg]α [deg]α [deg]α [deg]α [deg]α [deg]β in previous action [mm]β [mm]

β [mm]

β [mm]

Figure 8: State space of ball and goaltransition model which estimates the state transitionaprobability Pss
0 through the interactions, and a reward
model (see Fig. 9). Based on DP, the action value function Q(s, a) is updated and the learning stops when no
more changes in the summation of action values.
X
0 0aQ(s, a) =Pss(12)
0 [Rs + γ max Q(s , a )],0aα [deg]α [deg]α [deg]α [deg]α [deg]α in previous action [deg]β [mm]

β [mm]

β [mm]

β [mm]

β [mm]

β [mm]

s0

where Rs denote the expected reward at the state s.
α [deg]Update policy
value fanction

α in previous action [deg]Planner(a) left leg

Dynamic
Programming

Policy value function(b) right leg

ModelState transition
model

Reward model

Behavior strategy
Update state transition model

Figure 6: Experimental result of action rule
3.3

ActionFigure 9: Learning module

Reinforcement learning with visual
information

Fig. 7 shows an overview of the whole system which consists of two layers: adjusting walking based on the visual
information and generating walking based on neural oscillators. The state space consists of the visual information sv and the robot posture sp , and adjusted action a islearned by dynamic programming method based on therhythmic walking parameters (α，β). In a case of ballshooting task, sv consists of ball substates and goal substates both of which are quantized as shown in Fig. 8. In
addition to these substates, we add two more substates,that is, “the ball is missing” and “the goal is missing”
because they are necessary to recover from loosing theirsight.
Motion modulator system
Learning module
Sensory system
ActionState

VisualsystemMotion generator system

Trajectory
controlsystemPhase
controlsystemEncoder
FSR sensor

Environment

Figure 7: Biped walking system with visual perception
Learning module consists of a planner which determines an action a based on the current state s, a state

State

4

Experiments

4.1

Robot platform and environment set-up

Here, we use a humanoid platform HOAP-1 by Fujitsu
Automation LTD. [7] attaching a CCD camera with afish-eye lens at the head. Figs. 10 and 11 show a picture and a system configuration, respectively. The height
and the weight are about 480[mm] and 6[kg], and eachleg (arm) has six (four) DOFs. Joint encoders have highresolution of 0.001[deg/pulse] and reaction force sensors(FSRs) are attached at soles. The colour image processing to detect an orange ball and a blue goal is performedon the CPU (Pentium3 800MHz) under RT-Linux. Fig.
12 shows an on-board image.
The experimental set-up is shown in Fig. 13 where theinitial robot position is inside the circle whose center andradius are the ball position and 1000 [mm], respectively,
and the initial ball position is located less than 1500[mm] from the goal of which width and height are 1800[mm] and 900 [mm], respectively. The task is to take aposition just before the ball so that the robot can shoota ball into the goal. Each episode ends when the robot
succeeds in getting such positions or fails (touches theball or the pre-specified time period expires).
4.2

Experimental results

One of the most serious issues in applying the reinforcement learning method to real robot tasks is how

44Figure 10: HOAP-1

Fish-eye lensCCD camera

to accelerate the learning process. Instead of using Qlearning that is most typically used in many applications, we use a DP approach based on the state trana
sition model Pss
0 that is obtained separately from thebehavior learning itself. Further, we give the instructions to start up the learning, more correctly, during thefirst 50 episodes (about a half hour), the human instructor avoids the useless exploration by directly specifying
the action command to the learner about 10 times per
one episode. After that, the learner experienced about
1500 episodes. Owing to the state transition model andinitial instructions, the learning converged in 15 hours,
and the robot learned to get the right position from any
initial positions inside the half field.
Fig. 14 shows the learned behaviors from various initial positions. In Fig. 14, the robot can capture theimage including both the ball and the goal from the initial position while in Fig. 14 (f) the robot cannot see
the ball or the goal from the initial position.

H8 microcomputer

Motor
DriverUSB

Motor
FSR sensor

PC(pentium3 800MHz)
OS:RT-Linux

Encoder(a) Result 1(b) Result 2(c) Result 3(d) Result 4(e) Result 5(f) Result 6

Figure 11: Overview of robot system

Figure 14: Experimental results

Figure 12: Robot’s view (CCD camera image throughfish-lens)

Goal
1800

10
00

1500
Ball
Robot

Figure 13: Experimental environment

5Concluding remarks

A vision-based behavior of humanoid was generated byreinforcement learning with rhythmic walking parameters. Since the humanoid generally has many DOFs, it
is very hard to control all of them. Instead of using these
DOFs as action space, we adopted rhythmic walking parameters, which drastically reduces the search space andtherefore the real robot learning was enabled in reasonable time. In this study, the designer specified the state
space consisting of visual features and robot postures.
State space construction by learning is one of the futureissues.
Acknowledgments
This study was performed through the Advanced andInnovational Research program in Life Sciences from
the Ministry of Education, Culture, Sports, Science andTechnology, the Japanese Government.

45

References[1]

A. Fujii, A. Ishiguro. Evolving a cpg controller fora biped robot with neuromodulation. In Climbing
and Walking Robots (2002), pp. 17–24.

[2]

S. Grillner. Neurobiological Bases of Rhythmic Motor Acts in Vertebrates. Science, Vol. 228, (1985),
pp. 143-149.

[3]

S. Kajita and K. Tani. Adaptive Gait Control ofa Biped Robot based on Realtime Sensing of the
Ground Profile. In Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems(1996), pp. 570-577.

[14] J. Yamaguchi, N. Kinoshita, A. Takanishi, and I.
Kato. Development of a Dynamic Biped Walking System for Humanoid –Development of a Biped
Walking Robot Adapting to the Human’s Living
Floor–. In Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems (1996),
pp. 232-239.

Appendix: planning the reference
trajectory around the pitch axis
Z
X
Y

[5]

[6]

[7]

[8]

[9]

H. Kimura, Y. Fukuoka, and H. Nakamura. Biologically inspired adaptive dynamic walking of thequadruped on irregular terrain. In Proc. of 9th International Symposium of Robotics Research (1999),
pp. 271-278.
M. Laurent and J. A. Thomson. The role of visual
information in control of a constrained locomotor
task. J. Mot. Behav, Vol. 20, (1988), pp. 17–37.
S. Miyakoshi, G. Taga, Y. Kuniyoshi, and A. Nagakubo. Three Dimensional Bipedal Stepping Motion using Neural Oscillators –Towards Humanoid
Motion in the Real World–. In Proc. of IEEE/RSJ
International Conference on Intelligent Robots andSystems (1998), pp. 84-89.

L1
S

L2

J. Pratt Exploiting Inherent Robustness and Natural Dynamics in the Control of bipedal Walking
Robots Doctor thesis, MIT, June. (2000).

[10] Richard S.Sutton and Andrew G.Barto.
inforcement learning:An Introduction”,
Press/Bradford Books, March, (1998).

[12] G. Taga. A model of the neuro-musculo-skeletal
system for anticipatory adjustment of human locomotion during obstacle avoidance. Biological Cybernetics, Vol. 78, (1998), pp. 9–17.

θS4

B

θ5

S

θ5

F

A

b

b

β/2

β/2

C

Figure 15: Joint angles and the reference trajectory of
the foot
The reference trajectories of joints 3, 4 and 5 are determined by the position of the foot. Let x and z be the position of the foot in the plane XZ which is perpendicular to thepitch axis, the reference trajectory of the foot is given by,
xF

=

zF

=

xS

=

zS

=

β
cos(φF ),2−H + h sin(φF ),β− cos(φS ),2−H,

where (xF , zF ) and (xS , zS ) are the positions of the foot in
the free and support phase, respectively, H is the length fromthe ground to the joint 3, β is the step length, and h is
the maximum height of the foot from the ground (Fig. 15).
When the position of the foot is determined, the angle of eachjoint to be realized is calculated by the inverse kinematics asfollows,π+ atan2(z, x) − atan2(k, x2 + z 2 + L21 − L22 )2θ4 = atan2(k, x2 + z 2 − L21 − L22 )“ReMIT[11] G. Taga, Y. Yamaguchi, H. Shimizu. Self-organized
control of bipedal locomotion by neural oscillatorsin unpredictable environment. Biological Cybernetics, Vol. 65, (1991), pp. 147–159.

θF4

hY. Murase, Y. Yasukawa, K. Sakai, etc. Design of aCompact Humanoid Robot as a Platform. In 19th
conf. of Robotics Society of Japan, (2001), pp. 789790.
H. Kitano, M. Asada The RoboCup humanoid
challenge as the millennium challenge for advanced
robotics. In Advanced Robotics, vol. 13, (2000), no.
8, pp. 723-736.

θ3

θF3

H

[4]

θ3 =

θ5 = −(θ3 + θ4 ),where k is given by the following equation,k =p(x2 + z 2 + L21 + L22 )2 − 2{(x2 + z 2 )2 + L41 + L42 }.

In this research, the value of each parameter is set as
follows; H = 185[mm], h = 8[mm], W = 13[deg], L1 =100[mm], L2 = 100[mm].

[13] K. Tsuchiya, K. Tsujita, K. Manabu, S. Aoi. An
emergent control of gait patterns of legged locomotion robots. IAV2001, pp. 271-276, (2001), pp. 271276.

46

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑9 (5/2)

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

ロボカップ小型リーグにおける協調プレー実現の一手法について
Realization of Cooperative Soccer Play by Small-Size Robots
村上和人 1 日比野晋也 2 児玉幸治 2 加藤恭佑 2 鈴木英之 1 山本浩司 1 成瀬 正 1Kazuhito Murakami 1, Shinya Hibino 2, Yukiharu Kodama 2, Kyosuke Kato 2,
Hideyuki Suzuki 1, Koji Yamamoto 1 and Tadashi Naruse 1
1:愛知県立大学 情報科学部 2:愛知県立大学大学院情報科学研究科
1: Faculty of Information Science and Technology, Aichi Prefectural University
2:Graduate School of Information Science and Technology, Aichi Prefectural University
apurobo@ist.aichi-pu.ac.jp

Abstract

２．画像処理システム

One of the typical cooperative actions is the pass play in
RoboCup small-size league. This paper presents three technical

２．１ 認識対象物

key features to realize robust pass play between robots. First one isチームを識別するために、ルールでは黄または青の直径

the high resolution image processing to detect the positions and

4cm のチームマーカーをロボット上面に装着することにな

orientations of the robots. Second one is the control algorithm toっている。ロボット同士の区別、あるいは、ロボットの向move and adjust the robots for the pass play. Third one is the

きの検出のために、必要ならば規定の範囲内で補助マーカ

mechanism to catch the ball moving at high speed. This paper

ーの装着が許されている。相手チームに影響がなければ色discusses these methods and shows the effectiveness of theに関する制限はない（ただし、白、黒は使用可能）。数、

methods by experimental results.

配置なども自由である。各チームとも形状、色、配置に工夫を凝らしているが、筆者らのチームでは Figure 1 に示す

１．はじめにような長方形パターン（105mm×16.5mm）をロボットの方向検出に、また、小さな円形パターン（1〜4 個、直径

ロボカップ小型リーグでは、実機ロボットを用いてゲームを行う[1-5]。パスプレーは単に得点の機会を増やすだけ

8.5mm）をロボットの個体識別に利用している。画像処理
システムは、これらのパターン検出を目的とする。

ではなく、ロボット間の協調動作を実現する観点からも、その実現が期待されている。

２．２ 画像処理システム

ロバストなパスプレーを実現するためには、幾つかの技

PentiumXeon 2GHz、Windows2000 の PC を使用している。

術要素がある。第一に、ソフトウェアの観点からは、ロボ高速に動くロボットやボールを検出するために、プログレットの正確な位置・方向を検出する高精度な画像処理手法

ッシブ方式のカメラ（SONY, DXC-9000）を用いている。

は欠かせない。というのも、これらの情報を検出できない、

カメラはフィールドの上方 3.0m に設置されているが、ゴあるいは、できたとしても時間がかかるようでは、決めらール部分まで含めると 3.2m の範囲をカバーする必要がある。

れた位置でボールを受け取ることができなくなるためであ

このため、広角レンズアタッチメントを装着して対処してる。第二に、相手ロボットに正確にボールを蹴り出すためいる（Fujinon, WCV-65, ×0.75）。画像入力ボード（Matrox,には、ロボットの位置・方向制御アルゴリズムも重要であGEN/X/00/STD）より取り込まれる画像のサイズは 640(W)る。第三に、高速で移動するボールを受け取るためには、

×480(H)であり、5mm/pixel の分可能である。

キャッチ機構も必要である。
本論文では、パスプレーを実現するための諸技術、すな
わち、ロボットとボール追跡が約 1.4msec で実現可能な探索領域削減手法を組み込んだ画像処理手法、パスプレーを行う 2 台のロボットの制御アルゴリズム、および、あそびを持たせることにより保持率を高めたボールキャッチ機構について述べる。以下、２．〜４．で各々、画像処理手法、
協調動作アルゴリズム、および、ロボットのハードウェア
メカニズムについて述べる。

47

Figure 1: Overview of our robot team２．３ 画像処理アルゴリズム
画像処理システムでは、チームマーカーを利用してロボ
Input Image

ットの位置検出を行い、ロボットの個体（ID）識別ならびにロボットの向きの検出にはサブマーカーを利用している。

Calculation of Search Range

画像処理の流れを Figure 2 に示す。処理概略は次のとおり

Segmentation of Colored
Region Extractionである。なお、処理の詳細は文献[6-8]を参照されたい。

Labeling

Step-1(Input Image)：プログレッシブスキャンカメラから
RGB 画像を入力する。入力画像の一例を Figure 3 に

Selection of Objects

Calc.ID’s and Directions

Generation of Position Record

Calculation of
Modified Direction示す。Figure 3(b)はロボットの周辺を拡大したものである。
Step-2(Calculation of Search Range)：前フレームの結果のObject Positions
with ID & Dirc.Info.

信頼度に基づいて探索領域を決定する。信頼度は画

Figure 2: Flowchart of image processing

像処理結果を特性づける重要なパラメータであるので、詳しくは後で述べる。Figure 4 の白線で囲った長方形領域は探索範囲である。この範囲内において、RGB 画像を YUV 表色系に変換する。探索領域の限定によって計算時間が大幅に短縮されている。
Step-3(Segmentation of Colored Region)： CMU の方法[9]を拡張した 9 色（最大 32 色まで可能）のカラー照合をStep-2 と同じ範囲で YUV 画像に対して同時的に行う。
実際に対戦が行われる会場の照明は非均一なことが(a)global vision image（b）enlarged image
Figure 3: An example of grabbed image from a global
vision camera

多く、明るさもスペクトラムも同一ではないため、色に幅をもたせている。具体的には、ボールに 2 色、それぞれのチームカラーに 2 色ずつ、フィールドから除外したい色に 3 色割り振っている。この手法により、明るさの他、フィールド上における色あいの違いも吸収するようにしている。
Step-4（Labeling）：伝播処理を利用したラベリングを行っているが、その際、ラベリング処理の最初の伝播を対角近傍にのみ行うようにしている[8]。Figure 5 に処理結果を示す。

enlarged
image

Step-5（Selection of Objects）：ID マーカーと長方形のサブマーカーを検出する。長方形の ID マーカーと円形

enlarged
image
Figure 4: Restricted region to be searched(whitened area) and enlarged imagesのサブマーカーの区別は面積によって容易に判別可能である。Figure 6 に処理結果の一例を示す。
Step-6（Calculation of ID’s and Directions）：円形サブマー
カーの個数と位置を利用して ID を識別し、ロボットの大まかな向きを計算する。精度は約 8°である。
Step-7（Calculation of Modified Directions）：Figure 7 に示

Since the noise like a straight line of width 1pixel will be

すように、長方形パターンの長辺のエッジ点列に最recognized as separated objects, it is easy to remove them by

小二乗法を適用し、ロボットの詳細な向きを計算す

simple area thresholing.

る。精度は約 1°に向上する。

Figure 5: An example of line noises to be deleted
by the proposed labeling algorithm

Step-8（Generation of Position Record）: 現在のロボットの位置情報を記録する。

Step-2 と Step-3 において信頼度という指標を用いたが、Step-9（Object Position with ID and Direction Information）:
カメラ画面の座標からワールド座標に変換する。

これは画像処理結果の信頼性をパラメータ化表現したもの

画像処理の最終結果の一例を Figure 8 に示す。

である。つまり、もし、前フレームの処理における対象物
検出（追跡）の信頼度が低い場合は、次のフレームでは探索領域は広めにとる必要がある。逆に、信頼度が高ければ、48

次のフレームでは、Figure4 に示したような限定領域内だけ

３．協調動作アルゴリズム

探索すれば十分に対象物を検出（追跡）できることになる。
筆者らのシステムでは、{non, low, intermediate, high}の 4

筆者らのシステムが備える協調プレーには、例えば、パ段階の信頼度レベルを定義し、フレームレート（1/60sec ごス、ディフェンス、アシスト、などがある。本稿では、紙と）に更新するようにしている。基本的には、もし対象物面の制約により、パスプレーのアルゴリズム概要を説明す

検出に成功すれば 1 レベル上げ、そうでなければ 1 レベル

る。パスの出し手と受け手のそれぞれのアルゴリズムは次下げる。

のとおりである。

信頼度が下がると広い探索領域から探さなければならず、

まず、変数、フラグを次のように定義する。パスの出し計算時間を要する。しかし、情報管理システムは過度に下手と受け手のロボット中心を結ぶ線を LineA とする。また、がるのを防いでいる。例えばボールが隠蔽状態になったと出し手ロボットの前方に伸びる直線を LineB とする。そして、き、このルールでは信頼度が下がりつづけるが、隠蔽状態

LineA と LineB のなす角をθとする。方向フラグ、安定フラのときにはレベル 2（intermediate-level）になるように補正

グを各々、Dir、PassCounter とする。

している。具体的な探索領域サイズは、レベル 1（highlevel）のとき 20×20pixel、レベル 2（intermediate-level）の[Initializing]

とき 30×30pixel、レベル 3（low-level）のとき 60×60pixel

Step 1. もし θ が 20 °より大きければ、回転速度 v r をであり、20×20pixel は実際のフィールドでは 10cm×10cmに相当している。本手法では 3m/sec までのボール追跡が可θ / 20 + θ / θ × 9 (cm/sec)とする。そうでなければ能である。

θ / 2 (cm/sec)とする。回転を開始する。
Step 2. ドリブル機構を作動させる。
Step 3. もし LineA 上に障害物が存在するならば、障害物の中心が LineA のどちら側か計算する。もし、それが出し手ロボットから見て左側にあるならば、Dir を 1とする。そうでなければ、Dir を-1 とする。もし、LineA 上に何も障害物が無ければ、Dir を 0 とする。

(a) the result of marker extraction(b) enlarged
image
Figure 6: The result of marker extraction[Pass Algorithm]
Step 1. [Initializing]を行う。
Step 2. もし Dir が 0 でないならば、 PassCounter を 0 とし、Step 5 へ。
Step 3. LineB に沿って 5 cm/sec で移動する。
Step 4. もし θ が 3°より小さく、かつ、ボールとパスの出し手ロボットの距離が 10cm より小さいならば、
PassCounter を 1 増やす。もし、 PassCounter が 20 よFigure 7: Calculation of modified direction by LMS

り大きく、かつ、 θ が 1°より小さいならば、キック装置を起動させる。そして PassCounter をリセットする。
Step 5. 次のタイムステップを待つ。そして Step 1 へ。
[Receive Algorithm]
Step 1. [Initializing]を行う。

Step 2. もし Dir が 0 でないなら、 LineB から Dir × 70 °の方向へ、60 と 7 × （ボールと LineA の間の距離）の小さい方の値（cm/sec）で進む。

Figure 8: Final result of image processing for thegame field

Step 3. 次のタイムステップを待つ。そして Step 1 へ。

49

４．ロボットメカニズムしている。このメカニズムを、次の 3 つの状態、すなわち、(a)衝突の瞬間、(b)定常状態になるまでの遷移過程、および、

４．１ ロボットメカニズムの概要(c)定常状態、に分類してモデル化し、解析を試みる。

連携プレーを行うためには、メカニズムの面でも、移動、シュート、ドリブルなどの命令を確実に実行できる構造に(a) 衝突の瞬間

なっていなければならない。Figure 9 に筆者らのロボットシ

Figure 10 に示す X−Y 座標系において、ローラーとボール

ステムを示す。ロボットは 3 つのオムニホイールを持ち､全の中心を結ぶ線分と水平軸がなす角をθ、ローラー、ボー

方向に移動可能である。Figure 9(a)に示すように、3 つのエンコーダー付き DC モータ（FAULHAVER）を用いている。
ギア比は 9.7:1 である。キック装置にはソレノイドを利用している（Figure 9(b)）。最大約 3m/sec のシュートが可能である。カバーを外した Figure 9(b)に見られるように、ドリブルは回転ローラーを利用してボールにバックスピンを与えることによって実現している。

ルの質量と各々の重心の速度を m R 、 m B 、 v R 、 v B とする。
また、ローラーとボールの衝突点に水平、垂直にとった x−ｙ ローカル座標系における v R と v B の成分を、各々、(vR , x , vR , y ) 、 (v B , x , v B , y ) とする。

ローラーとボールの回転がない場合の衝突をモデル化す
ると、運動量保存則より、ｙ-軸方向に、

v B' , y − v R' , y = −e y (v B , y − v R , y )(1)m B v B , y + m R v R , y = m B v B' , y + m R v R' , y(2)が成り立つ。ここで、「´」がついた変数は衝突後の値を(a) omnidirectional drive(b) appearance of our
robot
Figure 9: Our robot system表す。 e y はｙ-軸方向の跳ね返り係数である。 ｘ-軸方向についても同様に、

パスプレーを実現するためには、技術的に達成すべき 2
つの大きな課題がある。一つは、ロボットとボールの正確

v B' , x − v R' , x = e x (v B , x − v R , x )(3)

mB v B , x + mR v R , x = mB vB' , x + mR vR' , x(4)

な位置・方向の検出である。もう一つは、ボール捕捉のたが得られる。これらは、ボールとローラーの衝突を質点とめの機械的な仕組みである。前者については、２．で述べ見なした場合のモデルである。

た高速かつ高精度な画像処理システムによって解決してい実際にはローラーもボールも回転しているので、角運動る。後者については、ドリブル機構にショック吸収機構を量についても考慮する必要がある。そこで、慣性モーメン

組み込むことで解決している。コーネル大学の BigRed チー
ムのように、スプリングを用いた方法は自然であるが、筆トと角速度を各々 I 、者らのチームでは別の簡単な手法で解決を図っている。

ω とすると、角運動量保存則より、

I Bω B + I Rω R = I Bω B' + I Rω R'

ドリブル装置は、Figure 9(b)に示すように、ロボットの前面に取り付けられている。ゴム製のローラーが回転し、が成り立ち、また、衝突点では、ボールにバックスピンを与えることによりボールを引き付

rBω B = v B , x , rRω R = vR , x ,けている。ゴム製であるが、ローラーはボールを噛まない程度に硬い。硬過ぎるとボールは簡単に跳ね返ってしまう。

rBω B' = vB' , x , rBω R = vR , x'

そこでローラー取り付け部にあそびを持たせ、上方に僅かに動くようにしている。単純な機構であるが十分に衝撃を吸収できている。しかし、吸収の程度は床材にも依存する

'

(5)

(6)

となる。ここで、 rB , rR は各々、ボールとローラーの半径

ので、あそびの量は調節できるようにしておく必要がある。

である。ローラーはゴムでできた円筒状なので、慣性モー

４．２ キャッチ機構のモデリングメント I R と I B は、 I = 1 r 2 m 、 I = 2 r 2 m となる。衝
B
B
B
R
R
R
5
2

一般的に、衝撃吸収メカニズムをモデル化するためには

'

'

'

'

様々な要因があり容易ではない。筆者らのシステムでは、突の瞬間の v R ,x , v R , y , v B ,x , v B , y の解は、式 (1)〜(6)を解ドリブル装置にあそびを持たせることによって衝撃を吸収いて得られる。

50

(c) 定常状態のモデリング
Figure 13 に示すように、垂直抗力を N B 、 N R 、動摩擦θyx

係数を µ1 、 µ 2 とすると、ボールの運動方程式は、
X-direction: − µ1 N B + N R cosθ − µ 2 N B sin θ = 0

θ
mR

(7)

Y-direction: N B − mB g − N R sinθ − µ 2 N R cosθ = 0 (8)

Y
Roll

mB

X

となる。式(7)、(8)を解くと N B , N R は次のように得られる。

Ball

Game Field
Figure 10: Physical situation at a the impact

NR =µ1 m B g− ( µ1 + µ 2 ) sin θ + (1 − µ1 µ 2 ) cosθ

(9)

NB =

(cosθ − µ 2 sin θ )m B g− ( µ1 + µ 2 ) sin θ + (1 − µ1 µ 2 ) cosθ(10)(b) 定常状態までの遷移過程
衝突の後、ボール（の重心位置）は Figure 11 に示したよ
うに反射を繰り返す。もし、定常状態になるまでの遷移過程においてθが僅かしか変化しないならば、重心の動きのしたがって、ボールのバックスピンによる力 f は、みを考慮すれば十分である。詳細な解析とモデル化は今後µ 1 (cos θ − µ 2 sin θ ) m B g− ( µ 1 + µ 2 ) sin θ + (1 − µ 1 µ 2 ) cos θµ1 (1 − µ 2 tan θ ) m B g=
1 − µ 1 µ 2 − ( µ1 + µ 2 ) tan θの課題であるが、もし、 ｘ−ｙ ローカル座標系において

f = µ1 N B =e x ≅ e y が成り立つならば、モデル化は容易である。

Figure 11 に示すように、反射する角度はθ, 2θ, 3θ, .....,
nθ,........のように跳ね返る毎に増える。 ｎ 回の反射の後にπ /2 を超え、ボールはもと来た方向に返ることになる。
Figure 12 はθ＝π/4 の場合である。このときは、ボールは短時間の間に跳ね返り、もしローラーが衝撃を吸収するた(11)となり、 ∂f > 0 および f θ =0 > 0 より、θが大きくなるに∂θ
つれて、より大きな力 f が得られることが分かる。

めに図の矢印で記した方向に動けば、定常状態に移るまで

θの遷移過程において角度関係は保たれる。

mR

Y
θ

roller
3θ

ball

θ

X

NR
μ2 NR

mBg

Roller

NB

mB
Ball

2θ

μ1 NB

game field
Figure 11: Reflections of ball in the transition

Figure 13: Stable model by dribbling device

Game

５．考察
メカニカルな機構の観点から、ドリブル機構とキック機構の有効性を確認した。フィールドのカーペットの動摩擦

ballroller

係数が大きい場合、およびフィールドの壁の辺りを除き、ドリブル機構は有効に作動した。
画像処理の観点からは、実験的に精度を確認した。実験
結果の一部を Table 1 に示す。実験は蛍光灯で照明された実験室環境のフィールド上に白熱灯を 2 基追加して実際の試

θ＝π／4

合会場に近い環境を作って行なった（結果的にフィールド
面上の照度は 450〜800Lux）。
静止 ID 検出率取得実験では、ロボット 5 台をフィールド

Figure 12: An example of shock absorption at θ＝π/4上のフリーキックマーカ及びセンターに配置し、静止状態

51

で 10,000 回各ロボットの ID を取得した。実際に配置した位

画像処理の観点からは、自然光のように幅広い光スペク

置から 10cm 以上離れていれば誤認識とみなして処理結果をトルが含まれている場合、境界部分に色にじみが発生する整理した。動的 ID 検出率取得実験では、ID0 のロボットに問題があるため、光学的な色収差によるオブジェクトの誤リサージュ曲線を描かせ 10,000 回ロボットの位置を取得し、検出への対処が必要となる。また、スポットライトのよう

そのデータを解析することによって認識率を計算した。位に、明るさのダイナミックレンジが広すぎると画像処理が置取得精度測定実験では、フィールド上の各フリーキック破綻するため、今後は明るさの変化や種々の光源に対して

マーカ、センター、ペナルティーキックマーカの 9 点におよりロバストな画像入力システムに改良する必要がある。

いて、静止状態でロボットの位置を取得し、その変位から行動計画の観点からは、前もって敵の戦略を知ることが最大誤差を得た。角度取得精度測定実験では、上述した 9

できないため、短時間で敵の行動パターンに柔軟に対応で個所の地点において、それぞれの点でロボットを 0°、

きる戦略が必要となる。敵の行動パターンを学習して弱点

45°、90°、135°のそれぞれの方向に向け、それぞれを分析するシステムの組み込みが課題である。

1,000 回ずつ計測を行い、その変位から最大角度誤差を得た。

ソレノイドを用いたキック機構は、現在、一定の強さのここで、フィールド上の位置や角度による特異な差は特にシュートしか放てない。パスを確実にするためにも、キッ認められなかった。処理速度測定実験では、フィールド上クの強さを可変にすることが必要である。今後、ソレノイにロボット 10 台、ボール 1 個がある状態で画像処理システ

ドに与えるエネルギーを変化させることによって、キック

ムのみの速度を 1,000 回計測し、その平均を得た。

に強弱をつける方式に改良する予定である。
現在、筆者らのロボットの最高速度は 1.2ｍ/sec であるが、ボール、チームカラーマーカー、サブマーカーなどの検出対象物の認識率は、実際のゲーム中のデータを基に評価

4 輪に増やしてロボットの高速化を図っている。障害物回した。ルールでは 700Lux〜1000Lux と規定されているが、避、経路生成法、行動生成法などのソフトウェア的な改良、現実的にはこの値から外れる場合もある。また、フィール

および、ハードウェアとソフトウェアのバランスの検証もド上の位置によっても変わり得る。筆者らのシステムは、

今後の課題である。

200Lux の照明環境下でも動作することが確認できている。

参考文献

画像処理システムは、ゲーム開始直後、ある期間完全に隠蔽状態になった場合、およびボールのシュート速度が[1] http://www.robocup2002.org/

5m/sec を超えた場合に全画面探索を行う。全画面探索を行[2] M.Veloso, E.Pagello, and H.Kitano (Eds.)：”RoboCup-99：

った場合でも、処理時間はおよそ 20msec/frame である。探RobotSoccerWorldCupⅢ”, Springer (June 2000).

索範囲限定を行う場合はおよそ 1.4msec/frame である。した[3] P.Stone, T.Balch and G.Kraetzschmar (Eds.) ： ”RoboCup

がって、ロボットの陰からボールがシュートされるような

2000:Robot Soccer WorldCupⅣ”, Springer (March 2000).

場合にも十分に対処可能である。

[4] A.Brik, S.Coradeschi, and S.Tadokoro (Eds.) ： ”RoboCup
2001:Robot Soccer WorldCupⅤ”, Springer (March 2002).

Table 1 Experimental results of image processing performance
Experimental item
ID recognition ratio
in a still mode [%]ID recognition ratio
in a dynamic mode [%]Maximum deviation
for the position [cm]
Maximum deviation
for the angle [deg][5] G.A.Kaminka, P.U.Lima and R.Rojas (Eds.) ： ”RoboCup

Planned
100.00Result99.68

2002:Robot Soccer WorldCup Ⅵ ”, The 2002 International
RoboCup Symposium Pre-Proceedings, Fukuoka, (June 2002).

100.0099.61[6] S.Hibino, Y.Kodama, T.Iida, K.Kato, S.Kondo, K.Murakami,

0.50

0.097

1.00

0.78

and T.Naruse：”System configuration of RoboDragons team in
RoboCup small size league”, Proc. of SI2002, Kobe,(Dec.2002).
[7] Y.Kodama, S.Hibino, K.Murakami, and T.Naruse ： ”Small
Robot Detection by Using Image Processing and its Application

６．まとめ

to Action Planning and Action Analysis”, Proc.of MIRU2002,
Vol.1, pp.223-228, Nagoya, (July 2002).

本稿では、ロボカップ小型リーグで複数のロボットが協[8] S.Hibino, Y.Kodama, Y.Nagasaka, T.Takahashi, K.Murakami,

調動作を行う例としてパスプレーを取り上げ、それを実現

and T.Naruse ： ”Fast image processing and flexible path

するためのロボットの制御アルゴリズム、キック機構とドgeneration system for RoboCup small size league”, The 2002

リブル機構、および、高速かつロバストな画像処理アルゴ

International RoboCup Symposium Pre-Proceedings, pp.45-57,

リズムについて紹介した。ロボットに対する画像フィード

Fukuoka, (June 2002).

バックシステムの動作を 1/60 秒ごとに行うことにより、[9] Bruce, J., Balch, T. and Veloso, M.: “Fast and Inexpensive

3.0m/sec のボールに反応できる高速な画像処理を実現した。

Color Image Segmentation for Interactive Robots”, Proc. of
IROS ’00, pp. 2061-2066 (2000).

52

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑10 (5/2)

An architecture that uniﬁes virtual and real environment
Kentaro Oda, Takeshi Kato, Toshiyuki Ishimura, Takeshi Ohashi
Dept. of Artiﬁcial Intelligence, Kyushu Institute of Technology

ken@mickey.ai.kyutech.ac.jp

Abstract
Development in real multi-agent system likerobotic soccer in the RoboCup leagues is ineﬃcient because of real world uncertainty. In
this paper, we introduce an architecture we developed in the Sony Four-Legged League 2002.
This architecture designed to unify the real andvirtual environment to accelerate multi-agent
system development and scientiﬁc research forthe communities not only for the legged league
one. The architecture consists of the abstraction layer, common communication protocol,
communication hub, and simulator named open
robot simulator. We implemented it with standards Java/XML technologies.

1

Introduction

Development in real multi-agent system like robotic soccer in the RoboCup leagues is ineﬃcient because of realworld uncertainty. Considering environment changes,
for example, the changes of the lighting condition affect robot’s behavior seriously in general. In this case,
it is diﬃcult to ﬁnd out where the problem occurred problems in vision module or planning module and soon. In order to locate the problem, generally, we debug
the target system with the introduction of monitoring
facility like logging. After ﬁxing the system, But how
we can verify whether the problem is ﬁxed. Reproducing the exactly same situation is almost impossible inreal world because of sensory noise. In multi-agent system, obviously this problem becomes more complex. To
focus on scientiﬁc problem, we must distinguish a discovered problem is just a programming error or an inherent
one. As a matter of the fact, we experienced a situation in which a programmer discovered an odd robot
behavior and convinced the problem is ﬁxed with consuming 10 hours, but actually the modiﬁed source code
had not been compiled at all. This clearly shows that
how real world development is unreliable and uncertain
one. In the previous case, later we found the problem

is in the vision code through real-time monitoring. AI
oriented simulators like SoccerServer [Noda, 1998] may
not help in this case. Here, it is necessary that a development environment unify both simulation and realenvironment. With uniﬁed environment, not only we
can run the same robot program on a real robot andvirtual simulated robot, the same monitoring tool canbe used for both environments. This may accelerate thedevelopment and scientiﬁc research.

2

Architecture Design

The main goal of proposed architecture is to unify thetwo environments - real and virtual (simulated) environment. With this abstraction, the same robot program
can be run under the simulated and real environment.
To introduce this abstraction, we prepared the environment abstraction layer on the top of robot dependent
API such as OPEN-R and our virtual robot API. Before
illustrating a speciﬁc part of proposed architecture, wegive the policy of overall our architecture as follows.
• Openness - each part of the system must be expandable to introduce new robots, new planning strategy,
new color models, new collision detection module,
new image processing module, etc.
• Distribution in a Network - Since individual robots
exist distributed in a physical space, the architecture must support distribution in a network.
• Rich Information - Provide rich information not
only for programmers but robots as much as possible in arbitrary abstraction level, to facilitatingmachine learning, debug, coordination strategy etc.
For example, information from a joint angle to an
exact global position (x, y, θ) in a virtual soccer ﬁeld
is necessary.
• Rich Debugging Facility - debug supporting functionalities such as taking a snapshot of virtual / realenvironment which contains overall information, nointerruption of disconnection/connection of agentsetc are necessary.

53• Heterogeneous Architecture - dependency on speciﬁc OS, programming languages, communication
protocols must be minimized.

root
Robo0
robot
head
tilt

• Minimize the Requirements - requirements migrating existing programs to this architecture must be
minimized.

value
pan
value
visionUnder this policy, we developed the architecture andimplemented it with standard/open technologies such
Java and XML.

yuvImage
leftLegsystemrgbImagerightLeg

frameCount

3

Proposed Architecture

event
collision

The main idea to unify the both real and virtual environment is the introduction of an environment abstraction
layer, a common communication protocol, commucation
hub and a vision-based simulator. We also developed themonitoring tool to visualize local information acquired
from virtual and real robots. Fig. 1 shows an example of conﬁguration both virtual and real robots resides
on at the same time. In this conﬁguration, the virtual
robot can be simulated in the simulator, but also withthe simulator, the real robot can be visualized so as toits estimated position is reﬂected to the virtual environment. This allows us simulate the environment based onsynthesized values and real-time sensory values. After
this section, we illustrate the each part of the architecture.

running under Linux,
FreeBSD etc.

3D Models
Effector
SensorCamera• Snapshot: The hub also can take a snapshot of its
contents. The snapshot is XML formatted so that
programmers can modify and export. Fig. 3 gives
an example of the XML output result.

Agent
ProgramEnvironment
Abstraction Layer

CoreEngine

Communication
Hub

Middleware

SharedInformation

Monitor Tool

EventManager

Middleware

The same
programSony ERS-210
Robot

Visualizer
Middleware

TablesAgent
Program

Logging
Environment
Abstraction Layer
Read/write operations.
Middleware

Send/Listen events.

MW

OPEN-R

Figure 1: The Architecture Overview

3.1<?xml version="1.0" encoding="UTF-8" ?><Environment version="0.1" xmlns="http://www.asura.ac/xethereal">
䇭<Leaf name="/Robo0/robot/head/tilt/value " type=“double " scalar="true "><i>32.5</i></Leaf><Leaf name="/Robo0/robot/head/pan/value" type=“double " scalar="true "><i>11.4</i></Leaf><Leaf name=" /Robo0/robot/leftLeg" type=“double " scalar=“false“ length=3><i>1.5</i> <i>131.4</i> <i>231.1</i></Leaf>….
</Environment>

Figure 3: An Example XML Output of Environmental
Information

Virtual Robot

Simulator

Figure 2: A Tree Representation Example of Environmental Information

Communication Hub

The communication hub holds whole environmental information including from each robot’s estimated positionin the soccer ﬁeld to camera images generated / acquired
through the simulator or a real robot camera.
• Tree structured: Environmental information is provided as external representation so as to programmer can get information user friendly: it is tree
structured as shown in Fig. 2.

• Dynamic connection/disconnection of clients: Thisis one reason why we introduce the hub. In development cycle, we frequently kill/run the clients. Using
this hub, the system can continue the execution regardless of disconnection because the last state of arobot is still hold even if it was crashed.
• Dual Communication: We provide two communication mechanisms - one is synchronous operations: read() and write() operations to the tree.
These operations are fairly simple. To read valueon the path name of /robot1/camera/yuvImage isread("/robot1/camera/yuvImage"). It returns abyte array container. To gain the performance,bulky versions of these operations are provided. The
other is an asynchronous event mechanism which
supports send and listen event operations. All
events must be sent with a string label to address
the contents. The event receiver can set a ﬁlter
to receive interested events and reduce bandwidthby specifying a regular expression. Only events
matches the regular expression can be received.
A communication pattern may be used in common is
like that 1) a client receives an update event, and 2) is-54

sues read() operations to get its interested nodes, 3) send
an ﬁnish read event. 4) After receiving the ﬁnish read
event, a client who wants to write data start to write
the nodes through write() operation. After that, 5) it
sends an update event. The tree held in the communication hub works as a shared memory. Asynchronous event
mechanism can be used as a synchronization mechanism
between data producer and consumer.
3.2

The Environment Abstraction Layer

The Environment Abstraction Layer (EAL for short) is
provided for two purposes. One is to hide details on aunderlying layer and the other is to give an illusion of amodeled environment. An example of the modeled environment is the Sony four-legged league soccer environment. Fig. 4 shows an example of classes for which anagent program interacts with the modeled environment.
This layer may be designed in an application speciﬁcway. It lies on the top of the platform dependent API
layer such as OPEN-R API and middleware for communication. The responsibility of this layer is to correctly
map the operations of a modeled environment to one inits underlying layers. For example, an implementationof the EAL in the simulated agent may become a set ofcode invokes the communication hub with read()/write()and send() event operations to reﬂect its environment information correctly. On the other hand, while providing
the same interface for an agent program, the EAL inSony ERS-210 actually responsible for getting information through image processing, self localization, locomotion modules etc. Thus, the EAL deﬁnitely deﬁnes the
mapping of a modeled environment to actual information sources/consumers. Implementation of this layer isapplication speciﬁc and user responsibility.

3.4

Simulator

The simulator is designed as vision based simulation.
This means that the simulator takes the several control
values as inputs and generates a synthesized image as an
output. These input and output comes in/out from thecommunication hub through accessing middleware. Fig.
5 shows a snapshot of running the application. It consistsof global, command line, tree, and local camera views. In
our implementation, the simulator takes ﬁve odometory
control values like forward[cm/cycle], left[cm/cycle], rotate[degree/cycle], and tilt-head[degree/cycle] and panhead[degree/cycle] from an agent. Virtual robot acquires
the synthesized image from the communication hub andsends back these control values. Accordingly, the simulator, communication hub and virtual robot forms loop
in simulation. This simulator has several useful features- plugin support, lisp like simple scripting, several views
etc.

Reperesents a soccer field
AbstractEnv

SoccerObject

getSelf()
getBall()
getEnemyDog()
getTeamateDog()
getTargetGoal()
getOwnGoal()….

getX()
getY()
getDistance()
getVisionInfo()
getSensorInfo()..

Class name

1:n

1:1

1:1
Reperesents an object in thesoccer field – like goals,
ball, enemy robots..

Method1()
Method2()
Method3()..

getHeadPan()
getHeadTilt()
getRange2Obstacle()….

VisionInfo
getAreaOfBlob()
getConfidence()..

Relatively low-level
information – created fromimage processing moduleand many sensors.

Figure 4: An Example Classes Diagram of The Environment Abstraction Layer

3.3

Figure 5: A Screen Snapshot of The Simulator

SensorInfo

Middleware

The middleware provides the interface of read()/write()and sendEvent()/receiveEvent() operations. The middleware implementation encapsulates ﬂoating point representation and byte ordering. At this time, Java andC++ version of middleware is implemented.

4

Implementation

To implement the communication hub, simulator andmonitoring tool, we use Java, Java Advanced Imaging
API and Java 3D API. For generating/parsing XML
ﬁle in the communication hub, we use the SAX parser.
For an agent programming we use C++ and partiallyscheme, a lisp dialect. The agent program can be run
both Sony ERS-210 platform and Linux and FreeBSD
with gcc.

5

Conclusion

With this architecture, we convince successfully introduce heterogeneity by using standard Java, distribution in a network with TCP/IP, minimized the requirements through simple communication operations, providing rich information through the tree structured external representation, openness with communication hub
and plugin facility in the simulator and rich debugging
facility with the communication hub.

55

In the four-legged league in RoboCup 2002, our system
had not been implemented. Now we have a good fundamental to experiment new planning and coordination
strategy and so on. At this time, the primary implementation has been done. As a future work, we have toevaluate the system in practical. In particular, the eﬀectiveness of combining information real and virtual robot
have to be evaluated.
The authors would like to express our gratitude to
the Information-technology Promotion Agency (IPA),
Japan for sponsor of this project and Professor Takaichi
Yoshida for supporting.

References[Oda, 2002] Kentaro Oda, Takeshi Ohashi, Takeshi
Kato, Toshiyuki Ishimura, Yuki Katsumi: The
Kyushu United Team in the Four Legged Robot
League in RoboCup 2002 Robot Soccer World Cup
VI, page. 452, 2002.
[Noda, 1998] Itsuki Noda, Hitoshi Matsubara, Kazuo
Hiraki, Ian Frank: Soccer Server: a tool for research on multi-agent systems, Applied Artiﬁcial
Intelligence 12, pp.233-250, 1998.

56

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑11 (5/2)

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

An Open Robot Simulation Environment

Toshiyuki ISHIMURA, Takeshi KATO, Kentaro ODA, Takeshi OHASHI

Dept. of Artiﬁcial Intelligence, Kyushu Institute of Technology
isshi@mickey.ai.kyutech.ac.jp

Abstract
Nowadays various kinds of robots are publicly available such as AIBO, ASIMO and soon. However, the development of robots isstill diﬃcult because of their complexity, continual changes of environments, limitation of
resources and so on. To solve this problem,
robot developers often use the simulator thatallows to program and test robots’ program effectively in the ideal environment where speciﬁed conditions can easily be reproduced. It is
still diﬃcult to realize the simulator regardlessof its usefulness, because the cost of simulator
implementation seems the unexpected cost in
the development of robots. To overcome thisproblem, it is need to realize the open robot
simulation environment in which any kind ofrobots can be simulated. This paper focuseson vision-based robot simulation environmentand describes a method to construct it. Finally,
we implemented a simulator for Robocup Sony
4-Legged League by this method.

1

Introduction

Nowadays various robots are publicly available such as
AIBO, ASIMO and so on. However, the development ofrobots is still diﬃcult because of their complexity, continual changes of environments, limitation of resources andso on. Considering environment changes in vision-based
robot, for example, the changes of the lighting conditionaﬀect robot’s behavior seriously. To clear problems therobot’s strategies in the real environment, it is need tocheck strategies in exactly same environment, because ineach testing time sensory values such as camera images
and the eﬀectors will change.
To solve this problem, there are the robot simulatorsthat are categorized two types; one aims to simulate therobot mechanical behavior with accurate robot model
data, the other aims to simulate the vision of the robot
in order to test robot strategy. The simulator allows developers to program and test robots’ program eﬀectively

in the ideal environment where speciﬁed conditions caneasily be reproduced. It is still diﬃcult to realize thesimulator regardless of its usefulness, because the costof simulator implementation can be seen the unexpected
cost in robot development. To overcome this problem,
it is need to realize the open robot simulation environment in which any type of robots can be simulated. This
paper focuses on vision-based robot simulation environment and describes a method to construct it. The next
section describes concept of open robot simulation environment. Section 3 shows design of architecture. Section
4 shows an implementation of the simulator for Robocup
Sony 4-Legged League. Finally, section 5 concludes witha discussion of our method.

2

What is Open Robot Simulator

The purpose of our simulation environment is to improve the eﬃciency of the development of vision-based
robots’ strategies in particular. When testing the robot
strategy by simulation, each developer would prepare thesimulator in which accommodate a single kind of robot.
However, each simulator has something in common suchas synthesis of the camera image, eﬀector simulation,
3D object management and so on. Thus, we provide
a general simulation environment to simulate any kindof robots and customize according to any testing condition. To archive this environment, we give the policy as
follows:• Openness that means the simulator reveals itself torobot developer• Reproducibility of simulation• Minimum modiﬁcation of robot program• Useful test and monitor tool
The ﬁrst one is our main subject. With high openness,developers can manipulate the simulation environment
easily to treat various kinds of robots and customize it
according to real environment. Second, reproducibilityof the simulation environment is very important in order

57

SimServer
3D Models
Effector
SensorCameraCommunication Hub
Write

Read
Environment
Abstraction Layer

Notification

Notification
EventManager

CoreEngine

Send Event

Send Event
Middleware

Agent
Program

Write

SharedInformation

Read

ClientMiddleware

Middleware

Network(TCP/IP)
Figure 1: The Simulation Environment Architecture
robot

to test the robot strategy correctly because real robot always aﬀects the change of the environmental condition
such as lighting condition. In development cycle of robot
strategy, robot developers would repeat coding and testing of programs. When developers ﬁnd out problems incertain situation, the simulator must support to reproduce that situation in short time. Third, to reduce thecost of simulation, the modiﬁcation of robot’s agent program must be minimized when migrating between realrobot and the simulator. Finally, it is important thatrobot developers are able to monitor any information in
the simulator to test the robot strategy eﬀectively.

3

head
tilt
value
range
pan
value
range
cameraresolution
rgbImagefrontLeftLeg
frontLeftShoulder
frontLeftKnee

System Design

frontRightLeg

Figure 1 illustrates our system architecture, which
adopts client/server model and introduces two servers
as follows:

Figure 2: An example of object structure

SimServer manages all objects in the virtual environment and synthesizes virtual camera images andsimulates the robots’ eﬀector.

Eﬀector keeps current value and the range of value. It
also can hold any sub-eﬀector and camera as children.

Communication Hub manages communication between the SimServer and clients and can capture
messages through it.
In this model, multiple heterogeneous robot agents implemented in various program languages can participate
to this environment because each client lies on the common communication middleware and connects the Communication Hub via the TCP/IP network. If the simulation environment communicates with real robots, it
can accommodate both real and simulated robots in thesame simulation environment. To reduce the cost of realization of the simulator, our simulation environment
provides a class library of fundamental component asfollows:
Robot holds cameras, eﬀectors and its position and orientation.
Camera holds parameters such as view angle, resolution and so on, synthesized images by the Core Engine.

They are implemented with opened interface in orderto operate easily. The SimServer always watches information of each object then updates the virtual environment. This library allows users (i.e. robot developers)
to construct the virtual robot by few steps; preparationof robot 3D shape model data, combination of several
objects according to each real robot, adjustment of object parameter such as camera resolution and the range
of eﬀectors, and corresponding to model data.
The SimServer manages all objects in tree structure
and provides name space according to that structure.
The robot’s agent program and developers can access all
objects and its all attribute information by that name.
Figure 2 shows a part of object structure that represents
Sony ERS-210. In this structure, an agent program accesses the head camera image to indicate its name likes/robot/head/camera/rgbImage. This increases openness of the simulator and allows developers to test the
robot strategy with the ideal information such as thelocation of robot. To customize the simulation environ-58

Global View
Command Line

Virtual Environment Tree

Camera View
Figure 4: The overview of the SimServer(let(set /Ball/loc/x(plus /ribo0/loc/x(/ (dist /robo0 /robo1) 2)))(set /Ball/loc/y(plus /ribo0/loc/y(/ (dist /robo0 /robo1) 2))))

Figure 3: An Example of script language

ment dynamically, any object in the SimServer can beappended and removed in runtime.
The Communication Hub supports synchronous andasynchronous communication to provide ﬂexible communication. The SimServer and clients usually communicate by asynchronous operation (i.e. read/write) to improve communication performance. The event manager
provides synchronous commutation by event sending andnotiﬁcation if needs to synchronize any information. The
clients can connect and disconnect to the Communication Hub at any time in order to help development ofstrategy program and to provide fault-tolerance. Even if
the client is disconnected, the Communication Hub andthe SimServer keeps all information about the virtual
robot. Consequently, developers can continue to examine the robot program in the same situation after ﬁx

problems.
Functionality The following functionalities enhance
our simulation environment: plug-in user module, ascript language, persistence of simulation environment
state, communication among the agents and visualization of view frustum.
First, developers can insert fragment of program as
plug-in module to the virtual robot in order to customize
its behavior. This allows us to realize strange camera
image and reduction of eﬀector speed. Naturally, thesemodules can be appended and removed in runtime.
Second, to provide interaction between developers andthe simulation environment, a script language likes the
S-Expression is introduced. By using this language, developers can access overall object and its attribute information. It is possible to adjust the simulation environment such as lighting condition, simulation speed
and so on. Figure 3 shows an example code to placea ball between two robots (named robo0 and robo1).
This functionality allows us to test the robot’s strategy
in the exactly same environment because the simulator
can reproduce it repeatedly.
Third, the Communication Hub can store simulation
environment state to a ﬁle in order to reproduce a certain
situation. To this, the Communication Hub watches any
information through it. After storing the ﬁle, developer
ever reproduces that situation in any time.
Forth, the Communication Hub provides communication among the agents. With this functionality, it ispossible to develop a strategy to collaborate the agents
without using the real robots.

59

Fifth, when using the active camera, enhancement ofcamera motions is important to recognize the virtual environment. The simulator provides functionality to visualize the view frustum that each of the cameras is now
seeing. This visualization is useful in order to tune-up
camera motion.

4

Implementation

First, we implemented the SimServer and the Communication Hub in Java and Java3D[Java3D]. The SimServer
shown Figure 4 consists of four components; global view,command line panel, the tree view, camera views. On
the global view, user can change own view by mouse operations. The command line panel allows us to interact
with the simulator by the script language described in
the above. The tree view shows information about all
objects in the simulation environment. We also implemented a library for communication between the server
and the client, which supports C++ and Java.
Second, to evaluate our method, we implemented asimulator for the Robocup Sony 4-Leggued League on
this environment. Then we succeed in migration fromreal robot’s agent program [Oda,2002] to the simulator
with a little bit modiﬁcation. By using robot communication functionality of the Communication Hub , thissimulator can simulate communication between robots
instead of wireless LAN.

5

Conclusion

On the vision-based robot simulator, it is important to
reduce cost of robot strategy programming. To achievethis, we proposed the open robot simulation environment
to accommodate any kinds of robots. In this paper, it
has been yet considered physical eﬀects in simulation,nevertheless, we plan to introduce simple method by using collision detection.
The authors would like to express our gratitude to
the Information-technology Promotion Agency (IPA),
Japan for sponsor of this project and Professor Takaichi
Yoshida for supporting.

References[Oda,2002] Kentaro Oda, Takeshi Ohashi, Takeshi
Kato, Toshiyuki Ishimura, Yuki Katsumi, The
Kyushu United Team in the Four Legged Robot
League, in Robocup-2002: Robot Soccer World
Cup VI, page.452, 2002
[Java3D]Java

3D(TM)

API

Home

http://java.sun.com/products/java-media/3D/.

60

Page.

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑12 (5/2)

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

並列シナリオ記述を用いた RoboCup-Rescue Civilian の動作記述
篠田 孝祐 1,2 , 野田 五十樹 1,2,3 , 國藤 進 2
1
サイバーアシスト研究センタ, 産業技術総合研究所,
2
北陸先端科学技術大学院大学
3
さきがけ研究 21, 科学技術振興事業団.

Abstract

効率的な問題解決プロセスに焦点がおかれてきた．

A framework to describe behaviors of civilian

したがって，そこで開発された記述言語では，明確

agents in RoboCupRescue simulations is proposed.
In a disaster situation, it is hard to model civilian’sに定義された問題空間における最適な行動モデルのbehaviors as logically. Furthermore, we model the
behaviors by “Scenario”. In the proposed frame-

心的課題であった．このような行動記述モデルは，

work, the behaviors are divided into multiple scenarios for each goal, in which behavior-rules are

合目的的な最適行動プロセスの解明やエージェント

grouped based on situations where the rules areactive.

シミュレーションでは一見無駄に思える寄り道した獲得や専門家の振舞いを獲得する過程の分析等が中
災害時の避難経路演習シミュレーション等のようにの行動記述を対象としている．しかしながら，社会という行動が自身や他の主体に影響を与え新たな現象を誘発する可能性がある．よって，社会シミュ

1

大規模社会シミュレーションにおけるエージェントモデル

レーションにおけるエージェントには，最適行動プ
ロセスの表現と同時に，合目的的には整理できない
多様な振舞いも容易に記述できる行動記述の枠組み

大規模社会シミュレーションは，災害救助や経済活が必要とされる．

動など問題空間を論理的かつ明示的に表現することが困難な領域を対象としている．そのような領

また，人間の振舞いは多様であり，それを再現す

域を分析するための実証手法として，エージェント
ベースシミュレーションは一般的になりつつある[3,るエージェントの行動は複雑になりやすく，必要と10]．社会シミュレーション上にて動作するエージェ
ントを作成する場合，その社会を構成する要素のモの増加はエージェントの行動決定に必要な計算時間

デルおよび振舞いの定義は重要な問題である．特に，の増加は，現実的な時間でのシミュレーションの観主要素である人間の行動は多様であるだけでなく，点から重要な問題である．さらに，社会シミュレー

集団となることでより複雑な様相を示す．エージェ

ションにおけるエージェントの振舞いは．エージェ

ントの振舞いを規定する行動記述モデルは，シミュントの本体の設計とは別に行動設計者としてのシナレーションの価値を左右する問題と言える．

リオライタにより設計されることが多い．シナリオ

される行動ルールの数は増加する．行動ルール数
コストの増加もたらしやすい．この計算時間コスト

社会シミュレーションにおけるマルチエージェン

ライタによるエージェントの行動設計には，より簡トの意義とは，単なる一要素でしかない個々のエー

単な行動を表現するルールからテストを重ね，徐々ジェント同士の相互作用から創発されるマクロ事に大きなルールを作り上げていけるプロトタイピン

象を再現する点にある．従来の人間やロボットなどの行動記述に関する研究 (Soar[16, 13], ACT-R[1,グの形が適切だと考える．よって，エージェントの

2], RAPs[4, 5]など) では，特定の行動目標に対する加が容易な行動記述が必要である．

行動に関してプロトタイプイングのための変更・追61

2

並列シナリオ行動記述

2.1

行動記述モデル成に至る行動の段階を状況で切り分け，それら状況の遷移という形で表現する．
避難行動:想定される状況

人間の行動は，知的であり多様であるだけでなく，

家の中

移動途中
目的地到着

家の外

集団となることでより複雑な様相を示す．そして，その振舞いは必ずしも合目的的に整理できるとは限状況の遷移

状況:家の中TV，ラジオをつける

らない．社会シミュレーションにおいて人間が示す

ガス栓を閉じる

家の中

移動途中

外に逃げる

様々な現象を適切に再現するためには，人間の多様地図で避難場所を確認

な振舞いを的確にそして容易に設計できるエージェ

家の外

目的地到着

Figure 1: The example of scenario-chart

ントフレームワークが必要である．大規模社会シ
ミュレーションにおいて，人間の行動をモデル化す

また，エージェントの行動全体については複数のるためのエージェントフレームワークに求められる目的の達成や習慣を同時に行なう様子は，複数のシ要素として，我々は以下の 3 点に着目する．

ナリオを同時に実行することで実現する．本研究で(1) 熟考型行動と反射型行動の両方の特性を持つ行動
モデル(2) 軽量実行は，このように複数のシナリオの並列実行を目的と(3) 変更，追加が容易な行動記述モデル

2.3

これらの点を実現するために，本論文ではシナリ(2) の軽量実行に関してシナリオベース記述では，シナリオにて長期的プランに基づく行動を状況のオと呼ぶ行動ルールの集合を導入する．

2.2

シナリオベース行動記述(1) の行動モデルに関して，社会シミュレーション
におけるエージェントの行動は，環境の変化に応じた反射型行動から，長期的なプランをもつ熟考型
行動まで多岐にわたる．エージェントの行動モデル
は，従来，反射型プランニング[4, 2]や熟考型プラン
ニング[13]として表現されてきた．一方で，社会シ
ミュレーションで扱う人間の行動は，長期的プランをともなう行動であっても熟考の上での行動というよりは，特定の目標の達成に必要な行動プランや習慣としての行動パターンをあらかじめ知見として持ち，それを状況に合わせて再現しているとみなせる．
よって，社会シミュレーションにおけるエージェン
トの行動をモデル化には，長期間にわたる一貫性を持った行動を表現が容易である熟考型と，多様な環境への対処が容易である反射型の両者の特徴をもつ行動モデルが適していると考える．本研究では，行動プランや習慣としての行動パターンをシナリオとする行動記述の枠組みを並列シナリオ記述と呼ぶ．
シナリオによる実行及び記述の効率化

時間的遷移として事前に展開することで表現する．
これにより，熟考に要する環境の同定やプランの展開などにかかる計算時間コストは最小限に押さえられ，行動決定を一段の推論として行なうことができる．さらに，並列シナリオ記述の枠組みにおける状況遷移の直接的操作をシナリオ作成の段階から行なうことで状況に適したシナリオのみが起動される．
この操作により，エージェントの行動決定に必要な評価の対象となる行動ルール数を小さく保つことができ，結果として行動決定モジュールは軽量に実装することが可能である．
さらに，(3) の行動記述モデルに関しては，状況遷移を意図するシナリオの追加や削除の操作を明示的に記述することにより，新たな行動の追加や変更を行なうことが容易になると考える．エージェントに新しい行動を追加するには，シナリオとして作成した後，避難行動のシナリオに組み込む．そして適切な状況にてシナリオを起動するように追加する．

3

エージェントフレームワークのシナリオに基づく行動記述をシナリオベース行動

3.1

Posit: Part Of SITuation

記述と呼ぶ．
シナリオベース記述では，特定の目的の解決や習Posit は，特定の目的を解決するシナリオの途中段
階を状況として切り出したものである．この Posit

慣を表わす一連の行動をシナリオとして表現する．

間の遷移により，シナリオにおける目的達成の過程

そのシナリオでは，Figure1 が示すように目標の達を表現する．各 Posit は，対応する状況で適用可能

して記述し，人間の行動をシナリオに基づいてモデル化することで人間の多様な振舞いを表現する．こ62

な行動ルールの集合として定義される．
エージェントの行動設計者であるシナリオライタ

Action に記述される．Posit におけるシナリオの操作は，以下の様な種類が用意される．

は，特定の目標を解決する過程をシナリオとし，切• (start scenario S): シナリオ S の開始

り分けられた個々のシナリオを状況および状況の遷• (end scenario S): シナリオ S の終了• (transit posit A B): シナリオ内の PositA か移から問題解決のプロセスを構築する．このとき，

ら PositB への遷移

切り分けられたある状況下において実行可能，もしくは実行すべき行動ルールを Posit に記述する．

並列シナリオ記述では，シナリオの起動・終了，そまた，シナリオにおける状況の時間的遷移である

してシナリオ内部での遷移の操作を Posit operator

Posit の遷移は，行動ルールのなかに明示的に記述を用いて明示的に行なうことで表現する．これにされる．

より，複数の行動タスクを同時に実行する．我々はPosit は，具体的には．Figure2 に示す文法にした

エージェントの行動全体を並列シナリオとして設計がって記述する．Posit を構成するルールは，ルーすることで，対象とする現象に対する人間の適応的

ル名と環境条件 (Condition)，活性式 (Activation)，

行動に関係する知識を最大限に活用する．そして，

行動 (Action) の要素から成り立つ．各ルールは，

特定の目標に対する行動プロセスをシナリオベース

Condition において内部情報を含めた環境情報に対として表現することで，エージェントの複雑な行動

する観測内容を記述する．その際，評価の対象となるをボトムアップに構築する．

ルールに優先度はなく，対象となったすべてのルー
ルの Condition は同列に評価される．Activation は

3.3

PS2 :Parallel Scenario Problem Solver

活性式を表わし，Condition の観測内容を満たした

PS2 は，並列シナリオ記述の概念に基づいて記述

ルールは Activation によりその活性値を決定する．

されたエージェント行動を，エージェントの環境に

エージェントは，この活性値を基にルールの選択を基づいてシナリオを活性化，そのシナリオの流れに行なう1 ．Activation は単純な数値だけでなく，変そって適切なルールを評価・選択する行動決定エン数を含む関数として表現できる．つまり，シナリオ
ライタは Action に示された動作に対する重要性をActivation を通じて環境状態を反映させることができる．Action には，シナリオの条件下 Condition

ジンである．Figure3 は，PS2 の情報とコントロー
ルのフローを含めた PS2 の基本サイクルを示して
いる．
2

PS

Scenario
Posit
rule
rule
rule

Cond.
Cond.
Cond.

Actv.
Actv.
Actv.

Cond.

Actv.

Action.

Cond.

Actv.

Action.

Cond.
Cond.
Cond.

Actv.
Actv.
Actv.

rule

Cond.

Actv.

Action.

Scenario
Scenario

Posit

Action.
Action.

rule

Action.

rule
rule

rule

Posit
rule
rule
rule

Cond.
Cond.

Actv.
Actv.

Posit

Action.

Cond.

Actv.

Action.

Cond.

Actv.

Action.

rule

Cond.

Actv.

rule

Cond.

Actv.

rule

Action.

rule
rule

rule

Action.
Action.

Cond.

Actv.

Action.

Cond.

Actv.

Action.

rule

Cond.

Actv.

Action.

rule

Posit

Cond.

rule

Cond.

rule

Cond.

rule

Posit

Cond.

rule

Cond.

rule

Cond.

Actv.
Actv.
Actv.
Actv.
Actv.
Actv.

Actv.
Actv.
Actv.

Action.

Actv.

Action.

Cond.

Actv.

Action.

rule

Cond.

Actv.

rule

Cond.

rule

Cond.

Actv.
Actv.

Actv.
Actv.

Action.

rule

Action.

rule

Cond.
Cond.

Actv.

Actv.

Action.

Actv.

Action.

Cond.

Actv.

Action.

rule

Cond.

Actv.

rule

Cond.

Actv.
Actv.

Posit
Cond. Actv.

Cond.
Cond.
Cond.
Cond.

Actv.
Actv.
Actv.
Actv.
Actv.

Action.

Actv.

Action.

Action.

rule
rule
rule
rule
rule

ものではなく，エージェントにて定義されるものと

Actv.
Actv.
Actv.

rule
rule
Action.
Action.
Action.

Actv.

Action.

Actv.

Action.

rule

Cond.

Actv.

Action.

Cond.

Cond. Actv.
Cond. Actv.
Cond. Actv.

rule
rule
rule

Cond.
Cond.
Cond.
Cond.

Actv.
Actv.
Actv.
Actv.

Action.

Cond.

Posit

Actv.

rule

Cond.

Actv.

rule

Cond.

Actv.

Action.
Action.

Action.
rule
rule

Action.
Action.

rule
rule

Action.
Action.
Action.

Cond. Actv.
Cond. Actv.
Cond. Actv.
Cond. Actv.

Action.
Action.
Action.
Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

Posit
Posit
Posit
Posit

Posit
Action.

rule

Action.
Action.
Action.

Cond.

Actv.

rule

Cond.

Actv.

rule

Cond.

Actv.

rule

Action.

Posit

Action.
rule
rule
rule

rule
rule

Actv.

Cond.

Actv.

Cond.

Actv.

Cond.

Actv.

Action.

Cond.
Cond.
Cond.

Actv.
Actv.
Actv.

Cond.
Cond.
Cond.

Actv.
Actv.
Actv.

Action.

Cond.

Actv.

rule

Cond.

Actv.

rule

Cond.

Actv.

Action.
Action.
Action.
Action.
Action.

Cond.

Actv.

Action.

Cond.

Actv.

Action.

rule
rule

Cond.
Cond.
Cond.

Actv. Action.
Actv. Action.
Actv. Action.

Cond.

Actv.

Action.

rule

Cond.

Actv. Action.

Cond.

Actv.

Action.

rule

Cond.

Actv. Action.

rule

Cond.

Actv.

Action.

rule

Cond.

Actv. Action.

rule

Cond.

Actv.

Action.

Action.

Cond.

Actv.

Action.

Cond.

Actv.

Action.

Posit
rule

Action.

rule

Action.

rule
rule

rule
rule

Cond.
Cond.
Cond.
Cond.

Actv.
Actv.
Actv.
Actv.

Action.
Action.
Action.
Action.

rule

Cond.

Actv.

Action.

rule

Cond.

Actv.

Action.

Action.
Action.

Posit

Action.

Posit

Action.

rule

Cond.

Actv.

Action.

rule

Cond.

Actv.

Action.

rule
rule
rule

Cond. Actv.
Cond. Actv.
Cond. Actv.

Action.

rule

Action.
Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Posit
rule
rule
rule
rule

Cond.
Cond.
Cond.
Cond.

Actv.
Actv.
Actv.
Actv.

rule

Action.

Cond.
Cond.
Cond.

Actv. Action.
Actv. Action.
Actv. Action.

rule

Cond.

Actv. Action.

rule

Cond.

Actv. Action.

rule

Cond.

Actv. Action.

Action.
Action.
Action.

Posit
rule
rule
rule
rule

Cond.
Cond.
Cond.
Cond.

Actv.
Actv.
Actv.
Actv.

Action.

rule Cond.

Action.
Action.
Action.

rule

Cond.

Actv.

Action.

rule

Cond.

Actv.

Action.

rule

Cond.

Actv.

Action.

rule

Cond.

Actv.

Action.

Posit
Cond. Actv.
Cond. Actv.

Action.

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

シナリオ，並列シナリオ処理

ruleCond. Actv.

Action.

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

Posit

Cond. Actv.

Action.

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

特定の目的解決プロセスにおける状況および状況の

Posit

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Action.

rule
rule

Posit
rule

Action.

Posit

Posit
Action.

rule
rule

Actv.

Part of Situation

Scenario
ruleselection

rule Cond. Actv.
Action.
rule Cond. Actv.
Action.
rule Cond. Actv.
Action.
rule Cond.ruleActv.
Cond. Action.
Actv.
Action.
rule Cond. Actv.
Action.
rule Cond. Actv.
Action.
rule Cond.ruleActv.
Cond. Action.
Actv.
Action.
rule Cond. Actv.
Action.
rule Cond. Actv.
Action.
rule Cond.ruleActv.
Cond. Action.
Actv.
Action.
rule Cond. Actv.
Action.
rule Cond. Actv.
Action.
rule Cond.ruleActv.
Cond. Action.
Actv.
Action.
rule Cond. Actv.
Action.
rule Cond. Actv.
Action.
rule Cond.ruleActv.
Cond. Action.
Actv.
Action.
rule Cond. Actv.
Action.
rule Cond. Actv.
Action.
rule Cond. Actv.
Action.

Posit

Action.
rule

Action.
Action.

rule
rule

Action.
Action.
Action.

rule
rule

Posit
rule

Cond. Actv.

Cond. Actv.
Cond. Actv.
Cond. Actv.

Posit
rule

rule

Cond.
Cond.
Cond.
Cond.
Cond.

rule

Cond. Actv.
Cond. Actv.
Cond. Actv.
Cond. Actv.
Cond. Actv.

rule

Action.
Action.

Action.
Action.
Action.

Cond. Actv.

Posit
rule

Posit
rule
rule
rule
rule
rule

Posit

rule

Action.

Actv.
Actv.

Action.

Cond. Actv.
Cond. Actv.
Cond. Actv.

Action.
Action.
Action.
Action.

Cond.
Cond.

rule

Posit

Action.

Cond. Actv.

rule

rule

Action.

Posit

rule
rule
rule
rule
rule
rule

Action.

rule

Action.

rule
Cond.

Actv.

Cond.
Cond.

Action.

rule

Action.
Action.
Action.

Scenario
Scenario
rule

Cond.

rule
rule

Action.

Action.

Actv.

rule
Cond.
Cond.

rule

rule

Action.
rule
rule

Action.
Action.

Action.
rule

Cond.
Cond.

rule
rule

Current
Situation

Posit

Action.
Action.

Cond.
Cond.

Action.

rule
rule
rule
rule

する．

Cond.
Cond.

rule
rule

Posit

Action.
Action.
Action.

rule
ruleの時，Action の具体的動作は Posit にて定義される

3.2

Environment

Scenario DBの条件下でのエージェントの振舞いを記述する．こCond. Actv.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule

Cond. Actv.

Action.

rule Cond.

Actv.

Action.

Figure 3: Process ﬂow of PS2遷移により表わされるシナリオは，特定の状況を意

PS2 のサイクルは，次のようになっている．

味する Posit の集合と，それらの時間的遷移から構下に述べる Posit oprator 2 によって行動ルールの

1. エージェントの起動時，すべてのシナリオは Scenario DateBase(SDB) に格納．
2. SDB 内にある起動シナリオの初期 Posit を Current Situation(CS) に格納．
3. CS 内のすべての行動ルールに対する評価(a) 行動ルールの Condition と入力された環境情報とを比較．

1 現時点では Activation が最大となるルールを選択する方式を採用しているが，ルーレット選択など確率を用いるなどいく
つかの選択方式が考えられる．
2 Posit operator のプリミティブ操作は，各 Posit の活性化，不活性化を行なう add posit, remove posit である．上記のオペレータは (start scenario S) {=(add posit S:init)(end scenario S) {=(remove posit S:*) (transit posit AB){=(add posit B:init)(remove posit A;*)} として実現される．このとき S:init は，シナリオ S の起動時の初期状態 init
を，S:* は．終了時の Posit を意味する．

成される．エージェントの行動全体は，複数のシナ
リオの時間的重ね合わせとして表現し，様々な環境の変化への対応を図る．その際，シナリオ内における Posit の遷移，シナリオの起動および終了は，以63

Posit::=(defposit PositName Rule ＊ )

Rule

::=

(defrule RuleName :condition CondiForm:activation ActivForm:actionCondiForm::=

ActioForm )([LogicOP] CondiForm ＊)|(InSensor ...)

ActivForm::=

CalcForm

ActioForm::=([LogicOP] ActioForm ＊)|(OutSensor ...)

LogicOP::=and | or | not | progn

InSenor::=input sensor name with prefix “？”OutSenor::=output sensor name with prefix “！”CalcForm::=

number|Var|(CalcOP CalcForm CalcForm)

CalcOP::=+ | − | ∗ | / |%

Var

::=

variable name with prefix “＊”Figure 2: Syntax of Posit(b) 次に 3(a) を通過した行動ルールの Activationを評価しそれぞれの評価値を格納
4. 任意の選択ポリシーに基づいて実行ルールを選択
5. (4) で選択された行動ルールの Action を実行．
6. (5) によって SRS が変化した場合，適応可能な行動
ルールがなくなるまで (3)-(5) まで繰り返す．3 CSにルールがあり，適応可能な行動ルールが無くなった場合には，(3) に移動後，次の環境からの入力を待つ．もし CS 内に評価の対象となる Posit が無くなった場合には，エージェントの実行を終了する．

この PS2 では，シナリオにて表現されたエージェ
ントの行動を再現することで，シナリオの実行やPosit の活性化の前提となる環境の同定を事前に排除している．また状況の変化などにしたがって，シ((defposit "初期 Posit"(defrule "初期状態":condition (?know "震災時室内にいる"):activation 1:action "自分の家の場所を確認")(defrule "避難できるか?":condition (?know "怪我がない"):activation 10:action "避難所探索，避難行動に遷移")(defposit "避難行動"(defrule goto_refuge1:condition (?know "避難所の場所"):activation 1:action "避難所の場所に移動")(defrule "避難所に到着":condition (?know "現在地が避難所"):activation 2:action "避難行動を終了"))(defposit "避難所探索シナリオ"(defrule "近隣の避難所を探索":condition (?know "近隣にある避難所の場所"):activation (- 50 *time):action "避難所の場所を記憶し，避難所探索を終了"))
避難行動シナリオ

ナリオ等の活性化をコントロールするために行動決

Posit

避難行動

初期Posit

シナリオ

定の対象となる行動ルールは全体のルールの一部に
すぎない．

4

評価実験

シナリオ起動点
Posit起動後終了
Posit 起動

避難所探索
避難所探索シナリオ

Figure 4: Example of Behavior:Simple Action

我々は提案した並列シナリオ記述によるエージェン
トの行動決定への効果を評価するあたり一般市民
エージェントを実装した．以下に示す Figure4 もっとも簡単な振舞いのルールをもとに振舞いを組み立ててある4 ．

Figure4 では，避難行動シナリオと避難所探索シ
ナリオの２つのシナリオが用意され，避難所探索シ
ナリオは避難行動 Posit が起動されたときに同時に起動される．なお，検証実験の環境は Table1 に示

Table 1: 実験環境
OS
言語
CPU
Memory

す通りである．
3 ただし，エージェントの処理系によりルールの適応回数はリソースの制限が設けられる場合が考えられる．
4 このルール記述の中では，細かい表記を省略し，文章にて表現している

64

VineLinux 2.5CR
gcc 2.95.3
PentiumXeon 2.4GHz x 2
2GB

4.1

行動ルール数とエージェント数の計算時間コ(3) 変更，追加が容易な行動記述モデル

これらに対してストに与える影響(a) シナリオベース行動記述(b) シナリオと状況によるルールの切り分けおよび状
況の直接的操作

Figure5 は，シナリオのなかにあるルール数の違い
による 1 エージェントの計算時間コストの最大値の(c) 並列シナリオとインタプリタ実行

違いと，エージェント数による変化を示したグラフの 3 点を実現することで，社会シミュレーションにである．x 軸は同時に実行したエージェント数，yて動作するエージェントの行動を表現し実行する．

軸は計算時間コスト [nsec] を示している．
num = 5n um = 10
num = 30
num = 75
num = 150

800

700

具体的には，(1) に対して (a) では，熟考型行動における一貫性のある行動プランをシナリオにおける状況の時間的変化として，反射型行動における状況

600

変化への対応を並列シナリオとルールの並列評価に500よる柔軟な制御により対応している．そして (2) に400対して (b) により 4 で示したように，各エージェン

300

トの行動決定における計算時間コストの軽量化を図

200

100

り，多数のエージェントが現実的な計算時間で動作

0
0

100

200

300

400

500

600

700

することを確認した．最後に (3) に関しては (c) にFigure 5: Diﬀerence of calculation time cost forより，シナリオライタは Figure6 の様に，個々の行

each agent

動目標に対するエージェントの振舞いをシナリオとFigure5 のグラフから，エージェント数が増加しても，1 体当りの計算時間コストはほとんど変わらして独立に設計可能できる．そして，Figure6c) の様に新たな Posit やシナリオを追加することでエーないことが分かる．よって，ルール数の増加によるジェントの行動を必要に応じて変更できるだけでなシステムとしての計算時間コストへの影響は微少でく，エージェントの動作を決定する為に評価する行ある．

動ルール候補を状況ごとに絞ることで，ルール評価

4.2

実行状態の比較

Table2 は，我々の実装した市民エージェントと同じフィールド上で動作するレスキューエージェント[14]のプロセスとの実行状態の比較である．表が示プロセスにかかる計算時間コストの軽量化が行えるなどの利点を与える．また，Posit は特定の状況下での利用可能なルールの集合であるために，他のシナリオでの再利用可能などの利点がある．
Scenario A

すように，互いのエージェント数は異なるが，CPU占有率，平均処理時間ともにレスキューエージェン

fork scenario

a1

トより軽量である．メモリの消費量に違いがあるこa2a) scenarioAとを含め，プログラムの実装に依存するところも大きいが，この結果から市民エージェントは十分軽量AB

5CPU 占有率 (%)
メモリ占有率 (%)
処理時間 (msec)
5.5
10.2
344.5
52.3
0.1
439.0
A:一般市民 (150 ルール,500 体) B:救助部隊 (10 体)

考察

b1

b2

b) scenarioB

Scenario Bc) add scenarioA toscenarioB on posit

Figure 6: Compound Sceanrio by Posit

で動作すると考える．

Table 2: 救助エージェントとの実行状態の比較

a3

6

まとめ

本論文では，大規模社会シミュレーションにおけるエージェントの行動記述に対して，並列シナリオ記述を導入した．並列シナリオ記述では，特定の行動
目標の解決を目的とする行動プランや習慣などをシ

我々が提案した並列シナリオ記述は，2.1 にて大規

ナリオと定義し，各エージェントの状況依存的振舞

模社会シミュレーションにおけるエージェント行動

いをシナリオの重ね合わせとして表現する枠組みで記述モデルに対する要求として以下の点をあげたある．

(1) 熟考型行動と反射型行動の両方の特性を持つ行動
モデル(2) 軽量実行

並列シナリオ記述では，シナリオの起動及び終了
はシナリオの記述の段階で明示的に記述する．これ

65

により，シナリオライタは設計するエージェントの参考文献

行動を，行動目標ごとにシナリオを作成できるだけ[1]

ACT-R. Web Page http: // act. psy. cmu. edu/ .

でなく，個々のシナリオの起動・終了を意味するシ[2]John R. Anderson, Michael Matessa, and Christian Lebiere.
Act-r: A theory of higher
level cognition and its relation to visual attention. HUMAN-COMPUTER INTERACTION,
12:430–462, 1997.

[3]

Joshua M. Epstein and Robert Axtell. Growing
Artificial Societies. MIT Press, 1996.

[4]

Robert James Firby. Adaptive Execution in Complex Dynamic Worlds. PhD thesis, Yale University, 1989.

[5]

Robert James Firby. Task networks for controlling continuous processes. In the Second International Conference on AI Planning Systems, 1994.

[6]

Dan Ingalls, Ted Kaehler, John Maloney, Scott
Wallace, and Alan Kay. Back to the future –thestory of squeak, a practical smalltalk written in
itself. In OOPSLA’97, 1997.

[7]

Interaction Design Language Q Web Page.
http: // www. digitalcity. jst. go. jp/
research/ Q/ .

[8]

Toru Ishida. Q: A scenario description language
for interactive. IEEE Computer, 10 2002.

[9]

Toru Ishida and Masahito Fukumoto. Interaction
design language q : The proposal(in japanese). In
Proceeding of JSAI’01, 2001.

ナリオ間の遷移を追加・削除するだけでエージェン
トの振舞いを変更することができる．さらに，並列
シナリオ記述に基づいて記述されたエージェントの行動を，解釈し行動を選択するのが，行動決定エンジンである PS2 である．PS2 では，シナリオの起動・終了，そしてシナリオ内の遷移にしたがって，
行動決定に必要な行動ルールの候補を小さくたもつ
ことで，個々のエージェントの意思決定にかかる計算時間コストの削減を意図している．
この並列シナリオ記述に基づく大規模社会シミュ
レーションのためのエージェント行動記述への有効性の検証の一つとして，行動ルール数ならびにエー
ジェント数に対する計算時間コストのシミュレーショ
ンに与える影響を実験した．実験では，エージェン
ト数の増加による影響はエージェント数に対して単純増加であり，行動ルール数の増加の影響は少ないと示された．また，同じシミュレーション上における他のエージェントとの比較を行なった結果，多数のエージェントが動作しても現実的な時間で行動決定ができることが示された．よって，我々は並列シ
ナリオ記述によるエージェントの動作記述は，大規模社会シミュレーションに適していると考える．
本研究は以下の点で改善が必要であると考える．
1. 状況の変化に対するシナリオの整合性の管理
2. ビジュアルプログラミングなどによるシナリオ設計
環境(1) に関しては，環境の変化に対する行動をシナ
リオ内にてあらかじめ展開するために場合によっては十分な対応が取れなくなり，状況と実行している
シナリオとの間に整合性が取れない可能性がある．
よって，本研究で提案するフレームワークにおいても，GAEA にて開発されている状況の整合性チェッ
クをする方法[11]を導入する必要がある．

(2) では，研究が対象とする社会シミュレーショ
ンでの利用を目指すのであれば，容易にエージェン
トのシナリオが設計・管理できることが理想である．
それには，Squeak[6]などに代表されるビジュアル[10] Hiroaki Kitano. Robocup rescue : A grand challenge for multi-agent system. In Proceedings of theThird International Conference on Multi-Agent
Systems(ICMAS-2000), pages 5–11, 2000.
[11] Hideyuki Nakashima and Itsuki Noda. Dynamic
subsumption architecture for programming intelligent agents. In Proceedings of International
Conference on Multi-Agent Systems 98, pages
190–197. AAAI Press, 1998.
[12] Hideyuki Nakashima, Itsuki Noda, and Kenichi
Handa. Organic programming language gaea
for multi-agents. In Proceedings of International
Conference on Multi-Agent Systems 96, pages
236–243. AAAI Press, 1996.
[13] Allen Newell. Unified Theories of Cognition. Harvard University Press, 1990.
[14] Rescue HP. http: // www. r. cs. kobe-u. ac. jp/
robocup-rescue/ .
[15] RoboCup WebPage.
org/ .

http: // www. robocup.

[16] Soar Web Page. http: // ai. eecs. umich. edu/
soar/ .

プログラミング環境が適切であると考える．以上の点を今後の課題として検討する．

66

人工知能学会研究会資料
JSAI Technical Report
SIG‑Challenge‑0317‑13 (5/2)

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

ヒューマノイドロボットの動的起き上がり運動の理解と実現
Dynamic Stand up Motion of a Humanoid

大賀 淳一郎 ∗荻野 正樹 ∗

細田 耕 ∗†

浅田 稔 ∗†

Jun’ichiro OOGA∗ , Masaki OGINO∗ , Koh HOSODA∗† , and Minoru ASADA∗†∗∗

大阪大学大学院工学研究科, † 阪大フロンティア機構

Graduate School Engineerging, Osaka University, † HANDAI Frontier Research Center{ooga, ogino}@er.ams.eng.osaka-u.ac.jp, {hosoda, asada}@ams.eng.osaka-u.ac.jp

Abstract
In this paper, dynamic stand-up motion is realized by a humanoid robot. To avoid hard
impact with the ground, and to overcome thelimits of the joints, a round back is attachedto the robot. Parameters of the back is determined by simulations since the motion analysis is quite difficult because of the nonlinearity,
friction, and position control. An experimental result is shown that a real humanoid robot
HOAP–1 equipped with the designed back canstand up dynamically.

本報告では，人間型ロボットの動的起き上がりを，平坦な背中のままで実現可能かどうかをシミュレーション
によって実験し，起き上がり運動に必要な条件について考察する．さらに制限条件によって平坦な背中のままでは起き上がることのできないロボットに対しては，ロボッ
トに丸い背中を実装することによって起き上がり運動を実現する．これは，丸い背中を装備することによって着地時の衝撃を減らすことができるため，より少ないエネル
ギーで起き上がることができると考えられるからである．
背中の形状をシミュレーションによって検討し，実際のロボットに実装して，起き上がりを実現できることを実験的に確認した．

2
1

平坦な背中での動的起き上がり

はじめに
起き上がり運動には多くの種類が存在するが，本報告でヒューマノイドロボットは人間の生活環境においてさまざ

は脚を振り降ろすときのモーメントを利用する動的な起

まな活動を行う存在としての期待が高まっている．人間

き上がり運動の実現を目指す．

の代わりとして，または人間と共同して仕事を行うためには安定した 2 足歩行をすることが求められ，これまでの研究では，倒れずに歩き続けることが注目されてきた．
しかし不確実性の高い実世界においては，倒れないこと
よりも，倒れても起き上がることができることに注目すべきであると考えられる．

2.1

ロボットのモデル

ほとんどのヒューマノイドロボットの背中は平坦であるので，Fig. 1 のようにヒューマノイドロボットをモデル化する．

起き上がり行動を実現するために，静的につりあいをとりながら起き上がることも考えられる[1]が，動特性をLink 0

生かして起き上がることができれば，より少ない自由度
あるいはモータ出力で，起き上がり行動ができると期待θ1Zされる．動的な起き上がりに関しては，階層型強化学習による 3 リンク 2 関節ロボットの起立行動の獲得[2]や，脚X
Yの振り降ろしを利用した 4 リンク 3 関節の一脚ロボット
による起き上がり運動[3]などが報告されている．これら

Link 1

θ2

Link 2

θ3 Link 3の方法は，平坦な背中での起き上がりを考えており，起き上がりの際に生じる衝突によるエネルギー損失が大きく

Figure 1: Robot model configuration. θi (i=1,2,3) indi-

なることが予想される．

cates joint angles for hip, knee, and ankle, respectively.

67ここで θi (i = 1, 2, 3) はそれぞれ腰，膝，足首関節の関節角である．また，進行方向を X 軸，鉛直方向を Z 軸とTable 1: Parameters of the simulation robot

している．

2.2

link

制御上の仮定lengthweightinertia[m][kg][kg m2 ]起き上がるための条件を考察するに当たり，以下のような

Link0

0.31

0.76

6.09 × 10−3仮定をおくことにした．

Link1

0.15

0.16

3.00 × 10−4

Link2

0.15

0.38

7.13 × 10−4

Link3

0.01

0.11

8.33 × 10−8

joint

range[rad]hip2.95〜5.94

1. 矢状面内の運動に限定する．
2. それぞれの脚のモータは PD 制御でコントロールし，
速度台形則で関節角軌道を算出する．速度台形則では速度関数が連続しているが，少なくとも加速，等速，減速 3 つの場合分けが必要であるので，計算量を減らすために加速時間と減速時間を同じ長さに設定する．駆動時間 T は
T =

b−a
θ̇max

+ ∆T

knee 0.35〜3.33
ankle 1.57〜4.71(1)となる．ただし，初期時刻における関節角度を a，終端時刻における関節角度を b，最大角速度を θ̇max ，加速時間 (=減速時間) を ∆T とする．

3. モータの最大角速度は θ̇max であり，予め分かっている．ここで加速時間を決めると，駆動時間 T は初期
時刻の関節角度と終端時刻の関節角度の変化量に依(a) 0.00 sec(b) 0.10 sec(c) 0.20 sec(d) 0.30 sec(e) 0.40 sec(f) 0.50 sec(g) 0.60 sec(h) 0.70 sec(i) 0.80 sec(j) 0.90 sec(k) 1.00 sec(l) 1.10 sec

存する．

2.3

起き上がり運動のための条件

上体が起き上がるときの回転中心は腰関節であるが，足先が床面と衝突した後の回転中心は足裏に移動する．この回転中心の移動距離が小さいほど，衝撃時に散逸するエネルギー Eimp を抑えることができる．回転中心の移動
距離を小さくするには• 関節角の可動範囲を広くすることで，しゃがんだ姿
勢のときの足先位置を腰関節に近づける• 足先と床面の衝撃を小さくするため，l1 ≥ l2 とする．
(ただし lk は Fig. 1 における Linkk の長さ)とすればよいと考えられる．

2.4

シミュレーションによる実験

起き上がり運動が実現できるかどうかをシミュレーションで検証した．用いたシミュレーションでは，リンクのダイ
ナミクス計算，床との摩擦，衝突計算，それぞれの関節のサーボの計算を行うことができる．シミュレーションに用いるロボットのモデルのパラメータを Table 1 に示す．
また，各関節可動範囲はそれぞれ次のようにした．シミュレーション上において各関節に設計された軌道を追従さ

Figure 2: A stand up motion in the simulation

せて，起き上がり運動を実現できたようすを Fig. 2 に示す．Fig. 2 を見ると約 1 秒で脚を振り降ろししゃがんだ

68

2.5

Energy [J]2.0

今回のシミュレーションでは関節可動範囲がかなり大きいEM

1.5

ので，足先と腰関節の距離を小さくすることができ，スムーズに回転中心を移動させることができた．しかし，既1.0に完成されたロボットにおいては，関節可動範囲を簡単に

0.5

∆U

0.0

大きくすることができないので，この問題を解決することは非常に難しいと思われる．そこで次に丸い背中をロ

EK
0.0

0.2

0.4

0.6
Time [sec]

0.8

1.0

1.2

ボットに装着した場合の動的起き上がりについて考察し，丸い背中を設計して実機を使って実験を行った．

Figure 3: Energy change during stand up motion in thesimulation
103

丸い背中での動的起き上がり

3.1

丸い背中の利点

ロボットに丸い背中を装着することによって，床面との衝8Power [J/sec]

平坦な背中による起き上がり運動の考察

撃を抑えて Eimp が小さくすることができれば，より少な

6いエネルギーによって起き上がりを実現できると期待さ

4

れる．

2

ロボットに丸い背中をつける利点として以下の点があ

0

げられる．
0.0

0.2

0.4

0.6
Time [sec]

0.8

1.0

1.2

Figure 4: Power change during stand up motion in thesimulation
姿勢で脚を深く曲げて，足裏に体重が載っているのが分か• 上体が回転している時に床面との摩擦で失われるエ
ネルギーが腰関節の一点で回転させるときよりも小さくなる．

• しゃがんで脚を曲げた状態のときに足先ができるだ
け背中と一続きになるように設計すれば，回転中心の移動が滑らかに行われるので，足先と床面の衝突る．また，シミュレーションで得られたエネルギーと仕事時の散逸エネルギーの量を減少させることができる．

率の時間変化をそれぞれ Fig. 3, 4 に示す．ここで，Fig.

3 の ∆U はロボットのリンクの持つ現在のポテンシャルエ
ネルギーから初期状態のポテンシャルエネルギーを引いたもの，EK はリンクの重心の並進運動エネルギーと重心
回りの回転エネルギーの和，EM は以下のようにして計算されるモータによって与えられたエネルギーである．
Z t
EM =

τ θ̇dt(2)

ただし，その場合に脚の各関節の可動範囲を考慮に入れなければならない．

• 非常に簡単な関節角軌道を関節角に与えるだけで起き上がることができる．
3.2

制御上の仮定2.2 で述べた制御上の仮定に以下の点を加える．

0• 運動の過程を以下の 3 つの状態に区分し，それらを経て立ち上がるものとする．

また，Fig. 4 はP ower =d(EM − ∆U − EK )dt

(3)

状態 A 脚を伸ばした状態で上方に持ち上げる．
状態 B 足裏が床面に接するまで，膝を曲げた状態でを表している．

素早く脚を振り降ろし始める．このとき関節の角Fig. 2 と合わせて見てみると，足先が床面と衝突する
瞬間以降 (t = 0.8〜[sec]) から運動エネルギーが減少し始速度は最大になっている．
状態 C 重心が足裏にうまく載ると，直立姿勢がとれめているのが読みとれる．このときポテンシャルエネル

るように膝を伸ばし起立する．

ギーはさほど大きく変化していないことから，衝撃によってエネルギーが散逸したと考えられる．

ロボットに丸い背中を装着したときのそれぞれの状

また，0.0 < t < 0.1 や t = 0.3 付近などで P ower が増態を Fig. 5 に示す．状態 A から状態 B へと遷移す加しているのはリンクを動かし始める時と止める時に急る間に，ロボットの脚と胴体に運動エネルギを蓄え，激に加速，あるいは減速するために衝撃が生じているた

これを位置エネルギーに変換することによって，起めである．

き上がり運動が実現される．

69

Table 2: Parameters of the simulation robot
lengthweightinertia[m][kg][kg m2 ]

body

0.20

3.55

1.32 × 10−2

thigh

0.10

0.7

5.83 × 10−4

shank

0.10

1.18

9.83 × 10−4

foot

0.098

0.50

1.67 × 10−5

joint

range[rad]link(a) State A(b) State B(c) State C

Figure 5: Key postures in stand up motion by attachinga round back

本報告では Fig. 6 のように，円弧状の背中をロボットに取り付けることとした．ここで，設定すべきパラメータ
Link 1
Link 0H

l0θ2Link 2hip

1.92〜5.15

knee

0.94〜3.14

ankle 2.10〜4.18

θ1RFigure 6: Robot model with a round backは，ロボットの重心に対する円弧の中心の位置 H と円弧の半径 R である．また，脚を曲げた状態で足先ができるだけ背中と一続きになる，すなわち円周上に足先が来るように設定し，H と R はR2 = H 2 + l02 ．

(a) 0.00 sec(b) 0.16 sec(c) 0.32 sec(d) 0.48 sec(e) 0.64 sec(f) 0.80 sec(g) 0.96 sec(h) 1.12 sec(i) 1.28 sec(4)という関係を充たすようにした．

3.3

シミュレーションによるパラメータの検討

ロボットに取り付ける背中のパラメータ H ，R を，ダイ
ナミックシミュレーションプログラムによって求めた．
シミュレーションに用いるロボットのモデルのパラメー
タを Table 2 に示す．重量バランスができるだけ HOAP-1に近付くように設定した．
シミュレーションにおいては R = 0.2[m]，H = 0.0[m]の背中によって起き上がりを実現できた．シミュレーショ
ン上において HOAP–1 の各関節に設計された軌道を追従させて，起き上がり運動を実現できた様子を Fig. 7 に
示す．

3.4

実ヒューマノイド HOAP での実装と実験

Figure 7: A stand up motion in the simulation

実験においては，富士通で開発された HOAP–1 を用いる．
高さがおよそ 0.48[m]，重量はおよそ 6.0[kg] であり，片脚6 自由度，片腕 4 自由度を備えている．装備されている腕70

はトルク不足で，腕を用いた静的な起き上がりを実現することができない．HOAP-1 の各関節はそれぞれローカ
ルに位置制御されているので，予め設計された軌道に追従させることとした．

3.5

背中の実装と起き上がり

4

おわりに

本報告では，人間型ロボットの脚の振り降ろしを利用した動的な起き上がり運動について考察し，ロボットに丸い背中を設計，実装することで床面との衝突時におけるエネルギー損失を減少させ，実現させることに実験的に成功した．

シミュレーションによって得られたデータを基に，丸い背中を設計し，ロボットに実装した．Fig. 8 に実装した様
子を示す．

今後はより安定して起き上がらせるために，着地時における制御を工夫したり，センサによるロボット自身の状態認知によって脚の振り上げ角の制御をオンラインで行うことにより，さまざまな床面で起き上がり運動が実現できるかどうかを考えていきたい．

参考文献[1] 金広文男, 稲葉雅幸, 井上博充. 倒れても起き上がることのできる人間型ロボット. 第 13 回日本ロボット学会
学術講演会, Vol. 1, No. 1, pp. 195–196, 1995.

[2] 森本淳, 銅谷賢治. 階層型強化学習を用いた 3 リンク
2 関節ロボットによる起立運動の獲得. 日本ロボット
学会誌, Vol. 19, No. 5, pp. 574–579, 2001.

Figure 8: HOAP–1 with a round back[3] 伊藤聡, 阪圭央, 川崎晴久. 脚の振り降ろしを利用した
起き上がり運動について. 第 20 回日本ロボット学会
学術講演会予稿集, pp. CD–ROM 1I34, 2002.

HOAP–1 の各関節に設計された軌道を追従させると，起き上がり運動を実現することができた．この様子を Fig.
9 に示す．

Figure 9: A stand up motion71

c 2003

Special Interest Group on AI Challenges
Japanese Society for Arti cial Intelligence

社団法人 人工知能学会 ＡＩチャレンジ研究会〒 162 東京都新宿区津久戸町 4-7 OS ビル 402 号室 03-5261-3401 Fax: 03-5261-3402(本研究会についてのお問い合わせは下記にお願いします.)

ＡＩチャレンジ研究会
主 査
奥乃 博
京都大学大学院 情報学研究科 知能情報学専攻

Executive Committee
Chair
Hiroshi G. Okuno
Dept.

of Intelligence Science and〒 606-8501 京都市左京区吉田本町
075-753-5376
Fax: 075-753-5977

Technology,

okuno@i.kyoto-u.ac.jp

Kyoto University

Gradulate School of Informatics
Yoshida-Honmachi Sakyo, Kyoto 6068501 JAPAN

Secretary
Minoru Asada

幹 事
浅田 稔

Dept. of Information and Intelligent

大阪大学大学院 工学研究科
知能・機能創成工学専攻

Engineering

武田 英明
国立情報学研究所 知能システム研究系

Osaka University

Graduate School of Engineering

Hideaki Takeda

樋口 哲也
独立行政法人 産業技術総合研究所

National Institute of Informatics

田所 諭
神戸大学 工学部 情報知能工学科

National Institute of Advanced

Tetsuya Higuchi

Industrial Science and Technology

Satoshi Tadokoro

Dept. of Information and Intelligent
Engineering
Kobe University
SIG-AI-Challenges home page (WWW):

http://winnie.kuis.kyoto-u.ac.jp/SIG-Challenge/