Competitive Coverage: (Full) Information as a Game Changer

This paper introduces the competitive coverage problem, a new variant of the robotic coverage problem in which a robot R competes with another robot O in order to be the first to cover an area. In the variant discussed in this paper, the asymmetric competitive coverage, O is unaware of the existence of R, which attempts to take that fact into consideration in order to succeed in being the first to cover as many parts of the environment as possible. We consider different information models of R that define how much it knows about the location of O and its planned coverage path. We present an optimal algorithm for R in the full-information case, and show that unless R has information about O’s initial location, it is as if it has no information at all. Lastly, we describe a correlation between the time it takes R to reach O’s initial location and the coverage paths quality, and present a heuristic algorithm for the case in which R has information only about O’s initial location, showing its superiority compared to other coverage algorithms in rigorous simulation experiments.