進化型多目的移動ロボットの目的関数空間における非劣解分布
Distribution of Non-dominated Solutions in the Objective Function
Space for an Evolutionary Multi-objective Mobile Robot○片田 喜章Yoshiaki KATADA
摂南大学
Setsunan University
katada@ele.setsunan.ac.jp
Abstract: Evolutionary multiobjective optimization (EMO) algorithms have attracted much researchinterest in recent years. In evolutionary robotics (ER), several papers have been published where EMO
algorithms have been applied to design multiobjective behavior of autonomous robots. However, performance of EMO algorithms on design of neural networks for robot control tasks has not been investigatedenough. In this work, a multiobjective genetic algorithm was applied to the design of a neural controller
for multiobjective behavior of a mobile robot in a looping maze problem, which is a popular test problem
for ER. Distribution of non-dominated solutions in the objective function space are obtained from anumber of trials in the problem in order to investigate which a decision maker prefers from them.

1

はじめに

近年，進化計算分野では進化計算がもつ多点探索の利点を活かし進化型多目的最適化 (EMO) が盛んに研究されている [1][2]．EMO の研究の方向性としては大別して，上述の多点探索の利点を活かして非劣解集合 (パレートフロント) 全体を一様に覆うように解を獲得するアプローチと，意思決定者の選好を考慮して非劣解集合の解を獲得するアプローチとがある．
一方，自律ロボットの行動獲得に進化計算を適用する研究分野は進化ロボティクス (ER)[3] とよばれるが，その多くは単一目的の進化を採用している．ER に EMO アルゴリズムを適用した事例も報告されているが [4][5][6]，ERにおけるロボットの標準的な制御器である人工神経回路網(ANN) の設計に EMO アルゴリズムを適用した場合のパフォーマンスについて，方法論的な立場 [4][5] から十分に議論されていないように思われる．
本稿では，ER の研究で多く用いられる移動ロボットの迷路内周回問題における制御器 (ANN) の設計に EMO の代表的なアルゴリズムの 1 つである NSGA-II[7] を適用し，複数回の試行から得られる非劣解集合の分布を調べる．その中で本問題における選好解がどのように分布するかを調べ，本問題あるいは ER において上述 EMO のアプローチのいずれを採用すべきかを検討する．

2Fig. 1: Experimental setup for a looping maze problem
θt+1

本稿では自律移動ロボットによる迷路内周回問題を扱う(図 1)．この環境は参考文献 [3] の環境をより簡略化したものになっている．ロボットに搭載する距離センサは図に示す距離まで測定が可能であり，物体までの距離と反比例する値を出力するように設定する．ロボットの移動機構を左右二輪独立駆動型と仮定し，その中心位置 (x, y) と姿勢
θ(図 2) は次式のように更新する．

xt+1

=

yt+1

=

VR + VLcos θt2
VR + VLsin θt
yt +2
xt +

θt +

VR − VL2R

ここで，VR と VL は両車輪の周速度，2R は車輪間隔とする．モータ出力は制御器として採用する人工神経回路網(ANN; 4 節で述べる) の出力値 z によって次のように与えられる: VR,L = Vmax × z. ここで，Vmax は車輪の最大周速度とする．

3タスク=適応度関数

Floreano ら [3] は自律移動ロボットによる迷路内周回問題を扱い，次の適応度関数を設定している．
1f=M axStepMaxStepV (1 −√ΔV )(1 − smax )

(1)

t=1

ここで，M axStep は 1 試行の最大ステップ数，V = (|VL |+|VR |)/2Vmax ，ΔV = |VL − VR |/Vmax ，smax = max{sj :j = 1, · · · , Ns } (sj : j 番目のセンサーの値，√ Ns :センサー数) とする．V はロボットの運動性，1 − ΔV はロボッ
トの直進性，1 − smax は障害物からの回避性をそれぞれ表

第20回インテリジェント・システム・シンポジウム（2010年9月25日〜26日・東京）

