Complete coverage path planning algorithm for known 2d environment

Abstract

Path-planning is an important primitive for autonomous mobile robots that lets robots find the optimal path between two points. Typical path-planning algorithms deal with finding an optimized path from start to end using a map of the environment and the robot to be aware of its location with respect to the map. Complete coverage path planning algorithm, on the other hand, is used in application where an autonomous mobile robot is required to visit all the points at least once in the given environment size with known obstacles. In this paper, a complete coverage path planning algorithm is developed and tested on a actual hardware. The algorithm is development for a known 2D environment with static obstacles with an optimization on minimal coverage time. The scaling of computational time with increasing map sizes and simulation results for different types of obstacle geometries are also presented. This kind of algorithm can be used for area inspection, cleaning robots, painter robot, land mine detectors, lawn mowers, agricultural field machines etc.