47

潮流場における自律型水中ビークルの最適経路計画
学生員

白 石 耕 一 郎∗

正員

木 村

元 ∗∗

Optimal Path Planning of an Autonomous Underwater Vehicle in a Sea Current Field
byKoichiro Shiraishi, Student Hajime Kimura, Member

Summary
Path planning of an autonomous underwater vehicle is one of the most important problems to reduce energy
consumption and to navigate safely. Since there exists more or less sea current in most of underwater environments,
a current disturbance becomes resistance and a factor to increase the energy consumption according to a directionof motion of AUV. Thus path planning considering a sea current ﬁeld make possible an improvement of energy
consumption. In this paper, optimal path planning considering energy consumption for AUV is formulated as ashortest path problem in Graph Theory. Solution of the formulated problem is obtained by Dijkstra’s Algorithm which
is an algorithm to ﬁnd the shortest paths in a weighted, directed graph. The eﬀectiveness of the proposed method
is veriﬁed through numerical simulation in several current ﬁelds with obstacles. Furthermore, authors propose atriangular panel interpolation method for the purpose of applying this technique to measurement data of sea current
ﬁelds. The method uses the Delaunay Triangulation to generate triangular panels from data points scattered at
random. Then sea current data at an arbitrary point are interpolated using triangular panels generated.

1. 緒 言近年、地球温暖化や異常気象など深刻な環境問題が発生しており、それらの問題の解決策を見つけるために海洋環境のモニタリ
ング体制の強化が望まれている。地球温暖化のメカニズムを解明するためには、様々な海域における海水サンプルを採取し、塩

分濃度、水温等の海洋データを収集することが重要である。しかし、広大な海洋でモニタリングを行うには膨大な時間と多額の費用がかかるため、効率的なモニタリングシステムの開発が要求されている。そこで、海洋調査を自律的に行うことが可能な新しい手段として自律型水中ビークル (Autonomous Underwater
Vehicle : AUV) が開発されており、海水のサンプリングだけでなく、自律して海洋調査が行えるという特長を活かし、船舶では観測が困難な海底火山周辺の調査にも活用されている。

AUV は支援船から海中に投入され、調査する海域もしくは海底火山へ移動する。その場合にどのような経路に従って航行するのかを設定しなければならない。また AUV は情報転送やエネル

ギー供給用のケーブルを持たないというシステム上の特徴により高い作業性と運動自由度が確保できるが、任務途中のエネルギー補給が困難であるため、長時間計測のためにはエネルギー消費をできるだけ抑えた経路計画が要求される。海中環境には、AUV∗∗∗

九州大学大学院 工学府海洋システム工学専攻

九州大学大学院 工学研究院海洋システム工学部門

原稿受理
原稿受理 平成平成20
年年月3 月日14 日のエネルギー消費を大きく変化させる要因の 1 つである潮流が存在する。潮流の流れる向きが AUV の進行方向と同じになる場合には、潮流の影響によって AUV を進行方向に押し出す力が働き、この力によって AUV のエネルギー消費を抑えることができる。しかし、AUV の運動の方向と潮流の向きが逆になる場合

は、潮流は AUV に進行方向と逆の向きの力、すなわち押し戻す力が働くため潮流は抵抗成分となりエネルギー消費を増大させてしまう。このため AUV が潮流の存在する海域で航行する場合、AUV の航行経路の選択により所要時間やエネルギー消費に大きな差が生じる。したがって、AUV の航行域の潮流分布を考慮した経路計画を立てることによって、AUV のエネルギー消費を抑えることが可能となり、航行時間の改善を図ることができる。また海底でのサンプリングのように障害物が数多く存在し、潮流が複雑な流れをしている海底付近や入り組んだ入り江のような場所
で AUV が海中作業を行う場合、AUV が潮流に流されて障害物に衝突し破損する可能性が高くなる。そのような事態を極力避けるためにも潮流分布を考慮し、安全に移動できる経路計画が必要である。
従来、陸上における移動ロボットの経路計画を行うために多くの手法が提案されてきた 1) 。これらの手法を用いることで、陸上の移動ロボットが障害物と衝突せずに目的点へ最小時間で到達できる経路計画を行うことが可能であり、これらは AUV の経路計画にも適用可能な方法である。しかし、これらの手法は衝突回避に重点を置いており、AUV のように衝突回避だけでなく、潮流によるエネルギー損失を考慮した経路計画を行うことはできない。潮流場におけるエネルギー消費を考慮した AUV の経路計画

