2B1-3

進化型移動ロボットのゴール
進化型移動ロボットのゴール到達問題
ロボットのゴール到達問題における到達問題における逐次近似最適化手法の逐次近似最適化手法の検証(サンプル点サンプル点の追加戦略による追加戦略による解探索性能による解探索性能への解探索性能への影響への影響)影響)○大島直人

片田喜章（摂南大学）

Application of the sequential approximate optimization method to an evolutionary robotics problem -Investigation of the effect of sampling method on the performance of the best evolved robot*Naoto Ohshima, Yoshiaki Katada (Setsunan University)

Abstract－Due to the parallel population search of evolutionary robotics, it takes a long time toAbstract
evaluate all robot in a real environment. Thus, such techniques as to shorten the time are required.
One of them would be the sequential approximate optimization (SAO) method in which the fitness
function is estimated by an approximate model during an evolutionary optimization process andsamples are taken sequentially after every optimization process. This study investigates theperformance of sampling methods of the SAO by varying the number of samples on a robot control
problem using simulated robots.
.
Sequential Approximate Optimization, Genetic Algorithm, RBF Networks
Key Words：
Words

1 はじめにも実環境で適切に振舞えるとは限らない．つまり，高い解探索能力が期待できる人工進化を用いて自シミュレーションで用いることのできる制御問題は，律ロボットの制御器を構築する進化ロボティクスがその環境およびロボットとの相互作用が適切にモデある1)．進化ロボティクスでは制御器を構築する際，ル化できる問題に限られる．これに対し，我々はこ制御器の評価方法として実環境で評価する方法とシれまでに遺伝的アルゴリズム(Genetic Algorithm:ミュレーションを用いて評価する方法がある．これ

GA) の遺伝長が短くなるように制御器となるニュらの方法にはそれぞれ問題点が指摘されている．実ーラルネットワーク(Artificial Neural Networks:環境で評価する場合では，ロボットを評価するためANN)をコーディングすることで短い進化時間で自に実時間がかかる．人工進化に要する進化時間は数

律移動ロボットの制御器を構築する手法を提案して百世代から数千世代が一般的であり，膨大な実験時きた2)．そして，計算機実験および実機実験によっ間が必要となる．一方，シミュレーションによっててその有効性を確認してきた．

評価する場合では，シミュレーションで獲得した制

一方，自律移動ロボットの制御器を GA と ANN御器を実ロボットに搭載した場合，シミュレーショを用いて構築する際に，実環境またはシミュレーシンと実環境とのギャップによってロボットが必ずしョンで評価したロボットの制御器となる ANN の設

1システム・情報部門学術講演会 2012（2012 年 11 月 21 日～ 23 日・名古屋）

263

SY0014/12/0000-0263 © 2012 SICE

計変数，およびその評価値から RBF ネットワーク

数の半径 は文献 5)で提案されている以下の(3)式をを用いて作成する近似評価関数を用いて GA により用いて計算する．
" ,#$%

ANN の最適化を行う．これにより，ロボットの評√' √(価回数を削減する手法を提案している 3)．北山らは

13

ここで，" ,#$% は 番目のサンプル点からの最大距離

この手法を統合的最適化システム 4)と呼んでおり，を表している．'は入力ベクトルの次元数であり，一般的には逐次近似最適化手法5)と呼ばれている．

は基底関数の数と同一とする 4)．

しかしながら，進化ロボティクスにおいて逐次近似最適化手法が用いられた事例は少なく，この文献 3)

逐次近似最適化手法による自律移動による自律移動ロボ
自律移動ロボ
3 逐次近似最適化手法によるで用いられている手法がより一般的な進化ロボティ
クスにおける制御問題に対してどのような性能を示

ットの制御器ットの制御器の制御器の構築すのかは知られていない．特に，文献 3)では北山ら

ここでは，ロボットの制御器である ANN の設計にによって提案されている逐次近似最適化手法のサン関して本研究で適用する逐次近似最適化手法を用いプル点追加戦略4)は考慮されていない．

た方法について述べる．

3.1 逐次近似最適化手法

以上より，本稿では進化ロボティクスにおけるロボット制御問題の一つであるゴール到達問題に対し

