Dispersion of Mobile Robots Tolerating Faults
| Autor: | Gokarna Sharma, Partha Sarathi Mandal, Debasish Pattanayak |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Discrete mathematics
Computer science Mobile robot 0102 computer and information sciences 02 engineering and technology Load balancing (computing) 01 natural sciences Upper and lower bounds Computer Science::Robotics Asymptotically optimal algorithm 010201 computation theory & mathematics Distributed algorithm 0202 electrical engineering electronic engineering information engineering Robot 020201 artificial intelligence & image processing Node (circuits) Time complexity |
| Zdroj: | ICDCN (Adjunct Volume) |
| Popis: | The dispersion problem on graphs asks k ≤ n robots initially placed arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration with each robot on a distinct node. This problem is of interest due to its relationship to many fundamental robot coordination problems, such as exploration, scattering, load balancing, relocation of self-driven electric cars (robots) to recharge stations (nodes), etc. The objective of this problem is to minimize simultaneously (or provide trade-off between) two fundamental performance metrics: (i) time to achieve dispersion and (ii) memory needed at each robot. The literature solved this problem on arbitrary graphs considering fault-free robots. In this paper, we study dispersion on arbitrary graphs considering crash faulty robots – a robot which has crashed vanishes from the system along with the information it carried. We present a deterministic O((min (m, kΔ) · f) time algorithm achieving dispersion with O(log (max (k, Δ))) bits memory at each robot starting from rooted initial configurations such that all k robots are on a single node, where m is the number of edges, f ≤ k is the number of crashes, and Δ is the maximum degree of the graph. When Δ and f are both O(1), time complexity of our algorithm asymptotically matches the lower bound Ω(k) and when Δ and f are both polylog(n), it is polylog(n) factor away from the lower bound Ω(k). The memory bound is asymptotically optimal. To the best of our knowledge, this is the first result for dispersion with faults in arbitrary graphs, even when starting from rooted initial configurations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|