スワームロボットによるターゲット探索–レヴィフライトに関するシミュレーションを用いた考察○ 片田 喜章（摂南大学）

Target detection problem using swarm robots–Computer simulation for Lévy flight○ Yoshiaki KATADA(Setsunan University)

Abstract: We tackle the task for swarm robotics where robots explore the environment to detect a target.
Once a robot detects a target, robots immediately communicate with a base station via intermediate relay
robots due to wireless communication. In our previous results, we confirmed that Lévy flight outperformed theusual random walk for exploration strategy in real robot experiment. In this study, we investigated the effectof a parameter for Lévy flight on the performance of exploration through a series of computer simulations.

1

はじめにスワームロボティクス (SR) とよばれる分野 [1][2][3] が近年，急速に注目を集めるようになってきている．その中でも Sahin ら [4] は単一ロボットでは問題解決が困難もしくは非効率なタスクに対して，構造が簡単で安価に構築でき制御器を含めて完全に均質な自律ロボット（シミュレーションではなく実機）を多数（最低でも10-20 台）用いて解決策を提示しようというアプローチを提案している．このアプローチでは各ロボットに指示を出す監督的なエージェントの存在を前提としないため，スワームの群れ行動は各ロボットの局所的相互作用から必ず創発的に生成されることになる．上述の設計理念に従うと，各ロボットの構成は制御器を含めて均質であることが望ましい．均質でありながら，個々のロボットが多様な，時として役割分担的な振舞いを示すことが要求される．
SR では，これまでに分散協調的な探索，搬送，囲い込み，形態形成，隊列の形成・維持といったタスクが取り扱われてきた [1]．本研究では，協調探索に分類される，ターゲット探索 [5] をタスクとして取り扱う．ここでは，無線ネットワークによって通信可能な複数ロボットを用いてターゲットの探索を行う．あるロボットがターゲットを発見すると，その情報は無線ネットワー
クを介して基地局に送られる．このとき，ターゲットを検出したロボットから基地局までは無線ネットワークによって「連結 [6]」されている必要がある．
我々の研究グループでは，スワームロボットネットワークにおける無線通信の連結性を保証する通信可能距離とロボット台数の関係について，パーコレーション理論にもとづく計算機実験を行った [7]．さらに，上述の SR により構成される無線ネットワーク (以降，SRネットワークとよぶ) の連結性を考慮したロボットの台数と無線通信装置を使用し，実環境においてターゲッ

ト探索の実機実験を行っている [8]．文献 [8] では，探索アルゴリズムとしてランダムウォークとレビィフラ
イト [9] を実装し，本タスクにおけるタスク達成率を比較した．その結果，移動距離が一定なランダムウォークに対し，移動距離が可変なレビィフライトが圧倒的に優位であることを確認した．そこで，本稿ではレビィフ
ライトの移動距離を決定する確率密度関数のパラメー
タに関して，計算機実験により考察を行う．

2

レビィフライト

本研究でははじめにで述べたようにターゲット探索を扱う．探索実行以前に環境に対する知識が全くない場合を想定する．この場合の一般的な探索行動としてランダムウォークがある．ランダムウォークの中でもブラウン運動として扱われるものが一般的である．一方，ランダムウォークの 1 つで，移動距離がレビィ分布とよばれる確率密度関数にしたがう，レビィフライト (Lévyflight[9]) が知られている．
レビィ分布は以下の式で表される．
Z
1 ∞ −γqαecos(wq)dq, γ > 0, w ∈ R
Lα,γ (w) =π 0(1)ここで，γ は分布の大きさを決めるパラメータであり，
α は分布の形状を決めるパラメータで 0 < α < 2 の値をとる．(1) 式は α = 1 のときにコーシー分布，α → 2のときにガウス分布と等価になる．本確率密度関数はw = 0 に関して対称であり，無限大の 2 次モーメントをもつことが特徴である．本研究では文献 [10, 11] に従い，γ = 1 とする．図 1 に (1) 式によるレビィ分布(γ = 1) を示す．
レビィ分布に従う確率変数を生成するアルゴリズムが提案されている [10]．以下にその生成式を示す [10, 11]．

