Name
Abstract | ||
|---|---|---|
We consider the problem of gathering $(n)$ anonymous and oblivious mobile robots, which requires that all robots meet in finite time at a nonpredefined point. While the gathering problem cannot be solved deterministically without assuming any additional capabilities for the robots, randomized approaches easily allow it to be solvable. However, the randomized solutions currently known have a time complexity that is exponential in $(n)$ with no additional assumption. This fact yields the following two questions: Is it possible to construct a randomized gathering algorithm with polynomial expected time? If it is not possible, what is the minimal additional assumption necessary to obtain such an algorithm? In this paper, we address these questions from the aspect of multiplicity-detection capabilities. We newly introduce two weaker variants of multiplicity detection, called local-strong and local-weak multiplicity, and investigate whether those capabilities permit a gathering algorithm with polynomial expected time or not. The contribution of this paper is to show that any algorithm only assuming local-weak multiplicity detection takes exponential number of rounds in expectation. On the other hand, we can obtain a constant-round gathering algorithm using local-strong multiplicity detection. These results imply that the two models of multiplicity detection are significantly different in terms of their computational power. Interestingly, these differences disappear if we take one more assumption that all robots are scattered (i.e., no two robots stay at the same location) initially. We can obtain a gathering algorithm that takes a constant number of rounds in expectation, assuming local-weak multiplicity detection and scattered initial configurations. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/TPDS.2012.212 | Parallel and Distributed Systems, IEEE Transactions |
Keywords | Field | DocType |
computational complexity,mobile robots,randomised algorithms,constant-round gathering algorithm,local-strong multiplicity detection,local-weak multiplicity detection,multiplicity-detection capabilities,oblivious mobile robots,polynomial expected time,polynomial-time randomized gathering algorithm,randomized solutions,time complexity,Distributed algorithm,autonomous mobile robots,gathering problem,randomized algorithm | Randomized algorithm,Polynomial,Computer science,Multiplicity (mathematics),Theoretical computer science,Distributed algorithm,Time complexity,Robot,Mobile robot,Distributed computing,Computational complexity theory | Journal |
Volume | Issue | ISSN |
24 | 4 | 1045-9219 |
Citations | PageRank | References |
11 | 0.60 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Taisuke Izumi | 1 | 284 | 39.02 |
| Tomoko Izumi | 2 | 141 | 21.33 |
| Sayaka Kamei | 3 | 186 | 21.28 |
| Fukuhito Ooshita | 4 | 236 | 36.40 |