日本船舶海洋工学会論文集 第 7 号

48

について次のような研究が行われている 2)3) 。金らは AUV の

経路計画問題を 2 点境界値問題として定式化し変分法を適用することで、流れ外乱を考慮した最適経路を求めている 2) 。この方法によって AUV の経路を連続値で扱うことが可能であるが、障害物との衝突を考慮することができないため衝突を回避した経路を求めることができない。Alvarez らは遺伝的アルゴリズム(Genetic Algorithm : GA) を用いた AUV の経路計画を行っている 3) 。この研究では AUV の経路を遺伝子の個体群として表現することで経路計画問題に GA を適用している。そして三次元空間での潮流や時間変化を想定した最適経路探索を行い、経路

2008 年 6 月

ことである。最適経路計画問題とは経路計画において、AUV のエネルギー消費を最小とする経路を見つけることである。ここで問題設定として AUV は定常速度で航行するとし、AUV の稼動領域である海洋空間は格子点で構成されているとする。ただし、AUV は対地速度が常に一定になるように推力が制御されるとする。AUV の運動特性は考えず、到着日時は指定されていない。
また AUV は二次元平面を移動するとし、潮流場は二次元定常潮流場とする。
2.1

エネルギー消費の定式化

計画問題における GA の有用性を示している。しかし、GA は潮流を考慮した AUV のエネルギー消費のコスト関数としてAlvarez3) が提案している次式を用いる。

在する可能性がある。また経路設計の問題設定を多段決定問題とエネルギー消費のコスト関数：

最適解を保証していないため求められた経路よりも優れた解が存しているため、多数の障害物が存在する複雑な経路やエネルギー

消費を抑えるために潮流の流れに沿うような複雑な曲がりや後戻りするような経路を探索することは難しい。

以上のように、障害物との衝突回避のみ、もしくはエネルギー

消費のみを考慮した経路計画に関する研究は数多く行われているが、両方とも考慮した経路計画に関する研究は、著者が知る限りでは皆無である。そこで本研究では、衝突回避と潮流分布を考慮した AUV の経路計画を最適経路計画問題として取り扱う。まず

最適経路計画問題をグラフ理論における最短経路問題として定式化を行い、後戻りや複雑に曲がるような経路計画を行うことを目的としている。最短経路問題を解く方法として、出発点からすべての点への最短距離と最短経路を求めることが可能な Dijkstra

法 (ダイクストラ法) を適用する。また提案手法によって得られた解の性能を比較するために、多段決定問題として定式化を行い、動的計画法を適用する方法を用いる。そして 2 つの手法を、
潮流分布を考慮したシミュレーション環境へ適用し、探索した最適経路を比較することによって提案手法の有用性を検証する。

また提案手法を実測データへ適用する場合、不規則に並んだ潮流データから潮流場を生成する必要があるが、著者が調べた限りに

Ji (pathi ) =2.2の点集合を最適な三角形分割を求めることが可能な三角形分割法である。そして、提案する潮流の補間方法を潮流の実測データへ適用し、得られた潮流場において AUV の最適経路探索を行うことで提案手法の有用性を示すことも目的としている。

本論文の構成は、まず AUV の最適経路計画問題の定式化について説明する。次に最適経路計画問題を多段決定問題とグラフ理� Vi (x, y) �3 dxdy

(1)

最適経路計画問題の定式化

AUV のエネルギー消費を最小とする最適経路計画問題は、(1)式を用いて次のように定式化される。
最適経路計画問題

おいて、このような潮流データを補間して潮流場を生成する方法

形パネル補間法を提案する。Delaunay 三角形分割とは、平面上

ρpathi−1 c

ただし、Vi (x, y) = cei − vc (x, y) は AUV と潮流の相対速度、ei は AUV の単位速度ベクトル、vc (x, y) は潮流の速度ベクト
ル、c は AUV の定常速度、ρ は流体の密度、pathi は i 番目に通る AUV の経路とする。
このコスト関数は、AUV の航行によって移動した流体の運動
エネルギーをエネルギー消費の基準として定められている。この
流体エネルギーが大きいほど AUV は周りの流体に多量のエネル
ギーを与えて航行していることになり、潮流に逆らって効率が悪い航行をしていることになる。よってエネルギー消費のコスト関
数は AUV 周辺の変化流量と AUV の潮流に対する相対速度を用いて表すことができる。

