Abstract:
This document discusses, among other things, a portable device that generates position and orientation data to facilitate movement within a building. The device can be, for example, handheld or affixed to a cane. Data for navigation is derived from reflections from interior surfaces and dead reckoning sensors.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation under 35 U.S.C. 111(a) of International Application No. PCT/US2007/020320, filed Sep. 19, 2007 and published as WO 2008/036325 on Mar. 27, 2008, which application claims priority to expired U.S. provisional application Ser. No. 60/845,925, filed Sep. 20, 2006, which is incorporated herein by reference in its entirety. 
    
    
     TECHNICAL FIELD 
     This document pertains generally to navigation, and more particularly, but not by way of limitation, to indoor navigation. 
     BACKGROUND 
     Human mobility entails execution of several tasks including path planning, navigation, and obstacle avoidance. Visually impaired people cannot accurately assess the surrounding environment. Seeing-eye dogs and white canes are widely used for the purpose of guidance and environment sensing. The former, however, has costly and often prohibitive training requirements, while the latter can only provide cues about ones immediate surroundings. 
     Traditional systems for navigating within a building are generally costly or ineffective. For example, the installation and operating costs associated with an installed base of radio frequency markers within a building are substantial barriers not readily overcome. In addition, poor reception of radio frequency navigation signals within a building, such as that used by satellite-based navigation systems (for example, global positioning systems), precludes widespread acceptance. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       In the drawings, which are not necessarily drawn to scale, like numerals describe substantially similar components throughout the several views. Like numerals having different letter suffixes represent different instances of substantially similar components. The drawings illustrate generally, by way of example, but not by way of limitation, various embodiments discussed in the present document. 
         FIGS. 1 and 2  include block diagrams of an indoor navigation system. 
         FIG. 3  includes an illustration of a cane mounted indoor navigation system. 
         FIG. 4  depicts a trace of attitude covariance of a cane with respect to time. 
         FIG. 5  depicts measurement residuals based on the trace of  FIG. 4 . 
         FIG. 6  depicts the yaw component of a cane&#39;s attitude estimate before and after low-pass filtering. 
         FIG. 7  depicts a trace of position covariance for a cane. 
         FIGS. 8A and 8B  depicts x and y axis position measurement residuals for a cane. 
         FIG. 9  illustrates an estimated trajectory and a floor diagram. 
         FIG. 10  illustrates a method according to the present subject matter. 
     
    
    
     DETAILED DESCRIPTION 
     The following detailed description includes references to the accompanying drawings, which form a part of the detailed description. The drawings show, by way of illustration, specific embodiments in which the present subject matter may be practiced. These embodiments, which are also referred to herein as “examples,” are described in enough detail to enable those skilled in the art to practice the present subject matter. The embodiments may be combined, other embodiments may be utilized, or structural, logical and electrical changes may be made without departing from the scope of the present subject matter. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present subject matter is defined by the appended claims and their equivalents. 
     In this document, the terms “a” or “an” are used, as is common in patent documents, to include one or more than one. In this document, the term “or” is used to refer to a nonexclusive or, unless otherwise indicated. Furthermore, all publications, patents, and patent documents referred to in this document are incorporated by reference herein in their entirety, as though individually incorporated by reference. In the event of inconsistent usages between this document and those documents so incorporated by reference, the usage in the incorporated reference(s) should be considered supplementary to that of this document; for irreconcilable inconsistencies, the usage in this document controls. 
     The present subject matter provides information derived from environmental sensing (e.g., position, orientation, or local geometry) based on the use of appropriate sensors and sensor fusion algorithms. 
     One example of the present subject matter includes a portable system for indoor human localization having a pedometer and a white cane, on which a laser range finder, and a 3-axis gyroscope are disposed. An algorithm executed by a processor estimates the heading and position of a person navigating in an indoor space. The algorithm includes a two-layered, Extended Kalman Filter (EKF) for attitude and position estimation wherein a first layer maintains an attitude estimate of the white cane and a second layer estimates a position of the user. 
     One example of the present subject matter includes a sensor package configured for mounting on a white cane. An exemplary embodiment of this configuration is unobtrusive to the user, is operable without calibration to a particular body type, and preserves the ability of the user to physically touch the environment with the white cane. 
     In one example, a pair of sensors (a laser scanner and a 3-axis gyroscope) are mounted beneath the white cane and provide attitude information about the cane, and a lightweight, foot-mounted pedometer measures the user&#39;s walking speed. Information from these three sources can be fused in a single pose estimator. All the sensors, however, can move in three dimensions (3-D) and the coordinate transformation from the pedometer to the laser/gyro is unknown and time varying. 
     The present subject matter includes a two-stage (2.5-D) estimator. In the first stage, rotational velocity measurements from the 3-axis gyroscope are combined with relative attitude measurements inferred from the laser scan data to estimate the 3-D attitude of the cane. The second stage incorporates corner features extracted from the laser data, linear velocity measurements from the pedometer, and a filtered version of the cane&#39;s yaw to compute 2-D pose estimates of the user. The laser data is utilized in both filters and statistical correlations in the estimates are avoided by using the even-indexed data points in the attitude filter, and the odd-indexed data points in the position filter. By exploiting a priori information about the location of environmental features (corners), and considering that the primary structural planes (floor, ceiling, walls) of a building lie perpendicular to each other, an example of the method generates a reliable localization estimate of a human traveling indoors. 
       FIG. 1  illustrates block diagram of system  100 A configured for indoor navigation. Data received from rotational velocity sensor  30 A and distance sensor  40 A is processed by processor  50 A to generate navigation data that is rendered using output device  60 . Rotational velocity sensor  30 A can include a gyroscope, an inertial measurement unit, an accelerometer, an inclinometer, a magnetometer or other device that generates data corresponding to rotational velocity. Distance sensor  40 A can include a range finding sensor such as a laser-based or ultrasonic-based sensor or other distance measuring equipment. In various examples, distance sensor  40 A includes an acoustical sensor or an optical flow sensor or other camera-based sensor. 
     Processor  50 A, in various examples, includes a handheld computer, such as a personal digital assistant (PDA), a laptop computer or other processor. 
     Output device  60  can include a headphone, a speaker or other audio transducer. In addition, output device  60  can include a haptic transducer that provides a human-perceivable signal corresponding to navigation data derived from processor  50 A. 
       FIG. 2  illustrates a block diagram of system  100 B having rotational velocity sensor  30 A and distance sensor  40 B coupled to processor  50 B. In the figure, distance sensor  40 B includes range sensor  42 A and linear velocity sensor  44 A. Range sensor  42 A, in one example, includes a laser-based rangefinder. Linear velocity sensor  44 A includes a pedometer, an accelerometer or an optical flow sensor. 
     Processor  50 B executes a filter algorithm as described elsewhere in this document and in various examples, includes an extended Kalman filter. In the figure, processor  50 B includes heading estimator  52  and position estimator  54 . Heading estimator  52  includes a filter that generates an estimate of heading based on data from rotational velocity sensor  30 A and data from range sensor  42 A. Range sensor  42 A provides data based on selected point locations and line segments. 
     Data corresponding to the heading estimate is provided to position estimator  54 . Position estimator  54  receives inputs from linear velocity sensor  44 A and, in the example shown, data from range sensor  42 A. Data provided by range sensor  42 A can include features and landmarks. 
     In addition, processor  50 B is shown coupled to additional data input  70 . In one example, additional data input  70  includes a digital file corresponding to a stored map. The stored map data can be received wirelessly by a transceiver or from a user-accessible storage device. 
       FIG. 3  illustrates exemplary system  300 . In the example illustrated, sensor  30 B and sensor  42 B are mounted using housing  20 . Housing  20  is shown affixed to white cane  10 . Housing  20  also includes power module  80  which, in various examples includes a rechargeable or replaceable battery. Processor  50 A is coupled to power module  80  as well as memory  55 . Memory  55  can provide storage for instructions used by processor  50 A in executing an algorithm as well as data storage corresponding to the navigation data generated by processor  50 A. Wireless interface  75  is coupled to processor  50 A and in various examples, includes a Bluetooth transceiver or other radio frequency telemetry link. In the example illustrated, output device  60  is coupled by wireless interface  75 . 
     Linear velocity sensor  44 B, in the example illustrated, includes a pedometer configured for attachment to the user. In various examples, the pedometer is attached to a leg, hip or foot. Sensors  30 B,  42 B and  44 B are interfaced to processor  50 A via USB, RS-232, and Bluetooth, respectively. The real-time software components are written in C++, and the software for simulation and data plotting is written in Matlab. The sensor bay, or housing  20 , is mounted beneath white cane  10  which measures 1.27 m when extended and 0.33 m when retracted. In one example, cane  10  is a light-weight carbon fiber cane and the total weight, including sensors, is approximately the same as a standard white cane. 
     Laser scanner of sensor  42 B, in one example, includes an URG-X002S which measures 5 cm by 5 cm by 7 cm. It has an angular scan range of 240 degrees, with an accuracy of ±1% of the measurement for distances 1 m to 4 m. Closer than 1 m, the measurement accuracy is ±10 mm. The laser scanner can measure distances ranging from 0.02 m to 4 m. The scanner weighs 160 g and consumes 2.5 W at 5V. 
     The 3-axis gyroscope of sensor  30 B, in one example, includes an ISIS Inertial Measurement Unit (IMU), with an angular-rate range of ±90 deg/sec. Over an RS-232 connection, the ISIS IMU provides measurements at 100 Hz. The weight of the sensor is 363 g, and the power consumption is 6.72 W at 12V. The IMU measures 5.5 cm by 6.5 cm by 7 cm. 
       FIG. 3  also illustrates pedometer of sensor  44 B which provides linear velocity measurements as the person walks. The size of this sensor is 8.5 cm by 3.5 cm by 3.5 cm. Communication packets are received via Bluetooth at a rate of 1 Hz. 
     Method 
     An exemplary method includes generating an attitude estimate of the white cane, determining the heading direction and determining a position of the person. The attitude of the white cane is estimated using a 3-axis gyroscope, and laser-scan measurements of structural planes in the building. The heading direction of the person is extracted from the yaw component of the white cane&#39;s attitude estimate with the use of a low-pass filter. This provides a heading measurement to the position filter. The position of the person is estimated using the heading estimates from the low-pass filter, the linear velocity measurements from the pedometer, and the relative coordinates of known corner features detected by the laser scanner. 
     A. Attitude Estimation of the White Cane 
     Estimating the attitude of an object in 3-D entails parametrization of the elements involved. One method for specifying an orientation in 3-D is by means of roll, pitch, and yaw (rpy) angles. While the rpy representation is intuitive and readily visualized, it suffers from singularities which can cause instability in an estimator. A more robust attitude representation is the quaternion of rotation 
                   q   =             [       k   ^     ⁢   sin   ⁢     θ   2                 cos   ⁢     θ   2       ]           T             (   1   )               
