Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Pattern Formation by Mobile Robots with Limited Visibility
verfasst von : Yukiko Yamauchi, Masafumi Yamashita
Erschienen in: Structural Information and Communication Complexity
Verlag: Springer International Publishing
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
We investigate the pattern formation problem by mobile robots with
limited
visibility that can observe the positions of robots within limited distance. For robots with
unlimited
visibility, Fujinaga et al. (DISC 2012) showed that asynchronous oblivious robots have the same formation power as fully-synchronous non-oblivious robots, that is, starting from any initial configuration
I
, target pattern
F
is formable if and only if
ρ
(
I
) divides
ρ
(
F
) where
ρ
(·) is the geometric symmetricity. We first show that fully-synchronous oblivious robots with limited visibility cannot form
F
even when
ρ
(
I
) divides
ρ
(
F
). Hence, limited visibility substantially weakens the formation power of oblivious robots. Secondly, we show that despite limited visibility, semi-synchronous robots with rigid moves, and fully-synchronous robots with non-rigid moves have the same formation power as robots with unlimited visibility. Consequently, local memory is necessary and sufficient for these robots.