
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

TimeOptimal Gathering Algorithm of Mobile Robots with Local Weak Multiplicity Detection in Rings
Tomoko IZUMI Taisuke IZUMI Sayaka KAMEI Fukuhito OOSHITA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E96A
No.6
pp.10721080 Publication Date: 2013/06/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E96.A.1072
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: mobile robots, gathering problem, ring graphs, multiplicity detection,
Full Text: PDF(1.1MB)>>
Summary:
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 nonpredefined 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 localweak 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 timeoptimal 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.

