進化型確率的有限状態機械を用いたスワームロボットの集合行動生成○片田 喜章（摂南大学）

Aggregation of Swarm Robots Using Evolutionary
Probabilistic Finite State Machine○ Yoshiaki KATADA (Setsunan University)
Abstract : This paper proposes to use evolutionary computations to design probabilistic finite state machine for thecontroller on an aggregation problem of swarm robotics. This problem formulated as an optimization problem was solved by
the PSOs. Several computer simulations were conducted to investigate the validity of the proposed method. The results
obtained in this paper show to us that the proposed method is useful for the aggregation problem and the best optimized
controllers are interpretable and scalable. This would be transferable to real swarm robots problems.

1.

緒言

計者は群れの振舞いを直接的に設計できないことから，この設計過程は相当な労力を要する．

スワームロボティクス (SR) とよばれる分野 [1][2] が近自動設計法には集団的振舞いを得る際の設計者の労力を年，注目を集めている．その中でもŞahin ら [3] は単一ロ減らしてくれる可能性がある．ここでは，進化ロボティクボットでは問題解決が困難もしくは非効率なタスクに対しスアプローチ (ER) とマルチロボット強化学習の 2 つが多て，構造が簡単で安価に構築でき制御器を含めて完全に均く用いられる．ER では人工神経回路網 (ANN) を制御器質な自律ロボット（シミュレーションではなく実機）を多とし進化計算を用いて設計する場合が多い．しかし，ANN数（最低でも 10-20 台）用いて解決策を提示しようというはシミュレーションで得られた結果を実機に実装する際に，アプローチを提案している．上述の設計理念に従うと，各その非線形性から所望の振舞いが得られないことが多い．

ロボットの構成は制御器を含めて均質であることが望ましさらに，実機での再調整も難しい．

い．均質でありながら，個々のロボットが多様な，時とし本研究では，確率的有限状態機械 (PFSM) を制御器とて役割分担的な振舞いを示すことが要求される．このようして採用する．各状態をモジュールとして実装し，確率的に設計された SR は頑健性・拡張性・柔軟性という特性をに状態を遷移させる．この状態遷移確率を設計変数とし進示すことが期待される [1]．

化計算を用いて集団的振舞いを設計する，進化型確率的有SR では，これまでに空間的な組織化行動・探索行動・集団的意思決定といったタスクが取り扱われてきた [1]．空間限状態機械 (EPFSM) アプローチを提案する．得られる的な組織化行動とは，集合・パターン形成および構造物のPFSM は状態遷移図として表すことができるため，視認性に優れ，人がその意味を理解可能である．また，実機実装自己組立や形成を指す．空間において，どのようにロボッが容易であることが期待できる．

トと物体を組織化し分散させるか (配置するか)，どのよう空間的組織化行動の中で最も基礎的な要素となるものはに凝集したロボットが構造物を形成するかについて焦点を集合である．集合行動では一般的に，ある制約条件のもと当てた研究が行われている．群れに関する大域的な情報のでロボット群を配置し，空間内でロボット群をお互いに最取得と相互通信が可能でかつ精度が求められる場合には，接近させる．集合行動に分散的な制御手法を適用する場合中央集権的な制御手法が適用される．精度は保証されるが，には，ロボットの制御器は行動規範型設計または ER に頑健性・拡張性・コストの面で問題がある．一方，群れに関よって設計されている．多くの研究 [6] がなされているが，する局所的な情報取得と近隣程度のロボット同士の通信が群れに関する局所的な情報を取得するセンサの測定範囲に可能である場合，分散的な制御手法が適用される．精度はよって，1 つのクラスタへの集合が困難になるといった問期待できないものの，頑健性・拡張性・構築の容易さといっ題が報告されている [7]．

た利点がある [4]．本研究では後者に焦点を当てている．

本稿では EPFSM をスワームロボットの集合行動生成に分散的な制御手法における設計手法には行動規範型設計適用し，その性能を検証する．第 2 節では進化計算として[5] と自動設計がある．行動規範型設計ではサブサンプションアーキテクチャ，確率的有限状態機械，ポテンシャル適用する粒子群最適化 (PSO) について述べる．第 3 節でフィールドなどが制御器に用いられており，その設計は手る．第 4 節では計算機実験において PSO を用いて PFSM動で行われている．つまり，群れとしての望ましい振舞いを設計し，集合行動の生成を行い，提案手法の性能を検証が得られるまで，個ロボットの行動の改良を繰り返す．設する．

