ばらまき型センサネット構築のためのマルチコプタの逐次行動計画○杉浦孔明，河井恒（情報通信研究機構）

1. はじめに情報収集等の応用において，マルチコプタの利用が広く行われるようになってきた．地区レベルのモニタリングを考えると，安価なセンサをマルチコプタに運搬させセンサネットを即座に構築することが合理性を持ち得る [1]．
本研究では，人手によるセンサ設置が困難，または危険な場所へのセンサネットの構築を扱う．対象としては，洪水，汚染，気象などに関するイベント検出や， 図 1 構築したハードウェア．電磁石による物体運搬機構を有する．
生態系，土壌などの環境モニタリングがある．近年，安価または使い捨て型のセンサが容易に入手可能になるととに，WiSUN など長距離かつ省電力な通信手段が出ンサ位置を知ることができるという仮定があるが，ば現し，コンシューマレベルのマルチコプタ（ドローン）
らまき型センサ配置ではこのような仮定を置くことがが普及してきた．このような背景から，マルチコプタできない．
を利用して安価なセンサをばらまけば，地区レベルの本論文では，位置誤差があるような状況下におけるセンサネットワークを即座に構築することができると劣モジュラ最適化によるセンサ配置手法を提案する．本考えられる．
研究の独自性は以下である．
現状では，バッテリー持続時間の制約からマルチコプタの飛行時間は極めて短い．そのため，限られた個数• 期待相互情報量最大化によるばらまき型センサ配のセンサをいかに配置するかが問題になる．単純に格置手法を提案した
子状に設置することも考えられるが，観測対象やニー• 再現性を確保可能な実験環境を構築し，提案手法
ズによっては必ずしも情報収集に有効とは限らない．
が優れることを確認した
本研究では，マルチコプタによるばらまき型センサ2. タスク環境およびハードウェア配置問題を扱う．ばらまき型センサ配置とは，マルチコプタにより観測対象の周辺にセンサを逐一投下する
2.1 ハードウェア行動計画問題を指すものとする．マルチコプタによる
図 1 に本研究で用いるハードウェアを示す．本マル
ばらまき型センサ配置を考えるうえで考慮すべき点がチコプタは Parrot 社 AR.Drone 2.0 を改造し，物体運搬２点存在する．1 点目は自己位置推定により得られる機構を有する脚部と，機構を制御する制御基板を追加
位置は必ずしも正確ではない点である．くわえて，空したものである．物体運搬機構は，電磁石の ON/OFF中からセンサを投下するため，材質によっては投下位により物体を吸着/投下する．安定して運搬・飛行可能置からかなりずれた位置にセンサが配置される．2 点な物体の最大重量は，50g 程度である．本研究では，マ目は，マルチコプタの可搬重量は小さいため，1 回にルチコプタはセンサを同時に 1 個だけ運搬可能なもの運搬可能なセンサ個数が限定されることである．以上とする．
2 点から，事前に最適配置が決定されてそれにしたがっマルチコプタの自己位置推定は，マルチコプタに搭て各センサが設置されるのではなく，逐次的に次の最載された単眼カメラを利用した位置推定手法 [7] を用適設置位置を得て配置を行う必要がある．
いて行った．すなわち，モーションキャプチャ等の外部センサ配置問題については，センサネットワーク，環デバイスは用いておらず，屋外への展開が可能である．
境モニタリング，ロボティクス等の分野で広く研究が行
2.2 タスクシナリオ
われてきた [2]．また，安価なセンサによるセンサネッ
マルチコプタは屋内に用意した図 2 に示す環境
トワークの構築およびセンサ位置推定についても多くの研究がある [3,4]．一般にセンサ配置問題においては， （8x12m）でセンサを運搬するものとする．なお，本手法自体には，屋内・屋外について本質的な違いはない．
取り得る配置部分集合が指数関数的に増加するため，最移動において，遠隔操縦など人間による操作は一切行適配置を厳密に計算する時間が極めて大きい．一方，相わないものとする．
互情報量規準における劣モジュラ性を利用すれば，逐まず，タスクの開始時点において，マルチコプタはス次的に貪欲法を適用しても (1 − 1/e) 近似が保証されタート位置から浮上し，空中でセンサ取り付け可能状る [5, 6]．すなわち，最悪のケースにおいても最適値の態に移行する．センサについては，ホバリング状態に63%が保証されているだけでなく，実際には 90%程度おいて実験者が取り付けるものとする．マルチコプタの性能を示すことも報告されている．ただし [5] ではセ表 1 変数定義

