Coverage Path Planning for Decomposition Reconfigurable Grid-Maps Using Deep Reinforcement Learning Based Travelling Salesman Problem

Abstract

Optimizing the coverage path planning (CPP) in robotics has become essential to accomplish efficient coverage applications. This work presents a novel approach to solve the CPP problem in large complex environments based on the Travelling Salesman Problem (TSP) and Deep Reinforcement Learning (DRL) leveraging the grid-based maps. The proposed algorithm applies the cellular decomposition methods to decompose the environment and generate the coverage path by recursively solving each decomposed cell formulated as TSP. A solution to TSP is determined by training Recurrent Neural Network (RNN) with Long Short Term Memory (LSTM) layers using Reinforcement Learning (RL). We validated the proposed method by systematically benchmarked with other conventional methods in terms of path length, execution time, and overlapping rate under four different map layouts with various obstacle density. The results depict that the proposed method outperforms all considered parameters than the conventional schemes. Moreover, simulation experiments demonstrate that the proposed approach is scalable to the larger grid-maps and guarantees complete coverage with efficiently generated coverage paths.

Keywords

• Coverage path planning
• cellular reconfigurable decomposition
• deep reinforcement learning
• recurrent neural network
• travelling salesman problem