System and/or method for pedestrian navigation

Abstract

Disclosed are methods, apparatuses and systems for tracking a location of a mobile device based, at least in part, on measurements over time. In response to measurements, particles in a motion model may be propagated in a first routing graph covering an area. Propagated particles may be indicative of a direction of movement along a second routing graph covering the same area or a larger area in some embodiments.

What is claimed is: 
     
         1 . A method comprising:
 identifying particles representing possible states of a mobile device, the possible states including at least possible locations of the mobile device in an area;   determining a target anchor node of a plurality of anchor nodes in a first routing graph connecting a plurality of cells of the area; and   propagating one or more of the particles subject to edges of a second routing graph connecting nodes within at least one cell of the plurality of cells to represent possible movement of the mobile device based, at least in part, on the determined target anchor node.   
     
     
         2 . The method of  claim 1 , wherein the target cell is adjacent a current cell of the plurality of cells, the method further comprising selecting the target cell based, at least in part, on an estimated speed of movement of the mobile device along the first routing graph. 
     
     
         3 . The method of  claim 2 , further comprising selecting a previous cell as a subsequent target cell in response to a detection that the mobile device has entered an adjacent cell other than the target cell. 
     
     
         4 . The method of  claim 2 , further comprising selecting a neighboring cell as a new target cell in response to a detection that the mobile device has entered the target cell following expiration of a wander timer. 
     
     
         5 . The method of  claim 1 , further comprising determining a direction from a current cell of the plurality of cells to the target anchor node. 
     
     
         6 . The method of  claim 5 , further comprising determining likelihoods for transitioning over a plurality of respective edges of the second routing graph based, at least in part, on the determined direction, wherein the propagating is based, at least in part, on the determined likelihoods. 
     
     
         7 . The method of  claim 1 , wherein the particles are indicative of a likelihood of a motion state of the mobile device including a location of the mobile device along an edge in the second routing graph. 
     
     
         8 . The method of  claim 1 , wherein the first routing graph comprises a reduced routing graph, and wherein at least some of the plurality of anchor nodes are located at opportunities for change of direction. 
     
     
         9 . The method of  claim 1 , wherein at least one of the anchor nodes is located at an intersection of hallways. 
     
     
         10 . The method of  claim 1 , wherein movement along the first routing graph models natural pedestrian movement. 
     
     
         11 . A mobile device comprising:
 one or more inertial sensors configured to generate measurement signals in response to movement; and   a processor configured to:
 identify particles representing possible states of the mobile device, the possible states including at least possible locations of the mobile device in an area; 
 determine a target anchor node of a plurality of anchor nodes in a first routing graph connecting a plurality of cells of the area; and 
 propagate one or more of the particles subject to edges of a second routing graph connecting nodes within at least one cell of the plurality of cells to represent possible movement of the mobile device based, at least in part, on the determined target anchor node. 
   
     
     
         12 . The mobile device of  claim 11 , wherein the target cell is adjacent a current cell of the plurality of cells, and wherein the processor is further configured to select the target cell based, at least in part, on an estimated speed of movement of the mobile device along the first routing graph. 
     
     
         13 . The mobile device of  claim 12 , wherein the processor is further configured to select a previous cell as a subsequent target cell in response to a detection that the mobile device has entered an adjacent cell other than the target cell. 
     
     
         14 . The mobile device of  claim 12 , wherein the processor is further configured to select a neighboring cell as a new target cell in response to a detection that the mobile device has entered the target cell following expiration of a wander timer. 
     
     
         15 . The mobile device of  claim 11 , wherein the processor is further configured to determine a direction from a current cell of the plurality of cells to the target anchor node. 
     
     
         16 . The mobile device of  claim 15 , wherein the processor is further configured to determine likelihoods for transitioning over a plurality of respective edges of the second routing graph based, at least in part, on the determined direction, wherein the propagating is based, at least in part, on the determined likelihoods. 
     
     
         17 . The mobile device of  claim 11 , wherein the particles are indicative of a likelihood of a motion state of the mobile device including a location of the mobile device along an edge in the second routing graph. 
     
     
         18 . The mobile device of  claim 11 , wherein the first routing graph includes a reduced routing graph, and wherein at least some of the plurality of anchor nodes are located at opportunities for change of direction. 
     
     
         19 . The mobile device of  claim 11 , wherein the processor is further configured to select an adjacent target cell based, at least in part, on an estimated speed of movement of the mobile device along the second routing graph. 
     
     
         20 . The mobile device of  claim 19 , wherein the processor is further configured to select a previous cell as a subsequent target cell in response to a detection that the mobile device has entered an adjacent cell other than the adjacent target cell. 
     
     
         21 . The mobile device of  claim 20 , wherein the processor is further configured to select a neighboring cell as a new target cell in response to a detection that the mobile device has entered the adjacent target cell following expiration of a wander timer. 
     
     
         22 . The mobile device of  claim 11 , wherein the processor is further configured to select an adjacent target cell based, at least in part, on a determined direction of movement of the mobile device along the second routing graph. 
     
     
         23 . A non-transitory storage medium comprising machine-readable instructions stored thereon which are executable by a special purpose computing apparatus to:
 identify particles representing possible states of a mobile device, the possible states including at least possible locations of the mobile device in an area;   determine a target anchor node of a plurality of anchor nodes in a first routing graph connecting a plurality of cells of the area; and   propagate one or more of the particles subject to edges of a second routing graph connecting nodes within at least one cell of the plurality of cells to represent possible movement of the mobile device based, at least in part, on the determined target anchor node.   
     
     
         24 . An apparatus comprising:
 means for identifying particles representing possible states of a mobile device, the possible states including at least possible locations of the mobile device in an area;   means for determining a target anchor node of a plurality of anchor nodes in a first routing graph connecting a plurality of cells of the area; and   means for propagating one or more of the particles subject to edges of a second routing graph connecting nodes within at least one cell of the plurality of cells to represent possible movement of the mobile device based, at least in part, on the determined target anchor node.   
     
     
         25 . The apparatus of  claim 24 , wherein the target cell is adjacent a current cell of the plurality of cells, the apparatus further comprising means for selecting the target cell based, at least in part, on an estimated speed of movement of the mobile device along the first routing graph. 
     
     
         26 . The apparatus of  claim 25 , further comprising means for selecting a previous cell as a subsequent target cell in response to a detection that the mobile device has entered an adjacent cell other than the target cell. 
     
     
         27 . The apparatus of  claim 25 , further comprising means for selecting a neighboring cell as a new target cell in response to a detection that the mobile device has entered the target cell following expiration of a wander timer. 
     
     
         28 . The apparatus of  claim 24 , further comprising means for determining a direction from a current cell of the plurality of cells to the target anchor node.