where {circumflex over (k)} is the axis of rotation, and θ signifies the magnitude of rotation. The quaternion representation of an attitude is compact and singularity-free. For clarity, the quaternion notation employed in this paper results in “natural order” quaternion multiplication. As such, the symbol             denotes quaternion multiplication fulfilling  L     3     L     1   q= L     2     L     1   q           L     3     L     2   q, which is the attitude rotation between successive frames.

     Attitude estimation is accomplished through the use of an EKF which fuses measurements from proprioceptive and exteroceptive sensing devices. Rotational velocity measurements from a 3-axis gyroscope are integrated to propagate the attitude estimate, and lines extracted from the laser-scan data are used to update the computed estimate. 
     1) Attitude Propagation 
     Propagation of the attitude estimate is performed through the incorporation of proprioceptive information and knowledge about the state propagation model of the system. The gyroscope measures the rotational velocities about each of the local coordinate axes; these velocities are integrated at each time step to generate a new attitude estimate (cf. (4)). 4)). The state vector X k  includes the quaternion q and the gyroscope bias  b . The error state {tilde over (X)} k  includes the attitude angle-error vector δθ and the gyroscope bias error state Δb=b−{circumflex over (b)}. 
     The state vector X k  is 7×1 and the error state {tilde over (X)} k  is 6×1. Some EKF formulations maintain equal sized state and error state vectors. The quaternion of rotation, however, is defined to have unit length which causes the corresponding covariance matrix to lose rank. To account for this, only the attitude angle-error vector δθ (cf. (2)) is used in the error state. 
     Some EKF applications employ an additive error model. It is convenient though, when using quaternions, to quantify the error as a multiplicative error term 
     
       
         
           
             
               
                 
                   
                     δ 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     q 
                   
                   = 
                   
                     
                       q 
                       ⊗ 
                       
                         
                           q 
                           ^ 
                         
                         
                           - 
                           1 
                         
                       
                     
                     ≅ 
                     
                       [ 
                       
                         
                           
                             
                               
                                 1 
                                 2 
                               
                               ⁢ 
                               δθ 
                             
                           
                         
                         
                           
                             1 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     The error quaternion δq denotes a small rotational error between the true, q, and the estimated, {circumflex over (q)}, attitude of the cane. 
     The state model for the quaternion representation of attitude is governed by the quaternion time derivative (3), which is computed in terms of the instantaneous rotational velocity ω. 
                         q   .     ⁡     (   t   )       =       1   2     ⁢     Ω   ⁡     (   ω   )       ⁢     q   ⁡     (   t   )           ⁢     
     ⁢       Ω   ⁡     (   ω   )       =     [           -     ⌊     ω   ×     ⌋           ω             -   ω         0         ]               (   3   )               
where └ωx┘ denotes the skew symmetric cross-product matrix
 
     
       
         
           
             
               ⌊ 
               
                 ω 
                 × 
               
               ⌋ 
             
             = 
             
               [ 
               
                 
                   
                     0 
                   
                   
                     
                       - 
                       
                         ω 
                         3 
                       
                     
                   
                   
                     
                       ω 
                       2 
                     
                   
                 
                 
                   
                     
                       ω 
                       3 
                     
                   
                   
                     0 
                   
                   
                     
                       - 
                       
                         ω 
                         1 
                       
                     
                   
                 
                 
                   
                     
                       - 
                       
                         ω 
                         2 
                       
                     
                   
                   
                     
                       ω 
                       1 
                     
                   
                   
                     0 
                   
                 
               
               ] 
             
           
         
       
     
     Propagating the quaternion from time step k to k+1 entails quaternion integration 
     
       
         
           
             
               
                 
                   
                     
                       q 
                       
                         k 
                         + 
                         1 
                       
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 
                                   ω 
                                   
                                      
                                     ω 
                                      
                                   
                                 
                                 ⁢ 
                                 
                                   sin 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         
                                            
                                           ω 
                                            
                                         
                                         2 
                                       
                                       ⁢ 
                                       Δ 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       t 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           
                             
                               
                                 cos 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       
                                          
                                         ω 
                                          
                                       
                                       2 
                                     
                                     ⁢ 
                                     Δ 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     t 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         ] 
                       
                       ⊗ 
                       
                         q 
                         k 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                        
                       ω 
                        
                     
                     = 
                     
                       
                         
                           ω 
                           T 
                         
                         ⁢ 
                         ω 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     The gyroscope noise model dictates that angular velocity measurements are corrupted by sensor bias b, as well as measurement noise n r . The gyroscope measurement is:
 
