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

Sweeping by 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 many targets. When arobot 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 experiment. In this study, we investigated the performance of Lévy flight on a sweeping task through aseries of computer simulations.

1.

緒言

ヴィフライトが圧倒的に優位であることを確認した．上述のタスクでは環境内でロボットの初期位置から最も遠い場

スワームロボティクス (SR) とよばれる分野 [1][2][3] が所に 1 つのターゲットを置いていた．

近年，急速に注目を集めるようになってきている．その中

本稿では環境内をくまなく探索する，もしくは複数ター

でも Sahin ら [4] は単一ロボットでは問題解決が困難もしゲットを探索する，ことを想定し，SR ネットワークによくは非効率なタスクに対して，構造が簡単で安価に構築でる掃引作業を扱う．探索アルゴリズムとしてレヴィフライ

き制御器を含めて完全に均質な自律ロボット（シミュレー

トの有効性に関して，計算機実験により考察を行う．

ションではなく実機）を多数（最低でも 10-20 台）用いて解決策を提示しようというアプローチを提案している．このアプローチでは各ロボットに指示を出す監督的なエー2.

レヴィフライトジェントの存在を前提としないため，スワームの群れ行動
探索実行以前に環境に対する知識が全くない場合を想定

は各ロボットの局所的相互作用から必ず創発的に生成されることになる．上述の設計理念に従うと，各ロボットの構成は制御器を含めて均質であることが望ましい．均質でありながら，個々のロボットが多様な，時として役割分担的する．この場合の探索行動としてランダムウォークが考えられる．ランダムウォークの中でもブラウン運動として扱われるものが一般的である．一方，ランダムウォークの 1つで，移動距離がレヴィ分布とよばれる確率密度関数にしな振舞いを示すことが要求される．
我々の研究グループでは，協調探索に分類される，ターたがう，レヴィフライト (Lévy ﬂight[10]) が知られている．

トの探索を行い，あるロボットがターゲットを発見すると，レヴィ分布は以下の式で表される．
∫1 ∞ −γqα
ecos(wq)dq, γ > 0, w ∈ R (1)Lα,γ (w) =π 0

その情報は無線ネットワークを介して基地局に送られる．

ここで，γ は分布の大きさを決めるパラメータであり，α

これまで，スワームロボットネットワークにおける基地局は分布の形状を決めるパラメータで 0 < α < 2 の値をとと各ロボット間の無線通信の連結性 [6] を保証する通信可る．本確率密度関数は w = 0 に関して対称であり，無限大能距離とロボット台数の関係について，パーコレーションの 2 次モーメントをもつことが特徴である．本研究では文理論にもとづく計算機実験を行った [7]．さらに，上述の献 [11, 12] に従い，γ = 1 とする．図 1 に (1) 式による確SR により構成される無線ネットワーク (以降，SR ネットワークとよぶ) の連結性を考慮したロボットの台数と無線率分布 (γ = 1, α = {0.8, 1.8, 1.99}) を示す．

通信装置を使用し，実環境においてターゲット探索の実機案されている [11]．以下にその生成式を示す [11, 12]．

ゲット探索 [5] をタスクとして取り扱ってきた．無線ネット
ワークによって通信可能な複数ロボットを用いてターゲッレヴィ分布に従う確率変数を生成するアルゴリズムが提実験を行っている [8][9]．文献 [8] および [9] では，探索アルゴリズムとしてランダムウォークとレヴィフライト [10]を実装し，タスク達成率を比較した．その結果，移動距離が一定なランダムウォークに対し，移動距離が可変なレ

第17回システムインテグレーション部門講演会(SI2016)（2016年12月15日～17日・札幌）- 0306 -v=|v|

x1|y| α,w = {(k(α) − 1)e− c(α) + 1)}v

(2)

SY0012/16/0000 - 0306 © 2016 SICE

Probability distribution

100Lapp
Lα=1.99
Lα=1.8Lα=0.8N(0,1)

10-1
10-2
10-310-40102030
Fig. 2: Diﬀerential wheeled robots

