䢴䣃䢳䢯䣍䢲䢸

レヴィフライトを用いたスワームロボットネットワークのターゲット探索
Swarm Robotic Network Using Lévy Flight in Target Detection Problem○片田喜章（摂南大）
森脇和也（摂南大）

西口晃央（摂南大）
渡壁亮介（摂南大）

Yoshiaki KATADA, Setsunan University, katada @ ele.setsunan.ac.jp
Akihiro NISHIGUCHI, Setsunan University
Kazuya MORIWAKI, Setsunan University
Ryosuke WATAKABE, Setsunan University
One approach in swarm robotics is homogeneous system which is embedded with sensing,computing, mobile and communication components. In this study, a target detection problem,
which is one of navigation problems, was employed. Once a robot detects a target, robots
immediately communicate with a base station via intermediate relay robots due to the multi-hoptransmission of wireless communication. Therefore, it is important to take connectivity of thenetwork into account. This study investigates the performances of the two kinds of random walkalgorithm in navigation while loosely ensuring connectivity of the robotic network based on ourprevious study.
Key Words: Swarm Robotics, Wireless Sensor Networks, Target Detection Problem, Lévy Flight1

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

2スワームロボット構成

本研究では, 左右二輪独立駆動型の移動ロボットを採用する.
図 1 の台車 (DFRobot 社製:直径 170mm, 高さ 75mm) に，距離センサ (赤外線:前方に 4 個)，ターゲット検出センサ (赤外線:両端に 2 個)，マイクロコントローラ (Arduino)，モータドライバ，無線通信装置 (XBee) を搭載する. 赤外線センサの計測可能距離は約 200mm である. 駆動装置としてギヤつきの DC モータ 2 個を採用し，モータドライバを介しマイコンから制御する．無線通信装置 XBee は Zigbee 規格であり，アドホックネットワークを構成し，マルチホップ通信が可能であるため，本研究で扱うタスクに適することから採用している．各ロボットに搭載する XBeeは rooter に設定する．また，本研究ではターゲットとして取扱いが容易なことから，ロボカップジュニア・サッカーに使用される赤外線発光ボール (直径 74mm) を使用する1 ．
1 波長が異なるため距離センサが発する赤外線とは識別可能である．

䣐䣱䢰䢢䢳䢷䢯䢴䢢䣒䣴䣱䣥䣧䣧䣦䣫䣰䣩䣵䢢䣱䣨䢢䣶䣪䣧䢢䢴䢲䢳䢷䢢䣌䣕䣏䣇䢢䣅䣱䣰䣨䣧䣴䣧䣰䣥䣧䢢䣱䣰䢢䣔䣱䣤䣱䣶䣫䣥䣵䢢䣣䣰䣦䢢䣏䣧䣥䣪䣣䣶䣴䣱䣰䣫䣥䣵䢮䢢䣍䣻䣱䣶䣱䢮䢢䣌䣣䣲䣣䣰䢮䢢䣏䣣䣻䢢䢳䢹䢯䢳䢻䢮䢢䢴䢲䢳䢷䢴䣃䢳䢯䣍䢲䢸䢪䢳䢫探索アルゴリズム

3

本研究でははじめにで述べたようにターゲット探索を扱う．探索実行以前に環境に対する知識が全くない場合を想定する．この場合の一般的な探索行動としてランダムウォークがある．ランダムウォークの中でもブラウン運動として扱われるものが一般的である．一方，ランダムウォークの 1 つで，移動距離がレビィ分布とよばれる確率分布にしたがう，レビィフライト (Lévy flight[8])が知られている．レビィフライトはターゲットが探索領域に対しまばらに，かつ，ランダムに分布している場合に有効であると言われている．
レビィフライトによる移動距離は以下のべき分布で近似できる．

p(d) ≃ d(1)−αここで，d は移動距離，α は分布の形状を変えるパラメータであり，本研究では文献 [10] に従い α = 1.2 に設定する．図 2 に dが [1, 30] の範囲の (1) 式 (p(d) = d−α , α = 1.2) を示す．

4コントローラ

