Relative localization of swarm robotics based on the polar method

Abstract

This article proposed a simple and efficient method for relative localization of swarm robotics. Firstly, the relative localization module of the micro-robot is designed to be composed of a compass and several pairs of infrared transceiver sensors evenly arranged on the edge of the robot. Based on the existing relative localization method and combined with the relative localization module, an improved relative localization method for swarm robots named as polar method is proposed, which includes distance calculation, relative direction calculation, and coordinates conversion. After that, a set of localization rules is designed to apply this method to the swarm system, which mainly include establishment of reference coordinate system, localization of the adjacent layer of the seed robot, and localization between layers, so that the initial coordinates of all robots can be obtained directly with only one seed robot. Then we described the implementation process of dynamic localization of swarm robots based on the initial static localization in the edge detour motion mode. Finally, the feasibility and flexibility of this localization method are verified by experiments on the swarm robotic platform, and the localization method is applied to realize the shape formation of swarm robots.

Introduction

With the continuous expansion of application scenarios and task requirements, robot has become an irreplaceable tool for humans. However, in some diversified and large-scale task environments, when dealing with some complex, uncertain, and large-scale problems, traditional single-robot and multi-robot systems face challenges. Therefore, swarm robots with flexibility, scalability, and robustness ^1,2 came into being. Because of its distributed characteristics and various advantages, swarm robots are widely used in scenarios such as aggregation, ³ decentralization, ⁴ pattern formation, ⁵ target search, ⁶ and joint transportation. ⁷ In various application scenarios of swarm robots, the position of the robot itself or the position information of neighboring robots is necessary.

Due to the distributed characteristics of swarm robots and limitations of the absolute localization method, many research teams choose relative localization method in the localization of swarm robots. The methods used to solve the relative localization problem can be divided into two categories: ranging-based method ^{8 –10} and nonranging method. ^{11 –13} Ranging-based method relies on the robot’s ability to measure its distance to reference nodes or nearby nodes, where the positions of the reference nodes are known. On the other hand, the nonranging method does not require distance information to estimate the position of the unknown node. The results of relative localization using nonranging method are not as accurate as those obtained based on ranging method.

In the research on the relative localization technology of swarm robots, the relative localization method is closely related to the hardware functions of individual robots. Due to the limitation of the swarm robot’s individual functional structure and perception ability, it is difficult to realize the relative localization of swarm robots. According to the distribution of sensors, swarm robots can be divided into two main categories, one is the robot with sensors at the center, and the other is the robot with sensors distributed on the edge. The robots with sensors at the center mostly use the trilateration method for relative localization, ^14,15 and the robots with sensors on the edge mostly use relative localization methods similar to the polar method proposed in this article. ^16,17

A typical representative of the robots with sensors at the center is Kilobot robot designed by Professor Rubenstein of Harvard University. Kilobot robot uses a pair of infrared transceivers at the bottom center to perform distance measurement and communication between individual robots, ¹⁴ and select three seed robots to establish a global coordinate system of swarm system. Kilobot robots use the improved trilateration method ¹⁵ to calculate the specific coordinates of the robot in the coordinate system.

A typical representative of the robots with sensors on the edge is Khepera robot developed by Jim Pugh at the Lausanne Institute of Technology in Switzerland. ¹⁶ Sixteen infrared transmitter and eight infrared receivers are evenly distributed on the edge of the Khepera robot for information interaction and distance measurement between robots. Khepera robot selects the three maximum signal intensity values detected by the eight infrared receivers and calculates the distance and relative direction between individual robots through the empirical function between the distance and the signal intensity. This method is similar to the polar method but does not establish a polar coordinate system. The specific coordinates of the unknown robot cannot be obtained, and only the position of the unknown robot relative to the known robot can be calculated. Another typical representative of the robots with sensors on the edge is an independent swarm system with fast onboard relative localization modules designed by the Polytechnic University of Madrid. ¹⁷ Twelve pairs of infrared transceivers are evenly distributed on the edge of the module for information interaction and distance measurement between robots. The relative localization module selects two maximum signal intensity values detected by the 12 infrared receivers and calculates the distance and deflection angle between the signal transmitter and the relative localization module according to the empirical function relationship between the signal intensity value, distance, and deflection angle. This localization method is also similar to the polar method, but the polar coordinate system with the seed robot as the pole is not established. Therefore, the specific coordinates of the robot cannot be calculated.