第16回システムインテグレーション部門講演会(SI2015)（2015年12月14日～16日・名古屋）- 0047 -SY0011/15/0000 - 0047 © 2015 SICE

3

本研究では，文献 [8] の実験で使用した，左右二輪独立駆動型の移動ロボットを動力学シミュレータ ODE を用いてモデル化する (図 2)．設定を以下に示す．直径170mm，高さ 75mm の台車に，距離センサ (前方に 4個)，ターゲット検出センサ (両端に 2 個)，無線通信装置を搭載する. 距離センサの計測可能距離は約 300mm，ターゲット検出センサの計測可能距離は約 200mm とする．駆動装置としてモータ 2 個を用いる．無線通信装置は Zigbee 規格を想定し，アドホックネットワークを構成し，マルチホップ通信が可能であると仮定する．
無線の通信可能距離の設定は 5.2 節で述べる．また，本研究ではターゲットは直径約 75mm の球とする．

Fig. 1: Lévy distributionv=

x
1|y| α|v|,

w = {(k(α) − 1)e− c(α) + 1)}v

(2)

ここで，x と y はガウス分布に従う独立な確率変数であり，k(α) と c(α) は α に依存し，文献 [10] によって
表 1 のように得られている．
第 4.3 節で詳細を述べるが，本研究では (2) 式を用いて移動ロボットの直進移動時間を決定する．したがって，(2) 式の w ≥ 0 の範囲だけを必要とするため，(2)式中の x を |x| として計算する．これにより，(1) 式の値は w > 0 の範囲で理論上 2 倍になる．
移動ロボットにレビィフライトを実装した研究として文献 [12] がある．ここでは，レビィフライトはターゲットが探索領域に対しまばらに，かつ，ランダムに分布している場合に有効であると報告している．文献[12] では，移動距離の決定に使用される確率密度関数
は (1) 式の近似を用いており，確率が高くなる移動距離が短い場合に (1) 式との乖離が大きくなっている可能性 [11] がある．そこで本研究では近似式ではなく，(1)式に基づく (2) 式を用いて移動距離を決定する．

Table 1: Parameters for generating Lévy distribution[10]
α0.80.91.1
1.2
1.3
1.41.51.61.7
1.81.91.95
1.99k
0.795112
0.0899389
1.100631.205191.31836
1.44647
1.599221.79361
2.064482.50147
3.46154.80663
10.498

スワームロボット構成

c
2.483
2.76752.945
2.941
2.90052.83152.737
2.61252.44652.206
1.79151.39250.60894コントローラ

4.1

SR における制御器の設計手法

SR では，1 節で述べた設計仕様を満たす制御器の設計手法としてサブサンプションアーキテクチャ(SSA)[13]に代表される，環境との相互作用に着目した行動規範型設計とよばれる設計，もしくは，強化学習や進化計算による自動設計 [2] が提案されている．現在，強化学習や進化計算を用いる手法はシミュレーション環境では有効であるが実環境でその動作を保証するのは容易ではない．そのため，SR が本来目指すべき実ロボット
志向の研究者の多くは行動型設計を採用している．
SR における行動規範型設計ではロボット間およびロボットと環境の相互作用に着目し, 望ましい群れ行動が獲得されるまでボトムアップ的に個の振舞いを繰り返し調整する．この「個の振舞い」を記述する表現様式として確率有限状態機械がよく用いられている [1]．一方，上述の SSA ではレイヤ (次節で述べる) を構成するモジュールに拡張有限状態機械が用いられている．本稿では計算機実験を用いているが，本来的には実機を志向している [8]．このため上述の流れにしたがい，スワームロボットネットワークを構成する個の振舞いを記述する表現様式として上述の SSA を採用する．

Fig. 2: Differential wheeled robots- 0048 -᝟ሗ㏦ಙ೵Ṇ㊥㞳䝉䞁䝃㞀ᐖ≀ᅇ㑊䝺䜲䝲㞀ᐖ≀᳨ฟྑᅇ㌿㻵ᕥᅇ㌿䝍䞊䝀䝑䝖᥈⣴䝺䜲䝲᥈⣴ᇶᆅᒁ┠ᶆ᳨ฟ㻵┤㐍䝰䞊䝍㉥እ⥺䝉䞁䝃䝍䞊䝀䝑䝖Ⓨぢ᝟ሗ㏦ಙ䝺䜲䝲ྑᅇ㌿
ᕥᅇ㌿

