CN108700421B

CN108700421B - Method and system for assisting enhanced portable navigation using offline map information

Info

Publication number: CN108700421B
Application number: CN201680082307.8A
Authority: CN
Inventors: T·李; J·乔吉; D·王; S·毛; H·萨利
Original assignee: InvenSense Inc
Current assignee: InvenSense Inc
Priority date: 2015-12-21
Filing date: 2016-12-07
Publication date: 2022-05-27
Anticipated expiration: 2036-12-07
Also published as: US10018474B2; US20170176191A1; EP3414524A1; CN108700421A; WO2017112414A1

Abstract

Map information may be used to enhance navigation solutions for portable devices. Sensor data of the portable device may be used to derive a navigation solution for a plurality of epochs within a first time period. The navigation solution may be used to estimate location information of the device at a time after the first time period. Map information for an area containing the current location of the portable device may also be obtained. Multiple hypotheses about possible locations of the portable device may be generated using the estimated location information and the map information. By managing and processing the hypotheses, estimated location information for at least one epoch during the first time period may be updated. An enhanced navigation solution for the at least one time period may be provided using the updated estimated location information.

Description

Method and system for assisting enhanced portable navigation using offline map information

Cross Reference to Related Applications

This application claims priority and benefit from U.S. patent application No.14/976,992 entitled "METHOD AND SYSTEM FOR USING NAVIGATION MAP INFORMATION AIDED ENHANCED PORTABLE NAVIGATION" filed on 21/12/2015.

Technical Field

The present disclosure relates to a method and system for subsequently enhancing at least one navigation solution derived from sensor data of a device within a platform (such as, for example, a person, vehicle or vessel) by using map assistance and/or map constraints on the navigation solution, wherein the device may be bundled or unbundled to the platform, and wherein in the case of unbundled, the mobility of the device may be constrained or unconstrained within the platform, and wherein the device may be tilted to any orientation and still provide seamless navigation.

Background

Portable electronic devices, such as those configured to be handheld or otherwise associated with a user, are used in a wide variety of applications and environments. These devices are increasingly equipped with one or more sensors or other systems for determining the position or movement of the portable device. Notably, a device such as a smartphone, tablet, smart watch, or other portable device may have the following features: a Global Navigation Satellite System (GNSS) receiver, a low cost micro-electromechanical system (MEMS) inertial sensor, a barometer, and a magnetometer. GNSS and multisensors can be integrated to provide promising positioning results in most outdoor environments. However, some mass-market applications require seamless location capabilities in various environments, such as malls, offices, or underground parking lots. Without GNSS signals in an indoor environment, conventional Strapdown Inertial Navigation Systems (SINS) using low cost inertial sensors suffer significant performance degradation due to accumulated sensor drift and bias. Thus, positioning techniques relying solely on motion sensors may not meet all the requirements of seamless indoor and outdoor navigation applications.

Pedestrian Dead Reckoning (PDR) is an example of portable device indoor/outdoor positioning technology and has recently become the focus of industrial and academic research. Similar to SINS, PDR accumulates successive displacements from known starting points to derive position. The displacement (step size) can be estimated within a certain accuracy using inertial sensor measurements with various algorithms. The position error using the step size from the PDR accumulates much slower than the position error from the accelerometer-derived displacement of the SINS. Without GNSS updates, PDR shows better performance than SINS. However, PDR still lacks robustness due to accumulated heading error. This disadvantage may lead to skewed paths over time and produce position estimates that may not be consistent with the building layout. Thus, the resulting navigation trajectory may pass through a wall, floor, or other obstruction. To avoid these types of navigation trajectories being inconsistent with the building layout, the PDR solution may be constrained to the area indicated as a possible path using the map information, or the determined location may be updated to match an assumed location derived from the map information. As used herein, the map assistance techniques of the present disclosure include either or both of constraining the derived location of the user or updating the derived location to a location determined from map information.

As described above, map information can be used to improve the reliability and positioning accuracy of a navigation system. In order to use map information in a navigation system, various map assistance algorithms have been proposed and applied in the related art. Map-aided algorithms can be generally divided into four categories: geometry, topology, probability, and other advanced techniques.

Geometric map assistance algorithms typically only consider the geometric relationship between the user's location and the map. They are widely used in vehicle navigation applications, where a spatial road network is abstracted into nodes and curves. The most common geometric map-assist algorithm is a point-to-point assist technique that matches the user location with the closest node of the road segment. While easy to implement, it is sensitive to the way the road network is digitized. Another geometric map-assist algorithm is point-to-curve assist. This technique matches the user location to the closest curve of the road. Each curve includes line segments that are linear segment by segment. The distance from the user position to each line segment may be calculated. The line segment giving the smallest distance is selected as the matching road. While it is more efficient than point-to-point assistance, it may be unstable in dense road networks. Another geometric algorithm is curve-to-curve assist, which matches a short history of user trajectories with road curves, and may select a road curve with the shortest distance to a user trajectory. Unfortunately, this method is very sensitive to outliers and therefore often gives unexpected results.

In addition to utilizing basic geometric information, the topological map assistance algorithm also utilizes historical user trajectory information (which may include previously identified road segments) and topological information, such as route connectivity, road classification, road restriction information (one-way, turn restriction). Various previous works have applied topology information at different levels. For example, (i) a set of candidate routes is identified using the topology information, (ii) and the correct route is identified from the set of candidate routes. Therefore, topological map-assist algorithms generally outperform algorithms that rely solely on geometric techniques. In addition, the weight-based topological map can further improve the matching assistance performance. These techniques use correlation values in network geometry and topology information and positioning information from the GPS/DR integrated system as weights for different road route candidates. The route with the highest weight score may be selected as the correct road segment. However, a false identification of a road route in a previous period may have a significant negative impact on the subsequent map assistance results.

Conventional probabilistic map assistance algorithms use an error ellipse or rectangular area around the user's location from the navigator. The error zone depends on the variance of the estimated navigation position. The error zone is then superimposed on the road network to identify the road segment on which the user is traveling. If the error zone contains multiple segments, the evaluation of the candidate segments is performed using heading, connectivity, and proximity criteria. To improve computational efficiency and system reliability, the error zone may be constructed only when the user crosses the intersection. This is because the construction of the error zone at each time period may result in incorrect route identification when other road routes are close to the route the user is traveling.

Advanced map-aided algorithms typically involve more advanced techniques such as kalman filters, particle filters, fuzzy logic models, or bayesian inference. For example, a Kalman filter may be used to propagate the user's position from GPS or GPS/DR and re-estimate the user's position by matching the position using an orthographic projection map to reduce along-track errors. Similar concepts may also be used with particle filters to predict and update the user's location. Further, the fuzzy inference system may be used to derive a matching road route, where i) the distance between the user location and the candidate route and ii) the difference between the platform direction and the route direction. Another example is map assistance using multi-hypothesis technology (MHT) by taking pseudo-measurements (projected location and heading) of all possible routes within a verification area from the current user location and topological analysis of the road network to derive a set of hypotheses and probabilities.

Although there are various conventionally available map-assist algorithms, whether geometric, topological, probabilistic, or advanced, they can be considered to be based on the assumption that the user is constrained to the road network (which can be abstracted as connected points, lines, and curves). While this assumption may be sufficiently effective in many outdoor land vehicle navigation applications, problems may be encountered in complex indoor environments where rooms, elevators, hallways and similar structures cannot be reduced to the above-described points, lines and curves. Some researchers use particle filters with geometric constraint (walls, hard-to-reach areas) information from building plans to improve indoor positioning accuracy, however, users can enter or leave rooms in a random manner, and simple geometric constraints are not desirable in these scenarios. Furthermore, this technique has not been adapted to multi-floor situations. In contrast, conventional multi-floor map assistance techniques rely solely on geometric information to identify the location of stairs. These methods may not be reliable enough, especially when drift occurs in the navigation solution. Furthermore, most existing map assistance algorithms ignore user motion state information. The user's motion state (such as going up/down stairs, standing/walking on an escalator, or using an elevator) is useful for verifying candidate matching level change routes or objects in indoor navigation applications. While advanced algorithms such as fuzzy logic or particle filters have the potential to provide improved performance, they may not generally be suitable for real-time or causal applications due to the heavy computational burden.

It is therefore desirable to provide navigation techniques using available map information, in particular indoor maps, to enhance the accuracy and reliability of the positioning application of portable devices. It is also desirable to provide map information assistance techniques that operate well in a seamless outdoor-to-indoor transition and handling multi-level indoor maps to reliably navigate users in complex multi-level indoor environments. It is also desirable to provide map information assistance techniques that can be subsequently applied to benefit from post-information and processing techniques. Further, it would be desirable to provide map-assist techniques adapted for efficient operation in both client and server modes that enhance one or more solutions by enabling a server to subsequently generate results of map matching using a user's uploaded navigation solution. The present disclosure satisfies these and other needs, as will be described in the following material.

Disclosure of Invention

As will be described in detail below, the present disclosure includes a method for enhancing a navigation solution for portable devices and platforms using map information, where mobility of the device is constrained or unconstrained within the platform, and where the device may be tilted to any orientation. The method can comprise the following steps: obtaining sensor data for the portable device, the sensor data representing movement of the portable device over a plurality of periods within a first time period; deriving a navigation solution for the epoch based at least in part on the sensor data; estimating location information of the portable device based at least in part on the plurality of navigation solutions at a time after the first time period; obtaining map information for an area containing a location of the portable device during a first time period; generating a plurality of hypotheses regarding possible locations of the portable device for at least one time period during the first time period based at least in part on the estimated location information and the map information; managing hypotheses based at least in part on the estimated location information and map information; processing the managed hypotheses to update estimated location information of the portable device; and providing an enhanced navigation solution for at least one time period using the updated estimated location information.

The present disclosure also includes a portable device having: an integrated sensor assembly that can output sensor data for a plurality of periods of a portable device within a first time period, the sensor data representing motion of the portable device; a navigation module configured to derive a navigation solution based at least in part on sensor data over a plurality of sensor epochs; and a processor, the processor may implement: a location estimator to provide estimated location information of the portable device based at least in part on a plurality of navigation solutions at a time after the first time period; a map handler to obtain map information for an area containing a location of the portable device during a first time period; and a hypothesis analyzer to generate and manage a plurality of hypotheses regarding possible locations of the portable device for at least one time period during the first time period based at least in part on the estimated location information and the map information, such that the processor may update the estimated location information of the portable device based at least in part on the managed hypotheses to provide an enhanced navigation solution for the at least one time period using the updated estimated location information.

The present disclosure also includes a server for augmenting a navigation solution for a portable device and a platform using map information, wherein mobility of the portable device is constrained or unconstrained within the platform, and wherein the portable device can be tilted to any orientation. The server may include a communication module to receive information provided by the portable device, wherein the information corresponds to sensor data representative of motion of the portable device for a plurality of time periods during a first time period, and a processor that may implement: a location estimator to provide estimated location information of the portable device at a time after the first time period based at least in part on a plurality of navigation solutions derived for the time period; a map handler to obtain map information for an area containing a location of the portable device during a first time period; and a hypothesis analyzer to generate and manage a plurality of hypotheses regarding possible locations of the portable device for at least one time period during the first time period based at least in part on the estimated location information and the map information, such that the processor may update the estimated location information of the portable device based at least in part on the managed hypotheses to provide an enhanced navigation solution for the at least one time period using the updated estimated location information.

Still further, the present disclosure includes a system for providing an enhanced navigation solution using map information. The system may have a portable device having: an integrated sensor assembly configured to output sensor data for a plurality of periods of the portable device within a first time period, the sensor data being representative of motion of the portable device; a communication module to transmit information corresponding to the time period. The system may also include a remote processing resource to receive information from the portable device and a processor to implement: a location estimator to provide estimated location information of a portable device at a time after the first time period based at least in part on a plurality of navigation solutions of the portable device derived for each time period; a map handler to obtain map information for an area containing a location of the portable device during a first time period; and a hypothesis analyzer to generate and manage a plurality of hypotheses regarding possible locations of the portable device for at least one time period during the first time period based at least in part on the estimated location information and the map information, such that the processor may update the estimated location information of the portable device based at least in part on the managed hypotheses to provide an enhanced navigation solution for the at least one time period using the updated estimated location information.

Drawings

Fig. 1 is a schematic diagram of a system for offline augmentation of navigation solutions, according to an embodiment.

FIG. 2 is a flow diagram of a routine for enhancing a navigation solution with offline map information, according to an embodiment.

Fig. 3 is a schematic representation of functional blocks for performing offline map matching to enhance a navigation solution of a portable device, according to an embodiment.

Fig. 4 is a schematic representation of an input handler for performing offline map matching to enhance a navigation solution of a portable device, according to an embodiment.

Fig. 5 is a schematic representation of a map entity crop in a geometric map, according to an embodiment.

Fig. 6 is a schematic representation of a grid map according to an embodiment.

Fig. 7 is a schematic representation of an error ellipse used in generating assumptions, according to an embodiment.

Fig. 8 is a schematic representation of an error ellipse projected onto a map entity, according to an embodiment.

Fig. 9 is a schematic representation of an error ellipse in a hallway scene with gate information, under an embodiment.

Fig. 10 is a schematic representation of an error ellipse in a hallway scene without gate information, under an embodiment.

Fig. 11 is a schematic representation of comparing navigation solutions in a horizon-changing scenario, according to an embodiment.

FIG. 12 is a schematic representation comparing navigation solutions after heading oscillation cancellation, according to an embodiment.

13-17 are schematic representations of comparing trajectories established from a navigation solution and an enhanced navigation solution in a retail location, according to an embodiment.

Fig. 18-26 are schematic representations of using forward and reverse processing in a retail location to provide an enhanced navigation solution, according to an embodiment.

Fig. 27 is a schematic diagram of another system for offline augmentation of navigation solutions, according to an embodiment.

Fig. 28 is a schematic diagram of an apparatus for offline augmentation of navigation solutions, according to an embodiment.

Detailed Description

First, it is to be understood that this disclosure is not limited to the particular illustrated materials, architectures, methods or structures, as these may vary. Thus, although many such options similar or equivalent to those described herein can be used in the practice or embodiments of the present disclosure, the preferred materials and methods are described herein.

It is also to be understood that the terminology used herein is for the purpose of describing particular embodiments of the disclosure only and is not intended to be limiting.