min Cost(Path)は存在しない。そこで、不規則に並んだ潮流データの補間方法として Delaunay 三角分割 (ドローネー三角形分割) を用いた三角Z Z pathi

Path

ただし、

Cost(Path) =mX

Ji (pathi )

(2)

(3)

i=0

Path = {path0 , path1 , . . . , pathi , . . . , pathm }(4)である。Path は出発点から目的点までの経路となる節点集合、

動的計画法、Dijkstra 法の適用方法について述べる。そして提Cost(Path) は出発点から目的点までの AUV のエネルギー消費量である。よって (2) 式を満たす経路が AUV の最適経路となる。

として定式化した場合との 2 つの方法で最適経路探索を行った結3. 最適経路問題の問題設定論における最短経路問題として定式化し、解を求める方法として案手法である最短経路問題として定式化した場合と多段決定問題
果を示す。また実測データへの適用するための潮流データの補間方法である Delaunay 三角分割を用いた三角形パネル補間法について述べ、その方法を実測データへ適用することで潮流場を生成し、AUV の最適経路探索を行うことで提案手法の有用性を検証する。

2. 最適経路計画問題
経路計画とは出発点と目的点を決め、その間の経路を設定する

本研究では前節で定式化した最適経路計画問題に対して 2 つの問題設定し、それぞれの問題において最適経路を探索する。その1 つは Alvarez 3) が用いた多段決定問題として定式化し、動的計画法を適用して最適経路を求める方法である。もう 1 つは本研究で提案する方法で、最適経路計画問題をグラフ理論における最短経路問題として定式化し、最適経路を求める方法である。そして最短経路問題の解を求める方法として Dijkstra 法を用いる。

潮流場における自律型水中ビークルの最適経路計画
3.1

49の総和が最小となる経路を求めるものである。この問題はカーナ

多段決定問題

最適経路計画問題を、多段決定問題として定式化するために、

次の制約条件を加える。

ビゲーションシステムで今の場所から目的地への最短の道順の探索などにも利用されている。

そこで最適経路設計問題においてエネルギー消費のコスト関数

制約条件

AUV は x 軸方向に 1 ステップで一定距離 ∆x だけ進むとする。つまり、すべての経路において xi+1 = xi + ∆x という関係が必ず成立するということである。ここで ∆x は AUV の移動空間である格子空間の格子間距離である。この条件は障害物が数多く存在する海底近くや潮流が強く複雑な流れをしている海域など前進できない場合が生じる場合には成立しない。しかし、このような変化の大きい海域は限られている。一般的な海洋を考える場合、この条件によって到着時間の制約を満たす経路を探索することができ、さらに経路の探索空間を小さくすることができる。最適経路計画問題は、制約条件を入れることによって多段決定問題として次のような関数方程式を用いて定式化することができる。

を重み関数とした重みつきグラフと考え、また AUV の経路がネットワーク上に広がっていると仮定すると最短経路問題として定式化することができる。最適経路計画問題を最短経路問題と考えるために、AUV は次のステップで現在地点に隣接する８点の全てに到達できるとする。この設定によって AUV は前後左右斜めのどちらにも進めるようになるので多段決定問題の場合よりも経路選択の自由度が増え、多様な経路設定することが可能である。また AUV の移動範囲を設定したことによって、AUV の

経路は Fig.2のようなネットワーク上に生成される。またネット

ワーク上の節点間における重み関数に最適経路計画問題におけるエネルギーのコスト関数を用いることによって最適経路計画問題
をグラフ理論における最短経路問題とし考えることができ、最短経路問題の解を求める手法の 1 つである Dijkstra 法を実装する

多段決定問題の関数方程式ことが可能となる。

F (x, y) = min {wyi (x, y) + F (x + 1, yi )}0≤yi ≤n

(5)
START

境界条件

F (xg , yg ) = 0

(6)
GOAL

ただし、F (x, y) は節点 (x, y) から goal(xg , yg ) までの最小のコスト、wyi (x, y) は節点 (x, y) から x 軸方向に１ステップ進

