2010 | OriginalPaper | Buchkapitel
Connectivity-Preserving Scattering of Mobile Robots with Limited Visibility
verfasst von : Taisuke Izumi, Maria Gradinariu Potop-Butucaru, Sébastien Tixeuil
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The
scattering
problem is a fundamental task for mobile robots, which requires that no two robots share the same position. We investigate the scattering problem in the limited-visibility model. In particular, we focus on
connectivity-preservation
property. That is, the scattering must be achieved so that the disconnection of the visibility graph never occurs (in the visibility graph robots are the nodes of the graph and the edges are their visibility relationship). The algorithm we propose assumes ATOM (
i.e.
semi-synchronous) model. In these settings our algorithm guarantees the connectivity-preserving property, and reaches a scattered configuration within
O
( min {
n
,
D
2
+ log
n
}) asynchronous rounds in expectation, where
D
is the diameter of the initial visibility graph. Note that the complexity analysis is
adaptive
since it depends on
D
. This implies that our algorithm quickly scatters all robots crowded in a small-diameter visibility graph. We also provide a lower bound of Ω(
n
) for connectivity-preserving scattering. It follows that our algorithm is optimal in the sense of the non-adaptive analysis.