日本船舶海洋工学会講演会論文集 第３号

潮流場における自律型水中ビークルの最適経路計画について
学生員 白 石 耕一郎*
正 員 木 村元**

正員 梶原 宏 之**

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

Hiroyuki Kajiwara, Member

Key Words: AUV, Current Field, Energy Consumption, Dijksra Method, Delaunay Triangulation

1. 緒rrei を AUV の単位ベクトル，vc ( x, y, z ) を潮流の速度ベク

言近年，地球温暖化や異常気象など深刻な環境問題が発生している。このような問題の解決策を見つけるために，海洋環境のモニタリング体制の強化が望まれている。そこで様々な危険を伴う海中環境で人間の代わりを行うことができる新しいプラットフォームとして自律型水中ビークル(Autonomous Underwater Vehicle : AUV)の利用が活発になってきている。AUV は情報転送やエネルギー供給用のケーブルを持たないというシステム上の特徴により高い作業性と運動自由度を確保できるが，任務途中のエネルギー補給が困難である。よって長時間計測のためにはエネルギー消費を出来るだけ最小に抑える必要がある。
AUV の稼動する海中環境には潮流外乱が存在し，AUVの運動方向によって潮流外乱は抵抗となりエネルギー消費を増大させる。このことから潮流外乱を考慮した経路計画を立てることによって，AUV のエネルギー消費を抑えることができる。本研究では潮流外乱を考慮した AUVの経路計画を最適経路計画問題として取り扱う。この問
題 を グ ラ フ 理 論 に お け る 最 短 経 路 問 題 (Shortest PathProblem)として定式化し，解を求める方法として動的計画法の一種である Dijkstra 法を適用する。この問題設定によって後戻りをするような複雑な経路も探索可能になる。
また離散的に存在する潮流データを補間する方法としてDelaunay 三角形分割を用いた三角形パネル補間法を提案し，有用性を検証する。

2. 最適経路計画問題
経路計画とは出発点と目的点を決め，その間の経路を設定することである。最適経路計画問題とは経路計画において，移動コストを最小とする経路を見つけることである。AUV が定常速度 c で航行するとし，AUV の稼動領域である海洋空間は格子点で構成されているとする。また潮流を考慮した AUV のエネルギー消費のコスト関数
として A.Alvarez1)らは次式を提案している。

J ( pi −1 , pi ) =∫∫∫ V ( x, y, z ) dxdydz
3i

pi −1 to pi(1)r r
ここで， Vi = cei − vc ( x, y, z ) を AUV と潮流の相対速度，* 九州大学大学院工学府海洋システム工学専攻**九州大学大学院工学研究院海洋システム工学部門
原稿受付 平成 18 年 3 月 31 日
春季講演会において講演 平成 18 年 5 月 11, 12 日
©日本船舶海洋工学会

トル，Path = { p0 , L , pm } を AUV の航行経路， pi を i 番目に通る節点とする。(1)を用いて最適経路計画問題は次のように定式化される。
(2)
min Cost ( Path)
Pathm

ただし

Cost ( Path) =∑J (p , p )i −1i(3)i =0(2) 式を満たす経路 ( Path) が最適経路となる。ただし，
本研究では AUV の運動特性は考えず，到着時刻は指定されていないとし，潮流場は二次元定常潮流場とする。

3. 最適経路探索
3. 1 Dijkstra 法
最短経路問題とは，グラフで表現されたネットワーク上において任意の 2 頂点を結ぶ経路の中から，辺の重みの総和（コスト）が最小となる経路を求める問題である。
Dijkstra 法とは，最短経路問題の解法として E.Dijkstra によって提案された手法である。ネットワーク上の全ての節点に対し，接続している節点とその間を結ぶリンクのコストが分かるとネットワーク全体の構成を知ることができる。その接続状態の情報を用いて目的の節点までコストが最も小さくなるような経路を計算し，最小コストと最短経路を求めることができる。
最適経路計画問題を考えるために，AUV は次のステップで現在地点に隣接する 8 点の全てに到達できるとする。
よって AUV は前後左右斜めのどちらにも進めるようになり，経路選択の自由度が増すため多様な経路設定が可能になる。また最短経路問題は関数方程式を用いて次のように定式化できる。
(4)
関数方程式： F (vi ) = min{w( pr , vi ) + F ( pr )}0<r <8境界条件：

F (v 0 ) = 0(5)

