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.

About Jurek Czyzowicz

Both MSc degree (1971) and PhD (1976) are from Warsaw University. Before moving to Canada in 1984 I worked in Poland (Polish Academy of Sciences, Warsaw University, Insitute of Mathematical Machines) and Algeria (Université de Constantine). In University of Québec from 1984 until now.

Presently adjunct prof at University of Ottawa, Carleton University, University of Liverpool and Warsaw University. Research interest in algorithms, distributed computing and computational geometry. Father of 5 children (42, 37, 32, 31, 24). Seven times bridge champion of Canada in pair and team competition. Bronze medal in Senior Teams at World Bridge Championships in 2014.

Personal site

This event will be conducted in English