䢴䣃䢴䢯䣚䢲䢸

パーコレーション理論を用いたスワームロボットネットワークの連結性―通信距離とロボット数に関する考察―

Connectivity of Swarm Robot Networks for Communication Range and the Number of Robots
Using Percolation Theory○ 西口晃央 (摂南大)

片田喜章（摂南大）

Akihiro NISHIGUCHI, Setsunan University
Yoshiaki KATADA, Setsunan University, katada @ ele.setsunan.ac.jp

One approach in swarm robotics (SR) is homogeneous system which is embedded withsensing, computing, mobile and communication components. This is identiﬁed with mobile
wireless sensor networks (WSNs). For some SR tasks, robots need to collect information fromthe environment and share their data with each other. Due to the multi-hop transmissionof WSNs, robots in such networks can communicate with each other via intermediate relayrobots. Therefore, it is important to take connectivity of the network into account. This
study investigates communication range and the number of robots required for a SR network
to achieve connectivity by using percolation theory.
Key Words: Swarm Robotics, Wireless Sensor Networks, Connectivity, Percolation Theory

1

はじめに

2

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

B

パーコレーション

本節ではパーコレーションについて簡単に紹介する．正方格子の格子点上に確率 p で要素（サイト）を配置する．p を 0 から大きくしていくと，要素がクラスター (かたまり) を形成するようになり，ある臨界値 pc に達すると正方格子の上下および左右の端がつながる (percolate: パーコレートする，浸透する) ような巨大なクラスターが出現する．このようなクラスターの構築過程
をサイト過程いう．また，別のクラスターの作り方として，要素を配置するのではなく，格子点間につながり（ボンド）を配置していくボンド過程がある．このように系を構成する要素間のつながり方およびつながった要素集合の特性を扱う理論がパーコレー
ションである [6]．
無限に大きな系を考えると，そこで無限に大きなクラスターが出現する臨界値は格子の形によって決まることが知られており，2 次元・3 次元の基本的な格子に関しては厳密解が得られている．
厳密解が得られないものに関しては計算機実験により近似値を得ている．また，無限という極限状態において，パーコレートする確率および臨界値にはある関数系が存在し，その関数系を規定するパラメータ (臨界指数) は格子の形には依存せず，次元によって決まることが報告されている．
格子におけるパーコレーションだけではなく，連続空間に要素を配置する場合に関しても研究が行われている [6][8][9]．連続空間では格子点のように要素が「隣接する」という概念がないため，要素間の「つながり」を定義する必要がある．2 次元連続平面において要素同士がつながる範囲を半径 R の円で設定する例を図2 に示す．このとき，要素間の距離を d とすると，d < R のときに要素間につながりが存在する．

TRFig.1 Target detection using SR (B: base station, T:target, solid lines: ad hoc network, ●: robot)
1 各ロボットはターゲットを検知するセンサをもち，かつ，移動することから，このシステムはモバイルセンサネットワークと同一と捉えることができる．

Fig.2 Illustration of the bonding criteria for two-dimensional ramdom-lattice site problem䣐䣱䢰䢢䢳䢶䢯䢴䢢䣒䣴䣱䣥䣧䣧䣦䣫䣰䣩䣵䢢䣱䣨䢢䣶䣪䣧䢢䢴䢲䢳䢶䢢䣌䣕䣏䣇䢢䣅䣱䣰䣨䣧䣴䣧䣰䣥䣧䢢䣱䣰䢢䣔䣱䣤䣱䣶䣫䣥䣵䢢䣣䣰䣦䢢䣏䣧䣥䣪䣣䣶䣴䣱䣰䣫䣥䣵䢮䢢䣖䣱䣻䣣䣯䣣䢮䢢䣌䣣䣲䣣䣰䢮䢢䣏䣣䣻䢢䢴䢷䢯䢴䢻䢮䢢䢴䢲䢳䢶䢴䣃䢴䢯䣚䢲䢸䢪䢳䢫

3.1

計算機実験

実験設定

本実験では 2 次元連続空間における離散パーコレーションをモデルとする [9]．図 3 に示す 1 × 1 の単位平面に Ns 個の点を一様分布させる．それらの点のつながりは，各点を中心として半径 R の円をえがき，互いの円内に入った点の間に生じるものとする．SR ネットワーク（無線センサネットワーク）と対応させると，密度 Ns は単位平面におけるロボットの台数（ノード数），点 i(i ∈ {1, · · · , Ns }) は任意のロボット（ノード），R は各ロボット (各ノード) の通信可能距離，をそれぞれ表す．ただし，R は全てのロボットで同じ値に設定する．本研究ではターゲット探索をそのタスクとして想定していることから，環境の左下の原点に各ロボットと同じ通信可能距離をもつ基地局を設置し，基地局と各ロボットの連結性を調べる．つまり，ロボットの台数 Ns を一定に保って通信可能距離 R を増加させる，もしくは，R を一定に保って Ns を増加させると，あるところで大部分のロボット間につながりが生じ（パーコレーションが起こり），マルチホップ通信による基地局との通信が可能となる．本実験では R ∈ {0.05, 0.1, 0.2, 0.3, 0.4, 0.5}，Ns ∈ {2, · · · , 1400} とし，ロボットの位置をランダムに設定した実験を各 (R, Ns ) に関して 10000 回行った．以上の設定では各点に配置するロボットに大きさを想定していない．つまり，各ロボットの近傍に何台でもロボットを配置できる．そこで 2 つ目の実験として，各ロボットに大きさ（半径: rHC ∈ {0.05, 0.075, 0.1}，ただし rHC < R）を設定する．rHC < R という条件は，通信可能距離 R よりも大きいロボットのボディrHC を設定すること (rHC > R) は本実験の目的と照らし合わせてあり得ないためである．他のロボッ
トおよび環境の境界と重ならないように各ロボットを配置し，1つ目の実験と同様の実験を行った．ただし，大きさを設定することから，Ns に関して上述の範囲すべての実験が行えるわけではない．結果を次節に示す．
(0,1)

