Mobile Robot Navigation Using Variable Grid Size Based Reinforcement Learning

Abstract

Robot navigation in an unknown environment is a very challenging problem. In order to navigate to a desired goal position in a given environment, the robot needs to interact with the environment and develop an understanding of the environment by remembering the results of such interactions. Typically, the robot navigation problem consists of two subproblems: i) generating a model of the environment; and ii) obtaining an obstacle-free shortest path. Reinforcement learning is a classical way to solve both of these sub-problems. Typically, to apply reinforcement learning to navigation problems, the environment is modeled by a grid based representation where each cell of the grid represents a physical space in the environment. A grid based representation results into a finite sized state-space of the system which can be used to solve the path planning problem using traditional reinforcement techniques. However, grid based representation gives rise to a new question regarding the size of each cell in the grid. A smaller grid size leads to better resolution of the state-space resulting in more optimal solutions to the path planning problem. A larger grid size, on the other hand, results into computationally tractable smaller state-space. This demands obtaining the grid size based upon trade-off between the optimality of the solution and the computational efficiency. This paper is focused on solving the above problem using a variable resolution grid size strategy. The method works by obtaining finer grids near obstacles where better resolution is needed to obtain more optimal solutions. Spaces where there are no obstacles have larger grid size so that the state-space does not become too big. Also, we focus on a novel way to store and understand the terrain of the environment. We describe and compare the algorithms for both classic and variable grid size based reinforcement learning. A test bed with Pioneer III DX robot is used to evaluate the real world scenario and a variety of simulations are used to evaluate the improved algorithm. We conclude by discussing the results and the other possible applications of the proposed method.