図 2 タスク環境．黄色のオブジェクトは投下済みのセンサである．

自身が設置されているセンサを自動で取り付けることもハードウェアとしては不可能ではないが，本論文の主旨ではない．その後，提案手法により得られるターゲット位置まで飛行し，センサを投下する．その後，マルチコプタはスタート位置に戻り，次のセンサを実験者が取り付ける．

3. 期待相互情報量最大化によるばらまき型
センサ配置
表 1 に変数定義をまとめる．新規にセンサをひとつ置いたときに得られる観測値は，以下のようなガウス分布に従うものとする．

p(yobs ) = N (µy , σy2 )全センサの集合AĀ
yobs

配置済みセンサの集合

V \{A ∪ y}
センサ y の観測値

YA
p(yobs ; µy , σy2 )センサ集合 A の観測値ベクトル

p(YA ; µA , ΣAA )µy , σy2µA , ΣAA

YA の同時分布 (Gaussian)p(yobs ) の平均および分散p(YA ) の平均および共分散行列

2µy|A , σy|A

YA で条件付けられた yobs の平均および分散

yobs の分布 (Gaussian)yobs と YA の共分散ベクトル
カーネル関数A と V \A の間の相互情報量

ΣyA
K(·, ·)M I(A)

センサ y を追加した際の M I(A)δyの増分
スタート位置

yinit
ypos
∗
ytarget

センサ y の位置
次のターゲット位置

p(ypos ; ytarget , Σscatter )ytarget , Σscatterypos の分布 (Gaussian)p(ypos ) の平均および共分散行列(1)

同様に，設置済みのセンサ集合 A から得られる観測値もガウス分布に従うものとする．

p(YA ) = N (µA , ΣAA )V(2)

いま，各センサの観測量の共分散が，適当なカーネル関数により近似できるものとする．本研究では，ypos′と yposに配置されたセンサ観測値の共分散は，以下の放射基底カーネルで与えられるものとする．
}{′||ypos − ypos||2′
K(ypos , ypos ) = exp2γ 2′)<ϵ
ただし，分散が 0 にならないように，K(ypos , ypos′であれば，K(ypos , ypos ) = ϵ とする．ここに ϵ は正の小数（例えば 0.01) とする．
多次元ガウス分布に従う確率変数を分割したときに得られる条件付き分布の公式から以下がいえる．

µy|A = µy + ΣyA Σ−1AA (YA − µA )

(3)

2σy|A
= σy2 − ΣyA Σ−1AA ΣAy(4)

いま，M I(A) を，センサ集合 A および V \A の観測値の相互情報量として以下のように定義する．

M I(A) ≜ I(A; V \A)
ここで，M I(A) は劣モジュラ関数であり，貪欲法が(1 − 1/e) 近似を与える [5]．(1 − 1/e) は約 63%である
ので，最適値の 63%が保証されているといえる．

∗貪欲法による ytargetの選択は，以下で与えられる．
∗ytarget= argmax δy(5)y∈V \A

センサが決められた位置に誤差なく設置できるのであれば，上記に従いセンサを配置することができる．しかし，ばらまき型センサ配置問題では，誤差なく設置できることはない．以下では，そのために M I(A) を拡張する．
ここで，Scattering Mutual Information (SMI) を以下のように定義する．

SM I(A) ≜ Epos [I(A; V \A)]
提案手法では，SMI(A) の増分を貪欲法により最大化する．これにより，ばらまき型センサ配置の計画が逐次的に行われる．
落下後のセンサの位置 ypos は，ガウス分布で与えられると仮定する．

