## 1 Introduction  
Robotics and automation systems have been introduced in recent conveyor systems, warehousing, the food industry, etc. It is necessary to develop automated systems that can make flexible actions to reduce the burden of human work. Automated Guided Vehicles (AGVs) are widely used in large-scale factories such as semiconductor factories, where demands for semiconductor production are increasing. In a transportation system, the task of transporting objects from one initial location to another is given periodically in real-time. The route planning for multiple mobile robots is required to complete the given transportation tasks while avoiding collisions and deadlocks between AGVs and obstacles. Design and control issues for AGVs have been extensively reviewed in [1; 2]. In general, the AGV routing methods are classified as static routing and dynamic routing. Static routing refers to a routing method that provides a conflict-free route according to a start point and a destination point when the set of transportation requests is known in advance. The static routing methods using [PERSON]'s algorithm [3], graph theory [4], iterative neighborhood search [5] and Petri net models [6; 7; 8] have been proposed. A distributed route planning method for multiple mobile robots using an augmented Lagrangian decomposition and coordination technique has also been proposed [9]. Among them, many graph search-based methods using the A* algorithm [10; 11; 12; 13] or conflict-based search (CBS) [14; 15; 16; 17] have been proposed [18]. In these approaches, the route planning problem is solved by iteratively solving static problems, even in dynamic environments where tasks are given in real-time. However, these approaches have the drawback that it is computationallyexpensive for solving large-scale problems. If the number of vehicles is increased in a transportation system, the frequency of deadlocks may also increase. It makes it much more difficult to avoid deadlocks and conflicts. A deadlock is a situation in which multiple vehicles are going to the location of another vehicle, and none of the vehicles can travel. Furthermore, unexpected events such as failures or delays may cause collisions that have not appeared in the planning phase. Therefore, many reinforcement learning methods have been proposed in recent years to solve dynamic routing problems [19]. One of the advantages of using reinforcement learning is that the routing of AGVs can be flexibly regenerated under unexpected situations. However, reinforcement learning is a trial-and-error method of the searching method to obtain suboptimal solutions. It requires much memory and large-scale computation for trial-and-error. To reduce the computation time, TD (Temporal Difference) learning error [20] is sometimes used to learn Q-values in the Q-learning algorithms. TD learning can reduce the total computation time by allowing AGVs to continuously learn the situations based on the reward obtained after each action. Each AGV determines its action based on the information obtained. Several methods [21; 22; 23; 24] have been proposed for route planning using the Q-learning approach. However, these methods do not ensure the optimality of the solutions, and sometimes, AGV may choose unnecessary actions, which may increase the total traveling time required for transportation. In this paper, we propose an efficient route planning algorithm that combines Q-learning and a graph search algorithm based on A\({}^{\star}\) algorithm. In the proposed algorithm, the shortest route to the destination of each AGV is searched by the A\({}^{\star}\) algorithm, and Q-learning is used to avoid collisions between AGVs. By combining the A\({}^{\star}\) algorithm with Q-learning, each AGV has the flexibility to accommodate the changes that can cope with unexpected situations, which is an advantage of reinforcement learning, while minimizing the total traveling time, which is an advantage of graph search. The rest of the paper consists of the following sections.