Circle formation of weak robots and Lyndon words

DOI10.1016/J.IPL.2006.09.008MaRDI QIDQ845920zbMATH OpenOpenAlexFDO

Authors Yoann Dieudonné, Franck Petit

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0605096

zbMATH Keywords

distributed computingmobile robot networksformation of geometric patternsself-deployment

Mathematics Subject Classification ID

Artificial intelligence for robotics (68T40) Distributed systems (68M14)

Abstract: A Lyndon word is a non-empty word strictly smaller in the lexicographic order than any of its suffixes, except itself and the empty word. In this paper, we show how Lyndon words can be used in the distributed control of a set of n weak mobile robots. By weak, we mean that the robots are anonymous, memoryless, without any common sense of direction, and unable to communicate in an other way than observation. An efficient and simple deterministic protocol to form a regular n-gon is presented and proven for n prime.

Cites work

• scientific article; zbMATH DE number 1629980 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1049494 (Why is no real title available?)
• A public key cryptosystem based on Lyndon words
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• Periodic musical sequences and Lyndon words
• Self-stabilization
• Structural Information and Communication Complexity

Cited in

(5)

• Deterministic geoleader election in disoriented anonymous systems
• Computing by mobile robotic sensors
• Optimal exclusive perpetual grid exploration by luminous myopic opaque robots with common chirality
• Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity
• The ``runs theorem

Describes a project that uses

Uses Software

• STAR

This page was built for publication: Circle formation of weak robots and Lyndon words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845920)