# UWB Base Station Cluster Localization for Unmanned Ground Vehicle Guidance

Authors: Yuzhan Wu; Susheng Ding; Yuanhao Ding; Meng Li
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In this paper, we seek to provide unmanned ground vehicles with positioning service using ultrawideband (UWB) technology, a high-accuracy positioning approach. UWB is chosen for two distinct reasons. First, it does not rely on global navigation satellite systems like GPS, making it able to be applied indoors or in an environment where GPS signal is unstable. Second, it is immune to interference from other signals and accurate enough to guide unmanned ground vehicles moving precisely in a complex environment within a narrow road. In this paper, three UWB base stations are aggregated as a group in a 2D space for localization. A large number of tests are performed with a UWB base station cluster in order to validate its positioning performance. Based on the experiment results, we further develop a dynamic particle swarm optimization-based algorithm and a genetic algorithm to deploy multiple clusters of UWB base stations to cover an area of interest. The performance of the proposed algorithms has been tested through a series of simulations. Finally, experiments using unmanned ground vehicles are carried out to validate the localization performance. The results confirm that the robots can follow complex paths accurately with the proposed UWB-based positioning system.


---

## Body

## 1. Introduction

Accurate positioning is essential for robot control while challenging to achieve, especially in an unstructured environment. Many applications, such as multirobot formation control and robot path planning, strongly rely on positioning accuracy either indoors or outdoors. Depending on the environment, positioning technologies can be roughly classified into outdoor localization, such as GPS, and indoor positionings, among which we can find Bluetooth, WiFi, Zigbee, and UWB technologies. As UWB-based localization can achieve higher accuracy positioning compared with other techniques, it is chosen in this paper to guide unmanned ground vehicles (UGVs).UWB has been a particularly attractive localization technology, especially for indoor positioning. Normally, UWB base stations, also known as beacons or anchor nodes, are scattered in the area of interest. Then, a UWB tag or agent needs to communicate with several base stations to obtain its position [1, 2]. One advantage of this scheme is an area of interest can be covered with fewer base stations, reducing the cost. Its drawback is that it is challenging to achieve time synchronization among anchor nodes. Thus, complex communication protocols need to be designed to eliminate clock offset among anchors, and multiple communication packages are required between tags and anchors for distance measurements or for localization. As a result, this strategy works well for fewer tags but is unable to provide real-time positioning for a tag swarm. Besides, it is also hard to obtain accurate positions of anchors during deployment or installation when it has a long distance between two anchors, which can introduce positioning errors for the entire system.In response to these problems, we apply UWB beacon clusters for localization. To be specific, a group of base stations can be regarded as an independent positioning device, which is able to provide highly accurate position information for tags within its coverage range. This is very useful for swarm robotic control with the leader-follower structure [3–5] because one cluster can be equipped on the leader robot, providing highly accurate positioning information for its followers. Since the beacons in one cluster are near each other, the installation accuracy can be guaranteed. Furthermore, it is feasible to share the same clock source among beacons in the same group, achieving clock synchronization. In this way, it is promising to realize accurate positioning with less communication, so that more tags can be supported simultaneously.In order to demonstrate our idea, a relatively simple situation is first considered in this paper, where three base stations are combined as a group to provide 2D petitioning for tags. Plenty of experiments are carried out to test the performance of the UWB cluster to determine the proper distances among anchor nodes. Three anchors are installed as equilateral triangles with different side lengths. In order to guarantee the system performance and improve efficiency, we develop a test platform that can adjust the side length continuously and an app used to record the positions of tags automatically. Based on the experiment results, an optimal distance between a pair of base stations and the range a beacon group can cover are obtained. Secondly, two strategies are explored to deploy UWB clusters to cover an area of interest. The main challenges for these strategies are the irregularity of UWB cluster coverage, the randomness of the shape of the area of interest, and uncertainty in the number of UWB clusters. Thus, we develop two algorithms to determine the best solution to deploy beacon clusters, namely, a dynamic particle swarm optimization- (DPSO-) based method and a genetic algorithm- (GA-) based method. Finally, the experiments of UGVs are performed based on UWB positioning to validate the performance of the localization system. The results show that UGVs can follow multiple complex paths. The maximum error is within 30 cm, and the average error is around 6.7 cm. Furthermore, one beacon group can simultaneously support multiple UGVs.The main contributions of this paper are as follows:(i)
An idea is proposed to combine several UWB base stations as one positioning cluster, which can potentially support more tags simultaneously, laying the ground for future application in swarm robotics(ii)
Experiments are carried out to test the positioning performance of a UWB group, concluding the tendency of positioning accuracy with the coverage range and the change of distances between base stations, which can be used as reference guidelines for the future application of UWB clusters(iii)
Two algorithms are proposed to deploy UWB clusters to cover an area of interest, addressing the issues of the irregularity of UWB cluster coverage, the randomness of the shape of the area of interest, and uncertainty in the number of UWB clustersThe remaining of the paper is organized as follows. In Section2, current works related to positioning for robots are presented. In Section 3, the developed test platform is introduced and the experiment results are provided. In Section 4, two proposed algorithms for deploying a set of UWB groups into a random area of interest are explained. In Section 5, we introduce the design of a UGV prototype and experiment results of UGVs following different trajectories under the positioning of a UWB cluster. Finally, in Section 6, concluding remarks are provided.


## 2. Related Work

Positioning plays an essential role in robot control. Various positioning methods have been proposed so far, with different features and suitable applications. The most widely used positioning technique for robots in an outdoor environment is GPS [6, 7]. It is low in cost and applicable to various seniors. Two main drawbacks constrain its further applications, i.e., its dependency on satellites and its low accuracy, with positioning error reaching meters. These two drawbacks encourage the study and application of other positioning techniques on robots.Positioning techniques that do not rely on satellites include inertial positioning [8–10], point cloud-based positioning [11–13], and a large family of positioning techniques generally called indoor positioning techniques [14–16].Inertial positioning has a long history, and lots of great achievements have been made so far in this field. This approach estimates positions according to acceleration and is widely used in many applications such as underwater positioning since it does not rely on any external information. However, the integral of acceleration introduces cumulative errors and finally affects the estimation accuracy. So far, various hybrid positioning methods have been proposed by combining inertial positioning with other methods, such as GPS [17, 18], acoustic ranging [19], and Doppler speedometer [20].The point cloud-based positioning includes a family of methods using kinds of sensors to detect environments around and represent sensing data as a point cloud. From the point cloud, the environment around a robot can be reconstructed. By comparing the environment with a digital map, the robot can recognize its position. Point clouds can be generated using various sensors suitable for different environments. Laser radar [11] can reach an accuracy of millimeters but is expensive. Although millimeter-wave radar costs less, it correspondingly provides few data points in space [12]. An infrared (IR) array can be equipped around a robot to provide a set of range information [21]. The provided data points are so rare that they can only be used for positioning in a structured environment. Ultrasonic sensors are used in a similar way as an IR array. Due to the low cost, they are equipped with various robots, for example, the AmigoBot [22]. From the perspective that positioning is achieved via comparing a reconstructed digital environment with a preinput map, vision-based localization can also be regarded as a special point cloud-based positioning, treating pixels as data points in the cloud. It is a rapidly developed field and various schemes have been proposed, such as positioning by recognizing landmarks [23–25] or detecting motion by comparing successive images [26]. Novel algorithms are mainly based on deep learning, enabling robots to construct a 3D map with only one camera [13]. However, vision-based positioning heavily relies on a preconstructed map, making it hard to fit for dynamic environments. Furthermore, it is prone to be deceived by similar scenes.Indoor positioning includes a family of positioning technologies suitable for GPS-denied areas, which include WiFi, Bluetooth, FRID, magnetic field, and UWB. Usually, these methods rely on beacons or base stations. For example, the WiFi-based positioning requires to predeploy a set of APs in the environment [27], and the magnetic field-based positioning method requires to preembed magnetic nails on the floor [28, 29]. At present, WiFi-based and Bluetooth-based methods mainly use the attenuation of signals to estimate distance, probably resulting in high positioning errors reaching 10 meters. The positioning accuracy may be enough for guiding customers in malls, but not enough for robot guidance. FRID-based positioning is realized by recognizing a tag when the tag is near to a reader. However, the distance between them needs to be close enough, constraining its application. Magnetic field-based positioning is precise enough to guide robots, making it suitable for automatic parking and automatic storage [30, 31]. However, the deployment of magnetic nails needs to be completed during the construction of the building. UWB-based positioning is achieved by measuring the distances between a base station and a tag using the time of flight, two-way ranging, or time of arrival, etc. The centimeter-level accuracy can be achieved by using UWB technology [32–34].In this paper, we seek for a positioning method suitable for robots moving in a complex area. This requires high positioning accuracy and working with fewer constraints. These requirements leave us limited choices. GPS, WiFi, Bluetooth, and RFID are not suitable due to large positioning errors. Furthermore, GPS is prone to fail indoors. The point cloud-based localization schemes such as IR, laser, and ultrasonic either are expensive or require pregiven maps for localization. Image-based positioning methods suffer from the same problem. As a result, UWB positioning is chosen as the solution considering the balance among performance, environment adaptation, and cost. Besides high positioning accuracy, UWB technology also has the advantages of high transmission rate, low power consumption, and strong anti-interference, making it suitable for guiding robots. In this paper, the positioning is realized based on ranging between base stations and a tag using two-way ranging. For more details about current research of UWB-based positioning, refer to [33] and other related literature studies.


## 3. Performance of UWB Station Cluster

