計測自動制御学会東北支部 第 312 回研究集会
資料番号 312-3

無人航空機によるセンシングの効率化のためのウェイポイントルート探索手法
A UAV Path Planning Method for Efficient Sensing in Radiation Dose Mapping○森田 暁志 大山 勝徳 見越 大樹 西園敏弘
Tokishi Morita，Katsunori Oyama，Taiju Mikoshi，Toshihiro Nishizono
日本大学
Nihon University
キーワード：クラスタ化された経路計画(clustered path planning)，UAV リモートセンシング(UAV-based remote sensing)，放射線量マッピング(radiation dose mapping)，
Flood Fill アルゴリズム(flood fill)，2-opt 法(2-opt)
連絡先：〒963-8642 福島県郡山市田村町徳定字中河原１
日本大学 工学部 情報工学科
森田暁志，Tel.:(024)-956-8830 Email: morita.python.1027@gmail.com——————————————————————
本研究は，一定地上分解能で時間効率を改1はじめに善するための UAV 経路計画法を提案する．
無人航空機（UAV）を用いたリモートセン
この提案手法は，Flood Fill アルゴリズムとシングは，災害対応や調査など多くの分野で2-opt 法を組み合わせたものであり，隣接する注目しており，復旧と復興の初期段階から除欠損領域の飛行経路には Flood Fill アルゴリ
染作業において重要な役割を果たしている
ズムで適用したウェイポイントルートを用
1) 2) ． 2011 年 3 月 11 日の福島第一原子力いる．提案手法は，飛行経路計画のためのウ発電所の災害に伴い，住宅地周辺の放射線量ェイポイント数の削減と，UAV が通過できるマップは，住居や農場から避難させた市民の効率的なウェイポイントルートを決定し，重大な懸念の一つとなった．森林や河川など
2-opt 法によりすべてのウェイポイントルーの侵入が困難な地域は，日本原子力研究開発
トを訪問する最短ルートを見つける特徴が機構（JAEA）が原子力発電所周辺の 80km 圏ある．
内での航空放射線量モニタリングの結果をフィールドテストによる実験の結果，原子示す調査図を初めて発表した 1)．航空モニタ
力災害の影響を受けた地域における放射線リングは広範囲の観測領域をカバーするこ量マッピングの現実的な事例を通じて得らとができた．しかし，航空モニタリングは地れた結果から，提案手法は 2-opt と Flood-fill
上 300ｍ以上で約 1.85km のトラック幅で行わのアルゴリズムから得られた結果と比較しれている 2)．積載重量が 10kg の無人ヘリコて飛行時間を約 10％と 29％改善した．さらプターについても，地上分解能のマッピングに，飛行中の旋回回数が，推定コストと実際について実験を行なった 3)．UAV を用いたコストの差の要因であることがわかった．
航空モニタリングの放射線量マッピングの分野では，近年，マルチロータの UAV によ
2 欠損領域の飛行経路計画って小さい領域の地上分解能が改善されて観測のためのUAV経路は，ウェイポイントいる 4) 5) 6)．従来研究では，小さな領域で集ルート上の長さと幅の固定された測定間隔で中的に解析するため，多数の平行線の周り形観測点を得られることが，放射線量マッピン作られた飛行経路に焦点を当てていた．しかグの理想的な経路である．しかし，実際は観し，これまで放射線量マッピングに関する測領域内に領域の近傍に観測点が存在しない
UAV 観測のための飛行計画に関する議論は領域が残り，地上分解能の向上の障壁となる．
ほとんど見当たらない．センサ技術の向上だ
この近傍に観測点がない座標の領域を欠損領
けでなく，UAV の経路計画も，時間効率と地域と定義する．Fig.１のようにウェイポイント
上分解能の実現に重要な役割を果たし，メーは各コーナーにしか配置されない場合，欠損トル単位で住宅地域に近い線量率の空間分
領域は風やUAV旋回半径の影響により障害物布を把握することが重要である．

