GNSS navigation solution using inequality constraints

Information such as altitude or speed limits for a specific geographic region can be utilized to improve position and velocity estimation for a mobile device using inequality constraints. The inequality constraints can be used as pseudo-measurements when needed to improve position and velocity estimation.

TECHNICAL FIELD

This disclosure relates generally to Global Navigation Satellite Systems (GNSS), and more particularly to improving GNSS navigation solutions and detecting fault measurements.

BACKGROUND

Modern mobile devices may include a variety of applications that depend on an accurate estimate of device location, such as a map application or location-based services (LBS) application. An integrated Global Positioning System (GPS) receiver and onboard sensors (e.g., accelerometers, gyroscopes) can be used to determine location and orientation of the device, and even provide a rough estimate of heading.

Many GPS receivers use a recursive estimation algorithm (e.g., Kalman Filter) to provide a computationally efficient navigation solution. A linear form of the Kalman Filter, such as the Extended Kalman Filter (EKF), can be used if the system equations or measurement equations are non-linear. The EFK provides a good result if the state vector is chosen carefully. Even if the state vector is carefully chosen, the EFK can generate erratic estimates due to biased GNSS measurements (e.g. multipath signals), poor solution geometry (e.g. urban canyons), and low measurement redundancy (e.g. few satellites available).

SUMMARY

Information such as altitude or speed limits for a specific geographic region can be utilized to improve position and velocity estimation for a mobile device using inequality constraints. The inequality constraints can be used as pseudo-measurements when needed to improve position and velocity estimation.

Various implementations of the subject matter described herein may provide one or more of the following advantages: 1) an improved horizontal and vertical accuracy for GNSS first fix cases, and 2) an improved ability to perform GNSS measurement fault detection.

The details of one or more implementations are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages will become apparent from the description, the drawings, and the claims.

DETAILED DESCRIPTION

Overview

Information for specific location regions of interest can be used to improve GNSS position and/or velocity estimation by providing constraints that limit the values of the estimated states (e.g., position and velocity parameters).

The maximum and minimum ground altitudes (and maximum building heights) for a specific location region may be known. This information can be held in a database as a digital elevation model for the region and the maximum and minimum values can be extracted from the database. The maximum and minimum information can be encoded using a look up table for specific regions. For example, a cell-location based look up table could be used to store maximum and minimum altitudes for the region in which the cell is used. The GPS position estimation can utilize this information as an altitude inequality constraint.

The use of speed or velocity inequality constraints can be also useful for estimation. For cases when the user is driving, the maximum speed value (with some allowance for typical speeders) can be determined from a street map database limited to the likely region including the user position. As an example, given a point estimate of location in downtown San Francisco with an associated uncertainty region (e.g., assuming a 200 m circle), the maximum speed could be assessed based on road map data and an assumption of how much people typically speed (e.g., 50 km/hr speed limit+40 km/hr excess speed=90 km/hr a maximum speed). A maximum speed inequality constraint can then be communicated to the GPS receiver's estimation process. The receiver can enforce this constraint as an inequality constraint on the state estimator in the event that the speed estimate exceeds the maximum value. Further, given knowledge of a map-matched solution, mapping to a specific road, the inequality constraint could become a vectorized constraint (max velocity east, and ma velocity north or max velocity across-track and max velocity along track).

A database of roads is not required for utilizing speed inequality constraints. If the user activity context is known, by analysis of the devices accelerometer samples for example, this information can be used to limit the maximum speed of the GPS solution. If the user context is walking, then it is unlikely that the user is traveling faster than 30 km/hr. If the user context is running, then it is unlikely that the user is traveling faster than 50 km/hr.

Inequality constraints are useful in position and velocity estimation to contain the navigation solution's estimated states within expected boundaries. Often when these boundaries are exceeded, this indicates that something is wrong with the estimation and the problem is usually due to measurement outliers. When inequality constraints are applied, these measurement outliers can be detected and the result is a much more accurate estimation.

Inequality tests can be employed after the regular estimation method is complete. If an estimated state crosses a boundary, the estimation method can be performed again with a pseudo-measurement to force the solution to the expected boundary. For example, if the maximum value is exceeded, a pseudo-measurement at the minimum value can be used. This seems counterintuitive in that the pseudo-measurement is not the boundary value that was exceeded. The boundary value that was exceeded cannot be used because it would necessitate using a small pseudo-measurement variance. This method is considered an optimal method of applying inequality constraints because it adds a minimal amount of information to move the state to the boundary value. Inequality constraints can be employed with estimation methods including recursive least squares and EKF.

