Relative Localization of Robot Swarms

Relative Localization of Robot Swarms: History

Please note this is an old version of this entry, which may differ significantly from the current revision.

Subjects: Robotics

Contributor:

Siyuan Chen

For robot swarm applications, accurate positioning is one of the most important requirements for avoiding collisions and keeping formations and cooperation between individuals. However, in some worst cases, the GNSS (Global Navigation Satellite System) signals are weak due to the crowd being in a swarm or blocked by a forest, mountains, and high buildings in the environment. Thus, relative localization is an indispensable way to provide position information for the swarm.

robot swarms
localization technology
relative localization

1. Introduction

Biological swarms in nature realize complex group behaviors in the form of distributed control and self-organization under the interaction between adjacent individuals and the environment through simple autonomous decision-making rules and local sensing communication [1]. A biological swarm has the following characteristics:

1.: Collective robustness

The biological swarm has a robust hierarchical structure that uses the interrelationship effect of the organizational framework to transform the structure to fill the gap when an individual failure causes a vacancy. Failure of a single individual does not significantly affect the biological swarm performance.
2.: Individual simplicity

Individuals within a swarm do not have a strong ability to accomplish the swarm’s tasks alone. Due to their simplicity, individuals accomplish complex tasks with each other through cooperative behavior with spatio-temporal relationships.
3.: Scalability

When the number of individuals in a swarm increases, the control mechanism is still effective. The relative relationships within a swarm can be maintained steadily. The characteristics displayed by a swarm depend on the ability of individuals within the swarm to obtain the relative position of those around them.

Due to the limitations of endurance, sensing and load capacity, the robot’s ability to perform tasks alone is restricted. With the complex changes of task demands, people turn their attention to robot swarms, hoping that they can break through the limitations of individual and complete more complex tasks through group cooperation. Inspired by biological swarms, robot research has been developing in decision-making planning, communication networking, formation control, conflict resolution and other aspects [2]. Kushleyev et al. [3] used a VICON motion capture system to obtain the position information of 20 MAVs (micro aerial vehicles) for highly agile formation control. Liu et al. [4] used GPS (Global Positioning System) for the group positioning of 21 small fixed-wing UAVs (unmanned aerial vehicles) to complete formation control and collaborative recognition. Localization is the fundamental technology to achieve group robustness, cooperation and extensibility.

Localization can be divided into GNSS-based positioning and relative localization according to whether absolute location information can be obtained [5,6]. Biological swarms rely on sun and scene perception for self-positioning. Robots can obtain absolute position information provided by GNSS such as GPS, BeiDou, GLONASS, and Galileo. Relative localization is used to determine the relative position of an individual robot relative to other agents when absolute position information cannot be obtained [5]. Relative localization technology mainly involves measuring the distance/angle between individuals by sensors and then calculating the relative position coordinates of individuals relative to other units, which mainly includes sensor measurement methods and relative localization algorithms.

With the development of technology, the accuracy of GNSS-based positioning has been continuously improved. The localization precision of GNSS using RTK (real-time kinematic) technology reaches the centimeter level [7,8]. However, the GNSS positioning resolution will be reduced or the system will fail in dense buildings or mountainous jungles, or when individuals in dense groups block each other. Relative localization technology mainly solves the problem of robot positioning in complex environments and has become a research hotspot of robot motion control, multi-aircraft formation, cooperative detection and other applications [9,10,11].

2. Measurement System

We use sensors to get raw measurement information. Typical sensor devices that can be used for relative localization include Bluetooth, Wi-Fi, RFID, UWB, lidar, RGB camera, infrared camera, etc.

2.1. Bluetooth

Bluetooth works in the 2.4 GHz ISM (Industrial Scientific Medical) band, with fast signal attenuation and weak penetration. When adjacent devices communicate, RSS (received signal strength) can be used to obtain distance information [31], and an antenna array can also be used to obtain angle information. The Bluetooth 5.0 signal range for positioning can reach 100 m, and the distance is calculated by modifying the signal intensity attenuation model in the environment, with accuracy to the meter level [32]. The angle accuracy of the obtained direction when using an antenna array is 8° [33]. Bluetooth can be used to locate mobile devices with slow motion speed [34].

2.2. Wi-Fi

Wi-Fi works in the ISM band of 2.4 G/5 GHz, and the signal range of Wi-Fi 4 can reach 250 m [35]. Similar to Bluetooth, Wi-Fi uses RSS to obtain distance information or an antenna array to obtain angle information, which can be used for outdoor emergency search positioning and indoor mobile device localization. The distance accuracy is at the meter level [14], and the direction error is less than 9° [36].

