Pathway matching

• US 9,226,111 B2
• Filed: 11/21/2012
• Issued: 12/29/2015
• Est. Priority Date: 11/21/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Marti, Lukas M., Ma, Shannon M.
• Primary Examiner(s): MAPA, MICHAEL Y
• Application Number:
  US13/683,474
• Publication Number:
  US 20140141796A1
• Time in Patent Office: 1,133 Days
• Field of Search: 455/404.2, 455/414.2, 4554561-457
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: G01S 5/0263 by combining or switching between positions derived from two or more separate positioning systems
• 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: G01S 5/0294 Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

Abstract

Methods, program products, and systems for estimating a location of a mobile device in a venue are provided. The venue can have pathways represented by a path network that includes segments connected by junctions. Estimating the location can include determining a first set of candidate locations for the mobile device, and mapping some of the candidate locations to updated candidate locations that are on or closer to one or more segments of the path network based on distances between the candidate locations and respective segments, resulting in a second set of candidate locations for the mobile device. The location of the mobile device can be derived from the second set of candidate locations.

Claims

1. A method comprising:

estimating a location of a mobile device in a venue having pathways represented by a path network that includes segments connected by junctions, the estimating including

determining a first set of candidate locations for the mobile device;

determining that distances between the candidate locations of a first subset of the first set and the corresponding segment or segments are less than a threshold distance;

shifting the candidate locations of the first subset to updated candidate locations that are on the corresponding segment or segments of the path network;

determining that distances between the candidate locations of a remaining second subset of the first set and corresponding segment or segments are larger than or equal to the threshold distance; and

shifting the candidate locations of the second subset to updated locations that are closer to, but not on, the corresponding segment or segments, wherein the shifting of the candidate locations of the first and second subsets results in a second set of candidate locations for the mobile device; and

deriving the location of the mobile device from the second set of candidate locations based on a sensor reading from a sensor of the mobile device that senses an environment variable.

2. The method of claim 1, comprising

propagating the second set of candidate locations based on the sensor reading and map data associated with the venue, resulting in a third set of candidate locations, in which the third set of candidate locations is not constrained to the path network for at least a portion of the path network;

and

estimating the location of the mobile device based on the third set of candidate locations.

3. The method of claim 2 in which the map data comprises information about constraints of movement of the mobile device in the venue, and the propagation of the second set of candidate locations takes into account the constraints of movement of the mobile device in the venue.

4. The method of claim 3 in which the constraints of movement of the mobile device comprise walls or obstacles in the venue that may block a pedestrian carrying the mobile device.

5. The method of claim 2 in which propagating the second set of candidate locations comprises using a state space estimator to explore possible candidate locations at a next time point given the second set of candidate locations at a previous time point.

6. The method of claim 5 in which the state space estimator takes into account directions of the segments when exploring the possible candidate locations at the next time point.

7. The method of claim 2 in which when propagating the second set of candidate locations to derive the third set of candidate locations, the third set of candidate locations is constrained to the path network for at least a portion of the path network.

8. The method of claim 1 in which shifting the candidate locations to updated candidate locations comprises for each of the candidate locations, identifying a segment having an orthogonal distance from the candidate location that is smallest among the segments in the path network, and shifting the candidate location to the corresponding updated candidate location that is on or closer to the segment.

9. The method of claim 1 in which the pathways represent routes in the venue that may be traveled by a pedestrian carrying the mobile device.

10. The method of claim 1, comprising determining that no constraint of movement of the mobile device is located between the candidate locations and the corresponding segment or segments prior to shifting the candidate locations to the updated candidate locations.

11. A method comprising:

estimating a location of a mobile device in a venue having pathways represented by a path network that includes segments connected by junctions, the estimating including;

determining a first set of candidate locations for the mobile device;

shifting some of the candidate locations to updated candidate locations that are on or closer to one or more segments of the path network based on distances between the candidate locations and respective segments, wherein the shifting of the candidate locations of the first set comprises determining a weight value based on a probability distribution that is a function of the distance between the first candidate locations and the corresponding segment, and determining a shift to a position of the updated candidate location based on the weight value, wherein the shifting of the candidate locations of the first set results in a second set of candidate locations for the mobile device; and

deriving the location of the mobile device from the second set of candidate locations based on a sensor reading from a sensor of the mobile device that senses an environment variable.

