[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Next Article in Journal
Distance Error Correction in Time-of-Flight Cameras Using Asynchronous Integration Time
Next Article in Special Issue
Perception in the Dark; Development of a ToF Visual Inertial Odometry System
Previous Article in Journal
A Flexible Strain Sensor Based on the Porous Structure of a Carbon Black/Carbon Nanotube Conducting Network for Human Motion Detection
Previous Article in Special Issue
High Definition 3D Map Creation Using GNSS/IMU/LiDAR Sensor Integration to Support Autonomous Vehicle Navigation
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Distributed Multi-Antenna Positioning for Automatic-Guided Vehicle

1
Department of Electronic Engineering, Tsinghua University, Beijing 100084, China
2
Luoyang Electronic Equipment Test Centre, Luoyang 471000, China
3
Beijing National Research Center for Information Science and Technology, Beijing 100084, China
*
Author to whom correspondence should be addressed.
Sensors 2020, 20(4), 1155; https://doi.org/10.3390/s20041155
Submission received: 4 January 2020 / Revised: 9 February 2020 / Accepted: 13 February 2020 / Published: 20 February 2020
(This article belongs to the Collection Positioning and Navigation)
Figure 1
<p>The flat structure of an automatic-guided vehicle (AGV) and its typical environment. The receiving antennas cannot be mounted at the highest point of the vehicle. The radio positioning signals are not only affected by the obstacles in the environment but also blocked by the carried cargoes.</p> ">
Figure 2
<p>An example of a signal-blocked environment of AGV. The AGV is carrying some cargo, and the receiving antennas are installed on the corners of its flat body.</p> ">
Figure 3
<p>The position of antenna <span class="html-italic">i</span> in frame <span class="html-italic">b</span>; c is the reference point on the AGV.</p> ">
Figure 4
<p>Flow chart of the two-step Levenberg–Marquardt (TSLM) algorithm.</p> ">
Figure 5
<p>Simulation scene. The blue triangles numbered from 1–6 represent the anchors, the purple stars numbered from 1–4 indicate the antennas mounted on the AGV, the red solid square indicates the center of the AGV (reference point), the red hollow cube in the center indicates the cargo on the AGV, the rectangle filled with blue indicates the AGV body, the rectangles with orange dashed lines indicate the walls on both sides of the road, and the green solid lines indicate the lines of sight (LOSs) from the antennas to their visible anchors.</p> ">
Figure 6
<p>The trajectory of the center and the attitude of the AGV in the dynamic test. The blue triangles represent the anchors, the red line indicates the trajectory of the center, the blue rectangle indicates the AGV body, and the red dashed lines indicate obstacles on both sides of the road.</p> ">
Figure 7
<p>The numbers of visible anchors vs. time.</p> ">
Figure 8
<p>Number of visible anchors of multiple antennas (top) and distributed multi-antenna horizontal dilution of precision (DMA-HDOP) (bottom).</p> ">
Figure 9
<p>Two-dimensional (2D) projection at (<b>a</b>) 84 s, and (<b>b</b>) 100 s. Blue triangles numbered from 1–6 indicate anchors, purple stars numbered from 1–4 indicate antennas mounted on the corner of the AGV, the red solid square indicates the center of the AGV, the red rectangle indicates the projection of the cargo on AGV, the rectangle filled with blue indicates the AGV body, the red dashed lines indicate the projections of the walls on both sides of the road, and green lines indicate the LOSs from the antennas to their visible anchors.</p> ">
Figure 10
<p>The Cramer–Rao lower bound (CRLB) of DMA positioning at each moment.</p> ">
Figure 11
<p>The 2D projection at the start point of the trajectory.</p> ">
Figure 12
<p>Root-mean-square errors (RMSEs) of Step 2 vs. initial yaw angle bias.</p> ">
Versions Notes

Abstract

:
Radio-based positioning systems are typically utilized to provide high-precision position information for automatic-guided vehicles (AGVs). However, the presence of obstacles in harsh environments, as well as carried cargoes on the AGV, will degrade the localization performance, since they block the propagation of radio signals. In this paper, a distributed multi-antenna positioning system is proposed, where multiple synchronous antennas are equipped on corners of an AGV to improve the availability and accuracy of positioning. An estimator based on the Levenberg–Marquardt algorithm is introduced to solve the nonlinear pseudo-range equations. To obtain the global optimal solutions, we propose a coarse estimator that utilizes the displacement knowledge of the antennas to provide a rough initial guess. Simulation results show a better availability of our system compared with the single antenna positioning system. Decimeter accuracy can be obtained under a Gaussian measurement noise with a standard deviation of 0.2 m. The results also demonstrate that the proposed algorithm can achieve positioning accuracy close to the theoretical Cramer–Rao lower bound. Furthermore, given prior information of the yaw angle, the same level of accuracy can be obtained by the proposed algorithm without the coarse estimation step.

1. Introduction

Automatic-guided vehicles (AGVs) play an important role in unmanned ports or warehouses. They can automatically and safely transport cargoes or materials to the expected destination. Since the 1980s, AGV became an indispensable part of the production logistics system. In order to realize the safe driving of AGVs and the accurate lifting of cargoes in unmanned environments, autonomous high-precision positioning and navigation of AGV are necessary.
In the early days, AGVs mainly used fixed path methods for navigation [1]. In these methods, positioning signs such as magnetic stripes or metal wires are embedded in paths, and the sensors on the AGV can then detect the signs and provide information to the controller for driving adjustment. Although this method is mature and it was widely used in early AGVs, it only works for a fixed path and can be easily affected by the magnetic and electric fields in the environment. With the increasing demand for flexibility and adaptability of the AGV navigation system, positioning methods free of path constraints are constantly being researched and promoted, including inertial, radio, laser, and visual positioning, among others [2]. The inertial navigation system (INS) can provide high-frequency velocity and attitude estimation by using inertial sensors installed on the vehicle. It gives an ephemeral precise positioning by dead reckoning, immune to external interference. However, it suffers significant accumulated errors in the long run. The laser positioning system uses laser scanning to obtain the location information of reflection signs to provide vehicle position. It has high precision, but it is susceptible to weather and needs a large number of reflective signs [2]. The visual positioning system provides localization services by processing images collected by visual sensors. It achieves high positioning accuracy in various scenes, albeit with a high cost and computational complexity. Due to the development of radio technology and data processing abilities of electronic devices, the radio positioning system became favored in recent years, among which the global navigation satellite system (GNSS) and ultra-wideband (UWB) system are particularly concerned.
GNSS is a wireless navigation system that provides global, all-weather, continuous, and real-time navigation and positioning by utilizing navigation satellites [3]. Centimeter-level accuracy can be achieved by carrier phase differencing technology, which can meet the positioning accuracy requirements of AGVs. However, GNSS signals are subject to blockage and multipath, which decrease the continuity and availability of the carrier phase measurements and further lower the precision, robustness, and availability of positioning [4,5]. Moreover, it is not suitable for indoor positioning due to significant signal loss [6,7].
Recently, we saw a trend of utilizing UWB as a navigation system. UWB radios have relative bandwidths larger than 20% or absolute bandwidths of more than 500 MHz [8,9]. UWB signals are particularly well suited for localization since they can provide accurate and reliable ranging measurements due to their fine time resolution and robustness in harsh environments [10]. Typically, centimeter-level accuracy can be obtained for UWB by using time-of-arrival (TOA) measurements [11,12]. Furthermore, the UWB positioning system can be configured for indoor applications [13,14]. With the development of UWB chips, UWB became a popular technology for regional navigation [15]. Similar to GNSS, the UWB navigation system also encounters the problem of accuracy and availability degradation caused by signal blockage [16,17].
Aiming at the problem of insufficient measurements caused by obstacles in the environment, researchers proposed a variety of solutions. Integrating radio navigation systems with other sensors such as INS [18,19], velocity sensor, Light Detection and Ranging (LiDAR) [20,21], or visual sensor [22] represents a solution. This fusion method is helpful to improve the availability but needs additional external devices, and the data fusion of different systems requires much more computation ability. In addition to the multi-sensor fusion method, the idea of cooperative localization is another solution. It solves the problem of insufficient information of a single node by sharing information among nodes [23,24]. Specifically, all users are nodes operating independently with unknown locations and asynchronous clocks. These users make measurements with both known location references and other unknown location nodes. The additional information gained from these measurements between pairs of unknown location nodes enhances the accuracy and robustness of the localization system [25]. Some studies showed that the cooperative technology can effectively improve the availability of the positioning system in harsh environments, and it is suitable for location service applications with a group of agent nodes [26,27]. However, it strongly depends on wireless communication networks, which requires stable operation of networks and reliable transmission of information.
In addition to all these difficulties mentioned above, another issue should be taken into account as shown in Figure 1. The red vehicle is an AGV, which has a flat structure. The cargoes are placed on the flat for transportation and there is no cab. Because of the restriction of the flat body, the receiving antennas cannot be mounted at the highest point of the vehicle. Thus, for the AGV, the radio positioning signals are not only affected by the obstacles in the environment but also blocked by the carried cargoes. The problem of insufficient measurements is even more serious in this case. Therefore, a method that can obtain as many measurements as possible and make full use of them is needed. Although more measurements will lead to an increase in computation, it is worth the improvement in availability, which is a prerequisite for the effective operation of the positioning system.
A multi-antenna method is our choice. Because of the spatial separation between antennas, more potential information can be provided for positioning from multiple antennas. Furthermore, redundant measurements by multiple antennas can improve the performance of positioning in terms of accuracy and robustness. Although the multi-antenna method was considered in many localization methods to improve localization [28,29,30,31], to the best of the authors’ knowledge, there are few studies on multi-antenna positioning systems in harsh environments. Some relevant studies typically only focused on multiple receivers. Some studies [32,33] improved the accuracy and reliability of positioning by using multiple low-cost receivers. These papers verified the accuracy improvement by utilizing spatially separated reception and data fusion, but did not discuss the problem of availability. Another study [33] set the position, attitude, velocity, angular rate of the center receiver, and clock bias of each receiver as unknown states and integrated the pseudo-range measurements from multiple global positioning system (GPS) receivers using an extended Kalman filter (EKF), which needs more measurements than single-receiver methods regardless of the availability. Multiple receivers were also used [34] to jointly track and estimate signal parameters to improve the reliability and robustness, but this study involved modification of the software and hardware of the tracking loop in the receivers.
Instead of multiple receivers, multiple distributed antennas with a synchronous clock are employed in this work. In our positioning system, fixed anchors periodically transmit positioning signals. Furthermore, there exist obstacles occasionally blocking the signals, such as buildings or containers on the roadside. The anchors can be automatically clock-synchronized and self-localized using a signal broadcast mechanism [35]. The distributed receiving antennas are mounted on the flat body of the AGV. The positions of these antennas are fixed and known with respect to a reference point on the vehicle. Due to the spatial differences, each antenna may encounter different blockages and, thus, have different subsets of visible anchors. Fusing the measurements of each antenna can improve the availability of the positioning system. Utilizing the position relationship between the receiving antennas and the reference point, the TOA measurements of each antenna can be expressed as a function of the reference position. In order to implement the transformation of the measurement representation, a rotation matrix from the body coordinate system (frame b) to the navigation coordinate system (frame n) is inevitably needed. Therefore, unlike the single antenna positioning method, in our distributed multi-antenna (DMA) method, not only the position and clock bias but also the attitude of AGV should be estimated, which forms a challenging nonlinear constrained optimization problem. The problem of finding the rotation matrix and the reference position was termed rigid body localization in some studies [36,37,38]. They localized a rigid body by placing a few sensors on the body and utilized the range measurements with respect to a few anchors to estimate the rotation matrix and the position [36]. A non-iterative estimator with two steps was also proposed [37]. The rotation matrix and position were coarsely estimated using sensor positions and then refined by estimating the corrections using Euler angle formulation. Another study [36] proposed two methods called constrained least squares (CLS) and simplified CLS based on linearizing the measurement model. In Reference [38], this problem of maximum likelihood (ML) formulation was addressed by using semidefinite relaxation to get a coarse estimate, before applying orthogonalization and refinement. Although these methods showed good performance in their circumstances, they are not suitable for our cases because they ignore the problem of insufficient measurements from a single sensor, and they simply assume that there is no clock bias, which is not practical in many real applications. If the rigid body localization methods are directly applied to our scene, the TOA measurements are treated as range measurements with large noise and the number of measurements is small, leading to low accuracy.
In this paper, we propose a DMA positioning algorithm based on the Levenberg–Marquardt (LM) algorithm with a coarse estimation step, which is introduced to provide a proper initial value to the iterative positioning algorithm. In the coarse estimation, the positions of the distributed antennas in frame n are jointly estimated and then used to coarsely estimate the reference position and the yaw angle according to the transformation relationship between frame b and frame n. Finally, the coarse estimates are applied to the iterative algorithm to get a refined positioning result. Thus, the algorithm is divided into two steps, and the positioning algorithm based on LM is hereinafter referred to as the two-step LM (TSLM) positioning algorithm. The Cramer–Rao lower bound (CRLB) of the positioning problem is derived as a benchmark to assess the performance of the proposed algorithm. The distributed multi-antenna horizontal dilution of precision (DMA-HDOP) model is also derived to analyze the positioning accuracy. Simulation results demonstrate that the positioning availability is significantly improved compared with the conventional single-antenna localization. Under a Gaussian measurement noise with a standard deviation of 0.2 m, the DMA method could achieve decimeter-level accuracy. Furthermore, in our simulation tests, the TSLM algorithm could provide positioning accuracy close to CRLB without requiring the initial yaw angle information. Simulation tests on the second step of the TSLM algorithm with different initial yaw angles verified that the iterative positioning algorithm in the second step is sensitive to the initial yaw angle. However, given prior information of the yaw angle, using only the second step can achieve similar results to TSLM.
The main contributions of this paper are summarized as follows:
1) A distributed multi-antenna method is proposed to improve the availability and accuracy of AGV positioning under the situation of signal blockage caused by environmental obstacles and carried cargoes.
2) A two-step LM algorithm is developed to optimally estimate both the position and the yaw angle, in which the initial value for the iterative algorithm in the second step is set by the coarse estimation from the first step.
The remainder of the article is organized as follows: Section 2 presents the model of the positioning system. The positioning algorithms are proposed in Section 3. Section 4 derives the CRLB of the position estimate problem and presents the DMA-HDOP model of the DMA positioning method. Section 5 gives the simulation results. Finally, Section 6 concludes the paper.