ω m   =ω+b+n   r   (5)
 
where the turn rate noise n r  is distributed as zero-mean white Gaussian with covariance σ r   2 I 3×3 . The sensor bias b is modeled as a random walk with
 
{dot over (b)}=n ω   (6)
 
where n ω  is also distributed as zero-mean white Gaussian noise with covariance σ ω   2 I 3×3 .
 
     The error state equation is computed by taking the derivative of the error state: 
                       X     ~   .       =         F   c     ·     X   ~       +       G   c     ·   n         ⁢     
     ⁢             [           δ   ⁢     θ   .                 Δ   ⁢           ⁢     b   .             ]     =       ⁢         [           -     ⌊       ω   ^     ×     ⌋             -     I     3   ×   3                   0     3   ×   3             0     3   ×   3             ]     ·     [         δθ             Δ   ⁢           ⁢   b           ]       +                     ⁢       [           -     I     3   ×   3               0     3   ×   3                 0     3   ×   3             I     3   ×   3             ]     ·     [           n   r               n   ω           ]                       (   7   )               
where the matrix F c  is the continuous-time system matrix, and G c  is the corresponding noise matrix. The matrices 0 m×n  and I m×n  are the m×n zero, and identity matrices, respectively.
 
     While knowledge of the continuous-time system and noise matrices is useful for attaining theoretical results, implementation on a digital computer requires the corresponding discrete-time matrices. For this reason, the above equations are discretized to obtain the discrete-time Kalman filter equations. The discrete-time state transition matrix is defined in terms of its continuous-time counterpart as: 
     
       
         
           
             
               
                 
                   
                     Φ 
                     ⁡ 
                     
                       ( 
                       
                         
                           t 
                           
                             k 
                             + 
                             1 
                           
                         
                         , 
                         
                           t 
                           k 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     ⅇ 
                     
                       
                         ∫ 
                         
                           t 
                           k 
                         
                         
                           t 
                           
                             k 
                             + 
                             1 
                           
                         
                       
                       ⁢ 
                       
                         
                           
                             F 
                             c 
                           
                           ⁡ 
                           
                             ( 
                             τ 
                             ) 
                           
                         
                         ⁢ 
                         
                           ⅆ 
                           τ 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     Attaining the discrete-time noise matrix Q d , is accomplished by integrating the equivalent continuous-time stochastic model over one time step. 
     
       
         
           
             
               
                 
                   
                     Q 
                     d 
                   
                   = 
                   
                     
                       ∫ 
                       k 
                       
                         k 
                         + 
                         1 
                       
                     
                     ⁢ 
                     
                       
                         Φ 
                         ⁡ 
                         
                           ( 
                           
                             
                               t 
                               
                                 k 
                                 + 
                                 1 
                               
                             
                             , 
                             τ 
                           
                           ) 
                         
                       
                       ⁢ 
                       
                         
                           G 
                           c 
                         
                         ⁡ 
                         
                           ( 
                           τ 
                           ) 
                         
                       
                       ⁢ 
                       
                         Q 
                         c 
                       
                       ⁢ 
                       
                         
                           G 
                           c 
                           T 
                         
                         ⁡ 
                         
                           ( 
                           τ 
                           ) 
                         
                       
                       ⁢ 
                       
                         
                           Φ 
                           T 
                         
                         ⁡ 
                         
                           ( 
                           
                             
                               t 
                               
                                 k 
                                 + 
                                 1 
                               
                             
                             , 
                             τ 
                           
                           ) 
                         
                       
                       ⁢ 
                       
                         ⅆ 
                         τ 
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
             
               
                 
                   
                     where 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       Q 
                       c 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             
                               σ 
                               r 
                               2 
                             
                             ⁢ 
                             
                               I 
                               
                                 3 
                                 × 
                                 3 
                               
                             
                           
                         
                         
                           
                             0 
                             
                               3 
                               × 
                               3 
                             
                           
                         
                       
                       
                         
                           
                             0 
                             
                               3 
                               × 
                               3 
                             
                           
                         
                         
                           
                             
                               σ 
                               ω 
                               2 
                             
                             ⁢ 
                             
                               I 
                               
                                 3 
                                 × 
                                 3 
                               
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     With the required matrices now defined, the propagated state is computed in the following manner; the bias estimate is:
 
 {circumflex over (b)}   k+1|k   ={circumflex over (b)}   k|k   (10)
 
     The turn rate measurement is estimated by subtracting the estimated bias from the actual measurement
 
{circumflex over (ω)} k|k =ω m     k     −{circumflex over (b)}   k|k   (11)
 
     The quaternion estimate is propagated using the quaternion integrator (4), and the current estimate of the turn rate {circumflex over (ω)} k|k . 
     After computing Φ (cf. (8)) and Q d  (cf. (9)), the covariance propagation is completed using the general form of the EKF covariance propagation
 
 P   k+1|k   =ΦP   k|k Φ T   +Q   d   (12)
 
     2) Attitude Update 
     Even-indexed laser scan data points from a laser range finder are employed to measure the relative orientation between the sensor frame of reference {S} and the global frame {G}. Specifically, the laser sensing plane intersects the planar surfaces inside a building (e.g., walls, floor, ceiling) along lines which can be reliably detected and extracted from the laser data. The direction of each of the extracted lines is processed as a measurement for updating the attitude estimates. 
     While inside a building, frame {G} can be assigned such that its principal axes {e1,e2,e3} are perpendicular to the prominent structural planes of the building (i.e., e1⊥Wallx, e2⊥Wally, and e3⊥Floor, Ceiling). Measurements to these planes are denoted by their corresponding unit-vectors (e.g., an x-measurement is a measured line which is perpendicular to the e1 of the global frame). Let e i ε{e1,e2,e3} be one of the three orthogonal unit vectors which span the frame {G}, and let  G l denote the (unit vector) direction of the line of intersection between the laser-scan plane and the measured plane with respect to {G}. Then from the geometric constraint, their inner product should be zero.
 
