Patrolling by faulty robots

23^rd June 2015, 13:00 Ashton Lecture Theater
Prof Jurek Czyzowicz
Université du Québec en Outaouais
Canada

Abstract

Mobile robots collaborate in order to solve efficiently the central problems in algorithmics of distributed computing like searching/exploration, rendez-vous or pattern formation. Patrolling is a perpetual traversal of an environment by a collection of mobile robots. The standard measure of efficiency of a patrolling algorithm is defined by its idleness – the minimal time interval during which every point of the environment is always visited by at least one robot. Boundary patrolling and fence patrolling were fundamental problems investigated by the robotics community in the last decade.

We sketch briefly previous results concerning the algorithms for the boundary and fence-patrolling problem. When some (unknown) robots of the collection cannot perform their duties, the fence patrolling algorithms become surprisingly unnatural. In more details we discuss a new algorithm for patrolling by unreliable robots. We show that the presented algorithm achieves the idleness, which is the best possible.