は PFSM および最適化問題としての定式化について述べ第 18 回システムインテグレーション部門講演会（SI2017）（2017 年 12 月 20 日 〜 22 日・仙台）– 2890 –c 2017 SICE
SY0011/17/0000 – 2890 ⃝2.

Particle Swarm Optimization

されない解は複数個存在し，解は一意には定まらない．全てのパレート最適解が変数空間で形成する集合をパレート

Particle Swarm Optimization (PSO)[8] は魚群や鳥の群れの社会行動に着想を得た確率的多点探索アルゴリズム

最適集合，パレート最適集合の目的関数空間に対する写像をパレートフロントという．語句の定義は [9] に従う．

であり，その探索性能とアルゴリズムの簡便さからさまざまな分野で適用されている．

PSO の更新 ((2) 式) には pbesti および gbest を設定する必要がある．(3) 式で更新された粒子 xi が pbesti を優越する場合に pbesti を更新する．探索過程で発見された複2.1数のパレート最適解候補はアーカイブとよばれるメモリに単一目的 PSO保存される．gbest はアーカイブ内の 1 つの粒子が選択さ

PSO を適用する単一目的最適化問題は以下のように定式化される．
minxf (x),ここで，x = (x1 , x2 , · · · , xL )T(1)れるのが自然な設定である．この選択はガイド選択とよばれ，いくつか方法が提案されている [10]．本稿では，アーカイブ内からランダムに選択する方法 [9] を適用する．
アーカイブは以下の方法で更新する．第 k 世代にアーカ∈ R は L 次元実数値ベL

イブに保存されているパレート最適解候補集合を S(k) とクトルである．

PSO では探索空間における解を「粒子」とよぶ．粒子群する．また，S(k) に第 (k + 1) 世代において更新された全におけるすべての粒子はそれぞれ位置と速度をもつ．粒子粒子を加えた集合を S ′ (k + 1) とする．S ′ (k + 1) 内の粒の位置と速度は次式によって更新される．

子の優越関係を評価し，他の粒子に優越されない粒子を選択することでパレート最適解候補集合 S(k + 1) を更新し，

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 は k 世代
k目における i 番目の粒子の j 番目の位置成分，vij
はi番目の粒子の j 番目の速度成分を表す．pbestij は i 番目の粒3.

確率的有限状態機械

3.1

確率的有限状態機械の定義

子がそれまでの探索で発見した最良点の j 番目の位置成分

SR の研究領域において，確率的状態遷移を伴う有限状であり，gbestj は全粒子がそれまでの探索で発見した最良態機械であると考えられる制御器を採用している文献が見点の j 番目の位置成分である．各粒子は最適化すべき目的られる．Brambilla[1] はこの種の制御器を確率的有限状態関数 f (·) によって評価される．(2) 式の更新式は “inertia

機械 (probabilistic finite state machines: PFSMs) としweight model” とよばれる最も基礎的なものの 1 つであり，て分類している．

本稿でも採用する．

SR で採用される PFSM では，個ロボットに対し複数の状態を設定する: S = {S1 , S2 , · · · , Sm }．ここで，S は状態の集合を表し，m は状態数を表す．この状態は，いわ2.2

多目的 PSOゆる，モジュール [5], プリミティブ，基本行動 [6] とよばれるものと等しい．状態はある確率で次の状態に遷移する

多目的最適化問題は以下のように定式化される．

minf1 (x), f2 (x), · · · , fn (x)(4)(図 1)．この確率は状態遷移確率行列として表すことができ，以下のように定義される．

多目的最適化問題では目的関数が複数あるため，単一の目P的関数では解の優劣を評価できない．そこで一般的に支配= {pij ∈ ℜ | 0 ≤ pij ≤ 1,かつ,(5)ft (x1 ) < ft (x2 ), ∃t ∈ {1, 2, · · · , n}pij = 1,(6)j=1

関係に基づいて解の優劣を決定する．最小化問題において，ft (x1 ) ≤ ft (x2 ), ∀t ∈ {1, 2, · · · , n}m∑i, j ∈ {1, 2, · · · , m}},
ここで，P ∈ ℜm×m は行列を表し，要素 pij は状態 i から状態 j への遷移確率を表す．

が成り立つとき，「x1 が x2 を優越する」，もしくは，「x2が x1 に優越される」，という．他のいかなる解にも優越されない解をパレート最適解という．一般に，お互いに優越– 2891 –