4.1 SR における制御器の設計手法
SR では，1 節で述べた設計仕様を満たす制御器の設計手法としてサブサンプションアーキテクチャ(SSA)[11] に代表される，環境との相互作用に着目した行動規範型設計とよばれる設計，もしくは，強化学習や進化計算による自動設計 [2] が提案されている．現在，強化学習や進化計算を用いる手法はシミュレーション環境では有効であるが実環境でその動作を保証するのは容易ではない．そのため，SR が本来目指すべき実ロボット志向の研究者の多くは行動型設計を採用している．
SR における行動規範型設計ではロボット間およびロボットと環境の相互作用に着目し, 望ましい群れ行動が獲得されるまでボトムアップ的に個の振舞いを繰り返し調整する．この個の振舞いを記述する表現様式として確率有限状態機械がよく用いられている [1]．一方，上述の SSA ではレイヤ (次節で述べる) を構成するモジュールに拡張有限状態機械が用いられている．本研究でもこの流れにしたがい，スワームロボットネットワークを構成する個の振舞いを記述する表現様式として上述の SSA を採用する．
4.2 SSA のレイヤ構造
図 3 にスワームロボットに実装する SSA のレイヤ構造を示す．
本タスクを実現する SSA は，ターゲット発見情報送信レイヤ・障害物回避レイヤ・ターゲット探索レイヤの 3 層から構成されている．図中の I は抑制を表し，上位のレイヤが活性化する場合，下位のレイヤを抑制することを表している [11]．各レイヤはモジュールの結合により構成されている．
各レイヤの動作を説明する．ターゲット探索レイヤの探索モ
ジュールは後述する探索アルゴリズムにより，直進モジュール・右回転モジュール・左回転モジュールのいずれかに実行指令信号を送る．障害物回避レイヤの障害物検出モジュールは 2 節で述
べた距離センサからの入力値をもとに，左回転もしくは右回転モジュールに実行指令信号を送り，障害物を回避する. ターゲット
発見情報送信レイヤの目標検出モジュールは 2 節で述べた左右いずれかの赤外線センサの出力値がしきい値を上回った場合に停止モジュールと情報送信モジュールに実行指令信号を送る．情報送信モジュールは SR ネットワークを介して基地局へターゲット発見情報を送信する．

4.3

探索アルゴリズムの実装

4.3.1

ランダムウォーク

本稿では以降，レビィフライトと区別するためにブラウン運動をモデルにしたアルゴリズムをランダムウォークとよぶ．ここでは，1 ステップの移動方向が確率的にランダムに決定され，その1 ステップの幅は一定であるものを言う．その実装方法を以下で説明する．
本研究で用いる左右二輪独立駆動型移動ロボットでは，回転を伴う移動（一般的には旋回と言う）において回転方向をランダムにすることと，移動距離を一定にすることを同時に行うことがその構造上難しい．そこで，回転ステップと移動ステップに分けて設定する (図 4)．移動ステップでは，ロボットは左右モータを回転させ前進する (図 3 における直進モジュール)．移動ステップ
における 1 ステップの実行時間は予備実験の結果にもとづいて 6秒に設定した．回転ステップでは，{45, 90, 135}[ °] のうちいず
れかの角度と回転方向（時計回り，反時計回り）をランダムに選択し，あらかじめ測定しておいた，おおよそ，その角度に回転するであろう実行時間でその場で回転する (図 3 における左右回転モジュール)．
ここで，移動ステップと回転ステップの実行方法について，つぎの 2 種類 (RN(2)，RN(6) とよぶ) を設定する．RN(2) は，移動ステップにおける移動ステップ数を 1 とし，移動ステップと回転ステップのどちらを実行するかはランダム（確率 50%）に選択する (図 4(a))．したがって，移動ステップ → 移動ステップなる遷移が可能である．この場合，すべての遷移に対する平均移動ステップ数は 2 となる．RN(6) は，移動ステップにおける移動ステップ数をレビィフライトとの比較のため 6 とし，移動ステップと回転ステップを交互に選択する (図 4(b))．

4.3.2

レビィフライト

