Dong-Geun Jeong, "A Method for Hierarchical Route Planning of Small ships in Coastal Area Using Quadtree Chart", M.Sc. Thesis, Seoul National University, 2023.02.24
정동근, "쿼드트리 해도를 활용한 연안 소형선의 계층적 경로 계획 방법", 석사학위논문, 서울대학교, 2023.02.24
| Abstract | Route planning of vehicles uses different data structures of the route planning map and route planning algorithms according to the purpose of route planning. The small size of the ship, the coastal areas where the small ships are mainly operated, and the fact that individuals mainly operate them are major considerations for choosing a data structure of the route planning chart and route planning algorithm. Electronic charts are generally produced according to the standard form regulated by the International Hydrographic Organization (IHO). Objects on the electronic chart are represented in vector format, making it difficult to use them directly for route planning. In this study, a quadtree, which can reduce the number of chart grids compared to regular grid charts by representing topography with non-uniform grid sizes, was used as a data structure for route planning charts. The quadtree chart can represent areas with complex and small obstacles with a high level of sophistication that small ships can pass through. In addition, since small ships frequently sail inside the marina, the center line created using the Voronoi diagram was selected as an additional data structure for the route planning charts to consider the characteristics of the marina. For the route planning algorithm, Hierarchical Pathfinding A* (HPA*) was used. HPA* divides the chart hierarchically and proceeds route planning sequentially according to the hierarchy, greatly reducing the memory usage and route planning time required for route planning. Moreover, a multi-step smoothing method was applied to improve the quality of the route to provide a route that enhances user experience. In this study, a route planning program considering objects for sailing was created using the quadtree, Voronoi diagram, and HPA* and verified in various coastal areas. |
|---|---|
| Publication Date | 2023-02-24 |
