目次
1. ロボットの行動獲得のための対話型進化計算,
藤井 聖也，中島 智晴，前田 慎吾(大阪府立大学大学院工学研究科) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2. 方策勾配法における状態空間の階層化の一考察,
五十嵐 治一 [1], 石原 聖司 [2](1 芝浦工業大学工学部情報工学科, 2 近畿大学工学部電子情報工学科) . . . . . . . . . . . . . . . .

7

3. 非定常環境下における自己位置推定法,
辻塚 弘一 [1]，大橋 健 [2](1 九州工業大学大学院情報工学研究科, 2 九州工業大学情報工学研究院) . . . . . . . . . . . . . . . 13
4. 安全領域：SSL リーグにおける守備アルゴリズムの評価指標,
前野 順也, 村上 和人, 成瀬 正

(愛知県立大学情報科学部) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5. サッカーロボットの Profit Sharing による学習,
山口 雅士 [1], 岡本 成晃 [1], 川上 誠 [2], 澤 洋一郎 [2](1 沼津高専専攻科, 2 沼津高専電子制御工学科) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6. 移動型ロボットにおける動作特性と行動知識の分離,
長谷川卓也 [1]，五十嵐治一 [1], 石原聖司 [2]，田中一基 [2](1 芝浦工業大学工学部, 2 近畿大学工学部) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7. Mutual Development of Behavior Acquisition and Recognition based on Value System,
Yasutake Takahashi[1], Yoshihiro Tamura[1], and Minoru Asada[1,2](1 Dept. of Adaptive Machine Systems, Graduate School of Engineering, Osaka University,
2 JST ERATO Asada Synergistic Intelligence Project) . . . . . . . . . . . . . . . . . . . . . . . . 33
8. ACO を用いた RoboCup サッカーエージェントにおける行動獲得手法の提案,
笹岡 久行 [1], 山田 太郎 [2](1 旭川工業高等専門学校 電気情報工学科, 2 旭川工業高等専門学校専攻科) . . . . . . . . . . . . . 40
9. ARToolKit を用いたヒューマノイドロボットのモーション推定,
清水 彰一, 藤田 征士, 草富 省吾, 伊藤 孝浩, 藤吉 弘亘(中部大学) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

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

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

ロボットの行動獲得のための対話型進化計算
Interactive Evolutionary Computation for Acquiring Robot Behavior

藤井聖也，中島智晴，前田慎吾
Seiya FUJII, Tomoharu NAKASHIMA, Shingo MAETA

大阪府立大学大学院 工学研究科
Graduate School of Engineering, Osaka Prefecture University

fujii@ci.cs.osakafu-u.ac.jp, nakashi@cs.osakafu-u.ac.jp, maeta@ci.cs.osakafu-u.ac.jp

ことはできない．例えば，プレーヤは他のプレーヤの頭上

Abstract

を越えてシュートを打つことはできない．そのため，ボーThis paper presents an interactive framework
for the design of robot behavior. Evolutionary computation is used in this framework. An

ルを持っているプレーヤがシュートを打つためには，相手

individual in the evolutionary algorithm represents a robot behavior. A human evaluator sub-

グは厳密に実際のサッカーをシミュレートできていないとのプレーヤを避けて，インターセプトされないシュート
コースを見つけなくてはならない．この点から，2D リー
いう指摘もある．

jectively evaluates the robot behavior. Evaluation results by the human evaluator are used infitness calculation. New individuals are gener-

それに対して，3D リーグでは高さの概念が取り入れられている．このことにより，3D リーグにおける試合は，
より実世界の試合に近づいたといえる．しかし，3D リー

ated through evolutionary operations using the
calculated fitness. We discuss the advantage

グ立ち上げ当初の数年間は，プレーヤとして球体のサッカーエージェントが用いられていた．そのため，当時のand disadvantage of the interactive design ofrobotic behavior. We also show some experimental results where walking gaits are success-

3D リーグの試合は，実世界の試合をシミュレートしているとは言いがたいものであった．しかし，2007 年，プレーヤとしてヒューマノイド型のサッカーエージェントが新

fully obtained by the interactive framework.

1

しく導入された．これにより，シミュレーションと現実のサッカーとの距離は一気に縮まったが，その反面，全てのはじめにチームがエージェントの低レベル行動から開発を進めな
くてはならなくなった．

本論文では，ロボットの行動を獲得するための対話型進化計算を提案する．対話型進化計算は，個体の評価方法に特

図 1 に 3D リーグで用いられているヒューマノイドロ徴がある．従来の進化計算では，適応度関数はアルゴリズ

ボットの外観を示す．このヒューマノイドロボットの自由

ムの実行前にあらかじめ定義されており，アルゴリズムの度は 20 に設定されている．すなわち，このヒューマノイ

実行中，各個体はその適応度関数に従って客観的に評価

ドロボットを完全に制御するためには，20 カ所の関節のされる．それに対して，対話型進化計算では個体の客観的角度をタイムステップごとに設定する必要がある．我々のな評価は行われない．その代わりに，人間が評価者となっ知る限り，図 1 に示すヒューマノイドロボットに関する研て主観的に個体の適応度を決定する．

究報告は存在しない．そこで，本論文では，このヒューマ
ノイドロボットを研究の対象とする．

現在，RoboCup サッカーシミュレーションには，2D,

3D, 3D development の３種類のリーグが存在する．3D
development リーグはサッカーサーバやそれに関連するシステムの開発を行うリーグである．2D リーグでは，プ

ヒューマノイドロボットの行動獲得に対しては，これまでに多くの手法が提案されている．例えば，[8]では倒立振子の制御手法が二足歩行ロボットの制御に適用されてレーヤ，ボールなどの全ての物体は二次元平面上のベクトいる．また，歩行ロボットの中枢パターン生成器 (CPG:
Central Pattern Generator) に神経振動子[3]を適用する研ルとして表現されている．2D リーグは，高レベル意思決定システムのテストベッドとしての利用価値が高い一方究も行われている[2],[7],[4]. その他に，ゼロモーメント点(ZMP: Zero Moment Point)[9]もまたロボットの安定したで，「高さ」の概念を必要とする低レベル行動を実現する-1-

ば，スポーツの場合，行動の「良さ」を数値的に，すなわ
ち客観的に求めることはできないが人間の主観的な評価であれば容易であるという状況は少なくない．そのような場合に，対話型進化計算は人間の主観性を導入することで，客観的に測定できない複雑な行動の評価を行うことができる．

2

対話型進化計算対話型進化計算の概念は，Takagi[6]によって提唱された．
その特徴は，進化計算における適応度の評価に人間であるユーザの主観を用いているという点にある．従来の進化計算と対話型進化計算の違いを，図 2，3 に示す．図 2では，従来の進化計算の枠組みが示されている．図 2 において，アルゴリズムと人間は互いに影響していないことがわかる．一旦進化が始まると，ユーザはアルゴリズ
ムが終了するのを待つことしかできない．それに対して，
対話型進化計算では，ユーザは個体を評価することで進Figure 1: ヒューマノイドロボット化に影響を与えることができる．この手法は，芸術などの分野に対して特にその効果を発揮する．

制御に広く用いられている．ゼロモーメント点の考えを用いることで，ロボットは転倒しないようにスムーズに体勢を変えることができる．これらの手法を用いることで，Initialization

上手くロボットを制御できるということは示されている
ものの，それぞれに欠点も存在する．例えば，神経振動子に関しては，最適な結合強度を求める手法が存在しない．

Fitness evaluation

その理由として，神経振動子には，誤差逆伝播法などの誤差をフィードバックするアルゴリズムを適用できないという点が挙げられる．また，ゼロモーメント点に対しては，

Evolutionary operation

No interaction with human

ヒューマノイドロボットの支持多角形を求めるための計
算時間のコストが高いということが挙げられる．これは，支持多角形を求める際，各タイムステップまたは行動ごとに繰り返し計算が行われるからである．

Stopping condition

Figure 2: 従来の進化計算以上で挙げた手法以外では，進化計算が考えられる．進化計算には，上で述べた従来手法に優る利点がある．それは，多くの場合，ロボットの行動を厳密にモデル化する必要がないという点である．例えば，第 3 章では，歩Initialization

行動作獲得を例とした対話型進化計算が述べられているが，厳密な物理モデルや複雑なメカニズムは用いていな
い．しかし，進化計算にも欠点がある．それは，適応度関

Fitness evaluation数の定義が難しいという点である．特に，動的な状況においてロボットの行動を最適化するような問題に対しては，個体の「良さ」の適切な定義はより困難になる．さらに，

Interaction with human
Evolutionary operation

最適化を行う対象の次元数が巨大であったり，個体の性能が事実上測定できないような場合には，適応度関数の定
Stopping condition

義はさらに複雑なものになる．
本論文では，ロボットの行動を獲得するための対話型

Figure 3: 対話型進化計算

進化計算を提案する．提案手法の主な特徴は，個体の評価
を人間の評価者の主観によって行っている点である．例え-2-

対話型進化計算によるロボットの行動獲得

3

3.2

個体表現

本論文では，足の動きを周期運動としてモデル化する．以下
本章では，ヒューマノイドロボットの行動獲得の一例を示の式により，時刻 t における関節 i, i ∈ {hip, knee, ankle}

す．獲得する行動は，歩行動作とする．本章の目的は，対の角度 θi (t) を求める．

話型進化計算によりヒューマノイドロボットの歩行動作を獲得することなので，この問題を以下のように簡略化の足関節の動きを最適化する．歩行の間，腕はロボットtt+B1i )+C1i +Ai2 sin(2π · +B2i )+C2i
T
T
(1)
i
i
i
i
i
i
ここで，A1 , A2 , B1 , B2 , C1 , C2 は足の動きを決める設計の状態に沿ってまっすぐに固定しておく．人間は普段，歩変数であり，T は周期である．すなわち，各関節に対して行の際には腕を振っていると考えられるため，この設定

６つの設計変数（Ai1 , . . . , C2i ）が，本章で説明する対話型