レビィフライトでもランダムウォークと同様に移動ステップと回転ステップの 2 つを設定する．レビィフライトの移動ステップ数は 3 節で述べたレビィ分布によって決定される．また，移動ステップと回転ステップを交互に選択する. 本研究では，予備実験の結果から移動ステップにおけるレビィフライトの最大移動ステップ数を 30 に設定する (図 2)．したがって，レビィフライトにおける平均移動ステップ数は 6 となる．ここで略語を LF(6) とする．RN(2)・RN(6) との違いは，LF(6) は移動ステップ数がレビィ分布に従ってさまざまな値をとることにある (図 4(c))．

㉥እ⥺䝉䞁䝃┠ᶆ᳨ฟ

᝟ሗ㏦ಙ
೵Ṇ

0.6㞀ᐖ≀ᅇ㑊䝺䜲䝲

0.2
051015 20
d [step]2530㞀ᐖ≀᳨ฟ

ྑᅇ㌿

㻵ᕥᅇ㌿
䝍䞊䝀䝑䝖᥈⣴䝺䜲䝲

᥈⣴㻵┤㐍
ྑᅇ㌿
ᕥᅇ㌿

Fig.2 Lévy probability distribution

Fig.3 Layer structure of SSA䣐䣱䢰䢢䢳䢷䢯䢴䢢䣒䣴䣱䣥䣧䣧䣦䣫䣰䣩䣵䢢䣱䣨䢢䣶䣪䣧䢢䢴䢲䢳䢷䢢䣌䣕䣏䣇䢢䣅䣱䣰䣨䣧䣴䣧䣰䣥䣧䢢䣱䣰䢢䣔䣱䣤䣱䣶䣫䣥䣵䢢䣣䣰䣦䢢䣏䣧䣥䣪䣣䣶䣴䣱䣰䣫䣥䣵䢮䢢䣍䣻䣱䣶䣱䢮䢢䣌䣣䣲䣣䣰䢮䢢䣏䣣䣻䢢䢳䢹䢯䢳䢻䢮䢢䢴䢲䢳䢷䢴䣃䢳䢯䣍䢲䢸䢪䢴䢫

䝰䞊䝍

0.4
㊥㞳䝉䞁䝃

PDF: p(d)0.8䝍䞊䝀䝑䝖Ⓨぢ᝟ሗ㏦ಙ䝺䜲䝲ᇶᆅᒁavg
1

100(a) RN(2)Success rate [%]80(b) RN(6)

N=10
N=15
N=20604020

移動回転(c) LF(6)0RN(2)

Fig.4 Transition between move phase and rotate phasein navigation
6.1m

70.4m

RN(6)

LF(6)

Navigation algorithm

Fig.6 Success rate for each navigation algorithm

6.3m

DB

2.4m

BCA

6.1m

8.4m

3.7m

6.0m

Fig.7 Environment divided into four areasT
82.8m

Fig.5 Setup for target detection problem (B: base station, T: target)
5

ターゲット探索実験

5.1 実験環境
本実験は摂南大学寝屋川キャンパス 1 号館 6 階の廊下を環境とした (図 5 の黄色部分)．廊下と隣接する部屋としては，製図室・学生実験室などがある．図 5 の右上に各ロボットに搭載した無線通信装置と同じ XBee (coordinator として設定) を PC に接続し，無線通信基地局 (以下，基地局) として設置する．また，図の左下に上述のターゲットである赤外線発光ボールを設置する．
スワームロボットの初期位置は基地局近傍とし，図の右下とする．
本環境の特徴として，ターゲットと基地局の間の見通しが不可能であり，また，直接通信も不可能という点が挙げられる．
5.2 実験設定
本スワームロボットのタスクは，基地局と直接通信が不可能な距離 (約 80m 先) にあるターゲットを見つけ，基地局にその発見情報を送信することである．したがって，タスクの達成にはネットワークの連結性 (ターゲットを発見したロボットと基地局間のマルチホップ通信が可能) を同時に満たす必要がある．本環
境では予備実験の結果，XBee の仕様から算出される通信可能距離 (45m) よりも長い距離 (54m) で通信可能であることがわかった．そこで，環境の長手方向の距離に対する通信可能距離の相対値は 54/82.8 ≃ 0.65 となり，連結性を満たす必要ロボット台数は 20-34 台となる [7]．ただし，文献 [7] では正方形の環境を想定していたことから本環境ではより少ない台数で連結性を満たすと考えられる．そこで，ロボット台数を N ∈ {10, 15, 20} と変化させて実験を行った．タスクはターゲットを発見するか，1800 秒(30 分) 経過した場合に終了とする．探索アルゴリズムとしてランダムウォーク (RN(2)，RN(6)) とレビィフライト (LF(6)) を実装した SSA を採用する．各実験の試行回数は 10 回とする．
5.3 実験結果
表 1 に各探索アルゴリズムを用いて台数を変化させた場合の結果を示す．表中，—はタスクを達成できなかった試行を，averageはタスクを達成した試行のみで計算したスタートからターゲット発見までにかかった平均所要時間を示す．また，図 6 にタスク達成率を示す．RN(2) の N = 10 の場合を除き，RN(2)，RN(6)，LF(6) の順でタスク達成率が高くなっていることがわかる．また，LF(6) のタスク達成率が非常に高い．所要時間でも LF(6) の方が短くなっている．ただし，LF(6) における平均ターゲット発見時間のロボット台数による差は有意ではないことを確認している．
タスク終了時は基地局から全ロボットに無線通信で停止信号を送って実験を終了する．このとき，すべてのロボットの行動を停止することができていたため，タスク達成時およびタスク達成時以外でも連結性が満たされていることを確認できた．