The detailed description set forth below in connection with the appended drawings is intended as a description of exemplary embodiments of the present disclosure and is not intended to represent the only exemplary embodiments in which the present disclosure may be practiced. The term "exemplary" used throughout this description is intended to serve as "an example, instance, or illustration," and should not necessarily be construed as preferred or advantageous over other exemplary embodiments. The detailed description includes specific details for the purpose of providing a thorough understanding of the exemplary embodiments of the present description. It will be apparent to one skilled in the art that the exemplary embodiments of the present description may be practiced without these specific details. In some instances, well-known structures and devices are shown in block diagram form in order to avoid obscuring the novelty of the exemplary embodiments presented herein.

Directional terminology, such as top, bottom, left, right, up, down, back, and front, may be used with respect to the drawings or chip embodiments for convenience and clarity only. These and similar directional terms should not be construed to limit the scope of the present disclosure in any way.

In the description and claims, it will be understood that when an element is referred to as being "connected to" or "coupled to" another element, it can be directly connected or coupled to the other element or intervening elements may be present. In contrast, when an element is referred to as being "directly connected to" or "directly coupled to" another element, there are no intervening elements present.

Some portions of the detailed description which follow are presented in terms of procedures, logic blocks, processing, and other symbolic representations of operations on data bits within a computer memory. These descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. In this application, a procedure, logic speed, process, etc., is conceived to be a self-consistent sequence of steps or instructions leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated in a computer system.

It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present application, discussions utilizing terms such as "accessing," "receiving," "sending," "using," "selecting," "determining," "normalizing," "multiplying," "averaging," "monitoring," "comparing," "applying," "updating," "measuring," "obtaining," or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

The embodiments described herein may be discussed in the general context of processor-executable instructions that reside on some form of non-transitory processor-readable storage medium, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The functionality of the program modules may be combined or distributed as desired in various embodiments.

In the figures, individual blocks may be described as performing one or more functions; however, in actual practice, one or more of the functions performed by the block may be performed by a single component or across multiple components, and/or may be performed using hardware, using software, or using a combination of hardware and software. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present disclosure. Moreover, an exemplary wireless communication device may include components in addition to those shown, including well-known components such as processors, memory, and the like.

The techniques described herein may be implemented in hardware, software, firmware, or any combination thereof unless specifically described as being implemented in a particular manner. Any features described as modules or components may also be implemented together in an integrated logic device or separately as discrete but interoperable logic devices. If implemented in software, the techniques may be realized at least in part by a non-transitory processor-readable storage medium comprising instructions that, when executed, perform one or more of the methods described above. The non-transitory processor-readable data storage medium may form part of a computer program product that may include packaging materials.

The non-transitory processor-readable storage medium may include Random Access Memory (RAM), such as Synchronous Dynamic Random Access Memory (SDRAM), Read Only Memory (ROM), non-volatile random access memory (NVRAM), Electrically Erasable Programmable Read Only Memory (EEPROM), flash memory, other known storage media, and the like. Additionally or alternatively, the techniques may be realized at least in part by a processor-readable communication medium that carries or communicates code in the form of instructions or data structures and that can be accessed, read, and/or executed by a computer or other processor. For example, a carrier wave can be employed to carry computer-readable electronic data such as those used in transmitting and receiving electronic mail or in accessing a network such as the Internet or a Local Area Network (LAN). Of course, many modifications may be made to this configuration without departing from the scope or spirit of the claimed subject matter.

The various illustrative logical blocks, modules, circuits, and instructions described in connection with the embodiments disclosed herein may be executed by one or more processors, such as one or more Motion Processing Units (MPUs), Digital Signal Processors (DSPs), general purpose microprocessors, Application Specific Integrated Circuits (ASICs), application specific instruction set processors (ASIPs), Field Programmable Gate Arrays (FPGAs), or other equivalent integrated or discrete logic circuitry. The term "processor," as used herein, may refer to any of the foregoing structure or any other structure suitable for implementation of the techniques described herein. Further, in some aspects, the functions described herein may be provided within dedicated software modules or hardware modules configured as described herein. Moreover, these techniques may be fully implemented in one or more circuits or logic elements. A general purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of an MPU and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with an MPU core, or any other such configuration.

Unless otherwise defined, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this disclosure pertains.

Finally, as used in this specification and the appended claims, the singular forms "a," "an," and "the" include plural referents unless the content clearly dictates otherwise.

The technology of the present disclosure is directed to enhancing navigation solutions of portable devices using map information. Typically, such portable devices may be associated with a platform of a delivery device. The platform may be a user, as in the example of a smartphone that is carried while the user walks, runs, swims, or otherwise experiences motion. The platform may also be considered a vehicle or vessel that transports the user and the portable device. Although the portable device may be generally transported or transported in the direction of movement of the platform, its orientation may be unconstrained. Returning to the example of a smartphone, it may be held in a user's hand and used in various orientations or carried in a pocket, holster, bag, or other manner. In other examples, the portable device may be strapped to the platform, such as with a vehicle mount, or may be unbundled. When not bundled, the mobility of the device may or may not be constrained within the platform, and therefore, there may be situations where: the device may be tilted to any orientation relative to the user or the platform. The portable device may generate a series of navigation solutions over a given period of time.

By way of illustration only and not limitation, a user may carry a smartphone while traversing a venue, such as shopping in a store. During this time, the smartphone may derive a plurality of navigation solutions representing the user's trajectory through the store. In one aspect, the smartphone may use any suitable real-time techniques to generate those navigation solutions, including inertial navigation routines employing dead reckoning, reference-based location services utilizing sources of absolute navigation information, location beacon systems, or any other suitable technique or combination thereof. Despite substantial benefits, these real-time solutions may still suffer from inaccuracies or limitations. Also without limitation, inertial dead reckoning systems may suffer from drift over time due to the characteristics of currently employed sensors or sources of absolute navigation information such as Global Navigation Satellite Systems (GNSS) may suffer from poor reception in indoor environments.

Accordingly, the techniques of this disclosure utilize a series of navigation solutions derived over a given time period at a subsequent time to enhance at least one of the navigation solutions through an offline map matching routine. For example, location information of the portable device may be estimated after the solution is derived. When a navigation solution is derived, multiple hypotheses may be generated and managed using the estimated location information and map information for an area corresponding to the area occupied by the user. Based on these assumptions, the estimated location information can be updated and used to enhance at least one of the navigation solutions.

As will be described in further detail below, techniques for enhancing navigation solutions for portable devices and platforms using map information involve obtaining sensor data for the portable device. The portable device derives a navigation solution using the sensor data. Subsequently, an offline map matching routine may be performed to enhance at least one of the navigation solutions. In some embodiments, the portable device may have sufficient processing power and/or other resources available to execute the offline map matching routine locally (such as in the background when greater access to processing power is available). However, in other embodiments, the portable device may transmit the navigation solution (which may include any or all of the associated sensor data) to a remote server, which may have greater processing power and/or better access to map information to be used in an offline map matching routine. After enhancement, the navigation solution may be used for any suitable purpose and need not be directly related to the user, such as for analyzing consumer metrics and behavior. However, the enhanced navigation solution(s) may also be returned to the portable device, again for any suitable purpose, such as providing more accurate navigation information about the trajectory to the user or helping to improve future navigation performance of the portable device.

To help demonstrate these aspects, a representative system for offline map matching is schematically depicted in FIG. 1, in which a portable device 100 is represented by a high-level schematic block. As will be appreciated, the device 100 may be implemented as a device or apparatus, such as a handheld device, that may be moved in space by a user and thereby sense its motion, position, and/or orientation in space. For example, such a handheld device may be a mobile phone (e.g., a smartphone, a cellular phone, a phone running on a local network, or any other telephone handset), a tablet, a Personal Digital Assistant (PDA), a video game console, a video game controller, a navigation device, a wearable device (e.g., glasses, watches, belt clips), a fitness tracker, a virtual or augmented reality device, a Mobile Internet Device (MID), a Personal Navigation Device (PND), a digital camera, a digital camcorder, binoculars, a telephoto lens, a portable music, video or media player, a remote control, or other handheld device, or a combination of one or more of these devices.

As shown, device 100 includes a host processor 102, which may be one or more microprocessors, Central Processing Units (CPUs), or other processors for running software programs, which may be stored in memory 104, associated with the functions of device 100. The software layers may be provided in memory 104, which may be any combination of computer-readable media (e.g., electronic memory) or other storage media (e.g., hard disk, optical disk) for use with host processor 102. For example, the device 100 may be provided with an operating system layer to control and manage system resources in real-time, implement the functions of application software and other layers, and interface application programs with other software and functions of the device 100. Similarly, different software applications may be provided, such as menu navigation software, games, camera function controls, navigation software, communication software (such as telephone or Wireless Local Area Network (WLAN) software), or any of a wide variety of other software interfaces and functional interfaces. In some embodiments, multiple different applications may be provided on a single device 100, and in some of these embodiments, multiple applications may run simultaneously.

The apparatus 100 includes so as to integrate a Motion Processing Unit (MPU)^TM)106, the integrated motion processing unit 106 featuring a sensor processor 108, a memory 110, and inertial sensors 112. The memory 110 may store algorithms, routines, or other instructions for processing data output by the inertial sensor 112 and/or other sensors as described below using logic or a controller of the sensor processor 108, as well as storing raw data and/or motion data output by the inertial sensor 112 or other sensors. The inertial sensor 112 may be one or more sensors for measuring the motion of the device 100 in space. Depending on the configuration, the MPU 106 measures one or more rotational axes and/or one or more acceleration axes of the device. In one embodiment, the inertial sensor 112 may comprise a rotational motion sensor or a linear motion sensor. For example, the rotational motion sensor may be a gyroscope for measuring angular velocity along one or more orthogonal axes, and the linear motion sensor may be an accelerometer for measuring linear acceleration along one or more orthogonal axes. In one aspect, three gyroscopes and three accelerometers may be employed such that a sensor fusion operation performed by the sensor processor 108 or other processing resource of the device 100 combines data from the inertial sensors 112 to provide a six-axis motion determination. As desired, the inertial sensor 112 may be implemented using a micro-electromechanical system (MEMS) to be integrated with the MPU 106 in a single package. Exemplary details regarding suitable configurations of the main processor 102 and MPU 106 can be found in co-pending co-owned U.S. patent application No.11/774,488 filed on 6.7.2007 and U.S. patent application No.12/106,921 filed on 11.4.2008, which are hereby incorporated by reference in their entirety. Can be obtained from Senneville, CaliforniaA suitable implementation of MPU 106 in device 100 is available from invansense corporation.

Alternatively or additionally, the device 100 may implement the sensor assembly in the form of an external sensor 114. This is optional and not required for all embodiments. The external sensor may represent one or more sensors as described above, such as an accelerometer and/or gyroscope, which output data used in deriving the navigation solution. As used herein, "external" refers to a sensor that is not integrated with MPU 106 and may be remote or local to device 100. Also alternatively or additionally, the MPU 106 may receive data from auxiliary sensors 116 configured to measure one or more aspects related to the environment surrounding the device 100. This is optional and not required for all embodiments. For example, barometers and/or magnetometers may be used to improve position determination with the inertial sensors 112. In one embodiment, the auxiliary sensors 116 may include magnetometers that measure along three orthogonal axes, and the output is to be fused with gyroscope and accelerometer inertial sensor data to provide data for nine-axis motion determination. In another embodiment, the auxiliary sensors 116 may also include a barometer for providing an altitude determination that may be fused with other sensor data to provide a ten-axis motion determination. Although the techniques of this disclosure are described in the context of one or more sensors being MEMS-based, the techniques may be applied to any sensor design or implementation.

In the illustrated embodiment, host processor 102, memory 104, MPU 106, and other components of device 100 may be coupled by a bus 118, which may be any suitable bus or interface, such as a peripheral component interconnect express (PCIe) bus, a Universal Serial Bus (USB), a universal asynchronous receiver/transmitter (UART) serial bus, a suitable Advanced Microcontroller Bus Architecture (AMBA) interface, an inter-integrated circuit (I2C) bus, a Serial Digital Input Output (SDIO) bus, a Serial Peripheral Interface (SPI), or other equivalents. Depending on the architecture, different bus configurations may be employed as desired. For example, additional buses may be used to couple the various components of device 100, such as by using a dedicated bus between host processor 102 and memory 104.

In one aspect, the various operations of the present disclosure for deriving a navigation solution for the portable device 100 may be implemented by the navigation module 120 as a suitable set of instructions stored in the memory 104, which may be read and executed by the main processor 102. The navigation module 120 may employ a reference-based policy, a self-contained policy, or any combination of policies to provide any desired degree of location awareness. For example, the navigation module 120 may employ inertial navigation techniques that utilize sensor data (e.g., from the inertial sensors 112 and/or the external sensors 114) as obtained for the current sensor epoch to derive the navigation solution for that epoch. These techniques may involve dead reckoning, etc., and may determine the orientation of the device 100, including values such as any roll, pitch, and bearing (heading) angles. The navigation solution derived by the navigation module 120 represents a simultaneous determination of the location information of the portable device 100. While some transmission time, some possible buffering time, and processing time may be required, the result is at least near real-time (there may be some possible delay) and any available information may be used until such time as the solution is derived. Still further, the navigation module 120 may also be configured to determine motion patterns indicative of a user's motion patterns, which may include, but are not limited to, walking, driving, running, going up/down stairs, riding an elevator, walking/standing on an escalator, and other similar motion patterns. In some embodiments, the navigation module 120 may employ a real-time map matching routine to assist in the derivation of navigation solutions in a causal manner.

The navigation module 120 may also use sources of absolute navigation information 122 in deriving navigation solutions, such as Global Navigation Satellite System (GNSS) receivers including, but not limited to, Global Positioning System (GPS), global navigation satellite system (GLONASS), galileo and/or beidou, and WiFi^TMLocation, cell tower location, bluetooth location beacon, or other similar methods. This is optional andand not required in all embodiments. Navigation module 120 may also be configured to use information from wireless communication protocols to provide position determination using signal trilateration. Any suitable protocol may be employed, including cellular-based and Wireless Local Area Network (WLAN) technologies such as Universal Terrestrial Radio Access (UTRA), Code Division Multiple Access (CDMA) networks, global system for mobile communications (GSM), Institute of Electrical and Electronics Engineers (IEEE)802.16(WiMAX), Long Term Evolution (LTE), IEEE802.11 (WiFi)^TM) And others. In addition, the portable device 100 may also have a communication module 124 for sending and/or receiving information, including navigation solutions derived by the navigation module 120.