2. System Model

2.1. Notation

We employ the following notations throughout this work: the upper and lower case boldface denote matrices and vectors, respectively; symbols with a hat denote estimated values; the notation E [ · ] is the expectation operator; A T , A 1 , and trace ( A ) denote the transpose, the inverse, the trace of matrix A , respectively; · denotes the Euclidean norm; I is the identity matrix; card ( ) denotes the number of elements in set ; C ( n , k ) denotes the number of k-combinations of n elements; A n 1 × n 2 denotes the n 1 -by- n 2 matrix; a [ n 1 : n 2 ] denotes the n 1 -th to n 2 -th elements of vector a ; a [ n ] denotes the n -th element of vector a ; [ A ] n 1 , n 2 denotes the element at the n 1 -th row and n 2 -th column of matrix A .
Coordinate frames involved in this paper are the navigation frame and the body frame, denoted as n and -b, respectively. All the positions of anchors and the positioning results are expressed in frame n, which defines a certain point in the given area as its origin and the east, north, and upward directions as its x n , y n , and z n axes, respectively. The known positions of the distributed antennas with respect to a reference point on AGV are expressed in frame b. The origin of frame b is the reference point. x b , y b , and z b axes of frame b are defined as the front, right, and downward directions of the AGV body, respectively. The rotation matrix of transformation from frame b to frame n is represented by R b n .

2.2. Problem Formulation

Consider a system in which there are M anchors with known position and known clock bias, an AGV with unknown position, and N antennas with unknown positions and the same unknown clock bias. Let N be the set of antennas with card ( N ) = N , be the set of anchors with card ( ) = M , and i be the set of visible anchors of antenna i with card ( i ) = M i , i . Position states of the reference point c on the AGV, antenna i N , and anchor j in frame n are indicated by p c = ( x c , y c , z c ) , p i = ( x i , y i , z i ) , and p ( j ) = ( x ( j ) , y ( j ) , z ( j ) ) , respectively. A typical signal blocked environment of the AGV using a radio positioning system is presented in Figure 2. The AGV is carrying some cargo, and the receiving antennas are installed on its flat body.
In unmanned transportation, the AGV is typically assumed to work in a flat and specific area without changing the height, pitch angle, and rolling angle. Therefore, the height, rolling angle, and pitch angle are regarded as known constants, and the problem can be considered as positioning in a two-dimensional (2D) plane. In addition to the horizontal coordinates of the reference point ( x c , y c ) , the clock bias δ t between the receiver and the anchor should also be estimated. Moreover, the yaw angle ψ is needed for the position vector transformation from frame b to frame n.
Three-dimensional (3D) AGV positioning is also needed in some application scenarios such as transportation on rough roads, open-air mines, etc., in which AGVs are moving with varying height and/or rolling and pitch angle. For the height estimate, a good geometry of anchor height should be additionally guaranteed. The height can then be solved by adding an extra unknown with an increase in the number of visible anchors required. As for the rolling and pitch angles, it is not only a matter of increasing the unknowns and the number of visible anchors required. The coupling between multiple attitude angles also brings more severe nonlinearity, which may require more sophisticated optimization algorithms, which will be investigated in future work. Fortunately, unlike the yaw angle, which is not easy to be measured directly by sensors, the rolling and pitch angles are easy to be accurately obtained using accelerometers and other sensors; thus, it is easy to extend the proposed method to 3D cases.
Based on the previous discussion, in this work, we focus on the 2D problem, and the parameters to be estimated are the reference position ( x c , y c ) , receiver clock bias δ t , and yaw angle ψ . The unknown state vector x can be written as
x = [ x c , y c , δ t , ψ ] T .

2.3. Measurement Model

