Mapping for Path Planning using Maximal Empty Rectangles

Abstract

This study applies a new map representation, named R-map, to the path-planning problem. The R-map is calculated as a reduced-element representation of a grid map. Grid maps express obstacles and free space with a binary representation for each cell. The concept of the R-map is to integrate free cells into the maximal empty rectangles by surveying the numbers in a grid map. By calculating the R-map, the number of free cells in the grid map is dramatically reduced and this accomplishes data reduction. Since the R-map is a new map representation, it has potential applications in many other fields. This thesis consists of two major parts, R-map and path planning. The R-map part explains a specific R-map algorithm with a simple example, and demonstrates its advantages comparing examples for indoor and outdoor environments. Also, data reduction by applying R-map is demonstrated. In the path planning part, the path planning using Dijkstra’s algorithm is described and paths according to four different weights are illustrated. Moreover, path planning with grid maps and R-maps is compared. R-maps are naturally suited for path planning due to their reduced number of elements and focus on the largest obstacle-free areas.