Multiple software layers may be employed as desired and may be stored in any combination of memory 104, memory 110, or other suitable location. For example, the motion algorithm layer may provide motion algorithms that provide low-level processing of raw sensor data provided from motion sensors and other sensors. The sensor device driver layer may provide a software interface to the hardware sensors of the device 100. Further, an appropriate Application Program Interface (API) may be provided to facilitate communication between the main processor 102 and the MPU 106, for example, to transmit desired sensor processing tasks.

In this exemplary system, the portable device 100 transmits raw sensor data or navigation solutions derived for a plurality of sensor periods within a first time period to the server 126. After the first time period, the server 126 may then perform an offline map matching routine in accordance with the techniques of this disclosure using the navigation solution from the portable device 100 to provide an enhanced navigation solution for at least one of the sensor periods. One suitable architecture for the server 126 is depicted in FIG. 1 using high-level schematic blocks, and may include a server processor 128 in communication with memory 130 over a bus 132. As will be described in further detail below, the server processor 128 may execute instructions stored in the memory 130, represented as functional blocks, including a location estimator 134, a hypothesis analyzer 136, a map handler 138, an input handler 140, and an anchor manager 142. The location estimator 134 may estimate the location information of the portable device 100 using the navigation solution for multiple sensor periods provided by the navigation module 120. The estimated location information may also be updated using information from the hypothesis analyzer 136, and the hypothesis analyzer 136 may be configured to generate, evaluate, and combine multiple hypotheses regarding possible locations of the portable device 100 using the estimated location and the information from the map handler 138. It is assumed that analyzer 136 may also be configured to analyze the navigation solution and determine a movement pattern indicative of a movement pattern of the user in a manner similar to that described above with respect to navigation module 120. Either or both of the navigation module 120 and the hypothesis analyzer 136 may determine the motion pattern, but the hypothesis analyzer may have advantages associated with the availability of past and future information for motion detection at a given time and/or may have greater processing resources available for more complex algorithms to execute, and may be given greater weight accordingly if there is a conflicting detection. In turn, the map handler 138 may be configured to access external information about the area containing the location of the portable device 100 when the solution is derived, and present the information in a form assumed to be available to the analyzer 136. The input handler 140 may perform preliminary processing of the navigation solution derived by the navigation module 120, including filtering, classifying motion segments, and/or detecting motion characteristics. Anchor manager 142 may identify one or more anchors having known location information that may be associated with one or more of the navigation solutions.

The output from the hypothesis analyzer 136 may be used by the location estimator to update the estimated location information by processing the generated hypotheses, such as combining using appropriate weighting and averaging, selecting a selected hypothesis, selecting a set of hypotheses and combining the hypotheses using only appropriate weighting and averaging, or other suitable operation. The estimated location information and/or the updated estimated location information may include speed and/or heading information in addition to location information, as well as any other information related to the motion or location of the device 100, and may also include map entity information. The updated estimated position may then be used as an enhanced navigation solution for the at least one sensor epoch, or may be fed back to the navigation module 120 for use in deriving an enhanced navigation solution for the at least one epoch. In some embodiments, values from the updated estimated location information and navigation solution may be used in an enhanced navigation solution.

The server 126 may also include a communication module 144 for receiving raw sensor data or navigation solutions of the portable device 100 derived by the navigation module 120 and, if desired, may send information related to the enhanced navigation solution to the portable device 100 or another destination. The communication between the portable device 100 and the server 126 may employ any suitable protocol. For example, a short-range, low-power communication protocol (such as,

ANT or a wired connection) or may use longer-range communication protocols such as transmission control protocol (TCP/IP) -based communication of packets, access using a Wireless Local Area Network (WLAN), cellular telephone protocols, etc. In general, the system depicted in FIG. 1 may embody aspects of a networked or distributed computing environment. The portable device 100 and the server 126 may communicate directly or indirectly, such as through a plurality of interconnected networks. As will be appreciated, various systems, components, and network configurations, topologies, and infrastructures (e.g., client/server, peer-to-peer, or hybrid architectures) can be employed to support a distributed computing environment. For example, computing systems may be connected together by wired or wireless systems through a local network or widely distributed network. Currently, many networks are coupled to the internet, which provides the infrastructure for widely distributed computing and encompasses many different networks, although any network infrastructure may be used for exemplary communications taking place over the techniques described in various embodiments.

As described above, the portable device 100 may derive navigation solutions, and the server 126 may execute an offline map matching routine to provide an enhanced navigation solution for at least one of the navigation solutions. However, any or all of the functions described as being performed may be performed by any number of separate devices in communication with each other, or in other suitable system architectures, may be performed by the portable device 100 itself. Accordingly, it should be understood that any suitable division of processing resources may be employed within a device or among multiple devices. Further, aspects implemented in software may include, but are not limited to, application software, firmware, resident software, microcode, etc., and may take the form of a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system, such as the main processor 102, the sensor processor 108, the server processor 128, the portable device 100, a dedicated processor or any other processing resource of the server 126, or other remote processing resource, or may be implemented using any desired combination of software, hardware, and firmware.

For example, another embodiment is schematically depicted in fig. 27. Here, similar components have corresponding reference numerals (e.g., portable device 100 of fig. 1 may correspond to portable device 2700 of fig. 27). As such, portable device 2700 includes a main processor 2702, which can be one or more microprocessors, Central Processing Units (CPUs), or other processors for running software programs, which can be stored in memory 2704, in association with the functions of device 2700. A number of software layers may be provided in memory 2704. The apparatus 2700 includes so as to integrate a Motion Processing Unit (MPU)^TM)2706, the integrated motion processing unit 106 features a sensor processor 2708, a memory 2710, and inertial sensors 2712. Memory 2710 may store logic or a controller for processing data output by inertial sensor 2712 and/or other sensors as described below using sensor processor 2708And storing raw data and/or motion data output by the inertial sensor 2712 or other sensors. Inertial sensors 2712 may be one or more sensors for measuring motion of apparatus 2700 in space, such as gyroscopes and/or accelerometers as described above. The device 2700 may also implement a sensor assembly in the form of an external sensor 2714. This is optional and not required for all embodiments. Also alternatively or additionally, MPU 2706 may receive data from auxiliary sensors 2716 that are configured to measure one or more aspects related to the environment surrounding device 2700. This is optional and not required for all embodiments. In the illustrated embodiment, the main processor 2702, the memory 2704, the MPU 2706, and other components of the device 2700 may be coupled by a bus 2718, which may be any suitable bus or interface. The device 2700 may also have a source of absolute navigation information 2722 (which is optional) and may have a communication module 2724 for sending and/or receiving information, including enhanced navigation solutions derived remotely.

In this exemplary system, the portable device 2700 transmits raw sensor data for a plurality of sensor time periods within a first time period to the server 2726, which the server 2726 may include a navigation module 2720 to derive a navigation solution for the portable device 2700 for the raw sensor data for each time period. The navigation module 2720 may be implemented as a suitable set of instructions stored in the memory 2730 that are readable and executable by the server processor 2728. After the first time period, the server 2726 may then perform an offline map matching routine in accordance with the techniques of this disclosure using the navigation solution from the navigation module 2720 to provide an enhanced navigation solution for at least one of the sensor periods. Using similar techniques, server processor 2728 may communicate with memory 2730 over a bus 2732 and may execute instructions stored in memory 2730, represented as functional blocks, including a location estimator 2734, a hypothesis analyzer 2736, a map handler 2738, an input handler 2740, and an anchor manager 2742. The server 2726 may also include a communication module 2744 for receiving raw sensor data of the portable device 2700 and, if desired, may send information related to the enhanced navigation solution to the portable device 2700 or another destination.

As another illustrative example, the embodiment schematically depicted in FIG. 28 represents a device that locally performs an offline map matching routine. Likewise, similar components have corresponding reference numerals (e.g., portable device 100 of fig. 1 may correspond to portable device 2800 of fig. 28). Accordingly, portable device 2800 includes a main processor 2802, which may be one or more microprocessors, Central Processing Units (CPUs), or other processors, for running software programs, which may be stored in memory 2804, associated with the functionality of device 2800. Multiple software layers may be provided in memory 2804. The apparatus 2800 includes so as to integrate a Motion Processing Unit (MPU)^TM)2806, the integrated motion processing unit 2806 features a sensor processor 2808, a memory 2810, and an inertial sensor 2812. The memory 2810 may store algorithms, routines, or other instructions for processing data output by the inertial sensors 2812 and/or other sensors as described below using logic or a controller of the sensor processor 2808, as well as storing raw data and/or motion data output by the inertial sensors 2812 or other sensors. Inertial sensors 2812 may be one or more sensors for measuring motion of device 2800 in space, such as gyroscopes and/or accelerometers described above. Device 2800 can also implement a sensor component in the form of an external sensor 2814. This is optional and not required for all embodiments. Also alternatively or additionally, MPU 2806 may receive data from auxiliary sensors 2816 that are configured to measure one or more aspects related to the environment surrounding device 2800. This is optional and not required for all embodiments. In the illustrated embodiment, main processor 2804, memory 2806, MPU 2800, and other components of device 2802 can be coupled by a bus 2818, which can be any suitable busA bus or an interface. Device 2800 may also have a source of absolute navigation information 2822, which is optional and required for all embodiments. .

In this embodiment, portable device 2800 includes a navigation module 2820 that represents instructions stored in memory 2804 for execution by main processor 2802 to derive a navigation solution for portable device 2800 using the sensor data for each time period. After the first time period, the server 2800 may then perform an offline map matching routine in accordance with the techniques of this disclosure using the navigation solution from the navigation module 2820 to provide an enhanced navigation solution for at least one of the sensor periods. Using similar techniques, main processor 2802 may execute instructions represented as functional blocks, including a location estimator 2834, a hypothesis analyzer 2836, a map handler 2838, an input handler 2840, and an anchor manager 2842.

A representative routine involving the techniques of this disclosure is depicted in fig. 2. Beginning at 200, sensor data of a portable device, such as sensor data from inertial sensors 112 and/or external sensors 114, may be obtained for a plurality of periods within a given time period. At 202, using the sensor data, the navigation module 120 may derive a navigation solution for each time period. In embodiments where offline map matching is performed remotely, either or both of the raw sensor data, the derived navigation solution, or both may be sent to a remote processing resource, such as server 126. For example, the derivation of the navigation solution for each sensor epoch may be performed by the navigation module 120 at the portable device 100, or may be performed at the server 126 using the raw sensor data for each sensor epoch as sent by the portable device 100. In other embodiments, the portable device 100 may perform offline map matching locally. Whether offline map matching occurs locally or remotely, location information of the portable device 100 may be estimated at 204 at a time after a given period of time, and map information of the surrounding area may be obtained at 206. Multiple hypotheses may be generated from the estimated location information and map information for at least one of the sensor periods at 208. Next, at 210, the generated hypotheses are managed as described herein, and then processed at 212 to update estimated location information. An enhanced navigation solution for at least one sensor period may then be provided in 214.

In one aspect, absolute navigation information may be obtained for a portable device, wherein a navigation solution derived for at least one time period may be based at least in part on the absolute navigation information. The absolute navigation information may be obtained from any one or any combination of the following: (i) global Navigation Satellite Systems (GNSS); (ii) a cellular-based positioning; (iii) WiFi-based positioning; or (iv) other wireless-based positioning.

In one aspect, providing an enhanced navigation solution may include performing a forward processing operation for a first time period.

In one aspect, providing an enhanced navigation solution may include performing a reverse processing operation over a first time period.

In one aspect, providing an enhanced navigation solution may include performing a forward processing operation and a reverse processing operation over a first time period.

In one aspect, providing an enhanced navigation solution may include forward processing operations, reverse processing operations, and a combination of forward and reverse processing over a first time period.

In one aspect, providing an enhanced navigation solution may include performing a smoothing operation over a first time period.

In one aspect, providing an enhanced navigation solution may include performing a reverse smoothing operation over a first time period.

In one aspect, providing an enhanced navigation solution may include performing a plurality of rounds of processing operations over a first time period.

In one aspect, heading information for a navigation solution for at least one epoch may be filtered. Filtering the heading information may include applying a zero-phase low pass filter.

In one aspect, the plurality of navigation solutions may be classified into straight and turn segments, and may further include detecting a false turn.

In one aspect, periods of nonsensical motion may be characterized within a first period of time (such as periods of restlessness). The misalignment may be tracked corresponding to periods of restlessness. Further, steps detected during periods of restlessness may be compensated for.

In one aspect, map information may be pre-processed. Preprocessing the map information may include extracting map entities. The pre-processing of the map information may further comprise cropping at least one foreground map entity from the background entity. Cropping the background entity may define a traversable area. Still further, preprocessing the map information may include representing the map entity as a relatively complex polygon and decomposing the polygon into a plurality of relatively simpler polygons. Preprocessing the map information may also include generating a grid of connected routes and nodes.

In one aspect, the estimated location information may be an error zone representing a potential location of the portable device during the at least one sensor epoch. At least one of the hypotheses may be generated by projecting the error region onto the map information. When overlapping with multiple map entities, multiple hypotheses may be generated by projecting error regions onto the map information.

In one aspect, the map information may be a polygon-based geometric map. Alternatively or additionally, the map information may be a grid map.

In one aspect, the map information may be a grid map, and the estimated location information may be based at least in part on a correlation between the determined user trajectory for at least one time instant during the first time period and topological features of the grid map. A weighted topology algorithm may be applied.

Managing the hypotheses may include at least one of adding, removing, and combining the hypotheses. Anchors associated with the navigation solution for at least one time period may be identified, and managing the hypotheses may be based at least in part on the identified anchors. Multiple ordered anchor points may be identified. Hypotheses may be generated based at least in part on the ordered anchor points. Alternatively or additionally, multiple unordered anchor points may be identified, which may be used in some embodiments to prune at least one hypothesis. Still further, one or more incorrectly ordered anchor points may be identified.

In one aspect, managing the hypotheses may include applying decision logic. The decision logic may be configured for a through-wall event. The decision logic may be configured for a level change event.

