Fast Path Planning Through Segmentation of the Map into Manhattan-Cohesive Areas

Abstract

This paper presents a method for fast planning within arbitrary maps, through segmentation of the map into Manhattan-cohesive areas. A Manhattan-cohesive area is a connected part of the map where the optimal distance between any two points in the area is equal to their Manhattan distance. We adopt a four directions Manhattan distance, where diagonal moves are allowed. In the paper we present the method we adopted to fragmentize the map, as well the method to extract the paths. The proposed method produces nearly optimal plans quite efficiently.