As mentioned in Section1, three UWB base stations are combined as one group in 2D space, providing positioning information for tags within the group’s coverage region, i.e., the overlap coverage region of the three base stations. To avoid bias caused by asymmetry, three base stations are initially placed as an equilateral triangle. Besides, we try to make side lengths of a triangle small so that the UWB cluster can be made as one small device. Therefore, the effect of side lengths on the localization accuracy needs to be determined by checking the positioning accuracy of tags in different locations.


### 3.1. Test Settings

The test platform is shown in Figure1, which consists of two tracks with an angle of 60°. The sliders can move continuously along guide rails. TT DC motor is installed on each slider, which is reserved for automatic testing in the future. One UWB beacon is installed at the intersection of the extension of two rails, which is defined as the origin (0, 0) in the Cartesian coordinate system of the UWB cluster. The other two UWB beacons are mounted on top of the two sliders.Figure 1
The test platform of a UWB cluster.In order to facilitate the testing process including data recording and data analysis, a Windows app is developed as shown in Figure2. The app can record UWB tag distances and positions, show tag trajectories, and control the movement of a UGV. It can also be used to update positions of UWB base stations.Figure 2
A Windows app developed mainly to show tag traces and to control the movement of a UGV.


### 3.2. Test Results

In this part, UWB-based ranging and positioning tests are carried out to determine the proper side edges of one UWB cluster. Due to the limitations of the physical environments, the maximum distance between a UWB tag and a base station is around 8 m in a room and around 38 m in a lobby. In order to achieve the best performance, the tests are conducted under line-of-sight propagation conditions. The absolute positions of sampling points are depicted in Figures3 and 4 , respectively. For each point, more than 50 samples are collected.Figure 3
Sampling point distribution in a room with the side length of UWB stations being 50 cm and 60 cm, respectively.Figure 4
Sampling point distribution in a lobby with the side length of UWB stations being 50 cm.The mean distance errors between a UWB tag and base stations are shown in Figures5 and 6 , respectively. These experiments are carried out in a room and in a lobby in order to determine the ranging performance of UWB. In a room, the mean distance errors are less than 20 centimeters in most cases. Within 40 meters, the maximum mean distance error is less than 40 centimeters. The distance errors grow with the increase of the distance between a station and a tag, indicating by Figures 5 and 6. This implies that the positioning error will be large when a tag is far from the three base stations.Figure 5
Mean distance errors between a UWB tag and base stations in a room.Figure 6
Mean distance errors between a UWB tag and base stations within 40 meters in a lobby.Meanwhile, mean positioning errors are measured in the same environments. The corresponding results are depicted in Figures7 and 8 , respectively. At present, two side lengths, i.e., 50 cm and 60 cm, are verified. From Figure 7, it can be seen that the performance with two side lengths is similar. Then, more experiments are conducted in a lobby with long distance, whose results are shown in Figure 8. The mean position error increases approximately in proportion to the distance from the origin in a long-term perspective. The mean position errors are no more than 60 centimeters in most cases within a 10-meter distance. Therefore, 50 cm side length is chosen for a UWB cluster and a 10-meter distance is determined as the coverage radius of a UWB base station.Figure 7
Mean position errors of a UWB tag in a room with different side lengths.Figure 8
Mean position errors of a UWB tag with 50 cm side length in a lobby.


## 3.1. Test Settings

The test platform is shown in Figure1, which consists of two tracks with an angle of 60°. The sliders can move continuously along guide rails. TT DC motor is installed on each slider, which is reserved for automatic testing in the future. One UWB beacon is installed at the intersection of the extension of two rails, which is defined as the origin (0, 0) in the Cartesian coordinate system of the UWB cluster. The other two UWB beacons are mounted on top of the two sliders.Figure 1
The test platform of a UWB cluster.In order to facilitate the testing process including data recording and data analysis, a Windows app is developed as shown in Figure2. The app can record UWB tag distances and positions, show tag trajectories, and control the movement of a UGV. It can also be used to update positions of UWB base stations.Figure 2
A Windows app developed mainly to show tag traces and to control the movement of a UGV.


## 3.2. Test Results

In this part, UWB-based ranging and positioning tests are carried out to determine the proper side edges of one UWB cluster. Due to the limitations of the physical environments, the maximum distance between a UWB tag and a base station is around 8 m in a room and around 38 m in a lobby. In order to achieve the best performance, the tests are conducted under line-of-sight propagation conditions. The absolute positions of sampling points are depicted in Figures3 and 4 , respectively. For each point, more than 50 samples are collected.Figure 3
Sampling point distribution in a room with the side length of UWB stations being 50 cm and 60 cm, respectively.Figure 4
Sampling point distribution in a lobby with the side length of UWB stations being 50 cm.The mean distance errors between a UWB tag and base stations are shown in Figures5 and 6 , respectively. These experiments are carried out in a room and in a lobby in order to determine the ranging performance of UWB. In a room, the mean distance errors are less than 20 centimeters in most cases. Within 40 meters, the maximum mean distance error is less than 40 centimeters. The distance errors grow with the increase of the distance between a station and a tag, indicating by Figures 5 and 6. This implies that the positioning error will be large when a tag is far from the three base stations.Figure 5
Mean distance errors between a UWB tag and base stations in a room.Figure 6
Mean distance errors between a UWB tag and base stations within 40 meters in a lobby.Meanwhile, mean positioning errors are measured in the same environments. The corresponding results are depicted in Figures7 and 8 , respectively. At present, two side lengths, i.e., 50 cm and 60 cm, are verified. From Figure 7, it can be seen that the performance with two side lengths is similar. Then, more experiments are conducted in a lobby with long distance, whose results are shown in Figure 8. The mean position error increases approximately in proportion to the distance from the origin in a long-term perspective. The mean position errors are no more than 60 centimeters in most cases within a 10-meter distance. Therefore, 50 cm side length is chosen for a UWB cluster and a 10-meter distance is determined as the coverage radius of a UWB base station.Figure 7
Mean position errors of a UWB tag in a room with different side lengths.Figure 8
Mean position errors of a UWB tag with 50 cm side length in a lobby.


## 4. Region Coverage with Multiple UWB Clusters

Based on the experiment results in Section3, both the proper side lengths of the triangle composed of three UWB base stations and the range covered by each UWB cluster can be determined.In general, for a complex area of interest, one group of UWB base stations is unable to cover the whole area. Then, we need to find the best solutions to deploy base station groups. There are three main challenges:(1)
The region covered by all the three base stations are the overlap area of three discs, which is irregular, making it hard to determine if a subarea is covered by the group(2)
The area of interest is of random shape with inaccessible region(3)
Because of (2), the number of UWB groups necessary to cover the area of interest cannot be determined in advanceTo solve this problem, we first approximate the overlap region of the three base stations as a disc, as explained in Section4.1. Then in Sections 4.2 and 4.3, two algorithms are proposed to deploy UWB base station groups to cover a randomly generated area. Finally, in Section 4.4, the performance of the two algorithms is compared.


### 4.1. Approximate the Covered Region as a Circle

In this paper, UWB positioning is achieved through ranging between base stations and tags. In 2D space, if one robot wants to determine its position, one option is to obtain distance measurements to at least three base stations that are not in a line. In our case, three base stations are located near to each other, forming a group. To determine positions with the group, a robot needs to be within the coverage range of each of them, i.e., it should be within the overlap region of the coverage range of all the three base stations, as shown in Figure9. We call this overlap region S and obviously it is irregular. To simplify the problem, S needs to be approximated into a regular shape, and there are two choices. We can either use an inscribed triangle St or a circumcircle Sc to approximate S, and the one whose area is closest to that of S is the solution. Thus, it is required to calculate the area of S, St, and Sc. To simplify the expression, in the following, S, St, and Sc are used to represent the area of the corresponding region.Figure 9
The overlap region and its approximation. Shadow in (a) indicates the overlap region of the coverage range of three UWB base stations, i.e.,S. Shadow in (b) approximates S with its inscribed triangle St, and shadow in (c) approximates S with its circumcircle Sc.
(a)(b)(c)In our case, three base stations are located atxi,yi,i=1,2,3, composing an equilateral triangle. As all the three base stations are identical in hardware configuration, the coverage range is supposed to be the same, which is a disc with a radius of R. With the information, S can be determined. The three vertices of S are also the vertices of St, which can be obtained with the following procedure.Define the vertices asxki,j, where i,j,k∈1,2,3 and i,j,k are different, representing the vertex who is a cross point of disks centered by xi,yi and xj,yj, and this cross point is within the range of the third disk centered by xk,yk. Then, we have(1)xki,j−xi2+yki,j−yi2=R2,xki,j−xj2+yki,j−yj2=R2,xki,j−xk2+yki,j−yk2<R2.With the expressions above, we can determine the three vertices. Furthermore, we can obtain any edge length ofSt by computing the distance between the corresponding two vertices. For example,(2)lt1,2=x31,2−x21,32+y31,2−y21,32.As the center of discs is placed as an equilateral triangle, thus the three vertices are equivalent, makingSt also an equivalent triangle, whose edges have(3)lt≔lt1,2=lt1,3=lt2,3.Thus,(4)St=34lt.ForSc, its center can be obtained with(5)xc,yc=x1+x2+x33,y1+y2+y33.The radius ofSc can be measured as the distance between xc,yc and a random vertex xki,j,yki,j, as(6)lc=xc−xki,j2+yc−yki,j2.So the area ofSc can be obtained as follows:(7)Sc=πlc2.The overlap regionS is a bit tricky, as shown in Figure 10. It consists of the inscribed triangle St and three arch form areas, represented as Sarchk, where k indicates the center of the circle corresponding to the arch and k=1,2,3. Then,(8)S=St+∑k=13Sarchk.Figure 10
An auxiliary figure for calculatingS.The area ofSarchk can be obtained with(9)Sarchk=Sfank−Strianglek,where Sfank is the corresponding fan centered by xk,yk and Striangle is the triangle with three vertices of xk,yk, xik,j,yik,j,andxjk,i,yjk,i, as shown in Figure 10.To calculate the area ofSfan, it requires its radius R and its span angle θ. R is obtained by experiments, and θ is lacking. To calculate θ, we first get two vectors starting from the center of the disk xk,yk and pointing at the other two points as(10)v⟶k,i=xik,j−xk,yik,j−yk,v⟶k,j=xjk,i−xk,yjk,i−yk.Since(11)v⟶k,i⋅v⟶k,j=v⟶k,iv⟶k,jcosθ,then(12)θ=acosxik,j−xkxjk,i−xk+yik,j−ykyjk,i−ykxik,j−xk2+yik,j−yk2xjk,i−xk2+yjk,i−yk2.The area of the fan can be obtained as(13)Sfank=πR2⋅θ2π=θ2R2,where Striangle is an isosceles triangle with two edges being R and the base line is the chord of the arch, whose length is(14)lchord=xik,j−xjk,i2+yik,j−yjk,i2.Then the area of the triangle can be calculated with Heron’s formula. Half of the perimeter is given by(15)lhp=122R+lchord.Then the area is(16)Strianglek=lhplhp−R2lhp−lchord.WithSfank and Strianglek,(17)Sarchk=Sfank−Strianglek.As the three arch form areas are equivalent, the area ofS then is(18)S=St+∑k=13Sarchk=St+3Sarchk,where k could be 1, 2, or 3.Compared withS, St is a bit smaller while Sc is a bit larger. Define the rate of approximate error as(19)rt=S−SapproximateS,Sapproximate∈St,Sc.The change of approximation error is shown in Figure11. If the distances among base stations are small, approximate the overlap region as a disc is a better choice. In our case, according to Section 3, three base stations are placed as an equilateral triangle, whose side length is 50 cm. The error rate is 1.9023%. This means the disk can approximate the actual overlap region with a minor error. Then methods to place multiple such disks to cover an area of a random shape can be considered in the following.Figure 11
Approximation errors ofSc and St with the increase of distances among base stations. When the distances among stations are less than 1 m, the approximation error of Sc is less than 5%, while that of St reaches 60%.