In one aspect, multiple hypotheses for the generation of multiple sensor epochs can be stored. Storing the generated plurality of hypotheses may include correlating the hypotheses with one another. The stored generated plurality of hypotheses may be weighted based at least in part on the relationship.

In one aspect, the navigation solution may include a motion pattern of the user. The estimated location information may be based at least in part on a motion pattern. The hypotheses may be managed based at least in part on the motion patterns. Further, the level change event may be based at least in part on the motion pattern.

In one aspect, an enhanced navigation solution may include a motion pattern of a user detected based at least in part on a map entity associated with estimated location information.

In one aspect, the location information of the portable device may be estimated using at least one of a prediction-only kalman filter, a near-constant velocity kalman filter, a prediction-only particle filter, and a near-constant velocity particle filter.

In one aspect, at least one of deriving a navigation solution, obtaining map information, generating a plurality of hypotheses, managing the hypotheses, processing the managed hypotheses to update estimated location information of the portable device, and providing an enhanced navigation solution using the updated estimated location information may be performed remotely.

As described above, the techniques of the present disclosure may be implemented using a portable device including: an integrated sensor assembly that can output sensor data for a plurality of periods of a portable device within a first time period, the sensor data representing motion of the portable device; a navigation module configured to derive a navigation solution based at least in part on sensor data over a plurality of sensor epochs; and a processor, the processor may implement: a location estimator to provide estimated location information of the portable device based at least in part on a plurality of navigation solutions at a time after the first time period; a map handler to obtain map information for an area containing a location of the portable device during a first time period; and a hypothesis analyzer to generate and manage multiple hypotheses about possible locations of the portable device for at least one time period during the first time period based at least in part on the estimated location information and the map information, such that the processor may update the estimated location information of the portable device based at least in part on the managed hypotheses to provide an enhanced navigation solution for the at least one time period using the updated estimated location information.

In one aspect, a portable device may have a source of absolute navigation information for the portable device, wherein a navigation solution for at least one epoch may be based at least in part on the absolute navigation information. The absolute navigation information may be obtained from any one or any combination of the following: (i) global Navigation Satellite Systems (GNSS); (ii) a cellular-based positioning; (iii) WiFi-based positioning; or (iv) other wireless based positioning. The portable device may have an output that represents sensor data of the movement of the portable device over a plurality of periods. The sensor assembly may include an accelerometer and a gyroscope. The sensor assembly may include an inertial sensor implemented as a micro-electromechanical system (MEMS).

In one aspect, a portable device may have a memory for storing a plurality of hypotheses generated by a hypothesis analyzer.

The present disclosure also includes a server for augmenting a navigation solution for a portable device and a platform using map information, wherein mobility of the portable device is constrained or unconstrained within the platform, and wherein the portable device can be tilted to any orientation. The server may include a communication module to receive information provided by the portable device, wherein the information corresponds to sensor data representing motion of the portable device for a plurality of periods within a first time period, and a processor, the processor may implement: a location estimator to provide estimated location information of the portable device at a time after the first time period based at least in part on a plurality of navigation solutions derived for the time period; a map handler to obtain map information for an area containing a location of the portable device during a first time period; and a hypothesis analyzer to generate and manage a plurality of hypotheses regarding possible locations of the portable device for at least one time period during the first time period based at least in part on the estimated location information and the map information, such that the processor may update the estimated location information of the portable device based at least in part on the managed hypotheses to provide an enhanced navigation solution for the at least one time period using the updated estimated location information.

In one aspect, the information received by the communication module may be sensor data of the portable device, the sensor data representing motion of the portable device over the time period, and the processor may derive a navigation solution for the time period based at least in part on the sensor data.

In one aspect, the information received by the communication module may be a navigation solution derived by the portable device for the time period.

In one aspect, the communication module may transmit the enhanced navigation solution to the portable device.

In one aspect, a server may have a memory for storing a plurality of hypotheses generated by a hypothesis analyzer.

Still further, the present disclosure includes a system for providing an enhanced navigation solution using map information. The system may have a portable device having: an integrated sensor component configured to output sensor data for a plurality of epochs of the portable device within a first time period, the sensor data representing motion of the portable device; a communication module to transmit information corresponding to the time period. The system may also include a remote processing resource to receive information from the portable device and a processor to implement: a location estimator to provide estimated location information of a portable device at a time after the first time period based at least in part on a plurality of navigation solutions of the portable device derived for each time period; a map handler to obtain map information for an area containing a location of the portable device during a first time period; and a hypothesis analyzer to generate and manage a plurality of hypotheses regarding possible locations of the portable device for at least one time period during the first time period based at least in part on the estimated location information and the map information, such that the processor may update the estimated location information of the portable device based at least in part on the managed hypotheses to provide an enhanced navigation solution for the at least one time period using the updated estimated location information.

In one aspect, the information received by the remote processing resource may be sensor data of the portable device, and the remote processing resource may derive navigation solutions for a plurality of time periods based at least in part on the sensor data.

In one aspect, the portable device may have a navigation module configured to derive a navigation solution based at least in part on sensor data for a plurality of time periods, and the communication module may transmit the navigation solution.

In one aspect, the remote processing resource may transmit the enhanced navigation solution to the portable device.

In one aspect, the remote processing resource may have a memory for storing a plurality of hypotheses generated by the hypothesis analyzer.

Examples of the invention

As described above, the techniques of this disclosure relate to providing offline enhanced navigation solutions using map information. In some embodiments, the operations AND/or algorithms related to MAP matching may be similar to those described in co-pending, commonly assigned U.S. patent application serial No. 14/845,903 entitled "METHOD AND APPARATUS FOR enhanced PORTABLE NAVIGATION with MAP INFORMATION assistance" (METHOD AND APPARATUS FOR USING MAP INFORMATION AIDED ENHANCED PORTABLE NAVIGATION), filed on day 9, month 4 of 2015.

For purposes of illustrating the exemplary embodiment, one suitable relationship between the functional blocks implemented by the server 126 is shown in FIG. 3. Navigation solutions derived by the navigation module 120 corresponding to a plurality of sensor epochs (epochs) within the first time period are fed to the input handler 140 at subsequent time instances. The input handler 140 may provide operations on navigation solutions to facilitate the use of these navigation solutions by the location estimator 134 and/or the hypothesis analyzer 136. The map handler 138 may feed map information corresponding to the area corresponding to the navigation solution to the location estimator 134 and/or the hypothesis analyzer 136. As will be described below, the map information may be pre-formatted in a form that may be used by the location estimator 134 and/or the hypothesis analyzer 136, or the map handler 140 may perform additional operations to organize and/or process the map information in order to present the map information in a suitable form. Anchor manager 142 may perform operations to associate one or more known locations with one or more of the navigation solutions.

Accordingly, navigation solutions provided by the navigation module of the portable device 100 may be initially processed to improve the availability of these navigation solutions (such as the availability for use by the input handler 140) during an offline map matching routine. As schematically shown in fig. 4, the input handler 140 may include a filter 400, a motion segment classifier 402, and/or a motion characterizer 404. The input handler receives as input the navigation solution derived by the navigation module 120.

The input orientation from the navigation solution provided by the navigation module 120 may be expected to be the platform orientation and may be derived from the difference between the device orientation and the estimated misalignment angle. In some cases, depending on the use case of the portable device, this derived platform orientation from the navigation solution may exhibit periodic orientation oscillations or sinusoidal wave-like orientation fluctuations. A use case is a characterization of the type of interaction between a portable device and a user, and may include: whether the user is carrying the device, or is holding the device with a swinging arm or "wagging," or positioning the device "on the ear" while talking, inputting data, or viewing or texting in a navigational direction, or carrying the device in a pocket or other receptacle or holder, and other uses that affect the orientation of the device relative to the user. For example, a pocket or swing use case may have a periodic motion component. It may be desirable to remove or reduce components in the navigation solution attributable to this oscillation. By employing all navigation solutions derived within the first time period, a zero-phase low-pass filter can be utilized to remove or reduce the effects of ringing without introducing undesirable delays into the signal.

In one aspect, it may be desirable to de-group one or more navigations into similar motion patterns. For example, when a navigation solution is considered to represent a trajectory of a user, multiple segments of the trajectory may be classified as turns or straight lines by the motion segment classifier 402. The entry and exit times for each straight and turn segment may be indicated for use by the position estimator 134 and/or the hypothesis analyzer 136. Further, the location segment classifier 402 may also determine the shape of the turn, e.g., as being U-shaped or L-shaped. Thus, the turn shape information may be employed by the hypothesis analyzer 136 during hypothesis management. Further, information from the navigation solution identified as being near the turn period may be considered to remove false turns induced by restlessness or short-term misalignment variations. Furthermore, if the turn shape cannot be determined correctly due to the occurrence of restlessness, inaccurate misalignment estimation, gyro drift, etc., then any turn indicator will be flagged so that the hypothesis analyzer can generate all possible candidates to compensate for the uncertainty of the turn shape.

In one aspect, it may be desirable to detect one or more navigation solutions that may be associated with a type of motion that may have an impact on information usage during offline map matching. For example, motion characterizer 402 may detect a motion pattern that indicates that the device is experiencing insignificant motion (such as a user sitting restless with the device). Accordingly, the motion characterizer 402 can be used to detect one or more periods during which some or all of the motion experienced by the device is insignificant or a result of sitting insecure and identify navigation solutions corresponding to such periods. For example, the entry and exit moments for the period of restlessness may be provided by the location estimator 134 and/or the hypothesis analyzer 136. Furthermore, information before and after each such period can be used to improve the identification of insignificant motion. In some embodiments, the detected period of nonsense motion can be used to track misalignment to isolate unintentional bias variations during the period of nonsense motion. In some embodiments, the detected periods of nonsense motion may be used to compensate for step detection in a pedestrian dead reckoning technique where nonsense motion may result in incorrect step detection.

As mentioned, the location estimator 134 may utilize the navigation solution from the navigation module 120 and the results from the hypothesis analyzer 136 to generate an improved map-matched location estimate. Hypothesis analyzer 136 uses these position estimates to create, eliminate, or combine hypotheses for the next epoch. The location estimator 134 maintains all possible candidates for map matching and generates their corresponding location estimates. The position estimator 134 may use any filter or any combination of filters to obtain the position estimate, including but not limited to a Kalman filter, an unscented Kalman filter, a particle filter, and so on. Different systems and measurement models may also be used depending on the application, for example: only predictive, near constant speed, and others. These models may employ different techniques to propagate the location of the portable device 100 and use the navigation solution output as a measurement update. Representative systems and measurement models are described in the following material, but other variations may be employed. The location estimator 134 may output an updated location, which may also include velocity and/or orientation information as a combination of assumptions. For example, the combination may be a weighted average. The weights used in combining the hypotheses may be adaptively adjusted based on empirical or topological models. For example, the weighting may be adjusted based on the number of hypotheses and/or the uncertainty of the location estimate. The updated location from the combination of hypotheses represents map assistance information and may be used to provide an enhanced navigation solution. Furthermore, map entity information that may be associated with a given navigation solution is also beneficial for improving motion detection associated with that navigation solution. For example, if it can be determined that the user was/is on a staircase, the pattern of the corresponding sensor data may be associated with that motion pattern.

The map information may be initially obtained from any suitable source, such as from an online map service provider. The map information may be preprocessed into a form suitable for use by the location estimator 134 and/or the hypothesis analyzer 136, as desired. For example, the map information may be converted to an internal map data structure, where the internal map data structure may be saved to local storage for future use as needed without the overhead of downloading and processing the internal map data structure again. Accordingly, preprocessing map information may include the following functions: i) converting map information from various map data providers into a unified data structure; ii) preparing the necessary map data structure suitable for the map assistance algorithm; and/or iii) store map information in a local store, such as: memory 130 (for embodiments in which offline map matching is performed remotely) or memory 104 (for embodiments in which offline map matching is performed locally).

Online indoor/outdoor map service providers may provide web Application Programming Interfaces (APIs) to access their map databases. Accordingly, a corresponding API from the map provider may be used to obtain map information for an area encompassing the user's current location. Particularly notable examples of locations with corresponding map information include indoor environments such as office buildings, hospitals, malls, exhibition centers, retail stores, and so forth. The map information may be pre-processed to facilitate its use during offline map matching. For example, this information may be decoded to use an API to extract the necessary map data for the techniques of this disclosure, and may be converted to a unified format, such as the geographic Javascript object notation (GeoJson) format, although xml files, binary files, and other files may be used. The converted map data may then be maintained in local storage for future use. The decoding and conversion may be performed by an external resource and may be communicated in any suitable manner for use during offline map matching. In general, it is desirable to minimize the number of preprocessing operations performed for each site. For example, map information may be appropriately formatted once for a given venue and allocated to any number of portable devices for use in generating assumptions, thereby enhancing navigation solutions within that venue. However, another pre-processing operation may be performed when new information becomes available or when a change in the field occurs.

Further, preprocessing the map information may include: the map information is separated into traversable and non-traversable areas. For example, in a typical indoor environment, a hallway represents a significant class of wearable areas. Thus, if corridor information is not available, a corridor cropping function may be performed to extract corridor shape information from the background entity, rendering the map information as a polygon-based geometric map. Many conventional map service providers do not provide corridor shape information, which is important in indoor map assistance algorithms. Thus, a suitable technique for obtaining the shape of a hallway that may be present in a venue may include extracting all other entities from the background entity. The background entity may be a boundary contour that establishes a level of a given building or other site. The foreground entities include all objects within the boundary profile, such as stores, elevators, escalators, and other obstacles. A clipping process as used herein refers to a process of cutting out those portions from a set of 2-dimensional geometric shapes that are outside a particular "clipping" window. This may be achieved by intersecting the subject polygon (background entity) with the clipping polygon (other foreground entity on top of the background entity). A polygon may be defined by a sequence of vertices, and any curve may be represented as an appropriate set of line segments.

After iteratively cropping all other entities from the background, the corridor polygon may be obtained. Suitable clipping algorithms, such as the Vatti clipping algorithm, may be configured to fit relatively complex perforated polygons. A graphical representation of the results of a clipping algorithm for a representative polygon-based geometric indoor map is shown in fig. 5. A background entity 500 of a portion of the map is represented by a dashed line. Foreground entities represented as polygons in thin lines, such as polygon 502 (other polygons not labeled to maintain clarity), are clipped on top of background entity 500. The resulting polygon 504, represented by a bold line, gives the shape of the corridor. The resulting corridor shape may be represented by a complex polygon. A complex polygon, as used herein, is a polygon (without self-intersection) with one or more internal holes.