Both of these two types of relative localization methods used for swarm robots have certain shortcomings. The trilateration method requires at least three noncollinear seed robots whose coordinates are known, which leads to the poor robustness of the swarm system. And the unknown robot needs to measure the distance between the three seed robots in sequence, so the large information throughput leads to low localization efficiency. The existing localization methods similar to the polar method don’t establish a reference coordinate system of the whole swarm system. To be specific, the robot receiving signals can only calculate the direction of the robot transmitting signals relative to itself and the distance between them, so that the specific coordinates of the unknown robot can’t be directly calculated by itself.

Based on the designed relative localization module and taking into account the existing relative localization methods, this article proposed an improved relative localization method for swarm robotics named as polar method, which includes distance calculation, relative direction calculation, and coordinates conversion. After that, a set of localization rules was designed to realize the layer-by-layer localization of all robots in the entire swarm system. And we also took the edge detour motion mode as an example to describe the implementation process of dynamic localization of swarm robots. Finally, some experiments on the swarm robot platform were carried out to verify the feasibility and flexibility of the localization method and realize the shape formation of the swarm system.

Compared with existing relative localization methods, this method has several important properties. First, after adding the self-direction determination unit to the micro-robot, this relative localization method can select one seed robot to establish a reference coordinate system of the entire swarm system and calculate the positions of unknown robots in the coordinate system directly, which solves some problems of the existing relative localization methods, such as multiple seed robots, a large amount of communication, and difficulty in getting the coordinates directly. Second, the localization is carried out layer by layer from the center to the outside, which improves the localization efficiency and the stability of the swarm system to a certain extent.

The rest of this article is organized as follows. The second section of this article describes the carrier robot used to implement the localization method, the third section describes the implementation process of the relative localization of the swarm robots based on the polar method, and the fourth section describes the application of this localization method to achieve the localization of the entire swarm system. The fifth section verifies the feasibility and flexibility of the relative localization method proposed in this article through physical experiments of swarm robots.

The robot and localization module

Micro-robot

The micro-robot adopts a layered structure, which is mainly composed of a perception layer, a decision-making layer, and an execution layer. The micro-robot is named as Cilibot and the size of the robot is 45 mm in diameter and 48 mm in height, as shown in Figure 1. The decision-making layer includes a microcontroller based on STM32, a power management unit, and various functional expansion interfaces. The perception layer is composed of infrared transceiver sensors and a compass interface. The executive layer is designed as a two-wheel differential drive form, with two drive rear wheels of the same specification and a universal support front wheel. Each drive wheel is directly driven by a 12 mm diameter DC geared motor.

Figure 1.

Micro-robot. (a) Robot model and (b) robot physical picture.

Relative localization module

The relative localization module of the robot is the perception layer of the robot, which chooses to use infrared sensors and compass to realize the relative localization between the swarm robots. The relative localization module is composed of infrared emitting diode, infrared receiving diode, integrated infrared receiving diode, and compass. Among them, infrared emitting diode TSKS5400-FSZ has a half angle of 30°, a radiation intensity of 7 mW/sr, and a wavelength of 950 nm. Infrared receiving diode TEFT4300 has a half angle of 30° and a receiving wavelength of 875–1000 nm. It can detect infrared signal intensity for calculation of relative distance and direction. And integrated infrared receiver HS0038 is an integrated receiver that integrates a series of circuits such as monitoring, amplification, filtering, demodulation, and so on. It can detect the signal modulated by the 38 kHz carrier, and demodulate the detected signal to directly output the original signal, which is used for communication. The electronic compass adopts HMC5883.

As shown in Figure 2, six infrared receiving diodes and six infrared emitting diodes are evenly distributed on the edge of the top and bottom of the robot’s perception layer. With these infrared receiving diodes and infrared emitting diodes, the distance between robots can be measured using the received signal strength indication (RSSI) principle of infrared signals. In addition, six infrared integrated receiving diodes are also evenly distributed on the edge of the top of the robot’s perception layer. Coupled with infrared emitting diodes, the robot can communicate with individuals in the neighborhood. And the robot uses an electronic compass to determine the deflection angle of its orientation relative to the earth’s magnetic field.

Figure 2.

Relative localization module.

The six infrared emitting diodes evenly distributed on the edge of the robot enable the robot to carry out 360° communication in all directions. The infrared signal radiation range of the robot is shown in Figure 3. It can be seen that there is a certain signal radiation blind zone between two infrared emitting diodes. Aiming at the radiation blind area problem, the effective radiation range of the robot’s infrared signal is determined to be 15 cm through experimental measurement. Because when the robot’s six infrared emitting diodes send infrared signals, the infrared signal intensity values at the same distance from the center of the robot within a circle of 15 cm from the center of the robot in the plane of the robot’s perception layer are approximately equal. And beyond 15 cm, there is a big difference between the signal intensity values in the radiation blind zone and the radiation range. If the signal intensity is not uniform, it will cause a large error in the distance measurement between individual robots. Therefore, the signal intensity value r_e at 15 cm of the robot’s signal radiation range is recorded as the minimum threshold for the robot’s distance measurement and communication.