### 4.2. Deployment with Dynamic Particle Swarm Optimization

We intend to place multiple groups of UWB base stations to provide positioning services for robots. In Section4.1, it is shown that the irregular overlap region of the three base stations can be approximated as a disk reasonably. Then the problem becomes where to place these disks and how many such disks are needed. Therefore, the deployment scheme is a trade-off between coverage rate and cost.Inspired by [35], a PSO-based algorithm is proposed in this paper that can dynamically adjust the number of UWB clusters. The algorithm is called dynamic PSO, or short as DPSO.Generally, DPSO consists of two loops. The outer loop adjusts the number of station groups, while the inner loop adjusts the positions of station groups following the idea of PSO. Assume that in theiout iteration of the outer loop, Niout station groups are used. Then, for its inner loops, the particles are encoded as the following sequence:(20)P=x1,x2,…,xNiout,y1,y2,…,yNiout,where xj,yj∈S and xj,yj,j=1,2,…,Niout, indicates the position of the jth station group.The fitness function is set to maximize the coverage rate(21)argmaxfP=SPS,where SP is the valid area covered by the station groups and S is the area of the valid area in the map. “Valid” refers to only the region accessible for the robots counts. To measure SP and S in an irregular area, we mesh the map into a set of grids and estimate areas by counting the number of grids. A swarm of particles is generated randomly in the init process. Then the particles search in the solution space guided by some historical best solutions randomly, as introduced in [36]. Besides, the particle P should not move out of the valid area S, so that a filter is designed. According to the idea above, the pseudocode of DPSO is presented in Algorithm 1. Key functions of Algorithm 1 are detailed in Algorithms 2 and 3, respectively. A general flowchart of Algorithm 1 is shown in Figure 12.Algorithm 1: Dynamic PSO.
Input: valid area S, radius of approximate disk ROutput: set Sbest consists of best particles with different lengths(1)
Set parameters: swarm sizeNswarm, iteration number Nin(2)
Set parameters for PSO:ω,c1,c2(3)
Sbest←ϕ(4)
Group number range:Nmin=S/πR2, Nmax=S/2R2(5)
foriout=Nmin,Nmin+1,…,Nmaxdo(6)
P≔pk|pk←GeneratePosS,iout,k=1,…,Nswarm(7)
V≔vk|vk←GenerateVel,k=1,…,Nswarm(8)
pbestj←pj,j=1,…,Nswarm(9)
gbest←argmaxfpj,j=1,…,Nswarm(10)
foriin=1,2,…,Nindo(11)
fori=1,2,…,Nswarmdo(12)
vtemp←ωvi+c1r⋅pbest−pi+c2r⋅gbest−pi(13)
ptemp←pi+vtemp(14)
pi,vi←ConstrainS,vtemp,ptemp,vi,pi(15)
pbesti←argmaxfp,p∈pi,pbesti(16)
end for(17)
gbest←argmaxfp,p∈pbest1,…,pbestNswarm(18)
end for(19)
Sbest←Sbest∪gbest(20)
end forFigure 12
The flowchart of Algorithm1.Thus, Algorithm1 has a complexity of ONmax−Nmin×Np+Nin×Nswarm×Ng. In Algorithm 1, the inputs are the valid area S and the radius R of the approximate coverage disk. The output is a set Sbest, consisting of best particles with different numbers of base station clusters. The parameters for the algorithm are set in lines 1-2. In line 4, the range of numbers of clusters to be explored is calculated. The floor is the number of groups needed to stuff the area with disks, which is S/πR2, and the ceil is the number of groups needed to stuff the area with the inscribed square of the disk, which is S/2R2. The loop in lines 5–20 is the outer loop, which increases the number of groups by one each time, expending the length of the particle. In each iteration, the particle swarm P, the velocity set V, the historical best solution for each particle pbest, and the best solution for all particles gbest are reset. Then, within the inner loop in lines 10–18, the velocity and position of each particle are updated randomly, affected by gbest and pbest. Then gbest and pbest are updated.In line 6, we use functionGeneratePos to obtain a random particle, as in Algorithm 2. The challenge here is that S is of random shape, and there is a high chance that the particle obtained with a general random number generation algorithm will go out of range. To solve this problem, in GeneratePos, we first scatter S into a set of grids and then stack the grids up into a sequence. The grids in the sequence are then labeled successively. We generate iout random numbers within the range of 1,Ns, where Ns is the number of the grids. These random numbers are the indexes of grids chosen as elements in the particle. The complexity of Algorithm 2 is ONp.Algorithm 2: function GeneratePos().
Input: the area of interest S, particle length NpOutput: random particle p(1)
functionGeneratePosS,iout(2)
ScatterS into NS grids, stacking as a sequence Ssequence: Ssequence=s1,…,sNS(3)
px←,py←(4)
fori=1,2,…,Npdo(5)
Index←ceilrand×NS−1(6)
px←px,sIndexx,sIndex∈Ssequence(7)
py←py,sIndexy,sIndex∈Ssequence(8)
end for(9)
p←px,py(10)
end functionIn line 7, the function GenerateVel() initializes the velocity of a particle with a zero sequence having the same size of the particle.In line 14, we use functionConstrain to ensure particles will not move out of S, as in Algorithm 3. According to the encoding rule, the particle represents the coordinates of the station groups. If a station group moves out of S, we just ignore the update of its position and corresponding velocity this time. Meanwhile, the updates of velocities and positions for other station groups are not affected. Algorithm 3 has a complexity of ONg.Algorithm 3: Function Constrain().
Input: the area S, original particle, and velocity p,v and the raw value based on them ptemp,vtempOutput: updated particle and velocity p,v(1)
functionConstrainS,p,v,ptemp,vtemp(2)
Number of station groupsNg=lengthp/2(3)
fori=1,2,…,Ngdo(4)
pxo,pyo←pi,pi+Ng(5)
vxo,vyo←vi,vi+Ng(6)
pxr,pyr←ptempi,ptempi+Ng(7)
vxr,vyr←vtempi,vtempi+Ng(8)
ifpxr,pyr∉Sthen(9)
pi←pxo(10)
pi+Ng←pyo(11)
vi←vxo(12)
vi+Ng←vyo(13)
else(14)
pi←pxr(15)
pi+Ng←pyr(16)
vi←vxr(17)
vi+Ng←vyr(18)
end if(19)
end for(20)
end functionIn lines 9, 15, and 17, the fitness functionf⋅ needs to be calculated to choose the best particle. As S is irregular, a meshing scheme is applied to estimate the coverage rate:(22)fp=SPS=NcoveredNS,where Ncovered is the number of grids covered by at least one of the station groups and NS is the number of grids in S. For each grid, we calculate the distance from its center to all the center of station groups as dis=di|i=1,…,iout. If mindis<R, we treat the grid being covered. In this way, Ncovered can be obtained.Running this algorithm, we notice that there is a chance that the best particle with more station groups performs worse than that with fewer station groups, as shown in Figure13. This is because in line 6 of Algorithm 1, each time the number of station groups is changed, the particle swarm is regenerated randomly. The red dots in Figure 13(a) indicate that, with 48 stations, the coverage rate is higher than that of 49 and 50 station groups. Clearly, the solution in Figure 13(b) performs better, with fewer station groups. There is a chance that the init swarm is rather bad, and we do not iterate enough times in the inner loop to obtain a good solution. It is not easy to check and decide when to increase the iteration number for the program automatically. With DPSO, the tendency is that more station groups will increase coverage rate, but not stable.Figure 13
Performance of DPSO. (a) The coverage rate changes with the increase of station groups. (b–d) The corresponding solutions provided by DPSO, with 48, 49, and 50 station groups, respectively. The yellow regions are covered by UWB clusters. (a) Performance of DPSO. (b) Group number = 48. (c) Group number = 49. (d) Group number = 50.
(a)(b)(c)(d)To solve this problem without increasing the iteration number, the DPSO algorithm is improved into the Elite DPSO algorithm, which ensures that the more UWB clusters are used, the better solution can be obtained. Elite DPSO is almost the same as DPSO, but line 6 in Algorithm1 is changed as(23)P≔Prandom∪Pelite,Prandom≔pk|pk←GeneratePos,k=2,…,Nswarm,Pelite≔pelite←GenerateElitegbest.This means that each time the group number is increased,Nswarm−1 particles are randomly regenerated, as is done in DPSO. A special particle called elite particle is also generated with function GenerateElitegbest based on the best particle gbest obtained in the last iteration of the outer loop. It should perform better than gbest. Two kinds of GenerateElitegbest are explored.One way to generate elite particle is to add a cluster with a random position inS to gbest. In the worst case, the newly added cluster overlaps with another cluster in gbest, resulting in fpelite=fgbest. Otherwise, pelite covers more region, ensuring that fpelite≥fgbest. This scheme is named as Random Elite DPSO.Another way to generate elite particle is to add a cluster far from other clusters ingbest, encouraging station groups to move to a relatively empty region. Assume that the newly added cluster is located at x,y and other clusters in gbest are located at xi,yi,i=1,…,iout. Then, the optimal position can be obtained with(24)argmaxdx,y=∑i=1ioutxi−x2+yi−y2iout.Apparently,dx,y is a convex function, so its maximum value is obtained with x,y on the border of the region. All grids at the border of S are exhausted to obtain x,y. This method is named Sparse Elite DPSO because it intends to encourage the locations of station groups to be sparse.The performance of both schemes is compared, showing in Figure14. From the figures, the Sparse Elite DPSO method performs slightly better than the Random Elite DPSO method. However, considering the computation cost on average, the Random Elite DPSO is a more reasonable choice.Figure 14
Performance of the Elite DPSOs. (a) Typical performance of the Random Elite DPSO and the Sparse Elite DPSO. With the increase of station groups, the coverage rate always increases. (b) Comparison of the average coverage of the Random Elite DPSO and the Sparse Elite DPSO in terms of computation cost. Boxplots in (c) and (d) show the statics results of the two Elite DPSOs. The data are obtained by repeating experiments 10 times. (a) Typical performance. (b) Average performance. (c) Random Elite DPSO. (d) Sparse Elite DPSO.
(a)(b)(c)(d)