θi (t) = Ai1 sin(2π ·する．
歩行動作の獲得が目的なので，ヒューマノイドロボット

進化計算によって最適化される．よって，最適化される設は適切でないかもしれない．しかし，本論文では，対話

計変数の総数は，3 × 6 = 18 となる．

型進化計算によるロボットの行動獲得の可能性を示すこ

各個体は，ヒューマノイドロボットが歩行動作を行うとを目的としているので，設計変数の数を減らし，数値のに必要な関節の軌道を表現している．歩行動作には両実験を行う．また，右足の動きは左足の動きを半周期ずらすことで得られるので，今回は左足の動きのみを考える．

足の関節を動かす必要があるが，本章では，左足の３関節の軌道のみを最適化する．右足の関節の軌道は，左足

以上をまとめると，対話型進化計算により最適化されるのものを半周期ずらすことで獲得する．また，３つの関関節の数は，股関節，ひざ，足首の３つとなる．

節は実数値にコード化する．すなわち，18 個の設計変数

3.1

hip
knee
, . . . , C2ankle を持, . . . , C2knee , Aankle
Ahip
1
1 , . . . , C2 , A1
つ個体 I は以下のように表すことができる．

アルゴリズムの概要

図 4 に本章で用いる対話型進化計算のアルゴリズムを示す．
まず，Step 1 では，標準正規乱数を用いて初期個体をランI = (x, Z)

ダムに生成する．生成する初期個体は 1 個体のみとする．

Step 2 では，複製操作により初期個体から２個体を生成する．今回は，複製操作として Correlated mutation[5],[1]を適用する．Step 3 では，人間の評価者が，親個体１体(2)

ここで，x, Z は以下のように表される．
hip
hip
ankle
, B2ankle , C2ankle )x = (Ahip
1 , B1 , C1 , · · · , A2


α1,1





Z=





と子個体２体を合わせた３個体の評価を行う．個体の表現型であるヒューマノイドロボットは，評価者の主観に基づいて３体同時に評価される．以上の手順を，あらかじめ決めておいた終了基準を満たすまで繰り返す．

α1,2

α1,3

···

α1,17

α2,2

α2,3
α3,3

···
···
..
.

α2,17
α3,17
..
.
α17,17

α1,18

(3)




α2,18 

α3,18 

.. 
. 


α17,18 (4)α18,18
Step 1: Initialization

式（2）における行列 Z は，分散共分散行列と呼ばれる上三角行列である．よって，Z の成分 αi,j は，i 番目の設計
変数と j 番目の設計変数の相関を表す．本論文において歩行動作を獲得する場合，18 個の設計変数を用いているの

Step 2: Reproduction

で，分散共分散行列 Z は 18 次正方行列となる．また，図4 の Step 1 に示す初期化操作では，対角成分を 1，その他をの成分を 0 として初期化を行う．この分散共分散行列がどのように用いられるかについては，第 3.4 節で述べる．

Step 3: Evaluation

3.3

評価

適応度の評価は，人間の評価者との対話により行われる．
すなわち，評価者が主観的に個体の評価を行う．そのため

Step 3: Evaluationには，評価者がヒューマノイドロボットの歩行動作を観察し，評価できるようなユーザインターフェースが必要

Figure 4: アルゴリズムの流れになる．本論文では RoboCup サッカーシミュレーション

3D リーグで用いられているヒューマノイドロボットを対-3-

象としている．そのため，ユーザインターフェースには，

図 5 の様子を横から観測したものである．この視点からリーグで用いられているのと同じ標準のモニタを用いる．

は，最も奥のロボットが最も手前のロボットよりも前進し

図 5，6 にヒューマノイドロボットが映されている様子をていることがわかる．そのため，最も高いランクを奥のロ示す．このモニタでは，視点の位置や向きを自由に変更す

ボットに与える．このようにして，評価者は３体のロボッることができる．評価者はこのモニタ上で同時に３体のトにランクを割り当てる．また，評価の基準は評価者の好ヒューマノイドロボットの歩行動作を観察し，評価する．

みなので，ロボットの行動として倒れる行動を獲得したい

ここで，モニタ上で同時に観察するロボットの数は３体場合には，最も高いランクを図 5 の中央のロボットに与としているが，それ以上に増やすことも可能である．しかえることで倒れる行動をとるロボットの進化が行われる．

し，評価者が同時に多くのロボットを適切に評価できるかどうかを考慮すると，あまり多くのロボットを用いる

3.4のは適切でないと考えられる．

複製操作

個体の複製操作には，突然変異操作を用いる．突然変異操作を受ける親個体は，第 3.3 節における適応度の評価に基づいて選択される．個体は 18 次元の実数ベクトルとしてコード化されているので，標準正規分布を用いて個体に摂動を与える．ここで，高次元の探索空間を持つ最適化問
題に適用される一般的な突然変異操作として，Correlated
mutation[5],[1]という手法がある．Correlated mutation では，個体の持つ分散共分散行列を用いて突然変異操作が行われる．Correlated mutation により新たに生成される子個体は，探索空間内の超楕円形の分布に従って生成される．分散共分散行列は，探索方向を表す超楕円の形状を決めるために用いられる．ここで，図 7 に二次元の探索

Figure 5: 評価画面（正面）

空間における Correlated mutation の例を示す．図 7 において，黒丸は親個体を表しており，楕円はその親個体の持つ分散共分散行列によって求められた分布を表している．
子個体はこの楕円形の正規分布に従って生成される．

：Parent：Children

Figure 6: 評価画面（横）評価者は，観測した歩行動作から各ロボットにランクを割り当てる．このランクは評価者の主観的な好みを表しており，この値が進化計算における個体の適応度として用いられる．ここで，図 5，6 に対して，歩行動作の獲得

Figure 7: Correlated mutation.

を目指す場合のランク割り当ての例を示す．図 5 では，中央のロボットが倒れていることがわかる．そのため，中央のロボットに最も低いランクを与える．次に，左と右のロ

子個体の分散共分散行列は，親個体の分散共分散行列

ボットの評価であるが，図 5 からどちらが好ましいかを見に突然変異操作を加えることで生成される．そのため，共極めることは容易ではない．このような場合に，視点の変分散行列に関しても，高いランクを与えられた個体が親更が可能であるという特徴が大きな利点となる．図 6 は，個体として選択されることになる．

-4-

3.5

実験結果

本節では，前節で述べた対話型進化計算により獲得されたヒューマノイドロボットの歩行動作を示す．数値実験では，前方への歩行と後方への歩行の２種類の動作獲得を試みる．この２種類の歩行動作を，対話型進化計算の枠組みに変更を加えることなく獲得する．唯一異なるのは，評価者が前方と後方のどちらへの歩行を高く評価するかという点である．また，RoboCup で用いられているモニタのようなユーザインターフェースは，異なる行動を獲得する場合でも，修正を加える必要はない．このような，評価者の評価の基準を変更するだけで異なる目的を達成

Figure 9: 中盤での様子できる点は，対話型進化計算の特長である．

3.5.1

前方への歩行動作の獲得

アルゴリズムの終了条件は 100 世代とする．各世代において３個体が同時に評価されるので，一回アルゴリズ
ムを実行すると 100 × 3 = 300 体の個体が評価されることになる．
まず，図 8 に進化の序盤でのヒューマノイドロボットの様子を示す．この段階では，ロボットは歩行することはできていない．しかし，ほぼ同じ位置でわずかに足踏みを行う様子が見られた．次に，図 9 に進化の中盤での様子を示す．この段階では，ロボットはすぐにバランスを失って倒れてしまうものの，短い距離の歩行ができるようになっ

Figure 10: 終盤での様子ている．最後に，図 10 に進化の終盤に獲得された歩行動
作を示す．獲得された歩行動作では，転倒することなく安定して歩行することができている．

ものを用いる．図 11 に獲得された歩行動作を示す．進化

実験結果から，提案した対話型進化計算により上手くの序盤では，ロボットはその場で足踏みを行うだけであっ前方への歩行動作が獲得されていることが示された．

3.5.2

た．しかし，100 世代を経ると，上手く後方への歩行を獲得することができた．

後方への歩行動作の獲得

実験手順は，前方への歩行動作を獲得した場合と全く

4

おわりに

同じである．唯一異なるのは，評価者が後方に向かう動作に高い評価を与えるという点である．終了条件などの実本論文では，ヒューマノイドロボットの行動を獲得する

験設定も，前方への歩行動作を獲得した場合と全く同じための対話型進化計算を提案した．行動の一例として，

RoboCup 3D リーグで用いられているヒューマノイドロ
ボットの歩行動作を対話型進化計算により獲得した．提案手法の効率性を示すために，ヒューマノイドロボットの歩行システムは簡略化したものを用いた．
対話型進化計算によるロボットの行動設計という分野には，今後解決されるべき問題が多く残っている．それらのうち，最も取り組まれるべき問題は，評価者が無限に評価を行い続けることができないという点である．この問題に対しては，適応度の予測メカニズムを適用し，遺伝子型の情報のみから適応度関数の評価を行うことで，評価者の負担を減らすことができると考えられる．
対話型という概念は，従来の手法と比べて計り知れないほどの利点を持っている．その一つが，「ひらめき」といFigure 8: 序盤での様子

う人間がコンピュータよりも優れている能力を十分に利-5-[7] K. Tsuchiya, S. Aoi, and K. Tsujita. Locomotion
control of a biped locomotion robot using nonlinear
oscillators. In 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003. (IROS
2003), volume 2, pages 1745–1750, 2003.
[8] T. Tsuji and K. Ohnishi. A control of biped robot
which applies inverted pendulum mode with virtual
supporting point. In 7th International Workshop
on Advanced Motion Control, 2002, pages 478–483,
2002.
[9] M. Vukobratovic and J. Stepanenko. On the stabilFigure 11: 後方への歩行

ity of anthropomorphic systems. Mathematical Bioscience, 15:1–37, 1972.

用できる点である．この考えは，サッカーチームのフォー
メーションや基本的で複雑なスキルなどの評価といった様々な問題に適用することができる．本論文では，歩行動
作の獲得という比較的単純な問題を取り扱ったが，その概念は，ロボットの行動の対話型設計という無限の研究分野へ拡張できると考えられる．

参考文献[1] Nikolaus Hansen.

Invariance, self-adaptation andcorrelated mutations in evolution strategies.
[2] Daniel Hein, Manfred Hild, and Ralf Berger. Evolution of biped walking using neural oscillators andphysical simulation. In RoboCup 2007: Proceedingsof the International Symposium, LNAI. Springer,
2007.
[3] K. Matsuoka. Mechanisms of frequency and patterncontrol in the neural rhythm generators. Biologicalcybernetics, 56:345–53, 1987. PMID: 3620533.
[4] Pinto and Golubitsky. Central pattern generatorsfor bipedal locomotion. Journal of Mathematical Biology, 53:474–489, 2006.
[5] Günther Rudolph. On correlated mutations in evolution strategies. In R. Männer and B. Manderick,editors, Proceedings of 2nd International Conference
on Parallel Problem Solving from Nature, Brussels
1992, pages 105–114, Amsterdam, 1992. Elsevier.
[6] H. Takagi.

Interactive evolutionary computation:
System optimization based on human subjective
evaluation. In Internationa Conference on Intelligent
Engineering Systems, 1998, pages 1–6, 1998.

-6-

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

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

方策勾配法における状態空間の階層化の一考察
Hierarchization of State Space in Policy Gradient Methods〇五十嵐 治一 (芝浦工業大学工学部情報工学科)
石原 聖司(近畿大学工学部電子情報工学科)* Harukazu IGARASHI(Shibaura Inst. of Tech.), Seiji ISHIHARA(Kinki Univ.)* arashi50@sic.shibaura-it.ac.jp

１）は，状態の粗視化や行動のマクロ化が，状態や行動の処理単位（粒度）を大きくすることにより，状態空間や行動空間のサイズを小さくし，次元の呪い（情報爆発）を防ぎ，学習を高速化しようとする
目的で階層化を行おうとする考えである．状態の粗視化自体は画像処理など様々な分野で用いられる常套手段である．また，時系列的な行動系列をひとまとめにする行動のマクロ化については Sutton らのoption [1]がよく知られている．RoboCup サッカーシ
ミュレーション・リーグでも Brainstormers チームは，サブゴールを持った行動列としてパスカット，ドリブル，キック，ホールドなどのマクロ行動を定義し，1. はじめにTD 学習に利用している[7]．
２）の目的は，状態や行動の抽象化（記号化）に
強化学習の階層化に関する研究例は多い[1-4]．しより，我々人間が環境のダイナミクスや状態推移をかし，まずここで問題となるのは，何の目的で階層
戦略的な観点から分析，理解することができること化を行うのか，そのためには何を階層化するのかとと，その結果を利用して戦略的なレベルにおいてゴいう２つの点であろう．次に問題となるのは，具体ール到達への最適ルートを強化学習により探索する的な階層型モデルと学習法を設計することである．
ということである．従来から，個々の primitive な行
本稿では，基本的な問題である，階層化の目的，対動による状態推移ではなく，空間的に大域的な，あ象，モデル，学習法について簡単な考察を行った後，るいは意味や概念の上で構造的なシステムの状態推
階層型強化学習のための一つの方式を提案する．
移を分析することや，学習過程や学習結果を理解す
従来提案されている階層型強化学習で用いられてるのはコンピュータにとっては，不得手な分野とさいるのは，マルコフ決定過程(MDP)や半マルコフ決れてきた．したがって，階層型強化学習により，こ定過程(SMDP)を前提としたＱ学習が多い．本研究のような大域的，抽象的な戦略的なレベルにおいてでは，マルコフ性を要求しない強化学習法として知最適方策を学習することができれば，知的システムられる方策勾配法[5][6]を用いた定式化を試みた．
の構築に大きな貢献をするものと期待される．
さらには，エージェントまたはマルチエージェン
３）の方策関数のモジュール化は，強化学習によト系の状態が Boltzmann 分布などの定常分布に従っり得られた獲得知識の再利用に役立つ．例えば，大て推移している場合の階層型学習へも本提案手法がきな状態空間を扱う場合に，学習器のモジュール化
容易に適用できることを示す．
と階層化とを行い知識を相補的に利用する高橋らの研究[4]があり，RoboCup 中型リーグのチームで使用
2. 強化学習の階層化されている．また，環境のダイナミクスが複雑な場
合はいくつかの方策関数を切り替えたり，出力結果
2.1 階層化の目的を統合するなどの行動決定法が工夫されている．例
強化学習の階層化の目的としては，１）粗視化にえば，MOSAIC[3]は環境ダイナミクスの予測関数のよる状態数削減がもたらす学習の高速化，２）状態
分化による環境状態の抽象化であるが，方策はこのや行動の抽象化（または記号化）による戦略的レベ予測関数を用いて与えられるので，方策関数のモジ
ルでの環境ダイナミクスの分析や方策学習を可能に
ュール化とみなすこともできる．
すること，３）方策関数のモジュール化による獲得
本稿で提案する階層化強化学習も上記の１）から知識の再利用，などの３つがあげられる．
Abstract— We propose hierarchical reinforcement learning based on policy gradient methods. Our proposedmodel consists of two layers. The upper layer is a coarsegrained or an abstracted state-space mapped from thelower layer. The learning on the upper layer is for obtaining more rewards from a strategic perspective and needs
the environmental dynamics and policies on the lower
layer. The lower-layer learning is intended to realize a
sub-goal state specified by an optimal policy obtained by
the upper-layer learning. As a special case, our model
deals with cases where states on the two layers are generalized by such stationary probabilistic distribution as a
Boltzmann distribution.

-7-３）を目的としている．

coarse resolution

characteristic space

2.2 階層化の対象
多くの研究では，２つの層からなる階層型モデルが用いられている．例えば，Sutton らの option [1]では，下層が通常の状態空間であり，上層はマクロ行動を表す option を状態とする状態空間である．
option は，option の起動条件，下層の行動決定を行う方策，終了条件の３つで記述される．どの optionを選択するかという方策も上層で定義されている．
環 境 に 関 し て は ， 下 層 で は MDP が ， 上 層 で はSMDP が仮定されている．下層に対して，上層はある程度の行動列が下層で実行された後に制御が戻り，
state spacefine resolution
行動を選択・実行するので，時間的なスケールは下(b)(a)
層とは異なる．上層の時間ステップの単位は確率的Fig. 1 Two-layer modelとなりこれが SMDP を仮定する理由である．
もちろん，階層型強化学習の目的に応じて，何を階層化の対象にするかは異なってくる．例えば，
a’τ
s’τ+1
MOSAIC では下層は連続的な状態空間であり，上層s’τ
として環境ダイナミクスを予測する関数の識別子からなる記号空間を考えている[3]．つまり，上層の各状態はそれぞれ別の予測関数を表現している．各予Ωsp(s)
測関数は，担当する下層の状態が異なり，モジュー
ル化されている．複数のモジュールを考えて，現在
a1s2 a2の状態に応じて切り替えることにより，非線形で複s4s1s3
雑な環境ダイナミクス下での次状態予測をカバーするという考えである．
本稿で提案する階層型モデルも２層からなる．下Fig. 2 Mapping from lower layer into upper layer.
層は通常の状態空間を，上層はそれを粗視化または抽象化（記号化）した状態空間を考える．しかし，考える．上層の状態に作用する行動を a’(∈A’)で表一般性を考えて，上層の状態として何か特定のもの
す．また，下層での（離散）時刻と方策を t, πで，に限定することはしない．下層から上層への状態間上層での（離散）時刻と方策をそれぞれτ, π’で表の写像としては，かなり一般的な形を許すものとす
す．上層の時刻は，上層の状態が変化したときに１る．例えば，単なる粗視化の場合であったり，特徴
ステップだけ進むものとする．この時刻
t と時刻τ
量抽出などのもっと複雑な写像でもよい．また，下との関係をτ=Ωtm(t)で表す．ただし，Ωtm(t)の値は層にも上層にもマルコフ性は特に要求しない．
下層の状態，方策に依存する確率変数である．
ΩFig.1a に粗視化の場合を，Fig.1b に抽象化（記号化）の場合の模式図を示す．Fig.1a は追跡問題におsp(s)により状態空間の粗視化や抽象化（記号化）が，
Ω tm(t)により時間的な抽象化(temporal abstraction)がける格子世界の粗視化を，Fig.1b は上層が特徴量空実現される．Fig.2 に階層モデルの模式図を示す．
間の場合を表している．
3.2 上層の学習：オンライン・コーチ学習
一般的に，下層はエージェントまたはマルチエー
ジェント系の状態を表している．ここでは RoboCup
3.1 階層型モデル
サッカーシミュレーション・リーグを例に，この階前節で述べたように，2 層からなる階層型モデル
層型モデルで行う学習について説明する．次の 2 種を考える．実際に学習対象とする世界の状態 s の状類の学習を考える．ここでは，「オンライン・コー
態空間を S とする．状態 s に作用する行動を a（∈As）とする．状態空間 S を 2 層モデルの下層とする． チ学習」と「オフライン・エージェント学習」と呼ぶことにする．
これに対し，下層の状態 s をある写像Ωsp(s)により最初のオンライン・コーチ学習とは，上層におけ生成される状態 s’（∈S’）を上層の状態とする．写る強化学習である．これは，記号世界における最適像Ωsp は確率的ではなく決定論的な写像をここでは

3.提案手法-8-習することもできる．これは，言わばコーチの頭の中（記号世界上でのシミュレータ上）における戦略
レベルの方策学習である．

方策を強化学習により求め，ゴール状態への最適行
動列や状態列を得るための学習である．この際，上層における環境のダイナミクスを無視して強化学習を行うことも可能であるが，実世界（下層）の環境
ダイナミクスや下層における実際の方策を反映させてないので，せっかく得られた最適方策も机上の空論に帰してしまう可能性がある．
そこで，下層の環境ダイナミクス P(st+1|ht+1)と方策を反映させた上層のダイナミクス P(s’ τ+1 |h’τ+1)を以下のように定義する．ここで，ht は過去(時刻 t-1 まで)の状態行動列を表している．

P ( s′ ht′+1 ) =∑ P (s = s) ∑ ∑ts∈Ω −sp1 ( sτ′ ){st +1} {at }∏ π ( a ; s , h , g ( aτ′ ; sτ′ ) ) P ( s

−1
t∈Ωtm
(τ )

3.3 下層の学習：オフライン・エージェント学習
前節で述べたように，下層の方策は上層での行動に依存すると考える．ここでは，上層において目標とする次状態をサブゴールと見なして，サブゴール
付の方策π(at;st,ht,g(a’τ;s’τ))を下層では考える．
さて，前節 3.2 で強化学習により得られた方策
π’(a’;s’,h’)を用いると上層においてゴールへの最適経路（i.e.報酬が高い経路）を観測，または（環境ダイナミクスがわかっていれば）計算することができる．一般的には最適経路は確率的に与えられ，推移
確率 P0(s’τ+1|s’τ)の形で表現される．この推移確率は
方策π’(a’;s’,h’)と環境のダイナミクス P(s’ τ+1|h’τ+1)と
を用いて，

t

t

t

t +1

ht +1 ) δ ( s 'τ +1 = s′)
(1)

(

) ∑

(

)

ここで，関数δ(X)は命題 X が真であれば１，偽であP0 sτ′ +1 sτ′ = π ′ ( aτ′ ; sτ′ , hτ′ ) P sτ′ +1 hτ′+1 (2)れば 0 の値を取る関数である．P(st=s)としては，例aτ′
えば一様分布を与える．また，下層の方策πは下層の状態 st と履歴 ht だけではなく，上層で選択する行と表される．下層の学習はこの推移確率 P0(s’τ+1|s’τ)
動 a’τと上層における現在の状態 s’τに依存すると仮を実現するように方策π(at;st,ht,g(a’τ;s’τ))を学習する
定する．つまり，上層（記号世界）の抽象的な行動ことを目的とする．すなわち，上層での次状態 s’τ+1を実行するには，その実現のために下層（実世界）を下層の方策中のサブゴール g(a’τ;s’τ)ととれば，下において何らかの具体的な行動を選択する必要があ
層の方策の学習は，下層の各状態において，上層でる．したがって，下層の方策は下層の状態や履歴だ与えられたサブゴールに到達するように下層の行動
けではなく，上層の行動に依存するものと仮定する．
選択を学習するということである．これは，サッカ
その依存性を表現する一つの方法として，本研究ーで言うと，例えば，攻撃側 3 人，守備側 2 人と想では上層における次の遷移先の状態（以下，「サブ定した場面で攻撃側が敵にボールを取られないようゴール」）を与える関数 g(a’;s’)∈S’を用いることににパスを回す Keepaway [8]の練習や，コーナーキッ
する．つまり，上層においてサブゴールを設定し，クやフリーキックからパスを繋いで得点する練習な
それに向かって下層の行動選択を行う方式をここでどの部分的な基本練習に相当する．このときのサブは採用する．例えば，サッカーシミュレーションリ
ゴールは，パス先の味方プレーヤが敵プレーヤよりーグにおいて，下層の行動を，kick（蹴る）, dash
もボールに近いこと（i.e.パス&レシーブが成功）や，（走る）, turn（方向転換）などの基本コマンドとす
ゴール前のフリーでいる味方プレーヤの近辺にボーると，状況に応じてこれらの基本コマンドを選択す
ルを存在させることなどである．つまり，上層で行る必要がある．敵ゴール前へボールを移動させて得った戦略レベルの学習とは異なり，下層ではコーチ
点可能性が高い状態を作り出すとか，敵選手からボが与えた限定された場面とサブゴールをオフラインールを奪ってボールを所有している状態を作り出す
でエージェントが学習する．なお，下層で学習されと言う様に，サブゴールを設定して，その実現へ向た方策は上層での環境ダイナミクスを通して上層のけての行動選択を考えることは本方式の一例である．
方策学習に影響を与える．これは，日頃の部分練習(1)で定義された上層の環境ダイナミクス（状態遷による基本的な協調プレイの精度向上が戦略レベル
移確率）の下で，実戦を通して上層における戦略レ
での方策へ影響し，高度な協調プレイの実現や学習
ベルでの最適方策π’(a’;s’,h’)を方策勾配法で学習すに結びつくと考えると直観的に理解しやすい．
ることができる．ただし，この際，学習結果は下層における方策πに依存する．また，もし，多数回の3.4 下層の学習則
実戦例から観測により上層における状態遷移確率の上層の環境ダイナミクスは(1)のように下層の方策
データを得ることができれば，下層を切り離して上π(at;st,ht,g(a’τ;s’τ))を用いて表すことができると仮定
層だけの記号世界の中で，最適方策π’(a’;s’,h’)を学した．そこで，(1)を用いて(2)の推移確率を表すと-9-

P ( s′ sτ′ ) =∑ P ( s = s )∑π ′ ( aτ′ ; sτ′ , hτ′ )ts∈Ω −sp1 ( s′ τ )aτ′∑ ∑ ∏ π ( a ; s , h , g ( aτ′ ; sτ′ ) ) P ( s{st +1} {at }ここで，(8)の右辺の種々の平均操作を Eπ,π’[…]で表すことにする．すなわち，

t

( )

−1
t∈Ωtm
τ

t

t +1

t

ht +1 )δ ( sτ′ +1 = s′)Eπ ,π ′ [ X ] =P π (σ ) ⋅ X∑ P ( s = s )∑ π ′ ( aτ′ ; sτ′ , hτ′ )∑σs∈Ω −sp1 ( s ′ τ )

t

(3)

aτ′

(11)
と定義すると，(6)は，となる．本研究では，(2)と(3)との誤差を表す量として，次のカルバック・ライブラー情報量(Kullback-Leibler divergence)G ( sτ′ ) ≡ ∑ P0 ( s′ sτ′ ) ln ⎣⎡ P0 ( s′ sτ′ ) P ( s′ sτ′ )⎦⎤

(4)

s′

を最小とするように，方策π(at;st,ht,g(a’τ;s’τ))中のパ
ラメータθを学習により求める方式を考案した．下層の方策を含むのは(3)だけなので，∂G ( sτ′ )∂=−∑ P0 ( s′ sτ′ ) lnP ( s′ sτ′ )
∂θ
∂θ s′
= −∑
s′

P0 ( s′ sτ′ ) ∂P ( s′ sτ′ ) ∂θP ( s′ sτ′ )4.状態生起が確率分布で表される場合の階層型強
化学習

(6)

4.1 スピン系とマルチエージェン系
大規模なマルチエージェント系のように，状態
空間や行動空間が極めて大きい場合には，個々の状
態遷移を学習するよりは，系全体の統計的な振る舞いを学習した方が良い場合がある．例えば，系全体の性質を特徴付ける特徴量の時間的な平均値や分散，相関などの値に対して報酬を与えるという形式の強化学習である．このとき重要なのは系の状態が生起される確率であり，これがある定常分布 P(s)で与えられる場合を考える．例えば，統計物理学の分野で出てくる Ising スピン系では，系のエネルギーE と
温度 T とを用いた Boltzmann 分布で生起確率が与えられる（正準集合）．この状態を「熱平衡状態」と呼ぶが，人工的に作り出すには，メトロポリス法や熱浴法（ギブス・サンプラー）などの方法がある[9]．
Ising スピン系とマルチエージェント系との対応付けを考えると，スピンの状態がエージェントの状
態に，スピンの次状態の選択（試行変形など）がエージェントの行動選択に，スピンの状態遷移確率（受理確率など）がエージェント周囲の環境ダイナ
ミクスに対応する．スピン系のエネルギー関数 E にはスピン間の相互作用が含まれているが，これはエージェント間の相互作用と考えることができる．また，エネルギー関数Ｅの学習は方策関数の学習に，エネルギー関数中のスピン間相互作用の強さなどのパラメータは，方策関数中のパラメータに対応する．
今，3 章で提案した階層型モデルにおいて，下層の状態生起がある定常分布 Plow(s)で与えられると仮∂P ( s′ sτ′ ) = ∑ P ( st = s )∑ π ′ ( aτ′ ; sτ′ , hτ′ )∂θaτ′s∈Ω−sp1 ( s′ τ )∂∑ ∑ ∏ π ( at ; st , ht , g ( aτ′ ; sτ′ ) ) P ( st +1 ht +1 )δ ( sτ′+1 = s′)∂θ {st +1} {at } t∈Ωtm−1 (τ )(7)=

∑ P ( s = s )∑π ′ ( aτ′ ; sτ′ , hτ′ )ts∈Ω −sp1 ( s ′ τ )

aτ′

(8)

⋅ ∑ P (σ ) ∑ eθ ( t ) δ ( sτ′ +1 = s′)
π

σ

−1
t∈Ωtm
(τ )

と表される．ただし，σは上層の状態が s’τから次状
態 s’τ+1 へ遷移するまでの下層での軌跡（状態列{st+1}と行動列{at}）を表し，
Pπ (σ ) ≡ ∑ ∑ ∏ π ( a ; s , h , g ( aτ′ ; sτ′ ) ) P ( s∑σ−1{st +1} {at } t∈Ωtm
(τ )

t

t

t

t +1

ht +1 )

(9)である．e θ (at;st,ht,a’τ)は方策勾配法における特徴的
適正度[5]に対応し，以下で定義されている．

eθ ( t ) = eθ ( at ; st , ht , aτ′ ) ≡(12)と表される．右辺の Eπ,π’[…]内のδ(s’τ+1=s’) (∈{0,1})
は，サブゴール s’を実現するための基本練習（サブタスク）を，方策勾配法を用いた強化学習により行う際の報酬と見なすことができる． (12)の勾配を計算することにより，下層の方策中のパラメータ θを更新する学習方式が考えられる．

(5)

ここで，(3)より，⋅⎡⎤
P0 ( s′ sτ′ )∂G ( sτ′ )= −∑Eπ ,π ′ ⎢δ ( sτ′ +1 = s′) ∑ eθ ( t ) ⎥−1∂θs′ P ( s′ sτ′ )
t∈Ωtm
⎢⎣
⎥⎦
(τ )

∂
ln π ( at ; st , ht , g ( aτ′ ; sτ′ ) )∂θ(10)- 10 -

定する． 例えば，マルチエージェント系のエネル
ギ ー 関 数 Elow(s;θ) と 温 度 パ ラ メ ー タ T を 用 い た
Boltzmann 分布
Plow ( s ) ≡e− Elow ( s ;θ ) T∑e− Elow ( x ;θ ) T

Δθ ′ = −(13)などが考えられる．
次に，下層の状態 s から上層への状態 s’への写像
を，より一般的に条件付確率 P(s’|s)で与えるものとする．このとき，上層の状態 s’の生起確率は次の定常分布で表すことができる．
Pup ( s′) = ∑ P ( s′ s )Plow ( s )

(14)

s

4.2 上層の学習：報酬の期待値を増大させる学習
下層を粗視化あるいは抽象化（記号化）した上層の状態 s’において，生起される状態に対して報酬
r(s’)を与える．学習の一般性を考えて，状態 s’から
計 算 さ れ る 系 の 特 徴 を 表 す 関 数 A(s’) の 期 待 値<A(s’)>up を所望の値 A*に制御するための強化学習を考える．これは下層に生起する状態に対して一種の制約を加えることに相当する．単に<A(s’)>up を増大させたいだけであれば，A*を十分大きな値に選んでおけば良い．また，A(s’)はベクトルでも構わない．
特別な場合として，上層の状態 s’そのものが系の特徴を表す変数やベクトルであっても良く，系の特徴量に対して，直接，報酬 r を与え，その期待値を増大させる学習の場合を含んでいる．
そこで，A(s’)と A*との類似度 d(A, A*)を考え，類似度 d の単調増加関数 r(d)を報酬として与える強化学習を考える．ただし，上層の状態 s’の生起確率
を Pup(s’) と す る ． こ こ で は 例 と し て ， 次 のBoltzmann 分布で与えられるものとする．
e− Eup ( s′;θ ′) T ′

∑e

(18)

− Eup ( x ;θ ′) T ′

4.3 下層の学習：上層の分布を実現するための学習
前節 4.2 の上層の学習により，報酬の期待値を増大させた上層の分布を得ることができる．これをP0up(s’)とおく．しかし，上層の分布と下層の分布との間には，(14)の拘束条件がある．これを完全に無視して学習しても，それは机上の空論に終わる可能性が高い．そこで，例えば，上層の学習の際に，(14)の拘束条件を上層のエネルギー関数 Eup の中に反映させておくとか，(15)と(14)の分布との距離をある程度保つなどの方法が考えられる．これは，3.2
節で上層におけるオンライン・コーチの学習を行う
際に，下層の環境ダイナミクスと方策とを考慮したことに対応する．
本節では，何らかの方法で上層の分布 P0up(s’)が与えられたときに，それを(14)の拘束の下で実現することを目的とする下層の学習を考える．そこで，２つの分布関数間の近さを測るために 3.4 節で用いた
カルバック・ライブラー情報量，G ( Pup0 , Pup ) ≡ ∑ Pup0 ( s′) ln ⎡⎣ Pup0 ( s′) Pup ( s′) ⎤⎦s′∈S ′∂G ( Pup0 , Pup )∂θ=∂∑ Pup0 ( s′) ln ⎡⎣ Pup0 ( s′) Pup ( s′)⎤⎦ (20)∂θ s′∈S ′Pup0 ( s′) ∂Pup ( s′)s′∈S ′ Pup ( s′) ∂θ

= −∑

(21)

(15)
(14)を代入して Pup (s’)を Plow(s)で表すと，Pup0 ( s′) ∂∑ P ( s′ s ) Plow ( s )s′∈S ′ Pup ( s′) ∂θ s

= −∑以下では，勾配法を用いて報酬の期待値 E[r]を極大にすることを試みる．そこで勾配を計算すると，∂E [ r ]∂=∑ r ( d )Pup ( s′)∂θ ′∂θ ′ s′(19)を考える．次に，この勾配を計算すると

x∈S ′

=−

⎛ ∂E ( s′;θ )∂Eup ⎞r ( d ) ⎜ up
−
⎟
T
∂θ ′
∂θ ′ T ⎠⎝ε

ただし，ε(>0)は学習係数である．

x∈S

Pup ( s′) ≡となる．さらに，報酬期待値の勾配(17)に対して確率的勾配法を用いると，上層のエネルギー関数中のパラメータθ’に関する以下の学習則を得る．

(16)⎛ ∂E ( s′;θ )∂Eup ⎞1r ( d ) ⎜ up−
⎟ Pup ( s′) (17)
∑
′
′
T s′
∂
∂
θ
θ
T ⎠
⎝

(22)

Pup0 ( s′)∂= −∑Plow ( s ) ⋅ P ( s′ s )ln Plow ( s )∑∂θs′∈S ′ Pup ( s′) s(23)
こ こ で ， 下 層 の 分 布 Plow(s) に よ る 期 待 値 操 作 を
Elow[X]≡Σs Plow(s)X で定義すると，- 11 -

∂G ( Pup0 , Pup )∂θ

Pup0 ( s′)= −∑Elow ⎡⎣ P ( s′ s ) eθ ( s ) ⎤⎦s′∈S ′ Pup ( s′)

本稿で提案した階層型強化学習の具体的な応用例について研究を進めていく予定である．

参考文献[1] R.S. Sutton, D. Precup, and S.P. Singh, “Between
MDPs and semi-MPDs: A framework for temporal ab∂
straction in reinforcement learning,” Artif. Intell.,eθ ( s ) ≡ln Plow ( s )(25)vol.112, no.1-2, pp.181-211, 1999.
∂θ
[2] A.G. Barto and S. Mahadevan, “Recent Advances in
Hierachical Reinforcement Learning,” Discrete Eventと定義した．(24)は，(12)と比較すると，下層 s から
Dynamic Systems: Theory and Applications, 13, pp.41上層 s’への条件付確率 P(s’|s)の値(∈[0,1])を報酬と77, 2003.
する強化学習と見なすことができる．(24)の勾配を[3]
杉本徳和，鮫島和行，銅谷賢治，川人光男，
用 い て ， 上層 の 分 布 P0up(s’)の 下 での 下 層 の 分布
“MOSAIC モデルにより環境を抽象化する階層型
Plow(s)中のパラメータθを更新する学習方式が考えら強化学習”，電子情報通信学会論文誌 D, vol.J89れる．なお，下層の分布 Plow(s)として(13)を代入し
D, no.7, pp.1577-1587, 2006.
た学習則は，我々が以前提案した「2 層確率場モデ[4] 高橋泰岳，浅田稔，“階層型学習機構における状態行動空間の構成”，日本ロボット学会誌，ル」[10]の学習則と一致する．2 層確率場モデルは，
vol.21, no.2, pp.164-171, 2003.
Boltzmann マシンを特殊例として含むより一般的な[5]
R.J. Williams, “Simple Statistical Gradient- Following
確率学習モデルであり，画像修復や組合わせ最適化
Algorithms for Connectionist Reinforcement Learn問題への適用例がある[11][12]．
ing,” Machine Learning, vol.8, pp.229-256, 1992.
本章で述べた階層型強化学習の応用例としては， [6] 五十嵐治一，石原聖司，木村昌臣，“非マルコ
例えば，大規模な組合わせ最適化問題を解く際に，フ決定過程における強化学習―特徴的適正度の統粗視化した上層で最適解を求めておき，それを拘束
計 的 性 質 ― ” ， 電 子 情 報 通 信 学 会 論 文 誌 D,
vol.J90-D, no.9, pp.2271-2280 , 2007．
条件として下層において最適解を求めることなどが[7]
M. Riedmiller and T. Gabel, “ On Experiences in a考えられる．また，人間社会をモデル化した大規模Complexand Competitive Gaming Domain な人工社会シミュレーションにおける制御や学習問
Reinforcement Learning Meets RoboCup-, “ Proceed題へも適用が期待できる．
ings of the 2007 IEEE Symposium on Computational(24)と表される．ただし，5.まとめ
本稿では，方策勾配法による階層型強化学習の定式化を試みた．提案した階層モデルは 2 層からなる．上層は下層の状態を粗視化または抽象化（記号化）した状態を表し，下層から上層への状態間の写像はシステム設計者が与える．学習は，上層で行う
オンライン・コーチ学習と下層で行うオフライン・
エージェント学習との 2 種類に分かれる．前者は戦略レベルの強化学習であり，このとき用いる上層での環境ダイナミクスは下層（実世界）の環境ダイナ
ミクスと方策に依存する．一方，後者は戦略レベルの強化学習で得られた最適方策が生成する状態列や状態推移確率を実現するように，下層の方策を学習する．具体的には，サブゴールとして上層の次状態を与えたときにそれを実現するための部分練習（サブタスク）の学習である．したがって，下層の方策
はサブゴールごとに用意する．この 2 種類の学習をループさせることにより，さらに報酬期待値を増大させることが期待できる．
また，特別な場合として，2 層の状態の生起確率が定常分布で表される場合の階層型モデルを考え，同様な階層型強化学習の定式化を行った．今後は，Intelligence and Games (CIG2007), pp.17-23, 2007.
[8] P. Stone, G. Kuhlmann, M.E. Taylor and Y. Liu,
“Keepaway Soccer:From Machine Learning Testbed to
Benchmark,” In A. Bredenfeld, A. Jacoff, I. Noda and
Y. Takahashi (Eds.), “RoboCup 2005:Robot Soccer
World Cup IX,” pp.93-105, Springer-Verlag, New
York, 2006.
[9] 伊庭幸人，種村正美，大森裕浩，和合肇，佐藤整尚，高橋明彦，“計算統計 II：マルコフ連鎖モンテカルロ法とその周辺”，第Ｉ部第３章，岩波書店，2005.
[10] 五十嵐治一, 川人光男，"標準正則化理論の２層確率場モデルへの拡張", 電子情報通信学会論文
誌 D-II, vol.J75-D-II, no.1, pp.157-161, 1992.
[11] 五十嵐治一, 川人光男，"２層確率場モデルによる逆問題の解法 -エッジ情報を用いた画像修復
へ の 応 用 -", 電 子 情 報 通 信 学 会 論 文 誌 D-II,
vol.J77-D-II, no.6, pp.1104-1113 , 1994.
[12] 五十嵐治一，"２層確率場モデルを用いた組合わせ最適化問題の解法 - 平均場近似-", 電子情報通信学会論文誌 D-II, vol.J76-D-II, no.9, pp.20932101, 1993.

- 12 -

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

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

非定常環境下における自己位置推定法
Monte Carlo Localization under Unsteady Environment
辻塚 弘一，○大橋 健
Koichi Tsujitsuka, *Takeshi Ohashi
九州工業大学大学院情報工学研究科1，九州工業大学情報工学部
Graduate School of Kyushu Institute of Technology, Kyushu Institute of Technology
tu3@ohashi-lab.bio.kyutech.ac.jp, ohashi@bio.kyutech.ac.jp[Crisman, 2002] [上田, 2005]ことで自己位置ズレ状態をAbstract— This paper presents an improved Monte
Carlo Localization (MCL) which is a method for mobile
robot localization and updating an environment map.
Under steady environment (i.e. landmarks never move),
MCL only requires a method for recovery of estimation
error of its position. However, under unsteady environment (i.e. landmarks may move), MCL must recover a
gap between the position of landmarks and an environment map. MCL requires not only the method of estimation error of its position but also a method of updating
environment map. Therefore, we propose the method of
updating environment map which consists in deciding bymajority. Experimental results show that our method
successfully performed environment map rebuilding.

解消する．

Figure 1: Statement transaction diagram of the MCL

1. はじめに

今後，ロボットが動作することになる非定常環境
下では自己位置ズレだけではなく，目印位置ズレも起こり得る（Figure 1）．実装した環境地図の細かい寸法が異なる際の問題[友納, 2002]だけでなく，人の手によって目印位置が変更される可能性がある．目印
位置ズレ状態を解消するためには，環境地図を更新する必要がある．しかし，通常の MCL は自己位置ズ
レのみを想定しているため，目印位置ズレ状態から遷移するには環境地図を更新する必要があるにも関
わらず，MCL リセットを行い続け，目印位置ズレ状態を解消することができない．
本論文では，各種位置ズレの原因を見分け，MCL
リセットもしくは環境地図更新を適切に行う自己位置推定手法の提案し，シミュレータを用いて評価を行う．

近年，既知環境下における自律移動型ロボットの自己位置推定手法として，Monte Carlo Localization（MCL）[Dellaert, 1999] [Fox, 1999] [Fox, 2003]が注目されている．この手法はまず，環境中にパーティクル（ロボット姿勢（x，y，θ）及びロボットの存在確率
w の 4 つのパラメータを持つ）をあらかじめ分布させておく．そして，環境地図（目印の位置を記載）と入力されたセンサ情報から，ベイズの公式を用いてパーティクルの重みを変更することでロボット姿
勢を推定する．現在，RoboCup サッカー 4 足リーグなど，目印位置が変化しない環境（定常環境）で多く用いられている．今後，家庭環境など（非定常環境）で人々の手伝いを迅速かつ確実に行うために，
MCL の使用が期待されている．
MCL は，なんらかの原因でベイズの公式が適用不可能となる状態に遷移する可能性がある．定常環境下における主な原因として挙げられるのが，自己位置ズレである．これは，ロボットが人間等によって強 制 的 に 移 動 さ せ ら れ る kidnapped robot problem[Gutmann, 2002] [Thrun, 2001]や，ロボット自身がスリップや他の物体と衝突することで起こり得る．これにより，真のロボット姿勢の周囲にパーティクルが存在しない状態となるため，パーティクルを再分布させる（MCL リセット）[Gutmann, 2002] [Lenser, 2000]
1

2. 2 つの改良した MCL を用いた環境地図更新
前述したように，各種位置ズレを見分けなければ，
MCL リセットを行うべきなのか，環境地図更新を行うべきなのかを判断することができない．ここで，予備実験として以下の 2 つを行った：1. MCL リセッ
トを行いながら周囲の目印を視認し，MCL リセットの挙動を調査；2. MCL リセットを行わずに周囲の目印を視認し，相対位置の確からしい目印数を調査．
それぞれの結果を Table 1 及び Table 2 にまとめた．

現在は、日立製作所。
1- 13 -

Table 1: behavior of the MCL reset
原因
自己位置ズレ
目印位置ズレ

自己位置ズレ+
目印位置ズレTable 2: Feature of the landmarks around the robot

MCL リセットの挙動（基本的に）短期間に一回発生
・短期間に複数回発生
・位置ズレしている目印を見た際に発生するとは限らない
・短期間に複数回発生
・位置ズレしている目印を見た際に発生するとは限らない（※1，※2）
原因
相対位置の確からしい目印数
自己位置ズレ少ない
目印位置ズレ多い
自己位置ズレ少ない+
目印位置ズレ
※1 同時期に多くの目印が移動しない場合に限る※2 設置してある目印数が多い場合に限る(a) perticles of MCL(b) robot and landmarks are in the room
Figure 2: The robot doesn’t know the fact that one landmark has been moved in the direction of the white broken arrow(a) perticles of MCL(b) robot and landmarks are in the room
Figure 3: The robot detects that the landmark’s position is suspicious(a) perticles of MCL(b) robot and landmarks are in the room
Figure 4: The robot is rotating counterclockwise to observe other landmarks in the white circles

2- 14 -

n： MCL のパーティクルの indexw： MCL の各パーティクルの重みλ： センサ等誤差許容範囲（cm）
Sb の閾値： exp（-1.0）

Table 1 及び Table 2 から，各種位置ズレを MCL
リセットの発生回数と相対位置の確からしい目印数で判断することが可能であると言える．これらの基準を得るには，一方では MCL リセットを行い，もう一方では MCL リセットを行わない必要があるが，1 つの MCL では同時に基準を得ることができない．
そこで本論文では，2 つの改良した MCL を用いる手法を提案する．環境地図を更新するか否かの判断
手法の具体的な流れは以下の通りである： 1. 目印
が人などの手によって動かされる（Figure 2）；2. ロ
ボットが移動中に，動かされた目印を視認する（Figure 3）；3. 目印との相対位置がおかしいことを検知する；4. 周囲の確からしい目印を用いて自己位置推定する（Figure 4）；5. おかしな位置にある目印を視認し，MCL リセットが発生するかを確認す
る；6. 手順 4.及び手順 5.を複数回繰り返す；7. 一定
時間内に MCL リセットが複数回発生すれば環境地図を更新し，目印位置ズレを解消する．そうでなけ
れば，MCL リセットを行い，自己位置ズレを解消す
る．
本提案手法を用いることで，ロボット自身が環境
地図を更新することは可能となる．しかし，本手法では多数決を用いて解決していることになるため，信頼度は以下の要素に依存する： 1.同時期に移動する目印の数；2.設置してある目印数．将来的に，屋内の物体（家具など）を目印とした自己位置推定を行うには，本提案手法のみでは不十分であると考えられる．本手法の信頼度を上げるために，次章で改善案を提案する．

従来の式では，目印の位置が確からしいかどうかを λ のみで判断していた．この式では，物体毎の移動範囲を考慮していないため，本論文では式(1)を改良した式（2）を提案する．式（2）を用いることにより，物体毎に異なる移動許容範囲を設定することが可能となる．

（2）
Sb(i) ：目印の評価値（0.0 〜 1.0）b(i) ： 目印の座標i： 目印の index
c(n) ： 各パーティクルから算出した目印座標n： MCL のパーティクルの indexw： MCL の各パーティクルの重みλ： センサ等誤差許容範囲（cm）µ： 目印毎の移動範囲（cm）
Sb の閾値： exp（-1.0）
前章で提案した自己位置推定及び環境地図更新手法の信頼度を上げるために，物体毎の移動範囲を基準としていくつかの制約条件を設けている。まず，
自己位置推定については，移動範囲が 100.0cm 未満の目印のみ使用する．これは，椅子やゴミ箱などの頻繁に移動し得る物体を使用しないことを想定している．また，移動範囲が 0.0cm の物体から得られる情報は必ず信用する．これは，壁や柱などの移動することがない物体を想定している．例えば，冷蔵庫のドアは開閉により移動するが目印として使えることをになる．
次に，環境地図更新については，おかしな位置にある目印を見た際，その目印よりも移動範囲の狭い
目印の情報のみを用いて環境地図を更新すべきかど
うかを判断する．これにより，多数決の信頼度が向上すると考えられる．

3. 物体の移動許容範囲を考慮した自己位置推
定法
家具などの物体は，種類毎に移動し得る範囲が異なる．例えば，椅子やゴミ箱などは比較的人の手によって動かされやすい．一方，壁や柱が移動することはほぼなく，また，洗濯機なども移動するとは考えにくい．つまり，各物体には自己位置推定に用いるべきか否か，環境地図を更新すべきものか否かに分類する必要があると考えられる．通常の MCL は目印が移動することが考慮されていないため，本論
文ではそれぞれが移動し得る範囲（移動範囲）を考慮した自己位置推定法を提案する．
通常の MCL は，目印の位置がおかしいかどうかを式（1）で判断する[三島, 2005]．

4. シミュレーション

（1）
Sb(i)
b(i)
i
c(n)

： 目印の評価値（0.0 〜 1.0）
： 目印の座標： 目印の index： 各パーティクルから算出した目印座標3- 15 -

本提案手法の環境地図更新における精度測定についてシミュレータを用いて検証する．シミュレー
タは，ODE(Open Dynamics Engine)[ODE, 2000]を用いて実装されており，家庭環境等中でのロボットの動作を確認することができる．ここでは㈱安川電機製移動台車ロボットを再現し，このロボットに解像
度 640 x 480，水平・垂直画角 77.3°のカメラ 1 台を搭載した．また，自己位置推定用の目印として，
RoboCup サッカー 4 足リーグで使用されている
Beacon を模した物を使用した（Figure 5）．

4.2. 環境地図更新誤差
本提案手法の環境地図更新誤差及び処理時間の測定を行った．各 Beacon の初期配置は Figure 8 の通りである．ロボットが自己位置推定を行った後，Beacon_RP（Figure 7）を移動し，環境地図更新を行う．Beacon_RP の移動後の位置は Figure 9〜Figure 12の 4 通りであり，それぞれテスト A〜テスト D とする（Figure 13）．詳しい条件は以下の通りである．

Figure 5: Simulator （robot and beacons）

4.1. システム概要・実装
本論文で提案した自己位置推定システムは，シミュレータ中のロボットと TCP で接続し，移動命令等の送信し，シミュレータ上のカメラの映像を受信す
る．この自己位置推定システムは，次のように動作する： 1. シミュレータ上のロボットが撮影したカメラ画像を取得する；2. カメラ画像に画像処理を施し，Beacon が写っているのであれば，Beacon までの距離・角度を計算する；3. 得られた Beacon 情報から自己位置を計算し，おかしな位置に Beacon が見えたのであれば，環境地図を更新するかどうかを判断する；4. ロボットの移動を制御する．
MCL のパーティクル数は 500 個とし，センサ等誤差許容範囲 λ は 25.0cm とした．これは，予備実験により，Beacon までの距離測定誤差が Figure 6 の結果となったためである．環境地図を更新するかどうかの判断には，3 分以内に 5 回 MCL リセットが発生した場合とした．これにより，各種センサ誤差やオド
メトリ誤差により MCL リセットが発生する場合を考慮する．

Figure 7: Beacon_RP

Figure 8: Initial positions of a robot and landmarks（Beacon_RP in the white circle will be moved）[実験条件]
 Beacon の移動範囲
 Beacon_RP： 50.0（cm）
 その他の Beacon： 30.0（cm）

ロボットと Beacon_RP 間の距離及びテスト名｛=（50.0cm，テスト A）,（100.0cm，テスト B）,（150.0cm，テスト C）,（200.0cm，テスト D）｝

テスト A〜テスト D をそれぞれ 500 回ずつ測定（計 2000 回測定）
ロボットは座標（0.0，0.0）上で反時計周りに回転 1 回転 / 約 30（sec）


Figure 6: Sensor errors of the beacons’positions4- 16 -

Figure 9: Beacon_RP is moved in the direction of awhite broken arrow（a distance between the
robot and Beacon_RP is 50.0cm）

Figure 12: Beacon_RP is moved in the direction of awhite broken arrow（a distance between the robot
and Beacon_RP is 200.0cm）

Figure 13: Statement transaction diagram of theexperiments
Figure 10: Beacon_RP is moved in the direction of awhite broken arrow（a distance between the
robot and Beacon_RP is 100.0cm）

得られた環境地図更新誤差及び処理時間はFigure 14 及び Figure 15 の通りである．移動した
Beacon までの距離が遠くなればなるほど，誤差が増加しているが，これは Beacon までの距離測定誤差だけでなく，角度測定誤差の影響も起因している．
処理時間は，各テストにおいて平均約 160sec かかっている．これは，本提案手法で各種位置ズレの原因を判断する際，ロボットがその場回転を 5 回行うように設定しており，1 回転に約 30sec かかるためである．
環境が変化したと判断するための時間（ここでは回転数）が長いとその間 MCL リセットを繰り返すことになるが，この時間が短すぎると雑音の影響を受けやすくなる．ここでは，明らかに環境が変化したと判断できるように長めに設定している．

Figure 11: Beacon_RP is moved in the direction of awhite broken arrow（a distance between the robot
and Beacon_RP is 150.0cm）

5- 17 -

た．この提案手法について，シミュレータを用いて，動作検証を行ったところ，動的環境下において環境
地図を適切に更新することができた．本提案手法は，目印の移動には対応可能であるが，目印の増加・減少には対応できていない．今後はこの問題を解決する必要があると考えられる．また，家庭環境など実際の非定常環境において実証試験を行い安定性の検証を行いたいと考えている．

参考文献[Dellaert, 1999] F. Dellaert, et al.: “Monte Carlo Localization
for Mobile Robots,” In Proc. of IEEE ICRA,
pp.1322–1328, 1999.
[Fox, 1999] D. Fox, et al.: “Monte Carlo Localization: Efficient

Figure 14: Error results of the experiments

Position Estimation for Mobile Robots,” In Proc. of
AAAI, pp.343–349, 1999.
[Fox, 2003] D. Fox: “Adapting the Sample Size in Particle Filters Through KLD-Sampling,” International Journal of
Robotics Research, vol.22, no.12, pp.985–1004, 2003.
[Gutmann, 2002] J. Gutmann and D. Fox: “An Experimental
Comparison of Localization Methods Continued,” In
Proc. of IEEE/RSJ IROS, pp.454–459, 2002.
[Thrun, 2001] S. Thrun, et al.: “Robust Monte Carlo Localization for Mobile Robots,” Artificial Intelligence Journal,

Figure 15: Processing time of the experiments

vol.128, no.1–2, pp.99–141, 2001.
[Lenser, 2000] S. Lenser, et al.: “Sensor Resetting Localization
for Poorly Modeled Robots,” In Proc. of IEEE ICRA,
pp.1225–1232, 2000.

5. 考察[Crisman, 2002] Z. Crisman, et al.: “Team description: UW

本提案手法を実装したシステムの実行結果より，
最大 14.0cm 未満の誤差で環境地図を更新することができた．これにより，非定常環境下においても信頼度の高い自己位置推定を行うことが可能になったと考えられる．
処理時間については，平均して約 160sec かかっており，実環境での使用に耐えられないと考えられる．この問題が起きた原因は，環境センサとしてカメラを 1 台しか搭載していないことによる．本提案
手法は周囲の目印を視認し，多数決を取る手法であるため，カメラ 1 台では周囲を視認する時間が必要となってくる．そこで，全方位カメラや複数台のカメラを使用するなど，広い視野を確保して多数決が早めに起きるようにすることで，問題を解決できると考えられる．また，レーザレンジファインダなど
他の環境センサと組み合わせることも有効であると考えられる．

Huskies-02,” In Proc. of International RoboCup Symposium, CD-ROM, 2002.
[上田, 2005] 上田隆一，新井民夫，浅沼和範，梅田和昇，
大隅久 :“パーティクルフィルタを利用した自己位置推定に生じる致命的な推定誤りからの回復法” 日本
ロボット学会誌，Vol.23，No.4，2005.
[友納, 2002] 友納 正裕，油田 信一: “不正確さを許すマップにおける移動ロボットの自己位置推定” 日本ロボット学会誌，vol.20, no.4, pp.425–436, 2002.
[三島, 2005] 三島拓朗，井上淳，小林隼人，石野明，篠原
歩: “モンテカルロ位置同定法による四足ロボットの自己位置同定とロボットサッカーへの応用” 火の国
情報シンポジウム 2005, 2005.
[ODE, 2000]
2000-2007

6. おわりに
本論文では，目印が移動し得る動的環境下において，各種位置ズレの原因を判断し，MCL リセット
もしくは環境地図更新を適切に行う手法を提案し

6- 18 -

Open Dynamics Engine. http://ode.org/,人工知能学会研究会資料
JSAI Technical Report
SIG-Challenge-A801-4 (5/2)

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

安全領域：SSL リーグにおける守備アルゴリズムの評価指標
Safety Region: an index to evaluate defense algorithm in Small Size League

前野

順也

村上

和人

成瀬

正

Junya MAENO Kazuhito MURAKAMI Tadashi NARUSE

愛知県立大学情報科学部
Aichi Prefectural University

is041039@cis.aichi-pu.ac.jp, {murakami, naruse}@ist.aichi-pu.ac.jp

Abstract

例えば potential ﬁelds[1] や playbook[2] は行動決定を行うとともに、守備ロボットの台数も決める。

This paper proposes a concept of “safety region”
which is deﬁned as a region that the opponent’s

本稿では、行動決定、特に守備ロボットの台数を決定するための新しい概念として安全領域を導入すshoot from the inside of the safety region can beる。そして、安全領域に基づいて守備ロボット台数
blocked by the teammate robot(s). The shape ofをどのように決定するかについて議論する。安全領the safety region varies depending on the number of
域とは、その領域内から打たれたシュートを、守備戦
defending robots and the defending strategy. The
略に従って適切に配置された守備ロボットがシュー
safety region can be used as an index to evaluate
トを防ぐことができる領域として定義する。安全領
the defending strategy. Inversely, it can be used as域の形状は、守備ロボットの台数と守備戦略によっ
an index to decide the number of defending robotsて変化する。
according to the situation of match. Since it is diﬃ安全領域は守備戦略を評価する指標として使用で
cult to get the accurate safety region, we propose alきる。逆に、試合状況によって守備ロボットの台数
gorithms that compute the approximated safety reを決定するための判断指標としても使用できる。安gion. The algorithms are given for the single shoot
全領域を厳密に求めることは困難であるため、本論
and the cooperative shoot, respectively. We also
文では近似解法を提案する。その解法は単独シュー
discuss the availability of the safety region as an
トと連携シュートそれぞれに対して与えられる。そindex of strategy evaluation and the availability of
して、近似解法の有効性および安全領域の指標とし
the approximated safety region.
ての有効性について議論する。

1

はじめに

2

昨今の RoboCup 小型リーグでは、攻撃と守備に定義
安全領域の概念は単純である。安全領域は、その用いられる戦略はより高度なものとなり、試合状況

領域内から打たれたシュートを守備戦略に従って適に合わせて攻守に用いるロボットの台数を変える戦

切に配置された守備ロボットがシュートを防ぐこと

略もよく用いられるようになった。典型的な戦略、

1- 19 -

ができる領域として定義する。また、安全領域では複数の場合は、j = r，j = l とした場合の式 (1) をない領域については非安全領域とする。

それぞれ、いずれかのロボットが満たした場合に bは安全領域内の点とする。また、||ri − pj,i || − R < 0以降の議論では、第一歩として、チップシュートとカーブシュートについては考慮しないものとする。 を満たす場合、同様に b は安全領域内の点であるとする。

安全領域の計算3

3.2

安全領域の計算はどのようなシュート動作 (例えば単独シュートや連携シュート) を行うか、また、ど連携シュート時における安全領域の計算のような守備 (例えば守備戦略や守備ロボットの台

2 台の相手ロボットがダイレクトプレイなどの連数) を行うかによって異なる。典型的な連携シュー

携を伴うシュートを行う場合、守備ロボットがゴールを守るためにはパスを行うロボットについても考1

トの例としてはダイレクトプレイ が挙げられる。

慮しなければならない。この場合、安全領域の計算を行うためには、パス時間についても考慮しなけれ

3.1

単独シュート時における安全領域の計 ばならない。
算
時刻 t におけるボールの座標を b、シュートするロ
ボットの座標を e とし、ri を守備ロボット i の座標と守備ロボットは守備戦略に従って適切な座標に移する。L′r ，L′l を，それぞれ，始点を e、終点をゴー動するものとする。時刻 t におけるボールの座標を

ルの両ポストとする線分とする。ゴールキーパーはb とする。時刻 t における守備ロボット i の座標を ri
ディフェンスエリア内に位置し、ディフェンスサー
とする。Lr ，Ll を，それぞれ，始点を b，終点を左
クルに沿って動くものとする。他の守備ロボットは右のゴールポストとする線分とする。守備ロボット
ディフェンスエリアの外側に位置し、ディフェンス
は多くの場合 Lr と Ll が作る領域の中に存在する。
サークルに沿って動くものとする。そのとき、pr,i
pr,i ，pl,i をそれぞれ ri から Lr ，Ll に降ろした垂線と pl,i をそれぞれロボット i が移動する線上と L′r ，との交点とする。||ri − pj,i || − R ≥ 0 を満たす場合
L′l との交点とする。時刻 t において、パスを行うロに、以下の式をそれぞれの守備ロボット i に対してボットがボールを保持し、ダイレクトプレイを行う
計算する。
場合に以下の式によって安全領域の計算を行う。

||b − pi,j ||>v√

2(||ri − pj,i || − R),ai(j = r, l)||b − e|| ||e − pi,j ||
+
>
vp
vs
√
2(leng(ri − pj,i ) − R)
,
ai

(1)

(j = r, l) (2)式中の v ，ai ，R は、それぞれ、シュート速度、ロ
式中の vp ，vs ，ai ，R は、それぞれ、パス速度、

ボット i の加速度、ロボットの半径とボールの半径

シュート速度、守備ロボット i の加速度、ロボットの和である。

j = r, l 両方に対して式 (1) を満たす場合、ボール の半径とボールの半径の和である。また、leng(a, b)の座標 b は安全領域内の点とする。守備ロボットが は中心をゴールラインの中央とする弧上の点 a、点b 間の弧の長さとする。

1 ダイレクトプレイとはシュートするロボットが味方ロボット
からパスを受け、ボールを保持せずにシュートを行うことである。
詳細は文献 [3] を参照されたい。

2- 20 -

式 (2) を満たすか、b と e の間にパスコースが存在しない場合2 、e は安全慮域内の点とする。守備ロ
ボットが複数である場合、j = r、j = l それぞれを、いずれかのロボットが満たす場合、e は安全領域内の点とする。また、leng(ri , pj,i ) − R < 0 を満たす
場合についても、e は安全領域内の点とする。

実験結果

4

ここでは、安全領域の実験結果を示す。実験には
図 1: Safety region: one shooting robot and one
RoboDragons[4] の守備戦略を用いる。その理由は、
defending robot
戦略の細部を把握しているので解析が容易にできるからである。
がわかる。しかし、シミュレーション結果では安全領

4.1

域と非安全領域の境界が滑らかではないこと、ゴー

単独シュート時の安全領域

ルライン近辺に非安全領域が存在しているという特1 台のシュートロボットと、1 台の守備ロボット 徴が見られる。前者はシミュレータのランダム性が(ゴールキーパー) がいるものとする。安全領域は解 原因であり、後者は主にボールがゴールキーパーに
3
析的に計算されるべきであるが、解析的に求めるこ 反射することに原因がある 。
とは困難であるため、フィールドを 20mm 間隔に格子点分割し、分割領域の中心点に対して計算を行う
ことで近似的に安全領域を求める。ゴールキーパーの位置は、ディフェンスサークルの内側かつ、2 直線 Lr 、Ll がなす角度の二等分線上である。
図 1 は近似的に求めた安全領域の計算結果である。
また、シュート速度は 3.5m/sec、守備ロボットの加2

速度は 2.4m/sec とした。図 1 の灰色の領域は安全領域であり、黒色の領域は非安全領域である。守備ロボット側のディフェンスエリア (白色の領域) は、
シュートされないため考慮しない。

図 2: Safety region: simulation result

計算結果と RoboDragons のシステムによるシミュ
レーション結果との比較を行った。
図 2 にシミュレーション結果を示す。この結果は、ロボット 1 台による守備下で、各分割領域の中心点からシュートさせたシミュレーション結果である。

2 つの安全領域の導出結果を比較し、どの程度一致しているかを調べた。適合率 R を以下の式によって定義した。

シュートを決められた点を黒色、そうでない点を灰R=色で示した。これらの図を見るとよく似ていること適合した点の数
格子点の総数適合した点は導出結果とシミュレーション結果が2r

i から b と e とを結ぶ線に降ろした垂線の長さがロボット
3 式 (1) ではボールの跳ね返りは考慮していない。

の半径より短ければ、パスをブロックできる。

3- 21 -

一致する点である。表 1 に結果を示す。
表 1: Coincidence rate (Single play)
適合点数 格子点総数 適合率 R

41126

4.2

42804

0.961

連携シュート時における安全領域
図 4: Safety region: simulation result

連携シュートにおいては、ゴールを 1 台のロボッ
トで守ることは困難である。したがって、守備ロボット 3 台という状況下で安全領域の計算を行う。Ro-

以下の実験では、ボールの初期位置はフィールド
boDragons の 3 台による守備戦略において、ゴールの中心からシュートされるゴールに向かって 1.5m のキーパーは単独シュート時と同じ場所に位置する。
位置とする。相手ロボットのパス速度とシュート速
Ls を前述の二等分線とする。他の 2 台のロボットは
度はともに 3.5m/sec とし、守備ロボットの加速度はLs に直交する直線 L 上に位置するものとする。直22.4m/sec とした。ダイレクトプレイを行うロボッ
線 L はディフェンスサークルから α cm 離れた位置
トは、任意の格子点上に置いて実験を行った。
で Ls と直交する (実験では α はロボットの半径＋
図 3 に計算によって求めた近似的な安全領域の結4cm)。直線 L 上に位置する 2 台のロボットは、ゴー果を示す。灰色の領域は安全領域であり、黒色の領ルを効率的に守れる点に位置する。
域は非安全領域である。守備側のディフェンスエリア(白色の領域) は考慮しない。図 4 にシミュレーショ
ン結果を示す。シミュレーション方法は単独シュート時と同じである。表 2 に適合率 R を示す。
２つの図には差異が見られる。これは、式 (2) の計算モデルがまだ不十分であることを示している。
実際、適合率は 0.952 と低めになっている。そのため、式 (2) には改善すべき余地が残されている。

5

安全領域の活用

図 3: Safety region: cooperative shooting (three
図 1 では 1 台の守備ロボットがゴールを守り、1 台

defending robots)の相手ロボットがシュートを行った場合の安全領域を示した。一方で改善された RoboDragons の戦略に従って 3 台の守備ロボットでゴールを守った場合
表 2: Coincidence rate (Cooperative play)
適合点数 格子点総数 適合率 R

40760

42804

の安全領域を図 5 に示す。式 (1) を用いて安全領域の計算を行った。計算に用いたパラメータは前と同

0.952

様とした。

4

- 22 -

も使うことができる。

6

おわりに
本稿では安全領域の概念について提案を行った。

安全領域とは、その領域内から打たれたシュートを守備ロボットが防ぐことができる領域である。安全領域は実際の試合で守備ロボットの台数を評価するために用いることができ、また、守備アルゴリズムの正確性を確認することもできる。

図 5: Safety region: one shooting robot and three

いくつかの守備戦略に対して安全領域の計算を行っ

defending robot (improved strategy)

た。連携プレー時における安全領域では、計算結果とシミュレーションの結果には差異が見られた。これは、今後改善すべき課題である。

参考文献[1] D. Ball and G. Wyeth “UQ RoboRoos 2004:
Getting Smarter”, in RoboCup 2004 Symposium CDROM, SSL Team Description Papers,
2004[2] M. Bowling, B. Browning, A. Chang and M.

図 6: Safety region: one shooting robot and three

Veloso “Plays as Team Plans for Coordination
and Adaptation”, in RoboCup 2003: Robot
Soccer World Cup VII, LNAI 3020, pp. 686 -defending robot (incomplete strategy)693, Springer, 2004

図 1 では、ディフェンスエリアの前方に大きな非安全領域が存在した。一方、図 5 には非安全領域は[3] Nakanishi, R., Bruce, J., Murakami, K.,

存在しない。このことから、ボールの位置に従って

Naruse, T. and Veloso, M ”Cooperative 3robot passing and shooting in the RoboCup
Small Size League”, RoboCup 2006: Robot

ロボットを適切な台数によってゴールを守る新たな戦略を提案できると考えられる。
改善する前の守備戦略に従って、3 台の守備ロボッ

Soccer World Cup X, LNCS 4434 pp.418-425

トを用いてゴールを守った場合の安全領域を計算したものを図 6 に示す。

[4] R. Nakanishi, K. Otake, R. Narita, M. Tanaka,

図 6 にはディフェンスエリア前方に三日月に似た

S. Ueno, H. Achiwa, J. Maeno, K. Murakami
and T. Naruse “RoboDragons 2007 Team
Description”, in RoboCup 2007 Symposium

形の非安全領域が存在する。これは、新たに加えた

2 台の守備ロボットの動作制御に起因する守備アル
ゴリズムの欠陥を示している。この例のように、安CDROM, SSL Team Description papers, 2007

全領域はアルゴリズムの正確性をテストすることに5- 23 -

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

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

サッカーロボットの Profit Sharing による学習
Learning of Robot Soccer Agent Using Profit Sharing〇山口 雅士 (沼津高専専攻科)
岡本 成晃 (沼津高専専攻科)
川上 誠(沼津高専電子制御工学科)
澤 洋一郎 (沼津高専電子制御工学科)* Masashi YAMAGUCHI(Numazu College of Technology), Shigeaki OKAMOTO(NCT),
Makoto KAWAKAMI(NCT), Yoichiro SAWA(NCT)yamaguchi@eces.numazu-ct.ac.jp, okamoto@eces.numazu-ct.ac.jp,
kawakami@numazu-ct.ac.jp, sawa@ece.numazu-ct.ac.jp

Abstract— In robot soccer systems, intellectually collective and cooperative actions by two or more robots areneeded. The robots are adjusting their knowledge, skills
and plans for a common goal. Thus the robot soccer system is a typical problem on studying multi-agent systems.
The purpose of our research is to get the knowledge about
designing excellent multi-agent systems. We introduce
Penalty Avoiding Profit Sharing (PAPS) which is connected Penalty Avoiding Rational Policy Making algorithm (PARP) with Profit Sharing (PS) to the robot soccer
system based on the rule of RoboCup soccer, F-180
league. In this paper, we report the effectiveness of PAPS
by applying it to a soccer game simulation software,“SoccerBots”. We investigate the change of game resultsby the agent which is implemented PAPS and PS, etc. respectively with ability of goalkeepers.
1. はじめにサッカーロボットシステムは、複数のロボットが共通の目標(goal)に対して各々の知識(knowledge)、
技術(skill)、計画(plan)を調整することによる知的な集団行動が要求され、マルチエージェントシステ
ムを研究する上での標準問題となっている 1)。
特に、マルチエージェント学習における「状態空間の爆発問題」に対して、中村等 2)3)はフィールドを格子状のセルの集合に区切り、状態数に依らない方
策表現を行い、強化学習法の一つである方策勾配法
を用いて協調行動の学習を実現した。そこでは、相手ゴール前のフリーキックからのパス・プレーについて例示したが、ゲーム中の様々な場面での適用については、その度に学習器を設計せねばならず、現状ではそのままフルゲームに適用し難い。一方、ゲーム中の状況を限定せずにゴールへ導くルールを、ゴールのたびに一括で強化する Profit Sharing4)に罰回避政策形成アルゴリズム PARP5)を組み合わせた
PAPS6)が、よい結果をもたらすことを宮崎等が報告している。しかも、PAPS は状態数のオーダーの記憶で済むという点で優れているので有望であるが、シミュレーション条件や学習パラメータ値など不明な部分があるので、PAPS の有効性について十分に明確にはされていないといえる。
そこで、本研究ではマルチロボットシステム構築
に関する有用な知見を得ることを目的とし、RoboCup7)サッカー小型リーグのルールに準拠したサッカーロボットシステム SoccerBots8)に PAPS を適用
し、シミュレーションによりその有効性を検証する。
具体的にはオウンゴール（失点）を抑えて、数多く得点する動きの学習効果を得点・失点で評価し、これらに影響を与える自他両チームのゴールキーパの能力を変えて調べる実験を行ったので報告する。
2. 学習の方法
本研究で扱う学習エージェントは、外部の環境と内部の状態を知覚し、その状態において実行可能な行動をあらかじめルールとして設定し、学習によりその価値（重み）が変更され、政策に応じてこの価値に基づきルールを選択して行動していくものである。エージェントはその学習に強化学習法の一つである Profit Sharing を用いるが、｢強化学習はオン
ライン学習法の 1 つであり、さまざまな報酬（即座に得られる報酬や時間的に遅れて得られる報酬など）を手がかりとしながら、単位時間当たりの受け取る報酬（あるいは最終的に受け取る報酬の総量）を最大化する政策を、試行錯誤によって獲得するものである(文献 1)p.30 より引用）｣。ここで、初期状態あるいは報酬を得た直後から次の報酬を得るまでのルール系列をエピソードというが、Profit Sharing
ではエピソード終了後に、すべての有効ルールについて、各ルールの価値(Q 値)は次式によって更新される。
Q(st,at) ← Q(st,at)＋Cbid [ｒ(t) － Q(st,at)],where t = 0,……,episode-1 … (1)
ここで episode は報酬を受けるまでのタイムステッ
プｔの数であり、st はｔでの状態、at は行動を表し、パラメータ Cbid はせり値、ｒ(t)は報酬関数である 4)。
また、あるエピソードにおいて、同一の状態に対して異なるルールが選択されているとき、その間のル- 24 -

