# Improved DQN for Dynamic Obstacle Avoidance and Ship Path Planning
## 2 Related Work
### Ship Navigation Environment Modeling  
For ship collision avoidance, simulation modeling of the navigation environment is essential. Compared with the road, the ship route contains more complex factors. Specifically, these factors will lead to fundamental differences in static collision avoidance, dynamic collision avoidance, and collaborative collision avoidance decision-making, so it is necessary to conduct modeling and analysis in advance ([PERSON] et al., 2019). The navigation environment includes the following aspects: (1) channel boundary and other boundary elements, including national boundaries and regional boundaries. (2) Water geographical elements, including intertidal zones, seabed topography, and navigation obstacles. (3) Various specific regional elements, including open water areas, restricted areas, port boundaries, and area boundaries. (4) Marine environmental elements include ocean currents, icebergs, undercurrents, and other elements in the ocean region. In order to solve the problem of ship collision avoidance, the channel is simplified according to the task requirements. During channel simulation modeling, the above channel elements are simplified as navigable and non-navigable zones. When planning the path, the first consideration is not the specific location of obstacles in the environment but to divide the environment into several sub-regions with consistent topological characteristics and connectivity. The topology method builds the network and finds the topological path in the connection area. However, it can only reflect the interconnection between points in the natural environment and cannot establish an environment consistent with the geometric shape of the natural environment. If specific geometric details and paths need to be considered, the path planning method based on free space is essential. The commonly used methods include the visual graph method ([PERSON] et al., 2019) and the grid method ([PERSON] et al., 2019). The visual graph method assumes that the agent and obstacle are particles and approximate polygons, respectively. It combines and connects particles, target points, and polygon vertices using visual line segments. This segment cannot pass through obstacles simulated by polygons. The path planning problem is transformed into a group of shortest line segments from the search starting point to the target point. Because the search path is a segment connecting the vertices of the obstacle, the proxy can obtain collision information with the obstacle. Many environmental barriers and feature information exist, extending the path search time. At the same time, the visual graph method has poor flexibility, lacksadaptability to changing environments and has real-time constraints. In addition, it cannot guarantee that the path sought is the most optimal path globally. The grid method uses a free grid and an obstacle grid, two grids with different attributes and sequence numbers to describe the environment. There are no obstacles in the free grid area, obstacles are divided into the obstacle grid area. The ship collision avoidance problem is transformed into a set of orderly feasible grids in the search workspace. This method takes the grid as the basic unit to record the agent's environment information. If the grid size is large, the description of the feature map will be rough. Thus, the quality of the planned path could be better, and the error could be more considerable. On the contrary, the more accurate the description of environmental obstacles, the better the quality of the planned path. It makes the storage space and search algorithm more complex. Therefore, the grid method should select an appropriate grid-scale and corresponding algorithm according to the specific application environment to optimize the ordered set of search grids. Grid graphs can describe many characteristics of the navigation environment and achieve the best consumption of time and space. Therefore, a grid map is widely used to describe the environment.