### 4.3. Deployment with Genetic Algorithm

The DPSO methods proposed in Section4.2 explore a set of group numbers and provide the best solutions correspondingly. However, they are unable to determine the best group number automatically. A GA-based algorithm is then developed, which can provide the best number of clusters needed to cover a region and the deployment scheme, indicating positions of clusters.We scatter the area of interest with random shape intoNS grids and use the center of the grids to represent them. Thus, these grids are labeled as g1,g2,…,gNS. Then in GA, the chromosome is encoded as an element vector with the length of NS. Each element is either 0 or 1. If the ith element is 1, then a cluster is deployed at the center of grid gi. Otherwise, a cluster will not be deployed. This implies that(i)
A cluster can only be located at the center of a grid, unable to move continuously(ii)
A chromosome always represents a feasible solution because the grid sequence only contains accessible areasThe fitness function is given by(25)fg=Sg1S=Ncovered1NS,where Sg1 indicates the sum of the area only covered by one cluster, Ncovered1 is the number of grids whose center is covered only by one cluster, and NS stands for the total number of grids. The ratio of Ncovered1 and NS is used to estimate the fitness function value. Defining the fitness function in this way encourages clusters to cover more grids, which satisfies the target that the whole area of interest to be covered. Meanwhile, this definition can prevent the algorithm from adding too many clusters to achieve a high coverage rate because the increase of overlap rate results in a decrease of fitness value. In this way, the algorithm can adjust the number of clusters automatically.Then a swarm of chromosomes is generated. The fitness function is used to evaluate and choose the chromosomes. A cross operator is used to create a new chromosome, and a mutation operator is applied to add randomness to the chromosomes, as the idea introduced in [37]. The algorithm is shown in Algorithm 4. Details of functions in Algorithm 4 are further introduced in Algorithms 5–9 . A general flowchart of Algorithm 4 is shown in Figure 15.Algorithm 4: Generate deployment scheme with GA.
Input: valid area S, radius of approximate disk ROutput: positions for station groups: P=xi,yi:i=1,…,Nbest(1)
Set parameters: swarm sizeNswarm, iteration number Niter(2)
Set parameter: mutation rateμ(3)
Set parameter: swarm creation parameterpinit(4)
ScatterS into grids, labeled as S=g1,g2,…,gNS(5)
Create swarm:C≔ck|ck←GENERATECHROMOSOMENS,pinit,k=1,…,Nswarm(6)
Initialize the best chromosome:cbest←argmaxfc,c∈C(7)
fori=1,…,Niterdo(8)
Calculate fitness value:F←fci:ci∈C(9)
Selection operation:Cnew←SELECTIONC,F(10)
Cross operation:Cnew←CROSSC,Cnew(11)
Mutation operation:Cnew←MUTATIONCnew,μ(12)
Update the swarm:C←Cnew(13)
Update the best chromosome:cbest←argmaxfc,c∈cbest∪C(14)
end for(15)
Decode:P=DECODES,cbestAlgorithm 5: Function GenerateChromosome().
Input:NS,pinitOutput: random chromosome c(1)
functionGenerateChromosomeNS,pinit(2)
GenerateNS random numbers obey normal distribution: c=c1,…,cNS(3)
fori=1,2,…,NSdo(4)
ifci>pinitthen(5)
ci←1(6)
else(7)
ci←0(8)
end if(9)
end for(10)
end functionAlgorithm 6: Function Selection().
Input:C,FOutput: new swarm Cnew(1)
functionSelectionC,F(2)
fori=1,…,Nswarmdo(3)
ri←fi/∑Nswarmj=1fj,fi,fj∈F(4)
end for(5)
Rfloor=0,Rceil=r1(6)
fori=1,…,Nswarm−1do(7)
Rfloor←Rfloor,∑ij=1rj(8)
Rceil←Rceil,∑i+1j=1rj(9)
end for(10)
Cnew←ϕ(11)
fori=1,…,Nselectiondo(12)
Cnew←Cnew∪ck, where ck∈CWithrkfloor<rand<rkceilWhererkfloor∈Rfloor,rkceil∈Rceil(13)
C←C∖ck(14)
end for(15)
end functionAlgorithm 7: Function Cross().
Input:C,CnewOutput: new swarm Cnew(1)
functionCrossC,Cnew(2)
fori=1,…,C−Cnewdo(3)
p1←RandC(4)
C←C∖p1(5)
p2←RandC(6)
Exchange elements inp1,p2 after random point, obtain s1,s2(7)
s←Rands1,s2(8)
Cnew←Cnew∪s(9)
end for(10)
end functionAlgorithm 8: Function Mutation().
Input:Cnew,μOutput: new swarm Cnew(1)
functionMutationCnew,μ(2)
forc∈Cnewdo(3)
fori=1,2,…,NSdo(4)
ifrand<μthen(5)
ci←/ci,ci∈c(6)
end if(7)
end for(8)
end for(9)
end functionAlgorithm 9: Function Decode().
Input:S,cbestOutput: positions for station groups P(1)
functionDecodeS,cbest(2)
P=ϕ(3)
fori=1,…,NSdo(4)
ifci=1,ci∈cbestthen(5
)P←P∪xi,yiWherexi,yi is the center of gi∈S(6)
end if(7)
end for(8)
end functionFigure 15
The flowchart of Algorithm4.In Algorithm4, necessary parameters are set in lines 1–3. Then the area S is scattered into grids, helping to calculate the fitness function value and enable us to decode the best chromosome. In line 5, the swarm is generated using a function GenerateChromosome(), and the chromosome with the biggest fitness value is chosen as the current best chromosome, which is presented in detail in Algorithm 5. Then the loop enters lines 7–14. In each iteration, the fitness values of chromosomes in the swarm are first calculated. Then go through selection operation as introduced in Algorithm 6, cross operation as introduced in Algorithm 7, and mutation operation as introduced in Algorithm 8. Finally, update the best chromosome cbest by comparing if a better solution is obtained in this iteration. Function Decode() is used to decode the chromosome into cluster positions, which is presented in detail in Algorithm 9. Algorithm 4 has a complexity of ONswarm×Ns×Niter.Function GenerateChromosome() randomly generates a sequence whose length is the same as the number of grids inS, with each element corresponding to a grid. The sequence only consists of 0 and 1, with 1 indicating a cluster to be deployed at the center of a grid. To generate such a sequence, i.e., a chromosome for the GA, we first generate Ns random values obeying normal distribution, as line 2 in Algorithm 5. If the value is larger than parameter pinit, it is set as 1, and 0 otherwise, as lines 4–8. Algorithm 5 has a complexity of ONs.It is obvious that the choice ofpinit affects the number of clusters deployed initially and affects the optimization process indirectly. Thus, setting a proper pinit is important. Our suggestion of setting pinit is to follow(26)NSPx>pinit=SSc,where P is a probability distribution and Sc is the area covered by one cluster. In this paper, the normal distribution is chosen for P. Then,(27)Px≤pinit=1NSNS−SSc.A properpinit can be obtained by solving this equation.Function Selection() presented in Algorithm6 takes current swarm C and the fitness values of these chromosomes F as inputs. With a roulette scheme, half of the chromosomes are selected into the next generation, which means Nselection=1/2Nswarm. The roulette scheme is achieved by creating a floor sequence Rfloor and ceiling sequence Rceil based on the ratio of a chromosome’s fitness value to the sum of the fitness values, shown in lines 2–9. Rfloor and Rceil form a sequence of slots. A random number is generated and falls into a slot. The chromosome corresponding to the slot is selected, as in lines 12-13. Algorithm 6 has a complexity of ONswarm.The selection operation presented in Algorithm6 is a general operation in GA and it works well in various scenarios. However, it performs poorly in our case, as shown in Figure 16. The reason is that the fitness values of a swarm are similar, resulting in a roulette scheme unable to select proper chromosomes for the next generation effectively.Figure 16
Performance of GA with a roulette scheme and an elite scheme during iterations. (a) The change of cluster number of the best chromosome for each iteration. (b) The coverage rate of the best chromosome. (c) The fitness value, i.e., the rate of the area only covered by one cluster.
(a)(b)(c)This problem is solved by adopting an elite chromosome scheme. The idea is to choose some best chromosomes and put them directly into the next generation. Then, lines 11–14 in Algorithm6 are replaced with the following:(i)
Sort elements inC as descending order of elements in F(ii)
Cnew←c1,c2,…,cNselection∈CNselection is the number of chromosomes directly passed to the next generation. To add more randomness, we set Nselection=1/4Nswarm. From Figure 16, it can be seen that this elite chromosome scheme can ensure that the fitness value never decreases. Besides, the algorithm can automatically adjust the number of clusters. Comparing with the roulette scheme, the elite chromosome scheme can achieve a higher fitness value and a coverage rate with fewer clusters. This point is clearly shown in Figure 17, where we exhibit the deployment of clusters according to solutions obtained with GA using two different selection operators. In both cases, 35 clusters are deployed. The solution with the elite scheme resulting in clusters spreading more evenly and covering more area than that of the roulette scheme.Figure 17
Deployment of clusters according to solutions obtained with GA using a roulette selection scheme and an elite selection scheme. The area with a blue background is the area of interest, and each red circle indicates the coverage range of a cluster. (a) Roulette scheme. (b) Elite scheme.
(a)(b)Function Cross() in Algorithm7 generates the rest chromosomes. It randomly picks two chromosomes as parents, exchanges their elements after a random point, and generates two children (lines 2–6). Then, in lines 7–8, a random child is chosen and added to the swarm. Algorithm 7 has a complexity of ONswarm.Function Mutation() in Algorithm8 randomly generates NS numbers. If the number is larger than the mutation parameter μ, the corresponding element in the chromosome is inverse from 0 to 1 or from 1 to 0. Attention should be paid that μ should be set as a relatively small number, as a big μ introduces 1s rapidly during iterations as shown in Figure 18, overwhelming the algorithm’s ability to adjust cluster numbers. Algorithm 8 has a complexity of ONs×Nswarm.Figure 18
Change of the number of 1s in the best chromosome with differentμ. As the number of 1s increases dramatically with bigger μ, use log10⋅ to record the numbers.Function Decode() in Algorithm9 decodes the best chromosome into a set of coordinates for cluster deployment. Algorithm 9 has a complexity of ONs.


