(12) United States Patent
`Soehren et al.
`
`I IIIII IIIIIIII Ill lllll lllll lllll lllll lllll lllll lllll lllll 111111111111111111
`US006522266Bl
`US 6,522,266 Bl
`Feb.18,2003
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) NAVIGATION SYSTEM, METHOD AND
`SOFTWARE FOR FOOT TRAVEL
`
`(75)
`
`Inventors: Wayne A. Soehren, Wayzata, MN
`(US); Charles T. Bye, Eden Prairie,
`MN (US); Charles L. Keyes, Forest
`Lake, MN (US)
`
`(73) Assignee: Honeywell, Inc., Minneapolis, MN
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by O days.
`
`(21) Appl. No.: 09/572,238
`
`(22) Filed:
`
`May 17, 2000
`
`Int. Cl.7 ................................................ G08G 1/123
`(51)
`(52) U.S. Cl. ........................ 340/988; 600/595; 702/160
`(58) Field of Search ....................... 340/988; 73/178 R;
`377/24.2, 39; 482/3, 8, 74; 600/595; 702/97,
`160
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`1/1972 Dahlquist et al. ........... 235/105
`3,635,399 A
`3/1974 Adler et al.
`................ 340/323
`3,797,010 A
`8/1975 Griffiths et al. ............... 73/490
`3,901,086 A
`10/1977 Sherrill .......................
`364/561
`4,053,755 A
`4/1979 Griffiths et al. ............... 73/490
`4,149,417 A
`4,220,996 A * 9/1980 Searcy
`.......................
`702/160
`4,409,992 A
`10/1983 Sidorenko et al. .......... 128/782
`4,991,126 A
`2/1991 Reiter
`........................
`364/561
`5,117,301 A
`5/1992 Tsumura .....................
`359/154
`5,117,444 A
`5/1992 Sutton et al. .............. 377/24.2
`5,367,458 A
`11/1994 Roberts et al.
`........ 364/424.02
`5,485,402 A
`1/1996 Smith et al. ................ 364/566
`5,583,776 A
`12/1996 Levi et al. ..................
`364/450
`5,760,737 A
`6/1998 Brenner ......................
`342/357
`5,955,667 A
`9/1999 Fyfe
`6,064,942 A * 5/2000 Johnson et al. ............. 701/213
`6,122,960 A * 9/2000 Hutchings et al. ............ 73/493
`6,132,391 A * 10/2000 Onari et al.
`................ 600/595
`
`6,243,660 Bl * 6/2001 Hsu et al. ...................
`702/160
`6,298,314 Bl * 10/2001 Blackadar et al. .......... 702/178
`6,301,964 Bl * 10/2001 Fyfe et al. ....................
`73/510
`
`FOREIGN PATENT DOCUMENTS
`
`DE
`FR
`WO
`
`19946212
`2670004 A
`9306779 A
`
`4/2000
`6/1992
`4/1993
`
`OTHER PUBLICATIONS
`
`Aminian K et al: "Estimation of Speed and Incline of
`Walking Using Neural Network"
`IEEE Transactions on
`Instrumentation and Measurement, IEEE Inc. New York,
`US, vol. 44, No. 3, Jun. 1, 1995, pp. 743-746, xp000527554,
`ISSN: 0018-9456.
`
`(List continued on next page.)
`
`Primary Examiner-John A. Tweel
`(74) Attorney, Agent, or Firm----Schwegman, Lundberg,
`Woessner & Kluth PA
`
`(57)
`
`ABSTRACT
`
`A navigation system for mounting on a human. The navi(cid:173)
`gation system includes one or more motion sensors for
`sensing motion of the human and outputting one or more
`corresponding motion signals. An inertial processing unit
`coupled to one or more of motion sensors determines a first
`position estimate based on one or more of the corresponding
`signals from the motion sensors. A distance
`traveled is
`determined by a motion classifier coupled to one or more of
`the motion sensors, where the distance estimate is based on
`one or more of the corresponding motion signals processed
`in one or more motion models. A Kalman filter is also
`integrated into the system, where the Kalman filter receives
`the first position estimate and the distance estimate and
`provides corrective feedback signals to the inertial processor
`for the first position estimate. In an additional embodiment,
`input from a position indicator, such as a GPS, provides a
`third position estimate, and where the Kalman filter provides
`corrections to the first position estimate, the distance esti(cid:173)
`mate and parameters of the motion model being used.
`
`29 Claims, 9 Drawing Sheets
`
`400
`
`/
`
`404
`
`430
`
`I
`
`.----~~1
`I
`INERTIAL
`PROCESSING UNIT I
`~~-~~I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`CORRECTIONS J
`
`410
`,----t-~'------.r----------------L------1
`
`INERTIAL NAVIGATIONl-+.----~---------i
`MOTION SENSORS
`
`4 20
`
`MOTION
`CLASSIFIER
`
`418
`
`MAGNETIC
`SENSORS
`
`440
`
`KALMAN
`FILTER
`
`L__
`
`__
`
`_J
`
`OUTPUT
`TERMINAL
`
`IPR2020-01192
`Apple EX1042 Page 1
`
`

