GS01-15
スワームロボットの集合行動生成における多目的 PSO の性能比較○片田喜章 （摂南大学）
概要 個々のロボットの状態を確率的に遷移させることでスワームロボットの集団的振舞いを創発させる確率的有限状態機械 PFSM を用いたアプローチがある．本研究では PFSM の設計を最適化問題として定式化し，多目的PSO を適用した．そして，複数の多目的 PSO に対し性能検証を行った．
キーワード: スワームロボティクス，多目的 PSO，集合，集団的振舞い

1

はじめに
1)2)3)

スワームロボティクス (SR) とよばれる分野が近年，注目を集めている．その中でもŞahin ら 4) は単一ロボットでは問題解決が困難もしくは非効率なタスクに対して，構造が簡単で安価に構築でき制御器を含めて完全に均質な自律ロボット（シミュレーションではなく実機）を多数（最低でも 10-20 台）用いて解決策を提示しようというアプローチを提案している．上述の設計理念に従うと，各ロボットの構成は制御器を含めて均質であることが望ましい．均質でありながら，個々のロボットが多様な，時として役割分担的な振舞いを示すことが要求される．このように設計された SRは頑健性・拡張性・柔軟性という特性を示すことが期待される 1) ．
SR の分散的な制御手法 5) における設計手法には行動規範型設計 6) と自動設計がある．行動規範型設計ではサブサンプションアーキテクチャ，確率的有限状態機械，ポテンシャルフィールドなどが制御器に用いられており，その設計は手動で行われている．つまり，群れとしての望ましい振舞いが得られるまで，個ロボットの行動の改良を繰り返す．設計者は群れの振舞いを直接的に設計できないことから，この設計過程は相当な労力を要する．
自動設計法には集団的振舞いを得る際の設計者の労力を減らしてくれる可能性がある．ここでは，進化ロボティクスアプローチ (ER) とマルチロボット強化学
習の 2 つが多く用いられる．ER では人工神経回路網(ANN) を制御器とし進化計算を用いて設計する場合が多い．しかし，ANN はシミュレーションで得られた結果を実機に実装する際に，その非線形性から所望の振舞いが得られないことが多い．さらに，実機での再調整も難しい．
そこで，確率的有限状態機械 (PFSM) を制御器として採用する．各状態をモジュールとして実装し，確率的に状態を遷移させる．この状態遷移確率を設計変数とし進化計算を用いて集団的振舞いを設計する，進化型確率的有限状態機械 (EPFSM) アプローチが提案されている．ここで得られる PFSM は状態遷移図として表すことができるため，視認性に優れ，人がその意味を理解可能である．また，実機実装が容易であることが期待される．
本稿では EPFSM アプローチによる SR の集合行動生成 7)8) において，進化計算として適用する多目的粒子群最適化 (PSO) の性能を検証する．第 2 節では進化計算として適用する粒子群最適化 (PSO) について述べ

システム･情報部門学術講演会2017(2017年11月25日-27日･浜松)- 57 -る．第 3 節では PFSM および最適化問題としての定式化について述べる．第 4 節では EPFSM アプローチによる集合行動生成に関する計算機実験において，多目的 PSO の探索性能を検証する．

2Particle Swarm Optimization

Particle Swarm Optimization (PSO)9) は魚群や鳥の群れの社会行動に着想を得た確率的多点探索アルゴリズムであり，その探索性能とアルゴリズムの簡便さからさまざまな分野で適用されている．
2.1

単一目的 PSO

PSO を適用する単一目的最適化問題は以下のように定式化される．
minxf (x),(1)ここで，x = (x1 , x2 , · · · , xL )T ∈ RL は L 次元実数値ベクトルである．
PSO では探索空間における解を「粒子」とよぶ．粒子群におけるすべての粒子はそれぞれ位置と速度をもつ．粒子の位置と速度は次式によって更新される．
k+1
kvij= w · vij
+ c1 · rand() · (pbestij − xkij )+c2 · rand() · (gbestj − xkij ),k+1
xk+1= xkij + vij
,ij

