1P2-H06
レヴィフライトを用いたスワームロボットのターゲット探索―最小移動量とターゲット分布に関するシミュレーションによる性能検証―

Swarm Robots Using Lévy Flight for Targets Exploration-Computer Simulation for Performance on Minimum Movement And Distribution of Targets-

正片田 喜章 (摂南大)Yoshiaki KATADA, Setsunan University, katada @ ele.setsunan.ac.jp
This study tackles the task for swarm robotics where robots explore the environment to detectmany targets. When a robot detects a target, the robot must be connected with a base station via
intermediate relay robots for wireless communication. In our previous results, we conﬁrmed that Lévyﬂight outperformed the usual random walk for exploration strategy in real robot experiments. This
paper investigated the performance of Lévy ﬂight varying minimum movement in navigation througha series of computer simulations. The results suggest that the search eﬃciency of Lévy ﬂight has an
optimal value for minimum movement and the overall target detection rate was not signiﬁcantly diﬀerent
between environments with uniformly and non-uniformly distributed targets.
Key Words: Swarm robotics, Navigation, Mobile robots

緒言

レヴィフライト2

スワームロボティクス (SR) とよばれる分野 [1][2][3] が近年，急速に注目を集めるようになってきている．その中でもŞahin ら[4] は単一ロボットでは問題解決が困難もしくは非効率なタスクに対して，構造が簡単で安価に構築でき制御器を含めて完全に均質な自律ロボット（シミュレーションではなく実機）を多数（最低でも 10-20 台）用いて解決策を提示しようというアプローチを提案している．このアプローチでは各ロボットに指示を出す監督的なエージェントの存在を前提としないため，スワームの群れ行動は各ロボットの局所的相互作用から必ず創発的に生成されることになる．上述の設計理念に従うと，各ロボットの構成は制御器を含めて均質であることが望ましい．このように設計された SRは頑健性・拡張性・柔軟性という特性を示すことが期待される [1]．
SR では，これまでに空間的な組織化行動・探索行動・集団的意思決定といったタスクが取り扱われてきた [1]．我々の研究グループでは，探索行動の中で協調探索に分類される，ターゲット探索をタスクとして取り扱ってきた．無線ネットワークによって通信可能な複数ロボットを用いてターゲットの探索を行い，あるロボットがターゲットを発見すると，その情報は無線ネットワークを介して基地局に送られる [5]．このとき，ターゲットを検出したロボットから基地局までは無線ネットワークによって連結 [6] されている必要がある．これまで，スワームロボットネットワークにおける基地局と各ロボット間の無線通信の連結性 [6] を保証する通信可能距離とロボット台数の関係について，パーコレーション理論にもとづく計算機実験を行った [7, 8]．さらに，上述の SRにより構成される無線ネットワーク (以降，SR ネットワークとよぶ) の連結性を考慮したロボットの台数と無線通信装置を使用し，実環境においてターゲット探索の実機実験を行っている [9, 10]．
文献 [9, 10] では，探索アルゴリズムとしてランダムウォークとレヴィフライト [11] を実装し，タスク達成率を比較した．その結果，移動距離が一定なランダムウォークに対し，移動距離が可変なレヴィフライトが圧倒的に優位であることを確認した．
レヴィフライトはレヴィ分布とよばれる確率密度関数に従って移動距離を決定するランダムウォークの 1 種である．文献 [12] では，レヴィ分布を表すいくつかの数式表現およびパラメータがス
ワームロボットネットワークによる探索性能に与える影響について計算機実験により考察を行っている．本稿では，文献 [12] で有効と報告されている数式を用いて，レヴィフライトをロボットに実装する際に設定する必要がある最小移動量に関して複数ターゲットが分布する環境における探索性能を検証する．以下，2 節
ではレヴィ分布について述べる．3 節では車輪型移動ロボットのモデルについて述べる．4 節ではロボットの制御器とレヴィフライトの実装法について説明する．5 節では複数ターゲット探索に関する計算機実験を行う．

探索実行以前に環境に対する知識が全くない場合を想定する．
この場合の探索行動としてランダムウォークが考えられる．ラン
ダムウォークの中でもブラウン運動として扱われるものが一般的である．一方，ランダムウォークの 1 つで，移動距離がレヴィ分布とよばれる確率密度関数にしたがう，レヴィフライト (Lévyﬂight[11]) が知られている．
レヴィ分布は w を移動距離として以下の式で表される．

∫ ∞Lα,γ (w) =α1e−γq cos(wq)dq, γ > 0, w ∈ R
π 0(1)