`

`US 6,522,266 Bl
`Page 2
`
`OIBER PUBLICATIONS
`
`In: Kalman Filtering: Theory and Application, Sorenson, H.
`W, (ed.), IEEE Press, New York,, 1-2, (1985).
`Berg, R.F., "Estimation and Prediction for Maneuvering
`Target Trajectories", IEEE Transactions on Automatic Con(cid:173)
`trol, AC-28, 303-313, (Mar. 1983).
`Bowditch, N., "American Practical Navigator An Epitome
`of Navigation", American Practical Navigator An Epitome
`of Navigation, Corrected Print-1966, 248-250, (1966).
`Cipra, B., "Engineers look to Kalman filtering for guid(cid:173)
`ance", Society for Industrial and Applied Mathematics
`News, 26, found at web address: http://www.cs.unc.edu/(cid:173)
`welch/siam_13 cipra.html, 1-4, (Aug. 1993).
`Evans, M., "Global Positioning Systems/Inertial Navigation
`Systems Integration Project", http://wwwcrasys.anu.edu.au/
`1-3,
`(Nov.
`admin/annualReports/1996-96/7-10.html,
`1996).
`Langley, R.B., "The
`Integrity of GPS", http://www.
`gpsworld. com/0699/0699innov.html, 1-9, ( c.1999).
`Leibundgut, E.G., et al., "Application of Kalman Filtering to
`Demographic Models", IEEE Transactions on Automatic
`Control, AC-28, 427-434, (Mar. 1983).
`
`Levy, L.J., "The Kalman Filter: Navigation's Integration
`Workhorse", http://www.gpsworld.com/columns/0997Innov/
`0997kalman.htm, 1-12, (c.1999).
`
`Margaria, R., "Biomechanics of Human locomotion", Bio(cid:173)
`mechanics and Energetics of Muscular Exercise In, Claren(cid:173)
`don Press, 106-124, (1976).
`
`Maybeck, P.S., "Stochastic Models, Estimation, and Con(cid:173)
`trol", Stochastic Models, Estimation, and Control, 1, Chap(cid:173)
`ter 1-Introduction, Academic Press, Inc., 1-16, (c.1979).
`
`Meijer, G.A., et al., "Methods to Assess Physical Activity
`with Special Reference to Motion Sensors and Accelerom(cid:173)
`eters", IEEE Transactions on Biomedical Engineering, 38,
`221-229, (Mar. 1991).
`
`Sorenson, H.W., "Least-squares estimation: from Gauss to
`Kalman", IEEE Spectrum, 7, 7-15, (Jul. 1970).
`
`Van Diggelen, F., "GPS Accuracy: Lies, Damn Lies, and
`Statistics",
`http://www.gpsworld.com/columns/9805in(cid:173)
`nov.html, 1-7, (c.1998).
`
`* cited by examiner
`
`IPR2020-01192
`Apple EX1042 Page 2
`
`

`

`U.S. Patent
`
`Feb.18,2003
`
`Sheet 1 of 9
`
`US 6,522,266 Bl
`
`SENSE MOTION AND NAVIGATION SIGNALS
`
`•
`•
`•
`
`DETERMINE FIRST POSITION ESTIMATE
`
`DETERMINE SECOND POSITION ESTIMATE
`
`DETERMINE CORRECTIONS TO FIRST
`
`FIG. 1
`
`SENSE MOTION AND NAVIGATION SIGNALS
`
`100
`
`,-/
`
`110
`
`,-/
`
`120
`
`,./
`
`130
`
`,-/
`
`200
`
`,-/
`
`210
`
`,-/
`
`220
`
`,-/
`
`•
`•
`•
`
`DETERMINE FIRST POSITION AND ATTITUDE ESTIMATE
`
`DETERMINE A DISTANCE TRAVELED ESTIMATE
`
`230
`DETERMINE CORRECTIONS TO THE FIRST POSITION
`AND ATTITUDE ESTIMATE AND ASSOCIATED MODELS
`
`,-/
`
`FIG. 2
`
`IPR2020-01192
`Apple EX1042 Page 3
`
`

`