Exemplary Navigation System

FIG. 1is a block diagram of an exemplary navigation system100using an altitude inequality constraint to improve a navigation solution. System100can be included in a mobile device and used to provide location information to various applications running on the mobile device (e.g., map applications, location-based services). A mobile device is any device that uses GNSS technology to determine location, including but not limited to: portable computers, smart phones, electronic tablets and vehicle navigation systems. In some implementations, navigation system100can include GNSS receiver front end102(e.g., a GPS receiver), estimation module104, altitude constraint module106and digital elevation data108. One or more of estimation module104, altitude constraint module106and digital elevation data108can be included with GNSS receiver front end102in a GNSS receiver apparatus, such as a GPS receiver.

Estimation module104can be implemented in software or firmware that is executed by one or more hardware processors or processing cores in the GNSS receiver. Estimation module can also be implemented at least partially in hardware or a combination of hardware and firmware or in application software. In some implementations, estimation module104can use pseudo-range and delta-range (Doppler) measurements provided by a GNSS receiver (front end and baseband processor)102to determine a navigation solution for a mobile device. Estimation module104can implement well-known estimation techniques, including EKF and least-squares estimation, as discussed below in more detail.

Digital elevation data108can be stored locally on the mobile device or on a network device. An example of digital elevation data is a Geographic Information System (GIS) that uses position coordinates (or latitude, longitude) as a key index variable for elevation information.

In some implementations, altitude constraint module106receives a horizontal position estimate ({circumflex over (x)},ŷ) and a corresponding statistical uncertainty (σx2, σy2) associated with the horizontal position estimate. The position estimate and corresponding uncertainty can be taken from one or more previous position estimates computed by estimation module104. For example, a position estimate can be taken from the current state vector estimate of EKF or least-squares estimator and the position estimate uncertainty can be determined from the current state error covariance associated with the state vector estimates, which will be described in more detail below. Alternatively, the position estimate and corresponding position estimate uncertainty can be provided by an Inertial Navigation System (INS). The INS can obtain measurements from inertial sensors (e.g., accelerometers, gyro sensors, magnetometers) and compute a position estimate and corresponding position estimate uncertainty from the INS data using known techniques.

In some implementations, an average or mean of horizontal position estimates can be used to retrieve digital elevation data108. The mean and variance of position estimate component {circumflex over (x)} can be calculated from a number of past position estimates of {circumflex over (x)}. For example, for N values of {circumflex over (x)}, a mean μxand variance σx2can be computed by

A similar calculation can be made for the y coordinate. The position coordinates can be provided by estimation module104or the INS in a reference coordinate frame that is compatible with accessing digital elevation108from a database. Alternatively, the position coordinates can be transformed into any desired reference coordinate frame using an appropriate transformation matrix and known coordinate transformation techniques (e.g., cosine matrices, quaternions).

Altitude constraint module106uses the estimated position to index a database of digital elevation data108to find an elevation corresponding to the estimated position, as described in reference toFIG. 2below.

Determining Altitude Boundaries

FIG. 2is a two-dimensional contour plot200illustrating the determination of altitude inequality constraints. Contour plot200is a visual representation of map elevation data108. In the example shown, the position estimate204received from estimation module104is marked on contour plot200as a solid circle. An uncertainty region202surrounds position estimate204and the true position of the mobile device lies somewhere within uncertainty region202. Uncertainty region202can be determined by the horizontal components (e.g., East ({circumflex over (x)}) and North (ŷ) components) of the statistical uncertainty of position estimate204. For example, the variances (σx2, σy2) can be taken from the state error covariance matrix P and used by estimation module104to define uncertainty region202. In some implementations, these variances are provided by an INS system or other assisted GPS device or process.

Within uncertainty region202, there are points of minimum elevation206and a maximum elevation208, each of which is marked as a solid diamond. Thus, given position estimate204and uncertainty region202, altitude constraint module106determines the minimum and maximum altitudes hmin, hmaxwithin uncertainty region202. The determined minimum and maximum altitudes in uncertainty region202are used in an altitude inequality constraint to improve the navigation solution and/or for integrity monitoring of GNSS or INS measurements.