ここで，γ は分布の大きさを決めるパラメータであり，α は分布の形状を決めるパラメータで 0 < α < 2 の値をとる．本確率密度関数は w = 0 に関して対称であり，無限大の 2 次モーメントをもつことが特徴である．
文献 [12] では，レヴィ分布を表すいくつかの数式を用いた場合の性能を比較し，小山ら [13] が用いた式が最も良い探索性能を示すことを報告している．文献 [13] では，w ≫ 1 としてレヴィ分布を近似した次式を移動距離の決定に使用している．

L(w) ∝ w−α(2)ここで，α は分布の形状を変えるパラメータである．本研究では
文献 [12][13] に従い，L(w) ≡ w−1.2(3)に設定する．式 (3) の分布を図 1 に示す．
4.2 節で詳細を述べるが，本研究では (3) 式を利用して移動ロボットの直進移動時間を決定する．移動方向に関しては，一様分布に従うものとして扱う．

Probability distribution

110.8
0.6
0.4
0.2
05

101520
Step size

2530

Fig.1 Lévy distributions

No. 19-2 Proceedings of the 2019 JSME Conference on Robotics and Mechatronics, Hiroshima, Japan, June 5-8, 2019
1P2-H06(1)obstacle avoidance layer
distance sensor

detectobstacleturn right㻵turn lefttarget exploration layer

explorebase stationstop㻵

forwardmotorstargetdetectingsensortransmission layertransmit
message㼟

detecttargetturn rightturn left

Fig.4 Layer structure of SSA
Fig.2 Diﬀerential wheeled robots in an ODE simulation

move forward

turnFig.5 Transition between move phase and rotate phasein navigation

Fig.3 Ray of the distance sensers and the target detection
sensers
3スワームロボット構成

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

4コントローラ

4.1 サブサンプションアーキテクチャ
図 4 にスワームロボットに実装するサブサンプションアーキ
テクチャ(SSA)[14] のレイヤ構造 [10] を示す．本タスクを実現す
る SSA は，ターゲット発見情報送信レイヤ・ 障害物回避レイヤ・ターゲット探索レイヤの 3 層から構成されている．図中の I は抑制を表し，上位のレイヤが活性化する場合，下位のレイヤを抑制することを表している [14]．各レイヤはモジュールの結合により構成されている．
各レイヤの動作を説明する．ターゲット探索レイヤの探索モ
ジュールは後述する探索アルゴリズムにより，直進モジュール・右回転モジュール・左回転モジュールのいずれかに実行指令信号を送る．障害物回避レイヤの障害物検出モジュールは 3 節で述
べた距離センサからの入力値をもとに，左回転もしくは右回転モジュールに実行指令信号を送り，障害物を回避する. ターゲッ
ト発見情報送信レイヤの目標検出モジュールは 3 節で述べた左右いずれかのターゲット検出センサの出力値がしきい値を上回った場合に停止モジュールと情報送信モジュールに実行指令信号を送る．情報送信モジュールは SR ネットワークを介して基地局へターゲット発見情報を送信する．
4.2 探索アルゴリズムの実装
本研究で想定している左右二輪独立駆動型移動ロボットの仕様
では，回転を伴う移動（一般的には旋回と言う）において回転方向をランダムにすることと，一定距離を移動することを同時に行うことがその構造上難しい．そこで，移動フェーズと回転フェーズを交互に選択する (図 5)．移動フェーズでは，ロボットは任意の移動時間 (後述) の間に左右モータを回転させ前進する (図 4 における直進モジュール)．文献 [12] では，移動フェーズにおける1 ステップの実行時間は実機における予備実験の結果に基づいて6 秒に設定していた．この値は移動フェーズにおける最小移動量に相当し，実用上，環境の大きさなどを考慮して適切に設定しなければならない．本研究では，最小移動量を表すパラメータ w0を設定し，探索性能に与える影響を検証する．したがって，移動フェーズ毎の移動時間は 2 節で述べたレビィ分布により得られる移動ステップ数と w0 の積で決定される．回転フェーズでは，{45, 90, 135}[ °] のうちいずれかの回転角度をランダムに選択し，あらかじめ測定しておいた，その角度に対応する実行時間の間はその場で回転する (図 4 における左右回転モジュール)．

5

複数ターゲット探索に関する計算機実験

