Leader election problem versus pattern formation problem
From MaRDI portal
Abstract: Leader election and arbitrary pattern formation are funda- mental tasks for a set of autonomous mobile robots. The former consists in distinguishing a unique robot, called the leader. The latter aims in arranging the robots in the plane to form any given pattern. The solv- ability of both these tasks turns out to be necessary in order to achieve more complex tasks. In this paper, we study the relationship between these two tasks in a model, called CORDA, wherein the robots are weak in several aspects. In particular, they are fully asynchronous and they have no direct means of communication. They cannot remember any previous observation nor computation performed in any previous step. Such robots are said to be oblivious. The robots are also uniform and anonymous, i.e, they all have the same program using no global parameter (such as an identity) allowing to differentiate any of them. Moreover, we assume that none of them share any kind of common coordinate mechanism or common sense of direction and we discuss the influence of a common handedness (i.e., chirality). In such a system, Flochini et al. proved in [11] that it is possible to elect a leader for n geq 3 robots if it is possible to form any pattern for n geq 3. In this paper, we show that the converse is true for n geq 4 when the robots share a common handedness and for n geq 5 when they do not. Thus, we deduce that with chirality (resp. without chirality) both problems are equivalent for n geq 4 (resp. n geq 5) in CORDA.
Recommendations
- Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
- On fast pattern formation by autonomous robots
- Leader election and gathering for asynchronous fat robots without common chirality
- Arbitrary pattern formation with four robots
- Pattern formation by oblivious asynchronous mobile robots
Cited in
(22)- Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane
- Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
- Monotonic self-stabilization and its application to robust and adaptive pattern formation
- Arbitrary pattern formation on infinite regular tessellation graphs
- On fast pattern formation by autonomous robots
- Building a nest by an automaton
- Asynchronous arbitrary pattern formation: the effects of a rigorous approach
- Plane formation by synchronous mobile robots without chirality
- Deterministic geoleader election in disoriented anonymous systems
- Leader election and gathering for asynchronous fat robots without common chirality
- Building a nest by an automaton
- Pattern formation by oblivious asynchronous mobile robots
- Optimal exclusive perpetual grid exploration by luminous myopic opaque robots with common chirality
- A structured methodology for designing distributed algorithms for mobile entities
- Arbitrary pattern formation on a continuous circle by oblivious robot swarm
- Exploration of convex terrains by a deterministic automaton with pebbles
- Exploring wedges of an oriented grid by an automaton with pebbles
- Move-optimal arbitrary pattern formation by mobile robots on rectangular grid using near-optimal spatial area
- Universal pattern formation by oblivious robots under sequential schedulers
- Pattern formation of mobile agents in dynamic grids
- Getting close without touching: near-gathering for autonomous mobile robots
- Autonomous mobile robots with lights
This page was built for publication: Leader election problem versus pattern formation problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3588308)