み y 座標が yi の節点に移動したときのコストとする。

3.2

ࡆ࡯ࠢ࡞ߩ⚻〝

動的計画法

多段決定問題に動的計画法 4) を適用することで、(5) 式における最適経路を求める。動的計画法とは、Bellman によって提案された最適化問題の解法であり、適用範囲の広い手法である。次ࡆ࡯ࠢ࡞ߩⴕേ▸࿐

Fig. 2 Path network of AUV
前節の AUV の移動範囲と経路ネットワークの設定に基づいに述べる Bellman の最適性原理は、動的計画法による数値解法て、関数方程式を用いて最適経路計画問題を最短経路問題として

程において、最適政策はシステムの最初の状態と最初の決定がど

最短経路問題の関数方程式の基礎をなす重要な定理である。最適性の原理とは「多段決定過んなものであれ、残りの決定は最初の決定によって生じた状態に関して、その後もまた最適政策を構成していなければならない」というものである。

F (vi ) = min {w(pr , vi ) + F (pr )}0≤r≤8(pr ∈ P(vi )) (7)境界条件

F(x+1,yi+1)
F(x+2,yi+1)
w4(x,yi+1)
w4(x+2,yi+1)
F(x,yi)F(x+1,yi)w0(x,yi-3)

F(x+2,yi)F(x+1,yi-3)

F (v0 ) = 0

F(x+2,yi-3)

最短経路問題

最短経路問題 5) はグラフ問題の 1 つである。重みつきグラフが与えられたときに、任意の 2 頂点を結ぶ経路の中から枝の重み(8)

ただし、vi = (xi , yi ) は経路ネットワーク上の節点、P(vi ) ={p0 , · · · , p8 } は点 vi に隣接する 8 点の集合、pr は節点 vi の隣接点、F (vi ) は出発点 v0 (x0 , y0 ) から節点 vi (xi , yi ) までの最小のコストの和、w(pr , vi ) は節点 pr (xr , yr ) から、節点 vi (xi , yi )に移動した時のコスト（重み関数値）とする。

3.4

w0(x+2,yi-3)

Fig. 1 Multistage decision problem

3.3

以下のように定式化する。

Dijkstra 法

Dijkstra 法 6) は、1959 年に E.Dijkstra によって提案された手法で、ネットワーク内のすべての節点に接続している節点とその間を結ぶ枝のコストが分かるとネットワーク全体の構成を知ることができる。その接続状態の情報を用いて目的の節点までのコストが最も小さくなるような経路を計算し、最短距離（最小コスト）と最短経路と求めることができる手法である。ただし、全ての枝において重みの値が負の枝が存在する場合は使用することができない。

日本船舶海洋工学会論文集 第 7 号

50

次に Dijkstra 法のアルゴリズムの概略を示す。ここでのコス

ト値はグラフの枝の重みの和を表す。

1. 出発点のコスト値を 0、それ以外の節点は無限大とし、出発点を探索点とする。

Fig.4より Dijkstra 法では後戻りするような経路を探索可能にしている。また、経路の自由度が増えたことにより複雑な渦の流れに沿ったエネルギー消費の小さい経路も探索できている。
Table 1 Cost Function (Case1)
Case1
Cost Function Calculate Time
Straight
42531
13708
Multistage
1553
17219
Dijkstra965
55360

2. 探索点に隣接する節点において、その節点のコスト値と探索点のコスト値と探索点と隣接点の間の枝の重みを足したもののどちらか小さい方の値に変更する。
3. 2 の操作を各隣接点において行い、その隣接点を探索中リ
ストに加え、探索点を探索終了リストに加える。そして、探索中リストの中で最もコスト値が小さい節点を新しい探索点とする。

35

4. 2,3 の操作を繰り返し、 すべての点が探索終了リストに加わったら終了である。

前の節点番号を記憶させておき、目的点から順に遡ることで最短

20[km]30

Dijkstra25

その結果、各点のコスト値が始点からのその点まで移動するのにかかる総コスト、つまり最短距離となる。また節点に対して 1 つyMultistage
GOAL

20
15

経路も求めることができる。ここで述べた Dijkstra 法を用いてStraight

最短経路問題 (7) 式の最短経路を探索する。

10

4. 定常潮流場における最適経路探索

5