`U.S. Patent
`
`Feb. 18, 2003
`
`Sheet 2 of 9
`
`US 6,522,266 Bl
`
`SENSE MOTION AND NAVIGATION SIGNALS
`
`t
`
`300
`
`,-/
`
`310
`
`,-/
`
`DETERMINE FIRST POSITION AND ATTITUDE ESTIMATE
`
`t
`
`320
`
`,-/
`
`DETERMINE A DISTANCE TRAVELED ESTIMATE
`
`t
`
`SENSE RF SIGNALS ( GPS)
`
`t
`
`330
`
`,-/
`
`340
`
`,-/
`
`DETERMINE A THIRD POSITION ESTIMATE
`
`350
`DETERMINE CORRECTIONS TO THE FIRST POSITION AND
`ATTITUDE ESTIMATE AND THE MODEL USED TO GENERATE
`THE DISTANCE TRAVELED ESTIMATE
`
`,-/
`
`•
`
`FIG. 3
`
`IPR2020-01192
`Apple EX1042 Page 4
`
`

`

`i,-
`~
`O'I
`O'I
`'N
`N
`N
`1J.
`O'I
`rJ'l
`e
`
`\C
`0 ....,
`~ ....
`'JJ. =(cid:173) ~
`
`~
`
`8
`C
`N
`~CIO
`"'""
`?'
`~
`"'!"j
`
`~ = .....
`~ .....
`~
`•
`r:JJ.
`d •
`
`FIG. 4
`
`TERMINAL
`OUTPUT
`
`460
`
`L
`
`_J
`
`... ______________
`
`FILTER I CORRECTIONS
`KALMAN
`
`J
`
`440
`
`,J
`
`PROCESSING UNIT
`
`•
`
`I
`I
`
`INERTIAL
`
`430
`
`------,
`
`...c. 404
`
`CLASSIFIER
`
`MOTION
`
`420
`
`-_____________
`
`-
`
`400
`
`/
`
`410
`
`~
`
`INPUT
`MOTION
`
`L-----~--
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`SENSORS
`MAGNETIC
`
`418
`
`,J
`
`I
`MOTION SENSORS
`INERTIAL NAVIGATION
`I
`I
`I
`r -
`
`414
`
`,-/
`
`I
`
`IPR2020-01192
`Apple EX1042 Page 5
`
`

`

`i,-
`~
`O'I
`O'I
`'N
`N
`N
`1J.
`O'I
`rJ'J.
`
`e
`
`\C
`0 ....,
`~ ....
`'JJ. =(cid:173) ~
`
`,i;;..
`
`C 8
`N
`~CIO
`"'""
`?'
`~
`"'!"j
`
`~ = .....
`~ .....
`~
`•
`r:JJ.
`d •
`
`FIG. 5
`
`TERMINAL
`OUTPUT
`
`460
`
`r'
`
`•
`
`ALTIMETER
`
`520
`
`r'
`
`d-GPS
`
`510
`
`L
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`FILTER CORRECTIONS
`KALMAN
`
`J
`
`_________
`
`___J---------~
`
`._ __
`
`L _______
`I
`I CORRECTIONS
`L____
`
`H-t------+1------'
`
`440
`
`i
`
`CLASSIFIER
`
`MOTION
`
`420
`
`I
`I
`I
`I
`I
`I
`I
`MOTION SENSORS
`INERTIAL NAVIGATION
`I
`
`418
`
`,.J
`
`SENSORS
`MAGNETIC
`
`PROCESSING UNIT I
`I
`I
`430 I
`
`INERTIAL
`
`,-----..c;__-
`
`'---.-------,r---11
`
`404
`
`500
`
`/
`
`:
`,----------------~------,
`
`414
`
`r'
`
`•
`
`410
`
`,.J
`
`INPUT
`MOTION
`
`IPR2020-01192
`Apple EX1042 Page 6
`
`