(2)
(3)

ここで，rand() は区間 [0, 1] の一様分布に従う乱数を表し，w，c1 ，c2 は各項の重みパラメータである．xkij はkk 世代目における i 番目の粒子の j 番目の位置成分，vij
は i 番目の粒子の j 番目の速度成分を表す．pbestij は
i 番目の粒子がそれまでの探索で発見した最良点の j 番目の位置成分であり，gbestj は全粒子がそれまでの探索で発見した最良点の j 番目の位置成分である．各粒子は最適化すべき目的関数 f (·) によって評価される．(2)式の更新式は “inertia weight model: iwm” とよばれる最も基礎的なものの 1 つであり，本稿でも採用する．
つぎに，“linearly decreasing inertia weight method:
ldiwm” とよばれる更新式も採用する．ldiwm では wは一定ではなく，世代が増えるにしたがって変化する．

w(k) = wmax −wmax − wmin
× k,kmax(4)

ここで，wmax ・wmin は w の上下限値であり，, kmaxは全世代数とする．

SY0008/17/0000-0057 © 2017 SICE

ここで，P ∈ ℜm×m は行列を表し，要素 pij は状態 iから状態 j への遷移確率を表す．

2.2 多目的 PSO
多目的最適化問題は以下のように定式化される．
minf1 (x), f2 (x), · · · , fn (x)

(5)

p33

多目的最適化問題では目的関数が複数あるため，単一の目的関数では解の優劣を評価できない．そこで一般的に支配関係に基づいて解の優劣を決定する．最小化問題において，ft (x1 ) ≤ ft (x2 ), ∀t ∈ {1, 2, · · · , n}かつ,p22p32

S3p13(6)p21

ft (x1 ) < ft (x2 ), ∃t ∈ {1, 2, · · · , n}が成り立つとき，「x1 が x2 を優越する」，もしくは，「x 2が x1 に優越される」，という．他のいかなる解にも優越されない解をパレート最適解という．一般に，お互いに優越されない解は複数個存在し，解は一意には定まらない．全てのパレート最適解が変数空間で形成する集合をパレート最適集合，パレート最適集合の目的関数空間に対する写像をパレートフロントという．語句の定義は 13) に従う．
PSO の更新 ((2) 式) には pbesti および gbest を設定する必要がある．(3) 式で更新された粒子 xi が pbestiを優越する場合に pbesti を更新する．探索過程で発見された複数のパレート最適解候補はアーカイブとよばれるメモリに保存される．gbest はアーカイブ内の 1 つの粒子が選択されるのが自然な設定である．この選択はガイド選択とよばれ，いくつか方法が提案されている 10, 11, 12) ．本稿では以下に述べる 2 種類を適用する．

S1

p31

p12

p11
Fig. 1: State transition diagram of the PFSM

3.2

PFSM の設計

PFSM を設計対象とする最適化問題を (7) 式より以下のように定義する．
minf (pij ),(8)0 ≤ pij ≤ 1, i, j = 1, 2, · · · , m(9)m∑
pij = 1, i = 1, 2, · · · , m (10)subject toj=113)

grand :

アーカイブ内からランダムに選択する

gref :

参照点までの距離が最小の粒子を選択する

アーカイブは以下の方法で更新する．第 k 世代にアーカイブに保存されているパレート最適解候補集合を S(k)とする．また，S(k) に第 (k + 1) 世代において更新された全粒子を加えた集合を S ′ (k + 1) とする．S ′ (k + 1) 内の粒子の優越関係を評価し，他の粒子に優越されない粒子を選択することでパレート最適解候補集合 S(k +1)を更新し，アーカイブに保存する．なお，アーカイブに保存されているパレート最適解候補集合の数が上限値を超える場合にはその粒子数を削除する必要がある．

3

S2

p23