As will be described below, some map entities may provide inherent location information (such as elevators, escalators, stairways, or conveyor belts that may be associated with a level change scenario) or other location information. The locations of entrances and exits to the background map entity and the locations of doors or other entrances/exits to the foreground entities may also be used. Still further, the direction of the inlet/outlet may also be used in generating the hypotheses. In a multi-story facility, the height of each level may be used with sensor information indicating elevation changes to help determine when a level change scenario is likely to exist.

Further, the pre-processing may include decomposing one or more shapes of the map entity into smaller, simpler polygons to improve computational efficiency when used by the location estimator 134 and/or the hypothesis analyzer 136. Trapezoidal decomposition may be used to decompose relatively complex polygons into simpler trapezoids, while convex decomposition may be used to decompose relatively complex polygons into simpler convex polygons. An optimal decomposition algorithm may be applied to generate a reduced number of polygons after the decomposition process. Any one of the decomposition methods or any combination of decomposition methods may be employed.

Preprocessing the map information may also include abstracting traversable areas of the indoor map with connected routes and nodes. The connected routes and nodes may contain both geometric and topological information of the map. Thus, the location estimator 134 and/or the hypothesis analyzer 136 may benefit from the topology information to improve the generation of updated estimated location information. As used herein, a map constructed from connected routes and nodes may be referred to as a grid map. The grid map may be generated using any suitable technique, such as, for example, by using a voronoi diagram (voronoi diagram) that may be accompanied by some other processing. Another example for generating a grid map is by directly using geometric shapes from traversable and non-traversable areas of the map, possibly accompanied by some of the map entity types. An example grid map is illustrated in fig. 6. As shown, a point may be used to represent a map node, such as point 600. The dashed lines represent connected routes between points 600 (such as route 602), and the map entities are represented by solid line polygons (such as 604). A node is a point on the map that has equal distance to its nearest three or more entities. For polygon-based geometric maps, the grid map may be preprocessed offline by external processing resources and may be saved in a map file for subsequent use by the location estimator 134 and/or the hypothesis analyzer 136 without preprocessing each time updated estimated location information is determined.

In one aspect, a grid map may enhance the geometric aspects of map matching and provide topological aspects. Topology information from indoor maps can also be applied to improve the reliability and accuracy of map matching algorithms. For example, a retail store map can be easily divided into structured and unstructured areas. Unstructured areas (such as open space, isolated booths) may benefit from a geometry-based map matching algorithm as described above. However, structured areas (such as aligned shelves, booths, and similar features) may be abstracted as connected routes and nodes for use in a grid-based map. Further, when a grid map is available, the location estimator 134 may be simplified to accumulate travel distances along the map route rather than estimating absolute locations. Similarly, assume that the analyzer 136 can also be simplified to operate based on map routes.

Both polygon-based geometric maps and grid maps may be applied to improve the reliability and accuracy of the updated estimated location information. For example, a retail store map can be easily divided into structured and unstructured areas. At those unstructured areas (such as open spaces, isolated booths, etc.), the geometry-based techniques described above may be applied. Alternatively or additionally, at a structured area (such as an aligned shelf or booth), the geometric and topological information may be represented as a grid map. When a grid map is available, a weighted topological algorithm based on the correlation between the user's trajectory and topological features can be applied to improve map matching performance. Multiple conditional tests may be applied to eliminate segments that do not meet some predetermined threshold, which may be obtained through statistical analysis of field test data. When there is ambiguity, new hypotheses may be created to take into account the user motion uncertainty. The user motion uncertainty may include an accumulated step uncertainty and/or a user orientation uncertainty. Thus, for a certain period of time, multiple hypotheses may be running in parallel, and unlikely hypotheses are removed after being given a low weight. As described above, anchor point information may also be used to remove unlikely hypotheses.

Accordingly, the map handler 138 may be used to load previously stored, preprocessed map information, which may include cropped and decomposed map information as described above, as well as original map information. The map handler 138 may access map information that has been formatted in a manner that facilitates generation of location hypotheses for the portable device 100, and may retrieve the information as needed. With the pre-processed map information, the map handler 138 initializes an internal map data structure, which may include map projection parameters, geometry, Identification (ID), and type information for all entities in the map. Projection parameters (e.g., a six-parameter affine transformation) may be used to transform between coordinates in the map and coordinates by dimension and precision. The entity type describes the functionality of a particular entity, such as a background, a cell, an escalator, an elevator, a staircase, etc. Both shape information and type information may be used by hypothesis analyzer 136. The map handler 138 may also organize the map geometry information in a spatial database so that efficient search algorithms may be applied to query points of interest or ranges of interest in the map. For example, the R-tree structure may be used for efficient and fast searching of map entities. As will be appreciated, the R-tree search algorithm may locate a given point in the map and return a pointer to the corresponding map entity.

Although described in the context of being performed by an external processing resource, any or all of the functions associated with pre-processing map information may be performed by the map handler 138 as desired.

The outputs from both the location estimator 134 and the map handler 138 may be fed into a hypothesis analyzer 136. Notably, the location estimator 134 can provide the estimated location information in the form of a location and variance estimate that defines an error region. Assume that analyzer 136 superimposes or projects the error region on the processed map in order to identify the likely entity in which the user is traveling. Hypothesis analyzer 136 maintains, creates, eliminates, and combines hypotheses based on any suitable decision logic, including those described below. Hypothesis analyzer 136 may also assign weights to all currently available hypotheses based on topological information and empirical information. Those weights may be used to combine or eliminate the hypotheses and to combine the hypotheses, such as by generating a weighted average to update the estimated location.

As indicated in fig. 3, the output from anchor manager 142 may also be fed to hypothesis analyzer 136 for use in generating, deleting, and otherwise managing hypotheses. The anchor manager 142 may identify one or more objects, structural features, or other map entities, such as points of sale, that have known fixed locations and may be associated with one or more navigation solutions provided by the navigation module 120. When relative timing information is available for multiple anchor points, the anchor points may be considered to be ordered, and hypothesis analyzer 136 may constrain the hypotheses to those anchor points that satisfy the order. When relative timing information is not available, it may be assumed that the user was at an anchor location, and thus these assumptions may be confirmed based on whether a trajectory containing the anchor is generated. The set of anchor points without timing information may be considered unordered. For some of the anchors that have timing information and others that do not, or when there is a timing error, the anchors may be considered to be not fully ordered. It is assumed that analyzer 136 may use all of these types of anchors, as provided by anchor manager 142, to varying degrees. For example, ordered anchor points may be used to create one or more hypotheses. Furthermore, any type of anchor point may be used to prune or evaluate the hypotheses that have been generated. Hypothesis analyzer 136 may use the location of the anchor point and use a predetermined uncertainty circle as a decision criterion to remove all hypotheses outside the uncertainty circle. Further, the hypotheses may be corrected with updated positions of those hypotheses that may be inside the uncertainty circle, but separated by structures such as rooms or corridors. Furthermore, since anchor point information can be used to efficiently remove unlikely hypotheses, more hypotheses can be created to adapt to various user motion uncertainties, thereby improving the success rate of map matching. In some cases, the ordering of the anchor points may include errors. Thus, assume that analyzer 136 may be configured to identify any outliers and isolate them as incorrectly ordered anchor points. For example, if there is a large deviation, anchor points may be reordered in a more reasonable manner using a trial-and-error based search mechanism. If ordering ambiguities cannot be resolved, they can be excluded from the hypothesis analysis so that they do not adversely affect the final solution.

Techniques of the present disclosure include using navigation solutions derived over a period of time for subsequent enhancement of at least one of the navigation solutions. Accordingly, for a given sensor epoch, it is assumed that the analyzer 136 may have information available from the future epoch as well as the previous epoch. As will be appreciated, a number of benefits stem from this feature. Hypothesis analyzer 136 may maintain a history of any or all of the hypotheses, including generating, pruning, or deleting hypotheses, allowing management of the hypotheses to be propagated forward as well as backward to improve accuracy. Similarly, the hypothesis analyzer 136 may have access to future navigation solutions such that management of hypotheses for a given time period may benefit from future and past information. For example, different management strategies may be used for straight lines than for curved segments, but when considering the trajectory as a whole, accurate detection of those segments may be significantly improved. Furthermore, since there is no need to provide a "current" navigation solution, no buffer and delay mechanism is required. As another example, information over the entire period may be used to adjust the step size scale factor based on various scenarios that may be detected for the trajectory. Further, hypothesis analyzer 136 may assign weights to the hypotheses based on similarity of trajectory shapes between the navigation solution and the enhanced navigation solution provided by offline map matching.

In one aspect, assume that analyzer 136 can use both forward processed data and backward processed data in order to improve the performance of the system as described. This is particularly useful for long tracks when positioning information towards the end of the track is available, such as from an anchor point like a checkout point or store exit. The enhanced navigation solution with backward processing can significantly reduce the cumulative error that would otherwise occur. Furthermore, a more reliable misalignment estimation may be obtained.

In some embodiments, the derivation of the navigation solution, such as by navigation module 120, may include first forward processing the sensor data to generate a forward navigation solution. An optional pre-run of sensor data may be applied to obtain the sensor bias estimate. Furthermore, pre-running may also be used to obtain segmented misalignment estimates, which may be further smoothed and later applied in forward and/or backward processes. Thus, pre-running may improve the overall performance of forward and backward sensor navigation solutions, especially during periods of restlessness(s). Backward processing may use the inverted sensor data as input and the forward exit point as an initial starting point, enabling the same positioning engine to be applied as in forward processing. Removing any identified initial period(s) of restlessness at the beginning or end may improve the reliability of the alignment process.

Forward and backward sensor navigation solutions may be used to improve performance map matching solutions in any suitable manner. For example, the offline map matching routine may first process the forward and backward sensor navigation solutions, respectively. Both forward and backward map matching solutions may be used to generate a final map matching navigation solution. During the solution merging process, overlapping map route histories of the hypothesis trees from the forward and backward map matching processes may first be identified. The common map line in both the forward solution and the backward solution may then be added to the candidate list. Accordingly, each candidate in the candidate list may be used as a starting point for iterating the hypothesis tree. The respective best candidate branches in the forward and backward directions may be merged together to provide the final navigation solution. Note that the common map route may be a route on which the anchor point resides or a normal route in the track history.

The forward and backward sensor solutions may also be combined and smoothed first, such as, for example, using two filter smoothers or multiple round smoothers. In addition, a Rauch-Tung-Striebel (RTS) smoother or any other suitable smoothing filter or any backward smoothing technique may be employed. In some embodiments, the offline map matching routine of the present disclosure may use the smoothed sensor navigation solution as input to perform map matching. Alternatively, a simplified smoothing technique that employs a weighted average of the step size estimates from the forward and backward sensor navigation solutions may be used. Since map matching primarily uses relative positioning information, weighted step size estimation not only reduces the computational load, but also provides significant benefits during the smoothing process. Alternatively, a simplified combination technique for forward and backward may be used that employs a weighted average of the relative position changes from the forward and backward sensor navigation solutions.

In one aspect, the initial enhanced navigation solution may represent a position gap relative to navigation solutions from adjacent epochs. Any gaps may be smoothed using a suitable technique, such as by recalculating the determined trajectories. For example, the recalculation may employ the estimated user step size scaling factor. The step-size scale factor may be updated segment-by-segment such that no unreasonable location jumps exist in the map matching enhanced navigation solution(s) after smoothing. While smoothing may not necessarily improve overall accuracy or success rate, it may provide a more useful presentation of location information.

Hypothesis analyzer 136 maintains, creates, deletes, and combines hypotheses as described. Assumptions refer to the likely location of a user with any desired corresponding attributes, such as location, speed, orientation, motion pattern, location variance, map entities occupied, and so forth. The decision logic applied to the various hypotheses may be selected based on the user operating scenario as indicated in the examples below.

Many implementations of decision logic for hypothesis management employ the concept of an error region. As will be appreciated, the error zone represents an uncertainty of the possible location(s) of the portable device 100 as determined by the location estimator 134. The error zone may define a rectangle, a circle, an ellipse, any polygon, or any other shape as desired. If a Kalman filter is used with the position estimator 134, an "error ellipse" may be used. The parameters of the error ellipse include a semi-major axis length (a) and a semi-minor axis length (b), and the orientation (α) may be derived from a covariance matrix of the kalman filter and a predetermined confidence. For example, a 95% confidence may be used to reasonably cover the location uncertainty, but other values may be employed depending on the performance characteristics desired. Accordingly, the error ellipse parameters may be given by equation (1):

wherein λ is₁And λ₂Represents eigenvalues of a covariance matrix, and v₁The eigenvector with the largest eigenvalue representing the covariance matrix. To reduce the computational load, the error ellipse may be approximated by a polygon having several vertices, such as 32 vertices evenly distributed around the edge of the ellipse.

If a particle filter is used, the samples of the position estimate approximate the error region. However, error ellipses or other regions are still needed in the hypothesis analyzer 136 to combine or eliminate the hypotheses. Thus, the covariance matrix may be derived from the position sample data. Subsequently, the parameters of the error ellipse can be calculated as in the kalman filter mode. For purposes of illustration, FIG. 7 shows an example of an error ellipse derived from a particle filter with 95% confidence. The "+" sign indicates the vertex of the approximated error ellipse 700.

Various decision logic approaches may be applied to the management hypothesis with reference to the context of the error region. A first example corresponds to a scenario with a wall through event. Each hypothesis may have its own occupancy field indicating the current map entity associated with the portable device 100. As shown in fig. 8, the location estimator 134 uses the error area overlaid on the map layout to obtain candidate hypotheses. If no overlapping area is detected between the error region and the map entity, except for the currently occupied entity, it is assumed that the analyzer 136 need not perform any further operations. However, when the error area intersects with a plurality of map entities, the attributes of the intersected entities are inserted into the intersection table. The overlap detection may be achieved by iteratively checking the positions of the vertices of the approximation polygon for the error ellipse. A spatial search algorithm (e.g., an R-tree search-place and point-in-polygon algorithm) may be applied to find map entities for each vertex of the error ellipse. If all vertices are on the same map entity as the current hypothesis is occupied, no overlap is declared. Otherwise, the new hypothesis candidate will be added to the intersection list. Note that each hypothesis maintains its own intersection list. The current hypothesis may be referred to as a parent hypothesis, and all candidate hypotheses may be referred to as child hypotheses.