SY0009/10/0000-0139 © 2010 SICE

VL
VR2R0Fig. 2: Simulated model for a mobile robot

Fig. 3: Relative angle between the initial and current positions of a mobile robot

す項となっている．文献 [3] では (1) 式を使って図 1 よりも少し複雑な環境でロボットが障害物の周囲を回る行動をGA によって獲得している．しかし追実験をしてみると環境の大きさやセンサー配置など環境設定の違いから必ずしも (1) 式を使って障害物の周囲を回るような望ましい行動が獲得できないことがわかる．そこで，本稿では (1) 式の各項を目的関数にとり，多目的最適化問題として定式化する．各項の物理的な意味（運動性・直進性・回避性）および項数から，以下のように 2 目的最大化問題および 3 目的最大化問題として定式化する．

3.1

2 目的最大化問題参考文献 [8] で定式化したように，直進運動性と障害物回避性を目的関数にとり，2 目的最大化問題とする．

Maximize fi
f1 =f2 =3.2

1M axStep
1M axStep(i = 1, 2)
MaxStep(2)

V (1 −√ΔV )(3)

t=1MaxStep(1 − smax )

(4)

t=1

3 目的最大化問題

運動性・直進性・回避性をそれぞれ目的関数にとり，3 目的最大化問題とする．

Maximize fi
f1 =1
M axStep

1
f2 =M axStep
f3 =1
M axStep

4

計算機実験

4.1

実験設定

(i = 1, 2, 3)
MaxStep


(5)

V(6)

t=1MaxStep


√ΔV )

(7)

