Method And Apparatus For Mobile Location Determination

RELATED CASES

0001This is a non-provisional application of provisional application Ser. No. 61/439,876 by Huang et al., filed 5 Feb. 2011, entitled “The present invention relates to a solution to Wireless or Signal Strength Based Mapping and Localization and more specifically to the simultaneous or real-time or post-processing mapping and/or localization of received and/or transmitted wireless and/or signal-strength information together with any combination of odometry, human interaction, or environmental context.”

BACKGROUND

00021. Field

0003This disclosure is generally related to location determination using mobile devices. More specifically, the disclosure is related to techniques that do not rely on GPS for location determination.

00042. Related Art

0005Mobile positioning via a mixture of GPS, cell towers, and previously mapped RF transmitters, e.g. WiFi access points, is commonly available. Such positioning is usually only accurate to approximately 7-25 meters—but can be 250 meters off in failure cases. Further, indoor environments tend to be poor for GPS reception, necessitating reliance on other mechanisms. One mechanism for improving reception is to make use of cell towers, e.g. use information about signal intensity from multiple known cell towers to triangulate an approximate location (200-1000 m accuracy). Another approach is to use a database of known WiFi transmitters, or other unregulated radio frequency (RF) transmitters.

0006For example, Skyhook Wireless provides software-only location mapping with about 10-20 meter accuracy using a database of known WiFi access points, GPS satellites and cell towers to compute a location. A core requirement for services like Skyhook Wireless is a reference database of WiFi access points. This database must be generated manually, e.g. via field surveys, manual data entry. Other companies such as Apple make use of the GPS in mobile devices to record a WiFi base station. These databases themselves must be regularly maintained and updated to provide good accuracy. Maintenance of such databases can require expensive monitoring equipment, trained field teams to survey locations, and regular updates. Additionally, such approaches do not address changing signal environments due to crowded-vs-empty areas, or changing signal conditions due to obstruction of the mobile devices' antenna(e) by the users' hands as the user changes the way in which he/she is holding the mobile device.

0007Still other approaches for indoor location determination such as those using ray tracing propagation models for indoor signal strength modeling, Sparse Extended Information Filter and GraphSLAM based approaches, or those approaches based on dead reckoning require prior information about the shape, layout, and sometimes materials of the location, e.g. shape priors. This approach can work if there are pre-existing maps and shape information that an authoritative source can provide. However, such an approach is often too computationally complex to run within the constraints of a mobile device or does not always work well in changing, or dynamic, environments.

0008Accordingly, what is needed is a method and apparatus for location determination on mobile devices without the need for prior information about the location, e.g. information about either the space itself or the unregulated RF transmitters/transmissions in the space.

BRIEF DESCRIPTION OF THE FIGURES

0009<figref idref="DRAWINGS">FIG. 1</figref> shows an architectural level schematic of a system in accordance with an embodiment.

0010<figref idref="DRAWINGS">FIG. 2</figref> shows an example of an embodiment of the location system in use on a mobile device.

0011<figref idref="DRAWINGS">FIG. 3</figref> is a process flow diagram for the location determination process according to one embodiment.

0012<figref idref="DRAWINGS">FIG. 4</figref> is a process flow diagram for refinement of the location determination process according to one embodiment.

0013<figref idref="DRAWINGS">FIGS. 5-6</figref> show example results from embodiments of the location determination process.

DETAILED DESCRIPTION

Related Cases . . . 1

Background . . . 1

0014Field . . . 1

0015Related Art . . . 2

Brief Description of the Figures . . . 3

Detailed Description . . . 3

0016Overview . . . 4

0017Terminology . . . 7

0018System Overview . . . 8

0019Positioning . . . 16

0020Further Improving Signal Maps . . . 30

0021Examples and Further Discussion . . . 35

0022Conclusion and Additional Embodiments . . . 37

0000claims . . . 45

Abstract . . . 51

Overview

0023The discussion is organized as follows. First, an introduction describing some of the problems addressed by various embodiments will be presented, followed by an explanation of terminology that will be used throughout the discussion. Then, a high level description of one embodiment will be discussed at an architectural level. Next, the details of processes used by some embodiments will be discussed. Then, some applications will be discussed. Lastly, various alternative embodiments are discussed.

0024Let's consider Lane visiting a convention. Because the space was set up at the last minute, there is no mapping of the WiFi access points in the convention center, some of which may have been replaced recently and not surveyed, some of which were erected by booths for the show, etc. However, the convention organizers likely have a general map of the show floor with exhibitor names that they can load into the mobile application for the convention. At the convention center, Lane pulls out his mobile phone and launches the mobile application, or website, for the convention, e.g. XYZ Convention 2011. It is desirable to provide Lane an easy way to track his path through the convention floor, ensure that Lane visits all of the exhibitors on his list of people to see, and do so on the mobile device even when GPS is poor or unavailable, and even if the landscape of the convention floor has changed since the map was finalized. In this context GPS may be poor both in terms of signal quality, but also in terms of high power requirements. Further, existing alternatives to GPS may also be too costly, e.g. pre-mapping locations or establishing pre-determined beacons within the location. Other features may include better accuracy in finding and meeting up with others at the convention. Other features may include optimal routes to visit booths you've expressed interest in. Other features may include handling for congestion in an area, e.g. dynamically suggesting alternative routes based on congestion in a part of the convention floor. Similar features could be used for route planning at large locations like theme parks with attractions if the location system <b>120</b> can contact a data source, e.g. in company info <b>112</b> or a third-party website, providing information about wait times for attractions. Additionally, such a feature could take into account congestion caused by events such as parades and shows. Other features can include providing a browsing history, e.g. booths you've visited; interactivity with the exhibits, e.g. displaying content relevant to the nearby booths; and/or personalization, e.g. depending on your interests, different information is shown. In the personalization context, for example, medical doctors registered at a medical convention might see different information than hospital administrators when near the same booth.

0025Other uses for better mobile location determination include shopping, e.g. at a mall generally, and within a store such as a department store, grocery store, pharmacy, specialty boutique, etc. For example, if Lane were using the XYZ Mall Application to wander through the XYZ Mall, he could receive targeted advertising as he approaches certain stores. Similarly, users looking at (adjacent to) a Brand X diaper display within a store could be offered coupons for that brand of diapers or a competitor's diaper. In some embodiments, a price checking functionality is supported. This embodiment could be offered by a competitor that uses knowledge of one store's layout, e.g. Safeway #123, to suggest lower priced alternatives they sell or as a brand competition mechanism, you are near Pepsi right now, but just a few meters down, there is a special on Coke. Other embodiments can include, providing supplemental nutritional information on nearby products;

0026providing reviews from other web sites and/or your social network(s) about nearby products; and/or providing supplemental information, e.g. highlighting products already on sale, advising of future sales.

0027Notably uses of the embodiments go beyond basic “check in” at a location to providing improved functions around a user's more precise location. For example, in the shelf position example, accuracy of closer to 1 m, optionally supplemented with other information such as heading (looking at the diapers or the other side of the aisle), movement speed (standing still in front of the diapers vs. walked right past), is important.

0028Although embodiments make use of communications and may use public networks such as the internet, e.g. for communication from the mobile devices to a server, one important feature is the relatively low amount of communication with the server. The minimal communication overhead enables the servers to scale to handle millions and millions of users even when the end points are from different providers and/or supporting different applications. Note that in some embodiments, there is no communication and/or all communication is offline of the location determination process. However, in some embodiments, some entities may set up a dedicated server that mobile devices could connect to. The minimal communication needs also help handle tens of thousands of devices in large venues over bandwidth-limited networks like cellular. For example, all thirty-thousand-plus attendees at a concert location with mobile devices could all easily use the location system <b>120</b> without significant bandwidth impacts. Additionally, because power consumption in mobile devices needs to be carefully managed, embodiments make use of particularly power-friendly computational techniques for location determination.

0029The use by some embodiments of WiFi transmissions for location determination takes advantage of a combination of WiFi's ubiquity as well as an ability to make use of the transmission without the need for the mobile device to connect to a network using the WiFi transmission. Specifically, a WiFi beacon with the MAC address is sufficient for mapping purposes. Additionally, from a power consumption standpoint, mobile devices may already be programmed to periodically scan for WiFi access points, some embodiments leverage such periodic scans and/or increase the frequency of such scans to build location and mapping information.

0030Additionally, embodiments make modified use of techniques drawn from fields of robotics such as SLAM (simultaneous location and mapping) including FastSLAM variants to provide mobile location determination. Embodiments make use of machine learning techniques, structured probabilistic models, Bayesian filtering, and sequential importance resampling to provide mobile location determination.

0031We describe a system and various embodiments to provide improved mobile location determination.

Terminology

0032Throughout this specification the following terms will be used:

0033Mobile Device: A mobile device is a portable electronic device such as a mobile phone, smartphone, or the like. Current exemplary mobile devices include iOS devices such as the iPhone, and Android devices such as the Nexus smartphone or Kindle tablets. Generally, some embodiments are targeted at small, handheld devices that a user can both easily transport and use while walking. Generally, the mobile device can have multiple sensors integrated such as accelerometers, and gyroscopes as well as multiple receivers such as GPS, cellular, a WiFi, and Bluetooth. Additionally, the mobile device will have a display and user input capabilities. Notably, embodiments may make particular use of inputs common on mobile devices such as buttons and touch inputs, a camera to decode barcodes, QR-codes, and/or other image analysis as well as microphones for voice recognition and/or sound analysis. Thus, the definition of mobile device could include portable electronic devices other than a smartphone such as tablets or portable, or laptop, computers, and their peripheral devices.

