# Automatic Docking Trajectory Design-Based Time-Varying-Radius Dubins for Unmanned Surface Vessel
## 3 Varying-Radius-Dubins-Based Trajectory Design  
On the path planning level, the USV is regarded as a point-mass system, and the dynamic model of the well-designed USV is a single integrator. Therefore, each specific segment in the trajectory sequence is assumed one kind of variant Dubins curve. So far, the investigated varying-radius-Dubins-based trajectory design is to achieve the optimized path by adjusting the minimum turning radius of Dubins curve. In the other word, the proposed multi-radius Dubins path is derived from the original Dubins path with multiple segments, and each segment is designed with different minimal turning radius. As we have seen, the key idea of our method is to sample a minimal turning radius. We consider the solution of optimal trajectory as a problem to efficiently create a set of particular minimal turning radius intervals. In Figure 7, each segment in the trajectory comprises of circle part \(C_{i}\) and straight line \(S_{i}\), i.e., \(\zeta_{i}=[C_{i}S_{i}]\). Since the segment length of \(\zeta_{i}\) is \(|\zeta_{i}|\), the total trajectory time is \(T(\Omega)=\sum_{1}^{m}\frac{|\zeta_{i}|}{V_{i}}\), herein \(m\leq n\). Considering the number of intervals is limited, we create an oriented graph, presented in Figure 8. Each layer corresponds to one segmented location \(p_{i}\) and consists of \(h\) nodes, each for one minimal turning radius in \(H\). The graph nodes are connected by edges representing a global searching solution. Therefore, the global searching method of the time-optimal trajectory is visualized in Figure 8. Moreover, the time complexity of finding the shortest path in the graph is \(O(nh^{3})\). Figure 6: The principle of automatic docking design with moving dockyard. Figure 7: Varying-radius Dubins curves. Although the above global optimization method can obtain optimal solutions, it is more complex to solve. Since the heuristic method can solve the problem in a shorter time, therefore, we implement an automatic docking trajectory algorithm-based ant colony optimization (ADTA-ACO) [27] to obtain the optimal solution. The proposed ADTA-ACO algorithm takes the sailing time of the USV as the optimization objective. As shown in Figures 9 and 10, the proposed ADTA-ACO algorithm initializes parameters such as the maximum number of iterations and the number of ant colonies. The core idea of ADTA-ACO algorithm is to select appropriate turning radius at each site step by step, and this optimization problem is solved by Ant Colony Optimization algorithm. In Figure 9, Dubins curves with different colors correspond to different turning radii. Then, ADTA-ACO algorithm takes the sailing time of the USV at different turn radii as the heuristic value. ADTA-ACO algorithm calculates the selection probability of next turn radius in combination with the pheromone concentration and heuristic value. Afterwards, ADTA-ACO algorithm selects the next turn radius until the USV returns to the dockyard according to the roulette wheel and selection probability. If all ants are traversed, the algorithm calculates sailing time of the USV for each ant. Finally, ADTA-ACO algorithm updates the global best solution and the pheromone concentration. If the maximum number of iterations is reached, ADTA-ACO algorithm outputs the global best solution as the set of minimal turning radius intervals. In conclusion, Figure 10 illustrates the main flowchart for ADTA-ACO algorithm. Figure 8: Global optimization searching algorithm. Figure 9: Automatic docking trajectory algorithm-based ant colony optimization algorithm. Although the proposed ADTA-ACO algorithm obtains solutions close to the optimal solution in a shorter time, the USV can only perceive local information, i.e., the USV can only determine specific parameters of next segment according to the current dockyard's position and direction. Therefore, we propose an automatic docking trajectory algorithm-based time-varying-radius Dubins (ADTA-TRD), as shown in Figure 11, to calculate the optimal minimal turning radius in the next step.