䢳䣃䢳䢯䢲䢷䣣䢶

スワームロボットネットワークのターゲット探索―個体の損失に対する頑健性の検証―

Swarm Robotic Networks in Target Detection Problem-Fault Tolerance for the Loss of Individuals○

片岡光留 (摂南大)
正谷島僚馬（摂南大）

片田喜章（摂南大）

Hikaru KATAOKA, Setsunan University
Yoshiaki KATADA, Setsunan University, katada @ setsunan.ac.jp
Ryoma TANISHIMA, Setsunan University
One approach in swarm robotics is homogeneous system which is embedded with sensing,computing, mobile and communication components. Such a system enhances the potential to
be robust, scalable and flexible. In our previous study, we confirmed that Lévy flight is usefulfor an exploration strategy of swarm robotic network in a target detection problem. This study
investigates the robustness of swarm robotic network in the target detection problem, whererobustness is the ability to cope with the loss of individuals.
Key Words: Swarm Robotics, Fault Tolerance, Wireless Communication Networks, Target DetectionProblem, Lévy Flight

1

はじめに

2

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

SR では，これまでに分散協調的な探索，搬送，囲い込み，形態形成，隊列の形成・維持といったタスクが取り扱われてきた [1]．
本研究では，協調探索に分類される，ターゲット探索 [5] をタス
クとして取り扱う．ここでは，無線ネットワークによって通信可能な複数ロボットを用いてターゲットの探索を行う．あるロボッ
トがターゲットを発見すると，その情報は無線ネットワークを介して基地局に送られる．このとき，ターゲットを検出したロボットから基地局までは無線ネットワークによって「連結 [6]」されている必要がある．以降，SR により構成される無線ネットワー
クを SR ネットワークとよぶ．
我々の研究グループでは，粒子のつながり方を扱うパーコレーション理論に基づき，無線通信可能距離に対して群れロボットの密度に SR ネットワークの連結性を満たす臨界値が存在することを計算機実験で確認している [7]．さらに，SR ネットワークの連結性を考慮したロボットの台数と無線通信装置を使用し，実環境においてターゲット探索の実機実験を行っている [8]．文献 [8] では，探索アルゴリズムとしてランダムウォークとレヴィフライト
[9] を実装し，ターゲット探索におけるタスク達成率を比較した．
その結果，移動距離が一定なランダムウォークに対し，移動距離が可変なレヴィフライトが圧倒的に優位であることを確認した．
また，文献 [10] ではレヴィフライトの移動距離を決定する確率密度関数のパラメータの効果をターゲット探索に関する計算機実験において調べている．本稿では，先に述べた特性の 1 つである頑健性，つまり，個体の損失に対処するスワームシステムとしての能力を計算機・実機実験において検証する．

レヴィフライト

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

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

ここで，γ は分布の大きさを決めるパラメータであり，α は分布の形状を決めるパラメータで 0 < α < 2 の値をとる．(1) 式は
α = 1 のときにコーシー分布，α → 2 のときにガウス分布と等価になる．この確率密度関数は w = 0 に関して対称であり，無限大の 2 次モーメントをもつことが特徴である．本研究では文献[11, 12] に従い，γ = 1 とする．
レヴィ分布に従う確率変数を生成するアルゴリズムが提案されている [11]．以下にその生成式を示す [11, 12]．

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

ここで，x と y はガウス分布に従う独立な確率変数であり，k(α)と c(α) は α に依存し，(α, k, c) の各値の組合せは文献 [11] で与えられている．
第 4.2 節で詳細を述べるが，本研究では (2) 式を用いて移動ロボットの直進移動時間を決定する．したがって，(2) 式の w ≥ 0の範囲だけを必要とするため，(2) 式中の x を |x| として計算する．これにより，(1) 式の値は w > 0 の範囲で理論上 2 倍になる．
文献 [8] では，移動距離の決定に使用される確率密度関数は(1) 式の近似を用いていたが，本研究では近似式ではなく，文献[10] で得られた知見を参考に，(2) 式 (ただし，α = 0.8, k =0.795112, c = 2.483) を用いて移動距離を決定する．

䣐䣱䢰䢢䢳䢸䢯䢴䢢䣒䣴䣱䣥䣧䣧䣦䣫䣰䣩䣵䢢䣱䣨䢢䣶䣪䣧䢢䢴䢲䢳䢸䢢䣌䣕䣏䣇䢢䣅䣱䣰䣨䣧䣴䣧䣰䣥䣧䢢䣱䣰䢢䣔䣱䣤䣱䣶䣫䣥䣵䢢䣣䣰䣦䢢䣏䣧䣥䣪䣣䣶䣴䣱䣰䣫䣥䣵䢮䢢䣛䣱䣭䣱䣪䣣䣯䣣䢮䢢䣌䣣䣲䣣䣰䢮䢢䣌䣷䣰䣧䢢䢺䢯䢳䢳䢮䢢䢴䢲䢳䢸䢳䣃䢳䢯䢲䢷䣣䢶䢪䢳䢫移動回転

