Method and system for detecting and correcting off route navigation for server based route guidance systems

• US 6,507,785 B1
• Filed: 09/21/2001
• Issued: 01/14/2003
• Est. Priority Date: 09/21/2001
• Status: Active Grant

• Current Assignee: General Motors LLC (General Motors Company)
• Original Assignee: General Motors Corporation (Motors Liquidation Co. GUC Trust)
• Inventors: Jijina, Jasmin, Stefan, Jeffrey M.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): MANCHO, RONNIE M
• Application Number:
  US09/960,693
• Time in Patent Office: 480 Days
• Field of Search: 701/200, 701/210, 701/217, 701/23, 701/24, 340/995, 340/989, 340/988, 340/990, 340/945, 342/357.08, 342/357.13, 342/357.09, 455/412, 455/413, 455/414
• US Class Current: 701/210
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

The present invention provides a system, a method and a computer usable medium including a program for a vehicle that has traveled off of a planned route.

This may be done by providing a plurality of nodes located on road segments, generating a plurality of pre-established checkpoints at intersections and receiving a signal including a location coordinate identifying current vehicle position. It may also be done by comparing the vehicle coordinates to the coordinates of checkpoints, constructing a proximity ellipse in response to the aforementioned comparison and identifying at least one return path cycle within the ellipse with acceptable road segments that allow travel back to a planned route.

Claims

1. A method of dynamically generating navigation instructions for a vehicle that has traveled off a planned route, comprising:

providing a plurality of nodes, the nodes located on road segments;

generating, at a remote route generation application, a plurality of checkpoints at intersections, the checkpoints having checkpoint coordinates;

receiving, at the remote route generation application, vehicle location coordinates, the vehicle location coordinates identifying a current vehicle position;

comparing, at the remote route generation application, the vehicle location coordinates to the checkpoint coordinates;

constructing, at the remote route generation application, a proximity ellipse based on the comparison of the vehicle location coordinates to the checkpoint coordinates; and

determining whether at least one return path cycle is within the proximity ellipse, the return path cycle comprising at least one node on the planned route.

2. The method of claim 1, wherein the checkpoints are pre-established by the remote route generation application, further comprising:

downloading the checkpoints from the remote route generation application to the vehicle.

3. The method of claim 1, further comprising:

predetermining the planned route at the remote generation application; and

downloading the planned route to the vehicle.

4. The method of claim 1, wherein a rightmost focal point of the proximity ellipse comprises the current vehicle location.

5. The method of claim 1, wherein the return path cycle comprises at least one navigable road segment that connects to a node on the planned route.

6. The method of claim 1, further comprising:

selecting the return path cycle which is closest to the planned route.

7. The method of claim 1, further comprising:

constructing a recovery rectangle if no return path cycle exists within the proximity ellipse.

8. The method of claim 7, wherein a leftmost focal point of the proximity ellipse comprises a rightmost point of the recovery rectangle.

9. Computer program product in a computer usable medium for dynamically generating navigation instructions for a vehicle that has traveled off a planned route, comprising:

computer program code that providing a plurality of nodes, the nodes located on road segments;

computer program code generating, at a remote route generation application, a plurality of checkpoints at intersections, the checkpoints having checkpoint coordinates;

computer program code that receives, at the remote route generation application, vehicle location coordinates, the vehicle location coordinates identifying a current vehicle position;

computer program code that compares, at the remote route generation application, the vehicle location coordinates to the checkpoint coordinates;

computer program code that constructs, at the remote route generation application, a proximity ellipse based on the comparison of the vehicle location coordinates to the checkpoint coordinates; and

computer program code that determines whether at least one return path cycle is within the proximity ellipse.

10. The program of claim 9, wherein the checkpoints are pre-established by the remote route generation application, further comprising:

computer program code that downloads the checkpoints from the remote route generation application to the vehicle.

11. The program of claim 9, further comprising:

computer program code that predetermines the planned route at the remote generation application; and

computer program code that downloads the planned route to the vehicle.

12. The program of claim 9, wherein a rightmost focal point of the proximity ellipse comprises the current vehicle location.

13. The program of claim 9, wherein the return path cycle comprises at least one navigable road segment that connects to a node on the planned route.

14. The program of claim 9, further comprising:

computer program code that selects the return path cycle which is closest to the planned route.

15. The program of claim 9, further comprising:

computer program code that constructs a recovery rectangle if no return path cycle exists within the proximity ellipse.

16. The program of claim 15, wherein a leftmost focal point of the proximity ellipse comprises a rightmost point of the recovery rectangle.

17. A system for remotely generating navigation instructions for a vehicle that has traveled off of a planned route comprising:

means for providing a plurality of nodes, the nodes located on road segments;

means for generating, at a remote route generation application, a plurality of checkpoints at intersections, the checkpoints having checkpoint coordinates;

means for receiving, at the remote route generation application, vehicle location coordinates, the vehicle location coordinates identifying a current vehicle position;

means for comparing, at the remote route generation application, the vehicle location coordinates to the checkpoint coordinates;

means for constructing, at the remote route generation application, a proximity ellipse based on the comparison of the vehicle location coordinates to the checkpoint coordinates; and

means for determining whether at least one return path cycle is within the proximity ellipse.

18. The system of claim 17, further comprising:

means for selecting the return path cycle which is closest to the planned route.

19. The system of claim 17, further comprising:

means for constructing a recovery rectangle if no return path cycle exists within the proximity ellipse.

20. The system of claim 17, further comprising:

means for predetermining the planned route at the remote generation application; and

means for downloading the planned route to the vehicle.