Time-Optimal Gathering Algorithm of Mobile Robots with Local Weak Multiplicity Detection in Rings

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

著者

• IZUMI Tomoko

  College of Information Science and Engineering, Ritsumeikan University

• OOSHITA Fukuhito

  Graduate School of Information Science and Technology, Osaka University

• Izumi Taisuke

  Graduate School Of Engineering Nagoya Institute Of Technology

• Ooshita Fukuhito

  Graduate School Of Information Science And Technology Osaka University

• Kamei Sayaka

  Graduate School of Engineering, Hiroshima University

関連論文

• A Self-Adaptive Routing Protocol in Wireless LANs Based on Attractor Selection
• A Biologically Inspired Self-Adaptation of Replica Density Control
• A Message-Efficient Peer-to-Peer Search Protocol Based on Adaptive Index Dissemination
• An Efficient Index Dissemination in Unstructured Peer-to-Peer Networks
• Self-Adaptive Mobile Agent Population Control in Dynamic Networks Based on the Single Species Population Model(Distributed Cooperation and Agents)
• Timed Atomic Broadcast Resiliet to Multiple Timing Faults
• Timed Atomic Broadcast Resiliet to Multiple Timing Faults
• Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model(Parallel and Distributed Computing,Foundations of Computer Science)
• Scheduling for Gather Operation in Heterogeneous Parallel Computing Environments
• Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment Property
• Distributed Construction Protocols of Probabilistic Degree-Weighted Peer-to-Peer Overlays
• Autonomous Multi-Source Multi-Sink Routing in Wireless Sensor Networks
• Autonomous Multi-Source Multi-Sink Routing in Wireless Sensor Networks
• Time-Optimal Gathering Algorithm of Mobile Robots with Local Weak Multiplicity Detection in Rings

もっと見る 閉じる

スポンサーリンク