In the example shown, position estimate204is lying on the contour line for elevation of 2000 feet. The highest elevation in uncertainty region202is lying on the contour line (or within the region surrounded by the contour line) for elevation 2500 feet. The lowest elevation in uncertainty region202is lying on the contour line (or within the region surrounded by the contour line) for 1250 feet. Thus, in this example hminis between about 1250 and about 1500 feet and hmaxis about 2500 feet. In some implementations, digital elevation data108can be accessed from a database table of elevations that can be indexed by latitude and longitude. Interpolation techniques can be used to determine elevations that fall between table values. Portions of digital elevation data108can be downloaded periodically to the mobile device based on the current estimated location of the mobile device. The portions of digital elevation data can be stored in local cache of the mobile device.

The minimum and maximum altitudes hmin, hmaxdetermined by altitude constraint module106can be used as an altitude (height) inequality constraint in an EKF formulation, as described below in reference toFIGS. 3A-3C.

For discussion purposes, we assume the mobile device navigation state vector is given by
{right arrow over (x)}=[x,y,z,{dot over (x)},{dot over (y)},ż],[3]
where x, y and z, and {dot over (x)}, {dot over (y)}, ż, are the position and speed components of the mobile device in ENU Cartesian coordinates, respectively.

Letting hmin, hmaxrepresent the minimum and maximum altitudes in the uncertainty region202shown inFIG. 2, an altitude inequality constraint can be defined by
hmin≦{right arrow over (h)}{right arrow over (x)}≦hmax,  [4]
where {right arrow over (h)}=[0 0 1 0 0 0] is a measurement function. Note that matrices will hereafter be represented by bold capital letters.

The state vector {right arrow over (x)} and corresponding state error covariance P can be updated using well-known EKF formulations that include a prediction phase and a updating phase as follows:

B. Updating
Kk=Pk−HkT(HkPk−HkT+R)−1[7]
{right arrow over (x)}k+={right arrow over (x)}k−+Kk({right arrow over (y)}−H({right arrow over (x)}k−))  [8]
Pk+=(I−KkHk)Pk−,  [9]
where, Φ is a state transition matrix, Q is the system noise error covariance matrix, P is the state vector error covariance matrix, H is the Jacobian of the measurement function evaluated at the predicted state, K is the gain matrix, {right arrow over (y)}; is the actual measurement vector and R is the measurement noise error covariance matrix. The superscript “−” is the state before the measurement update and the superscript “+” is the state after measurement update.

The matrices described above are known in EKF formulations, and the derivation of elements of these matrices is based on the particular application that is employing the EKF formulations. Of particular interest is the computation of the z-component of the measurement noise model represented by the measurement noise, error covariance matrix R, which can be computed using the altitude inequality constraint of equation [4].

Applying Inequality Constraints Using EKF

The general method of applying inequality constraints to the EKF is well known. This method described below adds a minimal amount of information to the EKF to achieve the constraint and is thus optimal (it does not over-constrain the solution). The general method of applying inequality constraints using an EKF can be revised to improve the ability of the EKF to detect and remove measurement failures and thus improve the solution accuracy as well as bound the state to the inequality region. It is preferred to use a sequential method of updating the EKF, as described in equations [5]-[9] above.

FIGS. 3A-3Cis a flow diagram of an exemplary process300for applying inequality constraints using the EKF. Process300can be implemented by system100shown inFIG. 1.

In some implementations, process300can begin by storing the state vector and state covariance matrix after the EKF prediction step (302), as described by equations [5] and [6]. Process300can continue by performing the EKF measurement update step(s) with appropriate measurement fault detection and isolation techniques (304), as described by equations [6]-[9]. If the measurement updates are applied sequentially, then the inequality test is applied after each update (306). Otherwise, the inequality test is applied after the measurement update step (308). If the inequality test passes, then the solution is final and process300ends. If the inequality test fails for any update, the EKF state vector and covariance matrix (post-update) are stored for use in computing the inequality constraint (310). The EKF then reverts to the stored state vector and state variance covariance matrix after the EKF prediction step (312).

The inequality constraint is then applied as a pseudo-measurement update with an appropriate measurement variance (314). If the maximum value was exceeded, a pseudo-measurement at the minimum value can be used to update the EKF (316). The measurement innovation, υβ, and the measurement variance for this pseudo-measurement σβ2, can be given by:

vβ=βmin-β^-⁢⁢σβ2=Pkβα+⁢βmax-βminβ^+-βmax,[10]
where {circumflex over (β)}−is the value of the state after the EFK prediction step, {circumflex over (β)}+is the value of the state after the update step (which exceeds the maximum bias value), βminis the minimum value and also the value of the pseudo-measurement, Pkβα+is the element of the state covariance matrix after the update step corresponding to the state which has exceeded the maximum, and βmaxis the value of the pseudo-measurement.