Fig.3 Transition between move phase and rotate phasein navigation

᝟ሗ㏦ಙ
೵Ṇ

㊥㞳䝉䞁䝃

㞀ᐖ≀ᅇ㑊䝺䜲䝲
㞀ᐖ≀᳨ฟ

ྑᅇ㌿

㻵
ᕥᅇ㌿
┤㐍䝍䞊䝀䝑䝖᥈⣴䝺䜲䝲᥈⣴ᇶᆅᒁ䝍䞊䝀䝑䝖Ⓨぢ᝟ሗ㏦ಙ䝺䜲䝲┠ᶆ᳨ฟ

䝰䞊䝍

㉥እ⥺
䝉䞁䝃

Fig.1 Setup for swarm mobile robots

Fig.4 Setup for computer simulation

ྑᅇ㌿

㻵ᕥᅇ㌿

送る．情報送信モジュールは SR ネットワークを介して基地局へターゲット発見情報を送信する．

Fig.2 Layer structure of SSA
3

スワームロボット構成

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

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

コントローラ5

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

ターゲット探索計算機実験

5.1 実験環境
文献 [10] の設定と同様に，壁に囲まれた正方形を実験環境とする (図 4)．図 4 の左下に無線通信基地局 (以下，基地局) の設置を仮定する．本実験は計算機実験のため，実際には基地局との通信を行わないが， SR ネットワークの連結性のチェックに基地局の位置情報が必要となる．また，図 4 の右上 (基地局の対角線上) に 3 節で述べたターゲットである球を設置する．スワームロ
ボットの初期位置は基地局近傍とし，図 4 の左下とする．
5.2 ロボットモデル
本計算機実験では，3 節で述べた移動ロボットを動力学シミュ
レータ ODE を用いてモデル化する．センサの計測可能距離も 3節と同じ値に設定する．
5.3 実験設定
本スワームロボットのタスクは，所定の時間内にターゲットを見つけ，ネットワークを介して基地局にその発見情報を送信することである．したがって，タスクの達成にはターゲットの発見とネットワークの連結性を同時に満たす必要がある．

䣐䣱䢰䢢䢳䢸䢯䢴䢢䣒䣴䣱䣥䣧䣧䣦䣫䣰䣩䣵䢢䣱䣨䢢䣶䣪䣧䢢䢴䢲䢳䢸䢢䣌䣕䣏䣇䢢䣅䣱䣰䣨䣧䣴䣧䣰䣥䣧䢢䣱䣰䢢䣔䣱䣤䣱䣶䣫䣥䣵䢢䣣䣰䣦䢢䣏䣧䣥䣪䣣䣶䣴䣱䣰䣫䣥䣵䢮䢢䣛䣱䣭䣱䣪䣣䣯䣣䢮䢢䣌䣣䣲䣣䣰䢮䢢䣌䣷䣰䣧䢢䢺䢯䢳䢳䢮䢢䢴䢲䢳䢸䢳䣃䢳䢯䢲䢷䣣䢶䢪䢴䢫

5000040000
30000
N=5N=10N=15N=20N=2510000
040000
30000
20000
10000

1234550000

50000

40000
30000
N=5N=10N=15N=20N=2512345021344545

N=5N=10N=15N=20N=2550000

30000
20000

53(c) R = 1.0, L = 1060000

N=5N=10N=15N=20N=2540000

2Num. of stopped robots

10000
120000(b) R = 0.5, L = 1060000

Average timestep

Average timestep(a) R = 0.2, L = 10030000

Num. of stopped robots

60000

10000

40000

10000
0Num. of stopped robots

20000

N=5N=10N=15N=20N=2550000

Average timestep

20000

60000

N=5N=10N=15N=20N=25Average timestep

60000

50000
Average timestep

Average timestep60000

40000
30000
20000
10000

0123450123

Num. of stopped robots

Num. of stopped robots

Num. of stopped robots(d) R = 0.2, L = 20(e) R = 0.5, L = 20(f) R = 1.0, L = 20

Fig.5 Average time to achieve the task for each N and the number of stopped robots

60
40
20100

8080

60
40
N=5N=10
N=15
N=20
N=25

20

00010012345040
N=5N=10N=15
N=20
N=25200123450123

Num. of stopped robots

Num. of stopped robots(a) R = 0.2, L = 10(b) R = 0.5, L = 10(c) R = 1.0, L = 10Success rate [%]604020100100808060
40N=5N=10N=15N=20N=252000060