`

`U.S. Patent
`
`Feb.18,2003
`
`Sheet 5 of 9
`
`US 6,522,266 Bl
`
`SENSE MOTION SIGNALS
`
`COMPARE MOTION SIGNALS TO STORED MOTION DATA
`
`600
`
`,-I
`
`610
`
`r'
`
`620
`
`r'
`
`'
`•
`
`IDENTIFY THE TYPE OF HUMAN
`MOTION BASED ON THE COMPARISON
`
`FIG. 6
`
`700
`
`720
`
`,..I
`
`730
`
`,..I
`
`FIRST
`SENSORS
`
`SECOND
`SENSORS
`
`710
`
`,J
`
`PROCESSOR
`
`FIG. 7
`
`IPR2020-01192
`Apple EX1042 Page 7
`
`

`

`U.S. Patent
`
`Feb.18,2003
`
`Sheet 6 of 9
`
`US 6,522,266 Bl
`
`WALKING
`FORWARDS
`FIG. BA
`
`FIG. 88
`
`40
`
`20
`
`0
`
`10
`
`0
`
`FIG. BC
`
`50
`
`0
`
`0
`
`FIG. 80
`
`BRIDGE
`(5% SLOPE)
`FIG. BE
`
`GOLF COURSE
`(10% SLOPE)
`FIG. BF
`
`IPR2020-01192
`Apple EX1042 Page 8
`
`

`

`U.S. Patent
`
`Feb. 18,2003
`
`Sheet 7 of 9
`
`US 6,522,266 Bl
`
`0
`
`STEEP BANK
`(20% SLOPE)
`FIG. BG
`
`5
`
`0
`
`20
`
`10
`
`0
`
`DOWN)
`
`FIG.
`
`FIG. 81
`
`FIG.
`
`IPR2020-01192
`Apple EX1042 Page 9
`
`

`

`U.S. Patent
`
`Feb.18,2003
`
`Sheet 8 of 9
`
`US 6,522,266 Bl
`
`40
`
`20
`
`0
`
`20
`
`10
`
`0
`
`0
`
`FIG. 9A
`
`FIG. 9C
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`FIG. 98
`
`FIG. 90
`
`20
`
`10
`
`0
`
`50
`
`0
`
`10
`
`0
`
`BRIDGE
`(5% SLOPE)
`FIG. 9E
`
`GOLF COURSE
`( 10% SLOPE)
`FIG. 9F
`
`IPR2020-01192
`Apple EX1042 Page 10
`
`

`

`U.S. Patent
`
`Feb.18,2003
`
`Sheet 9 of 9
`
`US 6,522,266 Bl
`
`/
`
`/
`
`/
`
`/
`
`10
`
`/
`
`/
`
`5
`
`/
`
`/
`
`STAIRS
`(UP & DOWN)
`FIG. 9H
`
`STEEP BANK
`(20% SLOPE)
`FIG. 9G
`
`0
`
`10
`
`5
`
`0
`
`20
`
`0
`
`100
`
`50
`
`0
`
`FIG. 91
`
`FIG.
`
`IPR2020-01192
`Apple EX1042 Page 11
`
`

