Robot Patrol Path Planning Based on Combined Deep Reinforcement Learning

Abstract

The optimal path planning for robot patrol is a combinatorial optimization problem that aims to solve the smallest Hamiltonian circle of a complete graph. Such problems are typical NP-hard problems, and the computational complexity of the existing precise algorithm increases exponentially with the expansion of the problem scale. Even if a considerable amount of running time is employed, it is difficult to obtain the global optimal solution. This paper presents a robot patrol path planning method based on combined deep reinforcement learning (DRL). This method combines reinforcement learning and neural networks to perform path optimization. The first step is performing DRL pre-training through asynchronous advantage actor-critic (A3C). Training data is adopted to optimize the recurrent neural networks (RNN) that parameterizes the stochastic policy. The second step is effective planning (EP) without pre-training. Using the expected reward objective, it iteratively optimizes the RNN parameters on test instances. The experimental results show that combined deep reinforcement learning method can jump out of the local optimal solution and outperform other state-of-the-art methods.