Site Accessibility Statement
Wilfrid Laurier University Faculty of Science
February 28, 2015

Canadian Excellence



Boundary Patrolling by Mobile Agents

Oct 23/12

October 25, 2012, 4pm

Room: 2C3 (WLU Arts Bldg)

Boundary Patrolling by Mobile Agents

Evangelos Kranakis

Carleton University

Abstract: We study a problem concerning the traversal of a rectifiable curve withk ?
1 mobile robots so as to minimize the idle time (i.e., duration of time any point on the curve is left unvisited by a mobile agent). At any time during the traversal the speed of the robots cannot exceed a max value (set equal to 1 for all robots). The rectifiable curve can be either closed (e.g., cycle) or open (e.g., segment) and consists of alternating contiguous subsegments of vital intervals (that must be traversed) and neutral intervals (that do not have to be traversed).Given such a rectifiable curve, our goal is to give algorithms describing the motion boundaries and movement of the robots within

the curve so that the idle time is optimized. Despite its apparent simplicity, designing such algorithms and proving their correctness turns out to be quite a challenging problem. We give optimal algorithms for solving this problem in the case where the rectifiable curve is either a (straight line) segment or a cycle.

About the Speaker:Dr. Kranakis has published extensively in the analysis of algorithms, bioinformatics, communication and data (ad hoc and wireless) networks,

computational and combinatorial geometry, distributed computing, and network security. He is the author of Primality and Cryptography (Wiley-Teubner series in Computer Science, 1986), and co-author of Boolean Functions and Computation Models with Peter Clote (Springer Verlag Texts in Theoretical Computer Science, 2002) and Principles of Ad Hoc Networking with Michel Barbeau (Wiley, 2007). He is currently CNS (Communication,

Networks, and Security) Theme Leader in the MITACS NCE (Networks of Centers of Excellence).

View all Mathematics news | View all Faculty of Science news
View all Laurier news