### 4.4. Comparison of the Two Schemes

Experiments have been carried out to test the algorithms provided in Sections4.2 and 4.3. The results in a rectangle region and a randomly generated irregular region are presented here, as shown in Figure 19. For the PSO, the swarm size is set as 20 and the iteration number is 50. The station group number increased from the number of clusters necessary to just fulfill the area ignoring the shape, which is 21. The solution of GA contains 29 clusters. To make it comparable, in DPSO, we also set the maximum number of clusters as 29. It turns out that the coverage can reach 87.98%. For the Elite GA, the swarm size is set as 50 and iteration number 200. Parameter μ is set as 0.00001 and pinit is automatically set with the method introduced in Section 4.3. The solution provided by the Elite GA contains 29 clusters, with a coverage rate reaching 89.87%, slightly better than that of the Elite DPSO. Taking the randomness of both algorithms into consideration, we cannot claim the Elite GA is better than the Elite DPSO. In fact, the algorithms have different features, and some discussion is provided in the following.Figure 19
Deployment of clusters into an irregular area of interest according to solutions obtained with (a) the elite DPSO and (b) the elite GA.
(a)(b)DPSO can provide a set of particles corresponding to a different number of groups. Thus, users can choose the best one according to the cost and the coverage rate. GA automatically decides how many clusters are needed, and users can directly use the scheme generated. However, users are unable to assign the number of clusters.In DPSO, base station groups move continually in the area of interest, while, in GA, base station groups jump among grids. This means DPSO has more flexibility than GA. If we are seeking for a more precise solution with GA, the area of interest has to be meshed into more grids, increasing the length of the chromosome and resulting in more computation. For example, if a region of100×100m2 is scattered into 1×1m2 grids, the length of the chromosome is 100×100/1×1=104. In case the region is rather complex, we have to divide it into grids of 0.1×0.1m2. Then, the length of the chromosome becomes 100×100/0.1×0.1=106, increasing the computation dramatically.In conclusion, both methods can provide a scheme to deploy base station clusters, and the choice depends on the users’ preference.


## 4.1. Approximate the Covered Region as a Circle

In this paper, UWB positioning is achieved through ranging between base stations and tags. In 2D space, if one robot wants to determine its position, one option is to obtain distance measurements to at least three base stations that are not in a line. In our case, three base stations are located near to each other, forming a group. To determine positions with the group, a robot needs to be within the coverage range of each of them, i.e., it should be within the overlap region of the coverage range of all the three base stations, as shown in Figure9. We call this overlap region S and obviously it is irregular. To simplify the problem, S needs to be approximated into a regular shape, and there are two choices. We can either use an inscribed triangle St or a circumcircle Sc to approximate S, and the one whose area is closest to that of S is the solution. Thus, it is required to calculate the area of S, St, and Sc. To simplify the expression, in the following, S, St, and Sc are used to represent the area of the corresponding region.Figure 9
The overlap region and its approximation. Shadow in (a) indicates the overlap region of the coverage range of three UWB base stations, i.e.,S. Shadow in (b) approximates S with its inscribed triangle St, and shadow in (c) approximates S with its circumcircle Sc.
(a)(b)(c)In our case, three base stations are located atxi,yi,i=1,2,3, composing an equilateral triangle. As all the three base stations are identical in hardware configuration, the coverage range is supposed to be the same, which is a disc with a radius of R. With the information, S can be determined. The three vertices of S are also the vertices of St, which can be obtained with the following procedure.Define the vertices asxki,j, where i,j,k∈1,2,3 and i,j,k are different, representing the vertex who is a cross point of disks centered by xi,yi and xj,yj, and this cross point is within the range of the third disk centered by xk,yk. Then, we have(1)xki,j−xi2+yki,j−yi2=R2,xki,j−xj2+yki,j−yj2=R2,xki,j−xk2+yki,j−yk2<R2.With the expressions above, we can determine the three vertices. Furthermore, we can obtain any edge length ofSt by computing the distance between the corresponding two vertices. For example,(2)lt1,2=x31,2−x21,32+y31,2−y21,32.As the center of discs is placed as an equilateral triangle, thus the three vertices are equivalent, makingSt also an equivalent triangle, whose edges have(3)lt≔lt1,2=lt1,3=lt2,3.Thus,(4)St=34lt.ForSc, its center can be obtained with(5)xc,yc=x1+x2+x33,y1+y2+y33.The radius ofSc can be measured as the distance between xc,yc and a random vertex xki,j,yki,j, as(6)lc=xc−xki,j2+yc−yki,j2.So the area ofSc can be obtained as follows:(7)Sc=πlc2.The overlap regionS is a bit tricky, as shown in Figure 10. It consists of the inscribed triangle St and three arch form areas, represented as Sarchk, where k indicates the center of the circle corresponding to the arch and k=1,2,3. Then,(8)S=St+∑k=13Sarchk.Figure 10
An auxiliary figure for calculatingS.The area ofSarchk can be obtained with(9)Sarchk=Sfank−Strianglek,where Sfank is the corresponding fan centered by xk,yk and Striangle is the triangle with three vertices of xk,yk, xik,j,yik,j,andxjk,i,yjk,i, as shown in Figure 10.To calculate the area ofSfan, it requires its radius R and its span angle θ. R is obtained by experiments, and θ is lacking. To calculate θ, we first get two vectors starting from the center of the disk xk,yk and pointing at the other two points as(10)v⟶k,i=xik,j−xk,yik,j−yk,v⟶k,j=xjk,i−xk,yjk,i−yk.Since(11)v⟶k,i⋅v⟶k,j=v⟶k,iv⟶k,jcosθ,then(12)θ=acosxik,j−xkxjk,i−xk+yik,j−ykyjk,i−ykxik,j−xk2+yik,j−yk2xjk,i−xk2+yjk,i−yk2.The area of the fan can be obtained as(13)Sfank=πR2⋅θ2π=θ2R2,where Striangle is an isosceles triangle with two edges being R and the base line is the chord of the arch, whose length is(14)lchord=xik,j−xjk,i2+yik,j−yjk,i2.Then the area of the triangle can be calculated with Heron’s formula. Half of the perimeter is given by(15)lhp=122R+lchord.Then the area is(16)Strianglek=lhplhp−R2lhp−lchord.WithSfank and Strianglek,(17)Sarchk=Sfank−Strianglek.As the three arch form areas are equivalent, the area ofS then is(18)S=St+∑k=13Sarchk=St+3Sarchk,where k could be 1, 2, or 3.Compared withS, St is a bit smaller while Sc is a bit larger. Define the rate of approximate error as(19)rt=S−SapproximateS,Sapproximate∈St,Sc.The change of approximation error is shown in Figure11. If the distances among base stations are small, approximate the overlap region as a disc is a better choice. In our case, according to Section 3, three base stations are placed as an equilateral triangle, whose side length is 50 cm. The error rate is 1.9023%. This means the disk can approximate the actual overlap region with a minor error. Then methods to place multiple such disks to cover an area of a random shape can be considered in the following.Figure 11
Approximation errors ofSc and St with the increase of distances among base stations. When the distances among stations are less than 1 m, the approximation error of Sc is less than 5%, while that of St reaches 60%.