If the minimum value was exceeded, a pseudo-measurement at the maximum value can be used to update the EKF (318). The measurement innovation, υβ, and the measurement variance for this pseudo-measurement, σβ2, can be given by:

vβ=βmax-β^-⁢⁢σβ2=Pkβα+⁢βmax-βminβmin-β^+,[11]
where βmaxis the value of the pseudo-measurement.

Process300can continue by performing the EKF measurement update step(s) with appropriate measurement fault detection and isolation techniques following the pseudo-measurement update (320). If a new combination of measurements results from the use of the pseudo-measurement constraint, the update steps can be performed again (from the stored filter after the EKF prediction step) with the set of measurements without fault detection and without the pseudo-measurement constraint to avoid over-constraining the solution (322). The inequality constraint can then be applied again if needed (324).

The impact of the pseudo-measurement when there is no change in the measurements used is that the state is moved to the expected maximum or minimum point. If different measurements are detected as measurement faults, then the state can be different from the boundary value. In many cases, the solution can be improved by the rejection of an outlier measurement, which improves the accuracy of the solution. However, it should be noted that the solution with the revised set of included measurements is potentially over-constrained unless the final iterative step is taken.

Applying Inequality Constraints Using Least-Squares Estimation

FIGS. 4A-4Cis a flow diagram of an exemplary process400for applying inequality constraints using least-squares estimation. Process400can be implemented by system100shown inFIG. 1.

In some implementations, process400can begin by performing regular least squares estimation with standard measurement fault detection and isolation (402). Once the solution has converged, the inequality test can be performed on the state (404). Next, the state can be checked to see if it is less than the expected minimum or larger than the expected maximum (406). If the inequality test fails, then the least squares estimation can be performed again using a pseudo measurement constraint (408). However, measurements identified as potential faults in the first least squares implementation are included in the second implementation because different measurements may be identified as faults based on the use of the inequality constraint pseudo-measurement.

If the maximum value is exceeded, a pseudo-measurement at the minimum value can be used (410). The measurement uncertainty for this pseudo-measurement can be Oven by

σβ2=Pkβα+⁢βmax-βminβ^-βmax,[12]
where {circumflex over (β)} is the value of the state after the least squares estimation (which now exceeds the maximum value), βminis the minimum value and also the value of the pseudo-measurement, Pkβα+is the element of the state covariance matrix corresponding to the state which has exceeded the maximum, and βmaxis the maximum value.

If the minimum value is exceeded, a pseudo-measurement at the maximum value is used (412). The measurement uncertainty for this pseudo-measurement is given by

σβ2=Pkβα+⁢βmax-βminβmin-β^,[13]
where {circumflex over (β)} is the value of the bias after an update step (which now exceeds the minimum bias value) and βmaxis the value of the pseudo-measurement.

Next, least squares estimation is performed again with a revised measurement set, fault detection steps and a pseudo measurement constraint (414). If a new combination of measurements results from the use of the pseudo-measurement constraint, to avoid over-constraining the solution least squares estimation can be run again with this revised measurement set, with fault detection steps and without the pseudo-measurement constraint (416). Process400can then continue to step402.

The impact of the pseudo-measurement on the estimation when there is no change in the measurements used is that the state is moved to the expected maximum or minimum point. If different measurements are detected as measurements faults, then the state can be different from the boundary value. In many cases, the solution will be improved a great deal by the rejection of an outlier measurement, which improves the accuracy of the solution. However, it should be noted that the solution, with the revised set of included measurements, are potentially over-constrained unless the final iterative step is taken.

Exemplary Hardware Architecture

FIG. 5is a block diagram of exemplary hardware architecture for a device implementing the features and processes described in reference toFIGS. 1-4. The device can include memory interface502, one or more data processors, image processors and/or processors504, and peripherals interface506. Memory interface502, processor(s)504and/or peripherals interface506can be separate components or can be integrated in one or more integrated circuits. The various components in the device, for example, can be coupled by one or more communication buses or signal lines.

Sensors, devices, and subsystems can be coupled to peripherals interface506to facilitate multiple functionalities. For example, motion sensor510, light sensor512, and proximity sensor514can be coupled to peripherals interface506to facilitate orientation, lighting, and proximity functions of the mobile device. Location processor515(e.g., GPS receiver) can be connected to peripherals interface506to provide geo-positioning. Electronic magnetometer516(e.g., an integrated circuit chip) can also be connected to peripherals interface506to provide data that can be used to determine the direction of magnetic North. Thus, electronic magnetometer516can be used as an electronic compass. Accelerometer517can also be connected to peripherals interface506to provide data that can be used to determine change of speed and direction of movement of the mobile device.

