# Multi-Robot Path Planning Method Using Reinforcement Learning
## 2 Reinforcement Learning
### Experimental Results in a Static Environment  
In Section 4.3, the proposed algorithm is compared with the A* algorithm. Because the A* algorithm always finds the shortest path, it can see how quickly the proposed algorithm can find the shortest path. The proposed algorithm and the A* algorithm were tested by four robots to find a path with an arbitrary numbers of obstacles in random initial positions. The test was repeated 100 times on the generated map, which is changed 5000 times to obtain the route visited by the robot and the shortest path for each robot to reach the target point. In the first case, the search area and the time to reach the target point of the proposed algorithm is smaller than the A* algorithm, but the actual travel distance of the robot is increased, as shown in Figures 8 and 9. Figures 8 and 9 depict the results of the A* algorithm and the proposed algorithm, respectively. The average search range of A* algorithm is 222 node visitation. The shortest paths of robots 1 to 4 were 35, 38, 43, and 28 steps, respectively, and the proposed algorithm, where each robot path are 41, 39, 44, and 31 steps, had 137 visited nodes.  
Figure 6: The rate at which episode goals are reached.  
Figure 7: The rate of reaching the goal by Epochs.  
In the fourth case, the search range of both algorithms is similar, and the movement path of the robot is the same. Figures 14 and 15 show the results of the A* algorithm and the proposed algorithm, respectively. In the average search range of A* algorithm, robot visited 121 nodes, and the shortest paths of robots 1 to 4 were 40, 38, 36, and 23 steps respectively. And the proposed algorithm had 100 visited nodes, and the shortest path of each robot is 40, 39, 36, and 23 steps, respectively.  
Table 1 shows the search range of the proposed algorithm and A* algorithm for each situation. The search range is one of the most important factors on effective robot navigation to the target point. As shown in Table 1, the proposed algorithm has a smaller search range than the A* algorithm.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Situation** & **A* Algorithm** & **Proposed Algorithm** \\ \hline Situation 1 & 258 & 155 \\ Situation 2 & 83 & 67 \\ Situation 3 & 69 & 69 \\ Situation 4 & 120 & 101 \\ \hline \hline \end{tabular}
\end{table}
Table 1: The average search range of A* and the proposed algorithm.  
Figure 14: The simulation result of A* algorithm for the fourth situation.  
Figure 15: The simulation result of proposed algorithm for the fourth situation.  
Table 2 shows the generated path for each robot according to the situation for both proposed and A* algorithm. The proposed algorithm results in no less number of steps than A* in an average generation. In general, A* algorithm is not always searching for the optimal path because it always searches the optimal path in a static environment. However, the proposed algorithm generates the path faster than A*.  
Table 3 shows the frequency of occurrence of each situation when a total of 5000 experiments were conducted. Although the search area is small, the situation 1 where the robot generation path is long shows about 58% of occurrence, and the situation 2 where the search area and travel distance are similar is about 34%. According to the simulation result, the search range of the proposed method is always smaller and the robot generation path is the same or similar to the robot path generated by the A* algorithm with a probability of about 34.76%.