# Research on Dynamic Path Planning of Multi-AGVs Based on Reinforcement Learning
## 2 K-L-Based Local Path Planning Algorithm
### Exploration Strategy Based on a Self-Adapting Simulated Annealing Algorithm  
Traditional Q-learning algorithms determine the exploration strategy according to a constant \(\varepsilon\). The exploration strategy has a probability of \(\varepsilon\) choosing an arbitrary action and a probability of \(1-\varepsilon\) of choosing the best action in the current scenario. A fixed value of \(\varepsilon\) in the static environment does not affect the learning efficiency of the algorithm, but in the dynamic environment, especially when dynamic obstacles appear, if \(\varepsilon\) is too large, the Q-learning algorithm will hardly converge, whereas if \(\varepsilon\) is too small, the Q-learning algorithm will easily converge to the local optimal solution. Therefore, for a dynamic environment, an adaptive simulated annealing algorithm (SSA for short) is used in this paper to dynamically adjust the value of \(\varepsilon\). The formula is as follows:  
\[\varepsilon=\left\{\begin{matrix}1,\Delta Q>0\\ e^{-\Delta Q/T(n)},\Delta Q\leq 0\end{matrix}\right. \tag{4}\]  
Variations of the \(Q\)-value are expressed as \(\Delta Q\), and \(T(n)\) is the temperature of iteration \(n\), which continues to decrease.  
We can infer from the formula that when the Q-value increases, the SSA-based strategy tends to explore a new action, and when the Q-value decreases, the strategy has a probability of \(1-\mathrm{e}^{-\Delta Q/T(n)}\) of choosing the best action in the current scenario. As \(T(n)\) continues to decrease, the K-L algorithm has a high probability of exploring new actions during the early stage of training and a high probability of choosing to exploit existing experience in the later stages of training.  
The decay of \(T(n)\) is a linear process, whereas the change in \(Q\) value is nonlinear. Therefore, we select the maximum of both \(\Delta Q\) and the fixed annealing rate (\(\gamma\)) as the actual annealing rate of the SSA. The actual annealing rate can be adjusted according to the variation of \(Q\) values, so when the variation of \(Q\) values is too large, the SSA-based strategy obtains a large \(\varepsilon\) value, and there is a high possibility of exploring new actions; as a result, the K-L algorithm is prevented from obtaining a locally optimal solution.  
\[T(n)=\left\{\begin{matrix}\frac{1}{1+e^{-(|Q_{n}-\Delta_{n-1}|)}}*T(n-1),\frac {1}{1+e^{-(|Q_{n}-\Delta_{n-1}|)}}>\gamma\\ \gamma T(n-1),\frac{1}{1+e^{-(|Q_{n}-\Delta_{n-1}|)}}\leq\gamma\end{matrix}\right. \tag{5}\]  
where \(Q_{n}\) denotes the \(Q\)-value after \(n\) iterations, \(\gamma\) is the decay factor, and \(\frac{1}{1+e^{-\varepsilon}}\) is a normalization function. According to Equation (5), slowing down the temperature drop in the early stage when the Q-value changes drastically adds more explorability to the suboptimal path, whereas accelerating the temperature drop in the later stage near convergence and decreasing \(\varepsilon\) makes the algorithm less exploratory, resulting in stable convergence.  
\begin{table}
\begin{tabular}{c c} _Number of Divisions_ & _Number of States_ \\ \hline
4 & **3072** \\
5 & **9375** \\
6 & **23,328** \\
7 & **50,421** \\
8 & **98,304** \\ \end{tabular}
\end{table}
Table 1: Number of distance divisions and number of states.  
In summary, the SSA algorithm controls the initial temperature and the temperature decay function, and the Q-value matrix stabilizes with an increasing number of iterations so that \(\varepsilon\) decreases gradually with successive iterations of the algorithm. The Q-learning algorithm ensures sufficient exploration of the path in the early stage and stable convergence in the later stage.