## 3 Multiple Destination Global Path Planning Strategy Based on Improved Q-Learning Algorithm  
### Q-Learning Algorithm Optimization  
The traditional path planning algorithm needs to perform adjacency transformation on the environment grid map matrix to obtain the adjacency transformation matrix. It mainly represents the feasibility of the agent moving to each grid and ensures the convergence. For the method of sequence arrangements designed in this article, the environmental grid map matrix was reconstructed. It increases the amount of map information of the environmental model. The traditional algorithm also repeats the analysis of the environmental model. It is too redundant and cannot guarantee the convergence. The path planning of the Q-learning algorithm has nothing to do with the initial value. The Q-learning algorithm can guarantee the convergence without the environmental model. Therefore, this article uses the Q-learning algorithm for path planning. Q-learning is a type of reinforcement learning algorithm. Reinforcement learning is mainly composed of agent, environment, state, action, and reward value [20]. It is a learning process to achieve a goal through multi-step decision making. The basic structure of reinforcement learning is shown in Figure 6. The Q-learning algorithm is based on the reinforcement learning framework. First, a Q value table is set, and the initial state and reward value are defined. After the agent performs an action, the environment will transform to a new state. In the new state, the environment will give the corresponding reward value. Then, the agent calculates and updates the Q value table according to the new state and the reward of the environment feedback. According to the Q value table, the strategy is selected, and the new action is executed. Finally, through continuous interaction with the environment, the optimal action set is found. The flow of the Q-learning algorithm is shown in Figure 7. The simulation effect is shown in Figure 8.  
Figure 8: Q-learning algorithm flow chart. Figure 6: Basic architecture of reinforcement learning. Figure 7: Q-learning algorithm flow chart. The following are the optimization measures in the algorithm. It can be seen from the algorithm flow in Figure 7 that Q-learning uses the action value function to update the Q value table. The Q value table can be used to select the optimal strategy. However, Q-learning is essentially a greedy algorithm. There is a behavior that takes the highest expected reward every time. During the training process, it cannot explore other possible behaviors. The algorithm enters the \"local optimum\" and fails to complete the path planning. Therefore, this article set the coefficient _path_ and the safety distance \(D\) as shown in Equation (10). In this way, the agent has a certain probability to take the optimal behavior. The efficient _path_ stores the actions. The algorithm also has a certain probability to take all the actions that can be taken immediately. The traversed path is incorporated into the memory bank to avoid local optima and small-scale loops. \[ \begin{cases}r(s^{\prime})=-1&s^{\prime}\in path\quad\text{or}\quad\text{ distance}>D\\ r(s^{\prime})=0&s^{\prime}\
otin path\quad\text{or}\quad\text{distance}\leq D \end{cases} , \tag{10}\]  
where \(s^{\prime}\) is the next state. \(r(s^{\prime})\) is the reward of the next state \(s^{\prime}\). The coefficient is _path_ and the safety distance is \(D\), _distance_ is distance from obstacles. In order to increase diagonal movement, this article sets the reward value of diagonal movement to take an approximate value of 0.707 as shown in Equation (11). It avoids the situation where the robot first moves to the upper left and then to the lower left instead of directly moving two squares to the left. Setting this value is determined based on the relative distance between two grids on the map. Definition: The right downward motion is (\(i,i+n+1\)). The left downward motion is (\(i,i+n-1\)). The right upward motion is (\(i,i-n+1\)).