Efficient path planning for searching a 2-D grid-based environment map

Abstract

In this paper, the aim is to find the shortest path from which a mobile robot can view the whole environment. Available solutions are based on polygonal representations of the environment. This has limited a detailed modeling of the obstacles due to the representation complexity and modeling limitations forced by the proposed solutions. Such inaccuracy can be critical in search related tasks. This work presents a solution based on a grid-based representation of the environment which provides a detailed modeling for complex obstacle strewn environments. The presented approach provides a close to optimal short search path which the robot can traverse to incrementally view all free spaces. The approach has been implemented and tested on a simulated environment. A number of test cases are presented.