p33

4.

p22
p32

S3

1. で述べたように，本稿ではスワームロボットの集合を扱う．集合問題ではスワームロボットは初期位置から可能S2p23な限り互いに近づいて集合することを目的とする．集合行

p13

動はさまざまな応用につながる基礎的要素と考えられてお

S1

p31

制御タスクと目的関数

p21

り，集合問題はケーススタディとして多く採用されている

p12[6][7]．
本稿では，文献 [7] に従って，集合行動の評価にクラス
タ指標 (cluster metric) と分散指標 (dispersion metric) な

p11

る，2 つの性能指標を採用する．
クラスタ指標は以下のように定式化される．

Fig. 1: State transition diagram of the PFSM

number of robots in the largest cluster at time tN(14)
ここで，分母の N はロボットの台数を表す．また，分子c=

PFSM の設計

3.2

PFSM を設計対象とする最適化問題は (6) 式より以下のように定義できる．の最大クラスタは連結サブグラフの最大値をとるものを差し，2 台のロボットはその中心間の距離が 4r 以下のときに連結しているとみなす．ここで，r はロボットの半径を表

minf (pij ),(7)0 ≤ pij ≤ 1, i, j = 1, 2, · · · , m (8)m∑
pij = 1, i = 1, 2, · · · , m(9)subject toす．本研究では最小化問題を扱うため，1 つめの目的関数を以下のように与える．

f1 =j=1|P | = m×m であることから，設計変数の数は L = m×mとなる．
2. で述べた PSO の探索過程において，初期の粒子群 x0(15)分散指標は以下のように定式化され，これを 2 つめの目的関数として与える．

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

f2 =の各設計変数は [0, 1] の範囲に一様に分布させる．x0 およ(16)h=1k

び (2)(3) 式によって更新される k 世代における x は制約条件 ((8)(9) 式) を満たさない可能性がある．評価の際に

1c(t)

ここで，ph は時間ステップ t における h 番目のロボット

xk を非実行可能解としないために，これらの制約条件を考慮しなければならない．

心位置を表す．この f2 に関しては各 N に幾何学的な最小本研究ではこれらの制約条件を以下の制約条件に置き換値が報告されている [11]．分散を示す指標であるが，統計える．のタスク環境における位置を表す．p(t) は全ロボットの中学における「分散」とは定義が若干異なることに注意され

0 ≤ pij ,(10)pij ≤ 1 ∩m∑

たい．
本研究では，t を各試行における最大時間ステップとす

pij = 1,i, j = 1, 2, · · · , m(11)る．つまり，各試行の終了時に各目的関数を評価する．

j=1(10) 式を pij が満たすために，pij に以下のような処理

5.

計算機実験

(12)

5.1

計算機実験設定

p′ij は次回更新のための設計変数として保存する．つぎに，(11) 式を満たすように，p′ij を以下のように正規化する．

5.1.1

スワームロボットおよび環境の設定を施す．

