Probabilistic reverse geocoding

• US 8,396,658 B2
• Filed: 10/06/2009
• Issued: 03/12/2013
• Est. Priority Date: 10/06/2008
• Status: Expired due to Fees

• Current Assignee: TeleCommunication Systems Inc (Comtech Telecommunications Corporation)
• Original Assignee: TeleCommunication Systems Inc (Comtech Telecommunications Corporation)
• Inventors: Barcklay, Bob, Hahn, John, Tsurutome, Kevin
• Primary Examiner(s): Jayne, Darnell
• Assistant Examiner(s): Varghese, Sasha T
• Application Number:
  US12/588,143
• Publication Number:
  US 20100088019A1
• Time in Patent Office: 1,253 Days
• Field of Search: 701/411, 701/412, 701/416, 701/417, 701/428, 701/431, 701/433, 701/491, 701/526, 701/541
• US Class Current: 701/417
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents

Abstract

The accuracy of a reverse geocode for a GPS fix in a mobile phone navigation device is improved significantly by considering together the user'"'"'s last known location on an original route, the elapsed time between the last known location on the original route and the latest GPS fix, and the likelihood that the user could have traveled from the last known location on the original route to one of numerous candidate locations (generated from the reverse geocode) in the elapsed time. The navigation server relies only on a GPS fix, timestamps, and a back-end routing database to provide improved or superior accuracy of reverse geocoding a GPS fix (selection of a point on a road) when a relevant user has deviated from the intended route. The reverse geocoding allows for accurate and functional re-routing capabilities.

Claims

1. A method of providing an accurate location to a user'"'"'s wireless navigation device in a congested area when in an off-route condition, comprising:

obtaining a latest off-route location fix of a user'"'"'s wireless navigation device;

obtaining a last known on-route location of said user'"'"'s wireless navigation device;

determining an elapsed time between said last known on-route location and said latest off-route location fix;

performing a reverse geocode on said latest off-route location fix based on said elapsed time, resulting in a plurality of potential location candidates;

determining an estimated time of travel from said last known on-route location to each of said plurality of potential location candidates; and

mapping as a current location of said user'"'"'s wireless navigation device one of said plurality of potential location candidates having said estimated time of travel time closest to said elapsed time.

2. The method of providing an accurate location to a user'"'"'s wireless navigation device in a congested area when in an off-route condition according to claim 1, wherein:

said latest off-route location fix is a global positioning system (GPS) fix.

3. The method of providing an accurate location to a user'"'"'s wireless navigation device in a congested area when in an off-route condition according to claim 1, further comprising:

calculating a new route from said current location to an original destination.

4. The method of providing an accurate location to a user'"'"'s wireless navigation device in a congested area when in an off-route condition according to claim 1, wherein:

said user'"'"'s wireless navigation device is portable.

5. The method of providing an accurate location to a user'"'"'s wireless navigation device in a congested area when in an off-route condition according to claim 1, wherein:

said user'"'"'s wireless navigation device is a wireless phone.

6. A method of providing navigation server-based support for a user'"'"'s wireless navigation device, comprising:

considering together a user'"'"'s wireless navigation device'"'"'s last known on-route location, a latest off-route GPS fix of said user'"'"'s wireless navigation device, and an elapsed time between said last known on-route location and said latest off-route GPS fix; and

performing a reverse geocode on said latest off-route GPS fix based on said elapsed time, resulting in a plurality of potential location candidates;

determining a likelihood that said user'"'"'s wireless navigation device could have travelled from said last known on-route location to each of said plurality of potential location candidates generated from performing said reverse geocode;

determining an estimated time of travel from said last known on-route location to each of said plurality of potential location candidates; and

providing mapping information based on a current location of said user'"'"'s wireless navigation device being determined as being one of said plurality of potential location candidates having an estimated time of travel closest to said elapsed time.

7. The method of providing navigation server-based support for a user'"'"'s wireless navigation device according to claim 6, further comprising:

calculating a new route from said current location to an original destination.

8. The method of providing navigation server-based support for a user'"'"'s wireless navigation device according to claim 6, wherein:

said user'"'"'s wireless navigation device is portable.

9. The method of providing navigation server-based support for a user'"'"'s wireless navigation device according to claim 6, wherein:

said user'"'"'s wireless navigation device is a wireless phone.