A Reduced Element Map Representation and Applications: Map Merging, Path Planning, and Target Interception

Abstract

Modern autonomous systems require complex and heavy computations. The complexity can be reduced by eliminating or integrating redundant information. In the case of mobile vehicles, occupancy grid map representations are conventionally adopted for path planning. Based on a grid map, a reduced element map representation named a rectangular map or an R-map has been introduced. The concept of R-map is integration of empty elements of a grid map into fewer elements with maximal sizes. Since an R-map has a reduced number of elements, path planning computations become much faster than conventional maps. Also, because the R-map algorithm focuses only on free space, it is naturally suited for obstacle avoidance.

The R-map can also be applied to map merging problems. Since R-maps represent spaces with varied sizes of rectangles, this feature can be a good source to recognize certain locations on the maps, unlike regular gridded cells. This work accomplishes map merging of local maps with unknown factors in their orientations, accuracy, and scales using the rectangular features from the R-map.

Further, this study extends the concept of the 2D R-map to 3D environments. Since 3D environments have an additional dimension of the z-axis, the process of R-mapping will be slightly different from 2D R-mapping, and the integrated cells will be represented as cuboids (volumes) instead of rectangles (areas). Those maximal empty cuboids (MECs) are obstacle-free spaces, and autonomous vehicles can accomplish obstacle avoidance by moving through a sequence of MECs. As applications, algorithms for path planning on R-maps are provided for stationary- and maneuvering-target interception in cluttered environments. This approach expects to provide a computational efficiency to guidance and navigation problems of autonomous systems.