## 4.2. Deployment with Dynamic Particle Swarm Optimization

We intend to place multiple groups of UWB base stations to provide positioning services for robots. In Section4.1, it is shown that the irregular overlap region of the three base stations can be approximated as a disk reasonably. Then the problem becomes where to place these disks and how many such disks are needed. Therefore, the deployment scheme is a trade-off between coverage rate and cost.Inspired by [35], a PSO-based algorithm is proposed in this paper that can dynamically adjust the number of UWB clusters. The algorithm is called dynamic PSO, or short as DPSO.Generally, DPSO consists of two loops. The outer loop adjusts the number of station groups, while the inner loop adjusts the positions of station groups following the idea of PSO. Assume that in theiout iteration of the outer loop, Niout station groups are used. Then, for its inner loops, the particles are encoded as the following sequence:(20)P=x1,x2,…,xNiout,y1,y2,…,yNiout,where xj,yj∈S and xj,yj,j=1,2,…,Niout, indicates the position of the jth station group.The fitness function is set to maximize the coverage rate(21)argmaxfP=SPS,where SP is the valid area covered by the station groups and S is the area of the valid area in the map. “Valid” refers to only the region accessible for the robots counts. To measure SP and S in an irregular area, we mesh the map into a set of grids and estimate areas by counting the number of grids. A swarm of particles is generated randomly in the init process. Then the particles search in the solution space guided by some historical best solutions randomly, as introduced in [36]. Besides, the particle P should not move out of the valid area S, so that a filter is designed. According to the idea above, the pseudocode of DPSO is presented in Algorithm 1. Key functions of Algorithm 1 are detailed in Algorithms 2 and 3, respectively. A general flowchart of Algorithm 1 is shown in Figure 12.Algorithm 1: Dynamic PSO.
Input: valid area S, radius of approximate disk ROutput: set Sbest consists of best particles with different lengths(1)
Set parameters: swarm sizeNswarm, iteration number Nin(2)
Set parameters for PSO:ω,c1,c2(3)
Sbest←ϕ(4)
Group number range:Nmin=S/πR2, Nmax=S/2R2(5)
foriout=Nmin,Nmin+1,…,Nmaxdo(6)
P≔pk|pk←GeneratePosS,iout,k=1,…,Nswarm(7)
V≔vk|vk←GenerateVel,k=1,…,Nswarm(8)
pbestj←pj,j=1,…,Nswarm(9)
gbest←argmaxfpj,j=1,…,Nswarm(10)
foriin=1,2,…,Nindo(11)
fori=1,2,…,Nswarmdo(12)
vtemp←ωvi+c1r⋅pbest−pi+c2r⋅gbest−pi(13)
ptemp←pi+vtemp(14)
pi,vi←ConstrainS,vtemp,ptemp,vi,pi(15)
pbesti←argmaxfp,p∈pi,pbesti(16)
end for(17)
gbest←argmaxfp,p∈pbest1,…,pbestNswarm(18)
end for(19)
Sbest←Sbest∪gbest(20)
end forFigure 12
The flowchart of Algorithm1.Thus, Algorithm1 has a complexity of ONmax−Nmin×Np+Nin×Nswarm×Ng. In Algorithm 1, the inputs are the valid area S and the radius R of the approximate coverage disk. The output is a set Sbest, consisting of best particles with different numbers of base station clusters. The parameters for the algorithm are set in lines 1-2. In line 4, the range of numbers of clusters to be explored is calculated. The floor is the number of groups needed to stuff the area with disks, which is S/πR2, and the ceil is the number of groups needed to stuff the area with the inscribed square of the disk, which is S/2R2. The loop in lines 5–20 is the outer loop, which increases the number of groups by one each time, expending the length of the particle. In each iteration, the particle swarm P, the velocity set V, the historical best solution for each particle pbest, and the best solution for all particles gbest are reset. Then, within the inner loop in lines 10–18, the velocity and position of each particle are updated randomly, affected by gbest and pbest. Then gbest and pbest are updated.In line 6, we use functionGeneratePos to obtain a random particle, as in Algorithm 2. The challenge here is that S is of random shape, and there is a high chance that the particle obtained with a general random number generation algorithm will go out of range. To solve this problem, in GeneratePos, we first scatter S into a set of grids and then stack the grids up into a sequence. The grids in the sequence are then labeled successively. We generate iout random numbers within the range of 1,Ns, where Ns is the number of the grids. These random numbers are the indexes of grids chosen as elements in the particle. The complexity of Algorithm 2 is ONp.Algorithm 2: function GeneratePos().
Input: the area of interest S, particle length NpOutput: random particle p(1)
functionGeneratePosS,iout(2)
ScatterS into NS grids, stacking as a sequence Ssequence: Ssequence=s1,…,sNS(3)
px←,py←(4)
fori=1,2,…,Npdo(5)
Index←ceilrand×NS−1(6)
px←px,sIndexx,sIndex∈Ssequence(7)
py←py,sIndexy,sIndex∈Ssequence(8)
end for(9)
p←px,py(10)
end functionIn line 7, the function GenerateVel() initializes the velocity of a particle with a zero sequence having the same size of the particle.In line 14, we use functionConstrain to ensure particles will not move out of S, as in Algorithm 3. According to the encoding rule, the particle represents the coordinates of the station groups. If a station group moves out of S, we just ignore the update of its position and corresponding velocity this time. Meanwhile, the updates of velocities and positions for other station groups are not affected. Algorithm 3 has a complexity of ONg.Algorithm 3: Function Constrain().
Input: the area S, original particle, and velocity p,v and the raw value based on them ptemp,vtempOutput: updated particle and velocity p,v(1)
functionConstrainS,p,v,ptemp,vtemp(2)
Number of station groupsNg=lengthp/2(3)
fori=1,2,…,Ngdo(4)
pxo,pyo←pi,pi+Ng(5)
vxo,vyo←vi,vi+Ng(6)
pxr,pyr←ptempi,ptempi+Ng(7)
vxr,vyr←vtempi,vtempi+Ng(8)
ifpxr,pyr∉Sthen(9)
pi←pxo(10)
pi+Ng←pyo(11)
vi←vxo(12)
vi+Ng←vyo(13)
else(14)
pi←pxr(15)
pi+Ng←pyr(16)
vi←vxr(17)
vi+Ng←vyr(18)
end if(19)
end for(20)
end functionIn lines 9, 15, and 17, the fitness functionf⋅ needs to be calculated to choose the best particle. As S is irregular, a meshing scheme is applied to estimate the coverage rate:(22)fp=SPS=NcoveredNS,where Ncovered is the number of grids covered by at least one of the station groups and NS is the number of grids in S. For each grid, we calculate the distance from its center to all the center of station groups as dis=di|i=1,…,iout. If mindis<R, we treat the grid being covered. In this way, Ncovered can be obtained.Running this algorithm, we notice that there is a chance that the best particle with more station groups performs worse than that with fewer station groups, as shown in Figure13. This is because in line 6 of Algorithm 1, each time the number of station groups is changed, the particle swarm is regenerated randomly. The red dots in Figure 13(a) indicate that, with 48 stations, the coverage rate is higher than that of 49 and 50 station groups. Clearly, the solution in Figure 13(b) performs better, with fewer station groups. There is a chance that the init swarm is rather bad, and we do not iterate enough times in the inner loop to obtain a good solution. It is not easy to check and decide when to increase the iteration number for the program automatically. With DPSO, the tendency is that more station groups will increase coverage rate, but not stable.Figure 13
Performance of DPSO. (a) The coverage rate changes with the increase of station groups. (b–d) The corresponding solutions provided by DPSO, with 48, 49, and 50 station groups, respectively. The yellow regions are covered by UWB clusters. (a) Performance of DPSO. (b) Group number = 48. (c) Group number = 49. (d) Group number = 50.
(a)(b)(c)(d)To solve this problem without increasing the iteration number, the DPSO algorithm is improved into the Elite DPSO algorithm, which ensures that the more UWB clusters are used, the better solution can be obtained. Elite DPSO is almost the same as DPSO, but line 6 in Algorithm1 is changed as(23)P≔Prandom∪Pelite,Prandom≔pk|pk←GeneratePos,k=2,…,Nswarm,Pelite≔pelite←GenerateElitegbest.This means that each time the group number is increased,Nswarm−1 particles are randomly regenerated, as is done in DPSO. A special particle called elite particle is also generated with function GenerateElitegbest based on the best particle gbest obtained in the last iteration of the outer loop. It should perform better than gbest. Two kinds of GenerateElitegbest are explored.One way to generate elite particle is to add a cluster with a random position inS to gbest. In the worst case, the newly added cluster overlaps with another cluster in gbest, resulting in fpelite=fgbest. Otherwise, pelite covers more region, ensuring that fpelite≥fgbest. This scheme is named as Random Elite DPSO.Another way to generate elite particle is to add a cluster far from other clusters ingbest, encouraging station groups to move to a relatively empty region. Assume that the newly added cluster is located at x,y and other clusters in gbest are located at xi,yi,i=1,…,iout. Then, the optimal position can be obtained with(24)argmaxdx,y=∑i=1ioutxi−x2+yi−y2iout.Apparently,dx,y is a convex function, so its maximum value is obtained with x,y on the border of the region. All grids at the border of S are exhausted to obtain x,y. This method is named Sparse Elite DPSO because it intends to encourage the locations of station groups to be sparse.The performance of both schemes is compared, showing in Figure14. From the figures, the Sparse Elite DPSO method performs slightly better than the Random Elite DPSO method. However, considering the computation cost on average, the Random Elite DPSO is a more reasonable choice.Figure 14
Performance of the Elite DPSOs. (a) Typical performance of the Random Elite DPSO and the Sparse Elite DPSO. With the increase of station groups, the coverage rate always increases. (b) Comparison of the average coverage of the Random Elite DPSO and the Sparse Elite DPSO in terms of computation cost. Boxplots in (c) and (d) show the statics results of the two Elite DPSOs. The data are obtained by repeating experiments 10 times. (a) Typical performance. (b) Average performance. (c) Random Elite DPSO. (d) Sparse Elite DPSO.
(a)(b)(c)(d)