e i   TG l=0,i=1,2,3  (13)
 
     The measurement equation is derived by rewriting the constraint (cf. (13)) using the transformation relation  G l= S   G C(q) S l=C T (q) S l, i.e.:
 
 z=e   i   T   C   T ( q ) S   l= 0  (14)
 
 {circumflex over (z)}=e   i   T   C   T ( {circumflex over (q)} ) S   l   m   (15)
 
the rotation matrix C T (q) denotes the rotation from frame {S} to frame {G} Note that since  S l is the unit vector direction of a line on the x-y plane of the laser sensor frame, it can be written as  S l=[sin φ−cos φ0] T  where φ is the complimentary angle to the line direction. In order to derive the measurement matrix, the true line direction is replaced by its equivalent representation  S l= S l m + S {tilde over (l)}. Here,  S l m  denotes the measured line direction and  S {tilde over (l)}=└e3x┘ S l m φ is the error in this measurement; the true rotation matrix is approximated as
 
 C   T ( q )= C   T (δ q               {circumflex over (q)} )≅ C   T ( {circumflex over (q)} )+ C   T ( {circumflex over (q)} )└δθ x┘ 

     Using (14) and (15), the measurement error {tilde over (z)}=z−{circumflex over (z)} is: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           z 
                           ~ 
                         
                         ≅ 
                           
                         ⁢ 
                         
                           
                             
                               - 
                               
                                 e 
                                 i 
                                 T 
                               
                             
                             ⁢ 
                             
                               
                                 C 
                                 T 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   q 
                                   ^ 
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               ⌊ 
                               
                                 
                                   l 
                                   m 
                                     
                                     
                                     
                                   S 
                                 
                                 × 
                               
                               ⌋ 
                             
                             ⁢ 
                             δθ 
                           
                           + 
                           
                             
                               e 
                               i 
                               T 
                             
                             ⁢ 
                             
                               
                                 
                                   C 
                                   T 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     q 
                                     ^ 
                                   
                                   ) 
                                 
                               
                               S 
                             
                             ⁢ 
                             
                               l 
                               ~ 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             
                               [ 
                               
                                 
                                   - 
                                   
                                     e 
                                     i 
                                     T 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     C 
                                     T 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       q 
                                       ^ 
                                     
                                     ) 
                                   
                                 
                                 ⁢ 
                                 
                                   ⌊ 
                                   
                                     
                                       l 
                                       m 
                                         
                                         
                                         
                                       S 
                                     
                                     × 
                                   
                                   ⌋ 
                                 
                                 ⁢ 
                                 
                                   0 
                                   
                                     1 
                                     × 
                                     3 
                                   
                                 
                               
                               ] 
                             
                             ⁡ 
                             
                               [ 
                               
                                 
                                   
                                     
                                       δ 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       θ 
                                     
                                   
                                 
                                 
                                   
                                     
                                       Δ 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       b 
                                     
                                   
                                 
                               
                               ] 
                             
                           
                           + 
                           
                             
                               e 
                               i 
                               T 
                             
                             ⁢ 
                             
                               
                                 C 
                                 T 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   q 
                                   ^ 
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               ⌊ 
                               
                                 e3 
                                 × 
                               
                               ⌋ 
                             
                             ⁢ 
                             
                               l 
                               m 
                                 
                                 
                                 
                               S 
                             
                             ⁢ 
                             
                               ϕ 
                               ~ 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             
                               h 
                               T 
                             
                             ⁢ 
                             
                               X 
                               ~ 
                             
                           
                           + 
                           n 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
     The line direction error {tilde over (φ)} accounts for measurement noise as well as inaccuracies in line fitting. Various line fitting methods and the corresponding error models can be utilized. 
     Updating the attitude filter is done by first computing the residual
 
 r=z−e   i   T   C   T ( {circumflex over (q)} ) S   l   m   =−e   i   T   C   T ( {circumflex over (q)} ) S   l   m   (17)
 
     Second, the covariance of the residual (cf. (18)), and the Kalman gain (cf. (19)) are computed:
 
 S=h   T   Ph+R   (18)
 
 k=PhS   −1   (19)
 