本研究では、Alvarez3) らが用いた多数の渦が存在する複雑0な潮流場において最適経路探索を行った。探索方法は最適経路

START

0

5

4.2

30
25

35

15
10

30

5

25
10

15

x

20

25

30

35
20[km]Fig. 3 Current ﬁeld

35
20[km]yFig.3の潮流場において、START(5,5),GOAL(30,25) とし

5

適経路、Table1は START から GOAL までのコスト関数の和0と経路探索の計算時間を示している。

Table1より直線に航行するよりも経路探索を行った経路の方がエネルギー消費を抑えることができていることが分かる。またSTART

c = 1.0 m/s

GOAL

c = 2.0 m/s

1510て最適経路探索を行った。Fig.4は経路探索によって得られた最20[km]20

複雑な渦の存在する潮流場における探索結果 (Case1)

4.1

30

定常速度を変化させた場合の探索結果 (Case2)

y 20

5

25

Table 2 Cost Function (Case2)
Case2
Cost Function Calculate Timec = 0.5 m/s
2725
102484c = 1.0 m/s
13714
58453
c = 2.0 m/s
87007
41488

35

0

20

AUV の定常速度を変えることによって探索される経路がどのように変化するか調べるために、定常速度 c を 0.5,1.0,2.0[m/s]として最適経路探索を行った。START(3,18),GOAL(32,18) として、Case1 と同じ潮流場において Dijkstra 法を用いて最適経路探索を行った。

20[km]0

15

Fig. 4 Optimal Path (Case1)

短経路問題として解いた場合 (Dijkstra)、そして最短距離で目

Fig.3の格子点間の距離 ∆x は 20km である。流体の密度 ρ は1025.0[kg/m3 ]、潮流のオーダーは 0.5[m/s]、AUV の定常速度 c は 0.5[m/s] と設定した。計算機環境は、OS:Windows,
CPU:Pentium4 3.0 GHz, Memory:512MB, プログラム言
語:JAVA を用いて数値実験を行った。また各 Table の単位は、Cost Function は [J]、Caluculate Time は [ms] とする。

10x計画問題を多段決定問題として解いた場合 (Multistage)、最的点に到達するために直進した場合 (Straight) の 3 つである。

2008 年 6 月

c = 0.5 m/s

0

5

10

15

20

25

x
Fig. 5 Optimal Path (Case2)30

35
20[km]潮流場における自律型水中ビークルの最適経路計画
Table2より定常速度が速くなるにつれてエネルギー消費が指数関数的に増加している。また、定常速度が増加するにつれて航行距離を短くするような経路になっているのが Fig.5より分かる。これは潮流によって損失するエネルギーよりも AUV が航行することで消費するエネルギーの方が大きくなるので、潮流に逆らってでも航行距離を短くした方がエネルギー消費が小さくなるからである。
多数の障害物が存在する潮流場における探索結果 (Case3)

4.3

次に Case1 の潮流場に Fig.6のような多数の小さな障害物を配置し、START(2,30),GOAL(33,5) として経路探索を行った。このシミュレーションは、多数の島が存在するような海域をAUV が航行する場合を想定しており、多数の障害物を回避しながら潮流の流れに沿った経路を探索可能か検証することを目的としている。また、Dijkstra 法の探索領域を変えることで、解の質がどのように変化するかについても検証する。これまでは隣接する点に移動するとしていたが、この場合は 3 点先まで移動できるとする。Dijkstra 法による隣接 8 点探索を Dijkstra range1、3 点先までの近傍 48 点探索を Dijkstra range3 とする。
Fig.6より、すべての探索手法で障害物を回避した経路を探索できていることが分かる。Fig.6と Table3から分かるように、渦の中心付近に障害物が存在するが Dijkstra 法では渦の流れに乗ることで障害物を迂回しても多段決定問題よりもエネルギー消費の小さい経路を探索できている。また AUV の移動範囲を広げる
ことによって探索可能な経路の範囲も広がり経路の組み合わせも増えるため、さらに潮流に沿った経路を探索できている。しかし移動範囲が隣接 8 点から近傍 48 点になることによって探索領域が広がり、それに伴って計算時間も増加している。