Fig. 3: Layer structure of SSA
4.2

SSA のレイヤ構造

図 3 にスワームロボットに実装する SSA のレイヤ構造[8] を示す．本タスクを実現する SSA は，ターゲット発見情報送信レイヤ・ 障害物回避レイヤ・ターゲット探索レイヤの 3 層から構成されている．図中の I は抑制を表し，上位のレイヤが活性化する場合，下位のレイヤを抑制することを表している [13]．各レイヤはモジュールの結合により構成されている．
各レイヤの動作を説明する．ターゲット探索レイヤの探索モジュールは後述する探索アルゴリズムにより，直進モジュール・右回転モジュール・左回転モジュールのいずれかに実行指令信号を送る．障害物回避レイヤの障害物検出モジュールは 3 節で述べた距離センサからの入力値をもとに，左回転もしくは右回転モジュー
ルに実行指令信号を送り，障害物を回避する. ターゲッ
ト発見情報送信レイヤの目標検出モジュールは 3 節で述べた左右いずれかのターゲット検出センサの出力値がしきい値を上回った場合に停止モジュールと情報送信モジュールに実行指令信号を送る．情報送信モジュールは SR ネットワークを介して基地局へターゲット発見情報を送信する．
4.3

探索アルゴリズムの実装

本研究で想定している左右二輪独立駆動型移動ロボットの仕様では，回転を伴う移動（一般的には旋回と言う）において回転方向をランダムにすることと，移動距離を一定にすることを同時に行うことがその構造上難しい．そこで，回転フェーズと移動フェーズに分けて設定する (図 4)．移動フェーズでは，ロボットは左右モー移動タを回転させ前進する (図 3 における直進モジュール)．
移動フェーズにおける 1 ステップの実行時間は実機における予備実験の結果に基づいて 6 秒に設定した．移動フェーズ毎の移動ステップ数は 2 節で述べたレビィ分布によって決定され，さまざまな値をとる．回転フェー
ズでは，{45, 90, 135}[ °] のうちいずれかの角度と回転方向（時計回り，反時計回り）をランダムに選択し，あらかじめ測定しておいた，おおよそ，その角度に回転するであろう実行時間でその場で回転する (図 3 における左右回転モジュール)．また，移動フェーズと回転フェーズを交互に選択する (図 4).

5ターゲット探索計算機実験

5.1

実験環境

壁に囲まれた正方形を実験環境とする (図 5)．図 5 の左下に無線通信基地局 (以下，基地局) の設置を仮定す
る．本実験は計算機実験のため，実際には基地局との通信を行わないが，SR ネットワークの連結性のチェックに基地局の位置情報が必要となる．また，図の右上(基地局の対角線上) に 3 節で述べたターゲットである球を設置する．スワームロボットの初期位置は基地局近傍とし，図の左下とする．
5.2

実験設定

本スワームロボットのタスクは，所定の時間内にターゲットを見つけ，ネットワークを介して基地局にその発見情報を送信することである．したがって，タスクの達成にはターゲットの発見とネットワークの連結性を同時に満たす必要がある．
探索アルゴリズムとしてレビィフライトを実装したSSA を採用する．2 節で述べたレビィ分布の形状を決めるパラメータ α を表 1 の各値に設定する．正方形環境の一辺の長さを L ∈ {10, 20}m とし，L に対する無線の通信可能距離の相対値を R ∈ {0, 2, 0.5, 1.0} とする．
つまり，レビィ分布による移動距離の変化の仕方が環境の大きさ・通信可能距離によってタスク達成能力にどの回転Fig. 4: Transition between move phase and rotate
phase in navigation- 0049 -Fig. 5: Set up for computer simulation

ような影響を与えるかを考察する．なお，無線の通信可能範囲は半径 R の円を仮定し，幾何学計算だけで連結性を判定する．1 節で述べたスワームロボットの定義および連結性を満たす通信可能距離と必要ロボット数の関係 [7] を参考に，ロボット台数を N ∈ {5, 10, 15, 20, 25}と変化させて実験を行う．タスクはターゲットを発見するか，1800 秒 (30 分，L = 10m の場合) もしくは 3600
秒 (60 分，L = 20m の場合) 経過した場合に終了とす
る．各実験の試行は各ロボットの初期姿勢を変えて 20回行う．
5.3