If the intersection area is above a suitable threshold (such as about 10% of the total area of the error ellipse), the new hypothesis candidate may undergo further analysis, otherwise it will be removed from the intersection list. Hypothesis analyzer 136 may then analyze all candidates in the intersection list that occupy a different amount than the current hypothesis. The initial position of the new candidate hypothesis is given by the current position estimate from the position estimator 134. However, if the point is not within the range of the overlapping polygon, the centroid moment of the overlapping polygon may instead be used as the initial position for the new hypothesis.

Subsequently, through-wall detection may be performed. The logic of the through-wall event is based on whether door information is available. If the door information is available, the algorithm may evaluate the distance between the initial position of the candidate hypothesis and the position of the door, as schematically indicated in FIG. 9. If the distance is within a predetermined threshold (such as 2 meters), a through-wall event may be declared. The central position of the door can then be used as the initial position for the new candidate hypothesis. Next, a validation check may be performed to determine if the initial point of the new hypothesis is within the range of other currently available hypotheses. Subsequent operations may be adjusted depending on the particular implementation. When using a particle filter, for example, a new hypothesis may be created where all particles reside in a new map entity and the new hypothesis is added to the hypothesis list. All other properties of the newly created hypothesis, except the location, may be inherited from the parent hypothesis. When using a kalman filter, for example, no new hypothesis creation and/or elimination is performed, and the location and occupancy fields of the parent hypothesis may be updated.

If the portal information is not available, the angle between the intersection edge of the error ellipse and the map entity of interest and the orientation of the user may indicate the likelihood of the user entering a new entity, as schematically indicated in FIG. 10. This intersection may result from a skewed navigation solution if the currently assumed orientation is nearly parallel to the edge of the room. In this case, if the overlap area is higher than a suitable value (such as about 45%), a new hypothesis with an offset from the intersection by a predetermined amount (such as about 0.5 meters) is created and the parent hypothesis is deleted. On the other hand, if the overlap area is below a predetermined amount (and optionally if the yaw dynamics of the user is small), the orientation of the intersecting edges may be used to update the orientation of the parent hypothesis. If the current assumed orientation is approximately perpendicular to the edge of the wall, a possible through-wall event is declared. Accordingly, a similar process may be performed as when door information is available.

Hypothesis analyzer 136 also examines the hypothesized occupied transitions. It is assumed that the user is free to enter and leave the corridor. However, inter-unit crossings are prohibited, or given minimal weight, to reflect the fact that it is not uncommon to have gates between stores. In addition, hypothesis analyzer 136 also weights the hypotheses based on the transition model or empirical model.

Another exemplary decision logic for managing assumptions can be applied when a level change event can be associated with one or more sensor periods. If the user was/is taking an elevator or escalator up or down, the navigation module 120 and/or hypothesis analyzer 136 may execute routines to detect corresponding motion patterns and/or contextual indicators for identifying a current user motion pattern/context (such as an elevator, stairs, walking on an escalator, standing on an escalator). When a level change event was detected/detected, it is assumed that the analyzer 136 may use the navigation solution corresponding to the sensor period to search for map entities in the map information that are sufficiently close according to the detected pattern, such as stairs, elevators or escalator entrances. For example, if an elevator mode was detected from/from the navigation solution, assume that the analyzer 136 can search for nearby elevator entrances on the map. If the entry is within a certain distance from the current user location, then it is assumed that the analyzer 136 can transition from the normal state to the level change state to apply the corresponding decision logic. As a non-limiting example, the distance threshold may be 10 meters. Further, the selected value may be adjusted according to the accuracy of the navigation solution.

In conjunction with the detection of a level change event, assume that analyzer 136 can transition from a normal state to a level change state to adjust its operation. If needed, a confirmation process is performed to avoid level change false alarms. During this process, it is assumed that analyzer 136 may initially propagate the user location using techniques similar to the normal state. The validation process may use the height difference between a given time period and the time period when entering the level change state as a metric to validate the state change. If a height difference above a threshold (such as, by way of non-limiting example, 2.0m) is detected within a given time, a transition to a level change state may be confirmed. Otherwise, the detection may be treated as a false alarm, resulting in a return to the normal state.

Given successful validation of the level change, the hypothesis analyzer 136 may eliminate all hypotheses and create new hypotheses using the identified level change entry information. The assumed initial position and/or orientation may be established by the entry location of the corresponding map entity. Map information corresponding to the new level may then be used such that the new level is identified as being above or below the previous level according to the sign of the height difference. Subsequently, the state of the hypothesis analyzer 136 may transition to a finalized state. If the validation process fails, the state returns to the normal state.

In this finalized state, hypothesis analyzer 136 may consider whether navigation module 120 detects a motion pattern for the associated navigation solution, or whether the hypothesis analyzer detects a motion pattern. If a walking state was detected/detected, the hypothesis analyzer 136 may reset the position of the corresponding hypothesis to the exit position of the level change entity and revert to the normal state, as schematically depicted in fig. 11. Hypothesis 1100 may correspond to a location estimate provided by a navigation solution, while hypothesis 1102 may reflect an updated location estimate based on the hypothesis of exiting elevator 1104. Otherwise, assume that the analyzer 136 can continue to propagate the user location. Note that after leaving the level change entity layout, the algorithm does not reset the assumed orientation according to the level change entity layout. This is because the user orientation may have changed due to a detection delay of the motion pattern if depending on the determination from the navigation module 120. As shown in fig. 11, the doors of the elevator are on the right side (0 °), however, after leaving the elevator, the user is oriented at about-90 °.

In addition to the motion patterns and/or context-aware scenarios discussed earlier (such as when a user is going upstairs or downstairs, riding an elevator or escalator), the operation of hypothesis analyzer 136 may be adjusted using some other motion patterns and/or contexts, such as walking or standing on a conveyor belt (moving walkway), walking near a wireless beacon or other wireless Radio Frequency (RF) tag, and so forth. When the system autonomously detects such motion patterns or context-aware scenes, the map information techniques presented herein may associate those motion patterns or context-aware scenes to a map entity. Benefits of this implementation include: (i) assume that analyzer 136 can detect a motion pattern/context related to a map entity and can enhance navigation solutions (particularly location and optionally orientation) to the location of the map entity; (ii) assume that analyzer 136 can receive entities that imply a motion pattern and/or context, which can be used to assist in identifying sensor data patterns associated with the implied motion pattern.

For example, when it is determined that the user has been/is walking/standing on the conveyor belt, it is assumed that the analyzer 136 can search for a nearby conveyor belt in the map information. When a nearby conveyor belt is found, a new hypothesis may be created in which the entrance of the conveyor belt is taken as the initial position and the orientation of the conveyor belt is taken as the initial orientation, and all other hypotheses are eliminated. A similar procedure to that applies to a level change event when a user walks out of the conveyor belt. This context-based 2D position adjustment may reduce the cumulative error from the PDR and thus improve the enhanced navigation solution for offline map matching. On the other hand, when the assumed error zone is above the top of a particular map entity (such as a conveyor belt, elevator, or escalator), the assumption analyzer 136 may base the detection of the corresponding motion pattern on this information to increase the sensitivity of the particular detection and improve the success rate.

A similar process may be applied to a walking/driving motion pattern detection scenario when a user is identified on a parking lot. For example, if the assumed location is above the top of a parking lot, this information may be fed to the navigation system to improve the sensitivity of the driving/walking detection module.

Another exemplary scenario involves updating from a wireless beacon or RF tag. If the store's entrance or interrogation station is equipped with wireless beacons or RF tags, the portable device can receive information from these wireless tags when the portable device is close enough. In this case, the assumed location may be updated using the location of the store entrance or the interrogation station.

The input orientation from the navigation solution provided by the navigation module 120 may be desired to be the platform orientation and may be derived from the difference between the device orientation and the estimated misalignment angle. As described above, this derived platform orientation from the navigation solution may exhibit periodic orientation oscillations, depending on the use case of the portable device. When navigation solutions are subsequently processed in accordance with the techniques of this disclosure, a zero-phase low-pass filter may be utilized to remove or reduce the effects of oscillation without introducing undesirable delays into the signal. An exemplary result of removing the heading oscillation is schematically illustrated in fig. 12, where the result of the individual navigation solution is indicated by trace 1200 and the enhanced navigation solution following low pass filtering is indicated by trace 1202.

If desired, hypotheses generated for one or more sensor epochs can be stored, e.g., by storing a plurality of hypotheses generated including correlating the hypotheses with one another. The stored generated plurality of hypotheses is based at least in part on the relationships. For example, to manage assumptions in a flexible manner, tree-based creation, pruning, merging, and deletion methods may be applied. Each hypothesis may maintain all of the history during the first of the sensor periods. The history may include positioning information, hypothesis statistics information, and hypothesis management information. Any or all of the information may be used to weight the hypotheses. The proposed architecture may also reduce memory usage of hypothetical data structures. Since all of the historical information may be maintained in a hypothesis data structure, a large number of hypotheses may represent significant storage requirements. The tree-based architecture can share the commonality of historical information and present memory usage efficiencies. As mentioned, it is assumed that a weighting scheme can be used with the tree-based architecture. With the ability to track parent and child hypotheses, the weighting may be calculated for information for the current epoch as well as for previous and future information. This may improve the accuracy and reliability of the weighting scheme. The tree-based hypothesis management system may enable manipulation of hypotheses in a more flexible manner, and may be particularly useful for map matching with anchor points of interest that may be associated with navigation solutions separate from the current time period. Where all history is maintained, new hypotheses can be easily created using the information of the anchor points. In one suitable implementation of a tree-based hypothesis data structure, each hypothesis may employ a unique ID, a pointer to its parent hypothesis, and an array of pointers to its child hypotheses. The root hypothesis may not have a parent pointer and the end hypothesis may not have a child hypothesis pointer.

At the end of the map matching process, a hypothesis pruning mechanism may be applied based on any suitable criteria to eliminate any unreasonable hypotheses. For example, the final assumed position may be expected to be within a certain range of the exit point. Hypotheses that exceed some threshold from the exit point may be pruned along with any parent branches. Further, when anchor points are available, hypothesis branches that do not pass through those anchor points may be removed from the hypothesis tree. Still further, the similarity between the sensor-based navigation solution and the enhanced navigation solution provided by offline map matching may also be used as a criterion for removing unlikely hypothesis branches.

Because of the uncertainty of the sensor navigation solution, the enhanced navigation solution may have many paths through any identified anchor point. The offline map matching routine may identify one or more appropriate solutions from any of the candidates. The final solution may be selected using any combination of criteria, including: 1) the shape of the enhanced navigation solution trajectory may be similar to the trajectory of the navigation solution, such as provided by the navigation module 120; and/or 2) the enhanced navigation solution may pass through all anchor points in the correct order. As will be appreciated, a longer trajectory may result in a greater number of possible paths. To compensate for the exponentially growing probability of paths that may undesirably consume processing and memory resources, a fast hypothesis search algorithm may be applied to optimize the search strategy by appropriately caching useful search information, and thus, the fast hypothesis search algorithm may be able to search for an optimal solution with reduced resource consumption.

As mentioned, the location estimator 134 may utilize the navigation solution and results from the hypothesis analyzer 136 to generate an improved positioning estimate aided by map information. Hypothesis analyzer 136 uses these position estimates to create, eliminate, or combine hypotheses for another epoch.

Although described primarily in the context of geographic map information, the above-described techniques may additionally or alternatively be used with map information represented as a grid map. For example, the user location may be projected into the connected lines and nodes by using location-curve matching or curve-curve matching. The two techniques can be combined to ease implementation and maintenance. Grid maps may also be used to assist the hypothesis analyzer 136 in deriving more reliable hypotheses by using a weighted topological algorithm based on the correlation between the trajectory of the user and the topological features of the grid map. Any suitable one or more conditional tests may be applied to eliminate segments that do not meet a predetermined threshold, which may be obtained through statistical analysis of field test data. For geometric techniques, when ambiguities exist, multiple hypotheses may be generated to account for user motion uncertainty. For example, user motion uncertainty can be caused by cumulative step error, user orientation error, and other errors. Thus, for a certain time period, multiple hypotheses may be running in parallel. Unlikely hypotheses with low weights may be removed. Further, with grid maps, an improved hypothesis weighting scheme may be employed by analyzing the topological history of the hypotheses. A weighted average of the information of all hypotheses may be used to calculate an improved uncertainty estimate. Thus, a more accurate estimate of the user's position uncertainty may be obtained.

Various filters, motion and/or measurement models may be used to update the assumed position in accordance with the techniques of this disclosure. The four example methods described below employ a prediction-only kalman filter, a near-constant velocity kalman filter, a prediction-only particle filter, and a near-constant velocity particle filter, although other filters and/or models may be employed as desired.

As a first example of employing a prediction-only kalman filter, the output of the integrated navigation solution provided by the navigation module 120 may be used to predict the system states for all currently available hypotheses. Three states may be used as the system state for each hypothesis, including position errors (δ x, δ y) and orientation errors δ ψ in the map coordinates. Further, dX_nRepresenting the system state of the nth hypothesis, both the position error and the orientation error can be modeled as a random traversal as indicated by equation (2):

(2)dX_n＝[δx δy δψ]^T

thus, one form of system model can be derived as shown in equation (3):

wherein,

ψ is the user orientation;

l is the step size, which can be obtained by calculating the displacement between two positions in adjacent epochs from the navigation solution;

w_Lis the driving noise of the step; and is

w_ψIs the drive noise towards the error.

Note that the position and step size may be calculated in the map coordinate system. The location by latitude and longitude may be transformed into a map coordinate system using affine transformation. The transformation matrix has six parameters, which are available from imported map data. In the prediction-only approach, there is no need to use measurement updates.

Thus, the communication of the system state can be given by equation (4):

wherein k and k +1 represent two consecutive periods, "-" represents a predicted value, "^" represents an optimum estimated value, ". DELTA.. psi ^ represents a predicted value, and_k+1representing the incremental orientation of the integrated solution compared to the current epoch.