2.3. RFID

RFID has LF (Low Frequency, 125 KHz), HF (High Frequency, 13.56 MHz), UHF (Ultra High Frequency, 433 MHz, 860–960 MHz, 2.4 GHz) and SHF (Super High Frequency, 5.8 GHz) frequency bands [24]. The effective reading range of the UHF passive label is 10 m [18,37,38]. RFID of UHF can read the phase of the tag signal response and has a linear relationship with the distance between the detector and tag. The signal phase is integrated with RSS, and the measurement accuracy can reach the cm level, which can be used for indoor warehouse location tracking or UAV positioning tracking [37,38]. To improve the localization accuracy, Bernardini et al. [39] proposed a synthetic aperture radar (SAR) localization method for UHF-RFID tags by properly combining the phase data associated with a set of multiple paths, and the total length of the combined synthetic aperture increased, which in turn can improve the localization accuracy to approximately 4 cm.

2.4. UWB

UWB devices operate in the 250–750 MHz, 3244–4742 MHz, and 5944–10,234 MHz frequency bands [40]. They transmit data signals using narrow nanosecond non-sinusoidal pulses with a bandwidth of 500 MHz or more. Their signals have an effective range of about 100 m and are highly penetrating and resistant to multipath [5]. The time of flight and thus the distance is solved by measuring the transmission of frames between two nodes with a measurement error in the centimeter level and a frequency up to 372 Hz [41]. It can be used for ranging and localization of indoor mobile devices and outdoor robots [42,43].

2.5. Lidar

Lidar [44] uses 905 nm or 1550 nm light to scan the environment and detect a distance of about 200 m [45]. It uses the propagation time of light reaching the object and reflecting to calculate the point cloud information of the distance between it and the environment. The point cloud information is used to analyze the relative position of the device compared to the surrounding objects with a level of accuracy at the centimeter level. Lidar can be used to solve the problem of road recognition and obstacle avoidance in autonomous vehicle driving [46].

2.6. RGB Camera

Similar to lidar, RGB cameras [47] are used to collect image information, extract features and construct scenes through algorithms to determine their positions from them. The accuracy of the position solution is within 20 cm. It is used for scene building and obstacle avoidance problems for UGVs and UAVs [48,49].

2.7. Infrared Camera

Infrared cameras use 850 nm infrared light to illuminate objects and receive reflected images. A typical infrared camera indoor positioning system is a motion capture system [50], which uses an array of infrared cameras to track reflective marker points and calculate coordinate positions. A single camera has a detection range of about 10 m and can provide two-dimensional coordinates of reflective marker points in the field of view with sub-millimeter accuracy. The data provided by the motion capture system can be used as ground truth for algorithm verification. However, the system is large and time-consuming to install and calibrate and unusable when the reflective marker points are obscured.

3. Location Algorithms

There are many kinds of relative localization algorithms [51], but the most typical ones are those based on RF (Radio Frequency) communication and optical signal.

3.1. Positioning Algorithms Based on RF

RF-based communication technology can provide signal strength information [38], which is applied to devices with radio sensors [52]. RSS uses a model of the relationship between signal strength attenuation and distance to estimate the distance value between a tag and an anchor. The tag solves for its position using the distance value to each anchor and the position of each anchor. RSS is classically used in Bluetooth, Wi-Fi, and RFID-based positioning algorithms. The distance values between the tag and more than three anchors are required to calculate the planar coordinates, and more than four anchors are required for 3D coordinates. The localization accuracy is related to the ranging accuracy. The localization error of Bluetooth [32] and Wi-Fi [35] is usually at the meter level. Regarding UHF-RFID, by combining POA (phase of arrival) data [38], its localization error is at the centimeter level. The algorithm is computationally small and fast and can run on an embedded chip. However, this technique requires anchors with known deployment coordinate positions, and a large workload to correct the signal strength attenuation model. Furthermore, it is affected by environmental interference.

TOA (Time of Arrival)

Similar to RSS, TOA [53] calculates the distance value based on the time of flight of electromagnetic waves between devices and then solves the position coordinates using a distance-based localization algorithm. Suitable for UWB, the localization error is about 20 cm. The TOA has low computational complexity and is less affected by environmental interference. However, a tag needs to interrogate the anchors sequentially, which consumes some time.

AOA (Angle of Arrival)

AOA [54] obtains the angles at which the signal sent by the tag reaches anchors by using an array of antennas. We use these angles with the position of anchors to calculate the location of the tag. In Bluetooth and Wi-Fi systems, fingerprint maps are constructed to reduce errors to improve indoor positioning accuracy to the decimeter level [33,36]. The hardware structure and algorithm of the anchor for obtaining angle information are more complicated. It can only be used in known spaces and is highly influenced by environmental disturbances.