文献 4)をもとに，RBF ネットワークにより評価関

逐次近似最適化手法を適用し，サンプル点追加戦略数空間を近似する応答曲面を作成する．作成した応答が解の探索性能に与える影響を計算機実験により検曲面を用いてロボットの制御器であるANN の結合荷証する．

重値の最適化を行う．その手順を以下に示す．

以下，第 2 節では応答曲面を作成するために用い(1) ANN の結合荷重値を設計変数として初期サンプル点を*+,+ 個生成する．

る RBF ネットワークについて述べる．第 3 節では(2) 計算機実験により初期サンプル点であるANN を逐次近似最適化手法によるロボットの制御器の構築について述べる．第 4 節では計算機を用いた検証実搭載したロボットの評価値を求める．

験を行う．第 5 節では本稿のまとめを述べる．

(3) RBF ネットワークを用いてサンプル点とその評価値から評価関数空間を近似する応答曲面を作

2 RBF ネットワーク成する．

RBF ネットワークは 3 層の階層型ネットワークである4)．入力変数ベクトル
するネットワークの出力,,,(4) 最適化手法により作成した応答曲面に対して最に対適化を行う．

は(1)式で計算される． (5) サンプル点追加戦略に従い，サンプル点を*個追1
ここで， は隠れ層の素子数，の基底関数の出力，加する．
(6) 計算機実験により，手順(4)で追加したサンプルは隠れ層の 番目点であるANN を搭載したロボットの評価値を求は隠れ層の基底関数と出力層める．
(7) 追加サンプル点数が最大サンプル点数*#$% になの素子間の結合荷重である．また，隠れ層の基底関数 は，(2)式で表されるガウス関数である．
expるまで，手順(3)から手順(6)を繰り返す．

3.2 最適化手法

23.1 の手順(4)における最適化手法には ANN の設計

ここで， は 番目の基底関数の中心， は 番目の基に対しその有効性が確認されている拡張型遺伝的ア底関数の半径である．また，本研究における基底関ルゴリズムである Operon GA6) (以下，OGA) を用い

2264

る．Operon GA はバイナリコーディングを用いたはバイナリコーディングをGA*/2個サンプル点を追加するする．但し，手法(b)は設計であり，バイナリストリングを実数値実数値に変換すること変数空間で近傍を定義しているのにしているのに対し，手法(c)でで ANN の設計に用いる．

は OGA の遺伝子空間で近傍近傍を定義する．ここでは最ここで，3.1
3.1 で述べた評価関数空間評価関数空間を近似する応答

適解1の遺伝子型に対し，ハミングハミング距離を 1 とする遺曲面を近似適応度関数と呼び，以下ににその最適化の手伝子を近傍とサンプル点が疎疎な領域にそれぞれ*/2順を示す．

個ランダムに生成する．

(1) 初期個体群を-+,+ 個とする．このこの初期個体群は3.1 における初期サンプル点と同一同一とする．

4 計算機実験
計算機実験(2) 近似適応度関数を用いて各個体各個体の近似適応度を4.1 実験設定
4.1.1 制御器の制御器の設定計算する．
(3) 近似適応度に基づき OGA の遺伝的操作遺伝的操作を実行

移動ロボットはセンサを 7 個搭載し，移動機構は左し，次世代の個体群を-個生成生成する．

右二輪独立駆動型と仮定する
する．この移動ロボットの制(4) 規定世代数. /0 まで(2)，(3)を繰繰り返す．

御器である ANN は入力層ニューロンニューロン数-K を 7，隠れ層ニューロン数-> を 1，出力層出力層ニューロン数-M を 2

3.3 サンプル点
サンプル点の追加戦略

サンプル点追加手法としてつぎのの三つが考えられと設定する．隠れ層と出力層のニューロンはのニューロンは完全相互結合とする．また，ANN の結合荷重値
結合荷重値の上限値を +:る．

1とし，下限値を +;(a) 追加サンプル点をランダムに追加追加する．

4.1.2 ゴール到達問題
ゴール到達問題(b) 応答曲面の最適解近傍とサンプルサンプル点の疎な領域

1ととする．

