Automatic Navigation Map Decomposition for Efficient Reinforcement Learning

Safe navigation in an environment with obstacles is a challenging problem. Reinforcement learning (RL) is a promising approach to solve the problem. However, RL often suffers lengthy training time with large maps. This paper presents an algorithm to decompose a map into smaller regions to enable efficient RL. The approach is based on the use of generalized Voronoi Diagrams. The idea is to decompose a large map into a set of regions that are free of crossroads, which greatly reduces the state complexity. In the experiments, the method is applied to decompose six maps. The results show that the approach is effective and efficient.