Weak robots performing conflicting tasks without knowing who is in their team

Abstract

In this paper, we consider the problem of having two teams of identical robots, each with its own task, inhabiting the same space. The robots operate in Look-Compute-Move cycles and each team needs to solve its own task without being able to distinguish which of the robots belong to its team. The tasks we consider are two classical conflicting pattern formation problems: gathering (where the robots need to gather at some arbitrary point), and circle formation (where the robots need to place themselves in distinct points of a circle). We show how to achieve this double goal using robots that are anonymous, oblivious, silent, and asynchronous; the robots share a coordinate system, but with possibly different orientations. Unlike all the previous literature, which considers a single team of robots with a single goal, this is the first result addressing multiple anonymous teams of robots performing different (and possibly conflicting) tasks in the same space at the same time.