・名古屋工業大学学術機関リポジトリは、名古屋工業大学内で生産された学術情報を電子的に収集・保存・発信するシステムです。 ・論文の著作権は、著者または出版社が保持しています。著作権法で定める権利制限規定を超える利用については、著作権者に許諾を得てください。 ・著者版フラグに「author」と記載された論文は、著者原稿となります。実際の出版社版とは、レイアウト、字句校正レベルの異同がある場合もあります。 ・Nagoya Institute of Technology Repository Sytem is built to collect, archive and offer electronically the academic information produced by Nagoya Institute of Technology. ・The copyright and related rights of the article are held by authors or publishers. The copyright owners' consents must be required to use it over the curtailment of copyrights. ・Textversion "Author " means the article is author's version. Author version may have some difference in layouts and wordings form publisher version.
The gathering problem of anonymous and oblivious mobile robots isone of fundamental problems in the theoretical mobile robotics. We consider thegathering problem in unoriented and anonymous rings, which requires that allrobots gather at a non-predefined node. Since the gathering problem cannot besolved without any additional capability to robots, all the previous works assumesome capability of robots, such as accessing the memory on node. In this paper,we focus on the multiplicity capability. This paper presents a deterministic gatheringalgorithm with local-weak multiplicity, which provides the robot with theinformation about whether its current node has more than one robot or not. Thisassumption is strictly weaker than that by previous works. Moreover, we showthat our algorithm is asymptotically time-optimal one, that is, the time complexityof our algorithm is O(n), where n is the number of nodes. Interestingly, inspite of assuming the weaker assumption, it achieves significant improvementcompared to the previous algorithm, which takes O(kn) time for k robots.
The original publication will be available at www.springerlink.comLNCS series17th International Colloquium on Structural Information and Commuication Complexity
Mobile Robots Gathering Algorithm with Local Weak Multiplicity in Rings
本文_fulltext
(149.9KB)