6

考察

スワームロボットネットワークによるターゲット探索において，レヴィフライトを用いた場合のタスク達成率の方が非常に高いという結果を得た (図 6)．これについて 4.3 節で述べたレヴィフラ
イトの特徴という観点から考察する．
図 7 は実験環境を 4 つのエリア（A，B，C，D）に分割した見取り図である．実験を行った試行全てにおいて，それぞれ 1 試行終了時点での，各エリアにおけるロボットの分布割合について平均値を求めた．その結果を図 8 に示す．RN(2) ではエリア Aに約 40%が留まり，エリア C・D における分布割合は両エリアをあわせても 10%ほどである (図 8(a))．つまり，初期位置近傍（エレベータホール）から抜け出せず先に進めていないことがわかる．RN(6) および LF(6) ではエリア C・D にも 20%から 30%のロボットが到着している (図 8(b), 8(c))．以上の結果と，RN(2)のタスク達成率が極端に低いことを考えると，本環境では移動ステップ数が大きい方がタスク達成に有利であることがわかる．
RN(6) と LF(6) を比較すると，RN(6) はエリア B に比較的多くのロボットが分布し，逆に LF(6) ではエリア A にも比較的多くのロボットが分布している．この結果は単にターゲットに近いエリアにより多くのロボットが分布してさえいればよいということではないことを示唆している．図 8 のデータからは，LF(6)が RN(6) よりもタスク達成率が高い理由を導くことはできない．
ロボットの振舞いを観察すると，RN(6) では LF(6) と同様に10%弱ほどのロボットが最終的にエリア D に到着しているが，そこまでにかなりの時間を要した．さらに，移動ステップ数がつねに 6 であるため，ターゲットの近傍に到着するもののターゲットを捉えきれずに通り過ぎてしまう行動が見られた．一方，LF(6)は移動ステップ数がつねに変化するため，エリア D に到着するまでの時間が短く，ターゲット近傍では小さい移動とそれに続く回転によりターゲットを発見できている．

䣐䣱䢰䢢䢳䢷䢯䢴䢢䣒䣴䣱䣥䣧䣧䣦䣫䣰䣩䣵䢢䣱䣨䢢䣶䣪䣧䢢䢴䢲䢳䢷䢢䣌䣕䣏䣇䢢䣅䣱䣰䣨䣧䣴䣧䣰䣥䣧䢢䣱䣰䢢䣔䣱䣤䣱䣶䣫䣥䣵䢢䣣䣰䣦䢢䣏䣧䣥䣪䣣䣶䣴䣱䣰䣫䣥䣵䢮䢢䣍䣻䣱䣶䣱䢮䢢䣌䣣䣲䣣䣰䢮䢢䣏䣣䣻䢢䢳䢹䢯䢳䢻䢮䢢䢴䢲䢳䢷䢴䣃䢳䢯䣍䢲䢸䢪䢵䢫