0034Unregulated radio frequency (RF) Transmitter, unregulated RF transmission: An unregulated radio frequency (RF) transmitter or transmission refers to RF transmitters/transmissions where there is not a regime of government regulation for positioning the transmitter/transmission sources. For example, cellular towers used for 3G/LTE are regulated RF transmitters. Similarly, GPS satellites are viewed as regulated RF transmissions. In contrast, unregulated RF transmitters are deployed in an ad hoc fashion, e.g. WiFi base stations, Bluetooth devices, near field communications (NFC) transmitters. Certain RF sources do not neatly fall into one category or the other, e.g. microcells/picocells for cellular communications. However, for purposes of this discussion, the term “unregulated” focuses on transmitters/transmissions where the transmitters can be moved/installed/changed regularly. There is an additional emphasis in some embodiments on WiFi transmitters/transmissions because of their ubiquity. Additionally, even if the position of the transmitters is allegedly known, it may be insufficient. For example, managed WiFi networks where the installer is supposed to record the location of the WiFi device are reported to often contain inaccurate location information. Thus, such information, where available, could be an input to some embodiments for coarse location determination.

0035Location: Location is used to refer to two distinct concepts in this document; the usage should be apparent from context. The first meaning refers to the general area you are in, e.g. the XYZ store #123, the ABC Convention Center, Central Park or a region within Central Park. The second meaning refers to the more precise position of the mobile device, and thus the user. Specifically, this second meaning of location can be a global coordinate, e.g. latitude/longitude plus altitude/floor or a relative x, y, z coordinate. This second meaning of location may also be referred to as position.

System Overview

0036A system and various embodiments to provide improved mobile location determination will be described with reference to <figref idref="DRAWINGS">FIG. 1</figref>, which shows an architectural level schematic of a system in accordance with an embodiment. Because <figref idref="DRAWINGS">FIG. 1</figref> is an architectural diagram, certain details are intentionally omitted to improve the clarity of the description. The discussion of <figref idref="DRAWINGS">FIG. 1</figref> will be organized as follows. First, the elements of the figure will be described, followed by their interconnections. Then, the use of the elements in the system will be described in greater detail.

0037<figref idref="DRAWINGS">FIG. 1</figref> includes a system <b>100</b>. The system includes external sources <b>110</b>, location system <b>120</b>, and end points <b>130</b>. The external sources <b>110</b> include map source <b>111</b>, company info <b>112</b>, and location info <b>113</b>. The location system <b>120</b> includes a controller <b>121</b> and storage <b>122</b>. The end points <b>130</b> include mobile <b>131</b>, mobile <b>132</b>, mobile <b>133</b>, and tablet <b>134</b>. Mobile <b>131</b> is coupled in communication with a display <b>160</b> showing a user interface generated by a combination of location software on the mobile <b>131</b> and location system <b>120</b> in accordance with one embodiment. Additionally, user input <b>150</b> to mobile <b>131</b> is shown, as well as sensors <b>155</b>, an unregulated RF receiver <b>157</b> and location software <b>159</b>.

0038The interconnection of the elements of system <b>100</b> will now be described. The external sources <b>110</b> are coupled in communication to the location system <b>120</b> (indicated by double-headed line with arrows at end). The different sources may arrive via different mechanisms. For example, the map source <b>111</b> may be retrieved over a network, e.g. the internet, using one or more protocols, such as HTTP using various APIs such as REST or SOAP. Other information such as the company info <b>112</b> or the location info <b>113</b> may be accessed over a different network, e.g. private network, VPN, MPLS circuit, or internet, and may be obtained using any appropriate API or download mechanism, e.g. SFTP download of data for processing and storage by the location system <b>120</b>. All of the communications may be encrypted and, as appropriate, the decryption credentials may be available to the location system <b>120</b> directly, or may be stored in storage <b>122</b> in encrypted form. Additionally, a variety of authentication techniques such as username/password, OAuth, Kerberos, and more can be used for the communications between the external sources <b>110</b> and the location system <b>120</b>.

0039Controller <b>121</b> and storage <b>122</b> can be composed of one or more computers and computer systems coupled in communication with one another. They can also be one or more virtual computing and/or storage resources. For example, controller <b>121</b> may be an Amazon EC2 instance and the storage <b>122</b> an Amazon S3 storage. Other computing-as-service platforms such as Force.com from Salesforce, Rackspace, or Heroku could be used, rather than implementing the location system <b>120</b> directly by the operator using physical computers or physical computers operating traditional virtual machines. Communications between the potentially geographically distributed computing and storage resources comprising the location system <b>120</b> are not shown.

0040The end points <b>130</b> are similarly coupled in communication to the location system <b>120</b> (indicated by double-headed line with arrows at end). This communication is generally over a network such as the internet, inclusive of the mobile internet, via protocols such as EDGE, 3G, LTE, WiFi, and WiMax. The end points <b>130</b> may communicate with the location system <b>120</b> using HTTP/HTTPS protocols and may be implemented in one embodiment using either a web interface or application to enable easy support of a range of device types as end points <b>130</b>. The mobile <b>131</b> can be any mobile device, see definition supra, e.g. iPhone, Android phone, Windows phone, Blackberry. The tablet <b>134</b> is considered a mobile device, see definition supra, and could be a tablet computing device, e.g. iPad, iPod Touch, Android tablet, Blackberry tablet. Other types of mobile devices such as laptops are not shown, but could be used. According to some embodiments, the location software <b>159</b> is implemented on end points as an HTML, or web, application while in other embodiments, a custom, or native, user interface is prepared for the device. Similarly, some mobile devices support an “application store” concept and the location software <b>159</b> may be a download from the app store. In some embodiments, direct communication (not shown) between end points <b>130</b> and external sources <b>110</b> is performed. It bears emphasis that the discussed communications can be offline relative to the location determination process, thus making communication with a server resource optional during the processes described herein.

0041The display <b>160</b> is coupled in communication with the mobile <b>131</b>, and the mobile <b>131</b> is capable of receiving user input <b>150</b>, e.g. via keyboard, mouse, track-pad, touch gestures (optionally on display <b>160</b>), camera and microphone, peripheral devices. The sensors <b>155</b> are coupled in communication with the mobile <b>131</b> (and generally integrated therewith). Similarly, the unregulated RF receiver <b>157</b> is coupled in communication with the mobile <b>131</b> (and generally integrated therewith). The location software <b>159</b> is stored on the mobile <b>131</b>, e.g. in volatile and/or nonvolatile memory for execution by the processor(s) of the mobile <b>131</b>.

0042The communication between the location system <b>120</b> and the end points <b>130</b> can be bidirectional with the end points <b>130</b> directly making requests to the location system <b>120</b> and the location system <b>120</b> directly making requests to the external sources <b>110</b>.

0043Having described the elements of <figref idref="DRAWINGS">FIG. 1</figref> and their interconnections, the system will be described in greater detail. This will be accomplished in conjunction with a discussion of <figref idref="DRAWINGS">FIG. 2</figref> showing an embodiment of the location system in use on a mobile device in scenario <b>200</b>. Specifically, scenario <b>200</b> shows a user <b>210</b> with mobile <b>131</b> navigating location <b>220</b>. Scenario <b>200</b> highlights the optionality of communication between end points <b>130</b> and location system <b>120</b> by marking the communication path between the mobile <b>131</b> and the location system <b>120</b> as optional (optional communication path <b>205</b>).

0044For discussion purposes, we will treat location <b>220</b> as a grocery store. In scenario <b>200</b>, the location <b>220</b> has four wireless access points (wireless access point <b>232</b>, wireless access point <b>234</b>, wireless access point <b>236</b>, wireless access point <b>238</b>) that are unevenly distributed. The locations of the wireless access points within the grocery store are shown in the figure for discussion purposes, but notably need not be known to the mobile <b>131</b> or the location system <b>120</b>, and could be either inside or outside the grocery store. Additionally, the wireless access points need not be within the grocery store, for example some or all of the access points could be in adjoining stores and those RF transmissions could be detected within the grocery store. The grocery store has several shelves and freezer cases (obstacle <b>222</b>, obstacle <b>224</b>, obstacle <b>226</b>, and obstacle <b>228</b>). Again, obstacle locations are shown in the figure for discussion purposes, but need not be known to the mobile <b>131</b> or the location system <b>120</b>. Also, the actual path <b>250</b> that our user <b>210</b> will take in walking through the store is shown (dashed line with dots). The user's present position is shown as the solid dot at to. Several additional points on the user's path are marked as t₁, t₂, t₃, t₄, t₅, t₆, and t₇. These points have been selected for discussion and represent locations the user will visit during this visit to the grocery store on the user's actual path <b>250</b>. Again, actual path <b>250</b> is not known to the mobile <b>131</b> or the location system <b>120</b>, but rather the goal of the location software <b>159</b> and/or the location system <b>120</b> is to determine the user's location within the grocery store at any time. This, in turn, could be used to generate a calculated path (not shown) that will not precisely follow the actual path <b>250</b>; however, using the approaches shown here, accuracy of approximately 1 meter is possible.

0045It bears emphasis that the location software <b>159</b> can be delivered as a library, software development kit (SDK) to application developers, or application programmer interface (API) to other software. The discussions herein will generally focus on embodiments where the location software <b>159</b> is a standalone application. However, it is expected that some embodiments have the functionality of the location software <b>159</b> encapsulated in other software, e.g. a Safeway application as opposed to a more general-purpose location software. Such embodiments may thus encapsulate some or all of the company info <b>112</b> directly in the application, e.g. store maps and directories may be pre-loaded in the Safeway application. Additionally, such applications may have greater contextual data available and/or offer customized features. In some embodiments, the correct contextual application, e.g. Safeway application, may be launched by the mobile device's operating system based on the general location and then the more detailed location capabilities of the system <b>100</b> become available within the specific application.

0046Lastly, <figref idref="DRAWINGS">FIG. 2</figref> shows one possible display <b>160</b> on the mobile <b>131</b>. This particular display shows the user's present position (solid dot) as well as the obstacles, for example if the location system <b>120</b> were able to obtain the indoor map from either map source <b>111</b> or company info <b>112</b>. As noted, the location of obstacles is not required. However, easy integration with external sources of mapping data is a feature offered by some embodiments, and the display shown in <figref idref="DRAWINGS">FIG. 2</figref> is a useful place to provide an example.