12. The method of claim 11 in which when a segment represents a path in a hallway, the probability distribution associated with the segment is dependent on a width of the hallway.

13. The method of claim 11 in which the probability distribution associated with the segment is dependent on a density of pathways in a vicinity of the segment.

14. A computer-implemented method of claim comprising:

identifying a path network representing pathways in a venue comprising a space accessible by a movable body carrying a mobile device and one or more constraints of movement of the movable body, the path network including segments that are connected by junctions;

determining an estimated location of a mobile device;

updating the estimated location to derive an updated estimated location, taking into account constraints imposed by the segments of the path network, wherein the updating of the estimated location comprises shifting the estimated location according to a weight value to the updated estimated candidate location that is on or closer to a segment of the path network according to a probability value associated with the segment;

propagating the updated estimated location of the mobile device using a state space model to generate a propagated estimated location, taking into account of a sensor reading from a sensor that senses an environment variable, and one or more constraints of movement of the movable body, but without being constrained to the segments of the path network; and

determining an updated estimated location of the mobile device based on the propagated estimated location.

15. The method of claim 14, comprising determining that no constraint of movement of the movable body is located between the estimated location and the segment prior to shifting the estimated location to the updated estimated location.

16. A mobile device comprising:

a sensor to sense an environment variable;

a storage configured to store map data associated with a venue comprising a space accessible by a movable body carrying the mobile device and one or more constraints of movement of the movable body, the map data including information about a path network representing pathways in the venue, the path network including segments connected by junctions; and

a processor configured to;

determine a first estimated location and a second estimated location of the movable body;

determine that a first distance between the first estimated location and a first segment in the path network is less than a threshold distance;

shift the first estimated location to a first updated estimation location that is on the first segment;

determine that a second distance between the second estimated location and the first segment is greater than or equal to the threshold distance;

shift the second estimated location to a second updated estimated location that is closer to, but not on, the first segment; and

determine a current location of the movable body based on the first updated estimated location, the second updated estimated location and a sensor reading from the sensor.

17. The mobile device of claim 16 in which the processor is configured to

perform determination that there is no constraint of movement of the movable body between each of the first and second estimated locations and the first segment;

and

perform, as a result of the determination, the shifting of the first estimated location to the first updated estimated location and the second estimated locations to the second updated estimated location.

18. A mobile device comprising:

a sensor to sense an environment variable;

a storage configured to store map data associated with a venue comprising a space accessible by a movable body carrying the mobile device and one or more constraints of movement of the movable body, the map data including information about a path network representing pathways in the venue, the path network including segments connected by junctions; and

a processor configured to determine a first set of candidate locations for the movable body;

shift the candidate locations according to a weight value to updated candidate locations that are on or closer to one or more segments of the path network based on distances between the candidate locations and respective segments, wherein the shift of the candidate locations of the first set results in a second set of candidate locations for the movable body;

mobile device, receive a sensor reading from the sensor;

propagate the second set of candidate locations based on the sensor reading and map data, resulting in a third set of candidate locations; and

estimate the location of the movable body based on the third set of candidate locations.

19. The mobile device of claim 18, wherein the processor is further configured to determine that no constraint of movement of the movable body is located between the candidate locations and the corresponding segment or segments prior to shifting the candidate locations to the updated candidate locations.

20. An apparatus comprising:

a non-transitory computer storage medium storing instructions that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising;

determine a first set of candidate locations for a mobile device in a venue having pathways represented by a path network that includes segments connected by junctions;

shifting some of the candidate locations to updated candidate locations that are on or closer to one or more segments of the path network based on distances between the candidate locations and respective segments, wherein the shifting of the candidate locations of the first set comprises;

determining a weight value based on a probability distribution that is a function of the distance between the first candidate locations and the corresponding segment, and determining a shift to a position of the updated candidate location based on the weight value, wherein the shifting of the candidate locations of the first set results resulting in a second set of candidate locations for the mobile device; and

estimating the location of the mobile device from the second set of candidate locations based on a sensor reading from a sensor of the mobile device that senses an environment variable.

21. The apparatus of claim 20, wherein

a segment represents a path in a hallway, and

the probability distribution associated with the segment is dependent on a width of the hallway.

22. The apparatus of claim 20, wherein the probability distribution associated with the segment is dependent on a density of pathways in a vicinity of the segment.