## 3 Multiple Destination Global Path Planning Strategy Based on Improved Q-Learning Algorithm
### Multi-Destination Simulation Experiment
The other complexity of MD-Q-learning based on passing the fewest obstacles is due to the nature of the proposed local operation. It has a great influence on the results of the algorithm. For better comparison, local search is merged into NSGA_II. If the proposed local search operator is added to NSGA_II, its complexity will be O(M\({}^{2}\)N\({}^{3}\)). The complexity of the MD-Q-learning algorithm based on passing the fewest obstacles will be O(M\({}^{2}\)N\({}^{2}\)). In addition, the first case is tested by using NSGA_II and the suggested local search. Table 1 shows the parameter initialization using local search and the performance of NSGA_II in better size of population and number of iterations. As shown in Table 2, the running time of the algorithm is 3.21 in the same size of population and number of iterations with the MD-Q-learning algorithm. In this test, the coefficient of variation of different targets is smaller than the previous NSGA_II. However, these values are much higher than the MD-Q-learning algorithm based on passing the fewest obstacles. Therefore, in this comparison, MD-Q-learning based on the fewest obstacles has better theoretical and experimental results. \begin{table}
\begin{tabular}{c c c} \hline
**Algorithm** & **NSGA\_II** & **CSD Based MD-Q-Learning** \\ \hline Size of population & 500 & 50 \\ Number of iterations & 800 & 100 \\ Number of heuristic operations & pc = 0.9 and pm = 0.032 & \(N_{\text{LocalSearch}}\) = between 10 and 60 \\ Fitness values of safest path/(length, safety) & 53.75, 0 & 55.54, 0 \\ Fitness values of shortest paths & 45, 61.25 & 45, 49.12 \\ Number of fitness function calls & 772,800 & 218,893 \\ Coefficient of variation in safety objective & 2.47 & 1.41 \\ Coefficient of variation in length objective & 2.71 & 0.437 \\ Run time of algorithm (s) & 2.99 & 3.04 \\ \hline \end{tabular}
\end{table} 
Table 1: Comparison of parameter initialization and performance between NSGA_II and the MD-Q-learning algorithm based on the fewest obstacles. \begin{table}
\begin{tabular}{c c c} \hline
**Algorithm** & **NSGA\_II** & **CSD Based MD-Q-Learning** \\ \hline Size of population & 50 & 50 \\ Number of iterations & 100 & 100 \\ Number of heuristic operations & pc = 0.9 and pm = 0.032 and & \(N_{\text{LocalSearch}}\) = between 10 and 60 \\ Fitness values of safest path/(length, safety) & 53.75, 0 & 55.54, 0 \\ Fitness values of shortest paths & 45, 61.25 & 45, 49.12 \\ Number of fitness function calls & 275,645 & 218,893 \\ Coefficient of variation in safety objective & 2.03 & 1.41 \\ Coefficient of variation in length objective & 1.92 & 0.437 \\ Run time of algorithm (s) & 3.21 & 3.04 \\ \hline \end{tabular}
\end{table} 
Table 2: Parameter initialization and performance in NSGA_II using local search operators and the MD-Q-learning algorithm based on the fewest obstacles. To test the ability of the algorithm to approach the best Pareto front, a benchmark test is added. As shown in Figure 16, there are 88 obstacle units on a 16 \(\times\) 16 obstacle grid. This test was also considered in earlier path planning studies. This experiment is performed using 50 populations and repeating 50 times. Similarly, the minimum and maximum values of the local search operation are equal to 10 and 50, respectively. As shown in Figure 16, in this case, the CSD based MD-Q-learning algorithm obtained the shortest and smoothest path (solutions A and C, respectively). Solution B shows an intermediate path. It seems that the middle path chosen makes a good compromise between the two extreme solutions. Figure 17b shows the best Pareto front of the CSD based MD-Q-learning algorithm. The obtained Pareto front shows that the minimum path length solution and several other solutions are superior to the earlier reported solutions. The algorithm in this paper is heuristic, so the failed Pareto solution will be obtained (represented by \"path X\" in Figure 17b). The main reason is the limitation of minimum path length and some safety factors.