計算機実験に使用するゴール
ゴール到達問題7) を Fig.1 ににサンプル点を追加する．
(c) 手法(b)において設計変数空をOGOGAの遺伝子空間示す．移動ロボットはより早くゴールにくゴールに到達することで近傍を定義し，サンプル点をを追加する．

を目的とする．移動ロボットのの初期位置を Fig.1 の環手法(a)は基底関数空間に一様乱数一様乱数でランダムにサ境における左下，ゴールの位置位置を右上とする．試行はンプル点を追加することで最適化手法
最適化手法によって大域ロボットがゴールに到達するかするか，あるいは到達せずに的最適解を得ることを期待しているる．

200 ステップ経過したときにしたときに終了する． ロボットの手法(b)は文献4)に従い，3.2
3.2 より最適化
最適化された応答

初期姿勢を0°から 45°ずつ変えた
えた試行を 3 回行う．以

曲面最適解 1の近傍を作成し，その近傍近傍に 3.1 で述べ下の(5)式を用いて個体の適応度適応度を計算する．
A<8'BCCたサンプル点を*/2個ランダムに追加追加する．また，サンプル点の疎な領域に対してもサンプルサンプル点を*/2個ランダムに追加する．ここで，近傍近傍の大きさ3+ は次式

1-7 D <E3C

FG HI+/JKL

N1O8BPL
Q 5*E O8BPにより決定する(文献4))．
341567'8 9 1:+;+ ,

<1
1,2,'

4(4)式中の +: は設計変数の上限値， +; は下限値をとし，'は設計変数の次元数を表す．また，，567'8 はパラメータであり，1 以上の整数である．
Fig.1 Experimental setup for a simulated environment

手法(c)は手法(b)のサンプル点の追加方法
追加方法と比較す

ここで，-7 D <E3Cは試行回数試行回数(3)であり，*E O8BPはるためのものである．追加手法(c)とと同様に手法(b)の200 となる．

最適解1の近傍とサンプル点が疎なな領域にそれぞれ

3265

4.1.3 OGA と逐次近似最適化手
逐次近似最適化手法の設定
本研究における OGA は-+,+べた手法(a)(b)(c)に対して乱数の種を変えた試行を50とし，. /0500

50 回試行する．とする．また，3.1
3.1 で述べた逐次近似最適化手法の設定として，*+,+は**ここで，解探索性能を比較するために，本タスクで50とする．追加するサンプル点数*

ゴールに到達できる制御器を持つロボットを単に解S10, 30, 50Tと変化させて実験を行う．と呼ぶ．また，ANN の結合荷重値の上下限値の設定

10, 50 の 場 合 で は 最 大 サ ン プ ル 点 数 *#$%

300， *30の場合では*#$%に従い，x4V290として，3.
3.2
3.2 で述1, x4W

1 ((4)式)とする．

Fig.2 Sampling method (a)Fig.5 Sampling method (b)Fig.8 Sampling method (c)(add 10 points each samples)(add 10 points each samples)(add 10 points each samples)

Fig.3 Sampling method (a)Fig.6 Sampling method (b)Fig.9 Sampling method (c)(add 30 points each samples)(add 30 points each samples)(add 30 points each samples)

Fig.4 Sampling method(a)Fig.7 Sampling method (b)Fig.10 Sampling method(c)(add 50 points each samples)(add 50 points each samples)(add 50 points each samples)

4266

Table.1 Number of successful trials toな更新回数が増す．そのため．応答曲面の最適解の精

reach the goal for each method

度が逐次的に向上することで高い適応度を持つ解が多く得られるものと考える．つぎに手法(c)では手法(b)の応答曲面の最適解近傍とサンプル点が疎な領域にサンプル点を追加する場合，3.
3.3
3.3 で述べた遺伝子空間で最適化解の遺伝子が変化することでサンプル点を生成するため，設計変数空間では大幅にサンプル点の配置が変化すると考えられる．このため，遺伝子空間でサンプル点を追加することは設計変数空間でサ4.2 実験結果ンプル点をランダムに追加することに等しくなり，近Fig.2-10 に各実験の各試行に対して OGA の最終世適応度の高い解を得ることが困難になると考える．

代において制御器が獲得した真の最大適応度を示す．