5.1 実験環境
壁に囲まれた正方形を実験環境とする (図 6(e))．環境の左下に無線通信基地局 (以下，基地局)1 台の設置を仮定する．本実験
は計算機実験のため，実際には基地局との通信を行わないが，SRネットワークの連結性のチェックに基地局の位置情報が必要となる．スワームロボットの初期位置は基地局近傍とし，図の左下方とする．本研究では文献 [12] の計算機実験設定と同様に，ロボットの初期位置付近を除く領域 (図 6(e) 右上の白枠内) に T 個の円柱 (直径 75mm) をターゲットとして設置し，ロボットが発見した円柱の数を最大数で割った値を発見率として定義しスワームロボットの探索性能評価を行う．T = {84, 168, 336} とし，ターゲットが一様に分布する環境 (84, 168, 336, uniform: 図 6(a), 図6(c), 図 6(e)) と偏って分布する環境 (84, 168, non-uniform: 図6(b), 図 6(d)) を設定する．
5.2 実験設定
本スワームロボットのタスクは，所定の時間内にできる限り多くのターゲットを見つけ，ネットワークを介して基地局にその発見情報を送信することである．したがって，ターゲットの発見時には発見したロボットと基地局はネットワークを介し，連結されている必要がある．また，連結性を満たして発見されたターゲッ
トは環境から取り除かれるものとする．
探索アルゴリズムとして 4 節で述べたレビィフライトを実装した SSA を採用する．正方形環境の一辺の長さを 20m とし，無線の通信可能距離を 20m とする．なお，無線の通信可能範囲は半径20m の円を仮定し，幾何学計算だけで連結性を判定する [6, 7, 8]．
1 節で述べたスワームロボットの定義および文献 [7, 8] を参考にNo. 19-2 Proceedings of the 2019 JSME Conference on Robotics and Mechatronics, Hiroshima, Japan, June 5-8, 2019
1P2-H06(2)Detection rate(a) T = 84, uniform(b) T = 84, non-uniform

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

w0=1
w0=5
w0=10
w0=15
w0=20
w0=25
w0=30
0100000

200000
Step300000(c) T = 168, uniform

Detection rate(a) T = 84, uniform(d) T = 168, non-uniform

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0w0=1
w0=5
w0=10
w0=15w0=20w0=25
w0=30
0100000

200000Step

300000Detection rate(b) T = 84, non-uniform

Targets

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0w0=1
w0=5
w0=10
w0=15
w0=20
w0=25
w0=30
0

Robots

100000200000Step

300000(c) T = 168, uniform

Base station(e) T = 336, uniform
Detection rate

Fig.6 Set up for computer simulation: distribution of targets

ロボット台数を N ∈ {5, 10, 15, 20} と変化させて，また，4 節で述べた最小移動量を表すパラメータを w0 ∈ {1, 5, 10, · · · , 30} と変化させて実験を行う．つまり，確率密度関数によって移動距離を決定する際に最小移動量が複数ロボットによる探索にどのような影響を与えるかを考察する．タスクはすべてのターゲットを発見するか，36 万ステップ (3600 秒に相当) 経過した場合に終了とする．各実験の試行は各ロボットの初期姿勢を変えて 50 回行う．

w0=1
w0=5w0=10w0=15
w0=20
w0=25
w0=300100000200000Step

300000(d) T = 168, non-uniform

Detection rate

5.3 実験結果
5.3.1 w0 に関する比較
各ターゲット分布に関して，N = 20 の場合に w0 を変えたと
きの時間経過に対する発見率を図 7 に示す．すべての w0 で最終ステップでの発見率はほぼ 100%に近づき，w0 の値で有意な差があるとはいえない．w0 = 1 では発見率の増加（以下，増加率とよぶ）は最も小さいうちの 1 つとなる．w0 = 5 のときに増加率は最も大きくなる．w0 > 5 の範囲では wo の値が増加すると増加率は低下する．w0 = 10 では増加率は最も小さいうちの 1 つとなり，探索の終盤では w0 = 1 よりも増加率は小さくなっている．w0 に関する探索性能の傾向は各ターゲット分布に関してほぼ変わらない．この増加率に関する傾向は他の N に関しても確認できた．

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
01
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

w0=1
w0=5w0=10
w0=15
w0=20
w0=25
w0=30
0

100000200000Step

300000(e) T = 336, uniform

Fig.7 Average detection rate for each time step with N =20No. 19-2 Proceedings of the 2019 JSME Conference on Robotics and Mechatronics, Hiroshima, Japan, June 5-8, 2019
1P2-H06(3)6Ditection rate