w
Fig. 1: Lévy and standard normal distributions

4.

コントローラ

ここで，x と y はガウス分布に従う独立な確率変数であり，4.1

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

k(α) と c(α) は α に依存し，文献 [11] によって 0.8 ≤ α ≤1.99 の範囲で各値が得られている．
第 4.2 節で詳細を述べるが，本研究では (2) 式を用いて移動ロボットの直進移動時間を決定する．したがって，(2)式の w ≥ 0 の範囲だけを必要とするため，(2) 式中の w を|w| として計算する．
計算機実験上の移動ロボットにレヴィフライトを実装した研究として文献 [13] がある．ここでは，w ≫ 1 として

図 3 にスワームロボットに実装するサブサンプションアーキテクチャ(SSA)[15] のレイヤ構造 [9] を示す．本タ
スクを実現する SSA は，ターゲット発見情報送信レイヤ・障害物回避レイヤ・ターゲット探索レイヤの 3 層から構成されている．図中の I は抑制を表し，上位のレイヤが活性化する場合，下位のレイヤを抑制することを表している[15]．各レイヤはモジュールの結合により構成されている．
各レイヤの動作を説明する．ターゲット探索レイヤの探レヴィ分布を近似した次式 [12][14] を移動距離の決定に使索モジュールは後述する探索アルゴリズムにより，直進モ用している．

ジュール・右回転モジュール・左回転モジュールのいずれ

L(w) ∝ w−α(3)かに実行指令信号を送る．障害物回避レイヤの障害物検出

ここで，w は移動距離，α は分布の形状を変えるパラメー

モジュールは第 3. 節で述べた距離センサからの入力値をも−1.2に設とに，左回転もしくは右回転モジュールに実行指令信号を定する．(3) 式および比較に用いる標準正規分布 (N (0, 1))

送り，障害物を回避する. ターゲット発見情報送信レイヤの確率分布を図 1 に示す．(2) 式よりも (3) 式から得られの目標検出モジュールは第 3. 節で述べた左右いずれかのる確率密度関数値の方が移動距離の範囲全体に対して大きターゲット検出センサの出力値がしきい値を上回った場合いことがわかる．に停止モジュールと情報送信モジュールに実行指令信号をタであり，本研究では文献 [13] に従い L(w) = w送る．情報送信モジュールは SR ネットワークを介して基地局へターゲット発見情報を送信する．

駆動型の移動ロボットを動力学シミュレータ ODE を用い䝍䞊䝀䝑䝖Ⓨぢ᝟ሗ㏦ಙ䝺䜲䝲┠ᶆ᳨ฟ

᝟ሗ㏦ಙ
೵Ṇてモデル化する (図 2)．設定を以下に示す．直径 170mm，㞀ᐖ≀ᅇ㑊䝺䜲䝲

ト検出センサ (両端に 2 個)，無線通信装置を搭載する. 距
離センサの計測可能距離は約 300mm，ターゲット検出センサの計測可能距離は約 200mm とする．駆動装置としてモータ 2 個を用いる．無線通信装置は Zigbee 規格を想定㊥㞳䝉䞁䝃

高さ 75mm の台車に，距離センサ (前方に 4 個)，ターゲッ㞀ᐖ≀᳨ฟྑᅇ㌿㻵ᕥᅇ㌿䝍䞊䝀䝑䝖᥈⣴䝺䜲䝲᥈⣴㻵┤㐍ྑᅇ㌿
ᕥᅇ㌿し，アドホックネットワークを構成し，マルチホップ通信が可能であると仮定する．

Fig. 3: Layer structure of SSA- 0307 -䝰䞊䝍本研究では，文献 [9] の実験で使用した，左右二輪独立ᇶᆅᒁ

スワームロボット構成
㉥እ⥺
䝉䞁䝃

3.

4.2

探索アルゴリズムの実装

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

Fig. 4: Set up for computer simulation

モジュール)．
探索アルゴリズムとしてレビィフライトまたはランダムウォークを採用し，性能を比較する．ランダムウォークで5.

掃引作業計算機実験

