進化型移動ロボットの検定に基づくシミュレーションの更新法
An Update Method of Computer Simulation for an Evolutionary
Mobile Robot Based on Statistical Tests○片田 喜章Yoshiaki KATADA
摂南大学
Setsunan University
katada@ele.setsunan.ac.jp

後藤 龍彌
Tatsuya GOTOH
摂南大学
Setsunan University

Abstract: One of advantages of evolutionary robotics over other approaches in embodied cognitive
science is its parallel population search. However, it generally takes an unrealistically long time toevaluate all candidate solutions by using a real robot. Thus, it makes difficult to use physical robots
for evolution without any consideration, especially in the case of tasks with human intervention. One
approach to overcoming this problem would be the use of simulations. Computer simulations may be
helpful to reduce the amount of experimental time to evaluate individuals in a population. However,the controllers evolved in a simulated environment do not always work well in the real one becauseof uncertain effects, e.g., noise and differences in the electronics and mechanics of robots. Therefore,
the validity of simulations is a particularly relevant problem. In this paper, in order to overcome thisproblem, we propose an update method of simulated robot/environment interaction dynamics based on
statistical tests during evolution. Then we conduct a series of experiments with a mobile robot in order
to investigate the effectiveness of the proposed method.

1

はじめにロボットが実環境で振舞うためには，システム自身が高い環境適応能力を有し，環境との相互作用を通して自らの振舞いを獲得しなければならない [1]．このアプローチの一つに多点探索による高い解探索能力が期待できる人工進化を用いて自律ロボットの制御器を設計する進化ロボティク
ス (Evolutionary Robotics:ER)[2] がある．
進化ロボティクスでは，制御器の評価は a) 実環境で実ロボットを用いる [3]，または，b) シミュレーションを用いて行われる [4]．a) の方法ではロボットは振舞うべき実環境で進化するため，その環境で適切に振舞うことができる．しかしながら，集団中のすべての個体を実環境で進化させるには膨大な実時間がかかる．人工進化で要する進化時間は数百世代から数千世代が一般的であり，さらに人の介入を必要とする類のタスクでは実質的に進化させることは不可能になる．この問題に対し，実時間を削減させる研究として，同じ構造のロボットを複数台用意し，並行して進化させる研究がある [3]．このようにロボットを複数台用意する場合，同じ構造でもセンサーやアクチュエータなどの部品によっては，機械的・電気的な性能の違いが生じるため，すべてのロボットで適切に振舞う制御器を獲得することは難しいと予想される．また，ロボットを複数台用意するためのコストもかかる．片田ら [5] は，可能な限り人工進化が解くべき問題の探索空間を小さくする，つまり，遺伝子長を短くし，進化時間を短くする方法を提案している．しかし，この方法は設計変数の定義域を粗くコーディングしていることになり，望ましい振舞いを示す個体もしくは実行可能個体を獲得できない可能性がある．
一方，b) の方法では，ロボットの評価にかかる時間を非常に短くすることができるが，シミュレーションで獲得した制御器を実ロボットに搭載した場合，シミュレーションと実環境のギャップによってロボットが必ずしも実環境で適切に振舞えるとは限らない [6]．この問題に対して Jakobi
らは Minimal Simulation を提案している [4]．これは，望ましい振舞いの創発に関連するロボットと環境の相互作用のみをモデル化する方法であるが，実験者の経験に大きく依存する．また，Miglino らはあらかじめすべてのセンサ・アクチュエータに関して，細かい精度でサンプルデータを取得し，精度の高いシミュレーションモデルを構築した [7]．しかし，この方法はすべてのサンプルデータを事前に用意しているため，時間の経過によるセンサ・アクチュエータの機械的・電気的な変化に対応できないという問題がある．
上述の問題点に対し，オンラインでサンプルデータを取得していきシミュレーションモデルを構築する方法が考えられる [8]．この考え方に基づき，高崎ら [9] は，個体集団中で実環境とシミュレーションで評価する個体を分け，実環境で評価している間に実環境の入出力に関するデータを取得し，オンラインでシミュレーションモデルを更新する方法を提案している．しかし，高崎らの方法では，実環境とシミュレーションモデルの整合性は十分に保証されていないという問題がある (3.4 節で詳述)．そこで，本研究では高崎らの方法に改良を加え，実環境とシミュレーションモデルの整合性が十分に保証される更新法を提案する．提案手法の有効性を，移動ロボットを用いたゴール到達問題において検証する．