In a broadcast positioning system, the receiver receives the signals transmitted from the anchors and measures the time of arrival with its local clock, which is not synchronized with the anchors. Assuming that all the anchors are synchronized to a system clock, the TOA measurement of the receiving antenna i from anchor j can be formulated as
ρ i j = p ( j ) p i + δ t i + ε i j ,
where δ t i is the receiver clock bias expressed by the equivalent signal propagation distance, and ε i j is the TOA measurement noise. Note that the measurement noises come from various sources, including the geometry of anchors, multipath effect, clock inaccuracies, etc. They are random variables, and it is very difficult to get their exact probability distribution. Without loss of generality, all the measurements noises are assumed to be independent and identically distributed Gaussian white noise, i.e., ε i j N ( 0 , σ 2 ) .
For our distributed multi-antenna positioning system, the position relationship between the antennas and the reference point is shown in Figure 3. For the distributed antennas, their positions relative to the reference point c are known and fixed in frame b, whereas the orientation of frame b varies with the motion of the AGV. The position of antenna i in frame n can be calculated as
p i = p c + R b n l c i b ,   i N ,
where l c i b is the vector from the reference point c to antenna i expressed in frame b, and R b n is the rotation matrix from frame b to frame n [18].
R b n = [ sin ψ cos θ cos ψ cos ϕ + sin ψ sin θ sin ϕ cos ψ sin ϕ + sin ψ sin θ cos ϕ cos ψ cos θ sin ψ cos ϕ + cos ψ sin θ sin ϕ sin ψ sin ϕ + cos ψ sin θ cos ϕ sin θ cos θ sin ϕ cos θ cos ϕ ] ,
where the rolling angle ϕ , pitch angle θ , and yaw angle ψ are defined as in Reference [18]. R b n is a function of yaw angle ψ in this 2D positioning case.
Substituting the expression of R b n into Equation (3), the position of antenna i is a function of the reference position ( x c , y c ) and the yaw angle ψ , as given by
p i = f i ( x c , y c , ψ ) .
With the same timing source, all antennas have the same clock bias δ t . Substituting Equation (5) into Equation (2), the TOA measurement ρ i j of the j-th anchor in the subset of visible anchors i of antenna i is
ρ i j = p ( j ) f i ( x c , y c , ψ ) + δ t + ε i j ,   i N ,   j i .
The unknowns in Equation (6) are x c , y c ,   δ t , and ψ . Unlike the single-antenna positioning equation of Equation (2), the yaw angle ψ is added.
For convenience, Equation (6) is rewritten into matrix form,
z = h ( x ) ,
where h ( x ) is the observation function. The observation vector z consists of the TOA measurements of all N antennas given by Equation (6). The total number of measurements is i = 1 N M i . For antenna i, the TOA measurement ρ i is
ρ i = [ ρ i 1 ρ i 2 ρ i M i ] T .
h ( x ) consists of the TOA measurement function of all N antennas. For antenna i, the TOA measurement function h i ( x ) is
h i ( x ) = [ h i 1 ( x ) h i 2 ( x ) h i M i ( x ) ] T ,
where h i j ( x ) is expressed as the right side of Equation (6).
The aim of the localization problem in this paper is to estimate the position, orientation, and clock bias parameters for an AGV. Utilizing the measurements given by Equation (7), the positioning algorithm is proposed in the next section.

3. Positioning Algorithm

To estimate the unknowns in a set of equations, the number of independent equations must be greater than or equal to the number of unknowns in the system. Therefore, the corresponding requirement is that the total number of visible anchors for all the distributed antennas must be greater than or equal to the dimension of x in Equation (1). In addition, to estimate the yaw angle, there should be more than two antennas, where each observes at least one anchor. Let X = { M i > 0 , i N } . If
i = 1 N M i 4   and   card ( X ) 2 ,
the unknown parameters in x can be solved. We note that, for the positioning case with a single antenna, the number of visible anchors should be at least three to determine the two-axis position and the clock bias terms. The condition in Equation (10) shows that this requirement is relaxed in the multiple-antenna case, i.e., the number of visible anchors for each antenna can be less than three. As long as it is satisfied that the total number of visible anchors is greater than four, and no fewer than two antennas can see one or more anchors, the position of the target can be obtained. This greatly improves the availability of the system in practice.
According to the above models, the problem of AGV positioning is to find an optimal estimate x ^ with the minimum variance. The cost function is
J ( x ) = i = 1 N j = 1 M i ( ρ i j p ( j ) f i ( x c , y c , ψ ) δ t ) 2 .
Note that, because the TOA measurement noise of each antenna is assumed to be independent and identically distributed, the weights used to represent the contributions of the measurements are then chosen to be in unity and, thus, are omitted in the cost function. The parameters are estimated by solving the following minimization problem:
x ^ = arg min x   J ( x ) .
The optimization problem in Equation (12) can be converted to a nonlinear least squares problem and solved by an iterative method such as the Newton iterative method [39].
However, the parameters to be estimated in this problem show high nonlinearities in the measurement equations. Therefore, to avoid a local minimum solution of the optimization problem, a reasonably good starting point is needed. For the time parameter, it is a linear item in the measurement model which can be set empirically or to zero for simplicity. For the space parameters, the initial position can be set according to the region formed by the anchors, e.g., the center of the region. In contrast, the yaw angle, which is expressed as a trigonometric function in the equations, has the strongest nonlinearity among all these parameters, and its initial value has great influence on the convergence of the optimization problem. This impact on convergence is demonstrated later in the simulations in Section 5.2. If there are some other sensors such as an INS that can provide the attitude information of the body, the iterative positioning algorithm can be applied directly. However, more generally, we have no prior information about the yaw angle, and the AGV may start at the same location but with completely different yaw angles; thus, its initial value may be a randomly guessed value from π to π rad. Therefore, some measures are needed to narrow the initial attitude guess within a proper accuracy to guarantee convergence to the global optimum.
Toward that end, we employ a coarse estimation process to the algorithm. In this process, the antenna positions are jointly estimated as intermediate variables with the initial values of space and time parameters as described in the last paragraph, which avoids randomly guessing the initial yaw angle. Moreover, the initial reference position ( x c | 0 , y c | 0 ) and the yaw angle ψ c | 0 are then calculated according to the transformation relationship of antenna positions between frame b and frame n. Finally, the coarse estimates of space, time, and attitude serve as initial values in the iterative positioning algorithm. Consequently, a refined estimate is obtained. With the coarse estimation process, the DMA positioning algorithm based on the LM algorithm can be divided into two steps, namely, the TSLM algorithm, as shown in Figure 4, which is presented in detail in the upcoming subsections.

3.1. Step 1: Coarse Estimation

In Step 1, coarsely estimated parameters are obtained by firstly estimating antenna positions and then determining the reference position and the rotation matrix utilizing the relationship between frame n and frame b.

3.1.1. Estimate Antenna Positions

