2P2-F14
レヴィフライトを用いたスワームロボットのターゲット探索―だまし環境における探索性能の検証―

Swarm Robots Using Lévy Flight in Target Detection Problem-Performance of Exploration in Weakly Deceptive Environment-○正 片田喜章 (摂南大)

古谷健太郎（摂南大）

Yoshiaki KATADA, Setsunan University, katada @ setsunan.ac.jp
Kentaro FURUTANI, Setsunan University
This study tackles the task for swarm robotics where robots explore the environment todetect a target. Once a robot detects a target, robots immediately communicate with a base station via intermediate relay robots due to the multi-hop transmission of wireless communication.
In our previous results, we confirmed that Lévy flight outperformed the usual random walk for
exploration strategy in real swarm robots experiment. This study investigated the performanceof Lévy flight on a target detection problem in a weakly deceptive environment through a series of real swarm robots experiments. The results suggest that the deceptive environment canweaken the performance of exploration as well as the increase of the number of robots improves
the performance in the environment.
Key Words: Swarm Robotics, Lévy Flight, Target Detection Problem
1

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

SR では，これまでに空間的な組織化行動・探索行動・集団的意思決定といったタスクが取り扱われてきた [1]．我々の研究グループでは，探索行動の中で協調探索に分類される，ターゲット探索をタスクとして取り扱ってきた．無線ネットワークによって通信可能な複数ロボットを用いてターゲットの探索を行い，あるロボットがターゲットを発見すると，その情報は無線ネットワー
クを介して基地局に送られる [5]．このとき，ターゲットを検出したロボットから基地局までは無線ネットワークによって連結 [6]されている必要がある．以降，SR により構成される無線ネットワークを SR ネットワークとよぶ．
我々の研究グループでは，スワームロボットネットワークにおける基地局と各ロボット間の無線通信の連結性 [6] を保証する通信可能距離とロボット台数の関係について，パーコレーション理論にもとづく計算機実験を行った [7][8]．さらに，SR ネットワー
クの連結性を考慮したロボットの台数と無線通信装置を使用し，実環境においてターゲット探索の実機実験を行っている [9]．文献 [9] では，探索アルゴリズムとしてランダムウォークとレヴィフライト [10] を実装し，ターゲット探索におけるタスク達成率を比較した．その結果，移動距離が一定なランダムウォークに対し，移動距離が可変なレヴィフライトが圧倒的に優位であることを確認した．また，文献 [14] ではレヴィフライトの移動距離を決定する確率密度関数の種類やそのパラメータの効果を複数ターゲッ
ト探索を意識した掃引作業に関する計算機実験において調べている．本稿では，文献 [9] で実験を行った環境を拡張し，レヴィフライトを用いた SR のターゲット探索性能を実機実験において検証する．

レヴィフライト

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

∫ ∞α1e−γq cos(wq)dq, γ > 0, w ∈ R
Lα,γ (w) =π 0(1)ここで，γ は分布の大きさを決めるパラメータであり，α は分布の形状を決めるパラメータで 0 < α < 2 の値をとる．本確率密度関数は w = 0 に関して対称であり，無限大の 2 次モーメントをもつことが特徴である．
計算機実験において移動ロボットにレヴィフライトを実装した研究として文献 [13] がある．ここでは，レヴィフライトはターゲットが探索領域に対しまばらに，かつ，ランダムに分布している場合に有効であると報告している．文献 [13] では，w ≫ 1 としてレヴィ分布を近似した次式を移動距離の決定に使用している．

L(w) ∝ w−α(2)ここで，α は分布の形状を変えるパラメータである．文献 [14] では文献 [13] に従い α = 1.2 に設定した (2) 式がレヴィ分布に従う確率変数を生成する他のアルゴリズムに対し探索性能が良いことが報告されている．そこで，本研究でも (2) 式を移動距離の決定に採用する．
移動方向に関しては，一様分布に従うものとして扱う．

3スワームロボット構成

本研究では, 左右二輪独立駆動型の移動ロボットを採用する (図1). 台車 (直径 170mm, 高さ 75mm) に，距離センサ (赤外線:前方に 4 個)，ターゲット検出センサ (赤外線:両端に 2 個)，マイクロコントローラ (Arduino)，モータドライバ，無線通信装置 (XBee)を搭載する. 距離センサの計測可能距離は約 300mm，ターゲッ
ト検出センサの計測可能距離は約 200mm である．駆動装置とし

