# Improved DQN for Dynamic Obstacle Avoidance and Ship Path Planning
## 3 The Proposed Deep Q Network(DQN)
### The Original DQN  
Reinforcement learning is a typical Markov decision process (MDP) [39]. The environment information obtained in the ship traveling process is insufficient, so the Markov decision process modeled in this paper is a partially observable Markov decision process (POMDP). POMDP can use \((S,A,P_{sa},R,\omega,O,\gamma)\) description, where \(S=s_{1},s_{2},\ldots,s_{n}\) is a set of state space, and \(s_{i}\) represents the state of step \(i\). \(A=a_{1},a_{2},\ldots,a_{n}\) is the action space set, and \(a_{i}\) indicates the action of the step \(i\). \(P_{sa}\) is the state transition probability matrix. \(R\) is the reward function. The probability of observation is \(\omega\). O is the observation space. \(\gamma\) is the discount factor. The value function iteration method of DQN and Q-learning is very similar. Q-learning directly uses the subsequent state data of the iteration for learning. Q-learning is based on the optimal action-value function \(Q_{*}\). Both algorithms adopt the optimal Behrman equation to make the agent learn some data, as shown Equation (1). \[Q_{*}(s_{t},a_{t})=\mathbb{E}_{s_{t+1}\sim p(\cdot|s_{t},a_{t})}[R_{t}+\gamma max _{A\in\mathcal{A}}Q_{*}(S_{t+1},A)|S_{t}=s_{t},A_{t}=a_{t}] \tag{1}\]  
Equation (1) is approximated. \(Q_{*}(s_{t},a_{t})\) on the left of the Equation (1) can be approximated as \(\bar{Q}(s_{t},a_{t})\). \(\bar{Q}(s_{t},a_{t})\) is made at step \(t\). On the right of the Equation (1), the mathematical expectation is about the state \(S_{t+1}\) at the next step. If the current state \(s_{t}\) is known, the agent executes the action \(a_{t}\) according to strategy, and the environment will return the reward \(r_{t}\) and obtain the new state \(s_{t+1}\). Based on \(r_{t}\) and \(s_{t+1}\), the expectation is calculated by Monte Carlo approximation, as shown in Equation (2). \[r_{t}+\gamma max_{a\in\mathcal{A}}Q_{*}(s_{t+1},a) \tag{2}\]Further, \(Q_{*}\) in Equation (2) is approximated by \(\tilde{Q}\). Equation (3) is used to estimate \(Q_{*}(s_{t},a_{t})\) at step \(t+1\), it is called Temporary Difference (TD). \(\tilde{Q}(s_{t},a_{t})\) and \(\hat{y}_{t}\) is the estimation with regard to optimal action value \(Q_{*}(s_{t},a_{t})\). Because \(\hat{y}_{t}\) includes reward \(r_{t}\) partially based on real observations, it is believed that \(\hat{y}_{t}\) is the more reliable. So, it is encouraged \(\tilde{Q}(s_{t},a_{t}))\) to be closed to \(\hat{y}_{t}\). Therefore, Equation (4) is used to update \(\tilde{Q}\). \[\hat{y}_{t}\triangleq r_{t}+\gamma\underset{a\in\mathcal{A}}{max}\tilde{Q}(s_ {t+1},a) \tag{3}\]  
\[\tilde{Q}(s_{t},a_{t})\leftarrow(1-\alpha)\tilde{Q}(s_{t},a_{t})+\alpha\hat{y }_{t} \tag{4}\]  
However, there are some differences between DQN and Q-learning. The DQN consists of two networks-network \(Q\) and target network \(\tilde{Q}\). At initialization, the structure of the target network \(\tilde{Q}\) and \(Q\) are the same. In each episode, the agent will obtain a state \(s_{t}\) and take an action \(a_{t}\) when interacting with the environment. Network \(Q\) based on \(\varepsilon\)-greedy is used to evaluate the Q-value function. Then, the agent obtains the reward \(r_{t}\) and enters the state \(s_{t+1}\). Therefore, some data (\(s_{t}\), \(a_{t}\), \(r_{t}\), \(s_{t+1}\)) will be collected and input to the experience replay. If the experience replay is full, some old data will be discarded. Next, the sampled data in the playback buffer is calculated by the target network \(\tilde{Q}\), as shown in Equation (3).