行った。これは AUV が入り江の周辺を航行する場合を想定したものである。AUV の目標点が入り江の内側にある場合は、Fig.7のように狭い入り口を通る必要がある。このような条件でも経路探索が可能であるか検証するためにシミュレーションを行った。
この場合、ゴールにたどり着くためには、必ず後戻りしなけ

ればならない。多段決定問題では 1 ステップで必ず x 方向に

1 進むという制約があるため、後戻りするような経路は探索できない。従って多段決定問題では GOAL にたどり着く経路を求めることはできない。しかし、Dijkstra 法は隣接する点を全て探索するので、後戻りするような経路でも探索が可能である。
Fig.7、Tab.4より、GOAL が障害物で遮られていても後戻りして GOAL に到達し、潮流場を考慮した妥当な経路を探索できている。また Dijkstra range3 は Dijkstra range1 よりも多様な経路を探索できるため、移動コストの小さい経路を得ている。
Table 4 Cost Function (Case4)
Case4
Cost Function Calculate TimeMultistage
Impossible
Impossible
Dijkstra range1
28068
398328
Dijkstra range3
23813
1986109
20[km]

35
30
25

y

20
15

Multistage

0

Dijkstrarange_3

4.5

START

0

5

10

15

x

20

25

30

35
20[km]

潮流場に迷路が存在する場合の探索結果 (Case5)

Case1 の潮流場に迷路のような複雑な障害物が存在する場合にDijkstrarange_1

を動的計画法と Dijkstra 法を用いて探索した。このシミュレー

ションは、気象条件が悪く AUV が航行できない海域が存在する

場合や複雑に入り組んだ海岸付近を航行する場合を想定したものでである。Fig.8のように、後戻りを何度も繰り返す必要がある

5

迷路のような環境下でも経路探索が可能か検証することを目的と

GOAL

0

Obstacle

Dijkstra range1
Dijkstra range3

おいて、START を (5,30),GOAL を (23,30) として最適経路

Obstacle

1005Fig. 7 Optimal Path (Case4)

30

y

10

20[km]

25

GOAL

START

20
15

Table 3 Cost Function (Case3)
Case3
Cost Function Calculate TimeMultistage
3901
28422
Dijkstra range1
3482
433937
Dijkstra range3
2664
1330453

35

51

5

10

15

x

20

25

30

35
20[km]Fig. 6 Optimal Path (Case3)

している。

多段決定問題では直接 GOAL までの経路を求めることは不可能であるので場合分けなどの操作が必要である。一方、隣接点・近傍点を探索する Dijkstra 法では迷路のような複雑な経路探索

でも START から GOAL までの経路が存在するのであれば、

4.4

GOAL が障害物で囲まれている場合の探索結果 (Case4)

Case1 の潮流場に GOAL を遮る障害物が存在する場合において、START を (5,18),GOAL を (20,18) として経路探索を

GOAL に到達する経路を探索し、さらに潮流場を考慮した妥当な解を求めることが可能である。

日本船舶海洋工学会論文集 第 7 号

52

Table 5 Cost Function (Case5)
Case5
Cost Function Calculate TimeMultistage
Impossible
Impossible
Dijkstra range1
41721
106485
Dijkstra range3
39971
1608250

2008 年 6 月

から生成される三角形パネルによって 3 点間の潮流を補間する。

(x, y) 平面からデータが与えられている任意の 3 点を選び、その3 点によって定まる三角形パネルの平面の式を求める。平面の式
は次のように定める。
三角形パネルの平面の式
ax + by + z + c = 0(9)20[km]35

ただし、任意の 3 点のうち少なくとも 2 点が一致することはない

GOAL

START

とする。なぜなら場所が同じならば定常潮流場では、潮流は同じ30になるからである。上式に 3 点を代入し三元連立一次方程式を立25yて、その解から平面の方程式を決定する。よって (9) 式より任意の点での潮流を三角形パネルの方程式から求めることができる。

20

5.2

15

前節で三角形パネル補間法による潮流の補間方法を述べたが、データ点は離散的に広がっているためデータ点を三角形分割の仕

10
5
0

三角形分割

方はデータ点に比例して増えていく。さらに三角形分割の仕方によって補間した値に大きな差が生じるという問題が発生する。 上

Dijkstra range1
Dijkstra range3

0

5

10

15

x

20

25

30

35

20[km]Fig. 8 Optimal Path (Case5)

