Determining User Device's Starting Location

• US 20140244163A1
• Filed: 02/28/2013
• Published: 08/28/2014
• Est. Priority Date: 02/28/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhao, Chunshui, Li, Fan, Zhao, Jun, Ding, Huan
• Granted Patent: US 8,990,011 B2
• Time in Patent Office: Days
• US Class Current: 701/445
• CPC Class Codes: G01C 21/1654 with electromagnetic compass
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/3889 Transmission of selected map data, e.g. depending on route
• CPC Class Codes: G01S 2205/02 Indoor
• CPC Class Codes: G01S 5/02529 not involving signal parameters, i.e. only involving identifiers
• CPC Class Codes: G01S 5/0264 at least one of the systems being a non-radio wave positioning system
• CPC Class Codes: G01S 5/0269 Inferred or constrained positioning, e.g. employing knowledge of the physical or electromagnetic environment, state of motion or other contextual information to infer or constrain a position
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A user device is equipped with one or more sensors that collect data relating to a movement of a user having the user device. An estimated area within which a starting location of the user device is located is determined based on one or more signals received from adjacent signal sources. A plurality of candidate locations is identified within the estimated area as the potential starting location of the user device. Map information of surrounding area that covers the estimated area is also obtained. One or more candidate locations are filtered out depending on whether they could have experienced the movement based on the map information. When one or more re-starting conditions have met during the movement, a then starting location of the user device needs to be determined.

Claims

1. A method comprising:

under control of one or more processors configured with computer-executable instructions;

estimating an area within which a starting location of a user device is located at a first time;

identifying a plurality of candidate locations within the estimated area, each candidate location representing a potential starting location of the user device at the first time;

receiving map information of a surrounding area of the user device, the surrounding area including the estimated area;

determining a movement of the user device starting from the first time; and

filtering out one or more of the candidate locations as potential starting locations of the user device at least partly based on the movement and the map information of the surrounding area.

2. The method as recited in claim 1, wherein the estimating the area comprises:

receiving by the user device one or more signals sent by one or more signal sources at the first time; and

calculating an estimated starting location of the user device at the first time at least partly based on the one or more received signals, the estimated area being based on the estimated starting location.

3. The method as recited in claim 2, wherein the estimated starting location is a central point of the estimated area.

4. The method as recited in claim 2, wherein the calculating the estimated starting location comprises:

calculating a starting signal location of the user device based on the received one or more signals;

determining whether the starting signal location is at an impossible location according to the map information;

if the calculated signal location of the user device is not at the impossible location, using the calculated starting signal location as the estimated starting location; and

if the calculated signal location of the user device is at the impossible location, identifying a location that is not the impossible location and is adjacent to the calculated signal location as the estimated starting location.

5. The method as recited in claim 4, wherein the impossible location includes:

a first location that has no space for the user device or the user to stay according to the map information;

or

a second location that a moving pattern between the estimated starting location and the second location is impossible for a human.

6. The method as recited in claim 4, wherein the calculating the starting signal location comprising using at least one of following models:

a fingerprint model or a radio propagation model.

7. The method as recited in claim 4, wherein the identifying the plurality of candidate locations within the estimated area comprises:

identifying the estimated starting location as a candidate location; and

randomly selecting multiple other candidate locations within the estimated area.

8. The method as recited in claim 7, further comprises excluding one or more of the plurality of candidate locations that are at one or more impossible locations that have no space for the user device to stay.

9. The method as recited in claim 1, wherein the determining the movement of user device comprises:

collecting by the user device sensor data relating to the movement of the user device; and

calculating the movement of the user device based on the received sensor data.

10. The method as recited in claim 1, wherein the filtering comprises:

determining whether, based on the map information, the user device could have experienced the movement from the one or more candidate locations; and

filtering out the one or more of the candidate locations as potential starting locations of the user device if, based on the map information, the user device could not have experienced the movement from the one or more candidate locations.

11. The method as recited in claim 10, wherein the determining that the user device could not have experienced the movement from the one or more candidate locations comprises determining that the movement from the one or more candidate locations would result in one or more impossible locations that have no space for the user device to stay based on the map information.

12. The method as recited in claim 10, wherein the determining that the user device could not have experienced the movement from the one or more candidate locations comprises:

detecting one or more steps of a user of the user device;

after a respective step of the user, calculating a confidence score of a respective candidate location at least partly based on the movement and the map information, the confidence score measuring a probability that the respective candidate location would end in an impossible location;