また，Fig2-10 より手法(a),(b)および(c)によって獲まず，手法(a)に対して各*の様子を比較する．Fig.2-4

得される真の最大適応度は 0.25 程度であり，構築しよりのサンプル点数が*た制御器のほとんどが低い適応度を示している．これ30の場合(Fig.3)に*10,50の実験より高い適応度を持つ解が少数ではあるが多は，設計変数空間において22 の(2)式で表される各基底く得られていることが確認できる．つぎに手法(b)に関数間の距離が遠く配置されているため，応答曲面の対して各*の様子を比較する(Fig.5-7)． *形状が平坦になると推測される．そのため，応答曲面10の場30,50のより高い適応度を持つ解がを用いて最適化される解が低い適応度を示すと考え多く得られていることが確認できる．つぎに手法(c)られる．また，RBF ネットワークを用いて応答曲面に対して各*の様子を比較する(Fig.8-10)．手法(b)とを作成する場合，最大サンプル点数が少ないことによ合(Fig.5)に*同様に*10の場合(Fig.8)に*30,50のより高いり近似した応答曲面の最適解の精度が向上せず，解の適応度を持つ解が多く得られていることが確認でき探索性能が低くなると考える．

る．

5 まとめ

つぎに Table.1 に手法(a),(b)および手法(c)における各実験に対する解のうち，4.1.
4.1.2
4.1.2 で述べたゴールに到

本研究では，RBF ネットワークによる逐次近似最適達する回数が 2 回以上の解の数を表す．まず，手法(a)化手法を用いて自律移動ロボットの制御器を設計し，と手法(b)の方が試行数に対してゴールに 2 回以上到サンプル点追加戦略が解探索性能にどのような影響達する解を多く獲得していることが確認できる．また， を与えるのかを計算機実験により検証した．その結果，手法(c)が手法(b)よりも試行回数に対してゴールに 2 応答曲面の最適解近傍とサンプル点が疎な領域にサ回以上到達する解の獲得数が減少していることが確

ンプル点を追加する場合に適応度の高い制御器を得認できる．

られることを確認した．これは，文献4)におけるサン以上より，手法(a)よりも手法(b)を用いる場合に適プル点追加戦略を用いた結果の傾向と同一である．ま

応度の高い解を得られることが確認できる．また，手た，追加するサンプル点数を少なく設定することで応法(b)において追加するサンプル点数を少なく設定す

答曲面の更新回数が増し，高い適応度を持つ制御器がることで高い適応度を持つ解が多く得られることが多く得られることを確認した．

確認できる(Fig.7)．これは，最大サンプル点数に上限

今後，今回の実験に用いたゴール到達問題の評価関があり追加サンプル点数を少なく設定すると逐次的数を再度検討し，検証実験を行っていきたい．また，

5267

追加サンプル点数をさらに増やす場合や最大サンプ
ル点数の上限を増やす場合でも同様に実験を行っていきたい．

参考文献

1 S. Nolfi and D. Floreano: Evolutionary Robotics:
The Bioligy, Intelligence, and Technology of
Self-Organizing Machines, MIT Press (2000)

2) 片田, 日高：簡易コーディングを用いた進化型人工神経回路網の移動ロボット制御問題における性能検証，システム制御情報学会論文誌, Vol.0, No.0,pp.149-154(2007)
3) 原，元木，山崎，安田：RBF ネットワークと遺伝アルゴリズムによる自律移動ロボットコントロー
ラ構築，電気学会論文誌 C(電子・情報・システム部門誌)，Vol.131，No.5，pp.1000‐1008(2011)4) 北山，安田，山崎：RBF ネットワークと Particle
Swarm Optimization による統合的最適化，電気学会論文誌 C ，Vol.128，No.4, pp. 636-645 (2008)
5) 北山，酒井，荒川，山崎：RBF ネットワークによる逐次近似最適化(離散変数への適用)，日本機械学会論文集(C 編)，78 巻，787 号 pp.177-190(2012)6) 片田，大倉：ニューラルネットワークを含む適応度景観における遺伝的アルゴリズムの進化ダイナ
ミクス‐進化ロボティクスでの検証，システム制
御情報学会論文誌，Vol.21，No.2，pp.31‐39(2008)

6268