0047The basic operation of the location determination approach is as follows. The mobile <b>131</b> receives a signal indicating that the user wishes to know their location, e.g. precisely where they are. The mobile <b>131</b> can optionally communicate with the location system <b>120</b> for information. However, one feature of embodiments is minimal, or no, need for mobile-to-server communications. Specifically, one advantage is that embodiments allow full processing of the location computation to be done on the mobile <b>131</b>. However, mobile-to-server communications allow for retrieval of useful information. Specifically, the primary server optional information can include: (i) maps, (ii) company-specific information (company info <b>112</b>) and/or customizations, (iii) supplemental location information, (iv) prior visit data, and (v) other internet delivered information. More generally, the company info <b>112</b> includes contextual metadata about the venue and/or event.

0048Taking each type of optional data in turn, starting with maps, the simplest form of map would be a scale image of the grocery store, convention floor, outdoor concert venue, or the like. More advanced maps may include additional information such as the location of specific items/brands/merchandise on a dynamic basis. For discussing the system, maps are considered to be retrieved from map source <b>111</b> which can be multiple sources such as company websites, convention center websites, and the like. In some instances, entities may be provided a mechanism for interacting with the location system <b>120</b> (not shown) to manually and/or programmatically provide maps. For example, companies can be provided a mechanism to upload a file containing a list of all of their store locations, together with a URL for retrieving a map of the store. In such an example, the download sites for the maps would be the map source <b>111</b>. For outdoor venues, simply knowing your location in the venue more precisely, as well as the location of your friend(s) in the venue, may be more than adequate without maps. Some embodiments support find-my-friend features and make use of mobile-to-server communications to enable that feature. However, for many indoor locations, maps can provide additional context for users to make use of the system.

0049The next category of optional server-provided information is company information (e.g. company info <b>112</b>). As discussed, supra, this can take a number of forms, including customized and/or co-branded software to use for the location software <b>159</b>. In other embodiments, the location software <b>159</b> can be customized on entry to a location, e.g. when you enter a Safeway, certain Safeway-specific customizations are loaded. The company info <b>112</b> could also be highly location specific, e.g. how freshly baked the bread you are standing near is, supplemental nutrition data for nearby products. The location system <b>120</b> obtains this information from the company info <b>112</b>. Exemplary features may include the display of one or more customized buttons on the display in a context- and location-aware fashion. For example, if the user seems to be lost (repeatedly moving over the same area or in circles), then a “Need somebody to help button?” could appear and the user's location could be sent to someone at the store. Similarly, coupons and/or advertisements could be targeted based on where the user is standing. Other usage contexts may have other features, e.g. customized features for a convention might help you make a list of booths you want to visit, plan a route over the show floor, and automatically check off booths you stopped at for at least 30 seconds. In another embodiment, a record is maintained of booths visited and the time of the visit and this is made available to the user as an itinerary to enable the person to associate business cards, company website content, and more with the location data. This is an example list of supported features for some embodiments from the company info <b>112</b>, but highlights the capability of the system.

0050Turning to the location info <b>113</b>, one or more third-party databases such as Skyhook lists of WiFi hotspot locations, databases of cell tower locations, and operating system-provided location information can be used to improve (i) accuracy, (ii) the initial absolute location determination, (iii) time-to-fix upon a location, and (iv) outlier rejection. Returning to scenario <b>200</b>, if this is the first time any user of the location system <b>120</b> has visited the location <b>220</b>, it could be difficult to determine the user's starting position (t₀). This may be particularly true for indoor locations. As such, while the system will function and show a path without absolute positioning information, finding the right map and/or figuring out where the user started from poses a different set of problems, e.g. longer time-to-fix on a location, orientation determination, etc. In some instances, location information may be provided from context, e.g. user is using the Safeway application (e.g. as location software <b>159</b>) thus more uniquely identifying her starting position. Thus, location info <b>113</b> offers a mechanism to make use of third-party data sources. In some embodiments, the mobile <b>131</b> may include features in the operating system that can similarly estimate a user's global position, and those features could be used instead of or in addition to the location info <b>113</b>.

0051The final main category of optional server-provided information to the mobile is signal maps from prior visits to the location <b>220</b>. Given the uniqueness of WiFi MAC identifiers, if the mobile <b>131</b> communicates the MAC identifier of hotspots near the mobile <b>131</b> to the location system <b>120</b>, then signal map data from prior visits to the location <b>220</b> can be sent to the mobile <b>131</b> for use in location determination. The approach to building signal maps using prior run data will be described in connection with <figref idref="DRAWINGS">FIG. 4</figref>.

0052Returning to the basic process and the uses of the elements of <figref idref="DRAWINGS">FIG. 1</figref>, as the user <b>210</b> moves along actual path <b>250</b>, the sensors <b>155</b> of the mobile <b>131</b> will record the movement, and the location software <b>159</b> will maintain a log of the sensor information, as well as the signal strengths on the unregulated RF receiver <b>157</b> and user inputs from user input <b>150</b>. For example, if a certain bar code is regularly associated with a certain set of WiFi MAC addresses, that can assist in location determination and signal snapshot refinement. The collected information can then be used to determine the user's location as will be described in greater detail in connection with <figref idref="DRAWINGS">FIG. 3</figref>.

0053In summary, the architecture of system <b>100</b> and the components and mechanisms through which it affords improved mobile location determination have been described. Benefits of the described embodiments include: minimal to no reliance on GPS (high power, poor quality indoors, and insufficient accuracy); computations can be performed solely on the mobile device; mobile device-server communications minimized (so millions of devices can be handled with relative ease) and optional; no prior knowledge of locations required (easy adaptation to changes in the location such as rearrangements (of access points and floor layout/obstacles); low cost for a company to include their locations because no costly pre-mapping is required); capable of high accuracy (positioning accuracy of 1-3 m which then supports greater targeting of information and offers); and personalized to the user (information from social network(s) can be incorporated) with direct feedback on location and information available.

0054Expanding on each of these points briefly, starting with minimal to no reliance on GPS. GPS requires relatively high power consumption for a mobile device and for indoor uses, is particularly poor quality. Additionally, the accuracy provided by GPS is insufficient for the level of granularity sought, 1-3 m location accuracy. Some embodiments make minimal use of GPS to make an initial absolute location determination and, optionally, as part of a query to obtain information from sources over a network. Computations can be performed solely on the mobile device, thus reducing mobile device-to-server communications. As noted previously this allows the server, e.g. location system <b>120</b>, to easily scale and efficiently handle huge numbers of users at a time.

0055Many existing location systems, especially those making use of WiFi require detailed prior knowledge of locations. For example, without a floorplan for a store, the prior systems may not work. Similarly, prior system that are not pre-provided information about the WiFi hotspots as measured by special measurement equipment may not work. Since floor layouts and WiFi transmission patterns change regularly, this approach can be extremely costly for businesses that want to provide advanced location-based functionality within their establishments. Additionally, wrong data about locations of WiFi access point placements are often provided. Highly inter-related is the capability for embodiments to offer high accuracy, 1-3 m, which in turn allows for support of a variety of functionality for both businesses and users.

0056Additional aspects of the system will be described in greater detail with reference to the scenario <b>200</b> and process flow diagrams in the subsequent figures.

Positioning

0057<figref idref="DRAWINGS">FIG. 3</figref> is a process flow diagram for the location determination process according to one embodiment. In this embodiment the processing may occur solely on the mobile device, e.g. mobile <b>131</b>, though points where optional communication with the location system <b>120</b> can be used will be discussed. In this embodiment, the process is primarily performed by location software <b>159</b>.

0058<figref idref="DRAWINGS">FIG. 3</figref> includes process <b>300</b> which has two primary flows shown separately to emphasize their independence and parallelism. The first flow is step <b>310</b>, collect measurements (used at step <b>330</b>). A loop emphasizes the continual iteration of this process. In one embodiment, this step occurs multiple times per second. For example in one embodiment, the location determination (step <b>330</b>), discussed infra, occurs every 0.05 seconds, as such measurement collection will generally be more frequent, though different sensors will have different collection rates. The specific measurements collected will vary based on the available sensors <b>155</b>, user input <b>150</b> and receiver <b>157</b> on the mobile <b>131</b>. Additionally, in some embodiments, step <b>310</b> may involve the software registering with the operating system to receive messages with measurement info already being collected by the system. In other embodiments, some measurements must be taken directly, and the software may need to run in the background and/or periodically poll for information. In one embodiment, step <b>310</b> includes logging information from sensors <b>155</b> in a log file with a timestamp, together with information from receiver <b>157</b> (e.g. signal strength of transmitters in range together with identifiers), and selected user inputs <b>150</b>. The information logged will be described in greater detail below in connection with step <b>330</b>. Also, while this discussion covers an embodiment using a text file to store the data, other data storage approaches are used by other embodiments, e.g. structured databases, key-value stores, etc. The term log or log file as used herein is used in the sense of referring to information linked to a timestamp, as opposed to a specific format such as a text log file, string formats, data structures and/or databases. The term data structure as used herein refers to a way of storing and organizing data in a computer system and should be understood to encompass objects and/or object oriented approaches. Additionally, some data structures may be stored or represented in databases.

0059The other flow of process <b>300</b> is the main location determination flow. This starts at step <b>320</b> with the optional download of information from the location system <b>120</b>. As discussed, supra, this can include obtaining maps, company information, location information, and/or prior signal maps for the location. This step may include transmitting some information from the measurements (step <b>310</b>). For example, the MAC identifiers for WiFi base stations sited by the mobile device in the last few readings could be transmitted to the location system <b>120</b>. The location system <b>120</b> could then provide signal maps from other users or other information about the location.

0060The process continues at step <b>330</b> with location computation from the collected measurements. Once the location is computed, it can be updated and displayed at step <b>340</b> to the user, e.g. the user <b>210</b> on display <b>160</b> of mobile <b>131</b>. Process <b>300</b> reflects a process for interactive location map/path display, thus step <b>340</b> is described as regularly occurring. In some embodiments, the user's location is not continually displayed, but rather only selectively displayed and/or displayed in the context of visited/unvisited areas. For example, in a museum, you might show unvisited vs. visited exhibits. At step <b>350</b>, optional user location input is possible; this may be particularly valuable for initial location determination and/or helping the system fine-tune the location. As discussed, some user input may be in the form of video and/or audio. For example, a bar code decoded from the camera may be helpful in fine-tuning the location and thus the signal map. This may be particularly true in company-specific application, e.g. Safeway app and user is scanning a frozen food item that is normally stored on aisle 7 of Safeway 123. Additionally, an explicit loop is shown here back to step <b>330</b> to emphasize the ongoing nature of the process <b>300</b>.