According to the TOA measurements expressed in Equation (2), the position of antenna i or p i can be estimated if there are sufficient independent measurements between antenna i and its visible anchors i . As mentioned before, due to the obstacles both in the environment and on the AGV, the number of TOA measurements of a single antenna may not be enough for positioning. Thus, we adopt the idea of collaborative positioning in Reference [40], where a group of receivers with unknown locations and asynchronous clocks were localized by jointly using the TOA measurements of all these receivers and the distance measurements between them. What distinguishes our work from the existing collaborative localization system is that the distance measurements between antennas are calculated according to their known positions in frame b and the antennas share a synchronous clock. The parameters to be estimated are positions of the antennas and receiver clock bias δ t . The unknown state vector y can be written as
y = [ x 1 y 1 x 2 y 2 x N y N δ t ] T .
We can rewrite the TOA measurement ρ i j of the j-th anchor in the subset of visible anchors i of antenna i as
ρ i j = p ( j ) p i + δ t + ε i j ,   j i ,
where ε i j N ( 0 , σ 2 ) .
The distance measurement between antenna i and antenna k can be expressed as
r ^ i k = p ^ k p ^ i .
The true distance is calculated by
r i k = l c k b l c i b ,
with the known positions of the distributed antennas in frame b l c i b , i N .
Although r i k and r k i are expressed as two measurements, they should be counted as one. For N antennas, there are C ( N , 2 ) independent distance measurements. Let K i be the set of antennas having effective distance measurements with antenna i, card ( K i ) = K i , K i N .
If the sum of the number of the TOA measurements and distance measurements is greater than or equal to the dimension of y , y can be solved. Thus, the requirement is
i = 1 N M i + C ( N , 2 ) 2 N + 1 ,
which can be easily met by reasonably deploying anchors, especially at the starting point of the vehicle. For example, there are four antennas mounted on the AGV and, thus, six distance measurements. According to Equation (17), the number of TOA measurements should be no less than three.
Jointly utilizing the TOA measurements and the distance measurements, an optimal estimate y ^ can be obtained by
y ^ = arg min y [ i = 1 N j = 1 M i υ i j ρ ( ρ i j p ( j ) p ^ i δ t ) 2 + i = 1 N k = 1 K i υ i k r ( r i k p ^ k p ^ i ) 2 ] .
where υ i j ρ and υ i k r are the weights for the TOA measurements and the distance measurements, respectively. According to the assumptions for TOA measurement noises, υ i j ρ can be chosen as υ i j ρ = σ 2 . The distance measurements should have heavier weights due to their high accuracy. Here, we set υ i k r = α σ 2 , where α is a factor greater than 1.
By linearizing the measurement equations by Taylor expanding and keeping the first-order terms, we have
δ q = K δ y ,
where δ y = y y ^ .
K = [ K ρ K r ] ,   δ q = [ δ q ρ δ q r ] .
The parameters related to the TOA measurements are denoted with subscript ρ .
K ρ = [ K ρ , 1 1 K ρ , 2 1 K ρ , N 1 ] ,   δ q ρ = [ δ q ρ , 1 δ q ρ , 2 δ q ρ , N ] ,
where
K ρ , i = [ u i 1 u i 2 u i M i ] ,   δ q ρ , i = [ Δ ρ i 1 Δ ρ i 2 Δ ρ i M i ] ,
where Δ ρ i j = ρ i j p ( j ) p ^ i δ t ^ , and
u i j [ x ( j ) x i d i j , y ( j ) y i d i j ] ,
where d i j = p ( j ) f i ( x c , y c , ψ ) .
The parameters related to the distance measurements are denoted with subscript r
K r = [ K r , 1 K r , 2 K r , N ] ,   δ q r = [ δ q r , 1 δ q r , 2 δ q r , N ] ,
where
K r , i = k - th row [ 0 1 × 2 i 1 v i k 0 1 × 2 i n d e x i 1 v i k 0 1 × 2 N i n d e x 0 ] ,   δ q r , i = [ Δ r i 1 Δ r i 2 Δ r i K i ] ,
where index denotes the index of the k-th element of set K i in set N and is supposed to be greater than i; Δ r i k = r i k p ^ k p ^ i , and
v i k [ x k x i r i k , y k y i r i k ] ,   k K i .
Thus, the linear least square form of the cost function is
J ( δ y ) = ( δ q K δ y ) T W ( δ q K δ y ) ,
where W is the weighting matrix.
W = [ σ 2 I ρ α σ 2 I r ] ,
where I ρ and I r are i = 1 N M i -order and C ( N , 2 ) -order identity matrices, respectively. The solution to estimate δ y is given by
δ y ^ = arg min δ y   J ( δ y ) = ( K T W K ) 1 K T W δ q .
The estimate of y can then be obtained by using the iterative algorithm. Consequently, the estimated ( x ^ i , y ^ i ) and δ t ^ are obtained and utilized in the next steps.

3.1.2. Coarsely Estimate Reference Position and Yaw Angle

In this subsection, we impose Equation (3) to determine the rotation matrix and the reference position, which is a typical problem in pattern analysis [37,41,42].
For our 2D problem, we denote the 2D positions of antenna i in frame b and frame n as c i b and s i , respectively, where c i b = l c i b [ 1 : 2 ] and s i = [ x i y i ] T . We can denote the 2D position of the reference point in frame n as d c = [ x c y c ] T and the rotation matrix between the two frames as
P = [ sin ψ cos ψ cos ψ sin ψ ] .
Then, Equation (3) can be rewritten as
s i = d c + P c c i b .
We construct the cost function as
J ( d c , P ) = i = 1 N s i d c P c c i b 2 .
We assume that each estimated antenna position has a similar contribution to the cost function, and the weights are then chosen to be in unity and are omitted in the cost function. The problem can then be formulated as a least squares minimization problem,
arg min d c , P   J = arg min d c , P i = 1 N s i d c P c c i b 2 , s . t .   P T P = I ,   det ( P ) = 1 .
We can utilize the method introduced in Reference [37],
d c = s ¯ P c ¯ ,
where s ¯ = 1 N i = 1 N s i , c ¯ = 1 N i = 1 N c c i b .
The minimization problem in Equation (33) can then be equivalent to the following [37]:
arg max P trace ( P i = 1 N c ˜ c i b s ˜ i T ) ,
where s ˜ i = s i s ¯ , c ˜ c i b = c c i b c ¯ .
Let
U Σ V T = SVD ( i = 1 N c ˜ c i b s ˜ i T ) .
By referring to the method based on singular value decomposition (SVD) in Reference [37],
P = V [ 1 0 0 det ( V U T ) T ] U T .
Then,
ψ = arctan ( [ P ] 1 , 1 [ P ] 1 , 2 ) .
Upon substituting P into Equation (34), d c can be solved.
At this point, the coarsely estimated reference position and the yaw angle are all obtained. Although there are some errors in the coarse estimates due to the intermediate transformation, they are not far from the optimum. Simulations validated that their accuracy is sufficient to initiate the iteration in Step 2 for producing a refined solution achieving CRLB.

3.2. Step 2: Refinement

To get the refined solutions, the coarse estimates denoted as ( x c | 0 , y c | 0 ) , δ t 0 , and ψ 0 are applied to Equation (12).
Firstly, the model of Equation (7) is linearized. Let x ^ be the estimated values; then, the first-order Taylor expansion of h ( x ) at x ^ is
h ( x ) = h ( x ^ ) + h x | x ^ ( x x ^ ) + o ( x x ^ ) ,
where o ( x x ^ ) is the high-order residual, which is ignored in the following text.
Let δ z = h ( x ) h ( x ^ ) , δ x = x x ^ , and H = h x | x ^ ; then, we have
δ z = H δ x .
Define
w i j h i j ( x ) ψ ,
and we have
H = [ H 1 H 2 H N ] ,   δ z = [ δ z 1 δ z 2 δ z N ] ,
where
H i = [ u i 1 u i 2 u i M i 1 1 1 w i 1 w i 2 w i M i ] ,   δ z i = [ ρ i 1 ρ ^ i 1 ρ i 2 ρ ^ i 2 ρ i M i ρ ^ i M i ] ,
in which, ρ ^ i j = h i j ( x ^ ) .
Thus, the linear least square form of Equation (11) is
J ( δ x ) = ( δ z H δ x ) T ( δ z H δ x ) .
The solution to estimate δ x is given by
δ x ^ = arg min δ x   J ( δ x ) = ( H T H ) 1 H T δ z .
The estimate of x can then be obtained using the iterative algorithm.
During iteration, matrix H in Equation (45) must be full rank, or the condition number of matrix Q = H T H cannot be too high to ensure convergence of the algorithm. To this end, we refer to the LM algorithm. The LM algorithm is a trust region method that improves the condition number of matrix Q by increasing coefficient matrix damping [43].
In the LM algorithm, a positive damping coefficient μ is added to the matrix Q , that is,
Q = H T H + μ I .
Q is used to calculate the increment of the unknown parameters. It can be seen that, if μ = 0 , it is the same as Q . The damping coefficient should be adjusted after each iteration. Since μ is positive, the matrix Q is always positive definite. In the iterative process, an error index is obtained by comparing the results of the current and the last iteration, which determines how to further update the damping coefficient. For a given μ , the commonly used adjustment strategy is as follows: if the residual result can reduce the error index, continue to reduce μ ; otherwise, increase it. The details of the iterative positioning algorithm are shown in Algorithm 1.
Algorithm 1. Iterative positioning algorithm in Step 2
Input: TOA measurements ρi, i N ; anchor positions p ( j ) , j i ,   i ; initial unknowns x 0   =   [ x c | 0 ,   y c | 0 ,   y c | 0 ,   δ t 0 ,   ψ 0 ] T ; maximum iterative number iter; convergence threshold thr > 0; known height h, rolling angle φ, pitch angle θ and the vectors from the antenna i to reference point c expressed in frame b l c i b ,   i N ; damping coefficient μ > 0; adjustment coefficient λ > 1.
Iteration:
  for q = 1: iter
    Calculate the position of each antenna:
     p ^ i = f i ( x c | q 1 ,   y c | q 1 ,   ψ q 1 ) ,   i N .
    Calculate residual: δ ρ i j = ρ i j p ( j ) p ^ i δ t q 1 ,   i N ,   , j i ,   i .
    Calculate uij and wij according to (23) and (41), respectively.
    Form H and δz according to (42).
    Calculate Q according to (46).
    Calculate unknown incremental: δ x q   = Q 1 H T δ z .
    Update unknown estimate: x q = x q 1 + δ x q .
     if ‖δxq‖ < thr
      exit;
     else if ‖δxq‖ < ‖δxq−1
       μ = μ λ ;
      else
      μ = μλ.
      end if
     end if
   end for
Output:xq

3.3. Computational Complexity

