Multivariate position estimation

Multivariate position estimation can be performed to provide a position estimate of a moving object. The multivariate position estimation approach can employ multiple types of information including time of arrival (or time difference of arrival), angle of arrival, Doppler, and/or prior location information in an iterative process to calculate a location estimate that is highly accurate. In particular, the multivariate position estimation approach can employ the statistical quality of each of these types of information to quickly arrive at a highly accurate position estimate within a 3D coordinate system. The multivariate position estimation approach can be implemented in environments where a single receiver is available as well as in environments where multiple receivers exist.

CROSS-REFERENCE TO RELATED APPLICATIONS

BACKGROUND

Geolocation refers to estimating the location of an object and is used in a wide variety of applications. There is also a wide variety of geolocation techniques. Some of these techniques only provide a general estimate of an object's location (e.g., a city in which the object is located), while others can provide a highly accurate estimate (e.g., latitude, longitude, and altitude of the object). The present invention is directed to improving these highly accurate geolocation techniques.

Most highly accurate geolocation techniques rely on multiple anchors (or known position sources) and therefore require complex systems to implement. This is especially true when geolocation must be performed in GPS denied spaces. Additionally, even with multiple anchors, many geolocation techniques may still fail to provide sufficient accuracy for many applications. For example, autonomous vehicles and other applications where objects are steered oftentimes require position estimates that are both highly accurate and capable of being produced in real-time.

BRIEF SUMMARY

The present invention extends to methods, systems and computer program products for performing multivariate position estimation. The multivariate position estimation approach of the present invention can employ multiple types of information including time of arrival (or time difference of arrival), angle of arrival, Doppler, and/or prior location information in an iterative process to calculate a location estimate that is highly accurate. In particular, the multivariate position estimation approach can employ the statistical quality of each of these types of information to quickly arrive at a highly accurate position estimate within a 3D coordinate system. The multivariate position estimation approach can be implemented in environments where a single receiver (i.e., a single anchor) is available as well as in environments where multiple receivers exist.

In one embodiment, the present invention is implemented by a tracker as a method for performing multivariate position estimation comprising. The tracker receives a communication emitted from a moving object and processes the communication to generate a time of arrival measurement, an angle of arrival measurement, and a Doppler measurement for the communication. The tracker also obtains a tracker location representing where the tracker was located when the communication was received. The tracker then estimates an object location representing where the moving object was located when the moving object emitted the communication using the time of arrival measurement, the angle of arrival measurement, the Doppler measurement, and the tracker location.

In another embodiment, the present invention is implemented as a tracker that includes: one or more antennas for receiving a communication emitted from a moving object; a time of arrival component that generates a time of arrival measurement for the communication; an angle of arrival component that generates an angle of arrival measurement for the communication; a Doppler component that generates a Doppler measurement for the communication; a tracker location component that obtains a tracker location representing where the tracker was located when the communication was received; and a location engine that receives and processes the time of arrival measurement, the angle of arrival measurement, the Doppler measurement, and the tracker location to estimate an object location representing where the moving object was located when the moving object emitted the communication.

DETAILED DESCRIPTION

In this specification, the term “tracker” should be construed as any computing system that is configured to receive periodic communications from a moving object and employ various types of information derived from the periodic communications to estimate a position of the moving object. The term “computing device” should be construed generally to encompass each of the various types of hardware platforms that one of skill in the art could use to implement the techniques of the present invention (e.g., a CPU platform, a microprocessor platform, an ASIC platform, an FPGA platform, a DSP platform, etc.). The term computing system should be construed as including one or more computing devices. Furthermore, although a tracker will be described primary as a single physical node, in some embodiments, a tracker can encompass more than one physical node. For example, a tracker could encompass two or more physically separated computing devices (i.e., two or more nodes).

FIG. 1illustrates an example environment in which the present invention could be implemented. As shown, a tracker100is configured to receive periodic communications from a moving object150. Moving object150can represent any type of moving object capable of transmitting periodic communications. Although it should not be limited to such use cases, the present invention may be particularly beneficial in environments where tracker100is employed to steer moving object150. For example, moving object150could be an object or a vehicle. Further, although not limited to such environments, the present invention may be particularly beneficial when moving object150is in a GPS denied space or when available GPS techniques will not provide sufficient accuracy.

FIG. 2illustrates an example architecture of tracker100. As mentioned above, tracker100is configured to receive periodic communications from moving object150. As shown, these periodic communications can each include a timestamp. In the following description, it will be assumed that moving object150is configured to generate a timestamp locally for inclusion in each communication to represent the time of transmission of the communication. In such cases, it will be assumed that tracker100and moving object150have synchronized clocks to allow tracker100to use time of arrival techniques. In other embodiments, moving object150may not include a timestamp in the periodic communications, and in such cases, tracker100may implement time difference of arrival techniques. In other embodiments, tracker100may be configured to transmit periodic communications that include a timestamp generated at tracker100, and moving object150may include such timestamps in the periodic communications that it sends back to tracker100(which may eliminate the need for the clocks to be synchronized). In any case, moving object150is configured to transmit periodic communications to tracker100, and tracker100is configured to process these periodic communications for purposes of implementing multivariate position estimation.