5.1

実験環境

は移動ステップ数を決定する確率密度関数として第 2. 節の末尾で述べた標準正規分布 (N (0, 1)) を採用する．第 2.
節で述べた (1) 式におけるレビィ分布 (以降，Lα と表示)

壁に囲まれた正方形を実験環境とする (図 4)．図 4 の左の形状を決めるパラメータ α は 0.8 ≤ α ≤ 1.99 の範囲下に無線通信基地局 (以下，基地局) の設置を仮定する．本で設定する．(3) 式におけるレビィ分布 (以降，Lapp ) の実験は計算機実験のため，実際には基地局との通信を行わパラメータは第 2. 節で述べたものを採用する．正方形環

ないが，SR ネットワークの連結性のチェックに基地局の境の一辺の長さを L = 20m とし，L に対する無線の通位置情報が必要となる．スワームロボットの初期位置は基信可能距離の相対値を R ∈ {0, 2, 0.5, 1.0} とする．つま地局近傍とし，図の左下方 (赤色) とする．掃引作業を想定

り，確率密度関数による移動距離の決定法が通信可能距離する場合，ロボットもしくは対象のセンサが通過した領域によってタスク達成能力にどのような影響を与えるかを考を掃引された領域とみなし，掃引可能面積に対する掃引さ察する．なお，無線の通信可能範囲は半径 R の円を仮定れた面積の比率を指標とすることが多い [16]．しかし，こし，幾何学計算だけで連結性を判定する．第 1. 節で述べたの方法では計算機実験の設定が煩雑になる．そこで，本研

スワームロボットの定義および連結性を満たす通信可能距

究ではロボットの初期位置付近を除く領域に 336 個の円柱離と必要ロボット数の関係 [7] を参考に，ロボット台数を(直径 75mm，緑色) をターゲットとして設置し，センサにより発見できた円柱の数を掃引率としてスワームロボットの性能評価を行う．

N ∈ {5, 10, 15, 20} と変化させて実験を行う．タスクはすべてのターゲットを発見するか，3600 秒 (60 分) 経過した場合に終了とする．各実験の試行は各ロボットの初期姿勢を変えて 50 回行う．

5.2

実験設定

本スワームロボットのタスクは，所定の時間内にできる

5.3

実験結果

限り多くのターゲットを見つけ，ネットワークを介して基図 5 に R = 1.0 の場合の Lα を用いた結果を示す．各 N地局にその発見情報を送信することである．したがって，に関して，α を変えた場合の時間経過に対する掃引率を示

ターゲットの発見時には発見したロボットと基地局はネッしている．α ≤ 1.8 の範囲では α の値が増加すると掃引率

トワークを介し，連結されている必要がある．また，発見も増加している．1.9 ≤ α の範囲では α の値が増加すると情報を送信されたターゲットは環境から取り除かれるもの掃引率は低下する．α に関する性能の優劣は時間経過に対とする．

しほぼ変わることはない．図 6 に R = 1.0 の場合の (N, α)の各組合せに関するタスク終了時における掃引率を示す．

- 0308 -

1.0

1.0

α=0.8
α=1.1
α=1.3
α=1.5
α=1.8
α=1.9
α=1.99Sweeping rate

0.8
0.7
0.6
0.5

0.9
0.8
Sweeping rate

0.9

0.4
0.3

0.7
0.6
0.5
0.4
0.3

0.2

0.2

0.1

0.1
0.0
0.8

0.0
0100000

200000
Step300000

N=5N=10
N=15
N=20
1.0

1.2

1.4α

1.6

1.82.0(a) N = 5
1.0
0.9
0.8Sweeping rate

Fig. 6: Average sweeping rate for each α and N with
R = 1.0 for Lα

α=0.8
α=1.1
α=1.3
α=1.5
α=1.8
α=1.9
α=1.990.7
0.60.5

上述の傾向に加えて，N が増加すると掃引率が増加することが確認できる．

0.4

つぎに，Lα=1.8 ，Lapp ，標準正規分布 (N (0, 1)) を用い0.3た場合の比較を図 7(R = 1.0) に示す．時間経過に対し