|P | = m × m であることから，設計変数の数は L =m × m となる．
2 で述べた PSO の探索過程において，初期の粒子群x0 の各設計変数は [0, 1] の範囲に一様に分布させる．
x0 および (2)(3) 式によって更新される k 世代におけるxk は制約条件 ((9)(10) 式) を満たさない可能性がある．
評価の際に xk を非実行可能解としないために，これらの制約条件を考慮しなければならない．
本研究ではこれらの制約条件を以下の制約条件に置き換える．
0 ≤ pij ,確率的有限状態機械

3.1 確率的有限状態機械の定義
SR の研究領域において，確率的状態遷移を伴う有限状態機械であると考えられる制御器を採用している
文献が見られる．Brambilla1) はこの種の制御器を確率的有限状態機械 (probabilistic finite state machines:PFSMs) として分類している．
SR で採用される PFSM では，個ロボットに対し複数の状態を設定する: S = {S1 , S2 , · · · , Sm }．ここで，S は状態の集合を表し，m は状態数を表す．この状態は，いわゆる，モジュール 6) , プリミティブ 14) ，基本
行動 7) とよばれるものと等しい．状態はある確率で次の状態に遷移する (Fig. 1)．この確率は状態遷移確率行列として表すことができ，以下のように定義される．
m∑P = {pij ∈ ℜ | 0 ≤ pij ≤ 1,
pij = 1,(7)j=1

i, j ∈ {1, 2, · · · , m}},- 58 -(11)pij ≤ 1 ∩m∑

pij = 1,i, j = 1, 2, · · · , m(12)j=1(11) 式を pij が満たすために，pij に以下のような処理を施す．
p′ij ={−pij :
pij :if pij < 0otherwize.

(13)

p′ij は次回更新のための設計変数として保存する．つぎに，(12) 式を満たすように，p′ij を以下のように正規化する．
p′ij
(14)
p′′ij = ∑m ′ .
j=1 pij
p′′ij は目的関数値の評価にのみ用いて，設計変数としては保存しない．

4

制御タスクと目的関数

1 節で述べたように，本稿ではスワームロボットの集合を扱う．集合問題ではスワームロボットは初期位置から可能な限り互いに近づいて集合することを目的とする．集合行動はさまざまな応用につながる基礎的要素と考えられており，集合問題はケーススタディとして多く採用されている 7)8) ．
本稿では，文献 8) に従って，集合行動の評価にクラスタ指標 (cluster metric) と分散指標 (dispersion metric)なる，2 つの性能指標を採用する．
クラスタ指標は以下のように定式化される．
number of robots in the largest cluster at time tN(15)
ここで，分母の N はロボットの台数を表す．また，分子の最大クラスタは連結サブグラフの最大値をとるものを差し，2 台のロボットはその中心間の距離が 4r 以下のときに連結しているとみなす．ここで，r はロボットの半径を表す．本研究では最小化問題を扱うため，1つめの目的関数を以下のように与える．

Fig. 2: Setup for swarm mobile robots

c=f1 =1c(16)分散指標は以下のように定式化され，これを 2 つめの目的関数として与える．

1 ∑ (t)||ph − p(t) ||2 ,4r2N

f2 =(17)h=1(t)

ここで，ph は時間ステップ t における h 番目のロボットのタスク環境における位置を表す．p(t) は全ロボットの中心位置を表す．この f2 に関しては各 N に幾何学的な最小値が報告されている 15) ．分散を示す指標であるが，統計学における「分散」とは定義が若干異なることに注意されたい．
本研究では，t を各試行における最大時間ステップとする．つまり，各試行の終了時に各目的関数を評価する．
一般的に多目的最適化問題では，各目的関数はトレードオフの関係にある．上述の f1 , f2 はトレードオフの関係にはない．次節で述べるように f1 , f2 を多目的最適化問題における目的関数として利用する理由を次のように考える．まず，SR の集合行動としてクラスタ数の最小化 (f1 = 1) を目指し，最適化計算の過程において f2 だけでなく f1 にも選択圧を加えたいからである．
また，得られた解を実機に実装することを考えると，ただ 1 つの解ではなく，パレート最適解候補集合を獲得できるという利点がある．

