In this video, I’ll describe a decentralized shape formation algorithm for kilobots.

Before getting into the algorithm, let’s first look at two basic features of a kilobot: motion and communication.

For motion, each kilobot uses three legs—one at the front and two at the back. When a kilobot is instructed to move left, it rotates counterclockwise around its rear left leg. To move right, it rotates clockwise around its rear right leg.

For communication, kilobots exchange messages wirelessly. The strength of the received signal is also used to estimate the distance between two kilobots.

To make this clearer, let’s discuss a simple star–planet algorithm for Kilobots. In this setup, the center kilobot plays the role of a star and constantly broadcasts a dummy message. Another kilobot plays the role of a planet. This kilobot moves around the star in a circular orbit of unit radius, in a clockwise direction.

Here’s how star-planet system works: at each step, the planet receives the star’s message and estimates its distance based on signal's strength. If the distance is greater than one, the planet moves right to decrease its distance from the star; otherwise, it moves left to increase its distance. Repeating this process makes the planet orbit around the star in a circle of unit radius.

This orbiting is the foundation of the shape formation algorithm. Orbiting is used by a Kilobot to reach a desired location using the help of other Kilobots. The only difference is that instead of orbiting a single star, a kilobot must maintain at least one unit of distance from multiple stars at the same time.

Now, let’s discuss the shape formation algorithm itself. To understand this algorithm, let's define two separate roles for a kilobot. One role is to act as a guide and the other is to act as a builder.

Guides are stationary robots that have already occupied a position; they constantly broadcast their position. This broadcasted message allows builder robots to orbit and identify which positions are already taken. Once a builder finds a suitable vacant position and settles down, it turns into a guide, helping the next set of kilobots to navigate.

At the beginning, three guide kilobots are placed in an L-shaped arrangement. They are labeled as 1, 2, and 3. Kilobot 1 is exactly one unit away from both 2 and 3, while the distance between kilobots 2 and 3 is root 2, or about 1.41 units.

To specify the desired shape, each kilobot stores a two-dimensional shape matrix. This matrix lists the kilobot number, its two desired neighbors, and the distance it must maintain from them.

For example, let’s build a rectangle with a width of 2 units and a height of 1 unit. The shape matrix defines the positions of the 4th, 5th, and 6th kilobots. According to it, kilobot 4 must be one unit from both kilobots 2 and 3. Kilobot 5 must be one unit from kilobot 2 and about 1.41 units from kilobot 4. Finally, kilobot 6 must be one unit away from both kilobots 4 and 5.

Here’s how the process unfolds:

When the first builder arrives near the three guides, it doesn’t know which position—4, 5, or 6—is vacant. It assumes position 4 is vacant and begins orbiting clockwise. Once it reaches that location, it settles and becomes a guide.

The second builder also assumes position 4 is vacant and starts orbiting. But as soon as it comes within the communication range of  guide kilobot 4, it realizes that the spot is occupied. So, it assumes that the next position 5 is vacant. When it orbits to position 5 and finds it vacant, it settles there as a guide.

The third builder repeats the process, initially assuming position 4 is vacant. After detecting that 4 is occupied, it starts moving to position 5. But before reaching it, it learns that position 5 is also taken. So, it moves towards next position, i.e., 6. When it reaches the final vacant spot, it becomes a guide. This completes the decentralized rectangle formation.

Now, let’s look at a demo on real kilobots. Note that in practice, instead of requiring perfect accuracy in meeting distance constraints, we allow a small tolerance, called an epsilon margin. A builder is considered to have reached a position once it comes within epsilon margin of the exact location. This localization method is simple, but it has a drawback: the error in position from one builder carries over to the next, causing the error to accumulate as the shape grows. For small structures, this naive localization approachh isn’t a problem. But for larger shapes, we require a more precise approach.

That’s where optimization-based localization comes in. In this method, at each step, a builder estimates its absolute position in the x–y coordinate system, using the known positions of other guides. By working with global positions instead of only relative distances, the algorithm greatly reduces the error that would otherwise propagate during the shape formation process.

-------------------------------------------------------

