Systems and methods for estimating initial heading at start-up of navigation

• US 10,324,197 B1
• Filed: 11/13/2018
• Issued: 06/18/2019
• Est. Priority Date: 11/13/2018
• Status: Active Grant

• Current Assignee: Pointr Limited
• Original Assignee: Pointr Limited
• Inventors: Akpinar, Ismail Ege, Isik, Sinan, Tunca, Can, Akpinar, Mehmet Can
• Primary Examiner(s): Henson, Mischita L
• Application Number:
  US16/189,520
• Time in Patent Office: 217 Days
• CPC Class Codes: G01C 21/16 by integrating acceleration or speed, i.e. inertial navigation
• CPC Class Codes: G01C 21/1654 with electromagnetic compass
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 19/53 Determining attitude
• CPC Class Codes: G01S 5/017 Detecting state or type of motion
• CPC Class Codes: G01S 5/0264 at least one of the systems being a non-radio wave positioning system
• CPC Class Codes: G01S 5/0294 Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering

Abstract

Estimating initial heading at start-up of navigation. At least some of the example embodiments are computer-implemented methods including: spawning a plurality of clone processes, each clone process given an identical location and speed, and each clone process given a unique direction; calculating, by each clone process, a respective position at the end of a frame period; terminating clone processes whose position at the end of the frame period is outside a predetermined threshold, the terminating results in remaining clone processes; and determining the heading of the mobile device from the remaining clone processes.

Claims

1. A computer-implemented method of determining a heading of a mobile device, comprising:

spawning a plurality of clone processes, each clone process of the plurality of clone processes being an Extended Kalman filter, each clone process given an identical location and speed, and each clone process given a unique direction;

calculating, by each clone process, a respective position at the end of a frame period;

terminating clone processes whose position at the end of the frame period is outside a predetermined threshold, the terminating results in remaining clone processes; and

determining the heading of the mobile device from the remaining clone processes.

2. The computer-implemented method of claim 1 wherein spawning the plurality of clone processes further comprises spawning the plurality of clone processes such that the unique directions span a range of headings greater than 90 degrees.

3. The computer-implemented method of claim 2 wherein spawning the plurality of clone processes further comprises spawning such that the unique directions are evenly spaced within the range of headings.

4. The computer-implemented method of claim 2 wherein spawning the plurality of clone processes further comprises refraining from spawning clone processes with unique directions heading toward one or more obstacles.

5. The computer-implemented method of claim 1 wherein spawning the plurality of clone processes further comprises spawning the plurality of clone processes such that the unique directions span 360 degrees.

6. The computer-implemented method of claim 1 wherein calculating, by each clone process, the respective position further comprises, a plurality of times during each frame period:

receiving, by each clone process, updated speed and a value indicative of change of direction; and

calculating, by each clone process, the respective position using the updated speed and the value indicative of change of direction.

7. The computer-implemented method of claim 1 wherein terminating clone processes further comprises, for each clone process:

receiving an actual position, and calculating a separation between the respective position and the actual position; and

terminating each clone process whose separation is greater than the predetermined threshold being a separation threshold.

8. The computer-implemented method of claim 1 wherein terminating clone processes further comprises, for each clone process:

determining a gap between the respective position and an obstacle; and

terminating each clone process whose gap is less than the predetermined threshold being a gap threshold.

9. The computer-implemented method of claim 1 wherein determining the heading of the mobile device further comprises:

calculating an average vector using the unique direction from each of the remaining clone processes; and

using a heading of the average vector as the heading of the mobile device.

10. The computer-implemented method of claim 1 further comprising, prior to determining the heading:

calculating an average vector using the unique direction from each of the remaining clone processes; and

repeating the calculating and terminating until an attribute of the average vector meets or exceeds a convergence threshold.

11. The computer-implemented method of claim 10 wherein repeating the calculating and terminating further comprises repeating the calculating and terminating until a magnitude of the average vector meets or exceeds a magnitude threshold.

12. The computer-implemented method of claim 1 further comprising, prior to spawning the clone processes:

reading an accelerometer of the mobile device, the reading creates accelerometer data;

estimating a stride length of a person carrying the mobile device using the accelerometer data;

determining the speed based on the stride length.

13. The computer-implemented method of claim 12 further comprising at least one selected from a group comprising:

modifying the stride length based on data regarding the person carrying the mobile device;

modifying the stride length based on data regarding a venue within which the person and mobile device are moving;

modifying the stride length based on data received from a beacon device within the venue.

14. A hand-held computing device comprising:

a processor;

a memory coupled to the processor;

a display device electrically coupled to the processor;

an accelerometer electrically coupled to the processor;

a wireless communication system electrically coupled to the processor, the wireless communication system configured to receive location information wirelessly from beacons external to the hand-held computing device;

wherein the memory stores a program that, when executed by the processor, causes the processor to;

spawn a plurality of clone processes, each clone process of the plurality of clone processes being a Kalman filter, each clone process given an identical location and speed, and each clone process given a unique direction;

calculate, by each clone process, a respective position at the end of a frame period;

terminate clone processes whose position at the end of the frame period is outside a predetermined threshold, the terminating results in remaining clone processes; and

determine the heading of the mobile device from the remaining clone processes;

provide an indication of direction to travel to a user of the hand-held device by way of the display device.

15. The hand-held computing device of claim 14 wherein when the processor spawns the plurality of clone processes, the program causes the processor to spawn the plurality of clone processes such that the unique directions span a range of headings greater than 90 degrees.

16. The hand-held computing device of claim 15 wherein when the processor spawns the plurality of clone processes, the program causes the processor to spawn such that the unique directions are evenly spaced within the range of headings.

17. The hand-held computing device of claim 15 wherein when the processor spawns the plurality of clone processes, the program causes the processor to refrain from spawning clone processes with unique directions heading toward one or more obstacles.

18. The hand-held computing device of claim 14 wherein when the processor spawns the plurality of clone processes, the program causes the processor to spawn the plurality of clone processes such that the unique directions span 360 degrees.

19. The hand-held computing device of claim 14 wherein when the processor calculates, for y each clone process, the respective position the program further causes the processor to, a plurality of times during each frame period:

calculate updated speed and a value indicative of change of direction; and

calculate, for each clone process, the respective position using the updated speed and the value indicative of change of direction.

20. The hand-held computing device of claim 14 wherein when the processor terminates clone processes, the program further causes the processor to:

determine an actual position using the wireless communication system;

calculate, for each clone process, a separation between the respective position and the actual position; and

terminate each clone process whose separation is greater than the predetermined threshold being a separation threshold.

21. The hand-held computing device of claim 14 wherein the processor terminates the clone processes, the program further causes the processor to, for each clone process:

determine a gap between the respective position and an obstacle; and

terminate each clone process whose gap is less than the predetermined threshold being a gap threshold.

22. The hand-held computing device of claim 14 wherein when the processor determines the heading of the mobile device, the program further causes the processor to:

calculate an average vector using the unique heading from each of the remaining clone processes; and

use a heading of the average vector as the heading of the hand-held computing device.

23. The hand-held computing device of claim 14 wherein the program further causes the processor to, prior to the determination of the heading:

calculate an average vector using the unique heading from each of the remaining clone processes; and

repeat the calculation of the respective positions and the termination until an attribute of the average vector meets or exceeds convergence threshold.

24. The hand-held computing device of claim 14 wherein prior to when the processor spawns the clone processes, the program further causes the processor to:

read the accelerometer, the reading creates accelerometer data;

estimate a stride length of a person carrying the hand-held computing device using the accelerometer data; and

determining the speed based on the stride length.

25. The hand-held computing device of claim 24 wherein the program further causes the processor to at least one selected from a group comprising:

modify the stride length based on data regarding the person carrying the hand-held computing device;

modify the stride length based on data regarding a venue within which the person and hand-held computing device are moving; and

modify the stride length based on data received from a beacon device within the venue.