We estimate the computational complexity of the proposed positioning algorithm in this subsection. The complexity is shown in big O expressions in terms of the number of anchors M, the number of antennas N, and the position dimension 2.
To investigate the worst case, it is assumed that all N antennas can each receive all M anchor signals, although this situation is unlikely to occur due to the obstacles. Step 1 has M N + C ( N , 2 ) measurements and 2 N + 1 unknown states. In each iteration of the procedure to estimate the antennas positions, the complexities to calculate δ q , K , and ( K T W K ) 1 are O ( M N + C ( N , 2 ) ) , O ( ( 2 N + 1 ) ( M N + C ( N , 2 ) ) ) , and O ( ( 2 N + 1 ) ( M N + C ( N , 2 ) ) 2 ) flops, respectively. Moreover, the procedure to obtain the coarse estimate takes O ( 2 3 ) flops for an SVD. Step 2 has M N measurements and four unknown states. In each iteration of the procedure to estimate the refined solutions, the complexities to calculate δ z , H , and Q 1 are O ( M N ) , O ( 4 M N ) , and O ( 4 ( M N ) 2 ) flops, respectively.
The involved operations are matrix inversion, SVD, and other ordinary addition and multiplication steps. Although the algorithm is implemented on a personal computer (PC) for our simulation tests in Section 5, it is expected that the proposed method can be realized with reasonable computational cost in embedded systems commonly adopted by AGVs.

4. Performance Metrics

In this section, availability and accuracy are referred to as the performance metrics for the issue introduced above. The availability is the time percentage through which the positioning service is available, taking into consideration the needed accuracy and integrity [13]. In this paper, it is simplified to the solvability of the positioning parameter estimation, which depends on whether the number of effective independent measurements is greater than the minimum number of measurements required and the geometry of the visible anchors. In the DMA method, the availability is expressed as the ratio of time satisfying Equation (10) to the total time. As for the accuracy, CRLB and the dilution of precision (DOP) are usually used as a performance measure. Although there are mature theoretical models of CRLB and DOP for conventional single-antenna positioning, we need to specifically derive the models for the DMA method.

4.1. CRLB

To evaluate the estimator, we derive the CRLB for the DMA method, which is the lower bound of the error variance of the unbiased estimator. The error variance of x [ l ] is as follows [44]:
var ( x ^ [ l ] ) C R L B ( x ^ [ l ] ) = [ FIM 1 ( x ) ] l , l ,
where FIM is the Fisher information matrix.
The entries of the Fisher information matrix are
[ FIM ( x ) ] l 1 , l 2 = E [ 2 ln p ( z ; x ) x [ l 1 ] x [ l 2 ] ] ,
where p ( z ; x ) is the likelihood function.
We can define g n ( x ) as the n-th residual of Equation (7), where n = 1 , 2 , , i = 1 N M i . Thus, g n ( x ) N ( 0 , σ 2 ) . The probability density function of each TOA measurement z [ n ] can be expressed as
p ( z [ n ] ; x ) = 1 2 π σ 2 exp ( 1 2 σ 2 g n ( x ) 2 ) .
Each measurement is measured independently; thus,
p ( z ; x ) = n = 1 L p ( z [ n ] ; x ) = 1 ( 2 π σ 2 ) L 2 exp ( 1 2 σ 2 n = 1 L ( g n ( x ) ) 2 ) ,
where L = i = 1 N M i .
Therefore, the Fisher information matrix FIM is
FIM = E [ 2 ln p ( z ; x ) x x Τ ] = 1 σ 2 n = 1 L ( g n ( x ) x ) T g n ( x ) x = 1 σ 2 H T H ,
where H is defined in Equation (42).
Consequently, the diagonal element of FIM 1 is the minimum variance that can be achieved theoretically in unbiased estimation for the DMA positioning method. To simplify and save space, the noise of each measurement is set to be independent and identically distributed. If the signal transmitted from an anchor or received by an antenna is interfered, it can be considered that the corresponding noise increases, resulting in a decrease in precision. Furthermore, the multipath has a complicated effect on TOA measurements. With respect to CRLB, the multipath equivalently increases the measurement noise, and then reduces the positioning accuracy. As there is a certain amount of work in multipath modeling, it will be further studied in future work.
Note that, in Equation (51), FIM is determined by H with the same measurement noise. Moreover, H is affected by the relative position between antennas and their visible anchors. Thus, the position and quantity of antennas will affect positioning accuracy. However, we mainly focus on providing a solution for AGV positioning with severe blockages in this work. The quantitative influence of antenna configuration and the criteria of antenna position and quantity configuration will be studied in future work.
Based on the theoretical CRLB, the positioning performance of the proposed method is tested using a simulation in Section 5.

4.2. DMA-HDOP

In this subsection, DOP is introduced to analyze the positioning accuracy. Considering the measurement noises ε and adding the estimate error ε x caused by ε , Equation (40) can be written as follows [45]:
δ z = H ( δ x + ε x ) + ε .
Then,
δ x + ε x = ( H T H ) 1 H T δ z ( H T H ) 1 H T ε .
According to Equation (45), we have
ε x = ( H T H ) 1 H T ε .
The covariance matrix of positioning error is
cov ( ε x ) = E [ ε x ε x T ] = E [ ( H T H ) 1 H T ε ( ( H T H ) 1 H T ε ) T ] = ( H T H ) 1 cov ( ε )
According to the discussion of the TOA measurements noise in Section 2.3, the covariance matrix of ε is cov ( ε ) = σ 2 I . Thus,
cov ( ε x ) = ( H T H ) 1 σ 2 .
This can be denoted as
G = ( H T H ) 1 = [ g 11 g 12 g 13 g 14 g 21 g 22 g 23 g 24 g 31 g 32 g 33 g 34 g 41 g 42 g 43 g 44 ] .
The diagonal elements of G are the variance of state estimation errors, while the non-diagonal elements represent the correlation between these states. G indicates the magnification of the measurement error. With the same measurement error, a greater G results in a lower positioning accuracy. The DMA-HDOP can be expressed as
DMA - HDOP = g 11 + g 22 .
In Section 5, the positioning accuracy is analyzed based on the DMA-HDOP model.

5. Simulation Results

To analyze the performance of the proposed method, several tests were conducted based on one simulation scene. As shown in Figure 5, we set up a scene with six anchors, an AGV, and two wall-like obstacles along both sides in the environment. There is some cargo on the flat of the AGV. Its length and width are smaller than that of the flat, which means that its dimensions are not outside the AGV. Both the walls and the cargo on board can block the positioning signals. Four strictly synchronized receiving antennas are mounted on the corners of the AGV. We set the center of the AGV as the reference point.
For this scene, M = 6 , N = 4 . The height of both walls was 10 m, the width of the road between the walls was 8 m, and the coordinates of four antennas in frame b l c i b were (4, 2, 0) m, (4, −2, 0) m, (−4, −2, 0) m and (−4, 2, 0) m, respectively. The coordinates of the six anchors in frame n are presented in Table 1. The length, width, and height of the cargo on the vehicle were 7 m, 3 m, and 6 m, respectively. We ignored the multipath effect here and the TOA measurement noise was considered as independent zero-mean Gaussian white noise with a standard deviation of σ = 0.2   m . The clock bias between the receiver and the anchors was 149.90 m. The visible anchor set of each antenna and the corresponding TOA measurements from each antenna were then generated at a 1-Hz update rate.
Our simulation was carried out in MATLAB R2017a on a PC with an Intel(R) core(TM) i7-6500U central processing unit (CPU) at 2.5 GHz. By using the simulated measurements, we examine the theoretical capability of the proposed method in terms of availability and accuracy in Section 5.1. In Section 5.2, the performance of the TSLM algorithm and the influence of the initial value on the iterative positioning algorithm are tested.

5.1. Theoretical Capability of DMA Method

Based on the above configuration, we carried out a dynamic simulation test to assess the theoretical capability of the DMA method. The trajectory of the center and the attitude of the AGV were plotted in a 2D projection, as shown in Figure 6. The vehicle moved along the road from west to east with varying yaw angle and north velocity. The vehicle started from (−4.75, 4.53, 2.4) m with an initial attitude angle of (0, 0, 1.47) rad. During the movement, the height, rolling angle, and pitch angle of the vehicle remained unchanged. The duration of the movement was 180 s, which was divided into 11 segments according to different motion states. With different position and attitude of the AGV, each moment of simulation had a different geometric distribution of the anchors and actually represented many different situations. The east velocity v E , north velocity v N , yaw angle rate ω , and duration T of each segment are shown in Table 2. Utilizing the above scene and parameters, the visible anchor set of each antenna and the corresponding TOA measurements from each antenna of every moment were generated.

5.1.1. Positioning Availability

As mentioned in Section 4, we analyzed the availability by the ratio of time satisfying Equation (10) to the total time. Due to the movement of the vehicle, the numbers of visible anchors of each antenna changed during the test, as shown in Figure 7.
In Figure 7, the minimum numbers of visible anchors required for the single-antenna method and DMA positioning method are also plotted as the green dotted line and blue dotted line, respectively. The lines denoting the visible anchor numbers of antenna 2 and antenna 3 were always below the green dotted line, while antenna 1 and antenna 4 had more than three visible anchors at some moments. That is to say, single-antenna positioning was not available during parts of this test. On the other hand, the line of the total number of visible anchors was always above the blue dotted line. This indicates a possible positioning for the AGV if all measurements were used. Furthermore, there were always more than two antennas with one or more visible anchors, indicating that the yaw angle could be determined. Therefore, the condition in Equation (10) was satisfied throughout the test. We combined the numbers of visible anchors of antennas 1 and 4, and calculated the proportion of time when the number of visible anchors exceeded three (the green dotted line in Figure 7). The result was 70.6%, which means that the single-antenna method was only available during 70.6% of the entire period. With respect to the DMA method, the availability increased to 100% because the total number of visible anchors was above four (the blue dotted line in Figure 7) throughout the simulation period. This verifies that, with obstacles both in the environment and on the AGV, the proposed DMA method significantly improved the positioning availability in this simulation.