0.2

Lapp が最も掃引率が高く，ついで Lα=1.8 ，N (0, 1) の順と0.1なる．とくに Lapp の立ち上がりがよい．N が増加するほ0.00100000

200000
Step300000

ど，掃引率の立ち上がり・最終的な収束値ともに良い性能を示す．N = 20 の場合には最終的な収束値に確率分布間(b) N = 10の差はほとんどみられない．
1.0以上の結果より，R = 1.0 の場合には N が大きい方がSweeping rate

0.90.8

良い性能を示し，Lapp ((3) 式) を用いたレヴィフライトが0.7

掃引スピード・掃引率ともに最も良い性能を示すことを確

0.6

認した．つまり，短距離および長距離の移動頻度がそれぞ

0.5

α=0.8
α=1.1
α=1.3
α=1.5
α=1.8
α=1.9
α=1.99

0.4
0.3
0.2
0.1
0.0
0100000

200000Step

れに大きい確率分布が支持されたということになる．また，Lapp の立ち上がりがよいことは初期位置に対する遠方だけではなく，近場の探索にも有効であることを示している．

R = 0.5 および R = 0.2 についても，同様の傾向を確認した (図 8, 9) 1 ．ただし，R の値が減少すると，掃引率は300000低下する．これは任意のロボットがターゲットを発見した(c) N = 15としても，基地局までの連結性が保たれていない場合，発1.0

見ターゲットとしてカウントされないためである．とくに

0.9

R = 0.2 のときには掃引率が 1 になることはなかった．

Sweeping rate

0.8
0.7
0.6
0.5

6.

α=0.8
α=1.1
α=1.3
α=1.5
α=1.8
α=1.9
α=1.99

0.4
0.3
0.2
0.1
0.0
0100000

200000
Step本稿では，スワームロボットネットワークによる掃引作業を扱った．本テスクでも，レビィフライトの性能がランダムウォークよりも優位であった．また，文献 [13] で提案300000

されているレヴィフライトの式を用いた場合の性能が文献(d) N = 20

Fig. 5: Average sweeping rate for each time step with
R = 1.0 for Lα

結言[11] で提案されている式を用いた性能よりも優れていることを確認した．これらの結果において，無線の連結性を満
1 R = 0.5, N = 10, 15 の L に関しては最も最終掃引率が良かった
α
α = 1.7 の結果を示している．

- 0309 -たし，ロボット台数が多ければ，掃引作業において良い性1.0能を示すことを確認した．障害物回避行動が機能している

0.9
0.8

士が密集する状態が散見された．効率改善のため，環境の0.7

Sweeping rate

ためデッドロックに陥ることはないが，探索過程で個体同疎な領域への早期展開を可能にする機構を開発したい．

参考文献

0.6
0.5
0.4
0.3
Lapp
Lα=1.8N(0,1)

0.2
0.0
0100000

200000
Step300000(a) N = 5
1.00.9Sweeping rate

0.8
0.7
0.6
0.5
0.40.3Lapp
Lα=1.8N(0,1)

0.2
0.1
0.0
0100000

200000
Step300000(b) N = 10
1.00.9Sweeping rate

0.8
0.7
0.6
0.5
0.40.3Lapp
Lα=1.8N(0,1)

0.2
0.1
0.00100000

200000
Step300000(c) N = 15
1.0
0.9
0.8
Sweeping rate