2

シミュレーションモデルの更新法

実環境におけるセンサ入力-モータ出力関係のサンプルデー
タ集合を R(s, a)(s:センサ入力，a:モータ出力) とし，シミュレーションにおける入出力データ集合を M (s, a) と表す．

- 128 -

goal

3000mm

m
3000m

robot

(a) real environment

Fig. 1: Evolution based on on-line model update

ここで，R(s, a) をもとに M (s, a) をオンラインで構成・更新する．この方法を用いた進化計算プロセスは次のようにまとめられる (Fig.1)．

(b) mobile robot(c) goalFig. 2: Experimental setup for a real environment

ステップ 1 個体集団を実環境で評価する個体とシミュレーションで評価する個体に分ける．
ステップ 2 実環境で個体を評価する間に，R(s, a) を取得し，M (s, a) に加える．

goal

ステップ 3 実環境での評価後，R(s, a) をもとに検定を行い，M (s, a) を更新する．更新された M (s, a) を用いて，シミュレーションで残りの個体を評価する．

wall

ステップ 4 実環境とシミュレーションで得た評価値に基づき選択を行い，遺伝的操作により次世代の個体を生成する．

goal

wall

(a) Camera image(b) Binarized image

ステップ 5 終了条件に達するまで 1→4 を繰り返す．

Fig. 3: Omni-directional image plane

ステップ 3 で，R(s, a) と M (s, a) の差が有意でなければR(s, a) と M (s, a) は等しいとする．もし有意であれば，有意でなくなるまで M (s, a) を繰り返し修正する．

3

移動ロボットのシミュレーションモデル

3.1

実験環境

本稿ではロボット制御問題の 1 つであるゴール到達問題において 2 節で示した提案手法の有効性を検証する．
実験環境を Fig. 2(a) に，実験に用いる移動ロボットをFig. 2(b) に示す．実験環境は平面で，3000 mm×3000 mmの正方形であり，周囲は壁で囲まれている．移動ロボット
は全方位カメラを搭載し，画像処理とロボットの制御を行うノート PC を搭載している．直径 380 mm，左右二輪独立駆動型である．ロボットが全方位カメラ画像を通して認識できる目標物 (ゴール) の形状は赤色の円筒形 (直径 300mm・高さ 290 mm) とする (Fig. 2(c))．

3.2

した．4 節で説明する目標物検出法に基づき，各セルにおいて目標物の存在を検出する．上で述べたように全方位カメラを用いた場合，平坦な環境では比較的高い精度で距離情報が得られることから，本研究ではセンサ入力モデルの更新は行わず一定とする．

3.3

文献 [11] から，左右モータへの速度入力に対する移動ロボットの実環境での移動量 (xR , yR , θR )(Fig. 4) は，実環境で計測した移動量データから求まる平均 (µxR , µyR , µθR )と分散 (σx2R , σy2R , σθ2R ) の正規分布で表されることが報告されている ((1) 式)．

センサ入力モデル

全方位カメラを用いる場合，一般的に角度情報は信頼性が高く計算も容易であるが，距離情報は計算が複雑になる．
しかし，平坦な環境では距離情報は計算が容易であり [10]，取得した画像の中心から同心円上では，全方位カメラの中心からの距離がほぼ一定となる．そこで，Fig. 3(a) に示すように円周方向に一定の角度 (22.5◦ ) で 16 分割し，半径方向に同心円で 7 分割して計 112 個のセルに画像を分割モータ出力モデル

xR=N (µxR , σx2R )yR=N (µyR , σy2R )=N (µθR , σθ2R )

θR

(1)

本研究で用いる移動ロボットの任意の速度入力 (デューティ比:4 節で述べる) に対する移動量は正規分布に従うことを予備実験において確認していることから，(1) 式をモータ出力モデルとして採用する．