## 4.3. Deployment with Genetic Algorithm

The DPSO methods proposed in Section4.2 explore a set of group numbers and provide the best solutions correspondingly. However, they are unable to determine the best group number automatically. A GA-based algorithm is then developed, which can provide the best number of clusters needed to cover a region and the deployment scheme, indicating positions of clusters.We scatter the area of interest with random shape intoNS grids and use the center of the grids to represent them. Thus, these grids are labeled as g1,g2,…,gNS. Then in GA, the chromosome is encoded as an element vector with the length of NS. Each element is either 0 or 1. If the ith element is 1, then a cluster is deployed at the center of grid gi. Otherwise, a cluster will not be deployed. This implies that(i)
A cluster can only be located at the center of a grid, unable to move continuously(ii)
A chromosome always represents a feasible solution because the grid sequence only contains accessible areasThe fitness function is given by(25)fg=Sg1S=Ncovered1NS,where Sg1 indicates the sum of the area only covered by one cluster, Ncovered1 is the number of grids whose center is covered only by one cluster, and NS stands for the total number of grids. The ratio of Ncovered1 and NS is used to estimate the fitness function value. Defining the fitness function in this way encourages clusters to cover more grids, which satisfies the target that the whole area of interest to be covered. Meanwhile, this definition can prevent the algorithm from adding too many clusters to achieve a high coverage rate because the increase of overlap rate results in a decrease of fitness value. In this way, the algorithm can adjust the number of clusters automatically.Then a swarm of chromosomes is generated. The fitness function is used to evaluate and choose the chromosomes. A cross operator is used to create a new chromosome, and a mutation operator is applied to add randomness to the chromosomes, as the idea introduced in [37]. The algorithm is shown in Algorithm 4. Details of functions in Algorithm 4 are further introduced in Algorithms 5–9 . A general flowchart of Algorithm 4 is shown in Figure 15.Algorithm 4: Generate deployment scheme with GA.
Input: valid area S, radius of approximate disk ROutput: positions for station groups: P=xi,yi:i=1,…,Nbest(1)
Set parameters: swarm sizeNswarm, iteration number Niter(2)
Set parameter: mutation rateμ(3)
Set parameter: swarm creation parameterpinit(4)
ScatterS into grids, labeled as S=g1,g2,…,gNS(5)
Create swarm:C≔ck|ck←GENERATECHROMOSOMENS,pinit,k=1,…,Nswarm(6)
Initialize the best chromosome:cbest←argmaxfc,c∈C(7)
fori=1,…,Niterdo(8)
Calculate fitness value:F←fci:ci∈C(9)
Selection operation:Cnew←SELECTIONC,F(10)
Cross operation:Cnew←CROSSC,Cnew(11)
Mutation operation:Cnew←MUTATIONCnew,μ(12)
Update the swarm:C←Cnew(13)
Update the best chromosome:cbest←argmaxfc,c∈cbest∪C(14)
end for(15)
Decode:P=DECODES,cbestAlgorithm 5: Function GenerateChromosome().
Input:NS,pinitOutput: random chromosome c(1)
functionGenerateChromosomeNS,pinit(2)
GenerateNS random numbers obey normal distribution: c=c1,…,cNS(3)
fori=1,2,…,NSdo(4)
ifci>pinitthen(5)
ci←1(6)
else(7)
ci←0(8)
end if(9)
end for(10)
end functionAlgorithm 6: Function Selection().
Input:C,FOutput: new swarm Cnew(1)
functionSelectionC,F(2)
fori=1,…,Nswarmdo(3)
ri←fi/∑Nswarmj=1fj,fi,fj∈F(4)
end for(5)
Rfloor=0,Rceil=r1(6)
fori=1,…,Nswarm−1do(7)
Rfloor←Rfloor,∑ij=1rj(8)
Rceil←Rceil,∑i+1j=1rj(9)
end for(10)
Cnew←ϕ(11)
fori=1,…,Nselectiondo(12)
Cnew←Cnew∪ck, where ck∈CWithrkfloor<rand<rkceilWhererkfloor∈Rfloor,rkceil∈Rceil(13)
C←C∖ck(14)
end for(15)
end functionAlgorithm 7: Function Cross().
Input:C,CnewOutput: new swarm Cnew(1)
functionCrossC,Cnew(2)
fori=1,…,C−Cnewdo(3)
p1←RandC(4)
C←C∖p1(5)
p2←RandC(6)
Exchange elements inp1,p2 after random point, obtain s1,s2(7)
s←Rands1,s2(8)
Cnew←Cnew∪s(9)
end for(10)
end functionAlgorithm 8: Function Mutation().
Input:Cnew,μOutput: new swarm Cnew(1)
functionMutationCnew,μ(2)
forc∈Cnewdo(3)
fori=1,2,…,NSdo(4)
ifrand<μthen(5)
ci←/ci,ci∈c(6)
end if(7)
end for(8)
end for(9)
end functionAlgorithm 9: Function Decode().
Input:S,cbestOutput: positions for station groups P(1)
functionDecodeS,cbest(2)
P=ϕ(3)
fori=1,…,NSdo(4)
ifci=1,ci∈cbestthen(5
)P←P∪xi,yiWherexi,yi is the center of gi∈S(6)
end if(7)
end for(8)
end functionFigure 15
The flowchart of Algorithm4.In Algorithm4, necessary parameters are set in lines 1–3. Then the area S is scattered into grids, helping to calculate the fitness function value and enable us to decode the best chromosome. In line 5, the swarm is generated using a function GenerateChromosome(), and the chromosome with the biggest fitness value is chosen as the current best chromosome, which is presented in detail in Algorithm 5. Then the loop enters lines 7–14. In each iteration, the fitness values of chromosomes in the swarm are first calculated. Then go through selection operation as introduced in Algorithm 6, cross operation as introduced in Algorithm 7, and mutation operation as introduced in Algorithm 8. Finally, update the best chromosome cbest by comparing if a better solution is obtained in this iteration. Function Decode() is used to decode the chromosome into cluster positions, which is presented in detail in Algorithm 9. Algorithm 4 has a complexity of ONswarm×Ns×Niter.Function GenerateChromosome() randomly generates a sequence whose length is the same as the number of grids inS, with each element corresponding to a grid. The sequence only consists of 0 and 1, with 1 indicating a cluster to be deployed at the center of a grid. To generate such a sequence, i.e., a chromosome for the GA, we first generate Ns random values obeying normal distribution, as line 2 in Algorithm 5. If the value is larger than parameter pinit, it is set as 1, and 0 otherwise, as lines 4–8. Algorithm 5 has a complexity of ONs.It is obvious that the choice ofpinit affects the number of clusters deployed initially and affects the optimization process indirectly. Thus, setting a proper pinit is important. Our suggestion of setting pinit is to follow(26)NSPx>pinit=SSc,where P is a probability distribution and Sc is the area covered by one cluster. In this paper, the normal distribution is chosen for P. Then,(27)Px≤pinit=1NSNS−SSc.A properpinit can be obtained by solving this equation.Function Selection() presented in Algorithm6 takes current swarm C and the fitness values of these chromosomes F as inputs. With a roulette scheme, half of the chromosomes are selected into the next generation, which means Nselection=1/2Nswarm. The roulette scheme is achieved by creating a floor sequence Rfloor and ceiling sequence Rceil based on the ratio of a chromosome’s fitness value to the sum of the fitness values, shown in lines 2–9. Rfloor and Rceil form a sequence of slots. A random number is generated and falls into a slot. The chromosome corresponding to the slot is selected, as in lines 12-13. Algorithm 6 has a complexity of ONswarm.The selection operation presented in Algorithm6 is a general operation in GA and it works well in various scenarios. However, it performs poorly in our case, as shown in Figure 16. The reason is that the fitness values of a swarm are similar, resulting in a roulette scheme unable to select proper chromosomes for the next generation effectively.Figure 16
Performance of GA with a roulette scheme and an elite scheme during iterations. (a) The change of cluster number of the best chromosome for each iteration. (b) The coverage rate of the best chromosome. (c) The fitness value, i.e., the rate of the area only covered by one cluster.
(a)(b)(c)This problem is solved by adopting an elite chromosome scheme. The idea is to choose some best chromosomes and put them directly into the next generation. Then, lines 11–14 in Algorithm6 are replaced with the following:(i)
Sort elements inC as descending order of elements in F(ii)
Cnew←c1,c2,…,cNselection∈CNselection is the number of chromosomes directly passed to the next generation. To add more randomness, we set Nselection=1/4Nswarm. From Figure 16, it can be seen that this elite chromosome scheme can ensure that the fitness value never decreases. Besides, the algorithm can automatically adjust the number of clusters. Comparing with the roulette scheme, the elite chromosome scheme can achieve a higher fitness value and a coverage rate with fewer clusters. This point is clearly shown in Figure 17, where we exhibit the deployment of clusters according to solutions obtained with GA using two different selection operators. In both cases, 35 clusters are deployed. The solution with the elite scheme resulting in clusters spreading more evenly and covering more area than that of the roulette scheme.Figure 17
Deployment of clusters according to solutions obtained with GA using a roulette selection scheme and an elite selection scheme. The area with a blue background is the area of interest, and each red circle indicates the coverage range of a cluster. (a) Roulette scheme. (b) Elite scheme.
(a)(b)Function Cross() in Algorithm7 generates the rest chromosomes. It randomly picks two chromosomes as parents, exchanges their elements after a random point, and generates two children (lines 2–6). Then, in lines 7–8, a random child is chosen and added to the swarm. Algorithm 7 has a complexity of ONswarm.Function Mutation() in Algorithm8 randomly generates NS numbers. If the number is larger than the mutation parameter μ, the corresponding element in the chromosome is inverse from 0 to 1 or from 1 to 0. Attention should be paid that μ should be set as a relatively small number, as a big μ introduces 1s rapidly during iterations as shown in Figure 18, overwhelming the algorithm’s ability to adjust cluster numbers. Algorithm 8 has a complexity of ONs×Nswarm.Figure 18
Change of the number of 1s in the best chromosome with differentμ. As the number of 1s increases dramatically with bigger μ, use log10⋅ to record the numbers.Function Decode() in Algorithm9 decodes the best chromosome into a set of coordinates for cluster deployment. Algorithm 9 has a complexity of ONs.


