Fence Patrolling with Two-speed Robots

Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Fraser MacQuarrie, Dominik Pajak

2016

Abstract

A fence is to be patrolled collectively by n robots. At any moment a robot may move in one of the two possible states: walking or patrolling. Each state is associated with a maximal moving speed which cannot be exceeded. We want to schedule the perpetual movements of the robots so as to minimize the idleness, defined as the smallest time interval within which every point is always visited by some robot. First, we give a centralized algorithm constructing schedules with optimal idleness, and subsequently we show an interesting application to a transportation problem concerning Scheduling with Regular Delivery. Our main contribution is the study of distributed, dynamical schedules for patrolling robots with only primitive capabilities. Surprisingly, we are able to design a dynamic schedule for very weak collections of two robots (silent, oblivious, passively mobile), achieving the optimal idleness. Part of our contribution is a very technical analysis of the dynamics of special families of dynamical systems of n robots that we call regular. For such systems we also propose a highly non-trivial O(n2) algorithm to decide whether or not robots converge to a stable configuration thus verifying if the dynamic schedule is optimal.

Paper Citation

in Harvard Style

Czyzowicz J., Georgiou K., Kranakis E., MacQuarrie F. and Pajak D. (2016). Fence Patrolling with Two-speed Robots . In Proceedings of 5th the International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES, ISBN 978-989-758-171-7, pages 229-241. DOI: 10.5220/0005687102290241

in Bibtex Style

@conference{icores16,
author={Jurek Czyzowicz and Konstantinos Georgiou and Evangelos Kranakis and Fraser MacQuarrie and Dominik Pajak},
title={Fence Patrolling with Two-speed Robots},
booktitle={Proceedings of 5th the International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES,},
year={2016},
pages={229-241},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005687102290241},
isbn={978-989-758-171-7},
}

in EndNote Style

TY - CONF
JO - Proceedings of 5th the International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES,
TI - Fence Patrolling with Two-speed Robots
SN - 978-989-758-171-7
AU - Czyzowicz J.
AU - Georgiou K.
AU - Kranakis E.
AU - MacQuarrie F.
AU - Pajak D.
PY - 2016
SP - 229
EP - 241
DO - 10.5220/0005687102290241