Figure 3.

Schematic diagram of robot infrared signal radiation.

Relative localization based on the polar method

Based on the research results of Pugh Jim, ¹⁶ we improved the individual functions of swarm robots and proposed an improved relative localization method, which is suitable for swarm robots with sensors on the edge.

Localization information collection

Before calculating the relative position between robot individuals, the robot first needs to collect the information required for localization, which mainly includes distance measurement between robots, position information interaction, and orientation determination. And then the robot uses this information and combines the polar method to calculate the relative position between the robots.

Distance measurement based on RSSI

First, we measured the signal intensity values detected by the unknown robot in the range of 0–15 cm when the infrared receiver of the unknown robot faces the seed robot, as shown in Figure 4. And then fit an empirical function between signal intensity and distance.

Figure 4.

Received signal intensity measurement.

A large amount of experimental data is used to fit the curve shown in Figure 5, and the signal intensity–distance empirical function corresponding to the fitted curve is

Figure 5.

Signal intensity–distance fitted curve.

$f\left(x\right)=a\cdot x^b+c$

1

where $f\left(x\right)$ is the distance between individual robots, x is the intensity value of the infrared signal collected by the signal receiving robot, the parameters a = 149.3, b = −0.7832, and c = 0.1038.

During the actual localization of the robot, the infrared receivers of the unknown robot O₁ rarely face the seed robot O. In Figure 6, the position of the sensor S_i (i = 1, 2, 3, 4, 5, 6) corresponds to the position of the six pairs of infrared transceivers, respectively. When the infrared receiver S ₄ of the unknown robot O₁ faces the seed robot O, let the signal intensity value detected by the infrared receiver S ₄ of the robot O₁ be r. When the robot O is at the deflection angle θ of the infrared receiver S ₄ of the unknown robot O₁, as shown in Figure 6, let the signal intensity value detected by the infrared receiver S ₄ be r′. Through a large amount of experimental data, it was found that the relationship between the signal intensity value r and r′ can be approximately expressed as

Figure 6.

Signal intensity measurement under any circumstances.

$r^{\prime }=r\text{cos}(\theta )$

2

