Algorithmic Generation of Path Fragment Covers for Mobile Robot Path Planning

Abstract

This paper describes a framework for mobile robot path planning in dynamic environments where the environments are represented by grid maps. The planning heuristics considered in the paper is to generate the minimal set of paths so that all the possible path fragments of two edges are covered. We show that the number of required paths is linear in the dimensions of the grid (thus making application of the approach realistic and scalable). The main contribution of the paper is the description of all the minimal covers by means of an efficient algorithm. We prove its correctness and conclude that there are ... minimal path fragment covers in an m × n grid.