As a second example of employing a near constant velocity hypothesis model, the output from the navigation model 120 is used as a pseudo measure for updating the system state for all available hypotheses. The system can be modeled as a velocity random traversal. The nth assumed system states are the same as those in the predictive model only. The velocity error may be modeled as a stochastic traversal, a stochastic constant, or a first order Gaussian-Markov (Gaussian-Markov) process. An exemplary system model using velocity stochastic traversal is given by equation (5) as follows:

wherein,

is the speed error in the x direction in the map coordinates;

is the speed error on the y coordinate in the map coordinates;

w_vxdrive noise that is x-axis speed error;

w_vyis the driving noise of the y-axis speed error.

Thus, the communication of the system state can be given by equation (6):

as will be appreciated, the predicted position may be derived from the best estimated velocity from the last epoch, while the predicted velocity may be a constant from the previous epoch, i.e., a "constant velocity" model.

Since the position from the navigation module 120 can be used as a measurement update, the measurement model can be expressed as equation (7):

wherein,

δ Z is the measured closure difference;

and

is the location of the transfer;

x_TPNand y_TPNIs a projected location update from a navigation solution; and is

v_xAnd v_yIs the measurement noise.

Note that the measurement noise may be adaptively adjusted based on location accuracy and dynamics of the user from the navigation solution. For example, when the user is walking in a straight line (small yaw dynamics), the measurement noise may be adjusted to be higher so that the system is more dependent on the prediction, and when the user is turning, the measurement noise may be adjusted to be lower to apply more weight to the measurement.

A third example employing a predictive particle-only filter may use a set of sample states or particles

To approximate the a posteriori density function (pdf) of the state of interest. Herein, each of

Is a specific shape of index iThe state samples, the index i ranges from 1 to M, M being the size of the particle filter. Thus, the examples can be used for a non-gaussian multi-model pdf. The multi-hypothesis nature of this example makes it also applicable to indoor navigation with map assistance. Similar to the kalman filter, the particle filter also has prediction and update states. Only the predictive particle filter only needs to adopt the prediction state.

The state of the predictive particle filter only may be the position and orientation of the user. During the initialization process, M random samples are derived from the position and variance of the navigation solution. This prediction is performed by the system model as indicated by equation (8):

wherein v is_LIs the driving noise of the step size, which can be modeled as a variance of

Gaussian noise of (2); and v is_ψIs the user-oriented driving noise, which can also be modeled as a variance of

Gaussian noise.

Note that when a new hypothesis is created by hypothesis analyzer 136, the new sample will be added to the current sample set according to the uncertainty of the created new hypothesis. Similarly, when a particular hypothesis is eliminated, the corresponding sample for the particular hypothesis may be removed from the sample set.

A fourth example employing a near constant velocity particle filter may use a similar concept as the near constant velocity multi-hypothesis kalman filter, and the system state corresponds to the user position and velocity. An exemplary system model is given by equation (9):

wherein, the speedThe driving noise of a degree can be modeled as a variance of

Gaussian noise. The measurement formula may be the same as that used for a near constant velocity multi-hypothesis kalman filter.

In one aspect, the positioning accuracy of the enhanced navigation solution provided by the offline map matching techniques of the present disclosure may be expressed as a user location uncertainty, such as by an error ellipse. Various factors may be used to determine this uncertainty, including: user motion uncertainty from a navigation solution, the number of hypotheses created during a period of time to augment a navigation solution, the state of hypotheses during that period, the relative proximity of any anchor points, map entities corresponding to the augmented navigation solution, or other factors. For example, the user motion uncertainty may be obtained directly from the navigation solution of the navigation module 120. Furthermore, uncertainty can be considered as having a direct correlation with the associated hypothesis that is active. When determining uncertainty, the hypothesis states may include age, weight, and the like. As described above, techniques using grid maps may facilitate determining appropriate weights for hypotheses, allowing uncertainty estimates to be computed using a weighted average of the information for all hypotheses.

In one aspect, the uncertainty may be inversely related to the age of the hypothesis, such that newer hypotheses may be considered more uncertain than older hypotheses that are assumed to have survived the management operation.

To help illustrate the benefits of the techniques of this disclosure, field tests are performed to evaluate the performance of utilizing offline map information to enhance navigation solutions. During this field test, the smartphone is used in various use cases, including a handheld mode and a pocket mode, and the smartphone is used to derive navigation solutions over varying periods of time. Subsequently, the offline map matching techniques of the present disclosure are applied to provide an enhanced navigation solution. The navigation solution derived in real time by the simulation of the navigation module 120 is represented as a contoured trajectory, the enhanced navigation solution provided by offline map matching is represented as a black trajectory, and the actual path taken by the user is represented by a cross-hatched trajectory. The pin symbols indicate anchor points, which have the order given in parentheses. For fig. 13-26, the tests were conducted at a retail location.

In fig. 13, the smartphone is held and the trace is obtained over a five minute period. In this depiction, the enhanced navigation solution trajectory overlays the reference trajectory such that deviations are indicated by cross-hatched portions. In fig. 14, the smartphone is held and the trace is obtained over a ten minute period. In this depiction, the reference trajectory overlays the enhanced navigation solution trajectory such that the deviation is indicated by the black portion. In fig. 15, the smartphone is held and the trace is obtained over a fifteen minute period. In this depiction, the reference trajectory overlays the enhanced navigation solution trajectory such that the deviation is indicated by the black portion. In fig. 16, the smartphone is in pocket mode and the trace is obtained over a twenty minute period. In this depiction, the reference trajectory overlays the enhanced navigation solution trajectory such that the deviation is indicated by the black portion. In fig. 17, the smartphone is held and the trace is obtained over a twenty minute period. In this depiction, the reference trajectory overlays the enhanced navigation solution trajectory such that the deviation is indicated by the black portion. As will be appreciated, the trajectory corresponding to the enhanced navigation solution more accurately reflects the user's true trajectory. Further, for longer periods of time indicated by fig. 14-17, the trajectory corresponding to the navigation solution is subject to increased deviation, reflecting the inherent drift of the inertial sensor, and clearly demonstrating the utility of the techniques of the present disclosure.

Next, the tests represented by fig. 18-26 are also conducted at the same retail location, and these tests reveal results obtained using forward and backward processing of the sensor data to derive navigation solutions and then applying the offline map matching techniques of the present disclosure. In fig. 18 and 19, the smartphone was held and the trace was obtained over a five minute period. In both depictions, the reference trajectory is cross-hatched and a forward processed navigation solution is shown in fig. 18, while a backward processed navigation solution is shown in fig. 19. The offline map-matching technique of the present disclosure is applied to these navigation solutions to provide the enhanced navigation solution shown in fig. 20 with two anchor points established by the point-of-sale location. Here, the cross-hatched reference trajectory is marked over the enhanced navigation solution trajectory so that the deviation is indicated by the black part. In fig. 21 and 22, the smartphone is swinging (i.e., held by a swinging arm as the user walks), and the trajectory is obtained over a ten minute period. In both depictions, the reference trajectory is cross-hatched and a forward processed navigation solution is shown in fig. 21 and a backward processed navigation solution is shown in fig. 22. The offline map matching technique of the present disclosure is applied to these navigation solutions to provide the enhanced navigation solution shown in fig. 23 with three anchor points established by the point-of-sale location. Also, the cross-hatched reference track overlay enhances the navigation solution track so that the deviation is indicated by the black part. Finally, in fig. 24 and 25, the smartphone is carried in the user's pocket and the trace is obtained over a fifteen minute period. In both depictions, the reference trajectory is cross-hatched and a forward processed navigation solution is shown in fig. 24, while a backward processed navigation solution is shown in fig. 25. The offline map matching technique of the present disclosure is applied to these navigation solutions to provide the enhanced navigation solution shown in fig. 26 with five anchor points established by the point-of-sale location. Also, the cross-hatched reference track overlay enhances the navigation solution track such that the deviation is indicated by the black portion. These tests show that very accurate trajectories can be obtained from the enhanced navigation solution.

Depending on the architecture of the device 100, the sensor processor 108 and the inertial sensors 112 may be formed on different chips or, as shown, may reside on the same chip. The sensor fusion algorithm for computing the orientation of the device 100 can be executed outside of the sensor processor 108 and the MPU 106, such as by the main processor 104, or can be executed by the MPU 106. A chip may be defined to include at least one substrate, typically formed of a semiconductor material. A single chip may be formed from multiple substrates, where the substrates are mechanically bonded to maintain functionality. The plurality of chips includes at least two substrates, wherein the two substrates are electrically connected, but do not require mechanical bonding. The package provides electrical connections between bond pads on the chip to metal leads that may be soldered to a PCB. The package typically includes a substrate and a cover. An Integrated Circuit (IC) substrate may refer to a silicon substrate having circuitry (typically CMOS circuitry).

If desired, one or more sensors may be incorporated into the package using any suitable technique. In one embodiment, the sensor may be MEMS-based, such that the MEMS cover provides mechanical support for the MEMS structure. The MEMS structural layer is attached to the MEMS lid. The MEMS cover is also referred to as a handle substrate or handle wafer. In some embodiments, the first substrate may be vertically stacked in a single semiconductor chip, attached and electrically connected to the second substrate, while in other embodiments, the first substrate may be laterally disposed in a single semiconductor package and electrically connected to the second substrate. In one example, the first substrate is attached to the second substrate by wafer bonding to simultaneously provide electrical connections and hermetically seal the MEMS device, as described in commonly owned U.S. patent No. 7,104,129, which is incorporated herein by reference in its entirety. The fabrication technique advantageously implements a technique that allows high-performance, multi-axis, inertial sensors to be designed and fabricated in very small and economical packages. Integration at the wafer level minimizes parasitic capacitance, allowing for improved signal-to-noise ratios relative to discrete solutions. Such integration at the wafer level also enables the incorporation of rich feature sets, minimizing the need for external amplification.

The techniques of this disclosure may be incorporated with any navigation solution independent of the type of state estimation or filtering technique used in the navigation solution. The state estimation techniques may be linear, non-linear, or a combination thereof. Different examples of techniques used in navigation solutions may rely on kalman filters, extended kalman filters, non-linear filters such as particle filters, or artificial intelligence techniques such as neural networks or fuzzy systems. The state estimation techniques used in the navigation solution may use any type of system and/or measurement model. The navigation solution may follow any scheme for integrating different sensors and systems, such as, for example, a loosely coupled integration scheme or a tightly coupled integration scheme, or the like. Navigation solutions may utilize modeling (whether linear or non-linear, with short or long memory lengths) and/or automatic calibration for errors of the inertial and/or other sensors used.

Contemplated embodiments

The present disclosure describes a body coordinate system: x forward, y positive towards the right side of the body, and z-axis positive downward. It is contemplated that any body coordinate system definition may be used for the application of the methods and apparatus described herein.

It is contemplated that the techniques of this disclosure may be used with navigation solutions that may optionally utilize: automatic zero velocity period or rest period detection, recalculated with its possible updates and inertial sensor bias; a non-integrable update module; advanced modeling and/or calibration of inertial sensor errors; derive their possible measurement updates from the GNSS when appropriate; automatic evaluation of GNSS solution quality and detection of degraded performance; automatically switching between a loosely coupled integration scheme and a tightly coupled integration scheme; an evaluation of each visible GNSS satellite while in the tightly coupled mode; and may ultimately be usable with a backward smoothing module having either type of backward smoothing technique, either running in a post-task or in the background of buffered data within the same task.

It is further contemplated that the techniques of this disclosure may also be used with certain patterns of transportation techniques or motion pattern detection techniques to establish a mode of transportation. This enables detection of a pedestrian mode as well as other modes, such as, for example, a driving mode. When a pedestrian mode is detected, the methods presented in this disclosure may be made operable to determine misalignment between the device and the pedestrian.

It is further contemplated that the techniques of this disclosure may also be used with the following navigation solutions: the navigation solution is further programmed to run a routine in the background to simulate manual interruption of absolute navigation information and to estimate parameters for another instance of the state estimation technique for the solution in the present navigation module to optimize the accuracy and consistency of the solution. Accuracy and consistency are evaluated by comparing the temporary background solution during the simulated interruption with the reference solution. The reference solution may be one of the following examples: absolute navigation information (e.g., GNSS); a forward integrated navigation solution in the device that integrates available sensors with absolute navigation information (e.g., GNNS), and possibly with optional velocity or speed readings; or backward smoothed integrated navigation solutions that integrate available sensors with absolute navigation information (e.g., GNNS), and possibly with optional velocity or speed readings. The background process may run on the same processor as the forward solution process or on another processor that may communicate with the first processor and may read the saved data from the shared location. The results of the background processing solution can benefit the real-time navigation solution in its future runs (i.e., real-time runs after the background routine has completed running), for example, by having improved values for the parameters of the forward state estimation technique for navigation in the present module.

It is further contemplated that the techniques of this disclosure may also be used with navigation solutions that are further integrated with maps (such as street maps, indoor maps or models, or any other environmental maps or models in the case of applications that make such maps or models available) and map-assisted or model-assisted routines. Map assistance or model assistance may further enhance navigation solutions during degradation or interruption of absolute navigation information (such as GNNS). In the case of model assistance, sensors or sensor clusters that acquire information about the environment may be used, such as, for example, laser rangefinders, cameras, and vision or sonar systems. These new systems may be used as an additional aid to enhance the accuracy of navigation solutions during absolute navigation information problems (degradation or loss), or in some applications they may completely replace absolute navigation information.

It is further contemplated that the techniques of this disclosure may also be used with navigation solutions that, when operating in a tight coupling scheme or hybrid loose/tight coupling option, are not necessarily limited to utilizing pseudorange measurements (which are computed from code rather than carrier phase and thus are referred to as code-based pseudoranges) and Doppler (Doppler) measurements (used to obtain pseudorange rates). Carrier phase measurements of GNSS receivers may also be used, for example: (i) as an alternative to computing range instead of code-based pseudoranges; or (ii) enhance range calculations by combining information from code-based pseudorange and carrier-phase measurements; such enhancements are carrier smoothed pseudoranges.

It is further contemplated that the techniques of the present disclosure may also be used with navigation solutions that rely on ultra-tight integration schemes between readings of GNSS receivers and other sensors.