5.1.2. Positioning Accuracy

In this section, we analyze the positioning accuracy using DMA-HDOP and the theoretical CRLB derived in Section 4.
Based on the above scene and parameter configuration, the DMA-HDOP was calculated according to Equation (58), as shown in Figure 8. The total number of visible anchors is also shown for comparison. It can be seen from Figure 8 that the change in DMA-HDOP value was consistent with that of the number of visible anchors. A greater number of visible anchors led to a smaller DMA-HDOP value; thus, with the same measurement error, we obtained a smaller positioning error. Note that the number of visible anchors did not change between 74 s and 114 s, while the DMA-HDOP value did. This is because, during this period, the geometry of visible anchors changed when the AGV moved. Taking 84 s and 100 s as examples, as shown in Figure 9, although the numbers of visible anchors were the same, the geometric distribution was more uniform at 84 s due to the reception by the distributed multi-antenna.
Next, the simulated measurements were used to calculate the theoretical CRLB according to Equation (47). As shown in Figure 10, the CRLB of DMA positioning was also consistent with the numbers of visible anchors at each moment. In addition, in line with the analysis of Figure 9, the error in the north direction was larger between 90 s and 114 s. Overall, according to CRLB, with the standard deviation of the TOA measurement noise as σ = 0.2   m , the DMA method could theoretically achieve decimeter-level accuracy.

5.2. Performance of TSLM Algorithm

In this subsection, we conducted a static test at the start point of the trajectory in Figure 7 to test the performance of TSLM algorithm and the influence of the initial yaw angle on the iterative algorithm. In this test, the true coordinates of the vehicle were (−4.75, 4.53, 2.4) m with the true attitude angles as (0, 0, 1.47) rad. The 2D projection is shown in Figure 11, with the same icons and symbols as those in Figure 9.
Because of the blockage by the obstacles both in the environment and on the AGV, the numbers of signals received by the antennas on the vehicle were two, two, one, and one. None of the antennas had more than three visible anchors; thus, none of them could complete positioning on their own. However, the total number of visible anchors was greater than four and all four antennas had their visible anchor. Equation (10) was satisfied; therefore, the proposed positioning algorithm could be applied. Furthermore, the total number of visible anchors satisfied Equation (17); thus, the coarse estimation process could be applied as well.
To compare its positioning performance with CRLB, the positioning errors were calculated by comparing the simulation results with the true values of the simulation setting. A Monte Carlo simulation over 1000 tests was implemented to obtain the root-mean-square error (RMSE). For each parameter ξ , the RMSE can be calculated by
RMSE = i = 1 N test ( ξ ξ ^ i ) 2 N test ,
where ξ ^ i is the estimation of ξ in test i, N test is the number of Monte Carlo simulation tests, and N test = 1000 in this simulation.
In order to evaluate the impact of initial yaw angle and validate the necessity and effectiveness of Step 1 in the proposed algorithm, we firstly imported the simulated measurements directly to Step 2, i.e., the iterative positioning algorithm. For Step 2, δ t 0 was set to 0, and ( x c | 0 , y c | 0 ) was set as the center of the range formed by the anchors. With the initial yaw angle bias varying from −π rad to π rad, the positioning results were calculated. By substituting simulation results into Equation (59), the positioning RMSEs of Step 2 could be determined, as presented in Figure 12. The positioning RMSEs fluctuated severely with the initial yaw angle bias, which indicates that the iterative positioning algorithm was sensitive to the initial yaw angle and was consistent with the analysis in the Section 3.
The simulated measurements were then imported into TSLM, with δ t 0 = 0   m , and initial positions of the distributed antennas as four random points near the center of the area formed by the anchors. The RMSE of the yaw angle obtained in Step 1 was 0.1829 rad, which means that the coarse solution was not far from the optimum. By using coarsely estimated solutions of Step 1, the refined solutions were obtained.
Utilizing the above simulation results, CRLB was computed based on Equation (44) using the true positions of AGV and anchors in the simulation settings. The positioning RMSEs of the proposed algorithm from 1000 Monte Carlo simulation tests were computed based on Equation (59). The positioning RMSEs of our algorithm and the theoretical CRLB of the DMA method are presented in Table 3. In this table, the results of the “only Step 2” column in the table were calculated with different representative initial values of ψ c | 0 as −1.67 rad, 3.04 rad, and 1.79 rad, representing π rad, π / 2 rad, and π / 10 rad bias with respect to the true yaw angle, respectively. When the bias was π / 10 rad, the positioning RMSEs were also close to the theoretical CRLB, as with those of the TSLM algorithm. However, when the bias was π rad or π / 2 rad, the positioning RMSEs from Step 2 only were far greater than for CRLB. This result indicates that, when the initial value is far away from the true value, the algorithm may converge to the local optimal solution, presenting the wrong position.
The simulation results verify that, without the prior information of the yaw angle, the TSLM algorithm avoids the initial yaw angle problem, and it can obtain a positioning accuracy close to the theoretical lower bound by using coarse estimation. Furthermore, if there is prior attitude information of the body, using Step 2 only can also achieve the desired accuracy.

6. Conclusions

Autonomous high-precision positioning and navigation of AGV are desperately needed in unmanned warehouses, ports, and similar environments. Radio broadcast positioning systems can be employed in these AGV positioning applications. Due to the limitation of the flat structure of AGV, the receiving antennas cannot be mounted at the highest point of the vehicle. The positioning signals are not only affected by the obstacles from the environment but also blocked by the AGV cargo. The availability and accuracy of the positioning system are severely challenged.
To tackle the above problem, a distributed multi-antenna positioning method was proposed, which utilizes the synchronous reception by multiple antennas. In this method, the measurements of the distributed multiple antennas are transformed to a function of the reference position by estimating the attitude of the body. To estimate the position, receiver clock bias, and attitude angle, a two-step positioning algorithm TSLM was proposed. Firstly, the positions of the distributed antennas and the clock bias are jointly estimated. Then, the reference position and the yaw angle are estimated according to the transformation of antenna positions between frame b and frame n. Through Step 1, the unknowns are coarsely estimated to a proper accuracy, so that they can be applied as initial values for Step 2 to guarantee its convergence to the global optimum. Finally, a refined positioning result can be obtained iteratively in Step 2. Simulation results demonstrated that, compared with the conventional single-antenna localization, the positioning availability was significantly improved. Moreover, with the standard deviation of the TOA measurement noise as 0.2 m, the DMA method could achieve decimeter-level accuracy. Simulation tests verified that the TSLM algorithm can provide a position estimation with an accuracy close to CRLB without the requirement for initial attitude information. Furthermore, with prior information of the yaw angle, Step 2 can achieve similar results to TSLM.
In the future, more factors such as multipath and non-line-of-sight (NLOS) will be considered in algorithm design and performance analysis, and more studies will be done on measurement noise modeling. In addition, the theoretical analysis of the influence of the initial values and the effect of the proposed algorithm will be carried out. The nonlinear constrained optimization problem will be further studied to extend the proposed method to 3D positioning and attitude determination. Improvements on computational complexity and other algorithms with possibly higher efficiency and better robustness will be investigated. Moreover, the quantitative influence of antenna configuration and the criteria of antenna position and quantity configuration will also be studied.

Author Contributions

Conceptualization, X.A., S.Z., and X.C.; data curation, X.A. and S.Z.; formal analysis, X.A., S.Z., and Q.S.; investigation, X.C. and Q.S.; methodology, X.A., S.Z., and X.C.; project administration, Mingquan Lu; software, X.A. and S.Z.; supervision, X.C.; validation, X.A.; visualization, X.A. and S.Z.; writing—original draft, X.A.; writing—review and editing, X.C. and Q.S.. All authors have read and agreed to the published version of the manuscript.

Acknowledgments

The authors are indebted to Wenyi Li for her help in simulation modeling, and to Peirong Fan for many helpful discussions and advice.

Conflicts of Interest

The authors declare no conflicts of interest.