5

Fig. 3: Distance sensor configurations: (left) sensors
for other robots, (right) sensors for obstacles
定する光センサ (ロボットの周囲に 4 個 (Fig. 3 の左)，環境の壁または他ロボットまでの距離を測定する距離
センサ (前方に 4 個 (Fig. 3 の右)) を搭載する. 距離センサの計測可能距離は 0.3 m，センサの測定範囲が集合行動に大きな影響を与えるという報告 8) から，光センサの計測可能距離を R ∈ {1.0, 1.5, 2.0, · · · , 5.0} [m]と変更して計算機実験を行う．駆動装置としてモータ2 個を用いる．スワームロボットの台数を 10 とする．
1 辺が 10 m の壁に囲まれた正方形を実験環境とする(Fig. 4)．スワームロボットの初期位置を Fig. 4 のようにとり，各ロボットを 1m 間隔に配置する．各試行の初期姿勢はランダムに設定する．各試行は 30, 000 ステップ (300 秒に相当) 実行する．実験の試行は 10 回行う．

5.1.2

制御器

本実験で採用する PFSM(Fig. 5) は文献 7) を参考にし，以下の 3 つの状態をもつ: {Approach, Wait, Repel}．m = 3 のため，|P | = 9 となる．以下に 3 つの状態について述べる．

計算機実験

5.1 計算機実験設定
5.1.1 スワームロボットおよび環境の設定
スワームロボットに関する計算機実験の設定は文献16)を参考にして以下のように行う．左右二輪独立駆動型の移動ロボットを動力学シミュレータ ODE を用いてモデル化する (Fig. 2)．直径 0.17 m，高さ 0.075 m の台車に，他ロボットに搭載されている光源の強さを測- 59 -Fig. 4: Set up for computer simulation: Initially,swarm robots are always placed at the center.

Distance to the reference point

p33

p22
p32

Repel

Wait

p23
p13
p21

p31

Approach

p12

510rand, iwmrand, ldiwm
ref, iwm
ref, ldiwm

410310210

110010-1

10-21012345

R

p11

Fig. 6: Distance to the reference point for each PSO
Fig. 5: State transition diagram of the PFSM for aggregation• W ait: ロボットは即時に停止する．
• Approach: (i) 光センサが他ロボットの光源を検出した場合，その強度の合計が最も大きい方向に接近する．(ii) 距離センサによって障害物を検出した場合，回避モジュールを活性化する．(iii) 他
ロボットも障害物も検出できない場合，ランダムウォークモジュールを活性化する．
• Repel: (i) 他ロボットもしくは障害物を検出した
場合，回避モジュールを活性化する．(ii) 他ロボッ
トも障害物も検出できない場合，ランダムウォークモジュールを活性化する．
制御器およびモジュールの詳細は文献 17) を参照されたい．