回避のために飛行軌道が変動するため残る．
また，UAVはコーナーを曲がるとき，慣性が働くため側線間隔での移動は曲線を描き欠損領域が残る．要求する地上分解能に応じて一つ一つ設置した場合，UAVはひとつずつのウェイポイントを認識するため一時停止してしまい時間の効率が問題となる．
Fig1の例のように，白色のスキャンされていない領域は複雑な形状を形成する可能性がある．この例では，赤色の曲線は計測区間長が6mの条件での飛行軌跡であり，点線は計画されている経由点ルートを示している．風速は5m / s以下であっても，風と旋回半径の影響を受けた．つまり，欠損領域での経路計画は，効率的なUAV観測にとって重要である．

能も飛行経路計画に適合するが，欠損領域のウェイポイントがお互い隣接していないことがある．
3

提案手法

本研究は地上分解能を一定水準に保ったまま，時間効率の向上を目的とした Flood Fillと 2-opt の特徴を組み合わせたものである．
Flood Fill は欠損領域からウェイポイントルートを抽出するために適用し，経路計画のウェイポイント数の削減と UAV が通過できる効率的なウェイポイントルートを提供する．
一方，2-opt はすべてのウェイポイントルートを訪問し，最短経路を検索するための局所探索手法である．以下，本手法を３ステップに分けて述べる．
Step1：欠損領域の判定

Fig1．観測領域内の欠損領域
UAV 経路計画へのアプローチは，車両の経路問題の変形である連続監視問題（CMP）7)
8) である． CMP はもともと災害救助用に定義されたもので，各ポイントへの単純訪問ではなく，さまざまなポイントへの定期的な訪問を扱い，監視に使用される車両には，エネルギー容量によって移動時間が制限される．
この移動時間には，ポイント間を移動するのに必要な時間や写真を撮るなど，各ポイントにサービスを提供するのに必要な時間が含まれている．車両はエネルギー容量を更新するため帰還地点に帰る必要がある．CMP の目
的は，各車両のルートの順序を計算，関心のあるポイントへの訪問回数を最大にし，所定の計画期間中の訪問間の時間遅延を最小限に抑えることである．CMP は UAV 観測の問題におおよそ適合することができるが，UAVが通過するウェイポイントが長さおよび幅方向に一定の測定間隔で配置されるため，ある観測領域にわたって一定の地上分解を維持することは難しい．通過するウェイポイン
トは，継続的な監視のためのパス計画の最初の段階で固定されているため，欠損領域が残る可能性がある．
対照的に，Flood Fill は深さ優先探索であり，壁が検出されるまで直線的に移動することを優先するため，多くの迷路探索の解決アル
ゴリズムに組み込まれている 9) 10) 11)．しかし，Flood Fill は一般的に追加観測点が８方向の 1 つにお互い隣接しているウェイポイントに適用される．領域を走査するのに必要な機欠損領域とは Fig２のように検索半径𝑟内に観測点を含んでいない判定領域である．観測点は必ずしも判定領域付近であるとは限らず補間が必要であり，補間するため逆距離加重法を使用する 2) 3) 4)．逆距離加重法は指定された地点と観測点との距離による重み付け平均を用いて補間を行う方法である．この方法では検索半径内の観測データを用いて𝑆#$ の地点の属性値を求めるため，Fig２のように，検索半径内に一定数の観測点が必要である．判定領域𝑆#$ の中心から検索半径𝑟内に含まれる観測点の数がない領域𝑆#$ を欠損領域と定義する．長さ𝑙を辺に持つ判定領域を平面に配置し，各判定領域の座標を（𝑠# , 𝑠$ ）とする．𝑙は要求する最小地上分解能でありGPS デバイスなどのセンサの精度に基づいて決定される．検索半径𝑟内に位置する観測点はそれぞれ（𝑠# , 𝑠$ ）で計算し，観測点の数は𝑝#,$ で表す．欠損領域はリスト 1 のように，𝑝#,$ の観測点の数が判定領域𝑆#$ の標準値𝑐よりも小さい条件に基づいて判定する．特定された𝑆#$ のすべてのインスタンス
UnscannedAreas オブジェクトに追加され，次の飛行中に追加観測を行う座標のリストとなる．