To generate the different types of information for the multivariate position estimation, tracker100can include a time of arrival component101(which could equally be a time difference of arrival component in some embodiments), an angle of arrival component102, a Doppler component103, and a tracker location component104. Tracker100also includes a location engine105which is configured to generate position estimates based on the information provided from components101-104.

Time of arrival component101can represent any combination of hardware and/or software components that are configured to generate time of arrival information for each periodic communication received from moving object150. For example, time of arrival component101can be configured to detect when a periodic communication is received and to generate a corresponding “receive timestamp.” This receive timestamp will be represented in the figures as ToAiwhere i represents the relative order of the communication. Time of arrival component101can also be configured to extract the “transmit timestamp” from the periodic communication which represents when the periodic communication was sent (whether by moving object150or by tracker100). This transmit timestamp will be represented in the figures as timestampi.

As mentioned above, the transmit timestamp may represent either (1) when the periodic communication received at tracker100was sent by moving object150; or (2) when a corresponding periodic communication was sent by tracker100to moving object150. In this later case, moving object150can be viewed as simply relaying a received communication back to tracker100. In either case, the difference between the receive timestamp and the transmit timestamp can represent the distance between moving object150and tracker100as will be further described below.

Angle of arrival component102can represent a monopulse antenna, a parabolic antenna, a phased array, or other suitable antenna configuration that can detect the angle at which the periodic communication arrives at tracker100. The angle of arrival for a particular periodic communication will be represented in the figures as AoAiwhere i again represents the relative order of the communication (e.g., ToA1and AoA1can define when and at what angle a “first” periodic communication was received).

Doppler component103can represent any combination of hardware and/or software components that are configured to calculate the Doppler shift of each periodic communication. The Doppler shift for a particular periodic communication will be represented in the figures as Doppiwhere i again represents the relative order of the communication.

Finally, tracker location component104can represent any combination of hardware and/or software components that are configured to maintain/provide known locations of tracker100at periodic intervals which generally correspond with the timing at which the periodic communications are received. These known locations can be represented in X, Y, and Z coordinates (or another suitable coordinate system) as Xi, Yi, Ziwhere i represents the relative order of the periodic communication to which the location corresponds (e.g., X1, Y1, Z1can represent the location of tracker100when it received a periodic communication from which ToA1, AoA1, and Dopp1were generated). If tracker100is stationary, this known location would remain constant. However, when tracker100is moving, the known location will likely change for each received periodic communication. One of skill in the art would understand that there are many different ways to determine the location of tracker100each of which could be employed by tracker location component104.

FIG. 3illustrates an example of how these various types of information can be provided to location engine105as periodic communications are received. In this example, it is assumed that time of arrival is employed and therefore time of arrival component101is shown as providing a series of transmit/receive timestamp pairs (ToAi, Timestampi). Alternatively, if time difference of arrival is employed, component101could instead provide a series of receive timestamps. Angle of arrival component102, Doppler component103, and tracker location component104are each similarly shown as providing a series of angles of arrival, Doppler shifts, and known locations respectively.

In this example, it is assumed that tracker100includes a single physical node. However, in other embodiments, tracker100may employ multiple physical nodes (e.g., two nodes that each independently receives the periodic communications). In such cases, the second physical node would include its own time of arrival component101, angle of arrival component102, and Doppler component103(and possibly its own tracker location component104if it is spaced a significant distance from the first receiver) to provide independent series of information to location engine105. It is noted however that one benefit of the present invention is that a highly accurate position estimate can be generated with only a single node.

In summary, for each received periodic communication, each node of tracker100will generate time of arrival information, angle of arrival information, Doppler information, and tracker location information and provide this information to location engine105. Location engine105can then use this information in an iterative manner to generate a location estimate for moving object150. By including the node's location information in this process, the location estimate can be an actual location rather than a relative location with respect to tracker100. In this regard, if a location estimate relative to tracker100is sufficient, the node location information could be excluded from the process.

In accordance with embodiments of the present invention, location engine105can be configured to implement a cost function by which moving object150's position can be estimated. This cost function can be represented as:

α^=arg⁢minα⁢∑i=1R⁢∑j=1T⁢{(ti⁢j-τi⁢j⁡(α))2στ2+(θi⁢j-φi⁢j⁡(α))2σφ2+(f.i⁢j-δ.i⁢j⁡(α))2σδ.2+α0}
where {circumflex over (α)} is the estimated position, T represents time, R represents the node (or “receiver,” which may be 1 or more), tijrepresents the known (or measured) time of arrival, θijrepresents the known angle of arrival, {dot over (f)}ijrepresents the known frequency, and α0represents a priori information defining uncertainty of tracker100's known position. The values of στ2, σφ−2, and σ{dot over (δ)}2represent a confidence of the time of arrival, angle of arrival and Doppler measurements respectively, and τij(a), φij(a), and {dot over (δ)}ij(α) are the variables whose values can be selected using a non-linear least squares algorithm (e.g., the Levenberg-Marquardt algorithm) to minimize the cost function.

