Swarm Robots
Group of Tiny Mobile Entities
Autonomous
Local Coordination
Coordinate via local sensing and communication
Anonymous
No unique IDs
Homogeneous
All robots run the same algorithm
Vision Sensors
Observe positions of other visible robots
LCM Execution Cycle
L
LOOK
Robot takes a snapshot — observes positions and light colors of all visible robots
C
COMPUTE
Based on the snapshot, the robot executes the algorithm and decides its next destination
M
MOVE
Robot moves toward the computed destination point
↻ Robots repeatedly execute the LCM cycle
Luminous Robots
External Visible Lights
Color Palette
Predefined finite color set
Weak Communication
due to light-based communication
Persistent Memory
Colors persist across LCM cycles — everything else is erased
View of a Robot
Observation Mode
Own
local coordinate system with the current location as the origin.
Sensor Range
Unlimited visibility, but might be obstructed.
Obstructed Visibility
Opaque Robots
i.e., non-transparent
Collinearity Creates Obstruction
The middle robot blocks the line of sight
The Mutual Visibility Problem
Goal: Move the robots so that no three robots are collinear, i.e., every pair of robots becomes mutually visible.
Initial Configuration
Target Configuration
Useful for Problems like:
-
Pattern Formation
-
Gathering
-
Leader Election in a group of robots
Collision is not Allowed
Collision: When two robots are located at the same time and the same place, they meet a collision.
Mutual Visibility does not allow collision.
Fault Model: Mobility Fault
Cannot Move
A faulty robot loses its ability to move to a new position
Light Works
Its light remains fully functional — it can still execute the algorithm and change colors
Fault may occur at any time — even during mid-movement
Poudel, P., Aljohani, A., Sharma, G.:
Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement.
Theoretical Computer Science 850, 116–134 (2021)
Fault-Tolerant Mutual Visibility
Aim is to achieve mutual visibility among non-faulty robots.
No three non-faulty robots should be collinear
should not occur
No faulty robot should lie between two non-faulty robots
should not occur
Three Important Aspects
Mobility Fault
A faulty robot cannot move but still executes the algorithm and can change its light color.
Disorientation
No agreement on any coordinate axis — each robot has its own local frame.
Asynchrony
No notion of global time — any robot can be activated anytime under a fair scheduler.
Comparison with State-of-the-Art
| Paper | No. of Faults | Scheduler | Axes Agreement | Colors | Time Complexity |
|---|---|---|---|---|---|
| Sharma et al. | None | ASYNC | No | 47 | $O(1)$ |
| Aljohani & Sharma | 1 | SSYNC | Yes (both axes) | 3 | - |
| Poudel et al. | $f$ | SSYNC | Yes (one axis) | 2 | $O(N)$ |
| Poudel et al. | $f$ | ASYNC | Yes (one axis) | 3 | $O(N)$ |
| This Work (Ours) | $f$ | ASYNC | No | 26 | $O(N)$ |
Power of the Adversary
Challenges of Mobility Fault
Movements do not always solve the problem.
Challenges of Mobility Fault
Power of colors might still be insufficient if movements are not carefully planned.
Some Impossible Configurations
Symmetric configurations with faulty robot lying at the center of symmetry.
Careful Movements Required
Cannot move all robots together -- that might create new collinearity issues.
Disjoint Convex Layers
Outermost Layer $\mathcal{L}^1$
- Consider the convex hull of all robots.
- The boundary of this hull forms $\mathcal{L}^1$.
Layer $\mathcal{L}^j$
For \(j \geq 2\), layer \(\mathcal{L}^{j}\) is obtained recursively after removing all robots from \(\mathcal{L}^{1} \cup \cdots \cup \mathcal{L}^{j-1}\).
Innermost Layer $\mathcal{L}^k$
Corner, Boundary and Interior Robots
- Corner robots are the ones on the vertices of the convex hull.
- Boundary robots lie on sides connecting vertices of the convex hull.
- Interior robots lie strictly inside the convex hull.
Corner
Boundary
Interior
This status remains intact even from a local point of view.
Broader Strategy: Where to Move?
- Shall we move the (non-faulty) robots in the outward direction?
- No. Because, faulty robots may obstruct visibility and robots do not know $N$ and $f$.
Broader Strategy: Where to Move?
- A natural option is to move the non-faulty robots inward.
- Robots can form a new convex shape inside the innermost layer, leaving the faulty robots outside.
Innermost Layer Detection
This subroutine may be of independent interest !
(for problems like universal dancing)
(for problems like universal dancing)
Two Possibilities of Innermost Layer
Non-linear Innermost Layer
Linear Innermost Layer
Our Aim: in Non-linear Case
We bring all
non-faulty robots
to the
innermost layer,
starting from the
outermost layer,
and then proceeds
layer by layer.
How to ensure that a robot lying on the
outermost layer
sees the entire
innermost layer
before the movement?
Visible Area for a Robot
The visible area of a robot is the polygonal subregion of the plane from which the robot can see all stationary robots without obstruction.
Robot $r$ (observer)
Visible robots to $r$
Not visible to $r$
$r_1, r_2$: neighbors on (local) convex hull
●
$u, v$: midpoints of $\overline{rr_1}$ and $\overline{rr_2}$
Algorithm for Non-linear Case
01
A corner robot
r
first moves to its
visible area
so that it can see the entire
innermost layer, which are stationary now.
02
Compute the
C.G.
of the
innermost layer
and find the
point of intersection
of the
innermost layer
and the line segment connecting the
C.G.
and the current position of
r.
03
If the point of intersection is
occupied,
shift the
target point
a little on the
innermost layer itself.
Algorithm for Non-linear Case
If the movement of
$r$
is successful, its neighboring boundary robots become
new corner robots.
However, A Robot Might Be Faulty
So, how to distinguish the the following two configurations for a robot $r$?
$r$
failed to reach the
innermost layer
$r$
has reached the
innermost layer
Fault Detection
Let $S$ = the color INNERMOST + the colors used till now from the start of movement.
$\mathcal{CH}_r^S$ = convex hull of the robots with colors in $S$ that are visible to $r$.
$\mathcal{CH}_r^S$ = convex hull of the robots with colors in $S$ that are visible to $r$.
01
Observe that,
a corner robot $r$
cannot remain a corner robot,
if it has reached the
innermost layer without fault.
02
When $r$ finds itself still a corner robot on $\mathcal{CH}_r^S$, it switches to
FAULT.
03
When $r$ finds itself still a corner robot on $\mathcal{CH}_r^S$, it switches to
FAULT.
04
Since FAULT $\notin S$, the robot $r_1$ becomes a corner robot on $\mathcal{CH}_{r_1}^S$, which earlier was a boundary robot before $r$ switched to FAULT.
Movement From Innermost Layer
01
When robots are gathered on the innermost layer and faulty robots are outside, corner robots on innermost layer contract the layer.
02
Such a robot moves inside the innermost layer so that its neighboring boundary robots on the innermost layer become new corners.
03
Repeating this process, non-faulty robots achieve mutual visibility.
Algorithm for Linear Case
Our target is to move the
non-faulty robots
on an
ellipse
whose major axis is the
line segement joining the central robots
on the
innermost layer.
Algorithm for Linear Case
It does not have to be a perfect ellipse.
The half ellipse on one half plane may have a different minor axis length than that of the half ellipse on the other half plane.
But
their major axes are the same,
so we still get a
convex shape.
We want that the
non-faulty robots
lying on this half plane should move to the
orange half-ellipse.
We want that the
non-faulty robots
lying on this half plane should move to the
orange half-ellipse.
Similarly, the
non-faulty robots
lying on this half plane should move to the
blue half-ellipse.
How to Determine the Half Ellipse?
We need two things.
- ① The central robots on the innermost layer to determine the major axis.
- ② Another robot to determine the minor axis and hence the ellipse.
How to Determine the Half Ellipse?
In this process, we first determine a
Marker robot and give it a designated color.
A robot that can see the entire
linear innermost layer.
Marker robots help determine the
central robots
on the innermost layer in
query-feedback fashion.
Concluding Remarks
“
This paper presents $O(N)$ Fault-tolerant Mutual Visibility using $O(1)$ colors in the most general model (Asynchrony and Disorientation).
”
Time Lower Bound
We believe that it is somewhere very close to linear in N.
Future Work
The whole spectrum of fault-tolerant pattern formation is open.