where R=E{n 2 }=(e i   T C T ({circumflex over (q)})└e3x┘ S l m ) 2 σ φ   2  and σ φ   2 =E{{tilde over (φ)} 2 }. The error state update is computed as
 
                     Δ   ⁢           ⁢       x   ^     ⁡     (   +   )         =       [           δ   ⁢       θ   ^     ⁡     (   +   )                   Δ   ⁢           ⁢       b   ^     ⁡     (   +   )               ]     =       [             2   ·   δ     ⁢           ⁢       q   ^     ⁡     (   +   )                   Δ   ⁢           ⁢       b   ^     ⁡     (   +   )               ]     =   kr               (   20   )               
The error quaternion estimate is
 
                     δ   ⁢           ⁢     q   ^       =       1       1   +     δ   ⁢           ⁢         q   ^     ⁡     (   +   )       T     ⁢   δ   ⁢           ⁢       q   ^     ⁡     (   +   )               ·     [           δ   ⁢           ⁢       q   ^     ⁡     (   +   )                 1         ]               (   21   )               
The quaternion estimate, and the bias estimate are updated as
 
 {circumflex over (q)}   k+1|k+1   =δ{circumflex over (q)}               {circumflex over (q)}   k+1|k   (22)
 
 {circumflex over (b)}   k+1|k+1   ={circumflex over (b)}   k+1|k   +Δ{circumflex over (b)} (+)  (23)

     The last step in the attitude filter update is to update the covariance [22]:
 
 P   k+1|k+1 =( I−kh   T ) P   k+1|k ( I−kh   T ) T   +kRk   T   (24)
 
     3) Attitude Observability 
     Due to physical limitations of planar laser scanning, it is impossible to resolve all three degrees of rotational freedom from a stationary vantage point. The attitude of the cane, however, is stochastically observable when the cane is in motion. The observability requirements are satisfied when the laser sensor detects all three main directions in space, at different time steps, over a given time interval. 
     Since observability of the attitude entails observability of the bias, a simplified measurement model is used with only the quaternion as state variable, and measurement matrix
 
 h   i   T   =└−e   i   T   C   T ( {circumflex over (q)} )└ S   l   m   x┘┘   (25)
 
     In order to establish stochastic observability of the attitude, it suffices to show that the observability Gramian 
                   M   =       ∑     μ   =     v   -   N   +   1       v     ⁢       ∑   i     ⁢       Φ       t   μ     ,     t   v       T     ⁢     h     i   ,     t   μ         ⁢     R     i   ,     t   μ         -   1       ⁢     h     i   ,     t   μ       T     ⁢     Φ       t   μ     ,     t   v                       (   26   )               
is of full rank for all v≧N [24].
 
     Noting that the state transition matrix equals Φ t     μ     ,t     v   =C( S     v     S     μ   q), the observability matrix can be expressed, after pre- and postmultiplication with the proper rotational matrices, as 
                         M   =       ⁢       ∑     i   ,   μ       ⁢       R     i   ,     t   μ         -   1       ⁢       C   T     ⁡     (       q   ^       t   μ       )       ⁢     h     i   ,     t   μ         ⁢     h     i   ,     t   μ       T     ⁢     C   ⁡     (       q   ^       t   μ       )                       =       ⁢       ∑     i   ,   μ       ⁢         R     i   ,     t   μ         -   1       ⁡     (       l       i   m     ,     t   μ                   G     ×     e   i               G       )       ⁢       (       l       i   m     ,     t   μ                   G     ×     e   i               G       )     T                       (   27   )               