Camera subsystem520and an optical sensor522, e.g., a charged coupled device (CCD) or a complementary metal-oxide semiconductor (CMOS) optical sensor, can be utilized to facilitate camera functions, such as recording photographs and video clips.

Communication functions can be facilitated through one or more wireless communication subsystems524, which can include radio frequency receivers and transmitters and/or optical (e.g., infrared) receivers and transmitters. The specific design and implementation of the communication subsystem524can depend on the communication network(s) over which a mobile device is intended to operate. For example, a mobile device can include communication subsystems524designed to operate over a GSM network, a GPRS network, an EDGE network, a WiFi or WiMax network, and a Bluetooth network. In particular, the wireless communication subsystems524can include hosting protocols such that the mobile device can be configured as a base station for other wireless devices.

Audio subsystem526can be coupled to a speaker528and a microphone530to facilitate voice-enabled functions, such as voice recognition, voice replication, digital recording, and telephony functions.

I/O subsystem540can include touch screen controller542and/or other input controller(s)544. Touch-screen controller542can be coupled to a touch screen or surface546. Touch screen or surface546and touch screen controller542can, for example, detect contact and movement or break thereof using any of a plurality of touch sensitivity technologies, including but not limited to capacitive, resistive, infrared, and surface acoustic wave technologies, as well as other proximity sensor arrays or other elements for determining one or more points of contact with touch screen546.

Other input controller(s)544can be coupled to other input/control devices548, such as one or more buttons, rocker switches, thumb-wheel, infrared port, USB port, and/or a pointer device such as a mouse or stylus. The one or more buttons (not shown) can include an up/down button for volume control of speaker528and/or microphone530. In one implementation, the user may be able to customize a functionality of one or more of the buttons. For example, the touch screen546can also be used to implement virtual or soft buttons and/or a virtual keyboard.

In some implementations, the device can present recorded audio and/or video files, such as MP3, AAC, and MPEG files. In some implementations, the device can include the functionality of an MP3 player. The device may include a pin connector that is compatible with accessories.

Memory interface502can be coupled to memory550. Memory550can include high-speed random access memory and/or non-volatile memory, such as one or more magnetic disk storage devices, one or more optical storage devices, and/or flash memory (e.g., NAND, NOR). Memory550can store operating system552, such as Darwin, RTXC, LINUX, UNIX, OS X, WINDOWS, or an embedded operating system such as VxWorks. Operating system552may include instructions for handling basic system services and for performing hardware dependent tasks. In some implementations, operating system552can include a kernel (e.g., UNIX kernel).

Memory550may also store communication instructions554to facilitate communicating with one or more additional devices, one or more computers and/or one or more servers. Memory550may include graphical user interface instructions556to facilitate graphic user interface processing; sensor processing instructions558to facilitate sensor-related processing and functions; phone instructions560to facilitate phone-related processes and functions; electronic messaging instructions562to facilitate electronic-messaging related processes and functions, such as SMS and MMS; web browsing instructions564to facilitate web browsing-related processes and functions; media processing instructions566to facilitate media processing-related processes and functions; GPS/Navigation instructions568to facilitate GPS and navigation-related processes and instructions, such as the processes described in reference toFIGS. 1-4; and camera instructions570to facilitate camera-related processes and functions. The memory550may also store other software instructions (not shown), such as security instructions, web video instructions to facilitate web video-related processes and functions, and/or web-shopping instructions to facilitate web shopping-related processes and functions.

Memory550can include instructions for magnetometer calibration572and associated calibration data574, as well as other instructions576for implementing various applications for using navigation solutions, such as mapping applications and location based service applications.

One or more features or steps of the disclosed embodiments can be implemented using an Application Programming Interface (API). An API can define on or more parameters that are passed between a calling application and other software code (e.g., an operating system, library routine, function) that provides a service, that provides data, or that performs an operation or a computation.

The API can be implemented as one or more calls in program code that send or receive one or more parameters through a parameter list or other structure based on a call convention defined in an API specification document. A parameter can be a constant, a key, a data structure, an object, an object class, a variable, a data type, a pointer, an array, a list, or another call. API calls and parameters can be implemented in any programming language. The programming language can define the vocabulary and calling convention that a programmer will employ to access functions supporting the API.

In some implementations, an API call can report to an application the capabilities of a device running the application, such as input capability, output capability, processing capability, power capability, communications capability, etc.