A new maze routing approach for path planning of a mobile robot

A new path planning approach for a mobile robot among obstacles of arbitrary shape is presented. This approach is based on a higher geometry maze routing algorithm. Starting from a top view of a workspace with obstacles, the so-called free workspace is first obtained by virtually expanding the obstacles in the image. After that, the 8-geometry maze routing algorithm is applied to obtain a shortest collision-free path. The proposed method is not only able to search a shortest path with rotation scheme but also capable to rotate the robot configuration to pass a narrow passage intelligently. The time complexity of the algorithm is O(N), where N is the number of pixels in the free workspace. Furthermore, for many researchers who work on dynamic collision avoidance for multiple autonomous robots and optimal path searching among various terrains (weighted regions), the concept of this algorithm can be applied to solve these problems.