Location determination techniques

• US 20070149216A1
• Filed: 12/05/2006
• Published: 06/28/2007
• Est. Priority Date: 12/07/2005
• Status: Active Grant

• Current Assignee: AiRISTA Flow, Inc. (AiRISTA, LLC), AiRISTA International Oy (AiRISTA, LLC)
• Original Assignee: Ekahau Oy
• Inventors: Misikangas, Pauli
• Granted Patent: US 7,904,097 B2
• Time in Patent Office: Days
• US Class Current: 455/456.100
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A method for estimating a target object properties, including location, in an environment. A topology model indicates permissible locations and transitions and a data model models a location-dependent physical quantity which is observed by the target object'"'"'s sensing device. Motion models model specific target object types, obeying the permissible locations and transitions. The target object is assigned a set of particles, each having a set of attributes, including location in relation to the topology model. The attributes estimate the target object properties The particles'"'"' update cycles include: determining a degree of belief for each particle to estimate the target object properties; determining a weight for each particle based on at least the determined degree of belief and generating new particles for update cycle n+1 in an evolutionary process.

Claims

1. A method for estimating a set of properties of a target object in an environment, wherein the set of properties comprises location;

the method comprising;

modelling the environment with a topology model and a data model, wherein the topology model indicates permissible locations and transitions within the environment, and the data model indicates at least one location-dependent physical quantity for each of several permissible locations indicated by the topology model;

modelling location changing characteristics of the target object with one or more motion models, wherein each motion model models a specific type of a target object and obeys permissible locations and transitions indicated by the topology model;

associating to the target object one or more co-located sensing devices, each of which is capable of making observations of one or more of the location-dependent physical quantities;

assigning to the target object a set of particles, each of which has a set of attributes, wherein the set of attributes comprises at least a location in relation to the topology model;

estimating the set of properties of the target object with the set of attributes of the particles assigned to the target object; and

updating the set of particles in a plurality of update cycles, wherein each update cycle comprises the following phases a) to c);

a) determining a degree of belief for each particle to accurately estimate the set of properties of the target object, using the data model and observations from at least one sensing device associated to the target object;

b) determining a weight for each particle based on at least the determined degree of belief; and

c) generating a set of new particles for update cycle n+1 wherein;

at least some of the new particles are based on one or more parent particles for update cycle n, wherein

the likelihood of a particle for update cycle n to be selected as a parent particle for a new particle in update cycle n+1 is a non-decreasing function of the weight of the particle; and

the set of attributes of a new particle for update cycle n+1 is derived from the set of attributes of one or more parent particles for update cycle n by using at least one of the one or more motion models and a predetermined algorithm.

2. A method according to claim 1, further comprising:

generating a snapshot of weighted particles for update cycle k, wherein the snapshot contains some or all particles for update cycle k, and assigning to each particle a weight defined by the following recursive rules, wherein n is the latest update cycle for which the weights have been determined;

if k equals n, the weight of a particle is based on the weight determined in step b of claim 1;

if k is less than n, the weight of a particle is based on the sum of weights of all direct descendants of the particle existing in a snapshot generated for update cycle k+1; and

using the snapshot to estimate the set of properties of the target object at the time of update cycle k.

3. A method according to claim 2, further comprising:

dividing the snapshot of weighted particles for update cycle k into one or more clusters, wherein each cluster contains particles that are similar to each other according to one or more predetermined similarity criteria; and

selecting at least one cluster and estimating the set of properties of the target object at the time of update cycle k for each selected cluster by using particles and weights in the selected cluster and omitting particles and weights not in the cluster.

4. A method according to claim 3, wherein at least one of the one or more predetermined similarity criteria is based on the particles'"'"' location whereby each cluster contains particles close to each other.

5. A method according to claim 3, further comprising:

maintaining a plurality of predetermined zones, wherein each zone includes one or more permissible locations of the topology model; and

wherein

at least one of the one or more predetermined similarity criteria is based on the plurality of zones, wherein particles whose locations belong to the same zone belong to the same cluster.

6. A method according to claim 3, further comprising associating a confidence value to an estimate generated using a cluster, wherein the confidence value is based on the sum of weights of particles in the cluster divided by the total sum of weights in the snapshot.

7. A method according to claim 3, wherein the estimated set of properties of the target object includes at least one spatial property in the environment, the method further comprising:

modelling the at least one spatial property with the data model, wherein the data model indicates the spatial property for each of several locations within the environment;

wherein the step of estimating the set of properties of the target object comprises;

generating particle-specific estimates of the spatial property for each particle, using the data model to indicate the spatial property at the location of the particle; and

combining particle-specific estimates using the weights of the particles.

8. A method according to claim 1, wherein the data model is or comprises a probabilistic model which indicates a probability distribution for the at least one location-dependent physical quantity at the permissible locations indicated by the topology model;

and

wherein the step of determining a degree of belief for a particle comprises;

indicating a probability distribution for a location-dependent physical quantity at the location of the particle by using the data model; and

using the indicated probability distribution to determine the probability of an observation of the physical quantity from at least one sensing device associated to the target object.

9. A method according to claim 8, wherein the data model is or comprises a probabilistic model which indicates a probability distribution for the at least one location-dependent physical quantity at several sample points;