0061Separately, the upload of signal map information (e.g. log data from step <b>310</b>) from the mobile <b>131</b> to the location system <b>120</b> is shown as outside the main loop at step <b>360</b>, which is optional. Step <b>360</b> could occur at other times, e.g. every X seconds/minutes/hours; as part of the step <b>310</b>; in a location-aware fashion, e.g. when a user leaves a location, the logs for that location are sent; based on bandwidth between the end points <b>130</b> and the location system <b>120</b>; as part of a reward/game mechanic to encourage visits to and collection of signal snapshots from a variety of location. Other embodiments may use additional location-aware triggers for step <b>360</b>, e.g. places with fewer existing signal snapshots may trigger step <b>360</b> more often then heavily visited locations, or places where greater precision is needed.

0062The process used by some embodiments at step <b>330</b> will now be discussed in greater detail. A Python-style pseudocode format will be used to discuss the process; however, other implementations are possible. There are two primary concepts for which processes will be presented: (i) assessing how good a guess of a location is as a match to the prior path model and the collected measurements; and (ii) how to make good guesses about the current location.

Fit Functions

0063Turning to the first issue, consider a simple example, accelerometer input only (so just relative movement information—no absolute position information). So, the user is walking with a mobile device, and there is a raw_log_file available as a data structure with timestamped accelerometer data. This function assigns a fit value to a proposed position that the user walked in a path_history data structure with locations every 0.05 seconds in one embodiment. The 0.05 seconds is not linked to the raw_log_file frequency per se, but rather to the rate selected for the path determination updates.

0000<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="35pt" align="left" /><colspec colname="1" colwidth="182pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def fit_function(path_history,</entry></row><row><entry /><entry>raw_log_file):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="49pt" align="left" /><colspec colname="1" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>total_fit = 1.0 # start with 100% fit</entry></row><row><entry /><entry>for each u in path_history:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><tbody valign="top"><row><entry /><entry>total_fit *=</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="35pt" align="left" /><colspec colname="1" colwidth="182pt" align="left" /><tbody valign="top"><row><entry /><entry>fit_function_accelerometer(u, raw_log_file)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="49pt" align="left" /><colspec colname="1" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>return total_fit</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0064To avoid multiplication in the computation, addition and logarithms can be used instead, thus speeding up computations and avoiding the possibility of overflow. So, consider how the fit of the accelerometer can be computed. The following conventions are used: u corresponds to a moment in time, u.location( ) is the specific x, y, z for that time, and u.t( ) is the timestamp. Similarly, p is the previous guess to u in the path_history and, in this embodiment, would be exactly 0.05 seconds prior in time; however, the more generic equation is shown.

0000<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def fit_function_accelerometer(u,</entry></row><row><entry /><entry>raw_log_file):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>distance = distance(u.location,</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>p.location)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>accelerometer_readings =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_log_file.get_accel_readings(u.t( ) − 0.2), u.t( ))</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>if at_rest(accelerometer_readings)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>return StandardGaussian(distance,</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>sigma_squared=0.01)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>else:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>regular_walking_speed = 1.22</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>meters per second</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>regular_walking_distance =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>regular_walking_speed * (u.t( ) − p.t( ))</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>return Laplace(distance −</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>regular_walking_distance, scale = 0.44)</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0065The constants used above are exemplary only, e.g. 1.22 meters per second, looking at the recent 0.2 seconds of accelerometer readings, using 0.01 in the Gaussian, and scaling the Laplace by 0.44. However, the values chosen correspond to prior research on walking paces. Other embodiments can use a more dynamic approach by counting the number/frequency of impulses like a pedometer. Similarly, the use of Gaussian and Laplace functions is not required; other functions could be used instead. These numbers should work well for common use cases of phone in pocket, phone swinging in hand, phone in front of user being looked at. The test for at_rest is straightforward:

0000<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="49pt" align="left" /><colspec colname="1" colwidth="168pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def at_rest (accelerometer_readings):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><tbody valign="top"><row><entry /><entry># input is a time series of</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="49pt" align="left" /><colspec colname="1" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>accelerometer measurements</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><tbody valign="top"><row><entry /><entry>return false if there are oscillations</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="49pt" align="left" /><colspec colname="1" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>in the readings</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><tbody valign="top"><row><entry /><entry>return true otherwise</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0066At this point, using the accelerometer only, an approach to determining whether a guess is a good fit or a bad fit for where the user's path has been presented. Returning to <figref idref="DRAWINGS">FIG. 2</figref>, if the user was at the location indicated by t₃and the recent accelerometer data reflected the distance between t₂to t₃, a guess of the location at t₇should be a worse fit for the accelerometer readings than a guess of the location at t₅. Before discussing the process for making guesses, we will discuss adding WiFi to the mix as an example of one unregulated RF signal to incorporate.

0067A signal_snapshot is a data structure that maps information about received WiFi transmitters in a physical vicinity. In one embodiment the map is divided into a two-meter (2 m) square grid—often referred to as cells—with the following for each transmitted in the map grip: the mean, the variance and the number of samples. More generally embodiments will either (a) maintain past measurements directly, e.g. list, or (b) maintain a set of sufficient statistics. The use of mean, variance, and number of samples is data compact and efficient to update with new data.

0068The fit_function can be modified to include the signal_snapshot and an adjustment based on WiFi:

0000<br />total_fit*=fit_function_wifi (u, raw_log_file, signal_snapshot)

0069Again, logarithms and addition can be used to avoid multiplication. Also, weightings can be applied if one sensor is more accurate than another. Alternatively, dynamic weightings can be applied, for example when at_rest==true the accelerometer could be emphasized because the WiFi readings will be more redundant as they are from the same location. The fit_function_wifi could be implemented as:

0000<tables id="TABLE-US-00004" num="00004"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def fit_function_wifi(u, raw_log_file,</entry></row><row><entry /><entry>signal_snapshot):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_wifi_readings =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_log_file.get_wifi_readings(u.t( ))</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>radio_map_cell =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>signal_snapshot.get_nearest_radio_map_cell(u.location( ))</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>total_fit = 1.0</entry></row><row><entry /><entry>for each mac_address in</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_wifi_readings:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>expected_wifi =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>radio_map_cell[mac_address]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>measured_signal_strength =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_wifi_readings[mac_address]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>total_fit *=</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>Rayleigh(measured_signal_strength,</entry></row><row><entry /><entry>expected_wifi.parameters)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>return total_fit</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0070This example does not include adjustments for gain factors such as transient environment effects, orientation of mobile device/antenna, crowded/empty room, antenna properties specific to mobile device model, or hand position over antennas. The gain factor could be guessed and incorporated as an adjustment to the inputs to the Rayleigh calculation, e.g. adjustments to measured_signal_strength or expected_wifi.parameters. Also, to handle cases where the current signal_snapshot does not have a map for the current cell, get_nearest_radio_map_cell could return the adjacent neighboring cells, and then expected_wifi.parameters could return the bilinear interpolation between those neighbors. Other interpolation approaches are possible too, e.g. eight neighbors, quadratic interpolation. Also, use of the Rayleigh distribution in volts is not required, but provides advantages. Other choices selected by some embodiment include: use of empirical log-distance path loss model, use of the Gaussian distribution in dBm, Nakagami-Ricean in volts, Loo's distribution (for shadow and multipath).

0071Intuitively, each grid (or cell/square) of the signal_snapshot describes the distribution of possible WiFi signal strengths for each transmitter “visible” at the cell's location. Returning to <figref idref="DRAWINGS">FIG. 2</figref> and scenario <b>200</b>, when the user is standing at t₃, the signal strengths for the wireless access points <b>232</b>-<b>238</b> should look quite different than when the user is at t₇. Also, other unregulated RF transmissions could be mapped, e.g. RFID, NFC, Bluetooth. In an alternative embodiment, regulated signals such as cellular signals and broadcast TV/radio can be used too; however, in some embodiments, the broadcast TV/radio may have too little variance over small distances to provide useful location determination at a fine level. What is important, in some embodiments, is that the reference signal has variation in signal strength over a short distance and the source can be identified. Nonetheless regulated signals like TV/radio can help with coarse location identification and may also be helpful for: distinguishing between floors of a building, distinguishing between two different rooms (as opposed to position within the room), time-to-fix, outlier rejection, and as an alternative to GPS.

0072A few more functions should be discussed before turning to how location guesses are made. Specifically, removing the assumption in the prior fit_function example that the signal_snapshot was known, and also providing some additional exemplary sensor fit functions used by some embodiments:

0000<tables id="TABLE-US-00005" num="00005"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def fit_function(path_history,</entry></row><row><entry /><entry>raw_log_file):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>signal_snapshot =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>new_empty_signal_snapshot( )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>total_fit = 1.0</entry></row><row><entry /><entry>for each u in path_history:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>total_fit *= fit_function</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>accelerometer(u, raw_log_file)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>total_fit *= fit_function_wifi(u,</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_log_file, signal_snapshot)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>signal_snapshot.append(u,</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_log_file)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>return total_fit</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0073Concepts from Bayesian filters are used to determine the contents of the signal_snapshot. Specifically, each grid (or cell) of the map only needs to store the mean and variance (or store sums and sums of squares for later division by the number of samples) for past WiFi observations at that location. This permits signal_snapshot.append( ) to just update the map with the latest observations:

0000<tables id="TABLE-US-00006" num="00006"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def signal_snapshot.append(u, raw_log_file):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_wifi_readings =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_log_file.get_wifi_readingds(u.t( ))</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>radio_map_cell =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>signal_snapshot.get_nearest_radio_map_cell(u.location( ))</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry># note in this embodiment path_history</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>is 0.05 seconds apart, but wifi scans only occur every 1.5</entry></row><row><entry /><entry>seconds</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>if there exists wifi scan between u.t( )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>and prior guess:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry># add this new scan, note could</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>store a list of readings instead</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>for each mac_address:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>radio_map_cell[mac_address].sum1 +=</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_wifi_readings[mac_address] ** 1</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>radio_map_cell[mac_address].sum2 +=</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_wifi_readings[mac_address] ** 2</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>radio_map_cell[mac_address].N</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>+= 1</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0074So the mean and variance as well as number of observations of the signal strength of each mac_address stored by the system for the given location. In one embodiment, the append function is modified to maintain the sums in two units: volts and dBm. Volts are useful for location computations in areas with multipath fading, while dBm are useful for location computations with shadow fading. Some embodiments may use more complex adjustments to neighboring snapshot grid cells. For example, each scan could contribute a fraction of the observation to neighbors with bilinear weighting and fractional values for N.

0075Some additional fit functions will now be discussed that could be added to the main fit_function depending on the sensors available.