潮流は連続的なデータとして測定することは難しく、離散した測定点のデータがほとんどである。そのため潮流データを扱う場

合、何らかの補間操作を行う必要がある。潮流は現在でも解明さ














S






S




5. 実測データへの適用










㜞ߐ


C














㜞ߐ






D

Fig. 10 Error margin by a triangulation
図から分かるように、三角形の内角に小さな角度を含む場合の三れていない部分が存在し、数値計算によって潮流の値を求めるこ角形分割は三角形パネル補間法に適していない。よって三角形分しない。しかし、現段階では有効な潮流の補間方法は確立されてした三角形分割であるといえる。三角形分割の最小角度を最大にとは困難であるので、測定したデータから補間する方法しか存在いない。そこで本研究では、海中に何らかの潮流場が存在していると仮定し、その潮流場を離散的な潮流データから補間して求める。そのために、ある xy 平面において潮流を z 軸にとることによって潮流の三次元空間を生成する。これによって地形図の近似手法である標本点の集合から多面体地形図を生成する方法 7) を潮流場の補間に適用し、潮流の測定点から潮流場を生成することができる。本研究では、この多面体を三角形パネルから生成し、三角形多面体パネルから潮流を補間する方法を提案する。本研究では、この潮流補間法を三角形パネル補間法と呼ぶことにする。
$

$

z

z

ax+by+z+c=0

$

$
%

%

#

%

#

する三角形分割として、Delaunay 三角形分割 7) といものが定義されている。Delaunay 分割とは、各三角形の最小角が最大になるような三角形分割である。各三角形の外接円の中に他の三角形の点が一つも存在しないことが実現できれば、最小角が最大になる条件が満足される。この Delaunay 三角形分割を得る方法
として逐次添加法というものがある。これは三角形分割する点集
合を全て含む大きな三角形を考え、その三角形の中に点集合から任意の点を加えていき角度最小となる三角形分割を得るというものである。よって本研究では離散的に得られた潮流データ点を逐次添加法を用いて Delaunay 三角形分割する。そして、任意の点が包含される三角形において三角形パネル補間法を用いて任意の点の潮流を求める。Fig.11は、ランダムに発生させた点集合に#[y割の最小角度を最大にする三角形分割が三角形パネル補間法に適逐次添加法を用いて、Delaunay 三角形分割を得た例である。

%

#

x

x

Fig. 9 Polyhedron panels (left) and Triangle
panel (right)

5.1

三角形パネル補間法

潮流場において x 座標、y 座標、潮流の x 方向成分 (y 方向成分) を z 軸方向にとることで三次元空間と考え、任意の 3 点

Fig. 11 Points generated at random (left) and
Plane triangulation generated by Delaunay trianglation (right)

潮流場における自律型水中ビークルの最適経路計画
5.3

実測データから潮流場を生成

実測データにから生成された潮流場において最適経路探索を行う。START を (5,30)、GOAL を (23,30)、直進した場合とAUV の最適経路問題を多段決定問題、及び最短経路問題として定式化し経路探索を行った結果と比較する。Table6より、実測データにおいても経路探索によってエネルギー消費が改善されていることが分かる。この場合は多数の渦が存在する複雑な潮流場
ではないため問題設定による解の差はあまり出ていないが、実測データにおいても潮流データを補間することで最適経路を探索できていることが分かる。

Table 6 Cost Function (Case6)
Case6
Cost Function Calculate Time
Straight
6271
8719
Multistage
5934
11562
Dijkstra
6017
52875

20[m]

35
30
25

y

実データの潮流場における最適経路探索 (Case6)

5.4

Fig.12は、JAMSTEC から提供された三陸海岸沖の東 300km、
深度 17m 付近における潮流データである。このデータは 2001
年 7 月 16 日に観測されたもので、航海番号は MR01-K03 である。Fig.12の格子点間の距離は、縦 20m、 横 40m である。
この実測データに提案手法である Delaunay 三角形分割を用いた三角形パネル補間法を用いて潮流場を生成する。Fig.13は、Delaunay 三角形分割を用いて生成した実測データにおける測定点の三角形分割である。そして Fig.14は、得られた三角形パネルにおいて三角形パネル補間法を適用することで生成された潮流
場である。

53

20
15

35

10

30

5

20[m]

Dijkstra

START

25
0

0

5

10

15

x

20

