Paper Info
Title
Time-Optimal Gathering Algorithm Of Mobile Robots With Local Weak Multiplicity Detection In Rings
Abstract
The gathering problem of anonymous and oblivious mobile robots is one of the fundamental problems in the theoretical mobile robotics. We consider the gathering problem in unoriented and anonymous rings, which requires that all robots eventually keep their positions at a common non-predefined node. Since the gathering problem cannot be solved without any additional capability to robots, all the previous results assume some capability of robots, such as the agreement of local view. In this paper, we focus on the multiplicity detection capability. This paper presents a deterministic gathering algorithm with local-weak multiplicity detection, which provides a robot with information about whether its current node has more than one robot or not. This assumption is strictly weaker than that in previous works. Our algorithm achieves the gathering from an aperiodic and asymmetric configuration with 2 < k < n/2 robots, where n is the number of nodes. We also show that our algorithm is asymptotically time-optimal one, i.e., the time complexity of our algorithm is O(n). Interestingly, despite the weaker assumption, it achieves significant improvement compared to the previous algorithm, which takes O(kn) time for k robots.
Year
DOI
Venue
2013
10.1587/transfun.E96.A.1072
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Keywords
Field
DocType
mobile robots, gathering problem, ring graphs, multiplicity detection
Discrete mathematics,Multiplicity (mathematics),Theoretical computer science,Mobile robot,Mathematics
Journal
Volume
Issue
ISSN
E96A
6
0916-8508
Citations 
PageRank 
References 
4
0.43
12
Authors
4
Name
Order
Citations
PageRank
Tomoko Izumi114121.33
Taisuke Izumi228439.02
Sayaka Kamei318621.28
Fukuhito Ooshita423636.40