[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,Springer-Verlag 2008.
[3] “スワーム：群れの創発的挙動生成”，計測と制御,Vol.52. No.3, pp.179–276, 2013.
[4] Sahin, E., “Swarm Robotics: From Sources ofInspiration 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.,
Hsiao-Hwa, C., “Connectivity, Coverage and Placement in Wireless Sensor Networks,” Sensors, Vol.9,
No.10, pp.7664–7693, 2009.
[7] 西口晃央，片田喜章，“パーコレーション理論を用いたスワームロボットネットワークの連結性―通信距離とロボット数に関する考察―”，ロボティクス・メカト
ロニクス講演会’14, 講演論文集 CD-ROM, 2A2-X06,
2014.
[8] 片田喜章，西口晃央，森脇和也, 渡壁亮介, “レヴィフライトを用いたスワームロボットネットワークのターゲット探索”, ロボティクス・メカトロニクス講演会’15, 講演論文集 CD-ROM, 2A1-K06, 2015.
[9] Katada, Y., Nishiguchi, A., Moriwaki, K. andWatakabe, R, ”Swarm Robotic Network Using
Levy Flight in Target Detection Problem”, Artiﬁcial Life and Robotics, Volume 21, Issue 3, pp.295–301, 2016.
[10] Lévy, P., “Theorie de l’Addition des VeriablesAleatoires”, Gauthier-Villars, 1937.
[11] 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.
[12] 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.
[13] 小山英朗, 生天目章, ”Random Walk と Levy Flightに基づく探索方法の比較”, 電子情報通信学会技術研究報告. AI, 人工知能と知識処理, Vol.107, No.523,pp.19–24, 2008.
[14] Buldyrev, S. V., Goldberger, A. L., Havlin, S., Simons, M., Stanley, H. E., “Generalized Levy-walkModel for DNA Nucleotide Sequences”, Physicalreview. Vol.47, No.6, pp.4514–4523, 1993.
[15] Brooks, R., “A Robust Layered Control System fora Mobile Robot”, IEEE Journal of Robotics andAutomation, Vol.2, No.1, pp.14–23, 1986.
[16] 江沢昌紀，福本裕介，斉藤雄樹，鳥毛明，小方博之, “掃引ロボットの掃引アルゴリズムの分析”, ロボティク
ス・メカトロニクス講演会’14 講演論文集, 2P1-L2-8,
2004.

0.1

0.7
0.6
0.5
0.4
0.3
Lapp
Lα=1.8N(0,1)

0.2
0.1
0.00100000

200000Step

300000(d) N = 20

Fig. 7: Average sweeping rate for each time step with
R = 1.0 for each probability distribution- 0310 -1.0

0.9

0.9

0.8

0.8

0.7

0.7

Sweeping rate

Sweeping rate

1.0

0.6
0.5
0.4
0.3
Lapp
Lα=1.8N(0,1)

0.2
0.1

Lapp
Lα=1.8N(0,1)

0.6
0.5
0.4
0.3
0.2
0.1

0.0

0.0
0100000

200000Step

3000000100000

1.0

1.0

0.9

0.9

0.8

0.8

0.7

0.7

0.6
0.5
0.4
0.3
Lapp
Lα=1.7N(0,1)

0.2
0.1

Lapp
Lα=1.8N(0,1)

0.6
0.5
0.4
0.3
0.2
0.1

0.0

0.00100000

200000Step

3000000100000

1.0

1.0

0.9

0.9

0.8

0.8

0.7

0.7

0.6
0.5
0.40.3Lapp
Lα=1.7N(0,1)

0.2
0.1

200000Step

300000(b) N = 10

Sweeping rate

Sweeping rate(b) N = 10Lapp
Lα=1.8N(0,1)

0.6
0.5
0.4
0.3
0.2
0.1

0.0

0.0
0100000

200000Step

3000000100000(c) N = 15
1.0

1.0

0.9

0.9

0.8

0.8

0.7

0.7

0.6
0.5
0.4
0.3
Lapp
Lα=1.8N(0,1)

0.2
0.1

200000Step

300000(c) N = 15

Sweeping rate

Sweeping rate

300000(a) N = 5

Sweeping rate

Sweeping rate(a) N = 5200000
StepLapp
Lα=1.8N(0,1)

0.6
0.5
0.4
0.3
0.2
0.1

0.0

0.0
0100000

200000Step

3000000100000

200000Step

300000(d) N = 20(d) N = 20

Fig. 8: Average sweeping rate for each time step with

Fig. 9: Average sweeping rate for each time step with

R = 0.5 for each probability distribution

R = 0.2 for each probability distribution- 0311 -