レヴィフライトを用いたスワームロボットのターゲット探索-最小移動量の更新則の提案とシミュレーションによる性能検証○片田 喜章（摂南大学）

Swarm Robots Using Lévy Flight in Targets Exploration-Computer Simulation for Performance of Lévy Flight withUpdated Minimum Movement○ Yoshiaki KATADA (Setsunan University)
Abstract : This study tackles the task for swarm robotics where robots explore the environment to detect many targets.
When a robot detects a target, the robot must be connected with a base station via intermediate relay robots for wirelesscommunication. In our previous results, we confirmed that Lévy flight outperformed the usual random walk for exploration
strategy in real robot experiments. This paper investigated the performance of Lévy flight with the update method of theminimum movement in navigation through a series of computer simulations. The results suggest that the performance of Lévy
flight with the update method fell between the best and worst performance with the fixed values of minimum movement.

1.

緒言てターゲット探索の実機実験を行っている [9, 10]．文献

スワームロボティクス (SR) とよばれる分野 [1][2][3] が近年，注目を集めている．その中でもŞahin ら [4] は単一ロボットでは問題解決が困難もしくは非効率なタスクに対して，構造が簡単で安価に構築でき制御器を含めて完全に均質な自律ロボット（シミュレーションではなく実機）を多数（最低でも 10-20 台）用いて解決策を提示しようというアプローチを提案している．このアプローチでは各ロボットに指示を出す監督的なエージェントの存在を前提としないため，スワームの群れ行動は各ロボットの局所的相互作用から必ず創発的に生成されることになる．上述の設計理念に従うと，各ロボットの構成は制御器を含めて均質であることが望ましい．このように設計された SR は頑健性・拡張性・柔軟性という特性を示すことが期待される [1]．

SR では，これまでに空間的な組織化行動・探索行動・集団的意思決定といったタスクが取り扱われてきた [1]．我々の研究グループでは，探索行動の中で協調探索に分類される，ターゲット探索をタスクとして取り扱ってきた．無線ネットワークによって通信可能な複数ロボットを用いてターゲットの探索を行い，あるロボットがターゲットを発見すると，その情報は無線ネットワークを介して基地局に送られる [5]．このとき，ターゲットを検出したロボットから基地局までは無線ネットワークによって連結 [6] されている必要がある．これまで，スワームロボットネット
ワークにおける基地局と各ロボット間の無線通信の連結性[6] を保証する通信可能距離とロボット台数の関係について，パーコレーション理論にもとづく計算機実験を行った[7, 8]．さらに，上述の SR により構成される無線ネット
ワーク (以降，SR ネットワークとよぶ) の連結性を考慮したロボットの台数と無線通信装置を使用し，実環境におい[9, 10] では，探索アルゴリズムとしてランダムウォークとレヴィフライト [11] を実装し，タスク達成率を比較した．
その結果，移動距離が一定なランダムウォークに対し，移動距離が可変なレヴィフライトが圧倒的に優位であることを確認した．
レヴィフライトはレヴィ分布とよばれる確率密度関数に従って移動距離を決定するランダムウォークの 1 種である．
文献 [12] では，レヴィ分布を表すいくつかの数式表現およびパラメータがスワームロボットネットワークによる探索性能に与える影響について計算機実験により考察を行っている．文献 [13] では，文献 [12] で有効と報告されている数式を用いて，レヴィフライトをロボットに実装する際に設定する必要がある最小移動量と複数ターゲットの分布に関して探索性能を検証した．探索効率に関して最小移動量に閾値が存在すること，ターゲットが一様に多く分布する方が効率が良いことがわかった．本稿では，最小移動量を自動的に更新する手法を提案し，その性能を計算機実験により検証する．
以下，2. 節ではレヴィ分布について述べる．3. 節では車輪型移動ロボットのモデルについて述べる．4. 節ではロボットの制御器とレヴィフライトの実装法について説明する．5. 節ではレヴィフライトを実装する際の最小移動量を決定するパラメータに関する自動更新則を提案する．6. 節
では複数ターゲット探索に関する計算機実験を行う．