5.3.2 各ターゲット分布に関する比較
前節で発見率の増加が最も大きかった w0 = 5 の場合の，各 Nに関してターゲット分布を変えた場合の時間経過に対する発見率を図 8 に示す．T が大きい方が増加率は大きくなっている．本
実験設定ではターゲットの重なりは想定していないため，一様な分布で T が大きいとターゲットは環境に対し相対的に広く分布する．そのため，ロボットの初期位置に近いターゲットも増えることで増加率は若干大きくなる．同じ N では一様な分布の方が偏った分布の場合よりも発見率の増加は大きくなっている．偏った分布ではロボットの初期位置よりも離れた場所にターゲットが分布しており，この結果も妥当なものだと考えられる．N が大きい方が発見率の増加は大きくなっている．

おわりに

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0

Ditection rate

本稿では，レヴィフライトをロボットに実装する際に設定する必要がある最小移動量と複数ターゲットの分布に関して探索性能を検証した．最終的なターゲットの発見性能に関しては，十分な時間が経過すれば，各設定に大きな差は見られないことを確認した．探索効率に関しては，最小移動量に閾値が存在すること，ターゲットが一様に多く分布する方が効率が良いことがわかった．
また，ロボット台数が多い方が良い性能を示すことを確認した．
今後，最小移動量を自動的に更新する手法を検討したい．

参考文献[1] M. Brambilla, E. Ferrante, M. Birattari, M. Dorigo: Swarm
Robotics: A Review from the Swarm Engineering Perspective,
Swarm Intelligence, vol.7-1, pp.1–41, 2013.
[2] V. Trianni: Evolutionary Swarm Robotics, Springer-Verlag,
2008.

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

[4] E. Şahin: Swarm Robotics: From Sources of Inspiration toDomains of Application, Swarm Robotics. SR 2004, Lecture
Notes in Computer Science, 3342 Springer, Berlin, pp.10–20,
2004.

Ditection rate

[5] 杉山久桂，辻岡哲夫，村田正: ネットワーク化された群ロボットにおける被災者発見システム，情報処理学会論文誌，vol.46-7, pp.1777–1788, 2005.
[6] J. Li, L.L.H Andrew, C.H. Foh, M. Zukerman, C. Hsiao-Hwa:Connectivity, Coverage and Placement in Wireless Sensor Networks, Sensors, vol.9-10, pp.7664–7693, 2009.
[7] Y. Katada: Connectivity of Swarm Robot Networks for Communication Range and the Number of Robots Based on Percolation Theory, Proceedings of the 2014 IEEE/SICE International Symposium on System Integration, pp.93–98, 2014.

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
00

Detection rate

[10] Y. Katada, A. Nishiguchi, K. Moriwaki, R. Watakabe: Swarm
Robotic Network Using Lévy Flight in Target Detection Problem, Artificial Life and Robotics, vol.21-3, pp.295–301, 2016.
[11] P. Lévy: Theorie de l’Addition des Veriables Aleatoires,Gauthier-Villars, 1937.
[12] 片田喜章, “レヴィフライトを用いたスワームロボットネットワークによる探索 −掃引作業に関する計算機実験を用いた検証”, 計測自動制御学会論文集, vol.54-1, pp.22-30, 2018.
[13] 小山英朗, 生天目章: Random Walk と Levy Flight に基づく探索方法の比較, 電子情報通信学会技術研究報告. AI, 人工知能と知識処理, vol.107-523, pp.19–24, 2008.
[14] R. Brooks: A Robust Layered Control System for a Mobile
Robot, IEEE Journal of Robotics and Automation, vol.2-1,pp.14–23, 1986.

300000100000200000
Step(b) N = 10300000T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform[8] 片田喜章: 通信距離とノード数に対する無線通信ネットワークの連結性, 計測自動制御学会 システム・情報部門学術講演会 2015 講演
論文集, pp.1135–1138, 2015.
[9] 片田喜章，西口晃央，森脇和也, 渡壁亮介: レヴィフライトを用いたスワームロボットネットワークのターゲット探索, ロボティクス・メカトロニクス講演会’15, 講演論文集 CD-ROM, 2A1-K06, 2015.

200000
Step(a) N = 5

T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0[3] 大倉和博: 特集 スワーム：群れの創発的挙動生成, 計測と制御,
vol.52-3, pp.179–182, 2013.

100000

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0100000

200000
Step(c) N = 15300000T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0100000

200000
Step(d) N = 20

300000

Fig.8 Average detection rate for each time step with
W0 = 5

No. 19-2 Proceedings of the 2019 JSME Conference on Robotics and Mechatronics, Hiroshima, Japan, June 5-8, 2019
1P2-H06(4)