In this video, I’ll explain a distributed shape formation algorithm for kilobots. This algorithm is easy to understand, and the key point is that it works without needing any optimization in localization.

Before we dive into the shape formation algorithm, let’s first look at two key features of a kilobot: motion and communication.

For motion, each kilobot moves using three legs—one in the front and two at the back. When it’s instructed to move left, it rotates counterclockwise around its rear left leg. And when it’s asked to move right, it rotates clockwise around its rear right leg.

Now, for communication, kilobots exchange information wirelessly. They can also estimate how far another robot is by measuring the strength of the signal they receive.

To make things clearer, let’s look at the star–planet system algorithm. In this setup, the center kilobot acts as the star, continuously broadcasting a dummy message. Another kilobot plays the role of a planet, moving around the star in a circular orbit of unit radius, in a clockwise direction.

Here’s how it works: at each step, the planet receives the star’s message and estimates its distance from it. If the distance is greater than one, the planet moves right; otherwise, it moves left. By repeating this process, the planet gradually orbits around the star.

This orbiting algorithm forms the backbone of the shape formation process. The only change is that instead of a single star, there are multiple stars. In this case, the planet adjusts its movement while making sure it always maintains at least one unit of distance from every star.

Now we’re ready to discuss the shape formation algorithm. In this algorithm, kilobots are classified into two types: guides and builders.

Guides are stationary kilobots that broadcast messages containing the positions they occupy. This information helps builder robots both in orbiting and in identifying which spots are already taken. Once a builder finds a suitable vacant position and settles down, it transforms into a guide and begins assisting other kilobots with navigation.

At the start, three guide kilobots are placed in an L-shaped arrangement. They are labeled as 1, 2, and 3. Kilobot 1 is positioned exactly one unit away from both 2 and 3, while the distance between kilobot 2 and 3 is root 2, which is approximately 1.41 units.

To define the shape we want to form, every kilobot stores a two-dimensional shape matrix. This matrix describes the desired structure. Each row specifies a kilobot number, its two neighbors, and the distance it should maintain from them.

Let’s demonstrate by building a rectangle with a width of 2 units and a height of 1 unit. The matrix here defines the positions of the 4th, 5th, and 6th kilobots. According to it, kilobot 4 should be one unit away from kilobot 2 and kilobot 3. For kilobot 5, the required distances are one unit from kilobot 2 and about 1.41 units from kilobot 4. Finally, kilobot 6 must stay one unit away from both kilobot 4 and kilobot 5.

When the first builder kilobot enters the area near the three guide kilobots, it doesn’t know which of the remaining positions—4, 5, or 6—is vacant. So, it assumes position 4 and begins orbiting clockwise. Once it reaches the location for position 4, it stops orbiting and transforms into a guide kilobot.

Next, when another builder arrives, it also assumes position 4 and starts orbiting. But as soon as it comes within the communication range of kilobot 4, it realizes that spot is already taken. It then shifts its assumption to position 5 and continues orbiting until it reaches that location. Once there, it stops and becomes a guide kilobot as well.

Finally, when the last builder kilobot comes in, it too starts by assuming position 4. After entering the communication range of kilobot 4, it updates to position 5. However, before reaching there, it is informed that position 5 is already occupied. So, it redirects towards position 6, the remaining vacant spot. On reaching it, the kilobot stops orbiting, becomes a guide, and completes the shape formation process.

Here’s a demo of the algorithm implemented on real kilobots. It’s important to note that instead of requiring a builder to occupy the exact position that satisfies the distance constraints from its two neighbors, we allow a small tolerance, called an epsilon margin. Once the builder comes within this margin, it settles down.

While this method is easy to implement, it has a drawback. The position error of one builder gets carried forward to the next, and the error keeps increasing as more kilobots join. For small shapes this is manageable, but for larger formations, a more robust method is recommended.

That is where optimization based localization comes handy. In this approach, at each step, a builder estimates its absolute position in the x–y coordinate system using the known positions of existing guides. This way, the builders rely on global positions rather than relative ones, which significantly reduces error propagated at successive positions.