## 4.4. Comparison of the Two Schemes

Experiments have been carried out to test the algorithms provided in Sections4.2 and 4.3. The results in a rectangle region and a randomly generated irregular region are presented here, as shown in Figure 19. For the PSO, the swarm size is set as 20 and the iteration number is 50. The station group number increased from the number of clusters necessary to just fulfill the area ignoring the shape, which is 21. The solution of GA contains 29 clusters. To make it comparable, in DPSO, we also set the maximum number of clusters as 29. It turns out that the coverage can reach 87.98%. For the Elite GA, the swarm size is set as 50 and iteration number 200. Parameter μ is set as 0.00001 and pinit is automatically set with the method introduced in Section 4.3. The solution provided by the Elite GA contains 29 clusters, with a coverage rate reaching 89.87%, slightly better than that of the Elite DPSO. Taking the randomness of both algorithms into consideration, we cannot claim the Elite GA is better than the Elite DPSO. In fact, the algorithms have different features, and some discussion is provided in the following.Figure 19
Deployment of clusters into an irregular area of interest according to solutions obtained with (a) the elite DPSO and (b) the elite GA.
(a)(b)DPSO can provide a set of particles corresponding to a different number of groups. Thus, users can choose the best one according to the cost and the coverage rate. GA automatically decides how many clusters are needed, and users can directly use the scheme generated. However, users are unable to assign the number of clusters.In DPSO, base station groups move continually in the area of interest, while, in GA, base station groups jump among grids. This means DPSO has more flexibility than GA. If we are seeking for a more precise solution with GA, the area of interest has to be meshed into more grids, increasing the length of the chromosome and resulting in more computation. For example, if a region of100×100m2 is scattered into 1×1m2 grids, the length of the chromosome is 100×100/1×1=104. In case the region is rather complex, we have to divide it into grids of 0.1×0.1m2. Then, the length of the chromosome becomes 100×100/0.1×0.1=106, increasing the computation dramatically.In conclusion, both methods can provide a scheme to deploy base station clusters, and the choice depends on the users’ preference.


## 5. Experiment Validation of UGV Navigation Based on UWB Cluster Positioning

In Section3, the performance of a UWB cluster is tested and validated, and then in Section 4, the deployment methods of UWB clusters are proposed and validated by simulations. In this section, the outcomes of the previous sections are applied to UGVs. Based on the experiments in Section 3, 50 cm side length is chosen for a UWB cluster and 10-meter distance is determined as the coverage radius of a UWB base station. UGVs are then set out to follow different paths, showing that under the positioning of UWB groups, errors of UGV trajectories are constrained around 25 cm. With UWB clusters, UGVs can move smoothly to their destinations.


### 5.1. Design of UGVs

In order to validate the navigation performance based on the UWB cluster positioning system, UGV prototypes are fabricated. The control kernel hardware is composed of an MCU, a UWB tag, an IMU, a WiFi module, and actuators. The structure is shown in Figure20. The MCU acts as the “brain” of a UGV, receiving input information and making control decisions. A 32-bit MCU, STM32H750VB, is adopted, which includes an Arm Cortex-M7 with 128 Kbytes of flash memory, 1 MB RAM, 480 MHz CPU, L1 cache, large set of peripherals. The UWB tag uses DWM1000 of Decawave. For IMU, MPU-9250 is applied, which has a 9-axis motion processing unit including a gyroscope, an accelerometer, and a digital compass. The WiFi connection is established using a low-cost WiFi microchip, ESP8266, with a full TCP/IP stack. The operation of DC motors is driven by A4950s, full-bridge DMOS PWM motor drivers. The UGV prototype is shown in Figure 21.Figure 20
UGV control kernel hardware structure.Figure 21
UGV with UWB tag.


### 5.2. UGV Automated Driving under UWB Positioning

In this part, experiments are carried out with UGVs using a UWB cluster positioning system. First, UGV automated driving is realized in an 8 m×9 m room, as shown in Figure 22. A UGV is programmed to follow designated trajectories shown in Figure 23. It can complete fixed-point back and forth trajectory, square trajectory, and circular trajectory. For each test, target positions or waypoints are generated. The UGV checks whether the current position is within a circle around these positions to guarantee that it follows the designated paths. The live demonstration video is provided in supplemental materials. The test results of a circular trajectory are depicted in Figure 24 and the corresponding positioning errors are provided in Figure 25. In all the experiments, the position errors are within 30 cm as shown in Figure 26, which are consistent with test results in Section 3.2.Figure 22
UWB positioning-based UGV automated driving test.Figure 23
UWB positioning-based UGV automated driving test.Figure 24
Field test results of a circular trajectory monitored by the Windows app.Figure 25
Position errors of a circular trajectory, corresponding to Figure24.Figure 26
Position error statistics of all field tests.


## 5.1. Design of UGVs

In order to validate the navigation performance based on the UWB cluster positioning system, UGV prototypes are fabricated. The control kernel hardware is composed of an MCU, a UWB tag, an IMU, a WiFi module, and actuators. The structure is shown in Figure20. The MCU acts as the “brain” of a UGV, receiving input information and making control decisions. A 32-bit MCU, STM32H750VB, is adopted, which includes an Arm Cortex-M7 with 128 Kbytes of flash memory, 1 MB RAM, 480 MHz CPU, L1 cache, large set of peripherals. The UWB tag uses DWM1000 of Decawave. For IMU, MPU-9250 is applied, which has a 9-axis motion processing unit including a gyroscope, an accelerometer, and a digital compass. The WiFi connection is established using a low-cost WiFi microchip, ESP8266, with a full TCP/IP stack. The operation of DC motors is driven by A4950s, full-bridge DMOS PWM motor drivers. The UGV prototype is shown in Figure 21.Figure 20
UGV control kernel hardware structure.Figure 21
UGV with UWB tag.


## 5.2. UGV Automated Driving under UWB Positioning

In this part, experiments are carried out with UGVs using a UWB cluster positioning system. First, UGV automated driving is realized in an 8 m×9 m room, as shown in Figure 22. A UGV is programmed to follow designated trajectories shown in Figure 23. It can complete fixed-point back and forth trajectory, square trajectory, and circular trajectory. For each test, target positions or waypoints are generated. The UGV checks whether the current position is within a circle around these positions to guarantee that it follows the designated paths. The live demonstration video is provided in supplemental materials. The test results of a circular trajectory are depicted in Figure 24 and the corresponding positioning errors are provided in Figure 25. In all the experiments, the position errors are within 30 cm as shown in Figure 26, which are consistent with test results in Section 3.2.Figure 22
UWB positioning-based UGV automated driving test.Figure 23
UWB positioning-based UGV automated driving test.Figure 24
Field test results of a circular trajectory monitored by the Windows app.Figure 25
Position errors of a circular trajectory, corresponding to Figure24.Figure 26
Position error statistics of all field tests.


## 6. Conclusion

In this paper, the concept of UWB clusters composing of multiple UWB base stations as one device is proposed to provide positioning service for robots. Tests in Section3 show that this positioning system works well. Within 8 meters, the mean distance errors are less than 20 centimeters in most cases. Within 10 meters, the mean position errors are no more than 60 centimeters in most cases. By approximating the overlap area covered by all the three base stations in one group as a circle, two algorithms are proposed to obtain the best deployment scheme in an area of interest with random shape. Both algorithms can help determine the number of groups necessary. Furthermore, the UWB positioning system is verified by conducting multiple tests with UGVs. The results confirm that UGVs can follow complex trajectories precisely. The UWB cluster’s ability to support multiple robots highlights its potential application in swarm robotics. Furthermore, combining multiple base stations as one positioning device, it can be equipped on a larger vehicle such as an unmanned surface vehicle or a heavy drone, providing high-accuracy positioning service for a swarm of smaller robots. Note that, in this paper, we mainly focus on the feasibility of the proposed idea, and the performance improvement of the positioning system is reserved as future work.



---

*Source: 6639574-2021-04-23.xml*