Rerouting in Vehicle Navigation Systems

• US 20080051995A1
• Filed: 08/23/2007
• Published: 02/28/2008
• Est. Priority Date: 08/25/2006
• Status: Active Grant

• Current Assignee: MiTAC International Corporation (MiTAC Holdings Corp.)
• Original Assignee: Magellan Navigation Incorporated (MiTAC Holdings Corp.)
• Inventors: Upparapalli, Karunanidhi, LOKSHIN, Anatole M.
• Granted Patent: US 7,945,386 B2
• Time in Patent Office: Days
• US Class Current: 701/210
• 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
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data

Abstract

A navigation device includes a processor, a map information storage medium storing map information, a position determining module configured to determine a current location, a velocity and direction of travel of a vehicle, and determine whether the current position indicates a deviation from an original route to a final destination. Further included is a routing module configured to determine an original route from a starting position to a destination, and at least one reroute from the current location to the destination, wherein the reroute includes a restoration route from the current location to at least one intermediate point on the original route and then continuing to the destination. Based upon an estimated cost of the restoration route plus a predetermined actual cost of the route from the intermediate point to the final destination, the routing module is further configured to estimate a reroute cost, and select a reroute based upon the estimated reroute cost.

Claims

1. A navigation device comprising:

a processor;

a map information storage medium storing map information;

a position determining module configured to enable the processor to determine a current location, a velocity and direction of travel of a vehicle, and determine whether the current position is a deviation from an original route from a starting position to a destination;

a routing module configured to enable the processor to determine the original route and a reroute from current location to the destination, the reroute comprising a restoration route from the current location to at least one intermediate point on the original route and then continuing to the destination;

wherein the route module is further configured to enable the processor to estimate a reroute cost upon an estimated cost of the restoration route plus a predetermined actual cost of the route from the intermediate point to the final destination, and then select a reroute based upon the estimated reroute cost.

2. A navigation device according to claim 1, wherein said processor is configured to assign an increased cost to turns on the restoration route for a predetermined distance from the current location.

3. A navigation device according to claim 1, wherein the processor is configured to select a plurality of intermediate points at predetermined intervals on the original route.

4. A navigation device according to claim 1, wherein the route module is configured to determine an original route from the starting position to the destination.

5. A navigation device according to claim 1, wherein the map information storage medium comprises the predetermined actual route cost from each intermediate point to the destination.

6. A method of determining a reroute after an off-route deviation, comprising:

detecting a position of the vehicle;

computing an original route for a vehicle from a starting point to a destination;

detecting a current location that indicates a deviation from the original route;

assigning an increased cost to turns within a predetermined distance of the current location;

selecting a plurality of intermediate points on the original route;

estimating a restoration route cost from the current location to each intermediate point using the increased cost assigned to turns within a predetermined distance of the current location;

estimating a total cost of each reroute from the current location to the destination, wherein each estimated reroute cost comprises the estimated restoration route cost plus an actual cost for the portion of the original route from the intermediate point associated with that reroute to the destination;

selecting a reroute from the plurality of reroutes, based upon the cost of each reroute; and

performing map guidance based upon the selected reroute.

7. The method of claim 6, further comprising calculating the predetermined distance based upon vehicle speed and a time required computing a reroute.

8. The method of claim 6, further comprising calculating multiple reroutes simultaneously.

9. The method of claim 6, further comprising selecting a reroute based upon a shortest distance.

10. The method of claim 6, further comprising selecting a reroute based upon a quickest route.

11. The method of claim 6, further comprising calculating each reroute based upon the MANHATTAN DISTANCE from the current location to the intermediate point associated with each reroute.

12. The method of claim 6, wherein selecting at least one intermediate point comprises selecting a intermediate point that is between a deviation point and the destination.

13. At least one processor configured to perform the actions of:

detecting a position of the vehicle;

computing an original route for a vehicle from a starting point to a destination;

detecting a current location that is a deviation from the original route;

assigning an increased cost to turns within a predetermined distance of the current location;

selecting a plurality of intermediate points on the original route;

estimating a restoration route cost from the current location to each intermediate point using the increased cost assigned to turns within a predetermined distance of the current location;

estimating a total cost of each reroute from the current location to the destination, wherein each estimated reroute cost comprises the estimated restoration route cost plus an actual cost for the portion of the original route from the intermediate point associate with that reroute to the destination;

selecting a reroute from the plurality of reroutes, based upon the cost of each reroute; and

performing map guidance based upon the selected reroute.

14. A machine-readable medium comprising executable instructions stored thereon, comprising:

a first set of instructions for causing a processor to detect a position of the vehicle;

a second set of instructions for causing a processor to compute an original route for a vehicle from a starting point to a destination;

a third set of instructions for causing a processor to detect a current location that is a deviation from the original route;

a fourth set of instructions for causing a processor to assign an increased cost to turns within a predetermined distance of the current location;

a fifth set of instructions for causing a processor to select at least one intermediate point on the original route;

a sixth set of instructions for causing a processor to estimate a restoration route cost from the current location to each intermediate point using the increased cost assigned to turns within a predetermined distance of the current location;

a seventh set of instructions for causing a processor to estimate a total cost of each reroute from the deviation route to the destination, wherein each estimated reroute cost comprises the estimated restoration route cost plus an actual cost for the portion of the original route from the intermediate point associate with that reroute to the destination;

an eighth set of instructions for causing a processor to select a reroute from the at least one reroute, based upon the cost of each reroute; and

a ninth set of instructions for causing a processor to perform map guidance based upon the selected reroute.