It is further contemplated that the techniques of this disclosure may also be used with navigation solutions that use various wireless communication systems that may also be used for positioning and navigation as additional assistance (which would be more beneficial if GNSS is not available) or as a substitute for GNSS information (e.g., for applications where GNSS is not available). Examples of such wireless communication systems for positioning are those such as provided by cellular telephone towers and signals, radio signals, digital television signals, WiFi or WiMax. For example, for cell phone based applications, absolute coordinates from cell phone towers and distances between indoor users and towers can be used for positioning, whereby the distances can be estimated by different methods in which the time of arrival or the time difference of arrival closest to the cell phone positioning coordinates is calculated. A method known as enhanced observed time difference (E-OTD) can be used to obtain the known coordinates and distance. The standard deviation of the distance measurement may depend on the type of oscillator used in the cellular phone and the cell tower timing equipment and transmission losses. WiFi positioning may be accomplished in a variety of ways including, but not limited to, time of arrival, time difference of arrival, angle of arrival, received signal strength, and fingerprinting techniques, among others; all these methods provide different levels of accuracy. Wireless communication systems for positioning may use different techniques to model errors in ranging, angle, or signal strength from wireless signals, and may use different multipath mitigation techniques. All of the above concepts and others may also be applied in a similar manner to other wireless location technologies based on wireless communication systems.

It is further contemplated that the techniques of this disclosure may also be used with navigation solutions that utilize assistance information from other mobile devices. This assistance information may be used as additional assistance (which would be more beneficial if GNSS is not available) or as a substitute for GNSS information (e.g., for applications where GNSS based positioning is not applicable). One example of assistance information from other devices may rely on a wireless communication system between different devices. The basic concept is that a device with a better positioning or navigation solution (e.g. with a GNSS with good availability and accuracy) may help a device with a degraded or unavailable GNSS to obtain an improved positioning or navigation solution. This help relies on the known location of the assistance device(s) and the wireless communication system for locating the device(s) with degraded or unavailable GNSS. This contemplated variation relates to one or both of the following: (i) device(s) with degraded or unavailable GNSS utilize the methods described herein and obtain assistance from other devices and communication systems; (ii) an assistance device with an available GNSS and thus a good navigation solution utilizes the methods described herein. A wireless communication system for positioning may rely on different communication protocols, and it may rely on different methods, such as, for example, time of arrival, time difference of arrival, angle of arrival, and received signal strength, among others. Wireless communication systems for positioning may use different techniques to model errors in range and/or angle from wireless signals, and may use different multipath mitigation techniques.

The above-described embodiments and techniques may be implemented in software as various interconnected functional blocks or distinct software modules. However, this is not essential, and there may be cases where: these functional blocks or modules are equivalently aggregated into a single logic device, program or operation with unclear boundaries. In any case, the functional blocks and software modules that implement the features of the various embodiments or interfaces described above may be implemented by themselves, in combination with other operations in either hardware or software, entirely within a device, or in combination with the device and other processor-enabled devices (such as servers) in communication with the device.

While some embodiments have been shown and described, it will be appreciated by those skilled in the art that various changes and modifications may be made to these embodiments without changing or deviating from their scope, intent, or function. The terms and expressions which have been employed in the foregoing specification are used therein as terms of description and not of limitation, and there is no intention, in the use of such terms and expressions, of excluding any equivalents of the features shown and described or portions thereof, it being recognized that the disclosure is limited only by the claims which follow.

Claims

1. A method for augmenting a navigation solution of a portable device and a platform using map information, wherein mobility of the portable device is constrained or unconstrained within the platform, and wherein the portable device is tiltable into any orientation, the method comprising:

a) obtaining sensor data for the portable device from at least one sensor integrated with the portable device, the sensor data representing movement of the portable device over a plurality of periods of time within a first time period;

b) deriving a navigation solution for the time period based at least in part on the sensor data;

c) an enhanced navigation solution is achieved by:

i) estimating location information of the portable device based at least in part on the derived navigation solution at a time after the first time period;

ii) obtaining map information for an area containing a location of the portable device during the first time period;

iii) generating a plurality of hypotheses regarding possible locations of the portable device for at least one time period during the first time period based at least in part on the estimated location information and the map information;

iv) managing the plurality of hypotheses based at least in part on the estimated location information and the map information, wherein managing hypotheses comprises at least one of adding, eliminating, selecting, and combining at least some hypotheses; and

v) processing the managed hypotheses to update the estimated location information of the portable device; and

d) outputting the enhanced navigation solution for the at least one time period using the updated estimated location information.

2. The method of claim 1, further comprising obtaining absolute navigation information for the portable device, wherein the navigation solution derived for at least one time period is based at least in part on the absolute navigation information.

3. The method of claim 2, wherein the absolute navigation information is obtained from any one or any combination of: (i) a global navigation satellite system; (ii) a cellular-based positioning; (iii) WiFi-based positioning; (iv) positioning by Bluetooth; or (v) signal trilateration positioning using a wireless communication protocol.

4. The method of claim 1, wherein providing the enhanced navigation solution comprises performing a forward processing operation on the obtained sensor data during the first time period.

5. The method of claim 1, wherein providing the enhanced navigation solution comprises performing a reverse processing operation on the obtained sensor data during the first time period.

6. The method of claim 1, wherein providing the enhanced navigation solution comprises performing a forward processing operation on the obtained sensor data during the first time period and performing a reverse processing operation on the obtained sensor data during the first time period.

7. The method of claim 1, wherein providing the enhanced navigation solution comprises performing a forward processing operation on the obtained sensor data during the first time period, performing a reverse processing operation on the obtained sensor data during the first time period, and combining outputs of the forward processing operation and the reverse processing operation.

8. The method of claim 1, wherein providing the enhanced navigation solution comprises performing a smoothing operation over the first time period.

9. The method of claim 1, wherein providing the enhanced navigation solution comprises performing a reverse smoothing operation during the first time period.

10. The method of claim 1, wherein providing the enhanced navigation solution comprises performing a plurality of rounds of processing operations within the first time period.

11. The method of claim 1, further comprising filtering heading information of the navigation solution for at least one time period.

12. The method of claim 11, wherein filtering the heading information comprises applying a zero-phase low pass filter.

13. The method of claim 1, further comprising classifying the derived navigation solution into straight and turn segments.

14. The method of claim 13, further comprising detecting a false turn.

15. The method of claim 1, further comprising detecting a period of nonsense motion within the first time period.

16. The method of claim 15, wherein the period of nonsense motion is a period of restlessness.

17. The method of claim 16, further comprising tracking a misalignment corresponding to the period of restlessness.

18. The method of claim 16, further comprising compensating for steps detected during the period of restlessness.

19. The method of claim 1, further comprising pre-processing the map information.

20. The method of claim 19, wherein pre-processing the map information comprises extracting map entities.

21. The method of claim 20, wherein preprocessing the map information further comprises cropping at least one foreground map entity from a background entity.

22. The method of claim 21, wherein cropping the background entity defines a traversable area.

23. The method of claim 20, wherein preprocessing the map information further comprises representing a map entity as a relatively complex polygon and decomposing the polygon into a plurality of relatively simpler polygons.

24. The method of claim 19, wherein pre-processing the map information comprises generating a grid of connected routes and nodes.

25. The method of claim 1, wherein the estimated location information includes an error region representing a potential location of the portable device at least one time during the first time period.

26. The method of claim 25, wherein at least one of the hypotheses is generated by projecting the error region onto the map information.

27. The method of claim 25, wherein multiple hypotheses are generated by projecting the error region onto the map information when overlap occurs with multiple map entities.

28. The method of claim 25, wherein the map information comprises a polygon-based geometric map.

29. The method of claim 25, wherein the map information comprises a grid map.

30. The method of claim 1, wherein the map information comprises a grid map, and the estimated location information is based at least in part on a correlation between the determined user trajectory for the at least one time period and topological features of the grid map.

31. The method of claim 30, further comprising applying a weighted topology algorithm.

32. The method of claim 1, further comprising identifying an anchor point, wherein the navigation solution derived for at least one epoch is associated with the anchor point, and wherein managing the hypotheses is based at least in part on the identified anchor point.

33. The method of claim 32, further comprising identifying a plurality of ordered anchor points.

34. The method of claim 33, further comprising generating a hypothesis based at least in part on the ordered anchor points.

35. The method of claim 33, further comprising identifying a plurality of anchor points that are unordered.

36. The method of claim 33, further comprising identifying at least one anchor point that is incorrectly ordered.

37. The method of claim 1, further comprising identifying a plurality of unordered anchor points, wherein managing the hypothesis is based at least in part on the unordered anchor points.

38. The method of claim 1, wherein managing the hypotheses further comprises applying decision logic.

39. The method of claim 38, wherein the decision logic is configured for a through-wall event.

40. The method of claim 38, wherein the decision logic is configured for a level change event.

41. The method of claim 1, further comprising storing the generated plurality of hypotheses for a plurality of time periods.

42. The method of claim 41, wherein storing the generated plurality of hypotheses comprises correlating the hypotheses with one another.

43. The method of claim 42, further comprising weighting the stored generated plurality of hypotheses based at least in part on correlating the hypotheses with one another.

44. The method of claim 1, wherein the navigation solution comprises a motion pattern of a user.

45. The method of claim 44, wherein the estimated location information is based at least in part on the motion pattern.

46. The method of claim 44, wherein the hypotheses are managed based, at least in part, on the motion patterns.

47. The method of claim 44, wherein a level change event is based at least in part on the motion pattern.

48. The method of claim 1, wherein the enhanced navigation solution comprises a pattern of motion of a user detected based at least in part on a map entity associated with the estimated location information.

49. The method of claim 1, wherein the location information of the portable device is estimated using at least one of a predictive kalman filter only, a near constant velocity kalman filter, a predictive particle-only filter, and a near constant velocity particle filter.

50. The method of claim 1, wherein at least one of: deriving the navigation solution, obtaining map information, generating a plurality of hypotheses, managing the hypotheses, processing the managed hypotheses to update the estimated location information of the portable device, and providing an enhanced navigation solution using the updated estimated location information.

51. A portable device for augmenting a navigation solution of the portable device and a platform using map information, wherein mobility of the portable device is constrained or unconstrained within the platform, and wherein the portable device is tiltable into any orientation, the portable device comprising:

a) an integrated sensor component configured to output sensor data for a plurality of epochs of the portable device within a first time period, the sensor data representing motion of the portable device;

b) a navigation module configured to derive a navigation solution based at least in part on the sensor data over a plurality of sensor epochs; and

c) a processor configured to implement:

i) a location estimator to provide estimated location information of the portable device based at least in part on a derived navigation solution at a time after the first time period;

ii) a map handler for obtaining map information of an area containing a location of the portable device during the first time period; and

iii) a hypothesis analyzer for:

A) generating a plurality of hypotheses regarding possible locations of the portable device for at least one time period during the first time period based at least in part on the estimated location information and the map information; and is

B) Managing the plurality of hypotheses based at least in part on the estimated location information and the map information, wherein managing hypotheses includes at least one of adding, eliminating, selecting, and combining at least some hypotheses,

wherein the processor is further configured to update the estimated location information of the portable device based at least in part on the managed hypotheses to output an enhanced navigation solution for the at least one time period using the updated estimated location information.

52. The portable device of claim 51, further comprising a source of absolute navigation information for the portable device, wherein the navigation solution derived for at least one time period is based at least in part on the absolute navigation information.

53. The portable device of claim 52, wherein the absolute navigation information is obtained from any one or any combination of: (i) a global navigation satellite system; (ii) a cellular-based positioning; (iii) WiFi-based positioning; (iv) positioning by Bluetooth; or (v) signal trilateration positioning using a wireless communication protocol.

54. The portable device of claim 51, wherein the sensor assembly comprises an accelerometer and a gyroscope.

55. The portable device of claim 51, wherein the sensor assembly comprises an inertial sensor implemented as a microelectromechanical system.

56. The portable device of claim 51, further comprising a memory to store a plurality of hypotheses generated by the hypothesis analyzer.

57. A server for augmenting a navigation solution of a portable device and a platform using map information, wherein mobility of the portable device is constrained or unconstrained within the platform, and wherein the portable device is tiltable into any orientation, the server comprising:

a) a communication module to receive information provided by the portable device, wherein the information corresponds to sensor data representative of motion of the portable device for a plurality of periods within a first time period; and

b) a processor configured to implement:

i) a location estimator to provide estimated location information of the portable device at a time after the first time period based at least in part on a plurality of navigation solutions derived for the time period;

iii) a hypothesis analyzer for:

58. The server of claim 57, wherein the information received by the communication module comprises sensor data of the portable device, the sensor data representing movement of the portable device over the period of time, and the processor is further configured to derive a navigation solution for the period of time based at least in part on the sensor data.

59. The server of claim 57, wherein the information received by the communication module comprises a navigation solution derived by the portable device for the time period.

60. The server of claim 57, wherein the communication module is configured to send the enhanced navigation solution to the portable device.

61. The server of claim 57, further comprising a memory to store a plurality of hypotheses generated by the hypothesis analyzer.

62. A system for providing an enhanced navigation solution using map information, comprising:

a) a portable device comprising an integrated sensor assembly configured to output sensor data for a plurality of periods of time of the portable device within a first time period, the sensor data being representative of motion of the portable device, and a communication module for transmitting information corresponding to the periods of time; and

b) a remote processing resource configured to receive the information from the portable device and having a processor configured to implement:

i) a location estimator to provide estimated location information of the portable device at a time after the first time period based at least in part on a plurality of navigation solutions of the portable device derived for the time period;

ii) a map handler for obtaining map information for an area containing a location of the portable device during the first time period; and

iii) a hypothesis analyzer for:

A) generating a plurality of hypotheses regarding possible locations of the portable device for at least one time period during the first time period based, at least in part, on the estimated location information and the map information; and is

63. The system of claim 62, wherein the information received by the remote processing resource comprises sensor data of the portable device, and the remote processing resource is further configured to derive a navigation solution for the time period based at least in part on the sensor data.

64. The system of claim 62, wherein the portable device further comprises a navigation module configured to derive a navigation solution based at least in part on the sensor data for the plurality of time periods, and wherein the communication module transmits the navigation solution.

65. The system of claim 62, wherein the remote processing resource is further configured to send the enhanced navigation solution to the portable device.

66. The system of claim 62, wherein the remote processing resource further comprises a memory for storing a plurality of hypotheses generated by the hypothesis analyzer.