- 129 -

Fig. 4: Displacement in a relative coordinate

3.4

Fig. 5: Displacement in an absolute coordinate

時に現世代から 500 世代以前のものは XR0 から削除する)．
XR 0 ← XR 0 + XR
(4)

仮説検定に基づく出力モデル更新

3.2 節で述べたように，入力モデルに関しては一定と仮定しているため実験の間更新しないが，出力モデルに関しては実環境の移動量データを基に更新する．このとき，はじめにで述べたように，時間経過に伴い，実環境で得られた移動量データとシミュレーションモデルを構成している移動量データとの間にギャップが生じてしまう可能性がある．
そこで，両データの整合性を保証するため，仮説検定に基づく更新を行う．シミュレーションモデルの更新法の概略についてはすでに 2 節で述べた．本節では 2 節の進化計算プロセス (ステップ 2,3) について詳述する．
3.3 節で述べたように，モータへの速度入力に対する移動量は正規分布に従うことから，平均と分散を考慮し，t検定および χ2 検定を用いる ( はじめにで述べたように，
文献 [9] の方法では平均しか考慮されていない)．以下にその方法を示す．

検定回数を表すフラグを count = 0 とする．

4. シミュレーション構成用の移動量データ集合 XM の2
平均を µXM ，分散を σX，実環境から得られた各移M2と動量データ集合 XR0 の平均を µXR0 ，分散を σX
R022する．σXM = σXR0 を仮説 1 とし，有意水準 α = 0.05で χ2 検定を行う．
5. 仮説 1 が棄却されたとき XM と XR0 の間に差が生じているため, XM を補正し，σXM を σXR0 に近づけていく．ここで，σXM < σXR0 のとき，XM に関して明確な方針の下で補正を行えないため，XM をそのまま XR0 に置き換える．σXM ≥ σXR0 のとき，XMのデータ補正を行う．ここで，µXM < µXR0 のとき，XM において値のもっとも小さいデータを削除することで σXR0 に近づける．逆に，µXM ≥ µXR0 のとき，XM において，値の最も大きいデータを削除することで σXR0 に近づける．このとき，補正するデー
タ数は 1 ずつとする．4. へ戻る．
仮説 1 が採択されたとき，6 へ進む．