Fig2．欠損領域の判定

Step2：欠損領域から追加観測点のマッピング
欠損領域𝑆#$ をウェイポイントとした場合，欠損領域は多く，UAV が通過できる範囲ではない．UAV が通過できる最小単位𝑡𝑠で観測領域をさらに区切り，欠損領域を含む領域の中心点を追加観測点𝑇,- とする．次のフライトの追加観測点を選択し，検索半径内の欠損領域を網羅する．座標（𝑡, , 𝑡- ）に位置する𝑇,は，地上解像度𝑙を辺に持つ欠損領域（𝑠# , 𝑠$ ）を覆うことができるようにするため，検索半径𝑟内に覆われる要素となる．すべての欠損領域を観測するため選択した𝑇,- の結果をウェイポイントとし設定する．
List1. ⽋損領域の判定// (1) counting the number of measured points
within the search radius
𝑗= 0
WHILE 𝑗 < 𝑗,12 DO
𝑘=0
WHILE 𝑘 < 𝑘,12 DO
𝑘=0
𝑐𝑜𝑢𝑛𝑡 = 0
WHILE 𝑖 < 𝑁 DO
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = sqrt ((𝑥? - 𝑠# )^2 + (𝑦? 𝑠$ )^2)
IF 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 ≤ 𝑟 THEN
𝑐𝑜𝑢𝑛𝑡 = 𝑐𝑜𝑢𝑛𝑡 + 1
ENDIF𝑖 =𝑖+1
ENDWHILE
𝑘 =𝑘+1
𝑝#,$ = 𝑐𝑜𝑢𝑛𝑡ENDWHILE
𝑗=𝑗+1
ENDWHILE// (2) Search of unscanned areas
UnscannedAreas = new Array []𝑗= 0
WHILE 𝑖 < 𝑗,12 DO
𝑘=0
WHILE 𝑗 < 𝑘,12 DO
IF 𝑝#,$ < 𝑐 THEN
𝑆#$ = True
UnscannedAreas.add (𝑆#$ )ENDIF
𝑘 =𝑘+1ENDWHILE
𝑗=𝑗+1
ENDWHILE
Output (UnscannedAreas)

3.1 Flood Fillと 2-optを用いた経路計画
選択した追加観測点は一定の間隔で置かれた追加観測点の集合が複数存在する．この一定の間隔で隣接する追加観測点の集合を判定し，飛行経路であるウェイポイントルートを生成するため Flood Fill アルゴリズムを適用する．Flood Fill アルゴリズムは迷路探索や領域内塗りつぶしなどの多次元配列内の特定のノードに隣接されている領域を決定するアルゴリズムである．Flood Fill アルゴリ
ズムから生成されたウェイポイントルートは欠損領域をくまなく走査することができる．しかし，ウェイポイントルートは最短距離経路ではない．ウェイポイントルート間の通過順序に 2-opt 法を適用し順序を入れ替えることにより最短距離経路を求める．2-opt法はあらかじめ決められた巡回路の内 2 つの枝の行き先と出発点を入れ替え，経路を再構築する改善法の一つである．2-opt 法はウェイポイントルートの出発地点と終了地点に適用する．
本研究では最初に，全ての追加観測点を網羅するまで Flood Fill を繰り返す Flood Fill の拡張について説明する．次に，Flood Fill により隣接し合う追加観測点をサブルートとした上で，2-opt によりサブルート間のウェイポイントルートの改善について説明する．
Step3-1：Flood Fill による飛行経路計画
Flood Fill は互いに隣接する観測点を一度に走査することができるため，1 組の V の集合に関する追加観測点の走査に有用である．
関数 Flood Fill（x,y,RouteLegs）は互いに隣接する追加観測点を走査し，UnscannedArea.get(𝑥, 𝑦)が呼び出され，現在の位置に追加観測点が存在するか判定を行う．隣接している追加観測点がある場合，この提案手法では，緯度，経度の順に次の追加観測点を走査する．
List2. Flood Fillの拡張による⾶⾏計画
FUNCTION FloodFill (𝑥, 𝑦, RouteLegs)
IF 𝑥 ≥ 0 && 𝑥 < 𝑥,12 && 𝑦 ≥ 0 &&𝑦 < 𝑦,12&& MissingArea.get (𝑥, 𝑦) == TRUE
THEN
𝑇2E = new waypoint (𝑥, 𝑦)RouteLegs.add (𝑇2E )ENDIF
FloodFill (𝑥 + 1, 𝑦)
FloodFill (𝑥 − 1, 𝑦)
FloodFill (𝑥, 𝑦 − 1)
FloodFill (𝑥, 𝑦 + 1)
FloodFill (𝑥 + 1, 𝑦 + 1)
FloodFill (𝑥 − 1, 𝑦 − 1)
FloodFill (x − 1, y + 1)
FloodFill (x + 1, y − 1)
RETURN 𝑇2E
EXIT
FUNCTION Main ()RouteLegs = new Array []// result offlood-filling
WHILE 𝑖 < 𝑖,12 DO

WHILE 𝑗 < 𝑗,12 DO
FloodFill (𝑖, 𝑗, RouteLegs)
𝑗=𝑗+1
ENDWHILE
𝑖 =𝑖+1ENDWHILE
WaypointRoute = RouteLegs
Output (WaypointRoute)
EXIT

Step3-2：2-opt による飛行経路計画
Step3-1 の方法では，隣接していない追加観測点間の経路は Flood Fill による塗りつぶし順のため，必ずしも最短経路ではない．そこ
で，提案手法は，隣接していない追加観測点のサブルート間の経路を 2-opt によりつなぎかえて改善する．隣接していない追加観測点のサブルートを経路計画のノードの最小単位，すなわち，ウェイポイントとする．
はじめに，FloodFill (𝑖, 𝑗)が関数 Main ()で呼び出される前後のウェイポイントを配列オ
ブジェクト WaypointRoute に格納する．すべてのウェイポイントが WaypointRoute に格納された後，関数 LocalSearch (WaypointRoute)で 2-opt を実行する．2-opt により経路をつなぎかえるときは，Path.reverseRoute (𝑖 + 1, 𝑗)
により，飛行経路のサブルートを逆順に並び替える．

WHILE 𝑖 < size − 2 DO
𝑖1 = 𝑖 + 1
𝑗=𝑖+2
WHILE 𝑗 < size DO
IF 𝑗 != size − 1 THEN
𝑗1 = 𝑗 + 1
ENDIF
IF 𝑖 != 0 OR 𝑗 != 0 THEN
length1 = distance (Path.get (𝑖),Path.get (𝑖1))length2 = distance (Path.get (𝑗),Path.get (𝑗1))length3 = distance (Path.get (𝑖),Path.get (𝑗))length4 = distance (Path.get (𝑖1),Path.get (𝑖1))IF length1 + length2 > length3 + length4
THEN
Path.reverseRoute (𝑖 + 1, 𝑗)count = count + 1
ENDIF
ENDIF
ENDWHILE
ENDWHILE
total += countIF count == 0 THEN BREAK
ENDWHILE
EXIT

4 実験
List3. Flood Fill-2-opt
FUNCTION Main ()𝑇?# = new waypoint (𝑖K , 𝑗K ) // initial position of the UAVWaypointRoute = new Array [] // result of
2-opt
RouteLegs = new Array [] // result offlood-filling
WHILE 𝑖 < 𝑖,12 DO
WHILE 𝑗 < 𝑗,12 DO
IF Waypoint (𝑖, 𝑗) == TRUE THEN
WaypointRoute.add (𝑇?# )𝑇?# = FloodFill (𝑖, 𝑗, RouteLegs)
WaypointRoute.add (𝑇?# )
ENDIF
𝑗=𝑗+1
ENDWHILE
𝑖 =𝑖+1ENDWHILE
LocalSearch (WaypointRoute)
WaypointRoute.merge (Clusters)
output(WaypointRoute)
EXIT
FUNCTION LocalSearch(Path)
total = 0
size = len (Path) − 1
WHILE TRUE DO
count = 0

本研究は，2017 年 4 月に推定コストと実コストのアルゴリズム比較のためのフィールドテストを実施した．観測場所は，福島第一原子力発電所の被災地から 10km 以内の森林に囲まれた住宅地である．
１）観測データ
UAV は 50m×50m の観測領域で飛行時間 10分，測線感覚 4m で観測点を取得した．最大風速は毎秒 2 メートル以下の条件で行なった．
UAV に搭載した放射線量検出機は，MPPC（マルチピクセルフォトカウンター）のCsl/TI シンチレータであり，線量率の変化後1 秒以内に誤差の 20%の観測点を記録する．
放射線量の住宅近くでの地上レベルの平均値は約 0.5µSv/ h であり，森林付近の平均値は約 1.0µSv/ h であった．

2）追加観測点の結果
観測領域内の 312 点の内，281 点の観測点が得られた．一方，残りの 31 点は，Fig3 の２回目の飛行で観測する追加観測点である．
ウェイポイントルートの結果から，互いに隣接する追加観測点は 6 組，分離された追加観測点は４点存在した．

Table１経路計画アルゴリズムの比較
処理
旋回回
推定実時間数
コスト コスト(≥90 度)2-opt

12340 sec 464 sec

0.1 sec

Flood Fill

12436 sec 595 sec

9.7secFig3．２回目の飛行で観測する追加観測点

提案⼿法

8302 sec 380 sec

8.9 sec

3）UAV 経路計画の比較結果
Fig4(a)に示す最初の結果は，巡回セールスマン問題のためのアルゴリズムで典型的に効率的な組み合わせである Greedy 法によって得られる初期配置を適用した経路を，2-optによって最適化した経路である．推定コストは 85 秒で得られたが，180 度以上の急激な旋回が少なくとも２回存在した．
Fig4(b)の結果は，Step3-1 で説明した FloodFill の飛行経路である．最初の結果よりも鋭い旋回の数が少なくなるが，推定コストは109 秒であり，特に 2 つ隣接するウェイポイント間の長い飛行が得られた．
3 つ目の結果は，提案手法によるウェイポイントルートと対応するウェイポイントを組み合わせたものである．Flood Fill で計算されたウェイポイントルートは Fig４(c)の太線で，2-opt で示された経路は赤色の細線で示されている．推定コストは 77 秒で，90 度以上の旋回は 8 回で他の結果に比べ少ない旋回の経路を得られた．

5４)推定コストと実コストの差異
Table１の実験結果から，Flood Fill によって計算された経路の実コストは推定コスト
より 159(sec)，2-opt 法は 124(sec)，提案手法は 78(sec)の時間を要した．主な理由は，UAVが 90 度の旋回後に飛行経路を修正する必要があったことである．急な旋回は実コストにとって重要な要素であることがわかった．

結論

本稿は，UAV 観測に短時間で一定の観測点を得られる Flood Fill と 2-opt を組み合わせた手法を提案した．提案手法はウェイポイントル
ートを抽出し，局所探索を適用してウェイポイントルート上の最短経路を求めることができる．実験から，実コストは旋回回数の影響を受けることがわかった．提案手法は，飛行経路の旋回回数を抑え，観測地点で効率的な経路計画を生成した．Greedy 2-opt，FloodFill，提案手法を比較し，UAV 経路計画の効率的な適用について検討した．原子力災害の影響を受けた領域付近の放射線量マップを用いた実験結果から，UAV 飛行の実コストの主な要因の 1 つは旋回回数であった．2-optは隣接しない分離しているウェイポイントに対して適用することができ，対照的に，Flood Fill は一様に隣接するウェイポイントを含む経路に良い結果を生み出した．
本研究は，2-opt は時間効率と推定コストの両方のために適用した．ただし，クラスタの数や隔離によっては，経路計画の最適なアルゴリズムが異なる場合がある．今後の課題として，観測領域の大きさや旋回回数などの実験条件を考慮した実験を行う．

謝辞
本研究は精密測定技術振興財団の助成を受けたものです．

参考文献
1).

2).

(b)：Flood fill(a)： 2-opt(c)：提案⼿法
Fig4．アルゴリズム適用後の経路トポロジ

3).

4).