0076Gain factor measures antenna gain, e.g. of the WiFi or cellular antenna. Gain can vary strongly based on how many people are in the room, how you hold the mobile device and the like. One embodiment sets a maximum gain factor, e.g. 0.02 dB as a flat cutoff, e.g. if abs(p.gain( )−u.gain( ) then a fit of 0 is returned and if it is within the cutoff a 1 is returned. Thus, new guesses should show relatively slow gain. Other return values for a fit_function_gain_factor could be Gaussian(p.gain( )−u.gain( ), sigma=0.003) which provides a smoother score.

0077Many mobile devices include a compass or other composite heading estimator that can provide a heading. We can use this sensor to favor guesses of locations that indicate movement in a continued direction:

0000<tables id="TABLE-US-00007" num="00007"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def fit_function_heading(u, raw_log_file):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>guessed_heading = (p.heading( ) +</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>u.heading( ))/2.0</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>t_midpoint = (p.t( )+u.t( ))/2.0</entry></row><row><entry /><entry>measured_heading =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_log_file.get_heading_reading(t_midpoint)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>return</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>Gaussian(angle_between(guessed_heading, measured_heading)</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0078In the heading estimation alternatives used by some embodiments to the Gaussian include rectangular or triangular kernels. The gyroscope of a mobile device can be similarly used (where q=the path history entry prior to p):

0000<tables id="TABLE-US-00008" num="00008"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def fit_function_gyroscope(u, raw_log_file):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>initial_heading = direction vector from</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>q.location( ) to p.location( )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>final_heading = direction vector from</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>p.location to u.location( )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>timespan = u.t( ) − q.t( )</entry></row><row><entry /><entry>guessed_rotation = angle between</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>initial/final headings</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>measured_rotation =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>row_log_file.get_gyroscope_readings(q.t( ), u.t( ))</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>return Gaussian(guessed_rotation −</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>measured_rotation, sigma_squared = timespan)</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0079Some embodiments of the gyroscope may employ a guessed bias to the gyroscope to allow the search function (to be described infra) to search for the optimal value. A similar approach together with a guessed bias could similarly be applied to compass data.

0080The magnetometer (different from the compass), which can be sensitive to indoor features, can also be especially useful without a gyroscope. The magnetometer may also be a particularly good movement/at rest discriminator function. The following is one embodiment; other embodiments are implemented more similarly to the gyroscope function:

0000<tables id="TABLE-US-00009" num="00009"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="196pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def fit_function_magnetometer(u,</entry></row><row><entry /><entry>raw_log_file):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="35pt" align="left" /><colspec colname="1" colwidth="182pt" align="left" /><tbody valign="top"><row><entry /><entry>rotation = angle between p.heading( )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="196pt" align="left" /><tbody valign="top"><row><entry /><entry>and u.heading( )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="35pt" align="left" /><colspec colname="1" colwidth="182pt" align="left" /><tbody valign="top"><row><entry /><entry>magnetometer_readings =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="196pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_log_file.get_mag_readings(p.t( ), u.t( ))</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="49pt" align="left" /><colspec colname="1" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>if magnetometer_readings</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="196pt" align="left" /><tbody valign="top"><row><entry /><entry>steady/unchanging:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><tbody valign="top"><row><entry /><entry>return</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="196pt" align="left" /><tbody valign="top"><row><entry /><entry>StandardGaussian(rotation, sigma_squared=0.001 radians)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="49pt" align="left" /><colspec colname="1" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>else</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><tbody valign="top"><row><entry /><entry>return 1.0</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0081Conceptually, in the steady state if you are not turning, the “fit” is best if you are moving straight. If it is changing, you could be walking, rotating the phone or the like, so a fit of 1 is returned to leave the rotation unconstrained. Note however, that phone movements can be de-correlated from body movements. For example, the user can rotate their phone without moving their body.

0082GPS fit functions can be Gaussian (gps_location at u.t( ), gps_confidence_interval at u.t( )). Other time-ranging signals such as infrared, time-difference-of-arrival estimates from advanced WiFi systems, and time-of-flight measurement systems could be incorporated similarly.

0083Occupancy, meaning whether a space is walkable or not, can be particularly useful. In some embodiments, occupancy information is exchanged implicitly via the signal_snapshot. Specifically, each grid of the signal_snapshot could be ascribed an occupancy value from 0 to 100%, starting at 50%. As log data is collected, the signal snapshot begins to reflect which areas are walkable vs. not and the occupancy value could be adjusted. In a similar fashion, old paths identify dead space as well. In one embodiment, occupancy maps can be generated from old paths computed using raw_log_files for a location. The occupancy maps can be downloaded at step <b>320</b>. In still other embodiments, foot traffic maps can be maintained identifying more commonly walked areas in a similar fashion.

0084Bluetooth and other short distance wireless technologies such as NFC/RFID, Zigbee, cross-phone WiFi detection can be used in the following basic approach (also, the shown Bluetooth process uses additional communication with the location system <b>120</b>, or directly between mobile devices on a peer-to-peer basis for the computation):

0000<tables id="TABLE-US-00010" num="00010"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def fit_function_bluetooth(u1, u2,</entry></row><row><entry /><entry>raw_log_file1, raw_log_file2):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>visible_bluetooth_devices1 =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_logfile1.get_bluetooth_detects(u1.t( ))</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>visible_bluetooth_devices2 =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>raw_logfile1.get_bluetooth_detects(u2.t( ))</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>if user1 in user2's visible list and</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>user2 in user1's visible list then:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry># the users are close to each</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>other</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>return Gaussian(distance between</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>u1.location( ) and u2.location( ), sigma=3.5 meters)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>else:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>return 1.0 − Gaussian(distance</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>between u1.location( ) and u2.location( ), sigma=3.5 meters)</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0085Some embodiments use values other than 3.5 meters and/or the Bluetooth signal strength to estimate the distance between users.

0086The fit functions used at step <b>330</b> have been discussed, along with the process for creating signal snapshots of unregulated RF transmissions such as WiFi which can be used to evaluate the variety of sensors on a mobile device for use in location determination. The next section will discuss the search approach for using the fit information to determine a user's location.

Search Functions

0087The search process is focused on finding the best-fitting path_history given the selected fit function in linear time. The proposed approach ultimately uses sequential importance resampling. Because the fit function is designed for sequential computation, e.g. for a “guess” along a path_history, the total_fit is accumulated incrementally and in chronological order. This allows for a path_history to be iteratively generated by making one guess at a time in chronological order. Then, at each step, just the incremental fitness score needs to be compared and the top few selected. This results in a greedy search process:

0000<tables id="TABLE-US-00011" num="00011"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def search_simple(raw_log_file,</entry></row><row><entry /><entry>signal_snapshot):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>hypothesis[0...499] = all empty path</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>histories # make 500 empty path_histories</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>for t = earliest timestamp to last</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>timestamp in 0.05s increments</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>weights[0...499] = all 1.0 # 500 total</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>fit values</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>for i = 0 to 499:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>next_guess = make a guess for</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>timestamp t in a uniformly random fashion</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>hypothesis[i].append(next_guess)</entry></row><row><entry /><entry>w = run one iteration of</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>fit_function( ) to get incremental fitness</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>weights[i] *= w</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>resample hypothesis by weights</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0088Improvements in this approach, thus, will come from choosing proposal distributions for the random guesses. One approach is to focus on areas of higher likelihood as opposed to completely random locations, so the code above in the inner loop could become next_guess=sample from Gaussian (hypothesis[i].prev_guess.location( ), sigma=5 m) and weights[i]*=w/Prob_sample(next_guess).

0089In other instances you can avoid computing the fit function of a sensor (e.g., accelerometer), by sampling from an equivalent distribution. For example, using the accelerometer, if at_rest==true, then given the prior fit function, it would match a Gaussian (distance, sigma_squared=0.01). Rather than sample a guess and then evaluate the fit, the next guess can be directly selected from the distribution, Gaussian (distance, sigma_squared=0.01). One way to implement this is to generate a random Gaussian distance according to sigma_squared=0.01, and set your next guess to be that distance from prev_guess. When sampling from the distribution equivalent to your fit function, additional simplifications can be made because w==Prob_sample(next guess); thus eliminating the need to update weights[i]*=w/Prob_sample(next_guess).

0090The simple_search( ) is deceptively simple; it allows step <b>330</b> to quickly test several hundred (intelligent) guesses at a time to generate a path_history iteratively from the raw_log_files and signal_snapshot and then display the current location to the user at step <b>340</b>. The number of test hypotheses, 500, was selected based on processing power in today's mobile devices to balance computation time, power usage, accuracy, and responsiveness. The specific number of hypotheses to test on future devices may be greater or fewer. For example, greater computational power in future devices may permit more complex analysis of fewer guesses while providing better results. Similarly, the chosen sampling intervals of 0.05 seconds to update the path and 1.5 seconds to scan for updated WiFi (or other unregulated RF transmissions/transmitters) are grounded in the same tradeoffs and could likewise be adjusted.

Further Improving Signal Maps

0091Further optimizations and improvements to the signal snapshot are possible and are used according to some embodiments. First, consider the handling of limited observation data, e.g. first visit to location <b>220</b> of <figref idref="DRAWINGS">FIG. 2</figref> and there is minimal data in the signal_snapshot. In this situation, as the user begins walking down the actual path <b>250</b>, the signal_snapshot will begin accumulating data, but many grid cells are empty and N==0.

0092One approach is to compute estimated means and estimated variances for empty cells. This is done as follows in one embodiment. First, a global_prior is computed (or obtained, e.g. from the location system <b>120</b>). The global prior can be computed as the global mean and variance of all dBm values in all raw_log_files available. The radio_map_cell [mac_address ] parameters for empty cells can be initialized to this global_prior. The selection of which log files to use is implementation-specific; some embodiments use all available log files, while other embodiments may use a subset of available log files, e.g. filtered for that user, that mobile device, that general location. Instead of the global_prior, actual observations from one cell can be used in neighboring cells as data becomes available. Adjusting the mean and variance for those cells is a type of interpolation based on nearby neighbors. One embodiment limits the propagation of observations to a maximum distance, e.g. 5 meters. Also, some embodiments make use of a counterintuitive decay function denominated in units of 1/volts as opposed to a linear decay in dBm. Other sufficient statistical methods could be used, e.g. medians, square root of the means squared.

0093The reason for the choice of units is an assumption that locally, signal strengths obey the log-distance path loss model. Interpolation is then an averaging function in units of Watts** (−1.0/γ), where γ is the wireless path loss exponent. For areas with free space in the vicinity, γ=2.0 can be used. If the signal_snapshot is maintained in units of volts, then converting the mean and variance to 1/volts for computation, and then back is simple.

0094Additionally, some embodiments assign an a-value to each cell in the signal_snapshot. The a-value for observed cells is 1.0 and the α-value for “empty” cells more than 3 cells away from the nearest observation is 0.0. Cells near an observed cell have an α-value that is higher for cells closer to observation. A cell with an α-value of 0.7 would take on its interpolated signal strength with only 70% weight. The remaining weight could be selected from the set of a uniform prior, the global_prior, a generic distribution, a heuristic based on the distance from the access point, a heuristic based on the log-distance path loss model. The fall off of a based on distance from observation can be implemented as a window function, e.g. quadratic window (Epanechnikov), triangular window, constant/rectangular window.

0095In the discussion thus far, the cell shape in the signal_snapshot has been assumed to be a uniform grid of squares. However, other cell shapes are used by other embodiments including: log-polar cells, centered around where the signal strengths are strongest; log-polar cells, centered around where the signal strengths have the largest gradients; square cells, but unequally sized. For example, to implement uneven square cells some embodiments start with a single-cell grid that is divided into smaller cells as sufficient WiFi observations are received, e.g. ensure every cell has at least N observations.

Further Improving Future Searches

0096We have now discussed the fit functions, search strategy, and signal map improvements used by some embodiments. Another technique used by some embodiments is to optimize and search across a larger collection of log files to build better snapshots. In discussing <figref idref="DRAWINGS">FIG. 3</figref>, we covered the optional steps (step <b>320</b> and step <b>360</b>) where data is transferred from the mobile device to the location system <b>120</b> and back.

0097As noted, one of the transfers down to the mobile device <b>131</b> could be a signal_snapshot and one of the transfers up to the location system <b>120</b> could be a raw_log_file. One optimization technique will be discussed in conjunction with <figref idref="DRAWINGS">FIG. 4</figref>, which is a diagram for refinement of the location determination process according to one embodiment. Additionally, <figref idref="DRAWINGS">FIG. 4</figref> will be described in the context of a client-server type usage with processing from multiple devices occurring on the server, e.g. location system <b>120</b>. In some embodiments, the process of <figref idref="DRAWINGS">FIG. 4</figref> is performed on the mobile device using multiple log files from that device and/or additional log files received from other mobile devices. In such an embodiment, the process of <figref idref="DRAWINGS">FIG. 4</figref> could be performed by the location software <b>159</b>.

0098Returning to the signal_snapshot data structure discussed supra, the append function was described according to an embodiment that permits easy crowdsourcing, self-healing (response to changes in the signal_snapshot), and real-time localization. Some embodiments may perform some or a portion of these functions on the location system <b>120</b> to reduce processing burden, network bandwidth, and response time on the mobile device. Additionally, in addition to providing for better location determinations for users, processing this information on the server can also provide a company analytics. Specifically, by aggregating raw_log_files from multiple visits (different users, different devices), a joint guess across a larger database of readings is possible. Specifically, if all raw_log_files are placed in chronological order; a fit_function is computed for each guess in chronological order; during the iterations of fit_function, the system continues to accumulate the signal_snapshot; and continues using the up-to-date accumulated signal_snapshot for future iterations. For implementation, some embodiments upload raw_log_files at step <b>360</b> and download signal_snapshots at step <b>320</b>.

0099<figref idref="DRAWINGS">FIG. 4</figref> includes a process <b>400</b> that starts at step <b>410</b> with collecting measurement streams, e.g. raw_log_files, from a location. For example, if multiple mobile devices (and their users) visit location <b>220</b>, then there might be many raw_log_files available. Some of those measurement streams may be from a single user/mobile device. For example, in the grocery store example, if the user <b>210</b> is an employee, she/he may account for the bulk of the available measurement streams. Process <b>400</b> continues at step <b>420</b> with analysis of the measurement stream using the others, described in greater detail infra. In one embodiment, step <b>420</b> is accomplished through the application of stochastic coordinate ascent to the raw_log_files. This can be considered an application of self-guided machine learning. The result of step <b>420</b> is an updated signal_snapshot that is generated at step <b>430</b>.

0100Turning to the details of step <b>420</b>, a variation on the previously described simple_search( ) approach can be used to build a better signal_snapshot. At step <b>420</b>, the simple_search( ) described above can be run on each raw_data_log in chronological order. Other orders are possible, e.g. most recent runs first, longest-duration runs first, most reliable contributors (e.g. based on past history), runs with the most user interaction first, and the like.

0101At the end of this initialization, one path for each raw_log_file will have the highest weight for that run of simple_search( ) e.g. best_hypothesis_so_far [logfileID]. Then, iterative improvement of each “dimension” can occur. In this example, database refers to the collection of log files in use:

0000<tables id="TABLE-US-00012" num="00012"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="196pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>def optimize(best_hypothesis_so_far,</entry></row><row><entry /><entry>database):</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="49pt" align="left" /><colspec colname="1" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>for each i in dimensions:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="35pt" align="left" /><colspec colname="1" colwidth="182pt" align="left" /><tbody valign="top"><row><entry /><entry>signal_snapshot.append(best_hypothesis_so_far[1..</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="196pt" align="left" /><tbody valign="top"><row><entry /><entry>(i−1)])</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><tbody valign="top"><row><entry /><entry>best_hypothesis_so_far[i] =</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="196pt" align="left" /><tbody valign="top"><row><entry /><entry>search_simple(database[i], signal_snapshot)</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0102The order in which the loop is performed is implementation-specific, e.g. reverse/forward chronological order, random. As shown, all previously explored dimensions up to i are used to build the signal_snapshot for re-running the simple_search( ). While the code above appends signal snapshots 1 . . . i-1, more generally it could be all except i when performing coordinate ascent. Also note that if performed on a server, more complex computations and/or a greater search space, e.g. more than 500, could be used compared with when the simple_search( ) is performed on a mobile device.

0103Further improvements, including applying outlier rejection techniques, to the data. Groups of outliers that are self-consistent are likely different floors of a building and can be separated into a separate signal_snapshot and/or collection of log files as appropriate. This capability provides for improved handling of multi-story indoor environments in some embodiments. Stand alone outliers may include moved/removed transmitters which could be removed from the data and/or that entire log file could be removed from consideration. For example, if discrete changes in the WiFi environment have occurred the system would detect that after a certain point in time logs will be consistently lower likelihood and degenerate versus prior to that point in time.

0104Because WiFi environments are unregulated, or ad hoc, they tend to change regularly. For this reason, it may be desirable to dispose of old log files after a period of time, e.g. 3-6 months. In some embodiments, older log files in locations that have a larger quantity of newer log files are disposed of sooner than locations with fewer log files. Thus, for example, if location <b>220</b> of <figref idref="DRAWINGS">FIG. 2</figref> is a heavily visited grocery store with dozens of log files generated each day, the value of a three-plus month old file is lower than for a location where there is only one visit every few months where it may be useful to save the log files for a longer period.

Examples and Further Discussion

0105The processes of <figref idref="DRAWINGS">FIGS. 3-4</figref> that were described, supra, will be illustrated in the context of the example of scenario <b>200</b> of <figref idref="DRAWINGS">FIG. 2</figref> as well as <figref idref="DRAWINGS">FIGS. 5-6</figref> which show example results from embodiments of the location determination process in variation of scenario <b>200</b>. Specifically, <figref idref="DRAWINGS">FIG. 5</figref> shows scenario <b>500</b> which is the same as <figref idref="DRAWINGS">FIG. 2</figref> with the user <b>210</b>, mobile <b>131</b> and related elements removed and a computed path <b>510</b> shown. <figref idref="DRAWINGS">FIG. 6</figref> similarly shows scenario <b>600</b> which like <figref idref="DRAWINGS">FIG. 5</figref> omits elements of <figref idref="DRAWINGS">FIG. 2</figref> and shows an alternate computed path <b>610</b>. On <figref idref="DRAWINGS">FIGS. 5-6</figref> the computed paths have been annotated with c₀-to-c₇showing the computed location at the respective t₀-to-t₇.

0106In this discussion, the location <b>220</b> is a grocery store and the obstacles <b>222</b>-<b>228</b> are aisles and shelves of the store. In this discussion, the location system <b>120</b> has provided the mobile <b>131</b> a scale, or roughly-to-scale, map of the store, e.g. at step <b>320</b> of process <b>300</b>, e.g. from company info <b>112</b> or a public website, e.g. a crowd sourced map website. In discussing <figref idref="DRAWINGS">FIG. 5</figref>, we will assume that there was no signal snapshot available on the location system <b>120</b> and the mobile <b>131</b> and this is the first visit to the location <b>220</b>.

0107The mobile <b>131</b> will be creating and then updating a signal snapshot (e.g. signal_snapshot data structure) every 1.5 seconds and an accelerometer on the mobile <b>131</b> will be used. In this example, the mobile <b>131</b> can at step <b>330</b> initially start collecting measurements and may prompt the user based on GPS used to obtain the map at step <b>320</b> to touch where they are on the map (step <b>350</b>). In this specific example, some additional input will be required to orient the path. Without that additional input, the path will lack an orientation given that this is a first visit ever to this location and the signal_snapshot lacks location-specific information. The additional input could come from a sensor, e.g. compass heading, from a second user touch, e.g. facing or “I'm here now” a few seconds later. The location is shown as c₀for actual location to. Note initially the location displayed prior to receiving the input may have been elsewhere on the display (step <b>340</b>); however, that initial “unanchored” location is not shown in <figref idref="DRAWINGS">FIG. 5</figref>.

0108As the user walks along the path from t₀to t₁, the log file is maintained and a signal snapshot is constructed. The signal snapshot reflects the received WiFi transmissions from the wireless access points <b>232</b>-<b>238</b>. The deviations between the computed path <b>510</b> from c₀to c₁versus the actual path <b>250</b> reflect the guesses chosen that are the best fit for the log data. In scenario <b>500</b>, we have never visited this location so there is no occupancy data (e.g. the obstacles <b>222</b>-<b>228</b> are not reflected in a format usable by the process) and there is no pre-existing signal snapshot.

0109In contrast, <figref idref="DRAWINGS">FIG. 6</figref> with scenario <b>600</b> shows a computed path <b>610</b> (again with markers c₀-to-c₇), which is a much closer fit to the actual path. Scenario <b>600</b> reflects a scenario after more visits where processes such as process <b>400</b> of <figref idref="DRAWINGS">FIG. 4</figref> have been used to analyze log files and derive a more useful signal snapshot. In this example, five hundred customers with mobile devices (end points <b>130</b>) have visited location <b>220</b> with the location software <b>159</b> transmitting log files to the location system <b>120</b>. Process <b>400</b> was then used to construct a signal map that is more reflective of conditions based on multiple readings. That signal map can be used by mobile <b>131</b> in scenario <b>600</b> to more accurately determine a user's location. Additionally, in contrast to scenario <b>500</b> where the user input may have been necessary to locate c₀, in scenario <b>600</b>, the combination of visible WiFi MAC addresses and their signal strengths is likely sufficient for initial location determination.

0110Contrasting the two results, is useful. In scenario <b>500</b>, the computed path <b>510</b> shares many characteristics with the actual path <b>250</b> while in scenario <b>600</b>, computed path <b>610</b> much more closely track the actual path <b>250</b>. In scenario <b>500</b>, GPS and/or user input was helpful for initial location determination whereas it was unnecessary in scenario <b>600</b>. Other differences between the two scenarios may include greater reliance and/or weighting of non-WiFi fit functions in scenario <b>500</b> vs. scenario <b>600</b>. Specifically, in scenario <b>500</b> inertial sensors (e.g. accelerometer, compass, gyroscope, heading, and the like) may be particularly important until an adequate signal snapshot is constructed. Alternatively, in lieu of inertial sensors, an occupancy map and/or user input, e.g. “here I am”, can also be used to supplement the newly developing signal snapshot. Scenario <b>500</b> also highlights the fact that no preconditions were imposed on the location. No information was required about the locations of the wireless access points <b>232</b>-<b>238</b> and using a map in this example was a discussion and diagramming convenience only. Notably, even if only a single user is collecting data and doing it entirely offline, as the signal snapshot is refined by additional visits, both past and future location determination get better with time. Other embodiments that can improve a first visit/cold start to a location could include providing an intended walking path, e.g.

0111user draws their planned path through the store.

0112In scenario <b>600</b>, it may also be possible for the location system <b>120</b> to create an occupancy map based on prior visits and log files. For example, if across <b>500</b> paths through the store, nobody has ever walked where obstacle <b>222</b> is, then obstacle <b>222</b> could be blocked as occupied space/unwalkable for use as an input to fit functions on mobile devices.

0113Locations with more detailed histories may also allow for changes to sampling rates. For example, if an environment has tens-of-thousands of visits regularly, it may be possible to reduce sampling frequencies on the mobile devices to conserve power while maintaining accuracy. Even in heavily visited locations, some parts of the location may be less-frequently visited than others. So selectivity can be applied to data retention, e.g. ensure that less trafficked portions of a location have longer streams of data than more heavily visited areas.

Conclusion and Additional Embodiments

0114We have now described a system and processes that provide improved mobile location determination.

0115Some additional embodiments and features include: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0116">When shopping/travelling in groups, being able to see and share the real-time and/or historical location of the other members of your party or your friends.</li><li id="ul0002-0002" num="0117">When taking or viewing photographs, being able to geo-tag photos and visually browse photos projected into a 2-d floor plan or 3-d environment interactively, with high, 1-3m accuracy.</li><li id="ul0002-0003" num="0118">Interactive games and augmented reality, e.g. <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0119">audio and/or video cues and/or in-game events can be automatically dispatched to users based on location coupled with the context of the application</li><li id="ul0003-0002" num="0120">automatic check-ins whenever a user enters a particular point of interest</li><li id="ul0003-0003" num="0121">rewards, leaderboards, or other incentives for capturing raw log files in locations that have not yet been added to location system (e.g. location system <b>120</b>) and/or storage (e.g. storage <b>122</b>).</li></ul></li><li id="ul0002-0004" num="0122">In malls, hospitals, airports and other similar spaces: <ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0123">finding a route to a specific store, a restroom, gate, connecting flight, reception area, or other point of interest</li><li id="ul0004-0002" num="0124">location-based search or real-time interactions with shops including line finding to identify shorter lines for checkout, ticket windows, check-ins, security screening</li><li id="ul0004-0003" num="0125">facilities and building operators can use pedestrian location data analytics, this can facilitate measuring the efficiency of signage and printed maps for demand planning including tenant rent optimization or to measure the efficiency of physical advertising space and digital signage based on traffic patterns</li><li id="ul0004-0004" num="0126">publication of targeted alerts, offers, or messages to only those patrons in a certain general location</li><li id="ul0004-0005" num="0127">leaving messages, offers, alerts at a location so that the message is only triggered when someone walks by that location (for the first time, always, etc.). Along with location, the triggers can also be combined with time of day, other people's locations, and/or other application context to determine when to display the information.</li></ul></li><li id="ul0002-0005" num="0128">Some additional features that may be present in museum embodiments include: <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0129">interactive audio/video tours based on real-time or historical location that customize their content based on what path you take through the exhibits and/or interactively guide you to related exhibits</li><li id="ul0005-0002" num="0130">location-based statistics, either real-time or historical analytics: e.g. “people in your demographic spend the most time at this exhibit”, “this exhibit is the most popular this hour”, “that exhibit has the shortest wait times right now”</li><li id="ul0005-0003" num="0131">“call for assistance feature” alert the nearest staff member of your location</li></ul></li><li id="ul0002-0006" num="0132">Some additional features that may be present in hospital embodiments include: <ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0133">track the location in real-time of your friends, loved ones, or other members of your party; broadcast your location to nearby staff members; search, navigation and contextual interactions for patients and visitors</li><li id="ul0006-0002" num="0134">location-based coordination tools for doctors, nurses, and other staff members</li><li id="ul0006-0003" num="0135">integration with itineraries and schedules</li><li id="ul0006-0004" num="0136">location monitoring for patient care</li></ul></li><li id="ul0002-0007" num="0137">Some additional features that may be present in office and campus embodiments include: <ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0138">real-time indicators of which shared rooms, e.g. conference or study rooms, are in-use vs. not; turn-by-turn navigation to the nearest shared room that is available; historical and/or real-time analytics about shared rooms usage, e.g. most vs. least and times of day</li><li id="ul0007-0002" num="0139">broadcast, receive, and share real-time location of participants during meeting times if at least one member is not yet present.</li><li id="ul0007-0003" num="0140">interactive reporting, e.g. “The light bulb in this room is broken”</li></ul></li><li id="ul0002-0008" num="0141">Some additional features that may be present in location analytics embodiments: <ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0142">case studies and user research: play back an anonymous user's path through a store to learn about the nuances of their visit</li><li id="ul0008-0002" num="0143">aggregate marketing optimization: translate mobile location and/or interaction events into web events, or their equivalents, for analysis in existing analytics engines, e.g., Coremetrics or Google Analytics.</li></ul></li><li id="ul0002-0009" num="0144">Some additional features that may be present in ground team coordination embodiments include: <ul id="ul0009" list-style="none"><li id="ul0009-0001" num="0145">real-time coordination for security teams, emergency response teams, cleaning staff, ushers, tour guides, and other ground teams</li><li id="ul0009-0002" num="0146">context-based assistance, e.g. “the fuse box for this room is there”.</li></ul></li><li id="ul0002-0010" num="0147">Additionally, some embodiments focused on location tracking may include: <ul id="ul0010" list-style="none"><li id="ul0010-0001" num="0148">tracking of personal items, pets, and infants</li><li id="ul0010-0002" num="0149">safety applications, including but not limited to E911 and AGPS enhancement</li><li id="ul0010-0003" num="0150">inventory and/or equipment tracking, e.g. warehouses, factories, hospitals</li></ul></li><li id="ul0002-0011" num="0151">Rather than provide a floor plan ahead of time, some embodiments may support automatic creation of estimated floor plans either interactively or based on: <ul id="ul0011" list-style="none"><li id="ul0011-0001" num="0152">walking/movement patterns, e.g. areas that are never walked are more likely to be walls, furniture, or other obstructions; areas that are frequently walked are more likely to be unobstructed open space in rooms or hallway</li><li id="ul0011-0002" num="0153">straight regions of sharper signal strength drops tend to be obstructions like walls and furniture</li><li id="ul0011-0003" num="0154">points of interest and other meaningful locations can be tagged manually, e.g. from timestamp, position, photographs</li></ul></li><li id="ul0002-0012" num="0155">Other embodiments may provide contextual, location driven information for stadiums, arenas, hotels, resorts, cruise ships, and/or casinos.</li><li id="ul0002-0013" num="0156">Some embodiments provide proximity based social applications including: <ul id="ul0012" list-style="none"><li id="ul0012-0001" num="0157">social networks that automatically form or remove connections—or adjust the strength of connection and/or group/circle—based on how often you spend time in close proximity</li><li id="ul0012-0002" num="0158">cross-person device pairing and communication based on proximity, e.g. providing a “bump app” without the need to bump or direct device-to-device communication</li><li id="ul0012-0003" num="0159">people-discovery based on interests coupled with where you spend your time, for example a social dating application could pair people who regularly visit the same park or a dine with someone application to pair groups up for dining at a conference</li></ul></li><li id="ul0002-0014" num="0160">Some embodiments may provide analytics for the individual, e.g. a “my places” and self-awareness tools. <ul id="ul0013" list-style="none"><li id="ul0013-0001" num="0161">This could include displaying a list of commonly frequented locations. Features can include an indicator displaying “in” or “out”, and time since last entry/exit, with “in” or “out” automatically determined from location context.</li><li id="ul0013-0002" num="0162">“Learn about me” features can include using a personal mobile device as a data collection utility. Since the device can be active and close to your person most of the time, it can log information about you. <ul id="ul0014" list-style="none"><li id="ul0014-0001" num="0163">Signal snapshots and logs can be recorded and compared to determine when new locations are entered and when old locations are revisited.</li><li id="ul0014-0002" num="0164">New signal snapshots can be tagged, e.g. “Meeting room A”.</li><li id="ul0014-0003" num="0165">The data can be analyzed to provide analytics including: time spent at a location “today”, total time ever spent at a location, number of steps taken in old/new/all locations, number of calories burned, other people who have spent time at this location, how often “meeting room A” is used by you; a qualitative rating of adventurousness</li></ul></li></ul></li><li id="ul0002-0015" num="0166">Some embodiments may provide assistive technology for users, e.g. blind, including: <ul id="ul0015" list-style="none"><li id="ul0015-0001" num="0167">providing audio cues, directions, and information based on the context of the application, your precise location, and/or which direction you are heading. This can serve to provide specific navigation or as a general guide</li><li id="ul0015-0002" num="0168">logging and/or tagging of previously visited locations before with alerts when you return to those locations, approach them, or leave them.</li></ul></li><li id="ul0002-0016" num="0169">Some embodiments focus on monitoring and liability including: <ul id="ul0016" list-style="none"><li id="ul0016-0001" num="0170">slip and falls: location tracking to verify whether an employee had already attended to the dangerous area prior to the accident occurring</li><li id="ul0016-0002" num="0171">security services: location tracking to verify when a security guard most recently surveyed the site of an incident.</li></ul></li><li id="ul0002-0017" num="0172">Some embodiments provide contextual remote controls based on location including: <ul id="ul0017" list-style="none"><li id="ul0017-0001" num="0173">personalized remote control interface based on whether you are in the TV room, the den, or the kitchen with that customized and/or dynamic buttons and behaviors</li><li id="ul0017-0002" num="0174">control of other devices (e.g., unlock car doors, stream music from your stereo) that respond to your proximity to the device</li><li id="ul0017-0003" num="0175">alarms, reminders, and phone settings (e.g. vibrate vs. silent) based on what type of room you are in, e.g. living room vs. bedroom, classroom vs. library, and the application context</li></ul></li><li id="ul0002-0018" num="0176">Some embodiments may provide for direct interaction and visualization of signal strengths and/or locations of transmitters and/or receivers including: <ul id="ul0018" list-style="none"><li id="ul0018-0001" num="0177">monitoring wireless coverage and performance, identify dead zones, etc.</li><li id="ul0018-0002" num="0178">locating transmitters and/or receivers</li><li id="ul0018-0003" num="0179">recommending locations to add a new access points</li></ul></li><li id="ul0002-0019" num="0180">Some embodiments can serve as a GPS substitute for pedestrian or vehicular positioning and/or navigation in areas where GPS services are poor, e.g. urban canyons.</li><li id="ul0002-0020" num="0181">Some embodiments include applications for importing, exporting, viewing, modifying, and/or analyzing all or parts of the generated path histories with respect to their raw log files, fit functions, sampling functions, and the resulting signal snapshots after they have been captured and determined. Such embodiments can include: <ul id="ul0019" list-style="none"><li id="ul0019-0001" num="0182">regenerating signal snapshots and/or path histories in real-time and/or interactively if log files, constraints, or data points are changed/added/removed</li><li id="ul0019-0002" num="0183">aligning, analyzing, or displaying floor plans or company information against the location data automatically or interactively</li><li id="ul0019-0003" num="0184">visualization of the fit functions and/or sampling functions in the context of a particular dataset</li></ul></li><li id="ul0002-0021" num="0185">The improved mobile location systems described herein can provide a seamless and/or holistic location experience by launching other mobile applications, intents, and/or behaviors as a user enters or leaves locations</li><li id="ul0002-0022" num="0186">In some embodiments, the approaches described herein are “flipped” around and performed from the server side. Thus, location determination occurs on the server using signal information from the transmitters and/or receivers coupled in communication with the server as opposed to measurements made on the mobile device itself.</li><li id="ul0002-0023" num="0187">In some embodiments, the determined location is represented as: <ul id="ul0020" list-style="none"><li id="ul0020-0001" num="0188">a probabilistic or heuristic area/region denoting, e.g. a confidence interval</li><li id="ul0020-0002" num="0189">qualitative descriptions such as the nearest point of interest or logical location (e.g. “just outside meeting room A”, or “beside person B”)</li><li id="ul0020-0003" num="0190">graphically, for example probabilistic indicators that are darker in areas of higher probability and lighter in areas of less probability rather than just as coordinates (e.g. x, y or latitude, longitude)</li></ul></li><li id="ul0002-0024" num="0191">In some embodiments, robots with motion capabilities are used to capture data. And the raw log file can include inputs from the robots' sensors. Applications include: <ul id="ul0021" list-style="none"><li id="ul0021-0001" num="0192">interactive guidance and/or fully autonomous robot navigation, e.g. tele-presence robots travelling between locations, e.g. conference rooms, cubicles</li><li id="ul0021-0002" num="0193">autonomous and/or low-manpower determination of signal snapshots and/or location information for an arbitrary indoor or outdoor location</li><li id="ul0021-0003" num="0194">route planning to maintain network connectivity while intelligently handing off network access over, e.g. a sequence of wireless access points</li><li id="ul0021-0004" num="0195">disposable devices or robotics designed to rapidly survey the signal snapshot for a given location by being transported or propelled, possibly in bulk, across the desired indoor or outdoor space while capturing raw log files and either processing them or uploading/transferring them to an external server for post-processing.</li></ul></li><li id="ul0002-0025" num="0196">The improved mobile location systems described herein, where instead of a discrete software application, all or part of the location determination processes described herein are performed by: <ul id="ul0022" list-style="none"><li id="ul0022-0001" num="0197">operating system kernel, driver, and/or software</li><li id="ul0022-0002" num="0198">vendor-level systems, firmware, software</li><li id="ul0022-0003" num="0199">chip-level systems, hardware implementations</li><li id="ul0022-0004" num="0200">third-party applications that access the location determination via a library, SDK, or API</li></ul></li><li id="ul0002-0026" num="0201">In some embodiments, the process for location determination takes into account changes in the receiving environment including but not limited to: time of day, number of obstacles, number of users, pedestrian traffic, make and model and/or calibration parameters of the wireless signal receivers and/or transmitters.</li><li id="ul0002-0027" num="0202">The improved mobile location systems described herein can in some embodiments: <ul id="ul0023" list-style="none"><li id="ul0023-0001" num="0203">solve jointly and/or simultaneously more than one floor and/or building at once</li><li id="ul0023-0002" num="0204">incorporate and/or solve coarse-location and/or approximations to the user's location to distinguish between floors and buildings as fit functions and/or sampling functions</li><li id="ul0023-0003" num="0205">identify discrete differences in MAC addresses, user interaction, availability of GPS and other traditional signal sources, and/or application context combined with this location system as fit functions and/or sampling functions. For example, spatial indexing (e.g. k-means clustering, quad-tree, oct-tree, or kd-tree data structures, discretization and bucketing, etc.) of MAC addresses by proximity to known buildings</li><li id="ul0023-0004" num="0206">seamlessly or interactively transition from indoors-to-outdoors using these features</li></ul></li><li id="ul0002-0028" num="0207">In some embodiments, the outlier rejection (either in the environment, dynamic or static changes to the environment, or of log files, or of data points within log files) described herein is based on: <ul id="ul0024" list-style="none"><li id="ul0024-0001" num="0208">consistency of the new data versus correlations with the outputs, for example, from past runs</li><li id="ul0024-0002" num="0209">relative self-consistency of a particular group/class of measurements</li><li id="ul0024-0003" num="0210">relative self-consistency of the given value versus other measurements in similar but different state space</li><li id="ul0024-0004" num="0211">determining if a data point is an outlier by comparing its own signal strength error of one access point to the signal strength of another access point from the same corresponding space-time measurement positions</li></ul></li><li id="ul0002-0029" num="0212">In some embodiments, walkable locations are represented as a spatial connectivity graph and an assumption can be made that user(s) are more likely to be on the graph or on a different floor/building. This can limit the search space needed to identify where new data is likely to be located. When a new measurement arrives, it can be compared against the database versus distinct nodes in the graph resulting in fewer comparisons than for a full search over the state space or otherwise. There is no minimum number of APs/transmitters required.</li></ul></li></ul>

0213Any data structures and code described or referenced above are stored according to many embodiments on a computer-readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, volatile memory, non-volatile memory, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs), DVDs (digital versatile discs or digital video discs), or other media capable of storing computer-readable media now known or later developed.

0214The preceding description is presented to enable the making and use of the invention. Various modifications to the disclosed embodiments will be apparent, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the invention. Thus, the invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein. The scope of the invention is defined by the appended claims.