TDOA (Time Difference of Arrival)

TDOA [55] uses tags to send electromagnetic waves to anchors that have been time-synchronized. The anchors at different locations receive electromagnetic waves at different moments. The upper computer uses the time difference of these moments to calculate the tag position centrally. UWB can use this algorithm with a positioning error of about 20 cm. The positioning accuracy is limited by the time synchronization error of the anchors, as well as the environmental interference. The tag cannot calculate its own position and can only be obtained from the centralized calculation node.

3.2. Positioning Algorithms Based on Optical Signals

SLAM (Simultaneous Localization and Mapping)

SLAM [56] helps robots to accomplish map building and localization in unknown environments using sensor information. This approach can be used for robots loaded with lidar or RGB cameras to obtain relative position information. Lidar SLAM [57] has centimeter-level localization accuracy, and vision SLAM [47] has a localization error of less than 20 cm. This algorithm consumes a lot of computational resources and is affected by the environment (e.g., light, rain, fog, etc.).

Multi-Camera Target Identification and Location Algorithm

The multi-camera target identification and localization algorithm determines the three-dimensional location of the target by capturing the two-dimensional position with a minimum of two cameras. The motion capture system uses an infrared camera array to solve the coordinates of the placed reflective marker points with sub-millimeter error. This algorithm centralizes the data from fixed nodes and consumes large computational resources. It is highly influenced by the environment, and the system cannot be used when the marker points are obscured.

4. Typical Positioning System

According to the positioning mode, this paper divides the positioning system into an “anchor-tag” mechanism and a full distribution mechanism.

4.1. “Anchor-Tag” Mechanism

The mechanism has anchors with known positions pre-installed in the scene (whether the anchor moves or not). The tag initiates measurement communication with the anchor, and the position of the tag relative to the anchor is solved by an algorithm. Typical positioning systems using this mechanism are based on Bluetooth, Wi-Fi, RFID, UWB, infrared cameras, etc.

Bluetooth

Obreja and Vulpe [32] studied an indoor localization scheme based on Bluetooth beacon technology and an RSS fingerprinting method for indoor lightweight localization techniques. The scheme uses six Bluetooth beacons as anchors; more than 80 percent of the errors are within 1 m, and the rest are within 6 m. Wang et al. [33] designed a single-anchor positioning system based on angular information using an antenna array with direction and polarization information for positioning, with a median accuracy of 30 cm. Chen et al. [58] proposed an unsupervised indoor positioning system. The system combines data from iBeacons, Wi-Fi fingerprints and smart phone sensors to automatically establish a fingerprint database without any on-site survey. The average localization error is about 1.1 m in the steady state, and the maximum error is 2.77 m.

Wi-Fi

Rubina et al. [14] proposed a method to locate surviving devices using RSS of Wi-Fi. An aerial UAV carrying a Wi-Fi base station was used for emergency rescue to localize an area of 160,000 m

^{2}

with meter-level accuracy. Kotaru et al. [59] proposed a Wi-Fi-based indoor localization system for locating human objects in indoor environments, providing a median accuracy of 40 cm for tracking tags and smartphones with Wi-Fi modules. The system uses access points with three antennas to create a virtual sensor array. It provides a higher accuracy AOA algorithm and performs position state estimation by fusing RSS information from each access point. Carvalho et al. [60] used machine learning technology to evaluate the faults of an indoor positioning system, and then proposed a fault-tolerant indoor positioning system [61]. The system uses the RSS set of Wi-Fi as input, and the RNN (recurrent neural network) determines the position of an agent according to the set. The system can distinguish momentary failure and permanent failure by a fault-tolerant mechanism.

RFID

Zhang et al. [37] proposed a UAV system using RFID in order to provide an accurate attitude to an indoor UAV. This system uses several readers with known locations to read the POA and RSS information fed by three UHF tags set on the UAV. Based on this information, distance values are calculated, and the position of the tags in the global coordinate system is tracked with a positioning error of approximately 0.04 m.

Chen et al. [62] optimized the UWB measurement method to solve the high-frequency positioning problem of mobile robots. The positioning refresh interval in the “Anchor-Tag” mode only needs 4.167 ms, and the 3D positioning error of UGV is within 20 cm. To reduce the errors generated by UWB devices subjected to multipath effects and NLOS, Liu et al. [63] proposed an effective framework for an integrated INS (inertial navigation system) and UWB positioning system for autonomous indoor mobile robots with a positioning error of about 20 cm. Li et al. [10] achieved 80 Hz 3D positioning of 6 micro UAVs based on the fusion of UWB and IMU, with an average error of 16 cm.