Num. of stopped robots

N=5N=10N=15N=20N=2580
Success rate [%]10012345Success rate [%]Success rate [%]Success rate [%]N=5N=10N=15N=20N=2580

Success rate [%]1000123454560
40
N=5N=10N=15N=20N=25200540123Num. of stopped robots

Num. of stopped robots

Num. of stopped robots(d) R = 0.2, L = 20(e) R = 0.5, L = 20(f) R = 1.0, L = 20

Fig.6 Success rate for each N and the number of stopped robots

探索アルゴリズムとして 2 節および 4.1 節で述べたレヴィフラ
イトをターゲット探索レイヤ (図 2) に実装した SSA を採用する．
正方形環境の一辺の長さを L ∈ {10, 20}m とし，L に対する無線の通信可能距離の相対値を R ∈ {0, 2, 0.5, 1.0} とする．なお，無線の通信可能範囲は半径 R の円を仮定し，幾何学計算だけで連結性を判定する．文献 [10] では，上述と同設定で通信可能距
離 R が小さく，ロボット台数が少ないほど，タスク達成率が低下し，タスク達成時間も遅くなることを確認している．また，Lが大きいときにこの傾向は顕著であった．この結果を踏まえて，本研究における目的は 1 節で述べたようにスワームロボットの頑健性を検証することにある．そのため，故障を模擬し，実験開始5 分後に D 台のロボットを停止させる．実験開始時のロボットの台数 (初期ロボット台数) を N ∈ {5, 10, 15, 20, 25} と変化させ，各 N に対して停止ロボット台数を D ∈ {1, 2, · · · , 5} と変化させて実験を行う．なお，N 台のうち停止させる D 台はあらかじめ実験開始前にランダムに決定しておく．タスクは SR ネットワー
クを介して基地局と連結している任意のロボットがターゲットを発見するか，1800 秒 (30 分) 経過した場合に終了とする．各実
験の試行は各ロボットの初期姿勢を変えて 50 回行う．

5.4 実験結果
各 (R, L) に対する平均タスク達成時間 (シミュレーションのステップ数．1 ステップは 0.03s に設定) およびタスク達成率を図5 と図 6 にそれぞれ示す．各グラフは横軸に停止ロボット台数 Dをとり，初期ロボット台数 N を変えた結果を示している．N = 5の場合および (R, L) = (0.5, 20), (1.0, 20) のときの N = 10 の場合を除いて，各 (R, L) において同じ N の値で比較した場合，停止ロボット台数の変化に対し大きな差は見られない．文献 [10] で確認された結果と同じように，R が小さく，または，L が大きい
ときタスク達成時間・タスク達成率ともに性能が悪くなる．
N = 5 の場合の性能が悪いのはある意味当然である．その理由
は，初期ロボット台数 5 台に対し，停止ロボット台数を 1 → 5 と変化させることで，環境で稼働し続けるロボット台数は極端に少なくなるからである．とくに (R, L) = (0.2, 10), (0.2, 20), (0.5, 20)の場合では，数台が停止すると，環境で稼働しているロボットだ
けでは基地局との無線の連結を保つことが難しいため，ターゲッ
トを発見したとしても基地局にその情報を送れないことが起き，タスク達成率はほぼ 0 となる (図 6(a), 図 6(d), 図 6(e))．

䣐䣱䢰䢢䢳䢸䢯䢴䢢䣒䣴䣱䣥䣧䣧䣦䣫䣰䣩䣵䢢䣱䣨䢢䣶䣪䣧䢢䢴䢲䢳䢸䢢䣌䣕䣏䣇䢢䣅䣱䣰䣨䣧䣴䣧䣰䣥䣧䢢䣱䣰䢢䣔䣱䣤䣱䣶䣫䣥䣵䢢䣣䣰䣦䢢䣏䣧䣥䣪䣣䣶䣴䣱䣰䣫䣥䣵䢮䢢䣛䣱䣭䣱䣪䣣䣯䣣䢮䢢䣌䣣䣲䣣䣰䢮䢢䣌䣷䣰䣧䢢䢺䢯䢳䢳䢮䢢䢴䢲䢳䢸䢳䣃䢳䢯䢲䢷䣣䢶䢪䢵䢫ターゲット探索実機実験

100