(0,0)

1
0.8
0.6
0.4
0.2
01

2

1010
Ns

R=0.9
R=0.8
R=0.7

R=0.6
R=0.5
R=0.4

R=0.3
R=0.2
R=0.1

Fig.4 Percolating sample fraction for each transmissionrange

Table 1 Critical values of Ns for each R and rHC, above
which a network is fully connected.
rHC
00.050
0.075
0.100

0.1
1388xx–

0.2
341xx–

0.3
163
47xx

0.4
83
36xx

R
0.5
50
26
18x

0.6
34
19
14
110.7
20
17
10
90.8
16
12
8
7

0.9
97
65(1,1)

4R

4.1(1,0)Fig.3 Experimental setup for two-dimensional ramdom-lattice site problem

3.2

Percolating Sample Fraction

3

実験結果

基地局から直接的もくしはロボットを介して間接的に連結したロボット数の割合（試行回数に対する平均）psf を縦軸に，Nsを横軸にとった片対数グラフを図 4 に示す．各 R に関して，psfが 1.0 に収束する Ns の臨界値が存在することがわかる．本実験で得られた臨界値を表 1 にまとめる (rHC = 0.0)．
つぎにロボットに大きさを設定した場合の結果を図 5 に示す．
グラフの重なりを避けるため，各 R について図 5(a)-5(d) にそれぞれ示している．ここで，横軸のスケールが異なることに注意されたい．また，rHC = 0.0 の結果は大きさを想定していない 1 つ目の実験の結果 (図 4) を示している．R の値が小さい場合，psfを得る計算自体が実行できていないことがある (例えば，図 5(a)の rHC = 0.075, 0.005，図 5(b) の rHC = 0.075, 0.1 など)．これは，R の値が小さい場合，大きな psf の値をとるにはより多くの Ns を必要とするが，ロボットに大きさを設定しているため，その台数分を環境に配置することができないためである．R の値が大きい場合，rHC が大きくなると psf の値が大きくなることがわかる (図 5(d))．また，各 R について rHC = 0.0 の場合にNs に対する psf の下限値をとることもわかる．ここでは省略す
るが，他の R についても同じ傾向を示すことを確認している．
各 rHC について，Ns の臨界値を表 1 に示す．表中，x は計算が実行できなかったことを表し，–は設定外であることを表している．R ≥ 0.5 の場合に，大きさを設定することにより，環境において各ロボットがより広範囲に分布することで，より少ないNs で連結性が満足されることがわかる．

考察

結果の利用方法

3 節で得られた結果の利用方法を考えてみる．3 節での実験設
定は 1 × 1 の単位面積あたりにロボットを Ns 台配置し，そのときの各ロボットの通信可能距離を R としたものであった．したがって，縦と横の長さが 1，その相対値として通信距離 R を捉えればよい．
例えば，通信距離が見通し通信で 200m であるとする．これを 400m × 400m の 2 次元平面で考えると，表 1 の R = 0.5 に対応し，50 台のロボットを配置すればよい．250m × 250m の 2次元平面で考えると，R = 0.8 に対応し，16 台のロボットを配置すればよい．R が大きい場合，ロボットに大きさを設定すると連結性の保証に必要となるロボット台数を減らすことができる．
しかし，上述の 250m × 250m の 2 次元平面で R = 0.8 に対応させる場合だと，250m × 0.05 = 12.5m となり，直径 25m のロボットという設定になる．一般的な通信距離を仮定しロボットの大きさが 1m 以下だと仮定すると，rHC  R となり，通常の大きさのロボットでは rHC = 0 の場合の結果を参照すればよいということがわかる．
では，実際の通信距離に対してどの程度の大きさの 2 次元平面を考え，表 1 の R(割合) に対応させればよいかという問題がある．これは用意できるロボットの台数および実行しなければならないタスク（本研究での想定ははじめにで述べたターゲット探索）に依って決定することになる．

4.2