References

  1. Le-Anh, T.; De Koster, M.B.M. A review of design and control of automated guided vehicle systems. Eur. J. Oper. Res. 2006, 171, 1–23. [Google Scholar] [CrossRef]
  2. Chen, Z.; He, X.; Cao, Z.; Jin, Y.; Li, J. Position Estimation of Automatic-Guided Vehicle Based on MIMO Antenna Array. Electronics 2018, 7, 193. [Google Scholar] [CrossRef] [Green Version]
  3. Kaplan, E.D.; Hegarty, C.J. Understanding GPS Principles and Applications, 2nd ed.; Artech House: Norwood, MA, USA, 2006. [Google Scholar]
  4. Fan, P.; Li, W.; Cui, X.; Lu, M. Precise and Robust RTK-GNSS Positioning in Urban Environments with Dual-Antenna Configuration. Sensors 2019, 19, 3586. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  5. Gao, H.; Li, X. Tightly-Coupled Vehicle Positioning Method at Intersections Aided by UWB. Sensors 2019, 19, 2867. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  6. Mazhar, F.; Khan, M.G.; Sällberg, B. Precise Indoor Positioning Using UWB: A Review of Methods, Algorithms and Implementations. Wirel. Pers. Commun. 2017, 97, 4467–4491. [Google Scholar] [CrossRef]
  7. Shi, G.; Ming, Y. Wireless Communications, Networking and Applications. Lecture Notes in Electrical Engineering; Springer: New Delhi, India, 2016; pp. 1269–1278. [Google Scholar]
  8. Sahinoglu, Z.; Gezici, S. Ultra-Wideband Positioning Systems: Theoretical Limits, Ranging Algorithms, and Protocols; Cambridge University Press: Cambridge, UK, 2008. [Google Scholar]
  9. Rahman, M.; NagshvarianJahromi, M.; Mirjavadi, S.S.; Hamouda, A.M. Compact UWB Band-Notched Antenna with Integrated Bluetooth for Personal Wireless Communication and UWB Applications. Electronics 2019, 8, 158. [Google Scholar] [CrossRef] [Green Version]
  10. Shen, Y.; Win, M. Fundamental limits of wideband localization—Part I: A general framework. IEEE Trans. Inf. Theory. 2010, 56, 4956–4980. [Google Scholar] [CrossRef]
  11. Jourdan, D.B.; Dardari, D.; Win, M.Z. Position error bound for UWB localization in dense cluttered environments. IEEE Trans. Aerosp. Electron. Syst. 2008, 44, 613–628. [Google Scholar] [CrossRef]
  12. Cetin, O.; Nazli, H.; Gurcan, R.; Ozturk, H.; Guneren, H.; Yelkovan, Y.; Cayir, M.; Celebi, H.; Partal, H.P. An experimental study of high precision TOA based UWB positioning systems. In Proceedings of the IEEE International Conference on Ultra-Wideband (ICUWB), Syracuse, NY, USA, 12 November 2012; pp. 357–361. [Google Scholar]
  13. Alarifi, A.; Al-Salman, A.; Alsaleh, M.; Alnafessah, A.; Al-Hadhrami, S.; Al-Ammar, M.A.; Al-Khalifa, H.S. Ultra wideband indoor positioning technologies: Analysis and recent advances. Sensors 2016, 16, 707. [Google Scholar] [CrossRef]
  14. Minne, K.; Macoir, N.; Rossey, J.; Van den Brande, Q.; Lemey, S.; Hoebeke, J.; De Poorter, E. Experimental Evaluation of UWB Indoor Positioning for Indoor Track Cycling. Sensors 2019, 19, 2041. [Google Scholar] [CrossRef] [Green Version]
  15. Shi, Q.; Cui, X.; Li, W.; Xia, Y.; Lu, M. Visual-UWB Navigation System for Unknown Environments. In Proceedings of the 31st International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS+ 2018), Miami, FL, USA, 24–28 September 2018; pp. 3111–3121. [Google Scholar]
  16. Shi, Y.; Wang, A.; Hao, J.; Jiao, B. Research on MIMU/UWB Integrated Indoor Positioning. In Proceedings of the China Satellite Navigation Conference (CSNC) 2017 Proceedings: Volume II, Shanghai, China, 23–25 May 2017; pp. 521–533. [Google Scholar]
  17. Feng, D.; Wang, C.; He, C.; Zhuang, Y.; Xia, X. Kalman Filter Based Integration of IMU and UWB for High-Accuracy Indoor Positioning and Navigation. IEEE Internet Things J. 2020. [Google Scholar] [CrossRef]
  18. Farrell, J.A. Aided Navigation: GPS with High Rate Sensors; McGraw-Hill: New York, NY, USA, 2008. [Google Scholar]
  19. Groves, P.D. Principles of GNSS, Inertial and Multisensor Integrated Navigation Systems; Artech House: London, UK, 2008. [Google Scholar]
  20. Wan, G.; Yang, X.; Cai, R.; Li, H.; Zhou, Y.; Wang, H.; Song, S. Robust and Precise Vehicle Localization based on Multi-sensor Fusion in Diverse City Scenes. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Brisbane, Australia, 21–25 May 2018; pp. 4670–4677. [Google Scholar]
  21. Gao, Y.; Liu, S.; Atia, M.; Noureldin, A. INS/GPS/LiDAR Integrated Navigation System for Urban and Indoor Environments Using Hybrid Scan Matching Algorithm. Sensors 2015, 15, 23286–23302. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  22. Vikram, S.; Chauhan, S.; Gao, G. Joint GPS and Vision Estimation Using an Adaptive Filter. In Proceedings of the 30th International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS+ 2017), Portland, OR, USA, 25–29 September 2017; pp. 808–812. [Google Scholar]
  23. Kok, M.; Hol, J.D.; Schön, T.B. Indoor Positioning Using Ultrawideband and Inertial Measurements. IEEE Trans. Veh. Technol. 2015, 64, 1293–1303. [Google Scholar] [CrossRef] [Green Version]
  24. Lobo, F.; Grael, D.; Oliveira, H.; Villas, L.; Almehmadi, A.; El-Khatib, K. Cooperative Localization Improvement Using Distance Information in Vehicular Ad Hoc Networks. Sensors 2019, 19, 5231. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  25. Patwari, N.; Ash, J.N.; Kyperountas, S.; Hero, A.O., III; Moses, R.L.; Correal, N.S. Locating the nodes: Cooperative localization in wireless sensor networks. IEEE Signal Process. Mag. 2005, 22, 54–69. [Google Scholar] [CrossRef]
  26. Kurazume, R.; Nagata, S.; Hirose, S. Cooperative positioning with multiple robots. In Proceedings of the 1994 IEEE International Conference on Robotics and Automation (ICRA), San Diego, CA, USA, 8–13 May 1994; pp. 1250–1257. [Google Scholar]
  27. Berafelt, F.; Boberg, B.; Nygards, J. Collaborative GPS/INS navigation in urban environment. In Proceedings of the 2004 National Technical Meeting of the Institute of Navigation(ION NTM 2004), San Diego, CA, USA, 26–28 Janauary 2004; pp. 1114–1125. [Google Scholar]
  28. Rozum, S.; Kufa, J.; Polak, L. Bluetooth Low Power Portable Indoor Positioning System Using SIMO Approach. In Proceedings of the 2019 42nd International Conference on Telecommunications and Signal Processing (TSP), Budapest, Hungary, 1–3 July 2019; pp. 228–231. [Google Scholar]
  29. Mahyiddin, W.A.; Ahmad Mazuki, A.L.; Dimyati, K.; Othman, M.; Mokhtar, N.; Arof, H. Localization Using Joint AOD and RSS Method in Massive MIMO System. Radioengineering 2019, 28, 749–756. [Google Scholar] [CrossRef]
  30. Widmaier, M.; Arnold, M.; Dorner, S.; Cammerer, S.; Brink, S.T. Towards Practical Indoor Positioning Based on Massive MIMO Systems. In Proceedings of the IEEE 90th Vehicular Technology Conference (VTC2019-Fall), Honolulu, HI, USA, 22–25 September 2019; pp. 1–6. [Google Scholar]
  31. Chen, C.; Chen, Y.; Han, Y.; Lai, H.-Q.; Zhang, F.; Liu, K.J.R. Achieving Centimeter-Accuracy Indoor Localization on WiFi Platforms: A Multi-Antenna Approach. IEEE Internet Things J. 2017, 44, 122–134. [Google Scholar] [CrossRef]
  32. Schrader, D.; Min, B.-C.; Matson, E.; Dietz, J. Combining multiple, inexpensive GPS receivers to improve accuracy and reliability. In Proceedings of the Sensors Applications Symposium (SAS), Brescia, Italy, 7–9 February 2012; pp. 1–6. [Google Scholar]
  33. Shetty, A.; Gao, G.X. Measurement level integration of multiple low-cost GPS receivers for UAVs. In Proceedings of the 2015 International Technical Meeting of the Institute of Navigation (ION ITM 2015), Dana Point, CA, USA, 26–28 January 2015; pp. 842–848. [Google Scholar]
  34. Ng, Y.; Gao, G. GNSS Multireceiver Vector Tracking. IEEE Trans. Aerosp. Electron. Syst. 2017, 53, 2583–2593. [Google Scholar] [CrossRef]
  35. Shi, Q.; Cui, X.; Zhao, S.; Xu, S.; Lu, M. BLAS: Broadcast Relative Localization and Clock Synchronization for Dynamic Dense Multi-Agent Systems. arXiv 2019, arXiv:1911.11995. [Google Scholar]
  36. Jiang, J.; Wang, G.; Ho, K.C. Accurate Rigid Body Localization via Semidefinite Relaxation Using Range Measurements. IEEE Trans. Signal Proc. Let. 2018, 25, 378–382. [Google Scholar] [CrossRef]
  37. Chen, S.; Ho, K.C. Accurate localization of a rigid body using multiple sensors and landmarks. IEEE Trans. Signal Proces. 2015, 63, 6459–6472. [Google Scholar] [CrossRef]
  38. Chepuri, S.P.; Leus, G.; Van der Veen, A.-J. Rigid body localization using sensor networks. IEEE Trans. Signal Process. 2014, 62, 4911–4924. [Google Scholar] [CrossRef]
  39. Bertsekas, D.P. Nonlinear Programming, 2nd ed.; Athena Scientific: Belmont, MA, USA, 1999. [Google Scholar]
  40. Huang, B.; Yao, Z.; Cui, X.; Lu, M. Dilution of Precision Analysis for GNSS Collaborative Positioning. IEEE Trans. Veh. Technol. 2016, 65, 3401–3415. [Google Scholar] [CrossRef]
  41. Umeyama, S. Least-squares estimation of transformation parameters between two point patterns. IEEE Trans. Pattern Anal. Mach. Intell. 1991, 13, 376–380. [Google Scholar] [CrossRef] [Green Version]
  42. Eggert, D.W.; Lorusso, A.; Fisher, R.B. Estimating 3-D rigid body transformations: A comparison of four major algorithms. Mach. Vis. Appl. 1997, 9, 272–290. [Google Scholar] [CrossRef]
  43. Nocedal, J.; Wright, S.J. Numerical Optimization, 2nd ed.; Springer: New York, NY, USA, 2006. [Google Scholar]
  44. Kay, S.M. Fundamentals of Statistical Signal. Processing, Volume I: Estimation Theory; Prentice Hall: Upper Saddle River, NJ, USA, 1993. [Google Scholar]
  45. Xie, G. Principles of GPS and Receiver Design; Publishing House of Electronics Industry: Beijing, China, 2009. [Google Scholar]
