A Combined Deep Q-Network and Graph Search for Three Dimensional Route Planning Problems for Multiple Mobile Robots

In recent years, automated multiple mobile robots are introduced for transporting loads and inspecting final products in factories to reduce the burden of human labor shortage. Mobile robots are required to develop automated systems that can make decisions as flexibly like human operators. Most conventional route planning problems for mobile robots have been utilizing either, optimization methods or learning methods. However, those conventional methods have a difficulty in applying it to the conflict-free route planning problems with a large number of states with three dimensional environment. We propose a method that combines deep reinforcement learning and graph search methods. In the proposed method, the routing is firstly determined by a graph search algorithm, and Deep Q-Network (DQN). A deep reinforcement learning method is used to avoid collisions. A route planning problem in a three dimensional environment is successfully solved by using DQN that can process multi dimensional states. The proposed method is also applied to the multiple drones route planning problem. The performance of the proposed method is compared with that of the optimization methods. As a result, it was found that a near optimal route planning was obtained in approximately 6% of the computation time required to find the optimal solution.