that is, as a weighted sum of outer products of vectors  G l im . If, over a period of time, the sensor observes surfaces with normals e i  that span R 3 , and recalling that  G l i   TG e i =0(cf. (13)), then the vectors  G h i  also span the 3D-space, ensuring M to be of full rank.
 
       FIG. 4  depicts graphic  240  showing the trace of the attitude covariance matrix with respect to time. As shown in graphic  240 , while the cane is stationary (during bias initialization) its attitude is initially unobservable, however, it becomes observable while the cane is in motion. 
     During this experiment, the white cane was initially stationary for 10 sec for the purpose of gyroscope bias initialization. As evident from the experimental results, the trace of the attitude covariance becomes bounded (as expected since the system is observable) once the cane is in motion. In order to ensure consistency of the EKF estimator, the measurement residuals should lie within the 3σ bounds of the residual covariance. This is verified by the results shown in graphic  250  of  FIG. 5 . Line measurement residual  252  and 3σ bounds  254  are shown in this plot from the residual covariance. The units of the vertical-axis are omitted considering that this measurement residual is by nature unit-less (it is the difference of unit vector dot-products). 
     B. Heading Estimation 
     By estimating the attitude of the cane, the orientation of the person can be inferred. During regular operation, the yaw angle of the cane will be an asymmetric cyclostationary random process in which the amplitude, phase, frequency and degree of asymmetry may all change ( FIG. 6 ). These characteristics result from swinging the white cane which helps the person identify a clear walking path. Extracting the heading direction of the person from the cane&#39;s yaw signal can be accomplished through signal processing. To facilitate real time operation, the following method can be used. 
     The heading of a person can be approximated as the mean value of the cane yaw over a period of swinging. One solution includes a combination of frequency estimation, and low pass filtering to remove the high frequency component of the yaw. This motivates the use of a Finite Impulse Response (FIR) filter. The attitude EKF provides yaw estimates at 100 Hz. Due to the nature of the motion of the cane, the high frequency component of the yaw does not fall below 0.5 Hz. In order to reduce the number of taps needed by the filter, the yaw signal is downsampled by a factor of 40. The signal is then filtered using a 7th order FIR filter with Kaiser window β=0.5, and a normalized cut-off frequency of 0.02. 
       FIG. 6  depicts graphic  260  showing the yaw component of the cane&#39;s attitude estimate ( 262 ) along with the filtered version ( 264 ). A byproduct of filtering the yaw signal is that a delay is introduced into the system. Although the filter has only seven coefficient-delay pairs, there is a delay of 1.2 sec because the downsampled yaw signal has a sampling frequency of 2.5 Hz. As a result, an equivalent time-lag exists in the position estimate. However, due to the relatively slow walking rate of a person carrying a white cane, this delay is acceptable for real-time operation. 
     C. Position Estimation of the Person 
     An EKF is employed for the purpose of map-based human localization. Estimating the position of a person within a building can be treated as a 2-D position estimation problem in which each floor of the building is a separate environment containing landmarks, in this case corner features, whose position is known. While a person is traversing a single floor, their motion will be constrained on the plane of that floor. This allows for the use of a generic odometry propagation framework. 
     1) Position Propagation 
     The non-holonomic formulation of the odometry state equations typically uses the linear and rotational velocity measurements during the propagation stage. These constraints are relaxed for the case of a person. Linear velocity measurements are provided by a foot-mounted wireless pedometer. Note that rotational velocity measurements need not be accessible as the person&#39;s heading direction is available from the FIR filter. This odometric model is referred to as direct heading odometry.
 
 x   k+1   =x   k   +Vδt  cos ψ, y   k+1   =y   k   +Vδt  sin ψ
 
 {circumflex over (x)}   k+1   ={circumflex over (x)}   k   +Vδt  cos ψ m   ,ŷ   k+1   =ŷ   k   +Vδt  sin ψ m  
 
where x, y, and ψ are the position and orientation of the person, and V is the average velocity during the time interval δt. In the above equations “^” denotes estimates while the subscript m refers to measured quantities, i.e.,
 
 V   m   =V+ω   v ,ψ m =ψ+ω ψ 
 