6.1 実験環境
本実験は摂南大学寝屋川キャンパス 1 号館 6 階の廊下を環境とした (図 7 の黄色部分)．廊下と隣接する部屋としては，製図室・学生実験室などがある．図 7 の右上に各ロボットに搭載した無線通信装置と同じ XBee (coordinator として設定) を PC に接続し，無線通信基地局 (以下，基地局) として設置する．また，図の左下にターゲットである赤外線発光ボール (3 節参照) を設置する．スワームロボットの初期位置は基地局近傍とし，図の右下とする．本環境の特徴として，ターゲットと基地局の間の見通しが不可能であり，また，直接通信も不可能という点が挙げられる．
6.2 実験設定
本タスクは 5 節と同様に，基地局と直接通信が不可能な距離(約 80m 先) にあるターゲットを見つけ，基地局にその発見情報を送信することである．本環境では予備実験の結果，XBee の仕様から算出される通信可能距離 (45m) よりも長い距離 (54m) で通信可能であることがわかっている．本環境では初期ロボット台数を N = 15 として実験を行った．停止ロボットの設定は 5 節と同じとする．タスクはロボットがターゲットを発見し基地局にその情報を送信するか，1800 秒 (30 分) 経過した場合に終了とする．探索アルゴリズムとして 5 節と同様にレヴィフライトを実装した SSA を採用する．各実験の試行回数は 10 回とする．
6.3 実験結果
図 8 に停止ロボット台数に対するタスク達成率および平均タスク達成時間を示す．停止ロボット台数 D = 0 の場合のタスク達成率は 90%であり，D = 1, 3 の場合に減少，D = 4, 5 の場合に増加している．一方，タスク達成時間は D = 0 の場合が最も遅く，数台のロボットが停止する場合の方が早い．
この結果から停止ロボット台数が多い方が良い結果を示す．これは本環境における N = 15 台が本タスクに対し冗長であることを示す．では，何台が適切かという話になるが，個々の環境に対して適切なロボット台数はいくつかという議論は本稿の趣旨ではない．提案するスワームロボットが「数」に関して冗長であり，個体の損失に対し頑健性を確認できたことが重要だと考える．5.4
節の結果についても同様のことがいえる．
6.4 考察停止したロボットが動作を継続しているロボットに与える影響を調べるために，停止ロボット台数分をあらかじめ差し引いた初期ロボット台数で追加実験を行った．初期ロボット台数 N = 10，停止ロボット台数 D = 0 とし，上記実験と同じように 10 試行行った．初期ロボット台数 N = 15，停止ロボット台数 D = 5の場合と比較した結果を表 1 に示す．どちらもタスク達成率は100%であり，タスク達成時間に大きな差は見られない．このことから，停止したロボットが動作を継続しているロボットに悪い影響を与えていないことが確認できた．

7おわりに

本稿では無線通信を用いた SR ネットワークによるターゲット探索に関する計算機実験および実機実験を行い，個体の損失に対するスワームロボットの頑健性を確認した．今後，囲いのない開放空間への拡張を行っていきたい．

6.1m

70.4m

6.3m

3.7m

6.0m

1200

Success rate [%]

80

1000
60

800

40600
400

20200

00012345

Num. of stopped robots

Fig.8 Success rate and average time for each number ofstopped robots
Table 1 Comparison between the trials with and without
stopping the robots
初期台数 (停止台数)
平均タスク達成時間 [s]タスク達成率 [%]N = 15 (5)
1129
100

N = 10 (0)
1111
100

参考文献[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.
[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., Chen,
H.H., “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] Lévy, P., “Theorie de l’Addition des Veriables Aleatoires”,
Gauthier-Villars, 1937.
[10] 片田喜章，“スワームロボットによるターゲット探索 − レヴィフライ
トに関するシミュレーションを用いた考察”, 第 16 回計測自動制御
学会システムインテグレーション部門講演会講演論文集, pp.47–52,
2015.
[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.

B

2.4m
8.4m

1400

Average time [s]

66.1m

T
82.8m

Fig.7 Setup for target detection problem in the real environment (B: base station, T: target)[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] Brooks, R., “A Robust Layered Control System for a MobileRobot”, IEEE Journal of Robotics and Automation, Vol.2,No.1, pp.14–23, 1986.

䣐䣱䢰䢢䢳䢸䢯䢴䢢䣒䣴䣱䣥䣧䣧䣦䣫䣰䣩䣵䢢䣱䣨䢢䣶䣪䣧䢢䢴䢲䢳䢸䢢䣌䣕䣏䣇䢢䣅䣱䣰䣨䣧䣴䣧䣰䣥䣧䢢䣱䣰䢢䣔䣱䣤䣱䣶䣫䣥䣵䢢䣣䣰䣦䢢䣏䣧䣥䣪䣣䣶䣴䣱䣰䣫䣥䣵䢮䢢䣛䣱䣭䣱䣪䣣䣯䣣䢮䢢䣌䣣䣲䣣䣰䢮䢢䣌䣷䣰䣧䢢䢺䢯䢳䢳䢮䢢䢴䢲䢳䢸䢳䣃䢳䢯䢲䢷䣣䢶䢪䢶䢫