`

`US 6,522,266 Bl
`
`1
`NAVIGATION SYSTEM, METHOD AND
`SOFTWARE FOR FOOT TRAVEL
`
`TECHNICAL FIELD
`
`The present invention relates to navigation systems, and
`in particular the invention relates to personal navigation
`systems.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`2
`unobstructed view of the sky, so they are used only outdoors
`and they often do not perform well within forested areas or
`near tall buildings. In these situations, an individual using a
`GPS is without an estimate of both distance traveled and
`5 position. Therefore, a need exists for a system that integrates
`the best navigation features of known navigation techniques
`to provide an individual with estimates of position and
`distance traveled, regardless of where they might travel.
`SUMMARY OF THE INVENTION
`The present invention provides solutions to the above(cid:173)
`identified problems.
`In an exemplary embodiment,
`the
`present invention integrates traditional inertial navigation
`and independent measurements of distance
`traveled
`to
`15 achieve optimal geolocation performance in the absence of
`GPS or other radio-frequency positioning aids. The present
`invention also integrates the use of GPS to control naviga(cid:173)
`tion error growth. However, when GPS signals are jammed
`or unavailable, the present system still provides a useful
`level of navigation performance.
`The expected performance characteristics of reasonably
`priced INS sensors, in particular the gyroscopes, have little
`practical value for long-term navigation applications (>60
`seconds) using inertial navigation algorithms alone. Dead
`25 reckoning techniques provide a better long-term solution;
`however, for best performance,
`these techniques require
`motion that is predictable (i.e., nearly constant step size and
`in a fixed direction relative to body orientation). Unusual
`motions (relative to walking) such as sidestepping are not
`30 handled and can cause significant errors if the unusual
`motion is used for an extended period of time. Integrating
`traditional
`inertial navigation and independent measure(cid:173)
`ments of distance traveled offers a solution to achieve
`optimal geolocation performance in the absence of GPS or
`35 other radio-frequency positioning aids.
`In one exemplary embodiment, the invention provides a
`navigation system for mounting on a human. The navigation
`system includes one or more motion sensors for sensing
`motion of the human and outputting one or more corre(cid:173)
`sponding motion signals. An inertial processing unit coupled
`to one or more of motion sensors determines a first position
`estimate based on one or more of the corresponding signals
`from the motion sensors. A distance traveled is determined
`by a motion classifier coupled to one or more of the motion
`sensors, where the distance estimate is based on one or more
`of the corresponding motion signals. In one embodiment, the
`motion classifier includes a step-distance model and uses the
`step-distance model with the motion signals to determine the
`distance estimate.
`A Kalman filter is also integrated into the system, where
`the Kalman filter receives the first position estimate and the
`distance estimate and provides corrective feedback signals
`to the inertial processor for the first position estimate. In one
`embodiment, the Kalman filter determines the corrective
`55 feedback signals based on the first position estimate and the
`distance estimate and past and present values of the motion
`signals. In an additional embodiment, input from a position
`indicator, such as a GPS, provides a third position estimate,
`and where the Kalman filter provides corrections to the first
`60 position estimate and the distance estimate using the third
`position estimate. The Kalman filter also provides correc(cid:173)
`tions (e.g., modifications) to parameters of the motion model
`based on the errors
`in the distance estimate.
`In one
`embodiment, the modifications to the model parameters are
`65 specific to one or more humans.
`The present invention also provides for a motion classi(cid:173)
`fication system. The motion classification system includes
`
`20
`
`Reliable navigation systems have always been essential
`for estimating both distance traveled and position. Some of
`the earliest type of navigation systems relied upon naviga(cid:173)
`tion by stars, or celestial navigation. Prior to the develop(cid:173)
`ment of celestial navigation, navigation was done by
`"deduced" (or "dead") reckoning. In dead-reckoning,
`the
`navigator finds his position by measuring the course and
`distance he has moved from some known point. Starting
`from a known point the navigator measures out his course
`and distance from that point. Each ending position would be
`the starting point for the course-and-distance measurement.
`In order for this method to work, the navigator needs a
`way to measure his course, and a way to measure the
`distance moved. Course is measured by a magnetic compass.
`Distance is determined by a time and speed calculation: the
`navigator multiplied the speed of travel by the time traveled
`to get the distance. This navigation system, however, is
`highly prone to errors, which when compounded can lead to
`highly inaccurate position and distance estimates.
`An example of a more advanced navigation system is an
`inertial navigation system (INS). The basic INS consists of
`gyroscopes, accelerometers, a navigation computer, and a
`clock. Gyroscopes are instruments that sense angular rate.
`They are used to give the orientation of an object (for
`example: angles of roll, pitch, and yaw of an airplane).
`Accelerometers sense a linear change in rate (acceleration)
`along a given axis.
`In a typical INS, there are three mutually orthogonal
`gyroscopes and three mutually orthogonal accelerometers. 40
`This accelerometer configuration will give three orthogonal
`acceleration components which can be vectorially summed.
`Combining the gyroscope-sensed orientation
`information
`with the summed accelerometer outputs yields the INS's
`total acceleration in 3D space. At each time-step of the 45
`system's clock, the navigation computer time integrates this
`quantity once to get the body's velocity vector. The velocity
`vector is then time integrated, yielding the position vector.
`These steps are continuously iterated throughout the navi(cid:173)
`gation process.
`Global Positioning System (GPS) is one of the most
`recent developments
`in navigation technology. GPS pro(cid:173)
`vides highly accurate estimates of position and distance
`traveled. GPS uses satellites to transmit signals to receivers
`on the ground. Each GPS satellite transmits data that indi(cid:173)
`cates its location and the current time. All GPS satellites
`synchronize operations so that these repeating signals are
`transmitted at the same instant. The signals, moving at the
`speed of light, arrive at a GPS receiver at slightly different
`times because some satellites are farther away than others.
`The distance to the GPS satellites can be determined by
`estimating the amount of time it takes for their signals to
`reach the receiver. When the receiver estimates the distance
`to at least four GPS satellites, it can calculate its position in
`three dimensions.
`When available, positioning aids such as GPS control
`navigation error growth. GPS receivers, however, require an
`
`50
`
`IPR2020-01192
`Apple EX1042 Page 12
`
`