where the velocity, ω v , and heading, ω ψ , noises are zero-mean white Gaussian processes with variances σ v   2  and σ ψ   2  respectively. The error model based on these relations is:
 
     
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             
                               
                                 x 
                                 ~ 
                               
                               
                                 k 
                                 + 
                                 1 
                               
                             
                           
                         
                         
                           
                             
                               
                                 y 
                                 ~ 
                               
                               
                                 k 
                                 + 
                                 1 
                               
                             
                           
                         
                       
                       ] 
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 
                                   x 
                                   ~ 
                                 
                                 k 
                               
                             
                           
                           
                             
                               
                                 
                                   y 
                                   ~ 
                                 
                                 k 
                               
                             
                           
                         
                         ] 
                       
                       + 
                       
                         
                           [ 
                           
                             
                               
                                 
                                   
                                     - 
                                     δ 
                                   
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   t 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   cos 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     ψ 
                                     m 
                                   
                                 
                               
                               
                                 
                                   
                                     V 
                                     m 
                                   
                                   ⁢ 
                                   δ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   t 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   sin 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     ψ 
                                     m 
                                   
                                 
                               
                             
                             
                               
                                 
                                   
                                     - 
                                     δ 
                                   
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   t 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   sin 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     ψ 
                                     m 
                                   
                                 
                               
                               
                                 
                                   
                                     - 
                                     
                                       V 
                                       m 
                                     
                                   
                                   ⁢ 
                                   δ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   t 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   cos 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     ψ 
                                     m 
                                   
                                 
                               
                             
                           
                           ] 
                         
                         ⁡ 
                         
                           [ 
                           
                             
                               
                                 
                                   ω 
                                   v 
                                 
                               
                             
                             
                               
                                 
                                   ω 
                                   ψ 
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         X 
                         ~ 
                       
                       
                         k 
                         + 
                         1 
                       
                     
                     = 
                     
                       
                         
                           X 
                           ~ 
                         
                         k 
                       
                       + 
                       
                         Γ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         n 
                       
                     
                   
                 
               
               
                 
                   ( 
                   28 
                   ) 
                 
               
             
           
         
       
     
     The covariance propagation is computed as 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       
                         k 
                         + 
                         
                           1 
                           ⁢ 
                           
                              
                             k 
                           
                         
                       
                     
                     = 
                     
                       
                         P 
                         
                           
                             k 
                              
                           
                           ⁢ 
                           k 
                         
                       
                       + 
                       
                         Γ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         Q 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           Γ 
                           T 
                         
                       
                     
                   
                   , 
                   
                       
                   
                   ⁢ 
                   
                     
                       where 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       Q 
                     
                     = 
                     
                       [ 
                       
                         
                           
                             
                               σ 
                               v 
                               2 
                             
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             
                               σ 
                               ψ 
                               2 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   29 
                   ) 
                 
               
             
           
         
       
     
     2) Position Update 
     The person&#39;s position estimate is updated by incorporating relative position measurements to known landmarks in the environment. Although the selection of features is arbitrary, using corners at hallway intersections is a good choice for an indoor environment because they occur with a relatively high frequency, and they can be extracted reliably from the laser-scan data. By extracting lines from the odd-indexed laser scan data points, corners are identified with the following characteristics: (i) two lines must be nearly perpendicular, (ii) the endpoints of the lines must be within 5 cm of each other, and (iii) the line orientations must match the possible wall orientations in the environment. 
     The relative position measurement is written as a 3-D vector from the sensor to the landmark which is aligned to the sensor frame and projected down to 2-D: 
     
       
         
           
             
               
                 
                   
                     z 
                     = 
                     
                       Π 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         C 
                         ⁡ 
                         
                           ( 
                           q 
                           ) 
                         
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             p 
                             
                               L 
                               i 
                             
                               
                               
                               
                             G 
                           
                           - 
                           
                             p 
                             S 
                               
                               
                               
                             G 
                           
                         
                         ) 
                       
                     
                   
                   , 
                   
                       
                   
                   ⁢ 
                   
                     
                       where 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       Π 
                     
                     = 
                     
                       [ 
                       
                         
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   30 
                   ) 
                 
               
             
             
               
                 
                   
                     z 
                     ^ 
                   
                   = 
                   
                     Π 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       C 
                       ⁡ 
                       
                         ( 
                         
                           q 
                           ^ 
                         
                         ) 
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           p 
                           
                             L 
                             i 
                           
                             
                             
                             
                           G 
                         
                         - 
                         
                           
                             p 
                             ^ 
                           
                           S 
                             
                             
                             
                           G 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   31 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           z 
                           ~ 
                         
                         ≅ 
                           
                         ⁢ 
                         
                           
                             
                               - 
                               Π 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               C 
                               ⁡ 
                               
                                 ( 
                                 
                                   q 
                                   ^ 
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               
                                 p 
                                 ~ 
                               
                               S 
                                 
                                 
                                 
                               G 
                             
                           
                           + 
                           
                             Π 
                             ⁢ 
                             
                               ⌊ 
                               
                                 
                                   C 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       q 
                                       ^ 
                                     
                                     ) 
                                   
                                 
                                 ⁢ 
                                 Δ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   p 
                                   ^ 
                                 
                                 × 
                               
                               ⌋ 
                             
                             ⁢ 
                             δ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             θ 
                           
                           + 
                           
                             Π 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               n 
                               p 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             H 
                             ⁢ 
                             
                               X 
                               ~ 
                             
                           
                           + 
                           Γδθ 
                           + 
                           
                             Π 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               n 
                               p 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   32 
                   ) 
                 
               
             
           
         
       
     
     The vector Δ{circumflex over (p)} in (32) is the difference between the true position of the ith landmark  G p Li  and the measured location  G p Li     m   . The measurement noise, denoted n p , is due to noise in the laser scan and linearization errors, and has covariance R p . The position of the sensor S in frame {G} is denoted as  G p S . 
     The measurement update is performed by computing the measurement residual
 
 r   k+1   =z   k+1   −{circumflex over (z)}   k+1   (33)
 
the covariance of the residual
 
 S   k+1   =H   k+1   P   k+1|k   H   k+1   T   +πR   p π T   (34)
 
and the Kalman gain
 
 K   k+1   =P   k+1|k   H   k+1   T   S   k+1   −1   (35)
 
     With the matrices computed, the state estimate is updated using
 
 {circumflex over (X)}   k+1|k+1   ={circumflex over (X)}   k+1|k   +K   k+1 ( z   k+1   −{circumflex over (z)}   k+1 )  (36)
 