Table 1 Time to detect the targetalgorithm
number of robots
trial 1
trial 2
trial 3
trial 4
trial 5trial 6
trial 7
trial 8
trial 9trial 10average [s]

7

10
—
—
1537
—
—
—
—
—
1676
—
1606

RN(2)
15
—
1328
—
—
—
—
—
—
—
—
1328

20
—
—
—
—
—
—
—
—
—
1690
1690

10
—
—
—
—
—
—
1594
—
—
—
1594

RN(6)
15
1446
—
—
—
—
1558
1536
—
1537
1708
1557

20
928
1336
—
—
—
—
—
—
—
1352
1205

10
1585
1666
—
1405
891
1031
1248
1135
1148
950
1229

LF(6)
15
650
634
—
1328
1634
1083
1072
1279
1392
815
1099

20
931
1140
—
1017
94911671428—1117
997
1093

おわりに
100
Distribution of the robots [%]本稿では無線通信を用いた SR ネットワークによるターゲット探索実験を行い，探索アルゴリズムとしてレビィフライトが有効であることを確認した．本環境では，初期位置近傍であるエリアA を抜け出ることがタスク達成への第一歩であるが，同時に数台のロボットがエリア A に滞留して連結性を保証する振舞いが見られた．これはあたかも昆虫による，エリア A を巣とする，ターゲットへの採餌行動のようである．
今後，ターゲット発見後のターゲットの位置推定，基地局への集合（帰巣）および，囲いのないオープンな空間への拡張を行っていきたい．

80DCB
A

60
40
200

文献

10[1] Brambilla, M., Ferrante, E., Birattari, M., Dorigo, M., “SwarmRobotics: A Review from the Swarm Engineering Perspective,” Swarm Intelligence, Vol.7, No.1, pp.1-41, 2013.

15
Number of robots

20(a) RN(2)100Distribution of the robots [%][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 of Inspiration toDomains 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.

80DCBA

60
40
2001015
Number of robots

20(b) RN(6)[7] 西口晃央，片田喜章，“パーコレーション理論を用いたスワームロボッ
トネットワークの連結性―通信距離とロボット数に関する考察―”，
ロボティクス・メカトロニクス講演会’14, 講演論文集 CD-ROM,
2A2-X06, 2014.

Distribution of the robots [%]100[8] Lévy, P., “Theorie de l’Addition des Veriables Aleatoires”,
Gauthier-Villars, 1937.
[9] Sutantyo, D., Levi, P., Möslinger, C., Read, M., “CollectiveAdaptive Lévy Flight for Underwater Multi-Robot Exploration,” In Proceedings of 2013 IEEE International Conference
on Mechatronics and Automation, pp.456–462, 2013.
[10] 小山英朗, 生天目章, ”Random Walk と Levy Flight に基づく探索方法の比較”, 電子情報通信学会技術研究報告. AI, 人工知能と知識処理, Vol.107, No.523, pp.19-24, 2008.

80

DCB
A

60
40
20010

[11] Brooks, R., “A Robust Layered Control System for a MobileRobot”, IEEE Journal of Robotics and Automation, Vol.2,No.1, pp.14-23, 1986.

15
Number of robots

20(c) LF(6)Fig.8 Distribution of the robots in each region for thenumber of robots䣐䣱䢰䢢䢳䢷䢯䢴䢢䣒䣴䣱䣥䣧䣧䣦䣫䣰䣩䣵䢢䣱䣨䢢䣶䣪䣧䢢䢴䢲䢳䢷䢢䣌䣕䣏䣇䢢䣅䣱䣰䣨䣧䣴䣧䣰䣥䣧䢢䣱䣰䢢䣔䣱䣤䣱䣶䣫䣥䣵䢢䣣䣰䣦䢢䣏䣧䣥䣪䣣䣶䣴䣱䣰䣫䣥䣵䢮䢢䣍䣻䣱䣶䣱䢮䢢䣌䣣䣲䣣䣰䢮䢢䣏䣣䣻䢢䢳䢹䢯䢳䢻䢮䢢䢴䢲䢳䢷䢴䣃䢳䢯䣍䢲䢸䢪䢶䢫