No. 18-2 Proceedings of the 2018 JSME Conference on Robotics and Mechatronics, Kitakyushu, Japan, June 2-5, 2018
2P2-F14(1)移動回転

Fig.3 Transition between move phase and rotate phasein navigation

B

6.1m

6.3m

3.7m

T

70.4m
6.0m 2.4m

8.4m

6.1m

82.8m
(a) common environment㊥㞳䝉䞁䝃㞀ᐖ≀ᅇ㑊䝺䜲䝲
㞀ᐖ≀᳨ฟ䝍䞊䝀䝑䝖᥈⣴䝺䜲䝲

┤㐍

3.7m

1.1m
B

(b) deceptive environment

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

ྑᅇ㌿

㻵ᕥᅇ㌿

Fig.2 Layer structure of SSAてギヤつきの DC モータ 2 個を採用し，モータドライバを介しマイコンから制御する．無線通信装置 XBee は Zigbee 規格であり，アドホックネットワークを構成し，マルチホップ通信が可能である．各ロボットに搭載する XBee は router に設定する．また，本研究ではターゲットとして取扱いが容易なことから，ロボカップジュニア・サッカーに使用される赤外線発光ボール (直径74mm) を使用する1 ．

4

コントローラ

4.1 サブサンプションアーキテクチャのレイヤ構造
図 2 にスワームロボットに実装するサブサンプションアーキテクチャ(SSA)[15] のレイヤ構造 [9] を示す．本研究で扱うタスクを実現する SSA は，ターゲット発見情報送信レイヤ・ 障害物回避レイヤ・ターゲット探索レイヤの 3 層から構成される．図中のI は抑制を表し，上位のレイヤが活性化する場合，下位のレイヤを抑制することを表している [15]．各レイヤはモジュールの結合により構成されている．
各レイヤの動作を説明する．ターゲット探索レイヤの探索モ
ジュールは後述する探索アルゴリズムにより，直進モジュール・右回転モジュール・左回転モジュールのいずれかに実行指令信号を送る．障害物回避レイヤの障害物検出モジュールは 3 節で述
べた距離センサからの入力値をもとに，左回転もしくは右回転モジュールに実行指令信号を送り，障害物を回避する. ターゲッ
ト発見情報送信レイヤの目標検出モジュールは 3 節で述べた左右いずれかのターゲット検出センサの出力値がしきい値を上回った場合に停止モジュールと情報送信モジュールに実行指令信号を送る．情報送信モジュールは SR ネットワークを介して基地局へターゲット発見情報を送信する．
4.2 探索アルゴリズムの実装
本研究で用いる左右二輪独立駆動型移動ロボットの仕様では，回転を伴う移動（一般的には旋回と言う）において回転方向をラ1 波長が異なるため距離センサが発する赤外線とは識別可能である．

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

5ターゲット探索実験

5.1 実験環境
本実験は摂南大学寝屋川キャンパス 1 号館 6 階の廊下を環境とした (図 4 の黄色部分)．廊下と隣接する部屋としては，製図室・学生実験室などがある．文献 [9] では図 4(a) において実験を行った．本研究では，さらに，図 4(a) の環境にターゲットが存在しない方向にもエリアを追加した環境 (図 4(b)) でも実験を行う．以降，前者を通常環境，後者をだまし環境とよぶ．図 4 の右上に各ロボットに搭載した無線通信装置と同じ XBee (coordinator として設定) を PC に接続し，無線通信基地局 (以下，基地局) として設置する．また，図の左下にターゲットとして 3 節で述べた赤外線発光ボールを設置する．スワームロボットの初期位置は基地局近傍とし，図の右下とする．本環境の特徴として，ターゲットと基地局の間の見通しが不可能であり，また，直接通信も不可能という点が挙げられる．
5.2 実験設定
本スワームロボットのタスクは，基地局と直接通信が不可能な距離 (約 80m 先) にあるターゲットを見つけ，基地局にその発見情報を送信することである．したがって，タスクの達成にはネットワークの連結性 (ターゲットを発見したロボットと基地局間のマルチホップ通信が可能) を同時に満たす必要がある．本環
境では予備実験の結果，XBee の仕様から算出される通信可能距

No. 18-2 Proceedings of the 2018 JSME Conference on Robotics and Mechatronics, Kitakyushu, Japan, June 2-5, 2018
2P2-F14(2)

6.1m

7.2m

6.3m

82.8m

ྑᅇ㌿

㻵
ᕥᅇ㌿

᥈⣴

T

6.0m 2.4m

