Paper Info
Title
Mobile robots gathering algorithm with local weak multiplicity in rings
Abstract
The gathering problem of anonymous and oblivious mobile robots is one of fundamental problems in the theoretical mobile robotics. We consider the gathering problem in unoriented and anonymous rings, which requires that all robots gather at a non-predefined node. Since the gathering problem cannot be solved without any additional capability to robots, all the previous works assume some capability of robots, such as accessing the memory on node. In this paper, we focus on the multiplicity capability. This paper presents a deterministic gathering algorithm with local-weak multiplicity, which provides the robot with the information about whether its current node has more than one robot or not. This assumption is strictly weaker than that by previous works. Moreover, we show that our algorithm is asymptotically time-optimal one, that is, the time complexity of our algorithm is O(n), where n is the number of nodes. Interestingly, in spite of assuming the weaker assumption, it achieves significant improvement compared to the previous algorithm, which takes O(kn) time for k robots.
Year
DOI
Venue
2010
10.1007/978-3-642-13284-1_9
SIROCCO
Keywords
Field
DocType
anonymous ring,mobile robot,deterministic gathering algorithm,additional capability,gathering problem,multiplicity capability,fundamental problem,previous work,local weak multiplicity,previous algorithm,current node,non-predefined node,time complexity
Multiplicity (mathematics),Algorithm,Theoretical computer science,Distributed algorithm,Artificial intelligence,Time complexity,Robot,Spite,Robotics,Mobile robot,Mathematics,Distributed computing
Conference
Volume
ISSN
ISBN
6058
0302-9743
3-642-13283-9
Citations 
PageRank 
References 
28
1.15
11
Authors
4
Name
Order
Citations
PageRank
Tomoko Izumi114121.33
Taisuke Izumi228439.02
Sayaka Kamei318621.28
Fukuhito Ooshita423636.40