determining whether the confidence score is higher than a score threshold; and

if the confidence score is higher than the score threshold, filtering out the respective candidate location as the potential starting location of the user device.

13. The method as recited in claim 1, further comprising:

determining that all but a remaining candidate location have been filtered out; and

using the remaining candidate location as the starting location of the user device at the first time.

14. One or more computer storage media having stored thereupon a plurality of computer-executable instructions that, when executed by one or more processors, causes the one or more processors to perform actions comprising:

receiving signal data at a first time;

calculating an estimated starting location of a user device of a user at the first time at least partly based on the received signal data;

estimating an area within which a starting location of the user device of the user is located at the first time based on the estimated starting location;

identifying a plurality of candidate locations within the estimated area, each candidate location representing a potential starting location of the user device at the first time, the plurality of candidate locations including the estimated starting location;

receiving map information of a surrounding area of the user device, the surrounding area including the estimated area;

determining a movement of the user device starting from the first time; and

filtering out one or more of the candidate locations as potential starting locations of the user device at least partly based on the movement and the map information of the surrounding area.

15. The one or more computer storage media as recited in claim 14, wherein the actions further comprise:

determining whether a re-initialization conditions has been met such that a starting location of the user device at a second time needs to be determined during the movement, the re-initialization condition including;

the starting location of the user device at the first time fails to be determined;

a distance between the estimated starting location and an ending location of a respective unfiltered candidate location during the movement is longer than a preset threshold;

or

a distance between the determined starting location of the user device at the first time and a current location of the user device is longer than another preset threshold;

if the re-initialization condition has been met,

stopping determining the starting location of the user device at the first time;

recording the second time when the re-initialization condition has been met; and

determining the starting location of the user device at the second time.

16. The one or more computer storage media as recited in claim 15, wherein the determining the starting location of the user device at the second time comprises:

receiving signal data at the second time;

calculating an estimated starting location of the user device of the user at the second time at least partly based on the received signal data;

estimating an area at the second time, within which the starting location of the user device of the user is located at the second time, based on the estimated starting location at the second time;

identifying a plurality of candidate locations within the estimated area at the second time, each candidate location representing a potential starting location of the user device at the second time;

receiving map information of a surrounding area of the user device at the second time, the surrounding area at the second time including the estimated area at the second time;

determining a movement of the user device starting from the second time; and

filtering out one or more of the candidate locations as potential starting locations of the user device at the second time at least partly based on the movement starting from the second time and the map information of the surrounding area at the second time.

17. The one or more computer storage media as recited in claim 14, wherein the filtering comprises:

determining whether, based on the map information, the user device could have experienced the movement from the one or more candidate locations; and

filtering out the one or more of the candidate locations as potential starting locations of the user device if, based on the map information, the user device could not have experienced the movement from the one or more candidate locations.

18. A system comprising:

one or more processors;

one or more signal sensors that receive signal data from one or more signal sources;

one or more motion sensors that collect sensor data relating movement of a user device; and

one or more computer storage media having stored thereupon a plurality of computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to perform actions comprising;

calculating an estimated starting location of the user device at a first time at least partly based on received one or more signals at the first time, the calculating comprises;

estimating an area within which a starting location of the user device is located at the first time based on the estimated starting location;

identifying a plurality of candidate locations within the estimated area, each candidate location representing a potential starting location of the user device at the first time, the plurality of candidate locations including the estimated starting location;

receiving map information of a surrounding area of the user device, the surrounding area including the estimated area;

determining a movement of the user device based on the collected sensor data starting from the first time; and

filtering out one or more of the candidate locations as potential starting locations of the user device at least partly based on the movement and the map information of the surrounding area.

19. The system as recited in claim 18, wherein the actions further comprise:

determining whether a re-initialization condition has been met such that a starting location of the user device at a second time needs to be determined during the movement, the re-initialization condition including;

the starting location of the user device at the first time fails to be determined;

a distance between the estimated starting location and an ending location of a respective unfiltered candidate location during the movement is longer than a preset threshold;

or

a distance between the determined starting location of the user device at the first time and a current location of the user device is longer than another preset threshold;

if the re-initialization condition has been met,

stopping determining the starting location of the user device at the first time;

recording the second time when the at least one of re-initialization conditions has been met; and

determining the starting location of the user device at the second time.

20. The system as recited in claim 18, wherein the actions further comprises:

synchronizing data stream from the signal data and data stream from the sensor data.