連結性の検証3 節で得られた結果を検証するために，各ロボットが障害物回避をしながらランダムに移動するシミュレーション実験を行った．実験設定のパラメータは表 1 を参考にして，rHC = 0.05，(R, Ns ) = (0.6, 20), (0.2, 20), (0.3, 50) とした．初期位置をランダムに設定し，10 試行行った．横軸にシミュレーションの時間ステップ数，縦軸に psf の 10 試行の平均 (connectivity) をとったグラフを図 6 に示す．
R = 0.6, Ns = 20 のときは，環境を広い通信可能範囲が覆うことで，比較的少ないロボット台数で連結性を保っている（図6(a)）．同じ台数で R を小さくした場合 (R = 0.2, Ns = 20)，大部分の時間帯で連結性を保てない（図 6(b)）．また，小さい通信距離で台数が多い，R = 0.3, Ns = 50 の場合でも，実験中のほとんどの時間帯において連結性が保たれていることがわかる．実験の後半で連結性を保てなかった試行では，50 台のロボットのうち数十台がロボット同士および環境の端でデッドロック状態に陥り移動することができず，環境における適当な広がりをロボット全体として保てていなかった．

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

0.8

1

rHC=0.0
rHC=0.050
rHC=0.075

Percolating Sample Fraction

Percolating Sample Fraction

10.6
0.4
0.2
01210100.8
0.6
0.4
0.2
03101210Ns10Ns(a) R = 0.1(b) R = 0.2
1
Percolating Sample Fraction

1Percolating Sample Fraction

rHC=0.0
rHC=0.050
rHC=0.075
rHC=0.100

0.8
0.6
0.4
rHC=0.0
rHC=0.050
rHC=0.075
rHC=0.100

0.2
01

0.8
0.6
0.4

02

10

rHC=0.0
rHC=0.050
rHC=0.075
rHC=0.100

0.210110NsNs(c) R = 0.3(d) R = 0.5

Fig.5 Eﬀect of the size of the robot on the percolating sample fraction

51Connectivity

0.8
0.6
0.4
0.2
00200

400600Time Step800

1000

文献(a) R = 0.6, Ns = 20

[1] “Swarm Robotics from Biology to Robotics”, Edited by Ester
Martinez Martin, InTech 2010.

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

Connectivity

0.8
0.6

[4] Sahin, E., “Swarm Robotics: From Sources of Inspiration toDomains of Application,” Lecture Notes in Computer Science,
Volume 3342/2005, pp.10-20, 2005.

0.40.200200

400600Time Step

8001000(b) R = 0.2, Ns = 20

[5] 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.
[6] 小田垣孝，“パーコレーションの科学”，裳華房, 1993.
[7] 杉山・辻岡・村田，ネットワーク化された群ロボットにおける被災者
発見システム，情報処理学会論文誌，Vol. 46, No. 7, pp.1777-1788,
2005.
[8] Gilbert, E.N., “Random Plane Networks”， J. Soc. Indust.
Appl. Math, Vol. 9, No. 4, pp.533―543, 1961.

10.8
Connectivity

おわりに

本稿では，パーコレーション理論を用いて，SR ネットワークの連結性を保証するロボットの台数と無線の通信距離を数値実験により算出した．その結果にもとづいてシミュレーションを行ったところ，環境で障害物回避行動中のロボットの大部分が基地局との連結性を保てることを確認した．実際の環境には，障害物などがあり，無線の通信品質は劣化するものと想定される．今後，これを考慮したパーコレーションに関する実験を行いたい．また，連結性を保った上でタスクの達成・効率の改善を可能とするロボットの行動設計などを考えていきたい．さらにこれらを踏まえた実機実験 [10] も予定している．

0.6[9] Pike, G. E. and Seager, C. H., “Percolation and Conductivity: A Computer Study. I”，Phys. Rev. B, volume 10, issue 4,
pp.1421-1434, 1974.

0.4
0.2
00200

400600Time Step

8001000[10] 西口晃央，片田喜章，“スワームロボティクスによるターゲット探索における実機実装の検討”，計測自動制御学会 システム・情報部
門学術講演会 2013，講演論文集, p.311-312, 2013.

(c) R = 0.3, Ns = 50Fig.6 Connectivity for each time step䣐䣱䢰䢢䢳䢶䢯䢴䢢䣒䣴䣱䣥䣧䣧䣦䣫䣰䣩䣵䢢䣱䣨䢢䣶䣪䣧䢢䢴䢲䢳䢶䢢䣌䣕䣏䣇䢢䣅䣱䣰䣨䣧䣴䣧䣰䣥䣧䢢䣱䣰䢢䣔䣱䣤䣱䣶䣫䣥䣵䢢䣣䣰䣦䢢䣏䣧䣥䣪䣣䣶䣴䣱䣰䣫䣥䣵䢮䢢䣖䣱䣻䣣䣯䣣䢮䢢䣌䣣䣲䣣䣰䢮䢢䣏䣣䣻䢢䢴䢷䢯䢴䢻䢮䢢䢴䢲䢳䢶䢴䣃䢴䢯䣚䢲䢸䢪䢵䢫