2.

レヴィフライト

探索実行以前に環境に対する知識が全くない場合を想定する．この場合の探索行動としてランダムウォークが考え

第20回システムインテグレーション部門講演会（SI2019）（2019年12月12日～14日・香川）- 2740 -SY0010/19/0000 - 2740 © 2019 SICE

Probability distribution

10.80.60.40.205101520
Step size2530Fig. 2: Diﬀerential wheeled robots in an ODE simulation

Fig. 1: Lévy distribution
られる．ランダムウォークの中でもブラウン運動として扱われるものが一般的である．一方，ランダムウォークの 1つで，移動距離がレヴィ分布とよばれる確率密度関数にしたがう，レヴィフライト (Lévy ﬂight[11]) が知られている．
レヴィ分布は w を移動距離として以下の式で表される．
∫1 ∞−γqαLα,γ (w) =ecos(wq)dq, γ > 0, w ∈ R (1)π 0
ここで，γ は分布の大きさを決めるパラメータであり，αは分布の形状を決めるパラメータで 0 < α < 2 の値をとる．本確率密度関数は w = 0 に関して対称であり，無限大の 2 次モーメントをもつことが特徴である．
文献 [12] では，レヴィ分布を表すいくつかの数式を用いた場合の性能を比較し，小山ら [14] が用いた式が最も良い探索性能を示すことを報告している．文献 [14] では，w ≫ 1 としてレヴィ分布を近似した次式を移動距離の決定

Fig. 3: Ray of the distance sensers and the target detection sensersの 1 点鎖線)，無線通信装置を搭載する. 距離センサの計
測可能距離は 300mm，ターゲット検出センサの計測可能
距離は 200mm とする．駆動装置としてモータ 2 個を用いる．無線通信装置は Zigbee 規格を想定し，アドホックネットワークを構成し，マルチホップ通信が可能であると仮定する．に使用している．

L(w) ∝ w−α(2)ここで，α は分布の形状を変えるパラメータである．本研
究では文献 [12][14] に従い，L(w) ≡ w−1.2

4.

コントローラ4.1

サブサンプションアーキテクチャ

Fig.4 にスワームロボットに実装するサブサンプション(3)

アーキテクチャ(SSA)[15] のレイヤ構造 [10] を示す．本タに設定する．(3) 式の分布 (1 ≤ w ≤ 30) を Fig.1 に示す．

スクを実現する SSA は，ターゲット発見情報送信レイヤ・4.2 節で詳細を述べるが，本研究では (3) 式を利用して障害物回避レイヤ・ターゲット探索レイヤの 3 層から構移動ロボットの直進移動時間を決定する．移動方向に関し成されている．図中の I は抑制を表し，上位のレイヤが活ては，一様分布に従いランダムに決定する．

性化する場合，下位のレイヤを抑制することを表している[15]．各レイヤはモジュールの結合により構成されている．
各レイヤの動作を説明する．ターゲット探索レイヤの探3.

スワームロボット構成

索モジュールは後述する探索アルゴリズムにより，直進モ