実験結果

各 (R, L) に対する平均タスク達成時間 (ステップ数．1
ステップは 0.03s に設定) およびタスク達成率を図 6 と図 7 にそれぞれ示す．各グラフは横軸にレビィフライトのパラメータ α をとり，ロボット台数 N を変えた結果を示している．各 (R, L) および N において，R = 0.2のときの N が小さい場合を除いて，ほぼ，α が 0.8 もしくは 0.9 のときに最もタスク達成時間が短くなっている．
L = 10 の結果を詳述する．台数 N で比較した場合，N が大きくなると，タスク達成時間が短くなる．通信
可能距離 R が 1.0 と 0.5 の場合，N = 15, 20, 25 のときの結果に大きな差はない (図 6(a), 6(c))．タスク達成率も R = 0.5 のときの N = 5 が少し下がるものの，その他はほぼ 100%を示している．R = 0.2 の場合でも，N が大きい方がタスク達成時間が短くなるが (図 6(e))，
タスク達成率は N が小さくなると下がる (図 7(e))．これは通信可能距離が短くなると少ないロボット台数では連結性を満たすことが難しくなり，ロボット台数がより多いほど連結性を満たしやすいことを示している．
つぎに L = 20 の結果を詳述する．タスク達成時間に関しては L = 10 よりも長くなるものの，傾向としては同様である (図 6(b), 6(d), 6(f))．ただし，タスク達成率に関しては，N が小さくなる，または，α が大きくなると，急激に減少する (図 7(b), 7(d), 7(f))．
5.4

しくは 0.9 のときが最良値とはいえない．したがって，通信可能距離およびロボット台数によって連結性が満たされていれば，α が 0.8 もしくは 0.9 のときに最も良い性能を示す．

6

おわりに

本稿では，スワームロボティクスに関する制御タスクの 1 つであるターゲット探索において，探索アルゴリズムであるレビィフライトの移動距離を決定するレビィ分布のパラメータに関して計算機実験によって考察を行った．その結果，無線通信ネットワークの連結性を満たす通信可能距離とロボット台数を使用していれば，レビィ分布の裾野が大きいほど探索性能は向上することがわかった．今後，本稿で得られた結果を実機実験において確認していく予定である．

参考文献[1] Brambilla, M., Ferrante, E., Birattari, M., Dorigo, M.,“Swarm Robotics: A Review from the Swarm Engineering Perspective,” Swarm Intelligence, Vol.7, No.1, pp.1-41,
2013.
[2] Trianni, V., Evolutionary Swarm Robotics, SpringerVerlag 2008.
[3] “スワーム：群れの創発的挙動生成”，計測と制御, Vol.52. No.3,
pp.179-276, 2013.
[4] Sahin, E., “Swarm Robotics: From Sources of Inspiration
to Domains of Application,” Lecture Notes in Computer
Science, Volume 3342/2005, pp.10-20, 2005.
[5] 杉山久桂，辻岡哲夫，村田正，ネットワーク化された群ロボッ
トにおける被災者発見システム，情報処理学会論文誌，Vol. 46,
No. 7, pp.1777-1788, 2005.
[6] Li, J., Andrew, L.L.H., Foh, C. H., Zukerman, M., HsiaoHwa, C., “Connectivity, Coverage and Placement in Wireless Sensor Networks,” Sensors, Vol.9, No.10, pp.76647693, 2009.
[7] 西口晃央，片田喜章，“パーコレーション理論を用いたスワー
ムロボットネットワークの連結性―通信距離とロボット数に関する考察―”，ロボティクス・メカトロニクス講演会’14, 講演
論文集 CD-ROM, 2A2-X06, 2014.
[8] 片田喜章，西口晃央，森脇和也, 渡壁亮介, “レヴィフライトを用いたスワームロボットネットワークのターゲット探索”, ロボ
ティクス・メカトロニクス講演会’15, 講演論文集 CD-ROM,2A1-K06, 2015.
[9] Lévy, P., “Theorie de l’Addition des Veriables Aleatoires”,
Gauthier-Villars, 1937.