(1 − smax )(8)(1 −t=1MaxStep
t=1

ロボットの初期位置を図 1 の位置とする．試行は 200 ステップ経過したときに終了する．ロボットの初期姿勢 θ0 を−45◦ から 45◦ ずつ変えた試行を 3 回行い，(3)(4) 式および (6)-(8) 式を用いて平均を計算し，目的関数の値とする．
ロボットの制御器として，我々の研究グループで提案している短いビットストリングでコーディングされる ANN[9] を用いる．ここで各ノードは全結合されている．これらの結合荷重を決定変数とし，{−1, 1} のいずれかの値をとる．入力ノード数は Ns = 7(距離センサ数)，中間ノード数は 1，出力ノード数は 2(モータ数) とする．
進化手法として今日最も広く利用されている EMO アルゴリズムの 1 つであり，Deb ら [7] によって提案されている NSGA-II を用いる．個体数を 100，参考文献 [7] に従い交叉率 0.9(一様交叉)，ビット反転突然変異率 1/L(L は遺伝子長)，終了世代数 500 と設定する．NSGA-II の実行回数を 100 とする．
4.2

選好情報と目的数

本稿では，はじめにで述べたように，複数回の試行 (100 試行) から得られる非劣解集合の分布を調べ，本問題における選好解がその中でどのように分布するかを調べる． 2 節
で述べたタスクおよび (2)(5) 式から直感的にわかるように，本問題における選好解は障害物に接触せず周回行動を示す個体である．定量的には，図 3 に示す初期位置からの相対角度 θ を各時間ステップごとに θmax = θt if θt > θt−1と更新していき，200 ステップ終了時に θmax > 360◦ となるものを選好解と定義する．
選好情報を定量的に表せるのであれば，それ自体を単一目的関数もしくは多目的最適化の目的関数の１つとして採用すればいいのではないかと思われるかもしれない．しかし，(6-8) 式を計算する場合と θ を計算する場合では，使われるセンサの存在がロボットの内側か外側かという観点からその意味するところが大きく異なる．まず，(6-8) 式
では，ロボット自身に装備しているセンサの値だけ (赤外線を用いた距離センサ，ロータリーエンコーダを用いた速度センサなど) を用いて目的関数を計算できる．一方，θ は鳥瞰図的な視点を必要とする．つまり，ロボットに備わっていない，ロボット外部のセンサ (ロボット上方に設置されたカメラなど) を用いて目的関数を計算することを仮定している．進化計算を含めたシステム全体の自律性 (もしくは自動化) を考慮した場合，システムの評価がロボットの内部システムのみで完結することが望ましい (これに類似した考え方が，ロボカップサッカーの中型ロボットリーグと小型ロボットリーグの設定法の差にも見られる [10])．
したがって，本稿では θ を進化システムの評価に用いるのではなく，あくまで選好情報として利用する立場をとる．
また，EMO 独特のダイナミクスとして，目的数の増加とともに (多数目的)，非劣解集合の収束性が悪化することが報告されている [11]．この意味からも目的関数空間を視覚化でき，かつ，これまで EMO で得られている多くの知見が適用できると予想されることから，2 目的 ((2) 式) および 3 目的 ((5) 式) 最大化問題として扱う．

4.3

5

実験結果

2 目的最大化問題として (2) 式を用いて 100 回試行し，500世代で得られた非劣解集合および選好解集合を目的関数空間にプロットした結果を図 4 に示す．ただし，非劣解集合はそれぞれの試行で最上位のフロントにランクされたすべての解を示している．標準的な NSGA-II を用いていることもあり最適パレートフロントである保証はないが，おおむねパレートフロントの形状を獲得していると考えられる．これら非劣解の中で選好解集合は一カ所の領域(0.06 < f1 < 0.19 かつ 0.08 < f2 < 1.8) に分布することがわかる．
同様に，3 目的最大化問題として (5) 式を用いて 100 回試行し，得られた非劣解集合および選好解集合を図 5 に示す．2 目的の場合と同様に非劣解集合はそれぞれの試行で最上位のフロントにランクされたすべての解を示している．3 目的関数空間では非劣解集合はパレート曲面を形成していると思われる (図 5(d))．f1 , f3 に関しては下限はな
く，非劣解は広い範囲に分布している．f2 はロボットの直進性を示すが，f2 の値が大きい範囲 (0.33 < f2 ) および小さい範囲 (f2 < 0.13) では，非劣解は分布していない．
これは，運動性 (f1 ) がある程度抑えられていても，直進性 (f2 ) が大きすぎると壁や障害物を回避できず，また小さすぎるとその場回転もしくは旋回を主とする振舞いとなり壁などを回避できないからであると考えられる． 2 目
的の場合と同様に，これら非劣解の中で選好解集合は一カ所の領域 (0.13 < f1 < 0.27 かつ 0.12 < f2 < 0.21 かつ
0.06 < f3 < 0.18) に分布することがわかる．とくに f2 に関して，非劣解の中でも小さい値が選好解となっていることが興味深い．これは選好解が障害物に接触せず周回行動を示す個体であることから，直線性を表す f2 は大きすぎても小さすぎてもうまく振舞えず，最低限の直進性を維持しながら旋回運動を頻繁にとる必要があるからであると推測する．
2 目的および 3 目的の場合で得られた選好解の振舞いを
図 6, 7 に示す．壁および障害物に接触することなく周回行動を示している．また，図からはわかりにくいが，2 目的で得られた振舞いに比べて，3 目的で得られた振舞いは直線的な行動が多く観察された．これは (5) 式において，運動性 (f1 )・直進性 (f2 ) の各目的関数を設定し，NSGA-IIで採用しているパレートランキングにより各目的関数を最大化する方向に選択圧が加わった結果であると考えられる．
以上の結果から，はじめにで述べた EMO の 2 つのアプ
ローチのうち，本問題に対しては意思決定者の選好を考慮して非劣解集合の解を獲得するアプローチを採用することが有効かつ効率的であると考えられる．

0.3

nondominatedpreferredf2

0.2

おわりに

本稿では，移動ロボットの迷路内周回問題に多目的 GA を適用し，複数回の試行から得られた非劣解集合の分布に関して考察を行った．実問題のため最適パレートフロントに対する収束性は議論できないが，パレートフロントの形状をおおむね把握できたと考えている．また，本問題における選好解は目的関数空間のある限定された領域内に存在することを 2 目的・3 目的の場合について確かめた．
今後は，本稿で得られた知見から，意思決定者の選好情報に基づいて限定された領域内で多様性を有する解集合を導出するアプローチ (例えば [12]) を適用していきたい．

参考文献[1] K. Deb: Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, 2001.
[2] C. A. C. Coello: An Updated Survey of Evolutionary Multiobjective Optimization Techniques: Stateof the Art and Future Trends, In Proceedings of theCongress on Evolutionary Computation, pp. 3–13,
1999.
[3] S. Nolﬁ and D. Floreano: Evolutionary Robotics:
The Biology, Intelligence, and Technology of SelfOrganizing Machines, MIT Press, 2000.
[4] G. Capi: Multiobjective Evolution of Neural Controllers and Task Complexity, IEEE Transactions
on Robotics, Vol. 23, No.6, pp.1225-1234, 2007.
[5] J. Teo and H. A. Abbass: Automatic Generation of Controllers for Embodied Legged Organisms:a Pareto Evolutionary Multi-objective Approach,
Evolutionary Computation, Vol. 12, No. 3, pp. 355394, 2004.
[6] J-H. Kim, Y-H. Kim, S-H. Choi and I-W. Park,
Evolutionary multi-objective Optimization in Robot
Soccer System for Education, IEEE ComputationalIntelligence Magazine, Vol. 4, No. 1, pp. 31–41, 2009.
[7] K. Deb, A. Pratap, S. Agarwal and T. Meyarivan:
A Fast Elitist Multi-Objective Genetic Algorithm:
NSGA-II, IEEE Transactions on Evolutionary Computation, Vol. 6, pp. 182–197, 2000.
[8] 片田: 進化ロボティクスにおける多目的 GA に関する一考察, 第 54 回システム制御情報学会研究発表講演
会論文集, pp.609–610, 2010.
[9] 片田, 日高: 簡易コーディングを用いた進化型人工神
経回路網の移動ロボット制御問題における性能検証,
システム制御情報学会論文誌, Vol. 23，No. 1，pp.
1–8, 2010.
[10] URL: http://www.robocup.org/

0.1

000.1

0.2

0.3

f1

Fig. 4: Distribution of non-dominated solutions andpreferred solutions in the two-objective space by theNSGA-II[11] 塚本, 能島, 石渕: 多数目的最適化問題における進化型多目的最適化アルゴリズムの問題点とその改良手法に関する考察, システム制御情報学会論文誌, Vol.
22，No. 6，pp.220–228, 2009.
[12] K. Deb and J. Sundar: Reference Point Based Multiobjective Optimization Using Evolutionary Algorithms, In Proceedings of the 8th annual conference
on Genetic and evolutionary computation (GECCO2006), pp. 635–642, 2006.

0.3
nondominatedpreferred

f3

0.2

0.1

00

0.1

0.2

0.3

f1

(a) f1 -f3 objective space
0.3
nondominatedpreferred

f3

0.2

0.1

00

0.1

0.2
f2

0.3

0.4

Fig. 6: Behavior of a preferred solution obtainedby the NSGA-II in the two-objective optimization
problem(b) f2 -f3 objective space
0.4

f2

0.3
0.2
0.1
nondominatedpreferred
00

0.1

0.2

0.3

f1

(c) f1 -f2 objective space

nondominatedpreferred
f3
0.3

0.4
0.3
0.2 f20.10.2
0.1
00

0.1

0.2

0.3

0f1(d) the three-objective space

Fig. 5: Distribution of non-dominated solutions andpreferred solutions in the three-objective space by
the NSGA-II

Fig. 7: Behavior of a preferred solution obtainedby the NSGA-II in the three-objective optimization
problem