5.1.3 PSO の設定
3.2 で述べたように，PFSM の状態遷移確率を設計変数とし，PSO を適用する．設計変数の数は L = 9となる．全粒子数を 20 とし，計算機実験を実行する．
PSO のパラメータ ((2) 式) は以下を採用する; iwm:
c1 = 2.0, c2 = 2.0, w = 0.5 ((2) 式)，ldiwm: c1 =2.0, c2 = 2.0, wmin = 0.4, wmax = 0.9 ((4) 式)．全世
代数を kmax = 200 とする．カイド選択法として 2.2 で述べた grand もしくは gref を適用する．gref では，参照点 (f 1 , f 2 ) = (1, 13.5) との目的関数空間でのユークリッド距離で粒子を評価する．ここで，f 1 は最小クラスタ数であり，f 2 は 15) で求められている幾何学的最小値である．アーカイブの上限値を 20 とする．各条件に対し，PSO を 10 回実行する．
5.2 計算機実験結果
PSO の 各 設 定 の 組 合 せ ({grand , gref },{iwm, ldiwm}) に 関 し て ，横 軸 に 光 セ ン サ の 計 測可能距離 R，縦軸に最終世代におけるアーカイブに保存されている粒子と参照点との距離の平均を示したグ
ラフ (10 試行の平均) を Fig. 6 に示す．各設定で比較すると iwm を用いた場合が良い性能を示す．R ≥ 2.5においてすべての設定で小さな値をとっている．ここで f1 ，f2 の各値を調べると，f1 = f 1 を示し，f2 もf 2 に非常に近い値をとる．クラスタ数 1 は集合行動を達成していることを表している．また，R ≥ 2.5 では- 60 -grand と gref の結果に差が見られない．これは，探索の過程で f1 = f 1 の粒子が見つかると，その粒子のみがアーカイブに保存されるようになるためであると考えられる．一方，R ≤ 2.0 では R が小さくなるにしたがい，参照点との距離は大きくなる．各設定で比較す
ると，(grand , iwm) の組合せが良い性能を示す．
つぎに，各世代で参照点に対する距離が最も小さくなった粒子に関して，f1 と f2 の世代数に対する変化(10 試行の平均) を Fig. 7 にそれぞれ示す．Fig. 6 と同様に光センサの計測可能距離 R の値によって大きく傾向が分かれる．R ≥ 2.5 の場合，初期世代から f1 が 1を示す1 ．分散を表す f2 も早い世代から小さい値をとり，徐々に最適値に近づいている．R = 2.0 の場合では (grand , iwm) のみが最終世代付近でクラスタ数 1 を示す．一方，R ≤ 1.5 の場合には，f2 は減少するものの，f1 はそれほど減少せず，クラスタ数が 1 になることはなかった．

6おわりに

本稿では，EPFSM アプローチによるスワームロボッ
トの集合行動生成において，多目的 PSO を適用し，その探索性能を検証した．多目的 PSO の探索性能はセンサの計測可能距離に大きく影響を受けることがわかった．センサの計測可能距離が集合行動に与える影響は文献 8) でも報告されている．また，粒子の更新式は iwmが良い探索性能を示した．
特定のセンサ条件の下，スワームロボットの集団的振舞いの基礎的要素である集合行動を生成できることを確認した．今後，目的関数の数を増やし，集合行動に新たな特性を付与していきたい．

1 Fig. 7 では，R ≥ 2.5 の場合のグラフは重なっているため，R = 5.0 のみが表示されて見える．

2.0500

R=1.0
R=1.5
R=2.0
R=2.5
R=3.0
R=3.5
R=4.0
R=4.5
R=5.0

f1

1.6
1.4400
300
f21.8

R=1.0
R=1.5
R=2.0
R=2.5
R=3.0
R=3.5
R=4.0
R=4.5
R=5.0200

1.21001.005010015020050

Iterations

500

1.4

R=1.0
R=1.5
R=2.0
R=2.5
R=3.0
R=3.5
R=4.0
R=4.5
R=5.0400
300
f2

f1

1.6200(b) f2 for (grand , iwm)

R=1.0
R=1.5
R=2.0
R=2.5
R=3.0
R=3.5
R=4.0
R=4.5
R=5.0

1.8150Iterations(a) f1 for (grand , iwm)

2.0

100

200

1.21001.0050100
Iterations

150

200

50(c) f1 for (grand , ldiwm)

2.05001.4200

R=1.0
R=1.5
R=2.0
R=2.5
R=3.0
R=3.5
R=4.0
R=4.5
R=5.0400
300
f2f1

1.6150(d) f2 for (grand , ldiwm)

R=1.0
R=1.5
R=2.0
R=2.5
R=3.0
R=3.5
R=4.0
R=4.5
R=5.0

1.8100Iterations

200

1.21001.0050100
Iterations

15020050(e) f1 for (gref , iwm)