Figure 1. The flat structure of an automatic-guided vehicle (AGV) and its typical environment. The receiving antennas cannot be mounted at the highest point of the vehicle. The radio positioning signals are not only affected by the obstacles in the environment but also blocked by the carried cargoes.
Figure 1. The flat structure of an automatic-guided vehicle (AGV) and its typical environment. The receiving antennas cannot be mounted at the highest point of the vehicle. The radio positioning signals are not only affected by the obstacles in the environment but also blocked by the carried cargoes.
Sensors 20 01155 g001
Figure 2. An example of a signal-blocked environment of AGV. The AGV is carrying some cargo, and the receiving antennas are installed on the corners of its flat body.
Figure 2. An example of a signal-blocked environment of AGV. The AGV is carrying some cargo, and the receiving antennas are installed on the corners of its flat body.
Sensors 20 01155 g002
Figure 3. The position of antenna i in frame b; c is the reference point on the AGV.
Figure 3. The position of antenna i in frame b; c is the reference point on the AGV.
Sensors 20 01155 g003
Figure 4. Flow chart of the two-step Levenberg–Marquardt (TSLM) algorithm.
Figure 4. Flow chart of the two-step Levenberg–Marquardt (TSLM) algorithm.
Sensors 20 01155 g004
Figure 5. Simulation scene. The blue triangles numbered from 1–6 represent the anchors, the purple stars numbered from 1–4 indicate the antennas mounted on the AGV, the red solid square indicates the center of the AGV (reference point), the red hollow cube in the center indicates the cargo on the AGV, the rectangle filled with blue indicates the AGV body, the rectangles with orange dashed lines indicate the walls on both sides of the road, and the green solid lines indicate the lines of sight (LOSs) from the antennas to their visible anchors.
Figure 5. Simulation scene. The blue triangles numbered from 1–6 represent the anchors, the purple stars numbered from 1–4 indicate the antennas mounted on the AGV, the red solid square indicates the center of the AGV (reference point), the red hollow cube in the center indicates the cargo on the AGV, the rectangle filled with blue indicates the AGV body, the rectangles with orange dashed lines indicate the walls on both sides of the road, and the green solid lines indicate the lines of sight (LOSs) from the antennas to their visible anchors.
Sensors 20 01155 g005
Figure 6. The trajectory of the center and the attitude of the AGV in the dynamic test. The blue triangles represent the anchors, the red line indicates the trajectory of the center, the blue rectangle indicates the AGV body, and the red dashed lines indicate obstacles on both sides of the road.
Figure 6. The trajectory of the center and the attitude of the AGV in the dynamic test. The blue triangles represent the anchors, the red line indicates the trajectory of the center, the blue rectangle indicates the AGV body, and the red dashed lines indicate obstacles on both sides of the road.
Sensors 20 01155 g006
Figure 7. The numbers of visible anchors vs. time.
Figure 7. The numbers of visible anchors vs. time.
Sensors 20 01155 g007
Figure 8. Number of visible anchors of multiple antennas (top) and distributed multi-antenna horizontal dilution of precision (DMA-HDOP) (bottom).
Figure 8. Number of visible anchors of multiple antennas (top) and distributed multi-antenna horizontal dilution of precision (DMA-HDOP) (bottom).
Sensors 20 01155 g008
Figure 9. Two-dimensional (2D) projection at (a) 84 s, and (b) 100 s. Blue triangles numbered from 1–6 indicate anchors, purple stars numbered from 1–4 indicate antennas mounted on the corner of the AGV, the red solid square indicates the center of the AGV, the red rectangle indicates the projection of the cargo on AGV, the rectangle filled with blue indicates the AGV body, the red dashed lines indicate the projections of the walls on both sides of the road, and green lines indicate the LOSs from the antennas to their visible anchors.
Figure 9. Two-dimensional (2D) projection at (a) 84 s, and (b) 100 s. Blue triangles numbered from 1–6 indicate anchors, purple stars numbered from 1–4 indicate antennas mounted on the corner of the AGV, the red solid square indicates the center of the AGV, the red rectangle indicates the projection of the cargo on AGV, the rectangle filled with blue indicates the AGV body, the red dashed lines indicate the projections of the walls on both sides of the road, and green lines indicate the LOSs from the antennas to their visible anchors.
Sensors 20 01155 g009
Figure 10. The Cramer–Rao lower bound (CRLB) of DMA positioning at each moment.
Figure 10. The Cramer–Rao lower bound (CRLB) of DMA positioning at each moment.
Sensors 20 01155 g010
Figure 11. The 2D projection at the start point of the trajectory.
Figure 11. The 2D projection at the start point of the trajectory.
Sensors 20 01155 g011
Figure 12. Root-mean-square errors (RMSEs) of Step 2 vs. initial yaw angle bias.
Figure 12. Root-mean-square errors (RMSEs) of Step 2 vs. initial yaw angle bias.
Sensors 20 01155 g012
Table 1. The coordinates of the six anchors in frame n (m).
Table 1. The coordinates of the six anchors in frame n (m).
Anchor No.123456
East−20−2020206060
North15−515−515−5
Up252525252525
Table 2. The parameters of the AGV movement.
Table 2. The parameters of the AGV movement.
Segment1234567891011
v E (m/s)0.250.250.250.250.3750.1250.250.250.250.250.25
v N (m/s)0.0250−0.0500.050.050.050−0.01300
ω (rad/s)0−0.01500.019−0.01800−0.00800.0020
T (s)5205301051030103025
Table 3. The positioning RMSEs of the proposed algorithm and the CRLB of the DMA method. This table lists the positioning RMSEs of the proposed TSLM algorithm and Step 2 only of the TSLM algorithm. The results of Step 2 only are given with different initial yaw angles. CRLB is listed as a benchmark.
Table 3. The positioning RMSEs of the proposed algorithm and the CRLB of the DMA method. This table lists the positioning RMSEs of the proposed TSLM algorithm and Step 2 only of the TSLM algorithm. The results of Step 2 only are given with different initial yaw angles. CRLB is listed as a benchmark.
ParametersRMSECRLB
TSLMOnly Step 2
bias = π   rad bias = π / 2   rad bias = π / 10   rad
x (m)0.1462.0532.0530.1460.144
y (m)0.2440.5460.5490.2430.242
Clock bias (m)0.0993.9803.9810.0990.099
Yaw angle (rad)0.0332.9242.9240.0330.032

Share and Cite

MDPI and ACS Style

An, X.; Zhao, S.; Cui, X.; Shi, Q.; Lu, M. Distributed Multi-Antenna Positioning for Automatic-Guided Vehicle. Sensors 2020, 20, 1155. https://doi.org/10.3390/s20041155

AMA Style

An X, Zhao S, Cui X, Shi Q, Lu M. Distributed Multi-Antenna Positioning for Automatic-Guided Vehicle. Sensors. 2020; 20(4):1155. https://doi.org/10.3390/s20041155

Chicago/Turabian Style

An, Xinyuan, Sihao Zhao, Xiaowei Cui, Qin Shi, and Mingquan Lu. 2020. "Distributed Multi-Antenna Positioning for Automatic-Guided Vehicle" Sensors 20, no. 4: 1155. https://doi.org/10.3390/s20041155

APA Style

An, X., Zhao, S., Cui, X., Shi, Q., & Lu, M. (2020). Distributed Multi-Antenna Positioning for Automatic-Guided Vehicle. Sensors, 20(4), 1155. https://doi.org/10.3390/s20041155

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop