Competitive Ant Coverage: The Value of Pursuit

This paper studies the problem of Competitive Ant Coverage, in which two ant-like robots with very limited capabilities in terms of sensing range, computational power, and knowledge of the world compete in an area coverage task. We examine two variants of the problem that differ in the robot's objective: either being the First to Cover a Cell (FCC), or being the Last to Cover a Cell (LCC). Each robot's goal is to acquire (by visiting first or last, respectively) more cells than the opposing robot, and by that win the game. We examine the problem both theoretically and empirically, and show that the main strategy for dominance revolves around the ability to pursue: in LCC, we wish to pursue the opposing robot, whereas in FCC, we wish to create a scenario wherein the opposing robot pursues us. We find that this ability relies more heavily on knowledge of the opponent's strategy than on the robot's sensing capabilities. Moreover, given the robot's limited capabilities, we find that this knowledge-gap cannot be easily mitigated by learning.