Select n sensors that measure the highest signal intensity as a sector, where n is no more than half of the total number of sensors. Define m = [n/2] and specify that the counterclockwise direction is the positive direction. $r_{-1}^{\text{"}}\dots r_{-m}^{\text{"}}$ is the signal intensity value measured by the sensor whose angle is larger than the center of the receiving sector, and $r_1^{\text{"}}\dots r_m^{\text{"}}$ is the signal intensity value measured by the sensor whose angle is smaller than the center of the receiving sector. (When n is an odd number, the value of the sensor on the axis of the sector is $r_0^{\text{"}}$ .) ${\beta }_i$ is the deflection angle of sensor i relative to the sector axis (an example of n = 3, m = 1 is shown in Figure 6). Then the value $r_i^{\text{"}}$ is obtained from equation (2)

$r_i^{\text{"}}=r\text{cos}(\theta -{\beta }_i)\text{\hspace{0.17em} with \hspace{0.17em}}{\beta }_i=-{\beta }_{-i}$

3

Position information interaction

The infrared communication protocol between individual robots is changed on the basis of Nippon electronic company (NEC) protocol. A complete signal is composed of boot code, check code, flag, coordinate x, coordinate y, check inverse code, and end code from low to high, with a total of 32 bits of valid data, as shown in Figure 7. The robot sending signal modulates a complete signal with a 38 kHz carrier wave and sends it out, and the robot receiving signal demodulates the received signal to obtain the original signal by infrared integrated receiver.

Figure 7.

IR communication packet format.

The position-known robot encodes its own coordinates (x, y) and the flag into a complete signal format and sends it out. After the unknown robot receives a complete signal, it decodes the coordinates and flag of the known robot.

Robot’s orientation determination

It is stipulated that the direction from the center of the robot to the infrared transmitter S ₁ is the robot’s orientation F, and the positive direction of the magnetometer’s Y-axis is the same as the robot’s orientation. Because when the robot faces due east, the output angle of the magnetometer is 0°. When the robot rotates clockwise, the output angle of the magnetometer gradually increases from 0° to 360°. Therefore, combining the position of the seed robot and the output angle of the magnetometer, a polar coordinate system is established as shown in Figure 8. In the polar coordinate system, the position of the center of the seed robot O is the pole, the east is the positive direction of the polar axis, and the clockwise direction is the positive direction of the polar angle. The orientation angle of a robot is the angle α resulting from the clockwise rotation of the robot orientation F from the east toward current direction. And the robot uses the compass to obtain the orientation angle α.

Figure 8.

Polar coordinate system of swarm system.

Relative position calculation between robots

After collecting the information required for localization, the relative position between robot individuals can be figured out, which is divided into three steps: distance calculation between robot individuals, calculation of relative direction between robot individuals, and calculation of unknown robot coordinates.

Distance calculation

First, calculate the distance between the robots. Using the formula (3), we can get

$r_i^{\text{"}}+r_{-i}^{\text{"}}=r\text{cos}(\theta -{\beta }_i)+r\text{cos}(\theta +{\beta }_i)=2r\text{cos}(\theta )\text{cos}({\beta }_i)$

4

$r_i^{\text{"}}-r_{-i}^{\text{"}}=r\text{cos}(\theta -{\beta }_i)-r\text{cos}(\theta +{\beta }_i)=2r\text{sin}(\theta )\text{sin}({\beta }_i)$

5

Let

$a=\frac{{{\displaystyle \sum }}_{i=0/1}^m{r}_i^{\text{"}}+r_{-i}^{\text{"}}}{{{\displaystyle \sum }}_{i=1}^{m}2\text{cos}({\beta }_i)}=r\text{cos}(\theta )$

6

$b=\frac{{{\displaystyle \sum }}_{i=0/1}^m{r}_i^{\text{"}}-r_{-i}^{\text{"}}}{{{\displaystyle \sum }}_{i=1}^{m}2\text{sin}({\beta }_i)}=r\text{sin}(\theta )$

7

Using the triangle identity $A{\text{cos}}^2(x)+A{\text{sin}}^2(x)=A$ , we get the formulas

$r={(a^2+b^2)}^{\frac{1}{2}}$

8

Through some control tests respectively using two and three sensors receiving signals, it was found that using three of the six sensors can achieve the highest distance measurement accuracy. Among the signal intensities measured by all sensors, select the sensors corresponding to the three strongest signal intensity values $r_{-1}^{\text{"}}$ , $r_0^{\text{"}}$ , $r_1^{\text{"}}$ to form a sector, as shown in Figure 6, where ${\beta }_1=\pi /3$ at this time, so

$r_{-1}^{\text{"}}=r\text{cos}(\theta +\frac{\pi }{3}),r_0^{\text{"}}=r\text{cos}(\theta ),r_1^{\text{"}}=r\text{cos}(\theta -\frac{\pi }{3})$

9

Based on the above formula, the following equation is obtained

$a=\frac{r_1^{\text{"}}+r_{-1}^{\text{"}}+2r_0^{\text{"}}}{2\text{cos}(\frac{\pi }{3})+2},b=\frac{r_1^{\text{"}}-r_{-1}^{\text{"}}}{2\text{sin}(\frac{\pi }{3})}$

10

Therefore

$r={(a^2+b^2)}^{\frac{1}{2}}$

11

Finally, the value of r is inserted into x of the empirical function $f\left(x\right)=a\cdot x^b+c$ in formula (1), and the value of $f\left(x\right)$ is calculated as the distance L between the unknown robot O₁ and the seed robot O.

Relative direction calculation

In the polar coordinate system shown in Figure 9, the angle θ, the angle α, and the angle γ are calculated separately, and finally the angle ω of the unknown robot relative to the seed robot in the polar coordinate system is calculated by combining these three angles.

Figure 9.

Relative direction calculation between robots.

1. Angle θ calculation

First, calculate the deflection angle θ of the seed robot O relative to the selected sector axis of the unknown robot O₁. Based on equation (6) and equation (7), we get the formulas

$\theta =\text{arctan}(\frac{b}{a})$

12

When selecting the three strongest signal intensity values $r_{-1}^{\text{"}}$ , $r_0^{\text{"}}$ , $r_1^{\text{"}}$ corresponding to the sector composed of sensors, we can get

$a=\frac{r_1^{\text{"}}+r_{-1}^{\text{"}}+2r_0^{\text{"}}}{2\text{cos}(\frac{\pi }{3})+2},b=\frac{r_1^{\text{"}}-r_{-1}^{\text{"}}}{2\text{sin}(\frac{\pi }{3})}$

13

Then, substitute a and b into the formula (12), and the deflection angle of the seed robot O relative to the sector axis of the unknown robot O₁ is figured out.

• 2. Angle α calculation

The angle α is the orientation angle of the robot, which is got by the compass.

• 3. Angle γ calculation

In Figure 9, the angle γ is the angle between the sector axis and the robot orientation F, and stipulate counterclockwise as the positive direction of the angle γ. Therefore, the angle between the sensor S_i (i = 1, 2, 3, 4, 5, 6) and the robot orientation F is $\gamma =60\left(i-1\right)$ , that is the angle between the sensor S_i and the sensor S ₁.

• 4. Angle ω calculation

The angle ω is the polar angle of the unknown robot O₁ in the polar coordinate system with the seed robot O as the origin. Using the angle θ, the angle α, and the angle γ together with the geometric relationship, we can get

$\omega =180-\left(\gamma -\alpha +\theta \right)$

14

Finally, the relative direction of the unknown robot O₁ relative to the seed robot O in the polar coordinate system is figured out, and the determination of the relative direction between the robots in the polar coordinate system is completed.

Coordinate conversion

Through the previous calculations, we have obtained the coordinates of the unknown robot in the polar coordinate system with the known robot as the pole, that is (L, ω). As shown in Figure 10, using the distance L and the angle ω obtained above, combined with the conversion of polar coordinates and rectangular coordinates, the coordinates of the unknown robot O₁ in rectangular coordinate system are calculated.

Figure 10.

Relative position calculation between robots.

Point O can be any robot with known coordinates. Assuming that the coordinates of robot O are (x ₀, y ₀), use this method to calculate the coordinates (x, y) of the unknown robot O₁:

$\{\begin{array}{c}x=x_0+L\text{cos }\omega \\ y=y_0+L\text{sin }\omega \end{array}$

15

In this article, the relative localization method is named as polar method, which can use one robot with known coordinates to calculate the position of the robot whose coordinates are unknown within the communication range. Then, using this method combined with the localization rules of the swarm robots, the overall localization of the swarm system is realized.

Relative localization of the swarm system

Assuming that the swarm robots are initially arranged into aggregates of arbitrary shape, and the initial orientation of each robot is random. In order to realize the localization of all swarm robots, we set a series of localization rules. Using the relative localization method proposed in the third section and combined with the relevant localization rules, the swarm system is initialized and statically localized layer by layer first, and then dynamically localized based on the static localization.

Static localization of swarm robots

Establishment of reference coordinate system

To establish a relative coordinate system of swarm system, the origin must first be established. In order to make the localization of swarm robots more efficient, make the moving distance of each robot during the movement relatively even, and improve the stability of the swarm system, we select the individual at the approximate center of the swarm as the origin of the coordinate system. To this end, we adopted a layer-by-layer stripping method.

Firstly, determine whether the robot is surrounded or not by infrared receiving diodes, which provides a basis for the selection of the seed robot, as shown in Figure 11.

Figure 11.

Enclosure or nonenclosure state determination.

The green dotted circles in Figure 11 represent the 15 cm effective communication range of robots. The states a, b, and c are the ideal situations where the black robot in the center is surrounded by the red robots, and the red robots continue to send out signals. At this time, the signal intensity values detected by six infrared receiving diodes of the black robot are significantly higher than when there is no signal received, and the weakest signal intensity $r_{\text{min}}$ is greater than half of the strongest signal intensity $r_{\text{max}}$ , that is $r_{\text{min}}>r_{\text{max}}/2$ . When the states a, b, c change to states d, e, f, the position of the black robot is gradually approaching from the center to the edge. The infrared receiver of the black robot which is not covered by the communication range of red robots detects the weakest signal intensity $r_{\text{min}}$ . At this time, $r_{\text{min}}$ is still greater than half of the strongest signal intensity $r_{\text{max}}$ , that is $r_{\text{min}}>r_{\text{max}}/2$ . When the states change from d, e, f to g, h, i, the position of the black robot gradually approaches from the center to the edge to be collinear with the two red robots. At this time, there are at least one infrared receiver of the black robot which can hardly detect infrared signals of the red robots. Therefore, the weakest signal intensity $r_{\text{min}}$ is less than half of the strongest signal intensity $r_{\text{max}}$ , that is $r_{\text{min}}\le r_{\text{max}}/2$ .

Through the above analysis, there are usually three or more robots in the communication range of an individual robot, and we determined the basis for judging whether a robot is surrounded. When the infrared signal intensity values detected by the robot’s six infrared receivers satisfy that $r_{\text{min}}>r_{\text{max}}/2$ , the robot determines that it is surrounded. And when $r_{\text{min}}\le r_{\text{max}}/2$ , the robot determines that it is not surrounded, which means that it is an edge robot.

Combined with the judging rules for whether the robot is surrounded or not, as shown in Figure 12, the selection process of the seed robot of swarm system is mainly divided into the following steps:

Figure 12.

Seed robot selection. (a) Encirclement decision, (b) outer layer separation, and (c) seed robot determination.

1. All robots are initialized and start to continuously send out signals. At the same time, each robot detects the intensity of surrounding infrared signals with six infrared receivers to determine whether they are surrounded, as shown in Figure 12(a).

2. If a robot directly determines that it is not surrounded by robots after initialization, the robot determines that it is in the outermost layer of the swarm system, and stops infrared signal transmission and infrared signal intensity detection, as shown in Figure 12(b), which is equivalent to that the outermost robots are stripped and a new smaller swarm system is formed. If a robot directly determines that it is surrounded by robots after initialization, the robot determines that it is inside the swarm system and continues to perform signal transmission and signal intensity detection.

3. When a certain layer of robots is stripped, if the robot that was originally determined to be inside determines that it is not surrounded by robots, the robot determines that it is in the outermost layer of the new swarm system, and sends a feedback signal to let the robots in the stripped layer know that there are robots inside the stripped layer, and then is stripped to form a new swarm system.

4. When the swarm system repeatedly executes steps (2) and (3) and is stripped layer by layer until only one robot remains, the robot cannot detect the surrounding infrared signal intensity and judges itself as a seed robot, as shown in Figure 12(c); if the swarm system repeating steps (2) and (3) is stripped layer by layer until the innermost layer contains two or more robots as shown in Figure 13, then the innermost robot will not receive feedback signals from a more inner layer within the specified time, and determine that it is in the innermost layer.

5. If the swarm system directly selects the seed robot, the swarm system starts to establish a coordinate system; if the swarm system is stripped layer by layer until the innermost layer contains two or more robots, since each robot has its own number, the robot with the smallest number is selected as the seed robot through interaction among the innermost robots, and then the swarm system starts to establish a coordinate system.

Figure 13.

The innermost layer contains two or more robots.

After the above process, the seed robot of the swarm system is selected, and the reference coordinate system as shown in Figure 14 is established.

Figure 14.

Establishment of the coordinate system of the swarm system.

Localization of the adjacent layer of the seed robot

After the coordinate system is established, the localization process of the robot in the layer adjacent to the seed robot is divided into the following steps:

The seed robot sends its own information to the neighboring robots, as shown in Figure 15, where its own information includes flag 0 and coordinates (x ₀, y ₀).

Each unknown robot in the layer adjacent to the seed robot detects the three strongest signal intensity values $r_{-1}^{\text{'}}$ , $r_0^{\text{'}}$ , $r_1^{\text{'}}$ , and the corresponding sensors form a sector. At the same time, the magnetometer measures its orientation angle α. Finally, the polar method is used to calculate the distance L and the angle ω between itself and the seed robot in the polar coordinate system.

Combining the seed robot’s flag 0 and coordinates (x ₀, y ₀), the unknown robot figures out its own coordinates (x ₁, y ₁) in the rectangular coordinate system, updates its own flag to 1, and then starts to send its own flag 1 and coordinates (x ₁, y ₁) to the surroundings.

It is stipulated that the robot flags of the same layer are the same, and the robot flags of the adjacent layers are different by 1.

Figure 15.

Relative localization of adjacent layer of the seed robot.

Localization between layers

The relative localization between layers is different from the localization of the adjacent layer of the seed robot. During the localization of the adjacent layer of the seed robot, only the seed robot is sending signals, so there is no signal interference problem. The localization between layers may be affected by the signal interference problem.

In the process of layer-to-layer localization, the positions of the inner robots are known, and the inner robots send out signals containing their own information. Since the time for a robot to send a signal is only a few tens of milliseconds, in most cases the outer robot completes localization after receiving a complete signal, but the outer robot will also have the problem of mutual interference between the received signals as shown in Figure 16 due to the relative position.

Figure 16.

Signal interference problem.

In the Figure 16, robots A and B are inner robots with known positions, and robot C is the outer unknown robot. The interference problem of received signals includes two situations. One is that an infrared integrated receiver of robot C receives the signals of robot A and robot B at the same time, and there is interference between these two signals, which leads to signal errors. The second is that the two infrared integrated receivers of robot C receive the signals of robot A and robot B, respectively. In both cases, the signal intensity detected by the infrared receiver is the superimposed intensity of the two signals, which will cause the distance measurement to be inaccurate.

Aiming at the interference problem of the received signals, the processing method of interference signals shown in Figure 17 is designed:

Figure 17.

Interference signal processing method. (a) Interference signal received, (b) clockwise rotation, (c) receive feedback signal, and (d) localization completed.

1. After the outer robot C receives the mixed signal of the inner robots A and B or receives two signals at the same time, the robot C only turns on the infrared emitting diode at the position of the infrared receiving diode which detected the weakest signal intensity, and sends out the search signal continuously and rotate clockwise, as shown in Figure 17(b);

2. When the robot C rotates until the robot B receives the search signal, the robot B sends out a signal containing its own information, as shown in Figure 17(c);

3. After the robot C receives the signal from the robot B, it stops sending the search signal and calculates the distance L from the robot B and the direction angle ω relative to the robot B;

4. Robot C uses the polar method to calculate its own coordinates and update its flag.

After completing localization of an inner layer, in order to localize the outer layer, each inner robot sends out a signal containing its own information, including its own flag and coordinates, and the robot that has completed localization will not act upon receiving the localization signal. If the outer robot receives only one localization signal, it uses the polar method to calculate its own coordinates and updates its own flag; if the outer robot receives interference signals, it performs the processing method of interference signals until receives only one localization signal to calculate its own coordinates and updates its own flag.

After the localization of the outer robots is completed, if there remain robots outside this outer layer, repeat steps above until the localization of the outermost robot is completed. Since the outermost robots have determined themselves as edge robots in the seed robot selection process, they will no longer send signals containing their own position information after localization, and the localization of the entire swarm system is completed.

At this moment, each outermost robot sends a high level for 100 ms without carrier modulation. When the infrared receiving diodes of the inner robot detect an enhanced infrared signal lasting 100 ms or longer, the inner robot knows that the outermost robot has been positioned, and it also sends a high level for 100 ms to the outside. Until the seed robot detects an enhanced infrared signal lasting 100 ms or longer, it knows that the localization of the entire swarm system is completed.

The reason why the robot sends a high level for 100 ms without carrier modulation is that the infrared integrated receiver cannot demodulate the signal, so it will not cause the problem of receiving signal interference. And if the robot detects two mixed high-level signals, it will not affect the detection of enhanced infrared signal lasting 100 ms or longer, but will only make the signal intensity value larger or make lasting time longer.

The following is a brief summary of the initial static localization of the swarm system, as shown in Figure 18.

Figure 18.

Initial static localization process of swarm system. (a) Encirclement decision, (b) outer layer stripped, (c) seed robot selection, (d) establish a coordinate system, (e) localization of the layer adjacent to the seed robot, (f) localization between layers, and (g) localization completed.

Localization during the movement of the swarm system

In the initial static localization stage of the swarm system, the robots don’t need to perform complex motions, and how the swarm robots realize information interaction, motion collision avoidance, and localization during the movement is the key to the swarm system to complete various given tasks. In this section, the polar method is the localization basis during the movement process, and the localization rules during the movement process of the robot are designed.

Through the analysis of various autonomous forming methods of swarm robots, it is found that many robots adopt edge detour motion mode, so we proposed the robot edge detour motion localization rules.

The schematic diagram of the localization rules for the edge detour motion of the swarm robot are shown in Figure 19. The process is based on the completion of the initial static localization of the swarm system. The moving individual moves clockwise along the edge. During the movement, it continuously interacts with the robot with known coordinates, judges the distance between itself and the robot with known coordinates, calculates its own coordinates, and finally reaches the target position and stops. With reference to Figure 19, the localization process during edge detour is described in detail as follows:

Figure 19.

The robot’s edge detouring process.

1. The moving individual 3 is separated from the aggregate when its own gradient and the gradient of neighboring individuals meet the individual movement activation conditions, and adjusts the movement direction to move from the initial position to position ①.

2. When detouring near the position ①, the moving individual 3 continuously interacts with the detour center individual 5, calculates the current detour radius and adjusts its own movement direction to ensure that the detour radius is close to 10 cm, and calculates the current coordinates to determine whether it has reached the target location.

3. When detouring to the vicinity of position ②, individual 3 interacts with individual 5 and individual 4 at the same time, and the signal received by individual 3 is aliased. At this time, individual 3 does not calculate its coordinates and only uses the signal intensity value to maintain the detour radius.

4. When detouring to the vicinity of position ③, the moving individual 3 can only interact with the individual 4 within the communication range. It will calculate the current detour radius and adjust the movement direction to maintain the detour radius, resume the coordinate calculation and determine whether it has reached the target position.

5. When reaching the target position, if there is only one robot in the communication range, individual 3 will interact with the robot to calculate its own coordinates, and then stop at the target position; if there are multiple robots in the communication range, the moving individual 3 will perform the processing method of interference signals to calculate its own coordinates, and then stop at the target position.

The edge detour motion and localization rules are summarized in the flow chart in Figure 20.

Figure 20.

Edge detour flow chart.

Experimental verifications

In order to verify the feasibility and flexibility of the relative localization method prosed in this article, 14 robots and a host computer are used to build a swarm robot experimental platform. The static localization and dynamic localization of the swarm robots are experimentally tested separately, and the autonomous forming experiment of the swarm robot is carried out.

Static localization test of swarm robotics

First, the initial static localization experiment of 14 robots was carried out, as shown in Figure 21. Figure 21(a) to (c) shows the process of seed robot selection and coordinate system establishment through layer-by-layer stripping, and Figure 21(d) to (f) shows the localization process from the inner layer to the outer layer. The robot is sending a signal when the red indicator is on, and the robot stops sending signals when the red indicator is off.

Figure 21.

Initial static localization experiment of swarm robots.

In order to improve the test efficiency and visualization degree of swarm robot physical experiment, using LabVIEW as the development tool, our laboratory has designed a swarm robot host computer software to realize the monitoring and control functions of swarm robots. The monitoring result of initial static localization of the swarm robots is as shown in Figure 22. In order to facilitate observation, the coordinates of each robot are processed so that they are in the center of the monitoring interface. Figure 22 respectively shows the coordinate values sent by the robots received by the monitoring software and the position distribution of their coordinates. It can be seen from the monitoring results that the seed robot and its neighboring robots have a better localization effect, and the accumulation of localization errors causes the localization accuracy of the outermost robot to be lower than that of the inner robot. Through actual measurement, there is an error of 1–2 cm between the robot localization result and the actual position, which can meet the requirement of the swarm robot forming experiment.

Figure 22.

Monitoring result of static localization experiment with 14 robots. (a) and (b) Coordinates of 14 robots. (c) Graph of raw data.

Dynamic localization test of swarm system

Based on the completion of the initial static localization of the swarm system, the localization test during movement in the edge detour motion mode as shown in Figure 23 was carried out. First, use six robots to complete the initial localization, of which the No. 1 robot is the seed robot, and then the No. 2 robot is selected to make an edge detour around the swarm system.

Figure 23.

Localization test during edge detour.

The monitoring result of dynamic localization of swarm robots is as shown in Figure 24. Through actual measurement, the maximum error between the localization results at the turning point and the actual positions of the No. 2 robot does not exceed 2 cm, which can ensure that the maximum orbiting radius of the robot does not exceed 15 cm, and the minimum orbiting radius is not less than 5 cm, thereby avoiding collision with the edge robots.

Figure 24.

Monitoring result of dynamic localization experiment with six robots. (a) Coordinates of six static robots. (b) Coordinates of a moving robot at the turning points. (c) Graph of raw data.

Shape formation experiment of swarm robotics

We adopted the parallel shape formation method ¹⁸ and selected triangle as the target configuration to carry out the autonomous forming experiment of swarm robots, as shown in Figure 25.

Figure 25.

Forming experiment of triangle configuration.

First, the swarm system automatically selects the seed robot and establishes a coordinate system by layer-by-layer stripping. Then, the initial static localization of the swarm robots is completed by the relative localization method proposed in this article. After that, robots perform different subtasks according to their initial positions. Edge robots deploy to the boundary of the desired shape, and internal robots spread evenly in the boundary. During the forming process, the two subtasks are executed in parallel, and the individuals continue to update their real-time positions by dead-reckoning. Finally, the target configuration is formed, which approves that the polar method proposed in this article can be applied to realize the shape formation of swarm system.

Conclusion

The research in this article involves the relative localization technology of swarm robots in the field of swarm intelligence. Driven by the goal of relative localization between swarm robots, a hierarchical mobile robot Cilibot with complete localization functions and versatility is designed. And based on the functions of Cilibot robot, a relative localization method for swarm robots named as polar method is proposed and applied to the swarm system, and the feasibility and flexibility of this localization method is verified by physical experiments.

In the current experiment, there is indeed a certain error. On the one hand, the localization error comes from sensor errors and environmental interference. On the other hand, in the forming experiment, the shape error is also affected by forming method and movement error. In general, the error mainly comes from the error of the robot hardware, especially the quality and inconsistency of components and parts, which cannot directly deny the value of the relative localization method.

This method selects only one seed robot to establish a reference coordinate system of the entire swarm system and complete the localization of all robots in the coordinate system, which makes up for the lack of existing relative localization method such as at least three noncollinear seed robots, a large amount of communication, and difficulty in getting the coordinates directly. This localization method provides a key support technology for the swarm robot field, and could be applied to other multi-node localization fields, and has a certain versatility.

For future research, we expect to enhance the quality and consistency of hardware and analyze the regularity of error to reduce the localization error. And we expect to build up a larger scale hardware system to demonstrate the relative localization method. We will also consider forming more complex shapes with swarm robots by this relative localization method and certain shape formation method.