本研究では，文献 [9, 10] の実験で使用した，左右二輪独立駆動型の移動ロボットを動力学シミュレータ ODEを用いてモデル化する (Fig.2)．設定を以下に示す．直径170mm，高さ 75mm の台車に，距離センサ (前方に 4 個:Fig.3 の点線)，ターゲット検出センサ (両端に 2 個: Fig.3

ジュール・右回転モジュール・左回転モジュールのいずれかに実行指令信号を送る．障害物回避レイヤの障害物検出モジュールは 3. 節で述べた距離センサからの入力値をもとに，左回転もしくは右回転モジュールに実行指令信号を送り，障害物を回避する. ターゲット発見情報送信レイヤの- 2741 -distance sensor

obstacle avoidance layer
detectobstacle㻵

最小移動量の更新則

1. 節で述べたように，レヴィフライトを用いたスワー
ムロボットの探索効率に関して最小移動量を決定するパラ

turn right

メータ w0 に閾値が存在する．w0 の最適値は環境大きさ・

turn left

形状およびターゲット分布に依存することが予想される．

㻵target exploration layer
explorebase station

stop

5.

forwardmotorstargetdetectingsensortransmission layertransmit
message㼟

detecttarget

この値を適切に決定しなければならない．そのための 1 つturn rightの方法として，w0 の値は SR の設計者によって経験と勘にturn left基づいて決定されるか，望ましい振舞いが得られるまでパラメータ調節を行うことが考えられる．我々の研究グルー
プはこれまでこの方法を採用してきた．別の方法として，

Fig. 4: Layer structure of SSA

自動設計という観点からパラメータの自動調節が考えられる．そこで，探索過程におけるターゲットの発見頻度に基move forward

づく w0 の更新則を以下のように提案する．

turn

各ロボットにおいて w0 を次のように更新する．
 w0 − ∆w0 , if s = 1 and w0 > w0min
w0 ←w0 + ∆w0 , if s = 0 and w0 < w0max (4)
w0 ,otherwise

Fig. 5: Transition between move phase and rotate phasein navigation
目標検出モジュールは 3. 節で述べた左右いずれかのターゲット検出センサの出力値がしきい値を上回った場合に停止モジュールと情報送信モジュールに実行指令信号を送る．
情報送信モジュールは SR ネットワークを介して基地局へターゲット発見情報を送信する．

ここで，w0min , w0max , s はそれぞれ w0 の下限値，上限値，新しいターゲットを発見したフラグを表す．∆w0 は 1に設定する．文献 [13] における先行研究の実験結果を参考に，w0min = 1, w0max = 30 に設定する．各試行におけるw0 の初期値を w0min とする．s を以下のように設定する．

4.2

探索アルゴリズムの実装

おいて回転方向をランダムにすることと，一定距離を移動


if a new target detected and ∆t > 5
 1,s =0,if ∆t > 10
−1, otherwise

することを同時に行うことがその構造上難しい．そこで，

ここで，∆t [s] は各ロボットがターゲットを最後に発見し回転フェーズと移動フェーズを交互に選択する (Fig.5)．回てからの経過時間もしくはリセットされてからの経過時間

本研究で想定している左右二輪独立駆動型移動ロボットの仕様では，回転を伴う移動（一般的には旋回と言う）に転フェーズでは，{45, 90, 135}[ °] のうちいずれかの回転角度をランダムに選択し，あらかじめ測定しておいた，そを表し，(4) 式により w0 が更新されたときにリセットされる．の角度に対応する実行時間の間はその場で回転する (Fig.4における左右回転モジュール)．移動フェーズでは，ロボッ
トは任意の移動時間 (後述) の間に左右モータを回転させ前進する (Fig.4 における直進モジュール)．文献 [12] では，移動フェーズにおける 1 ステップの実行時間は実機におけ

6.

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

6.1

実験環境

る予備実験の結果に基づいて 6 秒に設定していた．この値

壁に囲まれた正方形を実験環境とする (Fig.6(e))．各環は，モータ (車輪) の回転速度を一定に設定しているため境の左下に無線通信基地局 (以下，基地局)1 台の設置を仮に移動フェーズにおける最小移動量を設定することに相当定する．本実験は計算機実験のため，実際には基地局とのし，実用上，環境の大きさなどを考慮して適切に設定しな通信を行わないが，SR ネットワークの連結性のチェックにければならない．文献 [13] では，この値を，最小移動量を基地局の位置情報が必要となる．スワームロボットの初期決定するパラメータ w0 として設定し，探索性能に与える位置は基地局近傍とし，図の左下方とする．本研究では文影響を検証している．したがって，移動フェーズ毎の移動献 [12] の計算機実験設定と同様に，ロボットの初期位置付時間は 2. 節で述べたレビィ分布により得られる移動ステッ近を除く領域 (Fig.6(e) 右上の白枠内) に T 個の円柱 (直径プ数と w0 の積で決定され，厳密にはこれに車輪の角速度75mm) をターゲットとして設置し，ロボットが発見した円柱の数を最大数で割った値を発見率として定義しスワームと半径を掛けることで移動量が算出される．

- 2742 -トワークを介し，連結されている必要がある．また，連結性を満たして発見されたターゲットは環境から取り除かれるものとする．
探索アルゴリズムとして 4. 節で述べたレビィフライトを実装した SSA を採用する．正方形環境の一辺の長さを20m とし，無線の通信可能距離を 20m とする．なお，無線の通信可能範囲は半径 20m の円を仮定し，幾何学計算だけで連結性を判定する [6, 7, 8]．1. 節で述べたスワーム(a) T = 84, uniform(b) T = 84, non-uniform

ロボットの定義および文献 [7, 8] を参考にロボット台数をN ∈ {5, 15, 20} と変化させて実験を行う．つまり，確率密度関数によって移動距離を決定する際に最小移動量を決定するパラメータの更新が複数ロボットによる探索にどのような影響を与えるかを考察する．タスクはすべてのターゲットを発見するか，36 万ステップ (3600 秒に相当) 経過した場合に終了とする．各実験の試行は各ロボットの初期姿勢を変えて 50 回行う．
(c) T = 168, uniform(d) T = 168, non-uniform

6.3

実験結果

ロボット台数 N と各ターゲット分布に関して，時間経過に対する発見率を Fig.7-9 に示す．比較のために，先行研究の実験 [13] で得られている w0 を固定 (w0 ∈ {1, 5, 10, 30})した結果を併せて示している．N = 5 の場合ではいずれの設定でも最終ステップでの発見率は 100 % に達しなかった．N = 15, 20 の場合では発見率は 100 % に達し，w0 のTargets

更新則を用いた場合でも発見率は 100 % に達した．発見率の増加 (以下，探索効率とよぶ) に関して，更新則を用いた場合を含めてターゲットが一様に，かつ，多く分布する方が効率が良いことがわかった．更新則を用いた場合，wo = 5 と w0 = 1, 30 に関する探索効率の間の値をとるこRobotsとがわかる．つまり，提案する更新則は，w0 を固定した場
合に示す最高効率を上回ることはないが，最低効率よりもBase station(e) T = 336, uniform

つねに良い性能を示す．本実験では，試行開始時にすべてFig. 6: Set up for computer simulation: distribution ofのロボットの w0 を w0min に初期化していた．多様性を考

targets

慮し，例えば w0min ≤ w0 ≤ w0max の範囲でランダムに初期化するという方法も今後考えられる．

ロボットの探索性能評価を行う．T = {84, 168, 336} とし，ターゲットが一様に分布する環境 (84, 168, 336, uniform:

7.

Fig.6(a), 6(c), 6(e)) と偏って分布する環境 (84, 168, nonuniform: Fig.6(b), 6(d)) を設定する．

結言

本稿では，レヴィフライトをロボットに実装する際に必要な最小移動量を決定するパラメータを自動的に更新する手法を提案し，その探索性能を計算機実験により検証した．

6.2

提案する自動更新則は，十分なロボット台数を使用してい実験設定

れば，最終ステップではターゲット発見率 100% を示し，本スワームロボットのタスクは，所定の時間内にできる限り多くのターゲットを見つけ，ネットワークを介して基地局にその発見情報を送信することである．したがって，探索過程では最小移動量を決定するパラメータを固定した場合の探索効率の最悪値と最良値の間の値を示すことを確認した．探索効率に関してパラメータを固定した場合の最ターゲットの発見時には発見したロボットと基地局はネッ- 2743 -良値を優越することはないが，適応的にパラメータを更新することが可能であり，実用的な手法であるといえる．今Detection rate後，最小移動量を決定するパラメータをランダムに初期化する方法を用いて，提案する自動更新則の探索性能を検証したい．

参考文献

10.90.80.7
0.6
0.5
0.4
0.3
0.2
0.1
0

w0=1
w0=5
w0=10w0=30
updating w00[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)[3] 大倉和博: “特集 スワーム：群れの創発的挙動生成”,
計測と制御, vol.52-3, pp.179–182(2013)[4] E. Şahin: Swarm Robotics: “From Sources ofInspiration to Domains of Application”, SwarmRobotics. SR 2004, Lecture Notes in Computer Science, 3342 Springer, Berlin, pp.10–20(2004)[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.910, pp.7664–7693(2009)[7] Y. Katada: “Connectivity of Swarm Robot Networks for Communication Range and the Numberof Robots Based on Percolation Theory”, Proceedings of the 2014 IEEE/SICE International Symposium on System Integration, pp.93–98(2014)[8] 片田喜章: “通信距離とノード数に対する無線通信ネットワークの連結性”, 計測自動制御学会 システ
ム・情報部門学術講演会 2015 講演論文集, pp.1135–1138(2015)[9] 片田喜章，西口晃央，森脇和也, 渡壁亮介: “レヴィフライトを用いたスワームロボットネットワークのターゲット探索”, ロボティクス・メカトロニクス講演会’15, 講演論文集 CD-ROM, 2A1-K06(2015)[10] Y. Katada, A. Nishiguchi, K. Moriwaki, R. Watakabe: “Swarm Robotic Network Using Lévy Flightin Target Detection Problem”, Artificial Life andRobotics, 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] 片田喜章：“レヴィフライトを用いたスワームロボッ
トのターゲット探索 ―最小移動量とターゲット分
布に関するシミュレーションによる性能検証―”, ロ
ボティクス・メカトロニクス講演会’19 講演論文集,
CD-ROM, 1P2-H06(2019)[14] 小山英朗, 生天目章: “Random Walk と Levy Flightに基づく探索方法の比較”, 電子情報通信学会技術研究報告. AI, 人工知能と知識処理, vol.107-523, pp.19–24(2008)[15] R. Brooks: “A Robust Layered Control System fora Mobile Robot”, IEEE Journal of Robotics andAutomation, vol.2-1, pp.14–23(1986)

100000200000300000

StepDetection rate(a) T = 84, uniform
10.9
0.80.7
0.6
0.5
0.4
0.3
0.2
0.1
0

w0=1
w0=5
w0=10
w0=30
updating w00100000

200000Step

300000Detection rate(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=30
updating w00100000

200000Step

300000Detection rate(c) T = 168, 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=30
updating w00100000

200000Step

300000Detection rate(d) T = 168, non-uniform
10.9
0.80.70.6
0.5
0.4
0.3
0.2
0.1
0w0=1
w0=5
w0=10
w0=30
updating w0
0100000

200000Step

300000(e) T = 336, uniform

Fig. 7: Average detection rate for constant and updating w0 with N = 5- 2744 -Detection rate

Detection rate

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=30
updating w0
0100000

200000

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0300000

w0=1
w0=5
w0=10
w0=30
updating w0
0100000

Step

w0=1
w0=5w0=10w0=30
updating w0
0100000

200000
Step

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0300000

w0=1
w0=5
w0=10
w0=30
updating w00w0=1
w0=5
w0=10
w0=30
updating w0
0100000

200000
Step

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

3000000100000

200000Step

Detection rate

Detection rate

300000100000200000Step

300000100000200000Step

300000(d) T = 168, non-uniform

Detection rate

Detection rate

200000
Step

w0=1
w0=5
w0=10
w0=30
updating w0
0

w0=1
w0=5
w0=10
w0=30updating w00100000

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.10(d) T = 168, non-uniform
10.90.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0300000(c) T = 168, uniform

w0=1
w0=5
w0=10
w0=30
updating w00200000
Step

w0=1
w0=5
w0=10
w0=30
updating w0(c) T = 168, uniform
10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0100000(b) T = 84, non-uniform

Detection rate

Detection rate(b) T = 84, non-uniform
10.9
0.8
0.7
0.60.5
0.4
0.3
0.2
0.1
0300000(a) T = 84, uniform

Detection rate

Detection rate(a) T = 84, uniform
10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0200000
Step

300000

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=30
updating w00100000

200000Step

300000(e) T = 336, uniform(e) T = 336, uniform

Fig. 8: Average detection rate for constant and updating w0 with N = 15

Fig. 9: Average detection rate for constant and updating w0 with N = 20- 2745 -