To implement this cost function from the measurements received from components101-104, location engine105can be configured to process the measurements using the following version of the cost function:
{circumflex over (α)}=c1+c2+c3+c4
where c1represents the Doppler component of the cost function, c2represents the time of arrival component of the cost function, c3represents the angle of arrival component of the cost function, and c4represents the node location component of the cost function.

Each of the c1through c4components can be defined in terms of the following position vector:
{right arrow over (P)}=[A(1)−{right arrow over (B(n,1))}A(2)−{right arrow over (B(n,2))}A(3)−{right arrow over (B(n,3)])}
where A is the unknown position of moving object150defined as A=[xi, yi, zi] and {right arrow over (B)} is an n×1 vector (where n represents the number of nodes employed by tracker100) of the position of the node of interest defined as B=[x(n×1)i, y(n×1)i, z(n×1)i].

In particular, c1can be defined as:

c1=τo⁢b⁢s-A⁢B→^c-τeστ
where τobsis the measured time of arrival for the node of interest (i.e., ToAi), c is the speed of light, and τeis the emission time if known. If the emission time is not known this value is set to zero. στis the standard deviation of time of arrival component101.

Where θ is defined as the four quadrant arctangent function of the two dimensional x, y plane between A and B. φ is the measured angle of arrival (i.e., AoAi). The operation of θ−φ is defined as taking the modulus of each operand relative to π and subtracting the difference. If the operand is greater than π then the sign of the resulting modulus operation is flipped prior to the difference being taken. σφis the standard deviation of angle of arrival component102.

c3=fd⁢m+fc-fe-A⁢B→^·V→λσδ.
where σ{dot over (δ)}is the standard deviation of Doppler component103, fdmis the measured Doppler frequency (i.e., Doppi), fcis the carrier frequency of the node of interest, feis the measured frequency error, and V is the known velocity of the known node.

Finally, c4is defined as:
c4=WTpos554W
Where W=pos−pos, pos is the x, y, z of the known position of the tracker andposis the mean position of x, y, z. † is defined as the pseudo inverse, sometimes known as the Moore-Penrose inverse. Notably, the c4component accounts for the a priori uncertainty of the tracker's known position. For example, if the tracker's known position is determined using GPS, the accuracy of the GPS system can be accounted for within c4which in essence allows the known position to float in the cost function (as opposed to having the known position fixed). More specifically, by employing c4rather than a fixed known position, minimizing the cost function will yield more accurate estimates for the other components.

Accordingly, the cost function to be minimized can be implemented within location engine105as:

Location engine105can continuously receive the series of time of arrival measurements (ToAi), the series of angle of arrival measurements (AoAi), the series of Doppler measurement (Doppi), and the series of locations (Bi), and for each set of measurements (e.g, ToA1, AoA1, Dopp1, and B1), can input the measurements into the respective component (c1-c4) and then minimize the cost function by a non-linear least squares algorithm (e.g., Levenberg-Marquardt). The values of A that produce a minimum can be selected as the estimated position of moving object150at the corresponding time. Because location engine105generates this estimated position from the time of arrival, angle of arrival, Doppler shift, and known location of the node(s), a highly accurate estimate can be obtained even when tracker100employs a single node.

FIG. 4illustrates an example scenario in which the present invention could be employed. As shown, tracker100is assumed to be moving in a straight direction while moving object150is moving in a similar direction but along a curved path. For example, tracker100could be part of an aircraft and moving object150could be an object launched from the aircraft. Moving object150is shown as emitting four communications at periodic intervals as it traverses this path, and these communications are assumed to be received at tracker100at times t1-t4respectively. For simplicity, it will be assumed that tracker100includes a single node (i.e., R=1 in the cost function).

As described above, each time tracker100receives a communication from moving object150it can generate a corresponding angle of arrival measurements, time of arrival measurement, Doppler measurement, and node location. For example at time t1,FIG. 4represents that tracker100has generated AoA1, ToA1, Dopp1, and B(x1, y1, z1) based on the receipt of communication 1. These measurements can then be provided to location engine105to allow it to estimate the position of moving object150when it emitted communication 1—i.e., to identify the values of A(x1, y1, z1) that minimize the cost function. This process can be repeated for each communication that tracker100receives from moving object150. Notably, this process can be performed in real-time to produce a highly accurate and live position estimate for moving object150. Tracker100could then provide these position estimates to another system to perform any desirable task such as tracking and/or steering moving object150.

In summary, location engine105can be configured to estimate a position of a moving object based on multiple types of measurements obtained from processing a communication emitted by the object and based on a known location of one or more nodes that received the communication. By employing the multiple types of measurements and by minimizing a cost function based on such measurements, location engine105can produce accurate estimates even when a single node is available to provide measurements of the received communications.