ール系列を迂回系列といい、現在までの全てのエピ
ソードで常に迂回系列上にあるルールを無効ルー
ル、それ以外を有効ルールという。
次に PAPS では、個々のルールに対する上で説明した報酬用の重み（Q+）に加えて、罰用の重み Qを用意し、さらに、罰ルール判定用フラグを用意し、エピソード単位でこれらの重みに基づきルール選択を行う。そして、Q-は失点時の罰を受けた際、Q+と同様に更新される。ここで罰ルールとは、「直接罰を得た経験のあるルール」あるいは「選択可能なルールが罰を得たルールまたは無効ルールのみである遷移先を持つルール」である。このような方法により、報酬と罰が混在した環境で、記憶量が状
態数と行動数の積のオーダーで抑えられ、状態空間の爆発問題を回避できるのが PAPS の特長である 6)。
3. シミュレーション方法と実験条件使用するシミュレータ SoccerBots8)は、移動ロボッ
ト研究のために Java で開発された TeamBots ソフト
ウェア配布の一部であり、2 つのアプリケーション（サッカーサーバとユーザが作成する各チームのエージェントの動きを記述するプログラム）等から成る。初期のころの RoboCup 小型リーグのルールに準拠するように開発されており、コーナープレートやボールがフィールド外に出ないように壁が設定されている。通常、黄色チームと青チームそれぞれ最大 5台のエージェント（すべて円筒状であり、移動とボールキック等ができる）で試合ができるように作成されている。図１に本研究に用いた SoccerBots の画面の一例を示す。
3.1 SoccerBots のシミュレーション設定
文献 6)に記載されたパラメータ値を用い、その他のものについても以下のように設定した。競技フィールドの寸法を図２に示す。エージェントは直径15cm の円筒状であり、毎秒 0.3m/s で動き、360 度回転する。ボールは直径 40mm とし、キックされた際には 0.5m/s で動き、毎秒 0.1m/s で減速するように設定した。また、タイムステップ 0.1ｓで諸量を計算するように設定した。その他の設定値は SoccerBots がデフォルトで用意した値を使用した。また、シミュ
レーション中にボールの動きが 60 ステップ停止した
場合は、自動的にセンターに置かれる。
3.2 エージェントの設計(1) 状態集合
学習エージェントの状態集合ｓを、表１のとおり、
学習エージェントの位置ｐ(図３に示すようにフィールドを縦・横それぞれ４分割した１６通り)、学習
エージェントとボールとの距離ｄ（４通り）、ボー
ルへの角度 a（図４に示すとおり４通り）及び相手キーパの位置 k（ゴール前に位置しｘ座標を固定、ゴー
ルのｙ方向の幅 50cm を５分割、５通り）とした。
(2) 行動集合
学習エージェントの行動集合は表２のように４通りとし、それぞれの Kickspot の位置は図５に示す。
3.3 エージェントの行動(1) Random エージェント
学習効果を比較する基準として、行動選択をランダムに行うエージェント（以下、RND という）を使用した。
(2) PS エージェント
Profit Sharing を用いた学習エージェント（以下 PS という）ではルール集合の中から報酬用の重み Q+に従って確率的にルールを選択するルーレッ
ト選択法を採用した（重みの初期値を 0.1 に設定した）。また、本実験では重み更新式(1)において、
Cbid＝0.75 とし、報酬関数 r(t)は次式で与え、r(t)/r(t-1) = b… (2),where b＞1, r(0) ＞ 0
初期値 r(0)＝1、最終値 r(episode-1)=10 として、
公比を次式のように与えた。
ｂ＝10 1/(episode-1)… (3)(3) PAPS エージェント
前述の罰（つまりオウンゴール）を回避する PSを用いたエージェント（以下 PAPS という）を使用した。PS の部分のパラメータは(2)と同じ値に設定した。
(4) ゴールキーパ
自チーム及び相手チームのゴールキーパ GK はゴール前に位置し（x 座標を固定）、ゴールの幅の範囲で、ボールの y 座標を自身の y 座標に合わせるよ
うに移動し、ボールをはじいてゴールを防ぐ動作のみ行わせた。
3.4 実験条件
本シミュレーションでは図１に示したとおり、対象となるエージェント 1 台と両チーム各 1 台のゴー
ルキーパ GK を配置し、2 対 1 で試合を行うこととした。学習エージェントの行動選択回数は文献 6)と同様に 40,000 回とし、これを 1 試合 (4,000ｓ）とした。対象とするエージェントとして前述のとおり
PAPS、PS 及び RND を実装して 10 試合行うこととし、
以下のように GK の移動速度により得点と失点の学習効果の違いを調べた。
(1) 実験１
相手チーム GK の移動速度を学習エージェントの速度の 50%に固定し、自チーム GK の速度を 25％～
100％の 4 段階変化させた。
(2) 実験 2
自チーム GK の移動速度を学習エージェントの速度の 50%に固定し、相手 GK の速度を 25％～100％の4 段階変化させた。

- 25 -

4. 実験結果と考察ルが少なくなっている。また、PS は RND と同程度であるが、PAPS は両者に比べ失点がかなり抑えられて
4.1 実験１（相手チーム GK 移動速度 50％の場合）いる。つまり、PAPS が効果を発揮しているといえる。
PAPS、PS 及び RND について 10 試合シミュレーショ
図８および９に PS と PAPS の学習過程の一例を示ンを実施した時の結果を表３に示し、平均得点を図す。ともに、両チームの GK の移動速度は 50％の場合６に示す。相手チーム GK の移動速度を一定としていである。PS のゴールについて見ると、開始直後よりるので、自チーム GK の移動速度に対して、平均得点増加している。失点は徐々に増加していることがわはほとんど変化がみられない。しかし PS 及び PAPS
かる。一方、PAPS のゴールを見ると、10,000 ステッ
は、RND に比べてばらつきが大きいが、若干得点が上プ付近でゴール数が急激に増加して学習が進んだこ回っており、一定の学習効果が見られる。
とを表している。失点については PS に比べて徐々に
また、平均失点を図７に示す。すべてのエージェ
増加を抑えている。
ントで、自チームの GK の移動速度が大きくなるにつ
4.2 実験 2（自チーム GK 移動速度 50％の場合）
れて緩やかに平均失点が減少していることがわかる。
PAPS、PS 及び RND について 10 試合シミュレーショ
つまり、自チームの GK の能力が高いほどオウンゴーンを実施した時の結果を表４に示し、平均得点を図
Table1 States in the Soccer Simulation

Figure1 Simulation Software“SoccerBots”

Figure2 Field in the Simulation (unit：mm)

Figure3 Position of the Learning Agent

Table2 Actions

KS3
KS1

Ball

KS2

Centerof GoalFigure5 Kickspots
Figure4 The angle from thelearning agent to the ball- 26 -

１０に示す。相手 GK の移動速度が小さい時には三者とも差は見られないが、移動速度が増加するにつれて PAPS と PS は RND を上回っており、学習効果が見られる。
また、図１１に平均失点を示す。PS は RND に比べてわずかに失点が少ない程度であるが、PAPS は RND の半分近くまで押さえられており、PAPS が有効に機能していることがわかる。また、相手キーパの移動速度の増加につれてすべての失点がわずかに増加しているが、ゴール失敗によりボールが自陣に跳ね返されたときに、エージェントが戻って来て自チームのゴール側にキックしてしまうケースが増えているためと考えられる。
5. おわりに
PAPS の有効性を検証するために、行動選択をランダムに行う場合(RND)、罰回避のない PS で学習させた場合および PAPS を用いた場合、それぞれについて、
自チーム・相手チームのゴールキーパの能力（移動速度）によって得点および失点がどのように変化す
るかを調べた。その結果、以下のような結論が得られた。
(1) 相手チームのゴールキーパの移動速度が大きくなるにつれて得点はいずれも減少する。移動速度が小さい時には三者は同程度であるが、移動速度が増加すると、PAPS および PS は RND よりも得点が上回り、学習の効果が見られる。
(2) 自チームのゴールキーパの移動速度の大小にかかわらず、PAPS は PS および RND に比べて失点を抑える効果がある。
以上のとおり、PAPS による学習はゲームにおいて有効に働くことが確認されたが、今回のシミュレー
ションによって、PAPS と PS は RND に比べると結果にばらつきが多く見られた。また、式(1)の Cbid やルー
レット選択時に設定する Q の初期値により結果が若干異なるので、適切な値をあらかじめ調べて設定する必要があることもわかった。今後、PAPS による学習をさらに検討し、実機による検証を行っていきた
いと考えている。
謝辞
本研究の実施にあたり、ロボットシミュレータ
TeamBots を利用させていただいた Tucker Balch 氏とこの度沼津市で開催いただいた RoboCup ジャパンオープン関係者の皆様に心から感謝致します。
参考文献
1)
2)

高玉圭樹：マルチエージェント学習―相互作用の謎に迫る―、コロナ社、pp.2-9,pp30-31(2003)
中村浩二、五十嵐治一、石原聖司：“方策勾配法を用

Table3 Results of Experiment1 (Opponent GK speed is fixed at 50% of the learning agent)

PAPS

PS

RND

PAPS

PS

RND

50

75

100

16

60

12

Goals

Own Goals

40

20

8
4

0

0

0

25

50
75
100
Our GK Speed (%)

125

Figure6 Average of Goals in Experiment1

0

25

125

Our GK Speed (%)

Figure7 Average of Own Goals in Experiment1- 27 -

3)

4)

いたサッカーエージェントの学習～フリーキックにおけるキッカーとレシーバ～、第 23 回 SIG- Challenge
研究会予稿集、pp.7-12(2006)
福岡仁志、中村浩二、五十嵐治一、石原聖司：“方策勾配法を用いたサッカーエージェントの学習～フリー
キックの時の壁パス～、第 25 回 SIG- Challenge 研究会予稿集、pp.74-79(2007)
宮崎和光、斎藤淳平、小林博明：マルチエージェント
強化学習によるサッカーゲームにおける協調行動の学
習、第 45 回自動制御連合講演会予稿集 pp 167-170 ,(2002)

