Pattern formation for fat robots with memory

Distributed systems (68M14) Artificial intelligence for robotics (68T40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)

Review text

This is an interesting paper dealing with the subject of pattern formation for fat robots with memory. Let is considered the set-up. \N\NSuppose we are given a system of unit-disk robots in \(R^2\), that is, two-dimensional Euclidean space. The paper under review studies a system of unit-disk robots in the two-dimensional Euclidean plane and studies the problem of forming a pattern using these robots. Let us be more specific. The number of robots is \(n\geq 1\) which is fixed. The robots are also indistinguishable, possibly fat, autonomous, anonymous and silent. The robots must do the following.\N\NThey must reposition themselves to form a given target pattern from an arbitrary starting position. In this sense, the authors consider this as the pattern formation problem. The authors explain that the pattern formation problem comes about under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between the two robots.\N\NThe authors assume that a given robot's movement cannot be interrupted by an adversary and that robots have a small \(O(1)\)-sized memory that they can use to store information, but that cannot be communicated to the other robots. \N\NNow fix \(q>0\). The authors construct an algorithm which runs in \(O(n) + O(q\log n)\) rounds with probability at least \(1-n^{-q}\). The algorithm is collision-free and does not require the knowledge of the number of robots.\N\NThe paper is well written with an excellent set of references.

Cites work

This page was built for publication: Pattern formation for fat robots with memory

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