We developed a novel decentralized algorithm for a large number of
robots to form various repeated lattice patterns, including
squares, hexagons, octagon-squares, etc. Our
algorithm takes a desired lattice pattern as input,
which is represented as a
lattice graph. Robots can autonomously organize
themselves into a family of rooted trees, and use
these trees to perform task assignments locally
The input to our algorithm is a graph representation of the desired pattern:
a directed graph in which each vertex denotes a "role" for a
robot to play, and each outgoing edge is labeled with rigid
transformation indicating the desired location of one of that robot's
neighbors. (Right: lattice graph represents a repeated hexagon lattice pattern)
Each robot continually broadcasts
messages to the nearby robots. Based on these messages, robots
organize themselves into a rooted tree structure, then move towards the
destinations assigned to them by their parents in this tree.
Two critical limitations:
There is no guarantee that the robots will eventually form the desired
formation and terminate the algorithm.
The motion strategy may cause the communication network disconnected,
hence affects the overall solution quality.
By defining a new procedure to construct the tree structure and modifying the motion strategy,
we proved that robots executing this new algorithm will form the desired
lattice with bounded execution time while maintaining the communication graph connected.
Simulated software was implemented
with ROS. The
simulation of the
"repeating-square lattice pattern" formation is
Formation Demo with 10 Robots
The objective of our work is to form a plan for the
robot to execute using the information available in the
information space. Using a geometric approximation method
to represent the robot's states and uncertainty, we
constrained the true information state
(I-state) to remain in a structured subset
of the information space.
In the simulation of a navigation task, a mobile
robot followed predefined waypoints in environment by observing
the presence but not the distance to the randomly
generated landmarks. Robot was
guided by the centroid point of the approximated I-state.
The experimental results for a sensor-based navigation
task demonstrated that using our method, compared to a
high-fidelity representation of the un-approximated
I-state, could achieve a similar success rate at a small
fraction of the computational cost.
Figure shows a snapshot of
using double-rectangle to
approximate the I-state in a navigation task.
The blue region denotes
the range of where the robot could get observations from
The true I-state is shown as
a green region.
Two simulation videos are provided showing a robot could
complete the task using different approximations of I-state.
Navigation Task using Rectangle Range Space
Navigation Task using Double-Rectangle Range Space