宮崎和光,坪井創吾,小林重信,罰を回避する合理的政策 の 学 習 , 人 工 知 能 学 会 ,Vol.15,No.2,pp.148-156,(2001)
6) 宮崎和光、斉藤淳平、小林博明：罰を回避する Profit
Sharing の提案、第 45 回自動制御連合講演会予稿
pp441-442,(2002)
7) RoboCup 公式サイト、http://www.robocup.org/
Jintro.htm(2007)8) Tucker Balch , JavaBots http://www.teambots.org/,
CMU'sMultiRobotLab(2006)

Own Goals

Goals

50

50

40

40

30

30

Score

Score

Goals

5)

20

20

10

10

0

0

0

10000

20000

30000

Own Goals

0

40000

10000

20000

30000

The number of steps

The number of steps

Figure8 The example of PS

Figure9 The example of PAPS

40000

Table4 Results of Experiment2 (Our GK speed is fixed at 50% of the learning agent)

PAPS

PS

RND

PAPS

PS

RND

50

75

100

16

60

12

Goals

Own Goals

40

20

8
4

0
0

25

50

75

100

0

125

0

Opponent GK Speed (%)

25

125

Opponent GK Speed (%)

Figure10 Average of Goals in Experiment2

Figure11 Average of Own Goals in Experiment2- 28 -

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

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

移動型ロボットにおける動作特性と行動知識の分離
Separation of Action Characteristics and Value Functions in Policies
for Mobile Robot Control〇長谷川 卓也，五十嵐 治一（芝浦工業大学工学部）
石原 聖司，田中 一基（近畿大学工学部）*Takuya HASEGAWA(SIT), Harukazu IGARASHI(SIT), Seiji ISHIHARA(Kinki Univ.),
Kazumoto TANAKA(Kinki Univ.)
Abstract— Policy gradient methods are useful approaches
for reinforcement learning. Applying such methods tobehavior learning, we can deal with a decision problem at
each time step as a problem to minimize an objectivefunction. In this paper, we give an objective function thatconsists of two types of parameters that represent
environmental dynamics and value functions. To separate
the learning of the value functions from that of theenvironmental dynamics, we give respective learning
rules for both of parameters. This separation will make itpossible to reuse state-value functions and action-valuefunctions under other different environmental dynamics.
The effectiveness of separation is shown through ourexperiment of simple parallel translation with anomni-directional four-wheel drive robot.

1. はじめに
強化学習によりエージェントの行動決定方法（方策）を学習する際には，通常，環境の状態遷移確率に関する情報を事前に入手したり，別途学習したりする必要はない．例えば Q 学習[1]では，このような情報は，行動価値関数 Q(s, a)の値として，問題解決のための行動決定に関する知識と一体となって学習されていく．
しかし，環境に依存しないで有効な行動決定をもたらす普遍的な知識（以下，行動知識）は多くの問題で存在する．例えば，追跡問題において，ハンターが獲物に接近する行動を選択した方が捕獲に貢献し高報酬につながるといった知識[2]はハンターの動作特性に無関係である．ところが，ハンターの走行特性にくせがある場合や，障害物の存在やぬかるみに足を取られたり強風に煽られたりするなどの理由で，必ずしも思い通りの方向にハンターが進めず確率的にしか状態を遷移できない場合がある．
このような場合，学習により得られた方策はこの動作特性（状態遷移確率）の影響を強く受けてしまう．
もし，方策に関する知識が動作特性に依存するものと依存しないものとに分離された形で学習できれば，後者の知識を別の環境下でも容易に再利用できるという利点がある．また，動作特性だけを別の方法で測定しておいて，それを方策の学習時に利用できれば学習の効率化につながるであろう．例えば，ロボットの走行特性は実機で計測しておき，一方，行動知識については，くせのない走行特性を仮定してシミュレータ上で強化学習を行うことにより求Measuring dynamics
of mobile robot

Learning a task understandard dynamics

Relearning using both sources of knowledge
as initial values of parameters
Fig.1 Integration between dynamics of a robot andknowledge to solve a task
めておく．この両者を初期値として用いれば，実機を用いた強化学習の効率化が期待できるのではな
いだろうか．Fig.1 にこの方式の模式図を示す．我々はこのようなアイデアを実現するための強化学習
方式について具体的な提案を行ってきた[3] [4]．
本報告では，RoboCup 小型リーグ向けの移動型ロボットを題材にして，直進走行というごく簡単なタ
スクではあるが，実際のロボットの走行特性を考慮した行動選択の実験を行った．次章以下では，まず，提案手法の概略を述べる．次に，対象とするタスクと，ロボットの走行特性の測定結果について説明する．さらに，問題解決のための行動知識として予め用意したポテンシャルを導入し，測定した走行特性と組合わせた場合の走行実験の結果を報告する．

2. 提案手法の概略
まず，エージェントの行動決定を各時刻における目的関数の最小化問題に帰着させる．この目的関数の中に，状態の確率的な遷移，すなわちエージェン
トの動作特性を表すパラメータ（動作特性パラメー
タ）と，行動決定に必要ではあるが状態遷移確率に依存しない知識に関するパラメータ（行動知識パラメータ）の 2 種類のパラメータを用意する．3 章，
4 章では一般的な場合を論じているが，本稿では，前者の動作特性としては四輪ロボットの走行特性（走行の癖）を，後者の行動知識パラメータとしては状態価値を表すポテンシャルを想定している．

- 29 -

られる報酬 r の期待値 E[r] を最大（厳密には極大）にするパラメータを求めるために目的関数
E(a;s,{α})中のパラメータα（θ(s)やω(s,s’;a)のこと）
による E[r]の勾配を計算すると，

次に，これらのパラメータの値は強化学習の一種である方策勾配法を用いて，報酬の期待値が極大となるように学習することができる（3 章，4 章）．
ただし，今回は，学習ではなく，動作特性は観測により，状態価値はポテンシャルとして天下り的に与え（5 章），目的関数の形式が妥当であるかどうかの検証だけを行った．

