Robotics

We address questions in the field mobile sensors modeled as robots with minimal sensing. Minimalistic models provide a clean conceptual framework for performance analysis and lend insights into the inherent complexity of various tasks: the positive results identify the easy problems, while the negative results help isolate the difficult problems that necessitate richer functionality and sensing.

We consider problems of geometric exploration and self-deployment for simple robots that can only sense the combinatorial (non-metric) features of their surroundings. Additionally, we study the problem of counting identical targets spread in a polygon. Interestingly, in some cases robots with a seemingly different level of sophistication turn out to be equivalent, i.e., they are able to solve the same set of problems. Inspired by this observation we started the analysis of the relative strength of different robot models by establishing a hierarchy.

The following picture illustrates an open problem called the Rendezvous problem. Given a set of robots dispersed in a polygon, is it possible for them to reach a position in such a way, that they all mutually visible?