೵Ṇ8.4m᝟ሗ㏦ಙᇶᆅᒁ┠ᶆ᳨ฟ䝰䞊䝍

㉥እ⥺
䝉䞁䝃

䝍䞊䝀䝑䝖Ⓨぢ᝟ሗ㏦ಙ䝺䜲䝲

70.4m
5.3m

6.1m

Fig.1 Setup for swarm mobile robots

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

10750
—
1690
792
—
604
1095
999
767
845
943

common
15
20
1404
1115
1113
643
924
590
1223
897
1453
1049
1021
1614
1247
1218
1381
929
1179
1106
1273
1480
1222
1064

25
1706
892
780
1369
758
1583
1360
1349
816
1351
1196

100

deceptive
15
20
1655
1045
1146
994
— 1377
1120
869
1455
627
— 1104
1167
791
610
1180
1685
—
1090
1503
1241
1054

25
1259
—
1012
1419
847
1470
1477
835
1660
903
1209

commondeceptive

80

1200

Success rate [%]Time to detect the target [s]

1300

10
—
999
1041
—
928
1263
—
1031
1556
986
1115

1100

1000

60
40
20

commondeceptive

900
10

15
20
Number of robots

025

10

15
20
Number of robots

25

Fig.5 Average time to detect a target for each environment

Fig.6 Success rate for each environment

離 (45m) よりも長い距離 (54m) で通信可能であることがわかっている．そこで，環境の長手方向の距離に対する通信可能距離の相対値は 54/82.8 ≃ 0.65 となり，環境の縦横比を考慮すると連結性を満たす必要ロボット台数は 11-12 台と予測できる [8]．また，本研究では通常環境とだまし環境でレヴィフライトの探索性能を検証することを目的としている．そこで，ロボット台数をN ∈ {10, 15, 20, 25} と変化させて実験を行った．タスクはターゲットを発見するか，1800 秒 (30 分) 経過した場合に終了とする．探索アルゴリズムとしてレヴィフライトを実装した SSA(図2) を採用する．各実験の試行回数は 10 回とする．

前節のスワームロボットによるターゲット探索において，だまし環境であっても N = 20, 25 の場合のタスク達成率は，通常環境の N = 10 の場合のタスク達成率よりも高いという結果を得た(図 6)．これについて以下で考察する．
図 7 は実験環境を 7 つのエリア（A，B，C，D, X, Y, Z）に，分割した見取り図である (通常環境は 4 つのエリア（A，B，C，D) のみで構成される)．実験を行った試行全てにおいて，それぞれタスク終了時点での各エリアにおけるロボットの分布割合について平均値を求めた．その結果を図 8 に示す．だまし環境における N = 20, 25 の場合のエリア A・B・C・D における分布割合の合計 (図 8(b)) は，通常環境における N = 10 の場合のエリ
ア A・B・C・D における分布割合の合計 (図 8(a)) よりも大きくなっている．つまり，エリア X・Y・Z に留まるロボットがいても，エリア A・B・C・D に十分な数のロボットが供給されていればタスク達成率は上がると推測される．一方，だまし環境における N = 20, 25 の場合のエリア A・B・C・D における分布割合の合計は，通常環境における N = 15 の場合のエリア A・B・C・D における分布割合の合計よりも大きくなっている．しかし，だまし環境における N = 20, 25 の場合のタスク達成率 (90%) は通常環境における N = 15 の場合のタスク達成率 (100%) には及んでおらず，上記の推測を完全に支持する結果にはなっていない．
だまし環境における N = 25 の場合のエリア A・B・C・D における分布割合の合計と通常環境における N = 20 の場合のエリア65.3 実験結果
表 1 に各台数を用いた場合の結果を示す．表中，—はタスクを達成できなかった試行を，average はタスクを達成した試行のみで計算したスタートからターゲット発見までにかかった平均所要時間を示す．また，図 5 に平均ターゲット発見時間を，図 6 にタスク達成率を示す．平均ターゲット発見時間に関して，通常環境の N = 10 のときに 15 分程度で発見しているが，それ以外ではいずれも 20 分程度となっている．N ≥ 15 では通常環境とだまし環境で大きな差はみられない (図 5)．
通常環境では N ≥ 15 でタスク達成率が 100[%] であった．だまし環境でも台数を多くするとタスク達成率が高くなっている．だまし環境であっても N = 20, 25 の場合では，通常環境の N = 10の場合のタスク達成率よりも高い値を示す．これについては次節で考察する．

ZD考察YCXB