Infrared Camera

Motion capture systems locate a moving reflective marker ball by a fixed infrared camera array [50,64]. The data results are used as ground truth with an accuracy in the sub-millimeter range.

4.2. Full Distribution Mechanism

In this mode, there is no limit to the anchors in the scene, and centralized calculation is not required. By accepting external information or active detection, the position of the agent relative to the map can be calculated, which can be called a complete distribution mode. Methods of measurement using this mode include UWB, lidar and RGB cameras.

Cao et al. [65] designed a fully distributed UWB relative localization scheme based on TDMA (time division multiple access) and a self-assembling network. It implements 12 nodes to construct a two-dimensional global map by relative localization. Under the condition of a 50 ms time slot, it takes about 30 time slots to complete one relative localization (positioning refresh interval 1.5 s). The positioning accuracy is about at the decimeter level under the condition that the points remain stationary.

Lidar

Lu et al. [57] proposed a lidar autonomous driving positioning framework based on learning in order to solve the problem of inaccurate manual modeling of autonomous driving positioning. It can directly process lidar point cloud data and accurately estimate vehicle position and direction, achieving centimeter-level positioning accuracy.

RGB Camera

Zhang et al. [47] aimed to tackle VIO’s vulnerability to poor light and featureless environments; thus a RGB camera was used to build a three-dimensional map matching algorithm based on conditional random field and VIO’s indoor positioning algorithm, achieving decimeter-level positioning accuracy.

5. Analysis of Relative Localization Technology Matching with Robot Swarm Applications

In an emergency task scenario, a robot swarm should have the characteristics of the micro-miniaturization of the platform, low power consumption/lightweight load and limited energy, etc. The swarm has hierarchical relationship in communication and management, and the space-time relationship between individuals changes rapidly, so it must have the ability of mutual perception and collision avoidance [66]. Several characteristics of robot swarm relative positioning technologies are obtained by analysis as follows:

Sensors with the Characteristics of Being Lightweight, Having Low Power Consumption, and Being Low-cost

The sensors for relative measurement are lightweight, have low power consumption, and have low cost [67]. These features make the sensors easy to mount on the robot and stable to operate. Carrying lighter weight and lower power consumption sensors can reduce the load and consumption of robots. The lower cost facilitates robot cluster scaling.
Fully Distributed Localization Mechanism with Robustness

The relative localization mechanism should be adapted to the dynamic topology between nodes [68]. The number of node scales increases or decreases with task changes, scene changes, and confrontation conditions. Group nodes can still be positioned relatively under changes in topological structure.
Obtaining Positioning Information in a Very Short Time

Relative localization, as the fundamental access control loop of navigation [69], enables robot movement to be completed following a plan. Swarms of drones acquire faster positioning information, enabling more responsive control and more demanding mission requirements.

In a crowded dynamic environment, three aspects need to be considered for the application of micro-robots in large groups. First, it is important to focus on the power consumption, sensing distance, weight, and cost of sensors. Second, the localization mechanism should be considered in terms of the localization mode and cooperation method. Third, it is important to pay attention to the measurement frequency and localization solving delay in the update frequency.

A single UWB node [62,70] weighs about 5 g [71] and has an operating voltage of 3.3 V and a current of 130 mA [41]. Each node costs tens of dollars. As regards cooperative positioning, the node measurement can be selected by the host computer and RF chip. The measurement frequency can reach 372 Hz [41], which can adapt to the motion loop of a 50 Hz control loop platform [72].

RGB cameras [47,50] weigh about 100 g and have an average power of 0.36 w [73]. Each camera costs about several hundred dollars and can provide services for the self-positioning of robots without the need to cooperate with other robots. Although the visible range is all detected, the range distance for building maps is small. Map construction requires datasets for training, a long pre-learning time, and the need to process environmental information. The more complex the external environment, the higher the algorithm delay.

Lidar [46] weighs nearly 1 kg, has an average power of 10 W [45], and costs several thousand to several tens of thousands of dollars individually. Similar to RGB cameras, robots can use point cloud information from lidar for self-localization. Although lidar can detect objects up to 200 m, the point cloud information is too sparse at long distances, and the sensing distance is much smaller than the detection distance. The measurement frequency is affected by the hardware scanning speed, as fast as 20 Hz, and is susceptible to smoke obscuration.

This entry is adapted from the peer-reviewed paper 10.3390/s22124424

© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.