TY - GEN
T1 - Tight analysis of a collisionless robot gathering algorithm
AU - Sharma, Gokarna
AU - Busch, Costas
AU - Mukhopadhyay, Supratik
AU - Malveaux, Charles
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/12/11
Y1 - 2015/12/11
N2 - We consider the fundamental problem of gathering a set of n robots in the Euclidean plane which have a physical extent and hence they cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem has applications in many real world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (SOFSEM 2011) gave a local greedy algorithm in a synchronous setting and proved that, for the discrete version of the problem where robots movements are restricted to the positions on an integral grid, their algorithm solves this problem in O(nR) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this paper, we improve significantly the round complexity of their algorithm to R + 2 · (n - 1) rounds. We also prove that there are initial configurations of n robots in this problem where at least R + (n - 1) over 2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + (n - 1) rounds for the algorithm of Cord-Landwehr et al.. These results altogether provide a tight runtime analysis of their algorithm.
AB - We consider the fundamental problem of gathering a set of n robots in the Euclidean plane which have a physical extent and hence they cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem has applications in many real world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (SOFSEM 2011) gave a local greedy algorithm in a synchronous setting and proved that, for the discrete version of the problem where robots movements are restricted to the positions on an integral grid, their algorithm solves this problem in O(nR) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this paper, we improve significantly the round complexity of their algorithm to R + 2 · (n - 1) rounds. We also prove that there are initial configurations of n robots in this problem where at least R + (n - 1) over 2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + (n - 1) rounds for the algorithm of Cord-Landwehr et al.. These results altogether provide a tight runtime analysis of their algorithm.
UR - http://www.scopus.com/inward/record.url?scp=84958152651&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958152651&partnerID=8YFLogxK
U2 - 10.1109/IROS.2015.7354108
DO - 10.1109/IROS.2015.7354108
M3 - Conference contribution
AN - SCOPUS:84958152651
T3 - IEEE International Conference on Intelligent Robots and Systems
SP - 5189
EP - 5194
BT - IROS Hamburg 2015 - Conference Digest
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2015
Y2 - 28 September 2015 through 2 October 2015
ER -