考察

前節で得られた結果では，α が 0.8 もしくは 0.9 のときにタスク達成時間に関して最も良い性能を示した．これは表 1 において α が最も小さい 2 つであり，レビィ分布の形状の裾野が最も広い (図 1)，つまり，移動距離の変動が最も大きい場合に相当する．通信可能距離が長い場合 (R = 1.0) にはこの結果は予想しやすい．な
ぜなら，おそらく，移動距離が大きければターゲットの発見は早くなるが，どれだけ単体のロボットが全体と離れようとも通信可能距離が長いため，連結性が満たされるからである．通信可能距離が短い場合 (R = 0.2)についても N が大きい場合にはタスク達成時間に関してこれらの値が最も良い性能を示している．ただし，
R = 0.2 のときには，タスク達成率に関して α が 0.8 も- 0050 -[10] Mantegna, R.N., “Accurate Algorithm for Numerical Simulation of Lévy Stable Stochastic Processes,” Physical Review E, Vol. 49, No. 5 pp.4677-4689, 1994.
[11] Lee, C-Y. and Yao, X., “Evolutionary Programming Using
Mutations Based on the Lévy Probability Distribution,”
IEEE Transactions on Evolutionary Computation, Vol. 8,
No. 1, pp.1–13, 2004.
[12] 小山英朗, 生天目章, ”Random Walk と Levy Flight に基づく探索方法の比較”, 電子情報通信学会技術研究報告. AI, 人工
知能と知識処理, Vol.107, No.523, pp.19-24, 2008.
[13] Brooks, R., “A Robust Layered Control System for a Mobile Robot”, IEEE Journal of Robotics and Automation,
Vol.2, No.1, pp.14-23, 1986.

Average timestep

50000
40000

120000

N=5
N=10
N=15
N=20
N=25100000
Average timestep

60000

30000
20000
10000

80000

N=5N=10N=15N=20
N=2560000
40000
20000

0.8

1.0

1.2

1.4

1.6

1.8

2.0

0.8

1.0

1.2

α40000120000N=5N=10
N=15N=20N=25100000

30000
20000
10000
0.8

80000

1.6

1.8

2.0

1.8

2.060000
40000
200001.01.21.4α1.61.82.00.860000

120000

50000

10000040000
30000
N=5N=10N=15
N=20
N=2520000
10000
1.01.21.4α

1.01.21.4α(d) R = 0.5, L = 20

Average timestep

Average timestep

2.0

N=5N=10N=15
N=20
N=25(c) R = 0.5, L = 100.8

1.8(b) R = 1.0, L = 20

Average timestep

Average timestep

50000

1.6α(a) R = 1.0, L = 1060000

1.4

1.680000
60000
N=5N=10N=15
N=20
N=2540000
20000

1.82.0(e) R = 0.2, L = 100.8

1.01.21.4
α(f) R = 0.2, L = 20Fig. 6: Average time to detect a target for each α and N- 0051 -1.6

1.00.80.8
Success rate

Success rate

1.00.6
0.40.2

N=5N=10N=15N=20
N=250.00.8

0.6
0.4
0.2

1.01.2

1.4

1.61.8

N=5N=10N=15N=20
N=250.00.8

2.0

1.01.2α0.80.8
Success rate

Success rate

1.00.60.4
N=5N=10N=15N=20
N=251.2

1.4
α1.6

1.8

1.01.21.4α1.6

1.82.0(d) R = 0.5, L = 201.0

N=5N=10N=15N=20N=25

N=5N=10N=15N=20
N=250.8

0.6
0.4
0.20.00.82.0

N=5N=10N=15N=20
N=250.0
0.8

2.0

Success rate

Success rate

0.8

1.80.4(c) R = 0.5, L = 10
1.0

2.0

0.6

0.2

1.0

1.8(b) R = 1.0, L = 20

1.0

0.0
0.8

1.6

α(a) R = 1.0, L = 100.2

1.4

0.60.40.2

1.0

1.21.4
α1.6

1.82.0(e) R = 0.2, L = 10

0.0
0.8

1.0

1.2

1.4
α1.6(f) R = 0.2, L = 20

Fig. 7: Success rate for each α and N- 0052 -