and wherein the step of indicating a probability distribution comprises;

selecting at least two sample points near the location of the particle; and

combining the probability distributions for the physical quantity at the selected sample points.

10. A method according to claim 9, wherein the step of combining the probability distributions comprises:

forming a cumulative distribution function for each selected sample point and weighting each of the cumulative distribution functions with a relative weight; and

forming a combination of the weighted cumulative distribution functions.

11. A method according to claim 1, wherein the topology model comprises nodes and arcs between the nodes to indicate the permissible locations and transitions.

12. A method according to claim 9, wherein the topology model comprises nodes and arcs between the nodes to indicate the permissible locations and transitions;

and wherein the step of selecting at least two sample points comprises selecting at least two of the sample points that can be reached from the location of the particle by following the arcs.

13. A method according to claim 1, further comprising selecting the motion model for a target object adaptively, wherein the adaptive selection comprises:

selecting a specific motion model for each particle and setting the attribute set of a particle to contain a reference to the motion model selected for the particle; and

the step of deriving the set of attributes of a new particle from the set of attributes of one or more parent particles comprises using the motion models referred by the attribute sets of the parent particles.

14. A method according to claim 1, further comprising:

maintaining a plurality of device models each of which is capable of correcting observations of one or more sensing devices;

selecting a specific device model for at least one of the co-located sensing devices;

correcting the observations of the at least one of the co-located sensing devices with the selected device model.

15. A method according to claim 14, further comprising selecting the at least one device model adaptively, wherein the adaptive selecting comprises:

selecting at least one specific device model for each particle and setting the attribute set of a particle to contain a reference to each device model selected for the particle; and

applying each device model referred to by the attribute set of the particle to correct observations from the at least one sensing device before the step of determining a degree of belief for the particle.

16. A method according to claim 1, wherein the data model indicates a set of expected values of the location-dependent physical quantities for each of a plurality of sample points and the method further comprises:

maintaining a set of relevance indicators for indicating one or more sets of relevant sample points wherein the one or more sets of relevant sample points are subsets of the sample points in the data model;

based on the observations of the one or more of the location-dependent physical quantities and on the set of relevance indicators, determining a current set of relevant sample points; and

using the current set of relevant sample points to increase computational efficiency.

17. A method according to claim 16, further comprising discarding particles located far from the current set of relevant sample points.

18. A method according to claim 16, wherein the step a) of claim 1 further comprises assigning a minimal degree of belief to particles far from the current set of relevant sample points without further calculations.

19. A method according to claim 16, wherein the step c) of claim 1 further comprises generating some additional parentless particles near the relevant sample points.

20. A method according to claim 1, wherein the one or more physical quantities comprise at least one signal value.

21. A method according to claim 1, wherein the set of properties comprises one or more motional properties.

25. A computer program product for a data processor, comprising program code means for carrying out the method of claim 1 when the computer program product is executed in the data processor.

22. A property-estimation apparatus for estimating a set of properties of a target object in an environment, wherein the set of properties comprises location, the property-estimation apparatus comprising:

a topology model for indicating permissible locations and transitions within the environment and a data model for indicating at least one location-dependent physical quantity for each of several permissible locations indicated by the topology model;

one or more motion models for modelling location changing characteristics of the target object, wherein each motion model models a specific type of a target object and obeys permissible locations and transitions indicated by the topology model;

an association of one or more co-located sensing devices to the target object, wherein each sensing device is capable of making observations of one or more of the location-dependent physical quantities;

means for assigning to the target object a set of particles, each of which has a set of attributes, wherein the set of attributes comprises at least a location in relation to the topology model;

a property estimator for estimating the set of properties of the target object with the set of attributes of the particles assigned to the target object; and

update means for updating the set of particles in a plurality of update cycles, wherein each update cycle comprises the following phases a) to c);

a) a determination of a degree of belief for each particle to accurately estimate the set of properties of the target object, using the data model and observations from at least one sensing device associated to the target object;

b) a determination of a weight for each particle based on at least the determined degree of belief; and

c) a generation of a set of new particles for update cycle n+1 wherein;

at least some of the new particles are based on one or more parent particles for update cycle n, wherein

the likelihood of a particle for update cycle n to be selected as a parent particle for a new particle in update cycle n+1 is a non-decreasing function of the weight of the particle; and

the set of attributes of a new particle for update cycle n+1 is derived from the set of attributes of one or more parent particles for update cycle n by using at least one of the one or more motion models and a predetermined algorithm.

23. A property-estimation apparatus according to 22, further comprising means for dynamically adjusting the number of particles assigned to a target object based on one or more of the following:

a variance in the attributes of particles;

the number of target objects served by the property-estimation apparatus;

quality requirements for the property estimate;

a priority assigned to the target object;

a combined rate of observation sets received from the sensing devices per unit of time;

a motion history of the target object; and

overall load of the property-estimation apparatus.

24. A property-estimation apparatus according to 22, further comprising means for dynamically adjusting the time interval between update cycles based on one or more of the following:

variance in the attributes of particles;

the number of target objects served by the property-estimation apparatus;

quality requirements for the property estimate;

a priority assigned to the target object;

a combined rate of observation sets received from the sensing devices per unit of time

a motion history of the target object; and

overall load of the property-estimation apparatus.