Graph-Based Spatial Modeling for Optimal Ship Navigation in Coastal Areas = 연안 해역에서의 최적 항로 결정을 위한 그래프 기반 공간 모델링

다국어 초록 (Multilingual Abstract)

This study proposes a spatial modeling methodology for optimal ship navigation in coastal areas with high risks of collision with static obstacles. To precisely represent the complex topology of coastal areas, the spatial environment is modeled using a high-resolution graph structure, with each node weight defined as the risk of collision with static obstacles. This approach guides the A* algorithm, a shortest path algorithm, to determine optimal routes that are not only shorter in travel distance but also lower in navigational risk. The proposed spatial modeling utilizes ship trajectory data to calculate the risk of collision with static obstacles, and generates different graphs based on ship characteristics, thereby expressing the risks that vary according to the ship types or tonnage. The test results of the optimal ship navigation with the proposed graph-based spatial modeling have been evaluated both quantitatively and qualitatively, demonstrating that the proposed spatial representation is proper to the fast optimal ship navigation. Furthermore, the study demonstrates that it can provide safer optimal routes in coastal areas compared to those determined by the traditional A* algorithm.

국문 초록 (Abstract)

이 연구는 정적인 장애물과의 충돌 위험이 큰 연안 해역에서의 최적 항로 결정을 위한 새로운 공간 모델링 방법론을 제안한다. 연안 해역의 복잡한 지형적 특성을 정밀하게 표현하기 위하여, 정점이 조밀한 고화질의 그래프 구조로 공간 환경을 모델링하고, 각 정점의 가중치를 정적 장애물과의 충돌 위험도로 정의한다. 이로써 최단 거리 알고리즘인 A* 알고리즘이 항행 거리가 짧으면서도 정적 장애물과의 충돌 위험성이 낮은 최적 경로를 결정하도록 유도한다. 이 연구가 제안한 공간 모델링 방법은 선박 항적 데이터의 위치 정보를 기반으로 해상에서의 정적 장애물과의 충돌 위험도를 계산하며, 선박 종류 또는 톤수에 따라 달라지는 위험도를 표현하기 위하여 선박 특성에 따라 다른 그래프를 생성한다. 이 그래프 구조를 기반으로 한 해역 공간 모델로써 결정된 최적 항로 예시들은 정량적 및 정성적으로 평가되어 이 연구가 제시한 방법론이 신속한 최적 항로 결정 연산에 적합함을 입증하였다. 뿐만 아니라 기존 A* 알고리즘이 결정한 최적 항로와 비교하여 연안 해역에서 보다 안전하고 현실적인 최적 항로를 제공할 수 있음을 보여주었다.

목차 (Table of Contents)

• Abstract i
• Contents ii
• 1 Introduction 1
• 2 Related Works 6
• 2.1 The A* Pathfinding Algorithm 6
• 2.2 Ship Weather Routing 7
• 2.3 Optimal Ship Navigation in the Presence of Static Obstacles 9
• 3 Data & Methods 11
• 3.1 Geographic Data 11
• 3.2 Ship Trajectory Data 12
• 3.3 Graph-Based Spatial Modeling 14
• 3.4 Navigational Risk of Collision with Static Obstacles 15
• 4 Experiment 17
• 4.1 Test Cases 17
• 4.2 Test Results 21
• 5 Conclusion 29
• Bibliography 31
• Abstract (In Korean) 34