Japan Atomic Energy Agency, “Airborne Monitoring in theDistribution
SurveyofRadioactiveSubstances,”
http://emdb.jaea.go.jp/emdb/en/portals/b224/ (accessed 28
Mar 2017).
Y. Sanada, T. Sugita, Y. Nishizawa, A. Kondo and T. Torii,“The aerial radiation monitoring in Japan after the Fukushima
Daiichi nuclear power plant accident,” Progress in Nuclear
Science and Technology, vol.4, pp.76-80, 2014.
Y. Sanada and T. Torii, “Aerial radiation monitoring aroundthe Fukushima Dai-ichi Nuclear Power Plant using anunmanned helicopter,” Journal of EnvironmentalRadioactivity, vol.139, pp.294–299, 2015.
K. Oyama, H. Wakabayashi, A. Takeuchi and N. Ishitsuka,“Integration of 3D Trajectory Maps into a Local Distribution
Map of Radiation Dose Using Unmanned Aerial Vehicle,”

5).

6).

7).

8).

9).

10).

11).

36th IEEE Annual Computer Software and Applications
Conference Workshops (COMPSACW), pp. 607-612, 2012.
P.G. Martin, O.D. Payton, J.S. Fardoulis, D.A. Richards, Y.
Yamashiki and T.B. Scott, “Low altitude unmanned aerialvehicle for characterising remediation effectiveness following
the FDNPP accident,” Journal of Environmental
Radioactivity, vol.151, pp.58-63, 2016.
J. Jiang, K. Shimazoe, Y. Nakamura, H. Takahashi, Y.
Shikaze, Y. Nishizawa, M. Yoshida, Y. Sanada, T. Torii, M.
Yoshino, S. Ito, T. Endo, K. Tsutsumi, S. Kato, H. Sato, Y.
Usuki, S. Kurosawa, K. Kamada and A. Yoshikawa, “Aprototype of aerial radiation monitoring system using an
unmanned helicopter mounting a GAGG scintillator
Compton camera,” Journal of Nuclear Science andTechnology, vol.53(7), pp.1067-1075, 2016.
V. Mersheeva and G. Friedrich, “Routing for continuous
monitoring by multiple micro UAVs in disaster scenarios,”
Proceedings of the 20th European Conference on Artificial
Intelligence (ECAI), pp. 588–593, 2012.
S. Mishra and P. Bande, “Maze Solving Algorithms for
Micro Mouse,” IEEE International Conference on Signal
Image Technology and Internet Based Systems (SITIS), pp.
86-93, 2008.
J. Valente, A. Barrientos, J. del Cerro, C. Rossi, J. Colorado,
D. Sanz and M. Garzón, “Multi-robot visual coverage path
planning: geometrical metamorphosis of the workspace
through raster graphics based approaches,” In Proc. of the2011 international conference on Computational science andits applications (ICCSA), pp.58-73, 2011.
T. Pereira, M. Veloso and A. Moreira, “Multi-robot Planning
Using Robot-Dependent Reachability Maps,” Proc. of Robot
2015: Second Iberian Robotics Conference: Advances inRobotics, pp.189-201, 2016.
Sathyan, N. Boone and K. Cohen, “Comparison ofapproximate approaches to solving the traveling salesman
problem & its application to UAV swarming,” International
Journal of Unmanned Systems Engineering (IJUSEng), vol.
3(1), pp.1-16, 2015.