∂E [ r ]⎡ L−1⎤= E ⎢ r ∑ eα ( t ) ⎥∂α⎣ t =0⎦3. 方策勾配法による行動学習
3.1 方策勾配法
方策勾配法[5]による強化学習では， TD 法や Q 学
習などとは異なり，状態価値関数や行動価値関数を求めることなく，方策中のパラメータを直接学習することができる．また，環境や方策のマルコフ性を仮定することもなく適用することができる[6]．
3.2 目的関数と方策
各時刻における行動決定問題をある目的関数の最小化問題として定式化し，その目的関数の期待値を一定にするという条件下で行動決定に関する不確定さ（エントロピー）を最大にする確率的な方策関数を求めると，ボルツマン型の確率分布関数となる．今，状態 s∈S におけるエージェントの行動 a∈A を決定する方策π(a;s,{θ},{ω(s,s';a)})を以下のボ
ルツマン型の分布関数で定義する．

π ( a; s ) ≡

e

∑

(

となる[2]．ここで，L は各エピソードの長さ(時間ス
テップ数)であり，eα(t)は特徴的適正度と呼ばれる[5]．
(1)のように方策がボルツマン選択であるときには，eα ( t ) =e(5)

1 ⎡ ∂E ( a ( t ) ; s ( t ) ,{α })
∂E ⎤
−
⎢
⎥
∂α
∂α T ⎦⎥T ⎣⎢(6)と表される[2]．ただし，(6)の右辺の<・>T は分布(1)による期待値操作を表す．
方策勾配法の学習則は，(4)の勾配を用いて一般に，
L −1

)

(

∂
ln π ( a (t ); s ( t ), {α })∂α=−− E a ;s ,{θ },{ω ( s , s′;a )} T

b∈A

(4)

)

− E b;s ,{θ },{ω ( s , s′;b )} T

Δα = ε ⋅ r ⋅ ∑ eα ( t )(1)と表される[2]．なお，ε(>0)は学習係数であり，パラメータの更新は各エピソード終了時に行う．

(1)の方策中の目的関数 E(a;s)として，我々は次の２つの場合を考えた[4]．

4. 学習則(2)を(6)へ代入すると，θ(s’)とω(s,s’;a)に関する特徴的適正度が次のように計算できる[4]．

(i)動作特性と状態価値とで表現する場合：E ( a; s ) ≡ − ∑ ω ( s, s′; a ) θ ( s′)

(7)

t =0

(2)

s′

1⎡
ω ( s ( t ) , s′; a ( t ) ) − ω ( s ( t ) , s′; a′) ⎤ (8)
T⎦
T⎣
1
(9)
eω( s ,s′;a ) ( t ) = ⎡⎣δ a ,a(t ) − π ( a; s ( t ) )⎤⎦ θ ( s′) δ s ,s(t )Teθ ( s′) ( t ) =(ii)動作特性と行動価値とで表現する場合：E ( a; s ) ≡ − ∑ ω ( s, s′; a ) ∑ θ ( s, a ′) P ( a ′ s, s′)
s′

(3)

a′

(i)において，(2)の右辺のθ (s) は状態 s の価値を表す行動知識パラメータ，ω(s, s’; a) は状態 s で行動 aを選択したときに状態 s’へ遷移する度合いを表す動作特性パラメータである．従って，(2)では，行動 a の選択により得られる遷移先の状態 s’の状態価値 θ(s’)に基づいて，状態 s における行動 a の妥当性を目的関数により表している．ただし，確率的な状態遷移を扱うため，状態遷移確率に対応するパラメー
タω(s, s’; a) によって遷移先の状態価値θ(s’)は重み付けされている．5 章の実験では(i)の形の目的関数を用いる．なお，(ii)における(3)の意味や学習則の導出についてはここでは割愛する[4]．
3.3 学習則
本研究においてはエピソード的な学習を考える．
各エピソードは実際に選択した行動列{a(t)}と実現された状態列{s(t)}とで表される．エピソードに与えδs,s'は s=s’ならば 1, それ以外は 0 となる関数である．

θ(s’)と ω(s,s’;a)の学習則は，(7)において α = θ(s’)や
α =ω(s,s’;a)と置き，(8),(9)の表式を代入することにより得ることができる．(8)より，エピソード中に出現した s(t)から実際に選択した行動 a(t)により遷移
可能な状態 s'の価値θ(s')が，その遷移確率（動作特性パラメータ）の大きさω(s,s';a)に応じて更新される
ことがわかる．
また，(9)より，エピソード中に出現した状態 s(t)から状態 s'へと行動 a により遷移する度合いω (s, s’;a)が更新される．この際，実際に選択された行動 a(t)については，(9)の右辺の[ ]内が非負なので状態 s'の価値 θ(s')の大きさに比例して ω(s,s';a)の値が増加
する．

- 30 -

一方，選択されなかった行動 a≠a(t) については，
状態 s'への遷移が抑制されるようω (s,s';a)の値が減少する．この強化と抑制の度合いは，そのエピソー
ドに与えられた報酬 r に比例している．

5. 目的関数の検証実験
本章では，スマッツ社製の移動型ロボット，オム
ニ RoboE2007 の直進走行タスクを例に，(2)の目的関数により走行制御が可能であるかを検証する．
5.1 走行コマンド(2)に現れるω(s, s’; α)は，その環境におけるエージ
Fig. 2 Three parameters used in command “MOVE”
ェントの動作特性を表すパラメータである．今回の移動型ロボットの走行制御の場合では，走行コマン
ド a に対するロボットの状態 s（位置と姿勢）の変化の特性に相当する（＝走行特性）．この走行特性
は，実際のロボットを用いて，コマンド空間においてコマンド値をいろいろ与えてみることにより測定が可能である．これはそのロボット固有の性質であり，一般的にはロボットごとに異なる．
走行コマンド a としては，メーカーから提供された「MOVE コマンド」をそのまま使用する．MOVE
コマンドは 3 つの引数（φ,v,ω）で指定される．それぞれ，進行方向φ(0～360[degree])，速度 v (0～1800[mm/s])，回転速度ω(-128～127 [degree/s])を表している．φとωはロボットの正面方向を基準とし，反時
計回りに大きくなっていく（Fig.2）．
(φ,ω)
5.2 走行特性の測定
Fig.3 に移動ロボットの動作の実測値を示す．ただFig.3 Robot traces by command MOVE when ω=0
し，ｖ=500，ω=0 と固定し，φを 0～330°まで 30°ごとに指定した場合の走行結果の軌道が示されてFig.4 に動作特性を考慮しない場合の走行結果を示す．
いる．なお，ロボットの走行時間は 2 秒間で，500ms
このときの MOVE コマンドの引数φはロボットの正ごとの位置が示されている．この走行実験において面からみたゴールの方向をそのまま指定している．
はω=0 と固定しているため，本来は姿勢を保持した
つまり，現在の場所からゴールへの方向へ直進させまま指定されたφの方向に平行移動するはずである．しかし，実際には Fig.3 から，φ=0，φ=180 とるという greedy な方策を採用したことに相当する．
いった前後の動作の場合はその方向へほぼ直進しこの結果から，動作特性を全く考慮しない場合，ロているが，それ以外のφの値を指定した場合にはボットの軌道はスタートとゴールとを結ぶ直線から「ずれ」が生じ，軌道が変形していることがわかる． 大きくずれてしまう場合があることがわかる．
また，ロボット自身の姿勢も保持されていない．
5.4 行動知識
5.3 直進走行タスク(2)に現れるθ(s)は，ロボットの癖や床面によらなスタート地点から一定距離にゴール領域を設定し， いタスク固有の知識（＝行動知識）であり，汎用性
なるべく直線的にゴールへ到達するような直線走行がある．直進走行タスクにおいては，ゴール地点へ
タスクを考える．(2)のω (s, s’; a)としては，5.2 で測近づくことがタスクの目的であるので，ゴール地点
定したロボットの走行特性データを，また，θ(s')としからの距離が近い地点，かつ，ロボットの現在位置とゴール地点とを結ぶ直線に近い地点ほど状態と
てには予め用意したポテンシャル関数を用いた．
しての価値が高いと期待される．そこで，今回は予また，実験条件は以下のように設定した：
めポテンシャル関数θ(s)として・ゴールまでの距離は 1m とする．
・走行時，ゴール時の姿勢は問わない．
・MOVE コマンドの送信は 1 秒毎に行う．
・MOVE コマンドの v を 500，ωを 0 に固定する．
・スタート時の姿勢は 0,30,…,330 と 30 度ごとに行う．

θ ( s) = x 2 + y 2 + y(10)を用意し， (2)の目的関数中で用いた．ただし，(10)はロボットのゴールからの距離，そしてスタートとゴールを結ぶ直線との距離を足し合わせたもので，- 31 -

Fig.6 Robot traces considering robot dynamics foraction decision

Fig.4
Robot traces without considering robot
dynamics for action decision

ことができた．今後は，姿勢制御や追跡問題やサッカーゲームなどより難しいタスクにおいて提案方式による制御を行うことと，動作特性と行動知識の学習に関する検証実験とを行っていく予定である．

Fig.5 Definition of distances x and y. Symbols S and G
mean start and end points, respectively.
スタートからゴールまでを直線的に移動させるためのヒューリスティクスである．(10)のポテンシャ
ルはスタート地点とゴール地点を通る直線 l を基準としており，x はロボットとゴールの直線 l 上における距離，y はロボットと直線 l の距離である(Fig.5)．
Fig.6 に(10)のポテンシャルを行動知識として用いた場合の走行結果を示す．動作特性を考慮しなかった場合(Fig.4)と比べて直進性がかなり改善された
ことが見て取れる．

6. まとめ
方策勾配法によりエージェントの行動学習を行う際に，エージェントの動作特性（または状態遷移確率）とタスク固有の行動知識とを分離し，それぞれに対応するパラメータを用意して方策中の目的関数を表現することをこれまでに提案してきた．本
研究では，この形式の検証実験として，RoboCup 小型リーグ向けの四輪移動型ロボットによる直進走
行タスクを取り上げた．目的関数中の動作特性としてロボットの走行特性を実際に測定した結果を用い，行動知識としては予め用意したポテンシャルを用いた予備的な走行実験を行った．この実験により，目的関数中において動作特性と行動知識とを分離して表現する方式が有効であるという感触を得る

参考文献[1] R.S.Sutton, A.G.Barto: Reinforcement Learning, MIT
Press, 三上貞芳，皆川雅章(訳)：強化学習，森北出版．
[2] 石原聖司，五十嵐治一：“マルチエージェント系
における行動学習への方策こう配法の適用-追跡問題-”，電子情報通信学会論文誌 D-I, Vol.J87-D1,
No.3, pp.390- 397, 2004．
[3] 石原聖司，五十嵐治一，“方策こう配法を用いた行動学習―状態遷移確率の学習―”，平成 18 年
電気関係学会関西支部連合大会講演論文集，
p.G275，Nov. 26，2006．
[4] 五十嵐治一，石原聖司，“方策勾配法を用いた行
動学習：動作特性と行動知識の分離”，第 25 回
日本ロボット学会学術講演会 3N35，2007 年 9 月
13 日～15 日，千葉工大．
[5] Williams, R.J. : “Simple Statistical GradientFollowing Algorithms for Connectionist
Reinforcement Learning, “ Machine Learning, vol.8,
pp.229-256 , 1992.
[6] 五十嵐治一，石原聖司，木村昌臣：“非マルコフ決定過程における強化学習―特徴的適正度の統計的性質―”，電子情報通信学会論文誌 D,
Vol.J90-D, No.9, pp.2271-2280 (2007)．

- 32 -

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

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

Mutual Development of Behavior Acquisition and
Recognition based on Value System
Yasutake Takahashi, Yoshihiro Tamura, and Minoru Asada∗
Dept. of Adaptive Machine Systems, Graduate School of Engineering, Osaka University,∗
JST ERATO Asada Synergistic Intelligence Project
Yamadaoka 2-1, Suita, Osaka, 565-0871, Japan
Email: {yasutake,yoshihiro.tamura,asada}@ams.eng.osaka-u.ac.jp

Abstract

behavior learning through observation has been more
important. Understanding observed behaviors does notmean simply following the trajectory of an end-eﬀector

Both self-learning architecture (embedded
structure) and explicit/implicit teaching fromor joints of demonstrator. It means reading his/her intention, that is, the goal of the observed behavior andother agents (environmental design issue) arenecessary not only for one behavior learning

ﬁnding a way how to achieve the goal by oneself regardless of the diﬀerence of the trajectory. From aviewpoint of the reinforcement learning framework, thisbut more seriously for life-time behavior learning. This paper presents a method for a robot
to understand unfamiliar behaviors shown bymeans reading rewards of the observed behavior and estimating sequence of the value through the observation.

others through the collaboration between behavior acquisition and recognition of observed

Takahashi et al.[4] proposed a method of not only tolearn and execute a variety of behaviors but also to rec-behaviors, where the state value has an important role not simply for behavior acquisition (reinforcement learning) but also for be-

ognize behavior of others supposing that the observer has
already acquired the values of all kinds of behaviors theobserved agent can do. The recognition means, in thishavior recognition (observation). That is, thestate value updates can be accelerated by ob-

paper, that the robot categorizes the observed behavior to a set of its own behaviors acquired beforehand.

servation without real trials and errors while
the learned values enrich the recognition system since it is based on estimation of the state

The method seamlessly combines behavior acquisition
and recognition based on “state value” in reinforcement
learning scheme. Reinforcement learning generates notvalue of the observed behavior. The validity ofthe proposed method is shown by applying it to

only an appropriate behavior (a map from states to actions) to accomplish a given task but also a utility ofa dynamic environment where two robots playsoccer.

1

the behavior, an estimated discounted sum of rewards
that will be received in future while the robot is taking
an appropriate policy. This estimated discounted sum of

INTRODUCTION

Reinforcement learning has been studied well for motor skill learning and robot behavior acquisition in both

reward is called “state value.” This value roughly indicates closeness to the goal state of the given task if thesingle and multi-agent environments. Especially, in themulti-agent environment, observation of others make thebehavior learning rapid and therefore much more eﬃcient [1, 2, 3]. Actually, it is desirable to acquire var-robot receives a positive reward when it reaches the goaland zero else, that is, if the agent is getting closer to thegoal, the value becomes higher. This suggests that theious unfamiliar behaviors with some instructions fromothers in real environment because of huge exploration
space and enormous learning time to learn. Therefore,- 33 -

observer may recognize which goal the observed agent
likes to achieve if the value of the corresponding task isgoing higher.
This paper proposes a novel method that enhances be-havior acquisition and recognition based on interaction
between learning and observation of behaviors. A robot
learns its behaviors through not only trials and errors but

color-coded objects and players in real-time. The mobile
platform is based on an omni-directional vehicle. These
two robots and the human play soccer such as dribbling

also reading rewards of the observed behaviors of others(including robots and humans). Fig.1 shows a rough ideaa ball, kicking it to a goal, passing a ball to the other,and so on. While playing with objects, they watch eachof our proposed method. V (s) and V̂ (s) are the statevalue updated by oneself and the state value estimatedthough observation, respectively. Takahashi et al.[4]other, try to understand observed behaviors of the other,and emulate them. In this paper, all experiments aredone in computer simulation environment and the realrobot experiments are planning to have in near future.
A learning/recognizing robot assumes that all robots
and even the human player share reward models of the
behaviors. For example, all robots and the human player
receive a positive reward when the ball is kicked into thegoal. This assumption is very natural as we assume that
we share “value” with colleagues, friends, or our family
in our daily life.

図 1: Interaction between Learning and Observation of

Behaviors

OUTLINE OF THE MECHANISMS

The reinforcement learning scheme, the state/action

showed the capability of the proposed method mainly incase that the observer has already acquired a number ofbehaviors to be recognized beforehand. Their case study
showed how this system recognizes observed behaviors
based on the state value functions of self-behaviors. This
paper shows how the estimated state value of observed
behavior, V̂ (s), gives feedback to learning and understanding unfamiliar observed behaviors and this feedback loop enhances the performance of observed behavior recognition. The validity of the proposed method isshown by applying it to a dynamic environment where
two robots play soccer.

2

3value function, and the modular learning system for various behavior acquisition/emulation are explained, here.
3.1

Behavior Learning Based on
Reinforcement Learning

An agent can discriminate a set S of distinct worldstates. The world is modeled as a Markov process, making stochastic transitions based on its current state andthe action taken by the agent based on a policy π. The
agent receives reward rt at each step t. State value V π ,the discounted sum of the reward received over time under execution of policy π, will be calculated as follows:
Vπ =EXPERIMENTAL SETUP AND AN
ASSUMPTION∞∑

γ t rt .

(1)

t=0

In case that the agent receives a positive reward if itreaches a speciﬁed goal and zero else, then, the statevalue increases if the agent follows a good policy π. The
agent updates its policy through trials and errors in order to receive higher positive rewards in future. Analogously, as animals get closer to former action sequencesthat led to goals, they are more likely to retry it. For
further details, please refer to the textbook of Suttonand Barto[5] or a survey of robot learning[6].
図 2: Robots with a human player in a Soccer Field

Here we introduce a model-based reinforcement learning method. A learning module has a forward modelFig.2 shows two robots, a human player and colorcoded objects, e.g., an orange ball, and a goal. The

which represents the state transition model and a behavior learner which estimates the state-action value func-

robot has an omni-directional camera on top. A simple
color image processing is applied in order to detect thetion based on the forward model in a reinforcement learning manner.

- 34 -

Each learning module has its own state transition
model. This model estimates the state transition proba
ability P̂ss
0 for the triplet of state s, action a, and next
state s0 :a0P̂ss
0 = P r{st+1 = s |st = s, at = a}(2)

Each module has a reward model R̂s , too:R̂(s) = E{rt |st = s}(3)

All experiences (sequences of state-action-next state andreward) are simply stored to estimate these models. Nowawe have the estimated state transition probability P̂ss
0and the expected reward R̂s , then, an approximatedstate-action value function Q(s, a) for a state action pairs and a is given by
[
]
∑
a
0
0
Q(s, a) =P̂ss(4)0 R̂(s ) + γV (s )s0

V (s) = max Q(s, a) ,a(5)where γ is a discount factor.
3.2

the behavior of the module. The details are described infollowing sections.
3.3

Behavior Recognition based on Estimated
ValuesEach behavior module can estimate a state value of observed behavior at an arbitrary time t to accomplish thespeciﬁed task. An observer watches a demonstrator’s
behavior and maps the sensory information from an observer viewpoint to a demonstrator’s one with a simple
mapping of state variables. Fig.3 shows a simple example of this transformation. It detects color-coded objects on the omni-directional image, calculates distancesand directions of the objects in the world coordinate of
the observer, and shifts the axes so that the positionof the demonstrator comes to center of the demonstrator’s coordinate. Then it roughly estimates the state
information in the egocentric coordinate and the stateof the demonstrator. Every behavior module estimatesa sequence of its state value from the estimated state of
the observed demonstrator and the system selects modules which values are increasing. The learner tries toModular Learning System

In order to observe/learn/execute a number of behaviors
in parallel, we adopt a modular learning system. Many
modular architectures have been proposed so far (for example [7, 8, 9]). Each module is responsible for learning
to achieve a single goal. One arbiter or a gate module is
responsible for merging information from the individual
modules in order to derive a single action performed by
the robot.
We prepare a number of behavior modules (BMs inthe ﬁgure) each of which adopts the behavior learning
method described in 3.1. The module is assigned to one
goal-oriented behavior and estimates one action valuefunction Q(s, a). A module receives a positive reward
when it accomplishes the assigned behavior or zero reward else. The behavior module has a controller thatgenerates predictions of next state values, selecting theaction with the maximum value. The gating module willthen select one output from the inputs of the diﬀerent
behavior modules according to the player’s intention.
The same behavior modules are used for the behavior recognition. Each behavior module estimates thestate value based on the estimated state of the observed
demonstrator1 and calculates reliability of observed behavior, that is, how likely the demonstrator is taking
1

For reasons of consistency, the term ”demonstrator” isused to describe any agent from which an observer can learn,
even if the demonstrator does not have an intention to show
its behavior to the observer.

- 35 -

表 1: List of behaviors learned by self and state variables

for each behavior
Behavior

State variables

Approaching a ballApproaching a goaldb
dg

Approaching the teammate
Shooting a balldrdb , dg , θbg

Passing a balldb , dr , θbr

acquire a number of behaviors shown in Table 1. The
table also describes necessary state variables for eachbehavior. Each state variable is divided into 11 in order to construct a quantized state space. 4 actions areprepared to be selected by the learning modules: Approaching the goal, approaching the teammate, going infront of the ball while watching the goal, and going infront of the ball while watching the teammate.
Fig.4 shows an example task of navigation in a gridworld and a map of the state value of the task. Thereis a goal state at the top center of the world. An agent
can move one of the neighboring square in the grids every step. It receives a positive reward only when it stays
at the goal state while zero else. There are various optimal/suboptimal policies for this task as shown in theﬁgure. If one tries to match the action that the agent

nized as a behavior g + β if Vt − Vt−1 > 0 and g < 1
g= g
if Vt − Vt−1 = 0g − β if Vt − Vt−1 < 0 and g > 0 ,where β is an update parameter, and 0.1 in this paper.
This equation indicates that the reliability g will becomelarge if the estimated utility rises up and it will become
図 3: Estimation of view of the demonstrator. Left : acaptured image the of observer, Center : object detection
and state variables for self, Right : estimation of view ofthe demonstrator

low when the estimated utility goes down. Another condition is to keep g value from 0 to 1.
3.4

Learning by Observation

In the previous section, behavior recognition system
based on state value of its own behavior is described.
This system shows robust recognition of observed
behavior[10] only when the behavior to be recognized has
been well-learned beforehand. If the behavior is underlearning, then, the recognition system is not able to show

図 4: Behavior recognition based on the change of stategood recognition performance at beginning. The trajectory of the observed behavior can be a bias for learning
behavior and might enhance the behavior learning basedvalueon the trajectory. The observer cannot watch actions ofobserved behavior directly and can only estimate the se-

took and the one based on a certain policy in order toquence of the state of the observed robot. Let sot be theestimated state of the observed robot at time t. Then,the estimated state value Vˆo of the observed behavior

recognize the observed behavior, it has to maintain various optimal policies and evaluate all of them in the worst
case. On the other hand, if the agent follows an appropriate policy, the value is going up even if it is not exactly
the optimal one. Likewise, in emulation one is not com-can be calculated as below:
[
]
∑
o
0
o 0
P̂ss
Vˆo (s) =0 R̂(s ) + γV (s )

(6)

s0

mitted with the optimal policy, as the behaviors are theones available in the portfolio of the agent, which areowhere P̂ss
0 is state transition probability estimated fromthe behavior observation. This state value function Vˆonot necessarily the optimal ones, but the ones that theagent knows to lead to the goal.
While an observer watches a demonstrator’s behav-

can be used for can be used as a bias of the state valuefunction of the learner V . The learner updates its stateaction value function Q(s, a) during trials and errors

ior, it uses the same behavior modules for recognitionof observed behavior as shown in Fig.??. Each behavior

based on the estimated state value of observed behavior Vˆo as below:

module estimates the state value based on the estimatedstate of the observed demonstrator and sends it to theselector. The selector watches the sequence of the statevalues and selects a set of possible behavior modules ofwhich state values are going up as a set of behaviors thedemonstrator is currently taking. As mentioned before,
if the state value goes up during a behavior, it means thatthe module is valid for explaining the behavior. The observed behavior is recognized by a set of behaviors whose
modules’ values are increasing.
Here we deﬁne reliability g that indicates how muchthe observed behavior would be reasonable to be recog-- 36 -Q(s, a) =

∑

[
]
a
0
0 0
P̂ss
0 R̂(s ) + γV (s )

(7)

s0

while

{
V 0 (s) =V (s)Vˆo (s)if V (s) > Vˆo (s)elseThis is a normal update equation as shown in (4) except
using V 0 (s). The update system switches the state valueof the next state s0 between the state value of own learning behavior V (s0 ) and the one of the observed behaviorVˆo (s0 ). It takes V (s0 ) if the state value of own learning
behavior V (s0 ) is bigger than the one of the observedbehavior Vˆo (s0 ), Vˆo (s0 ) else. This means the state value
update system takes Vˆo (s0 ) if the learner does not estimate the state value V (s0 ) because of lack of experience

4. goto 1.
On the other hand, the later experiment, it follows :at the state s0 from which it reaches to the goal of the
behavior. Vˆo (s0 ) becomes a bias for reinforcing the ac-

1. 5 episodes for observation of the behavior of theothertion a from the state s even though the state value of its
own behavior V (s0 ) is small so that it leads the learner toexplore the space near to the goal state of the behavior

2. 10 episodes for behavior learning by self-trials withobserved experienceeﬀectively.

3. evaluation of self-behavior performance

A demonstrator is supposed to show a number of behaviors which are not informed directly to the observer.

4. evaluation of behavior recognition performance

In order to update the estimate values of the behavior
the demonstrator is taking, the observer has to estimate
which behavior the demonstrator is taking correctly. If
the observer waits to learn some speciﬁc behavior by observation until it becomes able to recognize the observed
behavior well, bootstrap of leaning unfamiliar behaviors
by observation cannot be expected. Therefore, the observer(learner) maintains a history of the observed trajectories and updates value function of the observed behavior with high reliability or high received reward. The
observer estimates the state of the demonstrator every
step and the reward received by the demonstrator is estimated as well. If it is estimated that the demonstrator
receives a positive reward by reaching to the goal state of
the behavior, then, the observer updates the state valueof the corresponding behavior even if it has low reliability for the observed behavior. The update strategy
enhances to estimate appropriate values of the observed

5. goto 1.
The both learners attempt to acquire behaviors listed
in Table 1. The demonstrator one of the behaviors one
by one but the observer does not know which behavior
the demonstrator is taking. In both experiments, thelearner follows ²-greedy method; it follows the greedy
policy with 80% probalibity and takes a random action
else. Performance of the behaviors execution and recognition of observed behavior during the learning time isevaluated every 15 learning episodes. The performanceof the behavior execution is success rate of the behavior while the learner, the ball, and the teammate areplaced at a set of pre-deﬁned positions. The one of the
behavior recognition is average length of period in which
the recognition reliability of the right behavior is larger
than 70% during the observation. The soccer ﬁeld area

behavior.

is divided 3 by 3 and the center of the each area is acandidate of the position of the ball, the learner, or the4

BEHAVIOR LEARNING BYOBSERVATION

teammate. The performances are evaluated in all possible combinations of the positions.

4.1

Experimental setup

4.2

Recognition of Observed Behaviors

Before evaluating the performance of the behavior exe-

In order to validate the eﬀect of interaction between acquisition and recognition of behaviors through observa-

cution and behavior recognition of other during learning
the behavior, we brieﬂy review how this system estimatestion, two experiments are set up. One is that the learnerdoes not observe the behavior of other but tries to ac-

the values of behaviors and recognizes the observed behavior after the observer has learned behaviors. Whenthe observer watches a behavior of the other, it recog-

quire shooting/passing behaviors by itself. The otheris that the learner observes the behavior of other andenhances the learning of the behavior based on the estimated state value of the observed behavior. In former
experiment, the learner follows the learning procedure:
1. 15 episodes for behavior learning by itself

nizes the observed behavior based on repertoire of its
own behaviors. Figs.5 (a) and (b) show sequences of
estimated values and reliabilities of the behaviors, respectively. The line that indicates the passing behavior
keeps tendency of increasing value during the behavior

2. evaluation of self-behavior performancein this ﬁgures. This behavior is composed of behaviors ofapproaching a ball and approaching the teammate again,

3. evaluation of behavior recognition performancethen, the line of approaching a ball goes up at the earlier stage and the line of approaching the teammate goes

- 37 -

Success rate[%]State value

8

6

100

100

80

80

Success rate[%]

10

60
40
20

4

0
ball approachgoal approachteammate approach
shoot
pass
0

20

40

60

80

100

120

140

160

100

150

through observation
no observation

0
200

0

50

Number of episode(a) approaching the ball

180

number of frame(a) Estimated Values
Success rate[%]

1
0.9
0.8
0.7

Reliability

50

0.6

100

100

80

80

60
40
20

150
Number of episode

200

60
40
20

through observation
no observation

0.5

0
0

0.4

100

(b) approaching the teammate

Success rate[%]

0

40
20

through observation
no observation

0
2

60

50

100

150

through observation
no observation

0200

Number of episode

0

50

100

150
Number of episode

200

0.3
ball approachgoal approachteammate approach
shoot
pass

0.2
0.1
0

20

40

60

80

100

120

140

160

(c) shooting the ball(d) passing to the teammate

180

number of frame

図 6: Success rate of the behaviors during learning(b) Reliabilities

with/without observation of demonstrator’s behavior
図 5: Sequence of estimated values and reliabilities dur-

ing a behavior of pushing a ball to the magenta player,
red line : approaching a ball, green line : approaching
the goal, light blue line : passing, blue line : approaching
the other, magenta line : shooting

up at the later stage in Fig.5(a). All reliabilities startfrom 0.5 and increase if the value goes up and decrease
else. Even when the value stays low, if it is increasing with small value, the reliability of the behavior increases rapidly. The reliability of the behavior of pushinga ball into the teammate reaches 1.0 at middle stage ofthe observed behavior. “Recognition period rate” of observed behavior is introduced here to evaluate how longthe observer can recognize the observed behavior as acorrect one. The recognition period rate is 85% here,that means, the period in which the reliability of passing behavior is over 70% is 85% during the observation.
4.3

Performance of Behavior Learning andtimes could not reach the goal of the behavior at the
beginning of the learning because there is no bias to leadthe robot to learn appropriate actions. This is the reason why the variances of the rate is big. On the other
hand, the system with value update through observation utilizes the observation to bootstrap the learning
even though it cannot read exact actions of observed behavior.
Recognition performance and recognition period rateof observed behaviors and their variances are shown in
Figs.7 and 8, respectively. They indicate a similar aspect with the ones of success rates. The performanceof the behavior recognition depends on the learning performance. If the learning system has not acquired data
enough to estimate state value of the behavior, it cannot
perform well. The learning system with value updatewith observed behavior rapidly enables to recognize thebehavior while the system without value update basedon the observation has to wait to realize a good recognition performance until it estimates good state value of

Recognition
In this section, performances of the behavior execution

the behavior by its own trials and errors.

and behavior recognition during learning the behavior
are shown. Fig.6 shows success rates of the behaviors

Those ﬁgures show the importance of learning throughinteraction between behavior acquisition and recognition

and their variances during learning in cases of learning
with/without value update through observation. The
success rates with value update of all kinds of behav-of observed behaviors.

iors grows more rapidly than the one without observation feedback. Rapid learning is one of the most impor-

Above, values are deﬁned as behaviors, which are deﬁned by the achieved goals. The observer uses its own

tant aspect for a real robot application. The successrate without value update through observation some-value functions to recognize what the demonstrator will
do. Preliminary investigations in a similar context have

- 38 -

5

CONCLUSION

60
40
20
through observation
no observation
0

50

100

150

60
40
20
through observation
no observation

0
200

0

50

Number of episode

150

40
20
through observation
no observation
100

150

through observation
no observation
0

50

60
40
20
through observation
no observation
0

50

100

150

60
40
20
through observation
no observation

0
200

0

50

60
40
20
through observation
no observation0

Number of episode

50

100

150

200

80
60
40
20
through observation
no observation

0200

Number of episode(d) passing to the teammate

150
Number of episode

100

80

0
200

100

(b) approaching the teammate

100

Number of episode(c) shooting the ball

150(a) approaching the ball

80

0
200

100

80

Number of episode

Recogntion period rate[%]Recogniton success rate[%]

60

50

20

200

100

80

0

40

0

(b) approaching the teammate

100

0

60

Number of episode(a) approaching the ball

Recogniton success rate[%]

100

80

Recogntion period rate[%]

0

80

100

Recogntion period rate[%]

80

100

Recogntion period rate[%]100

Recogniton success rate[%]Recogniton success rate[%]100(c) shooting the ball

0

50

100

150
Number of episode200(d) passing to the teammate

図 7: Recognition performance of the behaviors during

図 8: Recognition period rate of the behaviors during

learning with/without observation of demonstrator’s behavior

learning with/without observation of demonstrator’s behavior

been done by Takahashi at el. [10] and they showed muchbetter robustness of behavior recognition than a typical[5] R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA,

method. In this paper, unknown behaviors are also understood in term of one’s own value function throughlearning based on the estimated values derived from theobserved behaviors. Furthermore, value update throughthe observation enhances not only the performance of
behavior learning but also the one of recognition of theobserved behavior eﬀectively.

参考文献[1] Steven D. Whitehead. Complexity and cooperation in q-learning. In Proceedings Eighth International Workshop on Machine Learning (ML91),
pages 363–367, 1991.
[2] Bob Price and Craig Boutilier.

Accelerating re-inforcement learning through implicit imitatione.
Journal of Articial Intelligence Research, 2003.
[3] Darrin C. Bentivegna, Christopher G. Atkeson, andGordon Chenga. Learning tasks from observationand practice. Robotics and Autonomous Systems,
47:163–169, 2004.
[4] Yasutake Takahashi, Teruyasu Kawamata, Minoru
Asada, and Mario Negrello. Emulation and behavior understanding through shared values. In Proceedings of the 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages
3950–3955, Oct 2007.

- 39 -

1998.
[6] Jonathan H. Connell and Sridhar Mahadevan.
ROBOT LEARNING. Kluwer Academic Publishers, 1993.
[7] R. Jacobs, M. Jordan, Nowlan S, and G. Hinton.
Adaptive mixture of local experts. Neural Computation, 3:79–87, 1991.
[8] Satinder Pal Singh. Transfer of learning by composing solutions of elemental sequential tasks. Machine
Learning, 8:323–339, 1992.
[9] Steven Whitehead, Jonas Karlsson, and Jsho
Tenenberg. Learning multiple goal behavior via
task decomposition and dynamic policy merging. In
Jonathan H. Connell and Sridhar Mahadevan, editors, ROBOT LEARNING, chapter 3, pages 45–78.
Kluwer Academic Publishers, 1993.
[10] Yasutake Takahashi, Teruyasu Kawamata, and Minoru Asada. Learning utility for behavior acquisition and intention inference of other agent. In Proceedings of the 2006 IEEE/RSJ IROS 2006 Workshop on Multi-objective Robotics, pages 25–31, Oct
2006.

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

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

ACO を用いた RoboCup サッカーエージェントにおける
行動獲得手法の提案
Proposal of Acquiring Method for Agents’ Actions using Ant Colony Optimizationin RoboCup Soccer Simulation League〇笹岡 久行 (旭川工業高等専門学校 電気情報工学科)
山田 太郎 (旭川工業高等専門学校 専攻科)
* Hisayuki SASAOKA(Asahikawa National College of Technology),
Taro YAMADA(Asahikawa National College of Technology)*sasa@edu.asahikawa-nct.ac.jp, nisikawaken2004@yahoo.co.jp
Abstract—We propose the acquiring method foragents’ actions using Ant Colony Optimization (ACO)
in the multiagent system. The approach is one ofmeta-heuristics and some papers have reported the effectiveness of some applications using it. Then we havedeveloped the experimental system with soccer agentsusing ACO in RoboCup Soccer Simulation League.
Then this paper presents result of some experimentswith our system.

1. はじめに

2. 基本的な考え方
従来からRSSを始めとするMASでは協調行動の獲得を目指した研究がある．例えば，遺伝的アルゴリズムを適用した村田らの研究[7]や進化型計算を適用した中島らの研究[8]がある．遺伝的アルゴリズムを始めとする進化論的手法では，その汎用性の高さから種々の応用において有効性が確認されている．しかし，探索領域の広さや学習結果が収束するまでの試
行回数の多さ等が問題となる．
我々は人手で作成した静的な規則を組み込んだ強化学習の手法を提案し，RSSにおけるサッカーエージ
ェントに組み込み，その有効性を報告した[9]．この中で，エージェント間の局所的な協調行動の実現を確認したが，大域的な協調行動の実現は困難であった．つまり，手法を組み込んだエージェント間でのパスの成功率の向上及び得点能力の向上は見られたが，それ以上の協調行動の実現は困難であった．これらの解決を目指し，エージェント間でフェロモン
を媒介としたコミュニケーションを用いて，マルチ
エージェントにおける協調行動の獲得を目指す．

近年，メタヒューリスティクスの一手法である群知能に関する研究が盛んに行われている[1,2]．さらに，マルチエージェントシステム(MAS)における最適化
問題の解決等に適用され，その有効性が確認されている[1,3,4]．
一方，MAS に関する研究テーマの 1 つとして
RoboCup サッカーシミュレーション(RSS)[5]が提案され，人工知能の研究の観点から，実世界に存在する問題を多く備えた良いテストベットとなっている[6]．このシミュレーション環境では仮想の広大なサッカーフィールド上に 22 体の自律エージェント(自チーム 11 体 vs. 相手チーム 11 体)とボールが存在し，さらに実時間での行動が必要である．また，エージ
3. 提案手法について
ェントが利用可能な視覚情報や聴覚情報には，情報欠落や雑音等の不確実性を有する要素があり，エー
3.1 アントコロニー最適化法(ACO)
ジェントの行動決定アルゴリズムには，それらを適
アントコロニー最適化法(ACO) [1,3,4]はDorigoらに切に処理するための頑健性が必要不可欠である．
より提案された群知能の一つの手法である．これは
我々は，例えばRSSでのサッカーエージェントのよ蟻の採餌行動における最短経路選択行動に着目した
うなMASにおける群知能を用いた協調行動の獲得を
メタヒューリスティクスである．
目指している．本研究ではエージェントの行動選択
採餌行動において，蟻は餌を発見した場合，巣へにおいて，群知能の一つの特徴であるフェロモンをの帰路においてその経路上に化学物質を散布する．
媒介としたコミュニケーションを用いた協調行動獲通常，この化学物質のことをフェロモンと呼ぶ．蟻
得手法の提案を行う．本稿では，アントコロニー最の場合，フェロモンは空気を媒介として拡散する．
適化法( Ant Colony Optimization : ACO )をMASにまた，空気中のフェロモンは時間とともに蒸発し，適用し，エージェントの行動獲得手法の提案を行う． 濃度が下がる．このような蟻の行動やフェロモンの
今回，実験システムとしてRoboCupサッカーシミュ
性質が相互作用し，蟻は複数経路からフェロモン濃レーションリーグにおけるサッカーエージェントに度が濃く最短である経路を選択する．
提案手法を組み込んだ．そのシステムを利用して実つまり，蟻は各個体が有する知能は単純であり，施した小規模な評価実験の結果についても報告する． 管理する個体が存在せずとも，各々が自律的に行動し，集団全体としては非常に高効率の行動を実行し- 40 -

ている．これは各個体がフェロモンを媒介としたコ
ミュニケーションを実施しているためである．
ACOでは組み合わせ問題等における最適解は，フェロモンの濃度及び経路に対するコストに計算される確率に基づき選択により決定される．既にSimpleACO(S-ACO)[1,4]が提案され，この手法では式１により経路選択のための確率値が計算される．

  ij (t ) ij ( j  J ik )kpij (t )     il (t ) il k lJ i
 0
(その他)

…式１

この式１において，τはその経路におけるフェロモ
ン強度，ηは対象となる問題におけるヒューリステ
ィクス値，J は選択可能な経路の集合，i あるいは j
は J に含まれる経路の端点それぞれ表わしている．
そして，式２によりフェロモン濃度を計算する．

 ij (t )  (1   ) ij (t )   ij k (t )m Qk ij (t )  k 1 L (t )0((i, j )  選択済みものの集合)(それ以外)…式２

この式２においてρはフェロモンの蒸発に関するパ
ラメータ，Δτはフェロモンの更新値，Q は経路におけるコストの総和の逆数，Ｌは選択した経路のコ
ストの総和をそれぞれ表している．これらは時系列に変化する値である．上述したようにフェロモンは時間が経つと蒸発し，濃度が下がる．また，経路が短ければフェロモン濃度は高くなる．

3.2 RSS サッカーエージェントへの S-ACO 適用
における問題点
ACOの一つであるS-ACOを巡回サラリーマン問題(TSP)に適用する場合[1,4]，巡回すべき都市の選択
は，例えば，エージェントにより散布されたフェロ
モンの濃度，都市間の距離に求まる数値及びこれらに関するパラメータにより決定される．
本研究では，ACOにおけるフェロモンを媒介としたコミュニケーション処理を，RSSのサッカーエー
ジェントに組み込む．しかし，ACOを用いた先行研究において利用されたTSP等の適用対象となる問題と比較し，RSSには幾つかの困難となる点がある．
例えば，マルチエージェント環境（エージェントやサッカーボールの位置，チーム間の得点差や各エー
ジェントの体力等）が実時間で変化し，さらにエージェントが利用可能な情報に不確実な部分や得られない情報がある．これらに加えて，予め，経路に関するコスト(TSPにおける都市間の距離)等の情報を知ることが困難である．これは，S-ACOを適用する
上で，大きな問題となる．
また，RSSにおける目標は味方チームの勝利，あるいは得点を多く取ることや失点を可能な限り減らすことにある．しかし，RSSのように適用対象となる問題の特性によってはフェロモン濃度の更新頻度が極めて少なくなる．実際，RSSのシミュレーショ
ンにおいても実際の人間同士のサッカーの試合と同様に得点機会は少ない．これもS-ACOを適用する際，大きな問題になる．

3.3

ヒューリスティクス値（η）

上述したように，適用対象となる問題によってはこの値の決定は困難である．そのため，提案手法ではシミュレーション結果を人手により正規化する．
具体的には，ヒューリスティクス値である適用対象問題におけるコスト値を計算する際，その初期値

Table 1: Values of Costs Calculated with both Result of simulations and Hand-Coding Rules(ηused in equation-1 )
a

b

c

d

e

f

g

h

i

j

A

0.00000.00000.00800.00270.00000.00000.00000.00000.08880.0301B

0.00000.00000.01210.00400.00000.00000.00000.00000.1036

0.3445C

0.00000.00000.01620.08610.26380.32300.57470.57470.11840.3876D

0.00000.00000.01620.01620.20460.42400.58140.28260.14000.3876E

0.00000.00000.01210.00400.00000.04850.00000.00000.14130.3445F

0.00000.00000.00800.00270.00000.00000.00000.00000.08880.3014- 41 -

をシミュレーション結果からサッカーエージェントのボールの保持の状況とした．つまり，シミュレー
ション結果でのボール保持確率をベースとした．さ
らにそれらを正規化することにより決定した[11]．
それらをTable 1に示す．シミュレーションを行う環
境（２次元サッカーフィールド[5]）を6行×10列の格子状に分割した．そして，前頁の Table１において，この a 列が味方チームのゴールに近い側であり，他方，j 列が相手チームのゴールに近い側の格子のデータを表す．また，A 行あるいは F 行はサイド側であり，C 行あるいはD 行はサッカーフィールド中央付近を表わしている．

3.4

4. 評価実験
4.1 ベースエージェント
提案手法を組み込む基となるエージェントを UvA
Trilearn 2003 Base [10]とした．このエージェントの基
本的な行動の以下に示す通りである．

( i ) ボールが自分にキック可能な位置にある場合，
予め定められた方向（相手チームのボールの方向）へボールをキック( ii ) 上記以外で自分がボールに最も近い選手である場合，自分がボールを蹴ることが可能となる位置まで移動( iii ) 上記以外の場合，予め定められた位置へ移動（各エージェントに応じたポジションを予め設定）

フェロモン濃度の更新処理

ACO ではフェロモン濃度の更新により最適解へと近づくが，上述したように適用対象となる問題の特性によってはそれが困難となる．
そこで，今回，フェロモン濃度の更新に必要となるＱの値の決定には我々が既に提案した手法におけるにおける研究成果[9]を利用した．つまり，式２におけるＱ値を Table 2 の様にした．
Table 2: Values of Pheromone Trails in Case of Some
Results in its Selecting Actions
試合の状況
Ｑの値
1.0
味方チームの得点
0.5
味方チームのコーナーキックの獲得
0.1
相手チームのゴールキック

Figure 1: Basic Algorithm of Soccer Agents in UvATrilearn 2003 Base [10]4.2 提案手法を組み込んだエージェント

これは，選択した行動に応じ，周囲の状況は異なることに着目し，S-ACO における報酬となるＱの値を変化させた．つまり，最も効果的な行動をとることから生じると思われる味方チームの得点という状況を生み出した行動を選択したケースには最も高い値を付与している．以降，有効と思われる順に上記の表の通りにした．
そして，フェロモン値の蒸発に関しては，上述のようにフェロモンの散布機会が非常に少ないことが予想されたので，単にシミュレーションのステップ数に応じた処理とした．6,000 ステップ，つまり１試合分経過したら初期化することとした．
さらに，フェロモンの伝播については，今回は考慮していない．これは適用している問題が複雑であるため，種々の要素を考慮しなくてはならず，現段
階では導入を行っていない．例えば，相手チームのエージェントやボールの位置，さらには試合の状況により考慮すべき事項は実時間で変化する．また，地域に依存する問題も考慮する必要がある．これに関して，今後の課題とし，検討を進める予定である．

上記[10]において，ボールをキックする際，そのボー
ルを蹴る方向を決定する処理に対して提案手法を適用した．つまり，ベースエージェントでは予め決められている位置にしかボールを蹴り出さなかったのに対し，提案手法を組み込んだエージェントは
S-ACO を利用し，適切な位置を決定し，その位置を目指してボールを蹴り出すことを実現する．

4.3 実験方法
提案手法を組み込んだエージェント（4.2 節）により構成するチームをチームＡとし，ベースエージェン
トのみで構成するチームをチームＢとした．
そして，これらのチームを利用し，RSS の環境下において 30,000 ステップ（５試合分）のシミュレー
ションを実行した（実験１）．

4.4 実験結果
チームＡ及びＢの得点を下記の Table 3 に示す．僅差ではあったがチームＡの得点の方がチームＢを勝り，さらに勝敗数においても優れていた．

4.5 考察提案手法の有効性，特にフェロモン濃度の更新処理に関して考察する．そのために，4.2 節において上述
した提案手法を組み込んだエージェントにおいてフェロモン濃度の更新の処理のみを取り除いたエージ
ェントを準備した．このようなエージェントのみに- 42 -

より構成するチームをチームＡ－とした．そして，チームＡ－とチームＢを利用し，実験１と同様に，30000
ステップのシミュレーションを実行した（実験２）．
その結果を下記 Table 4 に示す．
これらの比較から，これも僅かではあるがチーム
Ａにおける得点能力の高さが確認できる．つまり，提案手法においてフェロモン濃度の更新処理が有効に働いていることを確認できた．

Table 3: Result in Experiments
実験１
試合
ステップ数
チームＡ
チームＢ
0
0
①
1 ～ 600034②6001 ～ 12000
1
1③
12001 ～ 18000
10④18001 ～ 24000
1
3⑤
24001 ～ 30000
6
8
総 得 点
勝 敗 数
２勝１敗２分
(チームＡ基準)

Table 4: Result in Experiments
実験２
試合
ステップ数
チームＡ－
チームＢ
1
0
①
1 ～ 60001
3②6001 ～ 12000
2
1③
12001 ～ 18000
03④18001 ～ 24000
2
1⑤
24001 ～ 30000
6
8
総 得 点
勝 敗 数
３勝２敗０分
(チームＡ－ 基準)

考察を進める．また，解の多様性を保ちつつ，動的な環境下でより効率的に適切な行動へと収束させる
方法についても検討を行う予定である．例えば，帰納的に汎化し，規則を獲得する処理等である．
参考文献[1] M. Dorigo and T. Stuzle : Ant Colon Optimization,
The MIT Press, 2004.
[2] J.F. Kennedy, R. Eberhart and Y. Shi : SwarmIntelligence, Morgan Kaufmann Pub., 2001.
[3] 中道, 有田: ACOにおけるランダム選択に基づ
く多様性調節の効果,情処学会論文誌, Vol.43,
No.9, pp.2939-2946, 2004.
[4] 大内，山本，川村：マルチエージェント
システムの基礎と応用，コロナ社，2002.
[5] RoboCup Soccer Simulation League 公式ホーム
ページ：http://sserver.sourceforge.net/[6] 野田, 太田, 秋山:ロボカップサッカー
シミュレータ，人工知能学会誌，Vol. 20，No. 5，
pp. 50 - 58，2005.
[7] 村田, 鈴木, 大内: GA によるサッカー
エージェントの動的配置探索問題に関する研究，
人工知能学会誌，Vol.14, No.3, pp.446-454, 1999.
[8] 中島, 高谷, 有働, 石渕：進化型計算を用いたチーム戦略獲得手法の一提案, 人工知能学会,
SIG-CHALLENGE 研究会，2004．
[9] H. Sasaoka, S. Muraki and K. Araki : “Soccer
Agents Using Inductive Learning with Hand-Coded
Rules”, In Proceedings of 2003 IEEE International
Conference on Systems, Man & Cybernetics, pp. 46– 51, 2003.
[10] UvA Trilearn 2003 - Soccer Simulation Team：
http://remote.science.uva.nl/~jellekok/robocup/2003/[11]笹岡，山田：群知能を用いた RoboCup サッカー
エージェントにおける行動獲得手法の提案，情処学第70 回全国大会講演論文集第二分冊，pp. 51 - 52(2008)．

5. 今後について
本稿では，Ant Colony Optimization ( ACO )を用いたRoboCupサッカーエージェントの行動獲得手法についての我々の基本的な考え方を述べ，Simple ACO ( S-ACO )をサッカーエージェントに適用する手法を提案した．この中で，ヒューリスティクス値
であるηの決定方法及びフェロモン濃度の更新処理について述べた．さらに，提案手法の有効性を確認するため，実験用プログラムを作成し，小規模の評
価実験を実施した．そして，S-ACOにおけるフェロ
モン更新処理について考察するため比較実験を実施した．これらのことから今回提案した手法の有効性を確認した．
今後は，引き続き，大量の評価実験を実施する予定である．特に，獲得されたものの多様性について- 43 -

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

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

ARToolKit を用いたヒューマノイドロボットのモーション推定
Motion Estimation for Humanoid Robot Using ARToolKit

清水彰一 藤田征士 草富省吾 伊藤孝浩 藤吉弘亘
Shoichi Shimizu, Masashi Fujita, Shogo Kusatomi, Takahiro Ito and Hironobu Fujiyoshi

中部大学
Chubu University

shiyou@vision.cs.chubu.ac.jp

Abstract

まると，そのモーションが終了するまで他のモーションを受けつけないという問題点がある．そこで我々は，敵のThe RoboCup SSL Japanese teams have proposed a new league that uses humanoid robots
and a global vision system. The humanoid

モーションを考慮に入れた戦略を作成するために，敵のモーションを初期段階で推定する手法を提案する．モーションベースの手法では，同じモーションの動作は毎回同

robot is able to execute motions by selecting them from a list implemented in advance.

じになるはずであるので，ビジョンシステムによって観測したモーションと予め登録しておいたモーションを DP

While the humanoid robot is moving, it cannotchange the motion. Therefore, it is importantto estimate the motion by observing the humanoid robot using global vision systems. We

マッチングで比較し，ヒューマノイドロボットのモーショ
ン推定を行う．
提案するシステムでは，ロボカップ小型リーグと同様にヒューマノイドロボットの頭部にマーカを設置し，ID 認識

propose a method of motion estimation for humanoid robots using ARToolKit. Our methodと位置・姿勢推定を行う．ロボカップ小型リーグではマー
カの色情報よりロボットの ID 認識，位置・方向を推定し

uses the ARToolKit to obtain this observed information, which includes the position and poseof the humanoid robot. We show that the proposed method can estimate the motion within
15 frames from the frame in which the current
motion was started.

1ており，高精度に向きや ID 認識を行う手法が提案されている[Murakami, 2003][Ball, 2004][Bruce, 2003][Shimizu,

2005]．しかし，ヒューマノイドロボットの頭部に取り付けられたマーカの認識，位置・姿勢推定をする場合，マーカは 3 次元空間中で回転と移動をするため，今までの推定法を適応することは困難である．そこで我々は，1 台のカメラのみでマーカ認識と位置・姿勢推定を行うことができる ARToolKit[Kato, 1999]を使用することで，ヒューマ

はじめにロボカップ小型リーグの日本チームは，小型リーグの次ノイドロボットの観測データを取得する．

のステップとして，ヒューマノイドロボットとグローバル2

ビジョンシステムを用いた新しいリーグを提案している[Japanese SSL teams, 2007]．グローバルビジョンシステ

Small Size robot League next
generation (SSLng)

ムを用いることで，広い領域の状況を一度に知ることが可グローバルビジョンシステムはフィールド上の情報をリ能となり，ヒューマノイドロボットに搭載されているロー

アルタイムで得ることが可能である．これらの情報から

カルビジョンの視野の狭さを補うことができる．グロー

戦略を作成し，命令をロボットに送信することでスピー

バルビジョンを用いて状況把握を行うことで，戦略の幅

ディーな試合が展開される．このようなビジュアルフィー

を広げ，人間との対戦に向けヒューマノイドロボットの製ドバックによるロボット制御技術はロボカップ小型リーグ

作と制御法の向上が期待できる．

ですでに確立されている．現在提案されているヒューマノ

小型のヒューマノイドロボットを制御する手法には，モーションベースの手法[Friedmann, 2006]が一般に用いられ

イドロボットを用いた新しい小型リーグ SSLng では，ロ
ボカップ小型リーグで使用している戦略や，ビジョンシスている．モーションベースの手法は，一度モーションが始テムなどを利用することで，新しいリーグを容易に立ち- 44 -

Figure 1: SSLng のフィールド上げることができる．この新しいリーグのロボットは統Figure 2: 各座標系の関係

一規格であり，4 足リーグのチームも容易に参加することができると考えられる．以下に，SSLng の特徴を示す．

ARToolKit を用いることで，1 台のカメラから ID の認識，
1. 4 軸ホイールの代わりにヒューマノイドロボットを 5台使用する．

マーカの位置と姿勢推定を行うことが可能となる．

ARToolKit は，図 2 に示すマーカ座標系とカメラ座標

2. 使用するロボットは，統一規格で作成され，すぐに入手できるものとする．また，チームでオリジナルのロボットの作成も可能とする．

系を持つ．ARToolKit の出力は，マーカ座標とカメラ座
標間の回転行列 Rmc と平行移動ベクトル T mc であり，マーカの姿勢と位置である．マーカ内部のパターンは，ID認識するためのパターンであり，ユーザが任意に作成す

3. 現在のグローバルビジョンシステムの代わりに，図 1

ることができる．図 3 に，我々が使用するマーカを示す．

に示すようにカメラを設置する．基本的に，カメラ

ARToolKit では，色情報も用いたパターン認識を実現しており，現行のロボカップ小型リーグと同様に，色毎にの台数は 2 台とする．

チームを分けて使用することが可能である．また，活字

4. 共有ビジョンシステム (カメラも含めて) を委員会が提供する．ロボットの位置と姿勢，ボールの位置の用の活字 (OCR-B フォント) を背番号としてマーカにつけ情報を得ることが可能である．また，チーム独自のることで，ロボットの ID 認識を行うことが可能である．

認識の分野で高精度に認識できるように設計された OCR

ビジョンシステムも使用可能とする．
このように，SSLng では，ヒューマノイドロボットの状態をグローバルビジョンで検出し，戦略を作成することが要求される．本稿では，SSLng の実現に向け，マー
カをヒューマノイドロボットの頭部に設置し，ARToolKitを用いたヒューマノイドロボットの ID 認識と位置・姿勢推定を行う手法を提案する．また，ヒューマノイドロボッ
トの動作はモーション毎に一定であることから，モーショ

ID 認識

ARToolKit の ID 認識はテンプレートマッチングを用いて行う．まず，図 4(a) の入力画像からマーカの正方形の 4頂点を検出する．次に，この 4 頂点間の 1 辺の長さが既知であることと検出した 4 頂点の関係から，式 (1) の H
を求める．

⎡

⎤
⎤
⎡
xi
Xm
⎢
⎥
⎥
⎢
α ⎣ yi ⎦ = H ⎣ Ym ⎦11ン推定法も提案する．

3

3.1

ARToolKit を用いたグローバルビジョン
システム

(1)

ヒューマノイドロボットのマーカは 3 次元空間を移動し，この式は，マーカ座標系 Xm −Ym 平面内の点 (Xm , Ym , 0)

回転するため，1 台のカメラからヒューマノイドロボット

を，画像座標系上の点 (xi , yi ) に変換する．したがって，の位置と姿勢を推定することは難しい問題となる．そこ

マーカ内部のパターンは式 (1) により，図 4(b) の正規化

で，提案手法では ARToolKit を用いて，ヒューマノイド

画像を得る．この正規化を行った画像と予め登録してあロボットの ID 認識と位置・姿勢推定を行う．ARToolKitるパターンとテンプレートマッチングをすることでマーは，拡張現実感の世界で使用されているシステムであり，カの ID を識別する．また，登録パターンを 90 度ずつ回

予め登録しておいたマーカを認識し，位置と姿勢推定す

転したパターンも登録しておくことにより，マーカの回転ることで，画像上に仮想物体を表示するシステムである．

に対する不変性を得る．

- 45 -

Figure 5: ARToolKit を用いた ID 認識と位置・姿勢推定

Figure 3: 黄色と青のマーカ

Figure 6: ヒューマノイドロボット用する．本提案手法では，これらの情報を用いることで，モーションを観測し，推定を行う．

Figure 4: パターンの正規化
3.2

マーカ位置と姿勢推定

4ロボットのモーション推定

ARToolKit は 1 台のカメラを用いて，カメラ座標のマー
カの 3 次元位置 T c = [Xc Yc Zc ]T と姿勢 Rc を出力する．

多くのロボットはモーションベースで制御される．この

図 5 に ARToolKit を用いて ID 認識とマーカの位置・姿場合，モーションは毎回同じ動作となる．そこで我々は，勢を推定した例を示す．黄色のマーカを球，青色のマーカ

ARToolKit を用いてロボットを観測し，得られる頭部のを立方体で表示し，球と立方体の数が ID のナンバーと対

3 次元位置情報から DP マッチング行い，ヒューマノイド
ロボットのモーションを推定する手法を提案する．

応する．

ARToolKit によって得られる 3 次元位置は，カメラ座標系であるので，ヒューマノイドロボットがサッカーを行

4.1

うためには，世界座標系へ変換する必要がある．図 2 に

図 6 に我々が使用するヒューマノイドロボット (近藤科学

示すようにカメラ座標系から世界座標系への変換は，回社製 KHR-1HV) を示す．このヒューマノイドロボットは，

転行列 Rcw と平行移動ベクトル T cw から行うことができ

歩行や旋回などのモーションが提供されており，ヒューマる．これらのパラメータは，予めカメラキャリブレーショ

ノイドロボットの製作知識を必要とせずに，SSLng リーンによって取得しておく．世界座標のマーカの 3 次元位置

グに参加することが期待される．

X w = [Xw Yw Zw ]T を以下の式を用いてカメラ座標系の3 次元位置 T c = [Xc Yc Zc ]T から求める．

ヒューマノイドロボットのモーション提供されているモーションの中で，サッカーに必要なモーションは，歩行，サイドステップ (左右)，旋回 (左右)の 5 種類となる．これにキックの動作を加えた計 6 種類のX w = Rcw T c + T cw

(2)

また，マーカの向き θ は，マーカ座標系の単位ベクトルe = [1 0 0]T と Rcw と Rmc ，世界座標系に変換された単位ベクトル e = [ex ey ez ]T を用いることで求められる．
θ= arctan(ex , ey )

(3)

e

= Rcw Rmc e(4)

このマーカの 3 次元位置と向きがヒューマノイドロボットの位置と向きとなり，サッカーの戦略を作成するために使- 46 -

モーションがサッカーに最低限必要である．したがって，
これらのモーションを推定することにより，サッカーを行うヒューマノイドロボットの状況を把握することがで
きる．

4.2

モーションの観測

ARToolKit の出力から式 (2) と式 (3) を用いて，世界座 標 の ヒュー マ ノ イ ド ロ ボット の 位 置 と 向 き X  =[Xw Yw Zw θ]T を算出する．モーションを推定するための観測データとして，各変位 ΔX = [ΔXw ΔYw ΔZw Δθ]T

以上の操作を各格子点にて行い，式 (10) より累積距離をそれまで辿った経路の長さ c(i, J) で正規化する.

G(i) =g(i, J)c(i, J)(10)

予め測定しておいたモーションを登録パターンとする．
推定するモーションは，歩行 (前)，サイドステップ (左右)，旋回 (左右)，キックの 6 種類とする．ARToolKit を用いて観測した入力パターンと全登録パターンとの DP マッ
チングを行う．そして，累積距離が最小となる登録パター

Figure 8: 対称 DP パス

ンのモーションの累積距離 G0 と次に小さい登録パターン

を次式から計算する．

のモーションの累積距離 G1 が以下の条件を満たすとき，

ΔX i = X 0 − X i , (i : フレーム番号)(5)

図 7 に各モーションの観測データを示す．この図から，累積距離が最小となる登録パターンを入力パターンのモーションとして決定する．

G0 < G1 × β

各モーション間で類似性が低く，分離することが可能であ(11)ると推測できる．

β を低く設定することで信頼度の高い結果を出力すること
4.3

DP マッチングを用いたモーション推定になる．この条件を満たさないときは，登録パターンにな

DP マッチングは，異なる二つの時系列信号の類似度と最適な対応を求める手法であり，音声認識等の，さまざまないモーションとして該当なしとする．例えば，ヒューマノ

分野で利用されている．DP マッチングは非線形の伸縮にれる．

より，長さの異なるパターンの類似度を計算することができる[Sakoe, 1978]．

5

イドロボットが倒れた際などは，該当なしとして判定さ実験提案手法では，データの始点を固定しない DP マッチン

提案手法の有効性を図るため，モーション推定実験，モーグを行う．以下に，DP マッチングの適用法について示す．

ションに必要なフレーム数の評価，連続モーションによるDP マッチングにおける始端領域においては，式 (6) に示すような初期値を設定する．
g(i, 0) = 0 (i = 0, 1, . . . , I)
(6)g(0, j) = ∞ (j = 1, 2 . . . , J)

モーション推定実験を行う．本実験では，式 (11) の β を

DP マッチングに用いる DP パスを図 8(a) に示す．各格
子点 (i, j) における累積距離 g(i, j) を次式より求める．
g(i, j) =⎧⎪⎨ g(i − 1, j − 2) + 2 · ld(i, j − 1)ming(i − 1, j − 1) + ld(i, j)⎪⎩g(i − 2, j − 1) + 2 · ld(i − 1, j)

0.7 として設定して，モーションの推定を行う．
5.1

提案手法を評価するために，モーションの推定実験を行う．各モーションを上下左右にヒューマノイドロボットの方向を変更して，10 回ずつ測定する．したがって，モーションの合計は 40 シーンとなる．フレーム数は，全シー⎫: (a) ⎪
⎬
: (b)
⎪
⎭
: (c)
+ld(i, j)

ン共に 120 フレームとする．各モーションの 1 シーン目
を登録パターンとして登録し，1 シーン目以外と DP マッ
チングを行い，モーションの推定を行う．

(7)

提案手法によってモーションを推定した結果，100 % の識別率を得ることができた．これは，入力するパターンが登録パターンと同じフレーム数であるため簡単な問題でローカルディスタンス ld(i, j) は式 (8) より求める．

あるといえる．

ld(i, j) = ||ΔX i − ΔX j ||

(8)
5.2

このとき使用するデータは，初期フレームのヒューマノ
イドロボットの向きを軸とするように，観測データを変換したものを用いる．格子点 (i, j) までに選択された経路の長さを式 (9) より求める．
⎧⎪⎨ c(i − 1, j − 2) + 3
c(i, j) =c(i − 1, j − 1) + 2⎪⎩c(i − 2, j − 1) + 3

モーション推定

入力フレーム数と認識率の評価

モーション推定では，いかに早い段階でモーションを推定できるかが重要となる．したがって，少ない入力フレーム
でモーションが推定されるべきである．そこで，入力フレーム数を 10 フレームから全フレーム (120 フレーム) に

if(a)
if(b)

変化させたときの認識率を評価する．表 1 にモーション推

(9)

if(c)

定に必要なフレーム数を示す．この結果から，モーション
は動作の始まりから 15 フレーム以内で推定できることが- 47 -

Figure 7: 各モーションの観測データ
から 86 フレーム目まで，歩行モーションとして推定されTable 1: モーション推定に必要なフレーム数ており，143 フレームから 214 フレームは左旋回と推定さ

歩行
10.6

れていることがわかる．また，歩行と左旋回の間には待機

左ステップ
10.1

左旋回
14.7

右ステップ
10.4

右旋回
12.0

キック
10.2

状態が含まれていることもわかる．しかし，待機モーショ
ン中に式 (11) の条件を満たさないため，該当なしと判定されているフレームがある．これは，キックモーションのx 軸と y 軸の変化が少なく累積距離が小さいため，待機
モーションと有意な差が表れなかったためである．連続したフレームであることを考慮にいれることで，この問題を解決することが可能であると考えられる．以上の結果
から，連続したモーションにおいても提案手法は誤認識が少なくモーションの推定を可能とすることを示した．

Figure 9: 入力パターンが歩行のときの累積距離わかる．したがって，敵ロボットのモーション開始後 15

6まとめフレームで，モーションを推定可能であり，敵のモーショ

本稿では，DP マッチングを用いてロボットのモーションンを考慮に入れた戦略を作成することが可能となる．ま

推定を行う手法を提案した．ARToolKit を用いることにた，図 9 に示すように，フレーム数が増えるにつれ累積

より，ヒューマノイドロボットの頭部に取り付けたマーカ

距離 (式 (10)) が他の登録モーションより大幅に小さくなの認識と位置・姿勢推定を行い，それらの情報を DP マッ

るため，高精度にモーション推定が可能である．また，式

チングのパターンとして使用した．入力パターンと登録(11) を満たす必要があるため，入力フレームが少ない場
合でも，信頼度の高いモーション推定が期待できる．

パターンのフレーム長が同じ時，モーションの推定は 100

5.3

連続モーションの推定% 成功することを確認した．また，初期フレームから 15
フレーム以内にモーションの推定が可能であることを示した．したがって，敵のモーションが動き始めから 15 フ

実際のシーンでは，モーションは連続して観測される．そ

レーム以内にわかり，そのモーションにしたがって戦略をこで，二つのモーションと待機からなる連続モーションに作成することが可能となる．

ついて推定を行う．

今 後 の 予 定 と し て ，カ メ ラ の 解 像 度 を FULL HD

図 10 にモーションを推定した結果を示す．11 フレーム

- 48 -(1920x1080 pixels) にして，実際のフィールドサイズでFigure 10: 連続した入力からのモーション推定の実験である．

2004 Australasian Conference on Robotics and Automation (ACRA), 2004.

参考文献[Japanese SSL teams, 2007]
SSL Next Generation : http://www.aichi-pu.ac.jp/ist/lab/narulab/indexNewSSL.html[Friedmann, 2006] M. Friedmann, et al.: Versatile, highquality motions and behavior control of humanoid soccer robots, Proc. of the Workshop on Humanoid Soccer
Robots of the 2006 IEEE-RAS International Conferenceon Humanoid Robots, pp. 9–16, 2006.
[Murakami, 2003] K. Murakami, S. Hibino, Y. Kodama, T.
Iida, K. Kato, S. Kondo and T. Naruse:
Cooperative Soccer Play by Real Small-Size Robot, RoboCup
2003: Robot Soccer World Cup VII, Springer, pp. 410–
421 2003.
[Ball, 2004] D. Ball, G. Wyeth and S. Nuske: A Global
Vision System for a Robot Soccer Team, Proc. of the- 49 -[Bruce, 2003] J. Bruce and M. Veloso: Fast and Accurate
Vision-Based Pattern Detection and Identification, Proc.
of ICRA-03, the 2003 IEEE International Conference on
Robotics and Automation, (ICRA’03), 2003.
[Shimizu, 2005] S. Shimizu, T. Nagahashi, and H. Fujiyoshi: Robust and Accurate Detection of Object Orientation and ID without Color Segmentatio, Proc. of
ROBOCUP2005 SYMPOSIUM, 2005.
[Kato, 1999] H. Kato, M. Billinghurst: Marker Tracking
and HMD Calibration for a video-based Augmented Reality Conferencing System, Proc. of the 2nd International
Workshop on Augmented Reality (IWAR 99), pp. 85–94
1999.
[Sakoe, 1978] H. Sakoe and S. Chiba: Dynamic Programming Algorithm Optimization for Spoken Word Recognition, IEEE Trans. on ASSP, Vol. 26, No. 27, pp. 43–49,
1978.

c 2008°

Special Interest Group on AI Challenges
Japanese Society for Artificial Intelligence
社団法人 人工知能学会 AI チャレンジ研究会〒 162 東京都新宿区津久戸町 4-7 OS ビル 402 号室 03-5261-3401 Fax: 03-5261-3402(本研究会についてのお問い合わせは下記にお願いします.)AI チャレンジ研究会
主査中臺 一博(株) ホンダ・リサーチ・インスティチュート・ジャパン〒 351-0114 埼玉県和光市本町 8-1
Tel: 048-462-5219
Fax: 048-462-5221 /東京工業大学大学院 情報理工学研究科
nakadai@jp.honda-ri.com
主幹事
光永 法明
金沢工業大学
基礎実技教育課程〒 921-8501 石川県石川郡野々市町扇が丘 7-1
Tel: 076-248-8754
Fax: 076-294-6723
mitunaga@neptune.kanazawa-it.ac.jp

SIG-AI Challenge
Executive Committee Chair
Kazuhiro Nakadai
Honda Research Institute Japan
8-1 Honcho, Wako,
Saitama, 351-0114, JAPAN /Dept. of Mechanical andEnvironmental Informatics, Graduate School of Information Sci. andEng., Tokyo Institute of Technology
Secretary in Charge
Noriaki Mitsunaga
Dept. of Practical Eng. Education,
Kanazawa Institute of Technology
7-1 Ohgigaoka Nonoichi,
Ishikawa 921-8501, JAPAN

担当幹事
上田 隆一
東京大学大学院工学系研究科
精密機械工学専攻知能システム分野〒 113-8656 東京都文京区本郷 7-3-1
Tel: 03-5841-6486
Fax: 03-5841-6487
ueda@robot.t.u-tokyo.ac.jp

Secretary in Charge
Ryuichi Ueda
Dept. of Precision Engineering,
School of Engineering,
The University of Tokyo
7-3-1 Hongo, Bunkyo-ku,
Tokyo, 113-8656, JAPAN

担当専門委員浅田 稔
大阪大学大学院 工学研究科
知能・機能創成工学専攻 先導的融合工学講座〒 565-0871 大阪府吹田市山田丘 2-1
Tel: 06-6879-7349
Fax: 06-6879-7348 /JST ERATO 浅田共創知能システムプロジェクト
asada@ams.eng.osaka-u.ac.jp

Advisory
Minoru Asada
Dept. of Adaptive Machine Systems,
Graduate School of Engineering,Osaka University
2-1 Yamada-oka, Suita,
Osaka 565-0871, JAPAN /JST ERATO Asada Synergistic
Intelligence Project

SIG-AI-Challenges web page; http://winnie.kuis.kyoto-u.ac.jp/SIG-Challenge/