ypos ∼ N (ytarget , Σscatter )すなわち，ytarget を中心として Σscatter で表される分散によりセンサが散らばるものと仮定する．Σscatter については，事前に実験を行い合理的な値を定めるものとする．また，V \A には，落下後に最も近くにある Vの要素のうち，まだ選択されていないセンサを入れるものとする．

∗以上より，ytargetは以下のように求められる．導出の詳細については，[8] を参照されたい．
∗ytaget= argmax δySM Iy∈V \A= argmax {Epos [M I(A ∪ y)] − Epos [M I(A)]}y∈V \A= argmax Epos [M I(A ∪ y) − M I(A)]y∈V \A= argmax Eposy∈V \A[σy2 − ΣyA Σ−1AA ΣAy−1σy2 − ΣyĀ ΣĀΣĀ Āy](6)

上記の期待値の計算において，センサが落下する位置の分布は本来連続であるが，粒度の細かい離散空間と仮定して期待値を求めることができる．

4. 実験
4.1 設定実環境を模擬した環境をシミュレータ上に構築した（図 3 参照）．図において，右下の画像はマルチコプタのカメラ画像であり，画像中の赤色・緑色・黄色で示す点は特徴点である．青い立方体は配置済みのセンサを示す．ターゲット位置候補領域として，緑の枠で示す4x4m の領域を設定した．ターゲット位置候補領域には25 個の格子点が設定されており，格子点はターゲット位置候補集合を形成する．各ターゲット位置候補同士の距離は 1m である．マルチコプタは各ターゲット位置候補を目標としてセンサを投下するが，必ずしも格子点上にセンサが配置されるわけではない．なお，位置のずれにより，ターゲット位置候補領域の外側にセンサが配置されることがあり得る．
貪欲法が (1 − 1/e) 近似を与えるためには，配置するセンサの最大数が V の大きさの半分を超えてはならな
い [5]．そこで，本実験では配置するセンサの最大数を12 とした．
前述したように，ばらまき型センサ配置においては必ずしも正確な位置が得られない．そのため，マルチコプタの位置推定手法としては [7] の手法を用いた場
合の Σscatter について事前調査を行った．事前実験の結果から，Σscatter は以下のように近似できるものとした．
[]
αx d + ββΣscatter =βαy d + β

図 5 センサ数に対する累積 δy を尺度とした性能評価結果．(a) 提案手法，(b) ベースライン [5]，(c) ランダム．
10 回の実験の平均を示す．左：(αx , αy ) = (0.3, 0.2)．
右：(αx , αy ) = (0.4, 0.4)．

ここに，d は移動距離 ||yinit − ytarget || を表し，β は正の小数（β = 0.01）である．αx , αy の設定については後述する．また，カーネル関数のパラメータを γ = 1とした．

4.2 結果図 4 に，定性的結果を示す．図において黒丸は yinit ，x はセンサが実際に配置された場所，25 個の四角は集合 V である．色の濃さは δy （ベースライン），または
δySM I （提案手法）の大きさを示す．すなわち，色が最も濃い四角が次の最適なセンサ投下位置である．また，(αx , αy ) = (0.3, 0.3) と設定した．
ベースライン手法は [5] により提案されたものであり，期待値を考慮せず式 (5) により次のセンサ位置を得る．どちらの手法についても，1 個目のセンサは中央をターゲット位置とすることとした．2 個目以降のセンサについては各手法により最適なターゲット位置を決定し，マルチコプタからセンサを投下した．
図 5 に，定量的な性能評価結果を示す．図の横軸はセンサ数であり，縦軸は累積 δy である．比較対象として (a) 提案手法，(b) ベースライン [5]，(c) ランダム，による結果を示す．ベースライン手法では，期待値を考慮せず式 (5) により次のセンサ位置を得る．ランダム手法では，ターゲット候補集合からランダムに次のセンサ位置を得る．左図は (αx , αy ) = (0.3, 0.2) の結果であり，右図は (αx , αy ) = (0.4, 0.4) の結果である．各々10 回の実験を行い，平均をプロットした．
図 5 左図より，提案手法はすべてのセンサ個数においてベースラインおよびランダムより大きい累積 δy を得ている．これは本実験設定において，提案手法が有効であることを示している．図 5 右図においても，提案手法はベースラインおよびランダムより良い結果を得ている．
図 6 に，様々なパラメータの組み合わせについて，提案手法とベースラインを比較した感度解析の結果を示す．各点の色は，以下で定義する提案手法とベースライン手法の差 ∆ を表す．
⌊|V |/2⌋∆=∑∆i (δySM I )i=2

