A Failsafe Fine Resolution Online Grid Coverage Algorithm for Autonomous Agents

Abstract

Plannig paths for vehicles which take aerial photographs/images or which collect topographic data for mapping from the air, on the ground or inside water is a  challenging problem. Moreover, if such vehicles are expected to move autonomously and if the terrain consist of obstacles, the complexity increases. In this article, we propose an are coveragealgorithm that is suitable for planning paths for autonomous agents assigned to cover an area. Our algorithm is a polynomial timeheuristic algorithm which guarantees complete coverage of an area consisting of obstacles. At each step of the algorithm, and agent observes the neighboring cells and moves to a cell that is surrounded by more obstacles or by already visited cells. With this simple behavior, we show in a simulated environment with a different number of agents that our method performs comparably to, and in certain configurations, better than the existing methods. An important advantage of our method is that is is failsafe. In other words, if a subset of the agents fails to complete their duties, the remaining agents suffice to cover any unvisited parts of an assigned area. This is due to the fact that (i) our algoriithm can run online, (ii) the agents are able to perceive only the grids in their neighborhood and (iii) there is no cooperation among them.