Patent ID: 8386422

Claim:
A method of updating a map of an indoor space, the map being based on a plurality of features, the method comprising: determining a plurality of paths of a portable handheld device through the indoor space, wherein determining each particular path of the plurality of paths includes: generating, by a processor, a first set of particles, each particle of the first set of particles representing a location on the map and being associated with a likelihood value, and wherein each particle of the first set of particles further represents a device heading; receiving data from one or more orientation devices; determining a direction and speed of movement based on the received data; identifying a heading based on the received data; applying the direction and speed of movement to each one of the first set of particles; adjusting the likelihood value of each particle of the first set of particles, based on whether the particular particle violated one or more of the plurality of features and whether the heading associated with each particular particle is associated with a heading consistent with the identified heading; generating a second set of particles by selecting particles of the first set of particles based on the likelihood values associated with the first set of particles and adjusting the representative locations of the selected particles of the first set by a minimal value; for each particular particle of the second set of particles, storing information identifying the particle of the first set selected to generate the particular particle of the second set; if all of the particles of the second set of particles are within a threshold radius of one another, selecting a given particle of the second set of particles closest to an average representative location of the second set of particles; and determining the particular path based on the stored information identifying the particle of the first set selected to generate the selected given particle of the second set; storing the plurality of determined paths in memory; comparing each path of the stored plurality of determined paths to the map to identify common patterns; and updating the map by making one or more changes to the plurality of features based on the identified common patterns.