{
p′ij =−pij :pij :if pij < 0otherwize.

p′ij

p′′ij = ∑m′j=1 pij.

(13)

スワームロボットに関する計算機実験の設定は文献 [12]を参考にして以下のように行う．左右二輪独立駆動型の移動ロボットを動力学シミュレータ ODE を用いてモデル

p′′ij は目的関数値の評価にのみ用いて，設計変数としては保存しない．

化する (図 2)．直径 0.17 m，高さ 0.075 m の台車に，他ロボットに搭載されている光源の強さを測定する光セン– 2892 –5.1.2制御器

図 5 に本実験で採用する制御器を示す．本制御器は文献[6] を参考にしている．制御器は PFSM の各状態における出力 (楕円・白抜きで表示)，ランダムウォークモジュール，回避モジュール，接近モジュール，停止モジュール (長方形・白抜き) で構成される．
本研究で採用する PFSM(図 6) は以下の 3 つの状態をもつ: {Approach, Wait, Repel}．m = 3 のため，|P | = 9となる．以下に詳細を述べる．
・ W ait: ロボットは即時に停止する．

Fig. 2: Setup for swarm mobile robots

・ Approach: (i) 光センサが他ロボットの光源を検出した場合，その強度の合計が最も大きい方向に接近する．(ii) 距離センサによって障害物を検出した場
合，回避モジュールを活性化する．(iii) 他ロボットも障害物も検出できない場合，ランダムウォークモ
ジュールを活性化する．
・ Repel: (i) 他ロボットもしくは障害物を検出した場
合，回避モジュールを活性化する．(ii) 他ロボットも障害物も検出できない場合，ランダムウォークモ

Fig. 3: Distance sensor configurations: (left) sensors forother robots, (right) sensors for obstacles

ジュールを活性化する．
ランダムウォークモジュールでは，移動フェーズと回サ (ロボットの周囲に 4 個 (図 3 の左)，環境の壁または他ロボットまでの距離を測定する距離センサ (前方に 4 個転フェーズを交互に選択する [12]．移動フェーズでは，ロボットは左右モータを回転させ前進する (図 5 における直(図 3 の右)) を搭載する. 距離センサの計測可能距離は 0.3m，光センサの計測可能距離は R ∈ {1.0, 1.5, 2.0, · · · , 5.0}進モジュール)．移動フェーズの実行時間は 6 秒に設定し[m] とする．駆動装置としてモータ 2 個を用いる．スワー
ムロボットの台数を 10 とする．の角度と回転方向（時計回り，反時計回り）をランダムに1 辺が 10 m の壁に囲まれた正方形を実験環境とする (図4)．スワームロボットの初期位置を図 4 のようにとり，各ロボットを 1m 間隔に配置する．各試行の初期姿勢はランた．回転フェーズでは，{45, 90, 135}[ °] のうちいずれか選択し，あらかじめ測定しておいた，おおよそ，その角度に回転するであろう実行時間でその場で回転する (図 5 における左右回転モジュール)．

ダムに設定する．各試行は 30, 000 ステップ (300 秒に相Wait当) 実行する．実験の試行は 10 回行う．

stopforward㻵turn rightapproach layer

turn left

motorsapproachrobot
distance
sensorApproachstop layer

obstacle
distance
sensorRepel

turn rightFig. 4: Set up for computer simulation: Initially, swarm
robots are always placed at the center.

– 2893 –avoidance㻵avoidance layer

turn left

forwardrandomwalk㻵turn right

exploration layer

turn left

Fig. 5: Subsumption architecture[5] with the PFSM

p33

p22

2.0

p32
Repel1.8Waitp23

1.6
f1

p13

1.4p21
p31

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.0Approach

1.2p12

1.050

p11

100

150200Iterations(a) f1 : 1/MaxClusterRatio

500

Fig. 6: State transition diagram of the PFSM for aggregation

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

400
300

PSO の設定

f2

5.1.3

200

3.2 で述べたように，PFSM の状態遷移確率を設計変数とし，PSO を適用する．設計変数の数は L = 9 となる．

100

全粒子数を 20 とし，計算機実験を実行する．PSO のパラ0メータ ((2) 式) は c1 = 2.0, c2 = 2.0, w = 0.5 とする．全50

世代数を kmax = 200 とする．アーカイブの上限値を 20 と100
Iterations

150200(b) f2 : Dispersion

する．各条件に対し，PSO を 10 回実行する．

Fig. 7: Objective function values for each iteration

5.2

計算機実験結果

5.2.1

目的関数値

ではなく，ある割合で Approach から Repel に遷移している．これにより，クラスタを形成した後にも少し離れたり

図 7(a), 7(b) に世代数に対する f1 と f2 の変化 (10 試行の平均) をそれぞれ示す．光センサの計測可能距離 R の値によって大きく傾向が分かれる．R ≥ 2.5 の場合，初期世代から f1 が 1 を示す1 ．これはクラスタ数が 1，つまり，集合行動を達成していることを表している．分散を表す f2

移動することでより密に集合することが可能になると考えられる．一方，R = 2.5 の場合には Approach に遷移する
確率も高いが，Repel→Wait の確率が高く，群れへの接近を維持しながら，より動く・離れるという振舞いが備わっていると考えられる．

も早い世代から小さい値をとり，徐々に最適値に近づいている．R = 2.0 の場合にも最終世代付近でクラスタ数は 1を示す．一方，R ≤ 1.5 の場合には，f2 は減少するもの5.2.3の，f1 はそれほど減少せず，クラスタ数が 1 になることはなかった．

拡張性に関する検証

上記の R = 2.5 および 5.0 の場合に最も良い性能を示した PFSM に関して，ロボット台数を変更した場合の f2 の値 (10 回平均) を表 1 に示す．theory は文献 [11] で得られ5.2.2ている各 N に対する f2 の幾何学的最小値を示している．

獲得された PFSM の状態遷移図なお，(R, N ) = (2.5, 40) を除く各 (R, N ) の組合せでクラ上述の実験で獲得した制御器の特徴をみる．図 8 にスタ数は 1 となることを確認している．N = 10, 20 のとき

R = 2.5 および 5.0 の場合に最も良い性能を示した PFSMの状態遷移図を示す．R = 5.0 の場合には Approach に遷には最適値に非常に近い値を示した．また，N = 30 のと移する確率が高い．ただ，Approach だけに遷移するわけした．N = 40 のときに，R = 5.0 の場合ではクラスタ数

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

きにも，f2 は最適値よりも大きい値となるが，近い値を示は 1 になり，f2 も近い値を示している．一方，R = 2.5 の場合ではクラスタ数は 1 にはならず，f2 も大きい値となっ– 2894 –0.059

0.642
0.450

Repel

Wait

0.105
0.277

0.253
Approach
0.033

0.491

(a) (R, N ) = (2.5, 30)

0.690

Fig. 9: Final positions of the swarm robots with thebest optimized PFSM(a) R = 2.5

0.014

0.872

までは集合行動が可能であり，拡張性が高いことを確認した．今後は実機実験を通して性能を検証したい．

0.137
Repel

Wait

0.022

参考文献

0.240
0.106
Approach
0.060

0.848

0.700
(b) R = 5.0

Fig. 8: State transition diagram of the best optimizedPFSM

た．図 9 に R = 2.5，N = 30, 40 のときのロボットの最終位置を示す．

6.

(b) (R, N ) = (2.5, 40)

結言

本稿では，進化型確率的有限状態機械をスワームロボッ
トの集合行動生成に適用し，その性能を検証した．センサの計測可能距離が閾値以上である場合に，群れの数が 1 となる集合行動の生成が可能であることを確認した．また，設計時に設定した台数以上のロボットでもある程度の台数

Table. 1: Performance of the best controllers on f2
N
1020

3040

theory

13.50

54.65

123.5

220.33

R = 2.5
R = 5.0

13.93
14.06

59.99
59.09

140.80136.025060.16
269.626[1] Brambilla, M., Ferrante, E., Birattari, M., Dorigo,
M., “Swarm Robotics: A Review from theSwarm Engineering Perspective,” Swarm Intelligence, Vol.7, No.1, pp.1–41, 2013.
[2] Trianni, V., Evolutionary Swarm Robotics,Springer-Verlag 2008.
[3] Şahin, E., “Swarm Robotics: From Sources ofInspiration to Domains of Application,” Lecture
Notes in Computer Science, Vol.3342, pp.10–20,
2005.
[4] Bahçeci, E., Soysal, O., Şahin, E., “A Review:
Pattern Formation and Adaptation in Multi-Robot
Systems”, Technical Report CMU-RI-TR-03-43,
CarnegieMellon University, 2003.
[5] Brooks, R., “A Robust Layered Control System fora Mobile Robot”, IEEE Journal of Robotics andAutomation, Vol.2, No.1, pp.14–23, 1986.
[6] Soysal, O., Bahçeci, E., Şahin, E., “Aggregationin Swarm Robotic Systems: Evolution and Probabilistic Control”, Turkish Journal of Electrical Engineering and Computer Sciences, Vol.15, No.2,pp.199–225, 2007.
[7] 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, pp. 1145–1161, 2014.
[8] Kennedy. J., Eberhart, R.C.,“Particle Swarm Optimization”, In Proceedings of IEEE International
Conference on Neural Networks, pp. 1942–1948,
1995.
[9] 増田和明, 栗原謙三, “多目的 Particle Swarm Optimization に基づく制約条件付き大域的最適化手法”,
電気学会論文誌Ｃ, Vol. 131, No. 5, pp. 990–999,2011.
[10] 内種岳詞, 畠中利治, “単一の目的関数に基づくガイド選択による多目的 PSO”, 進化計算学会論文誌, Vol. 3,No. 3, pp.155–162, 2012.
[11] Graham, R.L., Sloane, N.J.A., “Penny-Packing andTwo-Dimensional Codes”, Discrete ComputationalGeometry 5: p.1―11, 1990.
[12] Katada, Y., Nishiguchi, A., Moriwaki, K., Watakabe, R., “Swarm Robotic Network Using Levy
Flight in Target Detection Problem”, Artificial Lifeand Robotics, Volume 21, Issue 3, pp. 295–301,
2016.

– 2895 –