図 3 シミュレーション環境

ここに，∆i (δySM I ) は，i 番目のセンサを配置した場合における，提案手法およびベースライン手法による δySM Iの差分である．また，MI(A) が単調性および劣モジュラ

図 4 提案手法（上段）およびベースライン手法（下段）によるばらまき型センサ配置の定性的結果．黒丸は yinit ，四角で示される集合は V を示す．色の濃さは δy ，または δySM I の大きさを示す．x はセンサが実際に配置された場所を表す．

提案手法の応用としては，環境汚染物質等のモニタリングを行うばらまき型センサ配置計画立案などが挙げられる．
本研究に関する動画は，http://komeisugiura.
jp/ を参照されたい．
謝辞
本研究の一部は，JST CREST および JSPS 科研費 15K16074の助成を受けて実施されたものである．

参

図 6 パラメータに対する感度解析の結果．(αx , αy ) の組み合わせ 121 通りに対して，提案手法とベースライン手法の差を示す．各点は，提案手法およびベースライン手法による累積 δySM I の差分について，10回ずつ実験を行った場合の平均を示す．

関数であるためには，センサの最小数は 2 であり，最大数は |V | の 1/2 であることに注意されたい．図において，x 軸，y 軸はそれぞれ αx ，αy を表す．
図より，誤差が小さい領域（αx < 0.2 かつ αy < 0.2）
では，提案手法とベースライン手法はほぼ同等の性能である．提案手法はベースライン手法の拡張であり，誤差が小さい場合は等価となるため，これは合理的である．一方，誤差が大きい領域では，一般的に提案手法が優れることがわかる．

5. おわりにマルチコプタは，環境モニタリング，農業，エンターテイメントなど多岐にわたる応用可能性を有している．
Association for Unmanned Vehicle Systems International（AUVSI）の調査によると，アメリカ合衆国における飛行ロボットの経済効果は，2015 年から 2025 年の間に821 億ドルと予想されている [9]．本研究では以下を達成した．

• 期待相互情報量最大化によるばらまき型センサ配置手法を提案した• 再現性を確保可能な実験環境を構築し，提案手法が優れることを確認した

考文

献[1] M. Abdulaal, M. Algarni, A. Shamim, and C. Claudel, “Unmannedaerial vehicle based flash flood monitoring using lagrangian trackers,”
International Workshop on Robotic Sensor Networks, 2014.
[2] W.E. Hart and R. Murray, “Review of sensor placement strategies
for contamination warning systems in drinking water distributionsystems,” Journal of Water Resources Planning and Management,
vol.136, no.6, pp.611–619, 2010.
[3] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-less low cost outdoor
localization for very small devices,” IEEE Personal Communications
Magazine, vol.7, no.5, pp.28–34, 2000.
[4] K. Sugiura, D. Matsubara, and O. Katai, “Construction of robotic
body schema by extracting temporal information from sensory inputs,” Proceedings of SICE-ICASE International Joint Conference
2006, p.to appear, Busan, Korea, Oct. 2006.
[5] A. Krause, A. Singh, and C. Guestrin, “Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies,” The Journal of Machine Learning Research, vol.9,pp.235–284, 2008.
[6] 河原吉伸，永野清仁，劣モジュラ最適化と機械学習，講談社，2015．
[7] J. Engel, J. Sturm, and D. Cremers, “Scale-aware navigation of alow-cost quadrocopter with a monocular camera,” Robotics and Autonomous Systems, vol.62, no.11, pp.1646–1656, 2014.
[8] 杉浦孔明，“劣モジュラ性を利用したドローンによるばらまき型センサ配置,” 2016 年度人工知能学会全国大会資料，pp.1O5–OS–22b–5，2016．
[9] D. Jenkins and B. Vasigh, “The economic impact of unmanned aircraft systems integration in the united states,” 2013.