ここで， vi = ( xi , yi , zi ) を経路ネットワーク上の節点，v0 = ( x0 , y0 , z 0 ) を出発点， P(vi ) = { p0 , L , p8 } を節点 viに隣接する 8 点の集合， pr を節点 vi に隣接点の１つ，F (vi ) を出発点( v0 )から節点( vi )までの最小の移動コス
トの和，w( pr , vi ) を節点 ( pr ) から，節点 (vi ) に移動した
ときの移動コスト(重み関数値)である。
3. 2 最適経路の探索結果(Case1)
Case1 では，文献 1)の多数の渦が存在する複雑な潮流場

において，最短経路問題に Dijkstra 法を適用した最適経路探索(Dijkstra)を行った。また解の性能比較のために，最適 経 路 計 画 問 題 を 多 段 決 定 問 題 (Multi-stage DecisionProblem)として定式化し，動的計画法を適用した場合の最適経路探索(Multistage)も行った。ここで Fig.1 の格子点間の距離は 20km である。

Case2 では，JAMSTEC から提供された三陸海岸沖の東300km における潮流データに三角形パネル補間法を用いて潮流場を生成し経路探索を行った。Fig.2 の格子点間の距離は，縦 20m, 横 40m である。

Fig.2 Optimized Path (Case2)

Fig.1 Optimized Path (Case1)

Case1
Straight
Multistage
DijkstraTable.1 Cost Function (Case1)
Cost Function
Calculate Time(ms)20.746653
13708
0.757782
17219
0.470656
195297

Table1 より直線に航行するより経路探索を行った経路の方がエネルギー消費を抑えることができることが分かる。また Fig.1 より Dijkstra 法では後戻りするような経路を探索することができ複雑な渦の流れに沿った経路を探索できており，移動コストも改善されている。

4. 実データへの適用
4. 1 三角形パネル補間法
潮流を連続的なデータとして測定することは難しく，離散的に広がった測定点のデータがほとんどである。そのため潮流データを扱う場合，何らかの補間操作を行う必要がある。そのために，ある x − y 平面において潮流のある成分を z 軸にとることによって三次元空間を生成する。三次元空間 ( x, y, z ) において，データが与えられている任意の 3 点を選び，その 3 点を平面の式に代入し三元連立一次方程式を立て，その解から平面の方程式を決定する。よって任意の点での潮流を三角形パネルの平面の式から求めることができる。しかしデータ点は離散的に広がっているため，三角形分割の仕方はデータ点に比例して増えていく。さらに三角形分割の仕方によって補間した値に大きな差が生じることがある。そのような差を小さくするためには，三角形分割の最小角度を最大にする必要がある。本研究では，最小角度を最大にする三角形分割である Delaunay 三角形分割を逐次添加法を用いて求め，その三角形分割に三角形パネル補間法を適用して潮流データを補間する。
4. 2 実データにおける最適経路の探索結果(Case2)

Case2
Straight
Multistage
DijkstraTable.2 Cost Function (Case2)
Cost Function
Calculate Time (ms)3.058860
8719
2.894586
11562
2.935085
52875

Table.2 より実データにおいても経路探索によってエネルギー消費が改善されていることが分かる。しかし Case2
は複雑な潮流場ではないため問題設定による解の差はあまり出ていない。

5. 結言

本研究では，AUV の最適経路計画問題をグラフ理論における最短経路問題として定式化し，Dijkstra 法を適用することによってエネルギー消費が最小となる経路を探索可能にした。また迷路のように複雑な障害物が存在する潮流場においても，Djikstra 法を用いた経路探索によって最適経路探索を可能にした。そして潮流データの補間方法として Delaunay 三角形分割を用いた三角形パネル補間法を提案し，実データに適用することで有用性を検証した。しかし，実問題に適用するためには三次元空間における時間変動のある潮流場において経路探索を可能にしなければならない。よって今後の研究方針として潮流の不確実性を考慮した経路計画問題を取り扱っていくことを考えている。

謝辞
本研究を御支援いただいた JAMSTEC の山本郁夫氏，澤隆雄氏に感謝申し上げます。

参 考 文 献1)

2)

A.Alvarez, A.Cniti, R.Onken: Path Planning forAutonomous Underwater Vehicle in a Variable Ocean，IEEE JOURNAL OF OCEANIC ENGINEERING, vol.29,no.2, pp.418-429, 2004
M.deBerg, M.van Kreveld, M.Overmars, O.Schwarzkopf:
コンピュータ・ジオメトリ, 近代科学社, 2000