Fig.7 Environment divided into seven areas
No. 18-2 Proceedings of the 2018 JSME Conference on Robotics and Mechatronics, Kitakyushu, Japan, June 2-5, 2018
2P2-F14(3)ADistribution of the robots

25207DCB
A

おわりに

本稿では，文献 [9] で実験を行った環境を拡張した，“だまし環境” において，レヴィフライトを用いた SR のターゲット探索性能を実機実験において検証した．だまし環境では，タスク達成率が低下することを確認した．だまし環境であってもロボット台数N = 20, 25 の場合のタスク達成率は，通常環境の N = 10 の場合のタスク達成率よりも高くなることを確認した．また，タスクを達成した試行では 15 台以上のロボットを使用していればターゲット発見時間に大きな差は見られないことを確認した．
今後，だまし度合いがより大きい環境で実験を行なっていきたい．また，6 節で述べた機能拡張に関しても検討していきたい．

15105

参考文献
[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.

010

Distribution of the robots

2520151520
Number of robots(a) common environment

25[2] Trianni, V., Evolutionary Swarm Robotics, Springer-Verlag
2008.
[3] “スワーム：群れの創発的挙動生成”，計測と制御, Vol.52. No.3,pp.179–276, 2013.

ZYXDCBA[4] Şahin, E., “Swarm Robotics: From Sources of Inspiration
to Domains of Application,” Swarm Robotics. SR 2004. Lecture Notes in Computer Science, Volume 3342/2005, pp.10–20,
2005.
[5] 杉山久桂，辻岡哲夫，村田正，“ネットワーク化された群ロボットにおける被災者発見システム”，情報処理学会論文誌，Vol.46, No.7,pp.1777–1788, 2005.

10[6] Li, J., Andrew, L.L.H., Foh, C. H., Zukerman, M., Chen,H.H., “Connectivity, Coverage and Placement in Wireless Sensor Networks,” Sensors, Vol.9, No.10, pp.7664–7693, 2009.

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

0101520
Number of robots(b) deceptive environment

25Fig.8 Distribution of the robots in each area for the number of robots

A・B・C・D における分布割合の合計の関係に関しても同様のことがいえる．上記の推測に関してさらに試行回数を増やした統計的な検証が必要であると考える．また，本実験設定では，だまし環境で追加したエリア (X・Y・Z) は，基地局からターゲット方向を見たときに右側にのみ存在している．今後，左側にも同様のエリアを追加して実験を行う予定である．
ロボットの振舞いを観察すると，追加したエリア (X・Y・Z) に進入したロボットは，これらのエリアから出るときには大別してターゲット方向と基地局方向のどちらかに進んでいく．提案している探索アルゴリズムでは各ロボットは環境に対する大域情報を持たないので，通常環境であってもロボットが基地局方向に戻ってくることは起こりうる．しかし，だまし環境では，ある程度時間が経過し，各ロボットが環境に分散した状態でこれが起こる．
このためにターゲット方向，もしくは，未探索方向にロボット群を押し出すようなロボット間の相互作用が起こりにくいのではないかと思われる．本アプローチは探索の効率を極端に求めるものではないが，探索アルゴリズムに既に探索した領域を避けるような機能を追加することは検討の価値があると思われる．

[8] 片田喜章，“通信距離とノード数に対する無線通信ネットワークの連結性”，計測自動制御学会 システム・情報部門学術講演会 2015
講演論文集, pp.1135–1138, 2015.
[9] Katada, Y., Nishiguchi, A., Moriwaki, K. and Watakabe, R.,“Swarm Robotic Network Using Lévy Flight in Target Detection Problem,” Artificial Life and Robotics, Vol.21, Issue 3,pp.295–301, 2016.
[10] Lévy, P., “Theorie de l’Addition des Veriables Aleatoires”,
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., Yao, X., “Evolutionary Programming Using Mutations Based on the Lévy Probability Distribution”, IEEETransactions 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] 片田喜章，“レヴィフライトを用いたスワームロボットネットワー
クによる探索 −掃引作業に関する計算機実験を用いた検証”, 計測
自動制御学会論文集, Vol.54，No.1, pp.22–30, 2018.
[15] Brooks, R., “A Robust Layered Control System for a MobileRobot”, IEEE Journal of Robotics and Automation, Vol.2,
No.1, pp.14–23, 1986.

No. 18-2 Proceedings of the 2018 JSME Conference on Robotics and Mechatronics, Kitakyushu, Japan, June 2-5, 2018
2P2-F14(4)