25

30

35
40[m]

Fig. 12 Measured data at Sanriku coast oﬃng

20
GOAL
15
10

20[m]

35yyStraight

30

5

25

0

20

Multistage

0

5

10

15

x

20

25

30

35
40[m]

Fig. 15 Optimal path (Case6)

15
10
5
0

6. 結言
0

5

10

15

20

25

30

x

35
40[m]

Fig. 13 Delauney triangulation of mearured data
points20[m]

35
30
25

y

20
15
10
5
0

0

5

10

15

x

20

25

30

35
40[m]

Fig. 14 Interpolated current ﬁeld in the measured
data

本研究では、AUV のエネルギー消費を考慮した最適経路

計画問題をグラフ理論における最短経路問題として定式化し、Dijkstra 法を適用することによってエネルギー消費が最小となる経路を探索可能にした。また迷路のように複雑な障害物が存在する潮流場においても、Djikstra 法を用いた経路探索によって複雑に曲がり後戻りするような最適経路探索を可能にした。そして、潮流データの補間方法として Delaunay 三角形分割を用いた三角形パネル補間法を提案し、実データに適用することで有用性を検証した。経路探索に必要な計算時間は、AUV が航行に要する時間スケールに比べ十分に小さい。さらに、経路探索の計算量を求めるために、探索領域を x 軸方向、y 軸方向にそれぞれ n個に分割したと仮定する。動的計画法を用いた従来手法の計算量のオーダーは O(n2 ) となり、Dijkstra 法を用いた提案手法の計
算量のオーダーは O(n4 ) となる。これより、従来手法と提案手法の計算量はどちらも多項式時間であるので、計算時間は問題にならない。
しかし、実問題に適用するためには、三次元空間における時
間変動のある潮流場において経路探索を可能にしなければならな
い。潮流の時間変動の周期は約半日とゆっくりとしたものである

日本船舶海洋工学会論文集 第 7 号

54

ので、潮流の時間変動に応じて提案手法を用いて経路探索を行う

ことは可能である。提案手法を用いる場合、オンラインでその都度経路探索を行う方法が考えられるが、得られた経路の最適性が保証されなくなる。また、潮流の時間変動を考慮するために、時間軸を加えて高次元問題として解く方法が考えられるが、問題が大きくなりすぎるため、計算時間と記憶容量的にも現状では困難である。そこで、このような問題を解決できるような提案手法をベースにした新しい高次元空間での経路探索手法の開発を目指している。さらに、海中環境には不確実性を伴う潮流外乱が生じる

場合があるため、この影響も考慮する必要がある。本研究では最適経路計画問題を確定的な最短経路問題として定式化していたが、不確実性を考慮するために本問題を確率的な最短経路問題として定式化するアプローチを考えている。
謝

辞

本研究を実施するにあたり、研究初期の段階で貴重なご意見と潮流データを提供して頂いた独立行政法人 海洋研究開発機構の関係者の皆様に厚く御礼申し上げます。また、本研究について有益なご助言をいただいた九州大学大学院工学研究院 梶原宏之教

授に深く感謝申し上げます。

参 考 文 献1) 太田 順, 新井 民夫, 倉林大輔 : “知能ロボット入門 -動作計画問題の解法-” コロナ社, 2000
2) 金 岡 秀, 浦 環 : “自律型海中ビークルの流れ外乱中における最適誘導及び追従制御”, 日本機械学会論文集, 70 巻 699
号 2004
3) A.Alvarez, A.Cniti, and R.Onken ：“Evolutionary
Path Planning for Autonomous Underwater Vehicle ina Variable Ocean”, IEEE JOURNAL OF OCEANICENGINEERING, VOL.29, NO.2 APRIL 2004
4) 近藤 次郎：“オペレーションズ・リサーチの手法”，日科技連出版社，1973
5) 尾崎 弘, 白川 功, 翁長 健治 : “グラフ理論”, コロナ社,
1975
6) Thomas H. Cormen : “アルゴリズム・イントロダクショ
ン 第 2 巻” , 近代科学社, 1995
7) M.deBerg,
M.van
Kreveld,
M.Overmars,
O.Schwarzkopf : “コンピュータ・ジオメトリ - 計
算幾何学 : アルゴリズムと応用”, 近代科学社, 2000

2008 年 6 月