2. Measurement System
Sensors are used 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
[12], 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
[13]. The angle accuracy of the obtained direction when using an antenna array is 8°
[14]. Bluetooth can be used to locate mobile devices with slow motion speed
[15].
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
[16]. 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
[17], and the direction error is less than 9°
[18].
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
[19]. The effective reading range of the UHF passive label is 10 m
[20][21][22]. 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
[21][22]. To improve the localization accuracy, Bernardini et al.
[23] 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
[24]. 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
[25]. It can be used for ranging and localization of indoor mobile devices and outdoor robots
[26][27].
2.5. Lidar
Lidar
[28] uses 905 nm or 1550 nm light to scan the environment and detect a distance of about 200 m
[29]. 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
[30].
2.6. RGB Camera
Similar to lidar, RGB cameras
[31] 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
[32][33].
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
[34], 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
[35], 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
[22], which is applied to devices with radio sensors
[36]. 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
[13] and Wi-Fi
[16] is usually at the meter level. Regarding UHF-RFID, by combining POA (phase of arrival) data
[22], 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.
Similar to RSS, TOA
[37] 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
[38] obtains the angles at which the signal sent by the tag reaches anchors by using an array of antennas. These angles are used 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
[14][18]. 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
[39] 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
[40] 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
[41] has centimeter-level localization accuracy, and vision SLAM
[31] 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.).
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
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.
Obreja and Vulpe
[13] 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.
[14] 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.
[42] 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.
Rubina et al.
[17] 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.
[43] 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.
[44] used machine learning technology to evaluate the faults of an indoor positioning system, and then proposed a fault-tolerant indoor positioning system
[45]. 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.
Zhang et al.
[21] 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.
[46] 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.
[47] 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.
Motion capture systems locate a moving reflective marker ball by a fixed infrared camera array
[34][48]. 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.
[49] 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.
Lu et al.
[41] 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.
Zhang et al.
[31] 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
[50]. 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
[51]. 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
[52]. 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
[53], 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
[46][54] weighs about 5 g
[55] and has an operating voltage of 3.3 V and a current of 130 mA
[25]. 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
[25], which can adapt to the motion loop of a 50 Hz control loop platform
[56].
RGB cameras
[31][34] weigh about 100 g and have an average power of 0.36 w
[57]. 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
[30] weighs nearly 1 kg, has an average power of 10 W
[29], 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.