Lastly, the covariance is updated using
 
 P   k+1|k+1 =( I   2×2   −K   k+1   H   k+1 ) P   k+1|k ( I   2×2   −K   k+1   H   k+1 ) T   +K   k+1   RK   k+1   T   (37)
 
     The system and method described herein can be used in an indoor environment such as the closed loop path shown in  FIG. 9 . The closed loop has a path length of 130 m. Twenty-one corners along this loop are known a priori from the building blueprints or from another source and are used as features for position updates. While walking around, the user swings the cane to and fro in a natural manner while searching for obstacles which might lie in the path.  FIG. 9  shows the estimated trajectory super-imposed on the floor diagram. 
       FIG. 9  shows data for a 130 m test run, starting in the lower left corner, traveling counter-clockwise and ending back at the start location. The striped regions on the figure depict obstacles (such as furniture or garbage cans) and other objects not represented in the building blueprint. 
     Additionally, some of the doors along the hallway can be open, while others are closed. The data illustrated represents conditions of normal flow of pedestrian traffic through the hallways. The corners in the map are marked with a box, and measurements are used to update the position estimate as marked with a line to the corresponding corner. 
     Based on the data illustrated, the uncertainty in the position estimate is low (max σ=0.16 m), even though the number of position update measurements is small (only 9 corners were detected, approximately 110 total measurements). For the data shown, the attitude estimate of the cane is based on over 5,000 relative orientation measurements. When the orientation error is bounded, i.e., σ ψ ≦σ ψ     0   , then the position covariance grows as: 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       ⁡ 
                       
                         ( 
                         t 
                         ) 
                       
                     
                     ≈ 
                     
                       
                         
                           
                             σ 
                             v 
                             2 
                           
                           + 
                           
                             
                               σ 
                               
                                 ψ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 0 
                               
                               2 
                             
                             ⁢ 
                             
                               V 
                               2 
                             
                             ⁢ 
                             δ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               T 
                               2 
                             
                           
                         
                         2 
                       
                       ⁢ 
                       t 
                     
                   
                   = 
                   
                     α 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     t 
                   
                 
               
               
                 
                   ( 
                   38 
                   ) 
                 
               
             
           
         
       
     
     For the data shown, δT=100 ms and α=9.8204×10 −4 . This means that for the case of direct heading odometry, the position uncertainty grows approximately linearly with time between consecutive position updates. Thus, when detecting a small number of corners, the position filter maintains a good estimate. This is corroborated by the time evolution of the trace of the position covariance; the value of the trace remains below 0.054 m2 which corresponds to approximately 0.16 m 1σ error in each direction.  FIG. 7  illustrates that trace of the position covariance verifies that the positional uncertainty remains bounded, but grows linearly with time between consecutive position updates. 
     The filter maintains consistency as the x and y components of the measurement residuals fall within the 3σ bounds of the residual covariance, as shown in  FIGS. 8A and 8B . 
     The present subject matter includes processing of data from a pair of cane-mounted sensors, and a foot-mounted pedometer involving unknown and time-varying relative coordinate transformation fused using a two-stage pose estimator. The first stage uses inertial measurements from a 3-axis gyroscope and relative orientation measurements from laser scan data to accurately estimate the attitude of the white cane. The second stage generates a pose estimate of the person holding the cane, by incorporating linear velocity measurements from the pedometer, a filtered version of the cane&#39;s yaw estimate, and corner features extracted from the laser scan data. 
       FIG. 10  illustrates method  370  according to one example. In method  370 , rotational velocity data is received at  310  and distance data is received at  320 . A processor executes an algorithm at  330  to filter the data and generate aheading estimate. At  340 ,velocity data is received and at  350 , feature data is received. At  360 , the processor generates a position estimate. 
     ALTERNATIVE EXAMPLES 
     The present subject matter can be used for path planning by suitable programming of the processor. Path planning can entail generating paths between indoor locations, as well as a haptic feedback system to give the person simple directional commands. A haptic feedback system can include piezoelectric or other vibration inducing transducers. 
     In one example, the present subject matter can be used to generate a map of an interior space or building where no map is otherwise available. 
     As used in this document, pose refers to orientation (attitude) and position of a mobile or portable platform with respect to an initial location. The platform can be attached to or carried by a user. In one example, orientation (attitude) is estimated by integrating the rotational velocities (measured by gyroscopes). 
     In various examples of the present subject matter, attitude corrections are provided intermittently from a) the lines detected by laser scanning measurement (intersection of laser scanning plane with the walls, ceiling and floor); and b) the inclinometers (or equivalently, accelerometers) that measure device tilt angle. 
     Position can be computed by integrating the distance traveled and/or velocity measurements from the pedometer with the orientation estimate. 
     Map-based localization affords the ability to intermittently provide corrections to the pose estimator. Such a system uses measurements from laser scanner (and/or camera sensor) and makes reference to any available map. 
     In one example, the present subject matter allows simultaneous localization and mapping wherein the system both constructs and uses a map of the area. 
     As used herein, path planning refers to determining and communicating a route to the user. 
     CONCLUSION 
     It is to be understood that the above description is intended to be illustrative, and not restrictive. For example, the above-described embodiments (and/or aspects thereof) may be used in combination with each other. Many other embodiments will be apparent to those of skill in the art upon reviewing the above description. The scope of the subject matter should, therefore, be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled. In the appended claims, the terms “including” and “in which” are used as the plain-English equivalents of the respective terms “comprising” and “wherein.” Also, in the following claims, the terms “including” and “comprising” are open-ended, that is, a system, device, article, or process that includes elements in addition to those listed after such a term in a claim are still deemed to fall within the scope of that claim. Moreover, in the following claims, the terms “first,” “second,” and “third,” etc. are used merely as labels, and are not intended to impose numerical requirements on their objects. 
     The Abstract of the Disclosure is provided to comply with 37 C.F.R. § 1.72(b), requiring an abstract that will allow the reader to quickly ascertain the nature of the technical disclosure. It is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims. In addition, in the foregoing Detailed Description, various features may be grouped together to streamline the disclosure. This method of disclosure is not to be interpreted as reflecting an intention that the claimed embodiments require more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive subject matter may lie in less than all features of a single disclosed embodiment. Thus the following claims are hereby incorporated into the Detailed Description, with each claim standing on its own as a separate embodiment.