1. 実環境の上方に CCD カメラを設置し，ロボットの重心位置と前方位置を取得する．このとき，ロボットの重心位置は Fig. 2(b) で示すロボットの上に取りつけた青いマーカー (Fig. 4 参照) の中心で，前方位置は赤いマーカーの中心である．
2. Fig. 5 に示すように，ロボットの重心位置と前方位置から絶対座標におけるロボットの位置・姿勢 (xt , yt , θt )を計算し，同様に 1 秒後のロボットの位置・姿勢(xt+1 , yt+1 , θt+1 ) を計算し，速度入力に対する実環境での相対移動量 (xR , yR , θR )(Fig. 4) を取得する((2) 式)．
(xR = xt+1 − xtyR = yt+1 − yt(2)
θR = θt+1 − θt

6. µXM = µXR0 を仮説 2 とし，有意水準α=0.05 で t 検定を行う．
7. 仮説 2 が棄却されたとき XM と XR0 の間に差が生じているため, XM を補正し，µXM を µXR0 に近づけていく．ここで ，µXM < µXR0 のとき，XM において値のもっとも小さいデータを削除することで σXR0 に近づける．逆に，µXM ≥ µXR0 のとき，XM において，値の最も大きいデータを削除することで σXR0 に近づける．6. へ戻る．
仮説 2 が採択されたとき，count = count + 1 とする．

モデル更新は xR ，yR ，θR の各座標軸および各速度入力値の組合わせに対し独立に行う．表記の簡略化のため，以降，相対移動量 xR についてのみ説明を行
い，yR ，θR については省略する．

3. 取得したモータコマンドに対する相対移動量 xR の集
合 XR をシミュレーション構成用の移動量データ集
合 XM に加える．
XM ← X M + XR

8. count = 1 のとき，4. へ戻る．
count = 2 のとき，更新を終了．
補正後のデータを基に，シミュレーション上での移動量
モデル ((5) 式) を求める．

(3)

また，XR を現在の世代から 500 世代前までに実環境で得られた移動量データの集合 XR0 に加える (同- 130 -xM

2= N (µXM , σX)
MyM= N (µYM , σY2 M )θM

N (µθM , σθ2M )

=(5)

4

実験設定

4.1

タスクと適応度関数

ロボットは，より早くゴールに到達することを目的とする．
ロボットの初期位置は環境 (Fig.2(a)) の左下，初期姿勢は上向きと右向きの 2 通りとする．ゴールの位置は右上とする．実環境での評価は，ロボットの各初期姿勢において，それぞれ 1 試行ずつ計 2 試行行う．1 試行はロボットが目標物に到達するか，40 ステップで終了とする．このとき，1 ステップは約 1 秒と設定する．なお，ロボットのゴール判定は搭載されている全方位カメラを用いて行う．

4.2

4.2.1ロボット設定

センサ入力

3.2 節で述べたように，ロボットは全方位カメラを用いて目標物の位置を以下のように検出する．
1. 全方位カメラの画像 (Fig. 3(a)) に対し，2 値化，ラベリング，重心算出の画像処理を行い，目標物と床面が接しているエッジ部分を検出する．目標物は赤色の円筒形をしているため，赤色の物体を抽出するようにしきい値を設定する．2 値化処理した画像を Fig. 3(b)に示す．
2. 検出されたエッジ部分の位置に対応するセルから，半径方向に沿って外側のセル全てに対して入力値 1 を与える．

4.2.2

制御器

ロボットの制御器として，出力関数にシグモイド関数を用いた人工神経回路網 (ANN) を用いる．中間層と出力層のニューロンは完全相互結合 (非対称) しており，自己結合をもつ．このとき，112 に分割されたセル (3.2 節参照)を入力値として扱うため，入力ノード数を 112 とする．また，左右のモータコマンドを決定するために出力ノード数を 2 とし，中間ノード数を 1 に設定する．

4.2.3

モータ出力

4.3

F itness =5

N umTXrials
k=1(1 −Step) (6)M axStep

実験結果

世代数に対する適応度の推移を Fig. 6 に示す．最大適応度および平均値が初期世代から大きく上昇し，100 世代辺りから最終世代まで安定した適応度を示していることが確認できる．次に，各世代に対するデータ補正回数を Fig. 7 に示す．450 世代まではデータ補正がなく，500 世代で急激に増加し．その後は少しずつ補正を行っていることが確認できる．
最終世代で得られた最良個体の実環境での振る舞いを初期姿勢右向きの場合について Fig. 9 に示す．ロボットは，対角線上の目標物に対し，左に動き過ぎては右へ，右に動き過ぎては左へと進行方向を変え，左右のモータ出力をうまく調節しながら目標物に到達している (Fig. 9)．初期姿
勢上向きの場合も，右向き姿勢同様にモータ出力を調節しながら目標物に到達する振舞いを示している (Fig. 10)．実環境でタスクを達成する振舞いを示したことから，実環境を反映したシミュレーションモデルの構築ができたといえる．また，実験時間は約 3 時間で終了したことから，実環境のみで評価を行う場合と比べて大幅に短縮できている．
0.8
0.6

進化計算設定進化手法として拡張型 GA の 1 つであり ANN の進化に対し有効性が確かめられている Operon GA(OGA)[12, 13, 14]を用いる．OGA の個体表現は，ANN の結合係数を変数とし，10 ビットのバイナリコーディングを行う．ここで，入力ノード数を Ns 個，中間ノード数を Nh 個，出力ノードをNo 個としたとき，結合係数の総数 (Nh + No )(Ns + Nh +No ) 個となり，遺伝子長は L = 10(Nh + No )(Ns + Nh +No ) ビットとなる．前節で述べたように Ns = 112, Nh =1, No = 2 と設定するので L = 3450 となる．OGA では遺伝的操作として点突然変異に加えて 5 つの遺伝的操作を用いる．これらは結合，分割，重複，欠失，逆位とよ

1N umT rials

ここで，N umT rials は試行回数 (2) であり，M axStep は40 である．そして，2 節で提案した更新法に従い，50 世
代ごとに前世代の適応度上位 2 個体について，初期姿勢
上向き 1 試行・右向き 1 試行の 2 試行のみ実環境で評価する．実環境での評価の間，ロボットの移動量データを取得することで，シミュレーションのモデル更新を行う．残りの個体および他の世代 (g 6= 50n, n = 0, 1, 2, · · · , 20) ではシミュレーションのみで評価する．なお，初期世代のシミュレーションでは，実験前にあらかじめ実環境で取得した各モータへの速度入力に対する移動量データ 15 個をもとにモデルを構成する．

Fitness

ロボットの左右の DC モーターは，PWM 制御によりそれぞれ 9 段階 (前進方向) の速度制御 (デューティ比: D ∈{60, 65, · · · , 100}[%]) が可能である．速度入力値であるデューティ比は ANN の出力値を 9 段階に割り当てることで決定される．従って，左右モーター速度の組み合わせにより 9 × 9 = 81 通りの行動を取り得る．この 81 通りのモータ出力に対して，モデル更新を行う．

ばれ，各パラメータは文献 [13] における推奨値を参考に，(gcon , gdiv , gdup , gdel , ginv ) = (0.3, 0.3, 0.6, 0.3, 0.3) を使用する．また，点突然変異率を 1/L とする．各遺伝子座における値のリスト長は 6 とする．選択法としてトーナメント選択 (トーナメントサイズ: 6) を用い，エリート戦略を適用する．個体数を 50，世代数を 1000 とし．適応度関数は次のように設定する．

0.40.20.0MaxAverage0200400600
Generation

8001000

Fig. 6: Maximum and average fitness at each generation- 131 -Number of corrections

100Table 1: Success rate(%) for each method

χ2 testt test80

Initial orientation
Update method
Simulation only

60400

200

400600Generation

8001000

Fig. 7: Number of data corrections at each generation
0.8

model update
simulation onlyFitness

0.6
0.4
0.2
0.0

Average10075

ル環境のギャップを埋める方法を提案した．提案した手法
で最終世代まで進化させて得られた最良個体を実環境のロボットで評価したところ，タスクを達成する振舞いを確認したことから，提案したシミュレーションモデルの構築方法の有効性を確認した．また，シミュレーション上のモデ
ル環境と実環境の整合性を保証するために t 検定を用いたデータ補正によるモデル環境の更新方法を提案した．実験結果より，実環境でロボットを評価した場合，あらかじめ用意したシミュレーションモデルのみで進化させるより，本稿で提案した手法の方が，タスク達成率が高いことを確認した．これより，本稿で提案した入力モデルの構成と出力モデルの構成 · 更新方法の有効性を示すことができた．
今後は移動ロボットに関する他の問題 [15] や，本稿とは異なる確率モデルをもつロボットの制御問題 [16] において，本稿で提案した手法の有効性を検証していきたい．

参考文献
24

6[1] R. Pfeifer and C. Scheier: Understanding Intelligence, MIT Press, 1999.

8 10 12 14 16 18 20TrialFig. 8: Fitness at each trial on the best evolved robot
with and without update

考察

提案手法の有効性を検証するため，シミュレーションのみで進化させた個体との比較実験を行う．まず，オフライン進化として，4 節で述べた初期世代のシミュレーション用の移動量データを用い，モデル更新を行わず，シミュレーションのみで 1000 世代まで進化させる．得られた最終世代の最良個体と，提案手法で得られた最終世代の最良個体を実環境の移動ロボットに制御器として搭載し，評価を行う．両個体ともに，ロボットの初期姿勢を右向き 1 回，上向き 1 回を 1 試行とし，合計 40 試行行う．各試行に対する適応度を Fig. 8 に示す．提案手法を用いた場合は，全試行で安定して良い適応度を示したのに対し，シミュレーションのみの場合は，試行によって安定して良い適応度は得られなかった．
次にタスク達成率 (ゴール到達率) を Table1 に示す．モ
デル更新で得られた最良個体はシミュレーションのみで進化させた最良個体よりも，タスク達成率が良い結果が得られた．さらに，モデル更新で得られた最良個体は，右向き・上向きともに 100%のタスク達成率という結果になった．以上の結果より，提案手法の有効性が確認された．

7Upward100602006Rightward
10095

おわりに

本稿では，移動ロボットのゴール到達問題をタスクとし，実環境のデータを用いてシミュレーションモデルを構成・更新することで，実環境とシミュレーションにおけるモデ- 132 -[2] S. Nolfi and D. Floreano: Evolutionary Robotics:
The Biology, Intelligence, and Technology of SelfOrganizing Machines, MIT Press, 2000.
[3] R. A. Watson, S. G. Ficici and J. B. Pollack: Embodied Evolution: Embodying an Evolutionary Algorithm in a Population of Robots, In Proceedingsof Congress on Evolutionary Computation, pp. 335342, 1999.
[4] N. Jakobi: Half-baked Ad-hoc and Noisy: Minimal
Simulation for Evolutionary Robotics, In Proceedings of the Fourth European Conference on ArtificialLife, pp. 348-357, 1997.
[5] 片田, 高田: 簡易コーディングを用いた進化型ニューラルコントローラの性能評価, 第 34 回知能システム・シンポジウム資料, pp. 149-154, 2007.
[6] R. A. Brooks: Artificial Life and Real Robots, In
Proceedings of the First European Conference onArtificial Life, pp. 3-10, 1992.
[7] O. Miglino, H. H. Lund and D. Nolfi: Evolving Mobile Robots in Simulated and Real Environments,
Artificial Life 2, pp. 417-434, 1995.
[8] D. Keymeulen, M. Iwata, K. Konaka, R. Suzuki, Y.
Kuniyoshi and T. Higuchi, Off-line Mode-free andOn-line Model-based Evolution for Tracking Navigation Using Evolvable Hardware, In Proceedingsof the First European Workshop on Evolutionary
Robotics, Springer-Verlag, Paris, 1998.
[9] 高崎, 片田, 大倉, 田浦: 進化型自律移動ロボットのオ
ンラインモデル更新に関する一手法, 第 47 回自動制
御連合講演会, CD-ROM 予稿集, 404, 2004.

12

1

2

3

4

3

4

5

6

5

6

7

878

9

10

910Fig. 9: Behavior of the best evolved robot in the realenvironment from the initial rightward orientation

Fig. 10: Maximum and average fitness at each generation from the initial upward orientation[10] 森, 家田, 松井: 全方位移動機構と全方位視覚を有する小型ロボットによるサッカー競技の実現 -チームOMNI の戦略-, 人工知能学会 第 6 回 SIG-Challenge
研究会論文集, Vol. 1, pp. 42-47, 2000.

[15] 片田，西村: 進化型マルチエージェントによる協調荷押し行動獲得に関する一考察; 第 52 回システム制御
情報学会研究発表講演会論文集, pp. 469-470 2008.

[11] 小森谷, 大山, 谷: 移動ロボットのためのランドマー
ク観測計画, 日本ロボット学会誌, Vol. 11, No. 4, pp.
533-540, 1993.

[16] S. Thrun, W. Burgard and D. Fox: ProbabilisticRobotics, MIT Press, 2005.

[12] 大倉，上田: 中立突然変異型 GA による騙し問題の最適化, 計測自動制御学会論文集, Vol. 32, No. 10, pp.
1461-1469, 1996.
[13] 片田，大倉，上田: Neutral Networks を含む適応度
景観における遺伝的アルゴリズムの進化ダイナミク
ス, システム制御情報学会論文誌, Vol. 17, No. 5, pp.
187-195, 2004.
[14] 片田，大倉: ニュートラルネットワークを含む適応度
景観における遺伝的アルゴリズムの進化ダイナミク
ス –進化ロボティクスでの検証; システム制御情報学会論文誌, Vol. 21，No. 2，pp. 31-39 2008.

- 133 -