`

`US 6,522,266 Bl
`
`3
`first sensors coupled to a processor to provide a first type of
`motion information, and second sensors coupled to the
`processor to provide a second type of motion information. In
`one exemplary embodiment, the first sensors are a triad of
`inertial gyroscopes and the second sensors are a triad of 5
`accelerometers. A neural-network is then employed to ana(cid:173)
`lyze the first and second types of motion information to
`identify a type of human motion. The neural-network is used
`to identify the type of human motion as either walking
`forward, walking backwards, running, walking down or up 10
`an incline, walking up or down stairs, walking sideways,
`crawling, turning left, turning right, stationary, or unclassi(cid:173)
`fiable. Once identified, motion models specific for the
`motion type are used to estimate a distance traveled. The
`distance traveled estimate is then used with the navigation 15
`system for mounting on the human to provide distance
`traveled and location information as described above.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows an exemplary method of the present inven(cid:173)
`tion.
`FIG. 2 shows an exemplary method of the present inven-
`tion.
`FIG. 3 shows an exemplary method of the present inven- 25
`tion.
`FIG. 4 shows a system of the present invention.
`FIG. 5 shows a system of the present invention.
`FIG. 6 shows an exemplary method of the present inven(cid:173)
`tion.
`FIG. 7 shows a system of the present invention.
`FIG. 8 shows plots of neurons representing different types
`of human motion.
`FIG. 9 shows plots of neurons representing different types
`of human motion.
`
`4
`than inertial
`can provide better navigation performance
`navigation over longer periods of time, require the indi(cid:173)
`vidual to move predictably (i.e., nearly constant step size
`and in a fixed direction relative to body orientation) for
`accurate
`geolocation
`and navigation
`information.
`Unfortunately, the user does not always move in a predict-
`able manner and unusual motions (relative to walking), such
`as sidestepping, crawling, running, climbing, etc. are not
`correctly interpreted by conventional dead reckoning tech(cid:173)
`niques. As a result, significant errors accumulate, eroding
`the accuracy of the conventional dead-reckoning systems.
`GPS is one possible means of providing accurate geolo-
`cation and distance traveled information. However, GPS,
`and other RF location aids, are not always available because
`of satellite or transmitter outages, obstacles to radio-signal
`transmissions, and so forth. This leads to an unacceptable
`situation in which the individual's position and distance
`traveled are not accurately accounted for due to the short(cid:173)
`comings of using either the inertial navigation or traditional
`20 dead-reckoning systems alone.
`An advantage of the exemplary system is the ability to
`continue to provide accurate estimates of geolocation and
`distance traveled even when GPS, or other RF positioning
`aids, are not available. The exemplary system solves these,
`and other, problems by integrating inertial navigation and
`motion-model algorithms using a Kalman filter for estimat-
`ing the geolocation of the user in the absence of GPS or other
`radio-frequency position aids. The exemplary system also
`allows for user-specific enhancements and changes to the
`30 motion classification model when GPS positioning is used.
`FIG. 1 shows an exemplary method of estimating foot(cid:173)
`travel position according to the present invention. At 100,
`one or more motion signals are sensed through one or more
`motion sensors, and one or more navigation signals are
`35 sensed through one or more navigation sensors for providing
`motion data about a user. In one embodiment, the one or
`more motion sensors include accelerometers and gyroscopes
`as are used in inertial navigation systems. In an additional
`embodiment, the one or more motion sensors can further
`40 include magnetic sensors and step sensors as are used in
`dead reckoning systems.
`At 110, a first position estimate for the foot-travel position
`is determined from the one or more motion signals. In one
`45 embodiment, the first position estimate includes an estimate
`of the individual's geolocation, along with the distance
`traveled, as derived from signals from the accelerometers
`and gyroscopes as used in inertial navigation systems.
`At 120, a second position estimate for the foot-travel
`50 position is determined from the one or more navigation
`signals. In one embodiment, the second position estimate
`includes an estimate of the individual's geolocation, along
`with the distance traveled, from the magnetic sensors and
`step sensors as are used in dead reckoning systems.
`At 130, the first position estimate and the second position
`estimate are then integrated to determine corrections to the
`first position estimate. In one embodiment, the first and the
`second position estimates of foot-travel are determined by
`using past and present values of either the navigation signals
`60 or the motion signals. For example, a Kalman filter is used
`to provide the corrections to the first position estimate. The
`first estimate then represents an optimal system solution.
`Either the first or the second position estimate of geolocation
`and distance
`traveled
`is then displayed
`in a human-
`65 perceptible form, such as on a display terminal.
`FIG. 2 shows a second exemplary method of estimating
`foot-travel position according to the present invention. At
`
`DETAILED DESCRIPTION
`
`An exemplary navigation/geolocation system for an indi(cid:173)
`vidual
`is disclosed. The exemplary
`system provides
`enhanced navigation and position estimates for users trav(cid:173)
`eling on foot. The exemplary system uses inertial navigation
`information gathered from the individual, a motion algo(cid:173)
`rithm which identifies the motion type of the individual ( e.g.,
`walking) along with Kalman filtering to estimate travel
`distance and position. More particularly,
`the exemplary
`system compares the data from the motion algorithm and an
`inertial navigation processing unit using the Kalman filter to
`determine reliable travel distance and position information.
`This information is then used to estimate the individual's
`position and distance traveled. In one embodiment,
`the
`present
`system
`is incorporated
`into a self-contained
`apparatus, which is worn by the user.
`The exemplary system can also incorporate information 55
`gathered from a global positioning system (GPS) or other
`radio frequency positioning aids. GPS provides superior
`position and distance traveled information as compared to
`either the inertial navigation processing unit or the motion
`model algorithm. The exemplary system uses the additional
`GPS input to correct estimates of distance and position from
`the inertial navigation processing unit and modify
`the
`motion model parameters to maintain optimal performance.
`Small
`low-cost
`inertial sensors (i.e gyroscopes and
`accelerometers) make the standard strapdown inertial navi(cid:173)
`gation algorithms useful for only short periods of time ( <60
`seconds). Conventional dead-reckoning
`techniques, which
`
`IPR2020-01192
`Apple EX1042 Page 13
`
`

`

`US 6,522,266 Bl
`
`5
`200, one or more motion signals are sensed through one or
`more motion sensors, and one or more navigation signals are
`sensed through one or more navigation sensors for providing
`motion data about a user. In one embodiment, the one or
`more motion sensors include accelerometers, gyroscopes,
`and magnetic sensors as are used in inertial navigation
`and/or dead reckoning systems.
`At 210, a first position and attitude estimate for the
`foot-travel position is determined from the one or more
`motion signals. In one embodiment, the first position esti- 10
`mate includes an estimate of the individual's geolocation
`and attitude, along with the distance traveled, derived from
`signals from the accelerometers and gyroscopes used m
`inertial navigation system.
`At 220, a distance traveled estimate for the user is 15
`determined from the one or more navigation signals. In one
`embodiment, determining the distance traveled estimate is
`from a motion model for the type of motion being performed
`and an estimate of step frequency.
`At 230, the first position and attitude estimate, the dis- 20
`tance traveled estimate, and heading determined from the
`magnetic sensors are then integrated to determine correc(cid:173)
`tions to the first position and attitude estimate. In one
`embodiment, the distance traveled and magnetic heading are
`to equivalent values generated from the first 25
`compared
`position and attitude estimates to generate Kalman filter
`measurements. The Kalman filter is used to provide the
`corrections to the first position and attitude estimate. The
`first estimate then represents the optimal system solution.
`The first position estimate of geolocation and distance 30
`traveled is then displayed in a human-perceptible form, such
`as on a display terminal.
`FIG. 3 shows an additional exemplary method of esti(cid:173)
`mating foot-travel position according to the present inven-
`tion. At 300, one or more motion signals are sensed through
`one or more motion sensors, and one or more navigation
`signals are sensed through one or more navigation sensors
`for providing motion data about a user. In one embodiment,
`the one or more motion sensors include accelerometers,
`gyroscopes, and magnetic sensors as are used in inertial
`navigation and/or dead reckoning systems.
`At 310, a first position and attitude estimate for the
`foot-travel position is determined from the one or more
`motion signals. In one embodiment, the first position esti- 45
`mate includes an estimate of the individual's geolocation
`and attitude, along with the distance traveled as derived from
`an inertial navigation system.
`At 320, a distance traveled estimate for the user is
`determined from the one or more navigation signals. In one 50
`example, this is determined from determining both the
`motion class of the step being taken and the frequency of the
`steps.
`At 330 one or more RF signals are sensed through one or
`more RF antennas. In one embodiment,
`the RF signals 55
`emanate from the GPS satellite constellation.
`At 340, a third position estimate is determined from a
`position indicator. In one embodiment, the position indicator
`is a GPS receiver.
`At 350, differences between the first position estimate and
`the third position estimate are then taken and used by a
`Kalman filter to determine and provide corrections to the
`first position and attitude estimate and the model used to
`traveled estimate at 320. In one
`generate
`the distance
`embodiment, a difference between the first position estimate
`and the third position estimate is taken and used by the
`Kalman filter to identify errors in the first position estimate.
`
`6
`The parameters of the motion model (used to estimate
`distance traveled) are then modified based on the errors in
`the first position estimate. The first estimate then represents
`the optimal system solution. The first and/or the third
`5 position estimate of geolocation and distance traveled is then
`displayed in a human-perceptible form, such as on a display
`terminal.
`FIG. 4 shows an exemplary navigation system 400 for
`mounting on a human according to the present invention.
`The system 400 includes a computer or processor 404
`having one or more motion (or navigation) sensors 410 for
`sensing motion of the human and outputting one or more
`corresponding motion
`( or navigation)
`signals.
`In one
`example, the sensors 410 include an inertial navigation
`motion sensor 414 and magnetic sensors 418.
`The system 400 further includes a motion classifier 420,
`where the motion classifier 420 is coupled to one or more of
`the navigation sensors and the motion sensors 410. The
`motion classifier 420 uses the signals from the sensors 410
`to determine a distance estimate. The motion classifier 420
`implements an algorithm, which models step distance. In the
`exemplary system, a linear relationship between step size
`and walking speed that is tailored to the individual user is
`used. One example of this linear relationship is found in
`Biomechanics and Energetics of Muscular Exercise, by
`Rodolfo Margaria (Chapter 3, pages 107-124. Oxford: Clar-
`endon Press 1976)
`In one example, the magnetic sensors 418 and the accel(cid:173)
`erometers of the inertial navigation sensors 414 are used to
`estimate step frequency and direction. In one embodiment,
`the magnetic sensors 418 consist of three magnetic sensors
`mounted orthogonally. Distance traveled and direction of
`travel are determined using both the frequency of step (i.e.,
`number of steps counted per unit time) along with the
`heading of the steps. The motion classifier 420 then takes the
`estimated step length, the frequency of steps, and the motion
`direction for the steps, and calculates the distance traveled
`estimate.
`The system 400 further includes an inertial processing
`unit 430 coupled to the motion/navigation sensors 410. The
`inertial processing unit 430 uses the signals from the one or
`more navigation sensors and the motion sensors 410 to
`determine the first position estimate. The inertial navigation
`sensors 414 includes a triad of accelerometers and a triad of
`gyroscopes that provide the navigation signals of orthogonal
`movement and direction in three dimensions to the inertial
`processing unit 430. The inertial processing unit 430 then
`processes the signals according to known techniques to
`provide the first position estimate and the attitude estimate.
`The first position and attitude estimates and distance trav-
`eled estimate are then used in determining corrections that
`are applied back to the first position and attitude estimates.
`In the exemplary system 400, as motion and direction are
`sensed by the magnetic sensors 418 and the inertial navi(cid:173)
`gation sensors 414 (e.g., when
`the individual moves)
`samples of data are taken from the sensors at a predeter(cid:173)
`mined rate. In one embodiment, the sensors of the inertial
`navigation sensors 414 are sampled at a rate of 100 samples/
`60 second, where measurements are taken on the rates on the
`three axes and the acceleration on the three axes. The
`sampled data is then supplied to both the inertial processing
`unit 430 and the motion classifier 420. The inertial process(cid:173)
`ing unit 430 processes the data with a navigation algorithm
`65 to determine the first position estimate, which can include
`both direction and heading and the distance moved in that
`direction.
`
`35
`
`40
`
`IPR2020-01192
`Apple EX1042 Page 14
`
`

`

`US 6,522,266 Bl
`
`7
`In the exemplary system, data samples supplied to the
`motion classifier 420 are analyzed for artifacts indicative of
`motion, such as peaks ex