## 4 Proposed Scheme
### Formation Control Algorithm Based on Reinforcement Learning  
#### 4.2.1 Formation Generation Policy  
In a sophisticated maritime environment, the formation control problem can be regarded as a Markov decision process (MDP) and described as \(<S\), \(A,P,r>\). \(S\) describes a set of the possible states \(s\) of each USV. \(A\) is a set of actions \(a\) that a USV can take. The transition probability distribution for each pair of state \(s\) and action \(a\) is expressed as \(P:S\times A\times S\rightarrow[0,1]\). The expected reward for each state-action pair is computed as \(r:S\times A\rightarrow\mathbb{R}\). Moreover, a deterministic policy \(\mu:S\rightarrow\mathbb{R}^{|A|}\) is defined to output a deterministic action \(a\) in state \(s\) that will obtain a reward \(r(s,a)\) and make the environment change to a new state \(s^{\prime}\) with an environmental transition probability \(P(s^{\prime}|s,a)\). Policy optimization is realized by maximizing the cumulative return \(R_{i}=\sum_{t=0}^{T}\gamma^{t}r_{i}^{t}\) of each USV, where \(\gamma\in[0,1]\) is the discount factor. We propose an improved deep deterministic policy gradient based on the advantage function and deep deterministic policy gradient (DDPG) proposed in [48], named the advantage deep deterministic policy gradient (ADDPG). The multi-USV system for formation control considered in this paper is decentralized, and each USV runs its policy independently. We use the ADDPG to train the decentralized formation generation policy set \(\mu=\{\mu_{\theta_{1}},\mu_{\theta_{2}},\ldots,\mu_{\theta_{N}}\}\) for the team of USVs, as described in Algorithm 1. We use the advantage function of state-action value instead of the state-action value to calculate the policy gradient, which can make the policy update toward the direction of the larger action value and accelerate the efficiency of policy learning. For each USV, its observation includes information about its velocity and position, the relative distance of other USVs, the predefined parameters of the formations. Its action is the change of velocity. At each time step \(t\) of formation generation, each USV \(u_{i}\) obtains its observation \(s_{t}^{i}\), uses its policy \(\mu_{\theta_{i}}\) to generate an action \(a_{t}^{i}\), and receive a reward \(r_{t+1}^{i}\) from the environment. After the USV executes the action \(a_{t}^{i}\), the environment state \(s_{t}^{i}\) transfer to the next state \(s_{t+1}^{i}\) contains. The transition experience \(e_{t}^{i}=(s_{t}^{i},a_{t}^{i},r_{t+1}^{i},s_{t+1}^{i})\) of all USVs is collected and stored in the shared experience replay buffer \(D_{s}\) and used to train the formation generation policy. The network structure of the ADDPG is illustrated in Figure 4. Inspired by the target network in DQN, we introduce target networks and actor-critic paradigm in the proposed scheme to address continuous actions and action-value estimation and improve the stability of learning. Thus, there are four neural networks in the ADDPG. The critic is used to train  
Figure 3: Formation maintenance. Figure 2: Formation generation. the state value network to approximate the value of the state-action, including the current critic network and target critic network, which are three-layer multilayer perceptron (MLP) with parameters \(\theta^{V}\) and \(\theta^{V^{\prime}}\), respectively. The actor is designed to train the formation policy to output the action that should be taken in the current state, containing current actor network and target actor network, with parameters \(\theta^{\mu}\) and \(\theta^{\mu^{\prime}}\), respectively. The target networks' parameters \(\theta^{V^{\prime}}\) and \(\theta^{\mu^{\prime}}\) use the parameters from some previous iteration of \(\theta^{V}\) and \(\theta^{\mu}\). We use an advantage function to evaluate the relative advantage of each action in a state and accelerate the learning of policies. The actor part based on advantage function uses the DPG method; the critic part uses the TD error method to update the parameters.