Abstract | ||
---|---|---|
We deal with a team of autonomous robots that are endowed with motion actuators and visibility sensors. Those robots are weak and evolve in a discrete environment. By weak, we mean that they are anonymous, uniform, unable to explicitly communicate, and oblivious. We first show that it is impossible to solve the terminating exploration of a simple torus of arbitrary size with less than 4 or 5 such robots, respectively depending on whether the algorithm is probabilistic or deterministic. Next, we propose in the SSYNC model a probabilistic solution for the terminating exploration of torus-shaped networks of size \(\ell \times L\), where \(7 \le \ell \le L\), by a team of 4 such weak robots. So, this algorithm is optimal w.r.t. the number of robots. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/s00607-018-0595-8 | NETYS |
Keywords | Field | DocType |
Robot,Torus,Exploration,Obliviousness,68W15 | Randomized algorithm,Mathematical optimization,Visibility,Theoretical computer science,Torus,Probabilistic logic,Robot,Mathematics,Mobile robot,Homogeneous space,Actuator | Conference |
Volume | Issue | ISSN |
101.0 | SP9 | 0010-485X |
Citations | PageRank | References |
3 | 0.38 | 9 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stéphane Devismes | 1 | 192 | 25.74 |
Anissa Lamani | 2 | 118 | 11.31 |
Franck Petit | 3 | 736 | 60.02 |
Sébastien Tixeuil | 4 | 978 | 93.01 |