2.05001.4200

R=1.0
R=1.5
R=2.0
R=2.5
R=3.0
R=3.5
R=4.0
R=4.5
R=5.0400
300
f2f1

1.6150(f) f2 for (gref , iwm)

R=1.0
R=1.5
R=2.0
R=2.5
R=3.0
R=3.5
R=4.0
R=4.5
R=5.0

1.8100Iterations

200

1.21001.0050100
Iterations

15020050(g) f1 for (gref , ldiwm)

100Iterations(h) f2 for (gref , ldiwm)

Fig. 7: Objective function values for each generation- 61 -150200参考文献
1) Brambilla, M., Ferrante, E., Birattari, M., Dorigo,
M.: “Swarm Robotics: A Review from the Swarm
Engineering Perspective,” Swarm Intelligence, Vol.7,
No.1, 1/41 (2013)
2) Trianni, V.: Evolutionary Swarm Robotics, SpringerVerlag (2008)
3) “スワーム：群れの創発的挙動生成”，計測と制御, Vol.52.
No.3, 179/276 (2013)4) Şahin, E.: “Swarm Robotics: From Sources of Inspiration to Domains of Application,” Lecture Notes in
Computer Science, Vol.3342, 10/20 (2005)
5) Bahçeci, E., Soysal, O.:Şahin, E., “A Review: Pattern Formation and Adaptation in MultiRobot Systems”, Technical Report CMU-RI-TR-0343, CarnegieMellon University (2003)
6) Brooks, R.: “A Robust Layered Control System fora Mobile Robot”, IEEE Journal of Robotics and Automation, Vol.2, No.1, 14/23 (1986)
7) Soysal, O., Bahçeci, E., Şahin, E.: “Aggregation inSwarm Robotic Systems: Evolution and ProbabilisticControl”, Turkish Journal of Electrical Engineeringand Computer Sciences, Vol.15, No.2, 199/225 (2007)8) Gauci, M., Chen. J., Li, W., Dodd, T. J., Groß,R.: “Self-Organised Aggregation without Computation”, The International Journal of Robotics Research, Vol. 33, No. 9, 1145/1161 (2014)
9) Kennedy. J., Eberhart, R.C.: “Particle Swarm Optimization”, In Proceedings of IEEE International Conference on Neural Networks, 1942/1948 (1995)
10) Coello, C. A.C., Pulido, G. T., Lechuga, M. S.: “Handling Multiple Objectives with Particle Swarm Optimization”, IEEE Transactions on Evolutionary Computation, Vol. 8, No. 3, 256/279 (2004)
11) Reyes-sierra, M., Coello, C. A.C.: “Multi-Objectiveparticle swarm optimizers: A survey of the state-ofthe-art”, International Journal of Computational Intelligence Research, Vol. 2, No. 3, 287/308 (2006)12) 内種, 畠中: “単一の目的関数に基づくガイド選択による多目的 PSO”, 進化計算学会論文誌, Vol. 3, No. 3,155/162 (2012)13) 増田, 栗原: “多目的 Particle Swarm Optimization に基づく制約条件付き大域的最適化手法”, 電気学会論文誌
Ｃ, Vol. 131, No. 5, 990/999 (2011)14) Pfeifer, R., Scheier, C.: Understanding Intelligence,
MIT Press (1999)
15) Graham, R.L., Sloane, N.J.A.: “Penny-Packing andTwo-Dimensional Codes”, Discrete ComputationalGeometry 5: 1/11 (1990)16) Katada, Y., Nishiguchi, A., Moriwaki, K., Watakabe, R.: “Swarm Robotic Network Using Levy Flightin Target Detection Problem”, Artificial Life andRobotics, Volume 21, Issue 3, 295/301 (2016)17) 片田: “進化型確率的有限状態機械を用いたスワームロ
ボットの集合行動生成”, 第 18 回計測自動制御学会シス
テムインテグレーション部門講演会, 発表予定 (2017)- 62 -