US6507785B1 - Method and system for detecting and correcting off route navigation for server based route guidance systems - Google Patents

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.

Description

FIELD OF THE INVENTION

This invention relates generally to the navigation of a moving vehicle. In particular, this invention relates to a method and system for detecting and correcting off route navigation.

BACKGROUND OF THE INVENTION

As wireless communication continues to evolve, state of the art systems and technology continues to also increase in usefulness and effectiveness. Expectation of technology is also increasing and there is a growing need to develop applications, equipment and methods to drive this effectiveness even higher, while lowering cost. Costs are lowered primarily through building more capacity and functionality in existing technology or through designing systems or methods that require less processing time and increases data accuracy and transmission volume.

Many of these new developments in functionality are a result of advances in software development via complex algorithms based on established methods known in the art. In this inventions several key concepts are used to address a typical navigation challenge, which is a vehicle detouring off of a planned route.

It would be desirable therefore to provide a method for detecting and correcting off-route navigation to provide more effective navigation instructions to a moving vehicle that overcomes the above.

SUMMARY OF THE INVENTION

One aspect of the present invention provides a method of generating more effective navigation instructions for a vehicle that has traveled off of a planned route. A plurality of nodes located on road segments is provided, a plurality of pre-established checkpoints at intersections is generated and a signal including location coordinates identifying a vehicles current position is received. A vehicle's coordinates are compared to checkpoints coordinates, a proximity ellipse is constructed in response to the comparison of a vehicle's location coordinates to the coordinates of the checkpoints and determination is made if at least one return path cycle exist within a proximity ellipse.

Another aspect of the system provides a computer usable medium including a program for generating more effective navigation instructions for a vehicle that has traveled off of a planned route. The program may include computer readable program code that provides a plurality of nodes located on road segments, generates a plurality of pre-established checkpoints at intersections and receives a signal including location coordinates identifying a vehicle's current position. The program may also include computer readable program code that compares a vehicle's coordinates to coordinates of checkpoints, constructs a proximity ellipse in response to the comparison of the vehicle's location coordinates to the coordinates of the checkpoints and identifies at least one return path cycle within the proximity ellipse.

Another aspect of the present invention provides a system for generating more effective navigation instructions for a vehicle that has traveled off of a planned route. The system may include means for providing a plurality of nodes located on road segments, means for generating a plurality of pre-established checkpoints at intersections and means for receiving a signal including location coordinates identifying a vehicle's current position. It may also include means for comparing the vehicle's coordinates to coordinates of checkpoints, means for constructing a proximity ellipse in response to the comparison of the vehicle's location coordinates to the coordinates of the checkpoints and means for identifying at least one return path cycle within the proximity ellipse.

The foregoing and other features and advantages of the invention will become further apparent from the following detailed description of the presently preferred embodiments, read in conjunction with the accompanying drawings. The detailed description and drawings are merely illustrative of the invention rather than limiting, the scope of the invention being defined by the appended claims and equivalents thereof.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a schematic diagram of a system for generating navigation information for a vehicle in accordance with the present invention;

FIG. 2 is a schematic diagram of another embodiment of a system for generating navigation information for a vehicle in accordance with the present invention;

FIG. 3 is a flow diagram of one embodiment of a method for of a method for detecting and correcting off-route navigation of a vehicle in accordance with the present invention;

FIG. 4 is a sequence diagram of one embodiment of a method for detecting and correcting off-route navigation of a vehicle in accordance with the present invention.

DETAILED DESCRIPTION OF THE PRESENTLY PREFERRED EMBODIMENTS

FIG. 1 shows one embodiment of a system for providing services to a vehicle in accordance with the present invention at100.

The system may include one ormore vehicle clients101, one ormore carrier systems120, one ormore communication networks130, one or moreservice management subsystems140, and one ormore navigation subsystems150. The service management subsystems may comprise one or moreservice management applications142 and one ormore service managers144. Thenavigation subsystems150 may comprise one ormore route applications151,152 and one ormore coordinate databases153,154.

Navigation subsystem150 is a system for generating routes to be delivered tovehicle client101 and for receiving route information fromvehicle client101.Navigation subsystem150 may be connected with or in communication withservice management subsystem140.Service management subsystem140 may be used to manage the delivery of information to or fromnavigation subsystem150 to other parts ofsystem100. Routes may be delivered or information may be received via a live agent, such as a human advisor, or via a virtual agent, such as an interactive computer program.

Navigation subsystem150 may be any suitable hardware or software configuration, or combination of hardware and software that is configured to generate a route, process route information or receive information fromvehicle client101. In one embodiment of the invention,navigation subsystem150 comprises one ormore route applications151,152 and one ormore coordinate databases153,154. For example,route applications151,152 may be any suitable software application for generating route information or otherwise processing route information. Coordinatedatabases153,154 may be any suitable databases for storing route information, such as location coordinates.

Vehicle client101 may be any suitable vehicle. For example, the vehicle may be an automobile or a passenger-carrying unit such as a bus or train. Alternatively,vehicle client101 may be an occupant of the vehicle or any suitable client device contained in the vehicle. In one embodiment of the invention,vehicle client101 may be a mobile or portable device equipped to communicate withservice management subsystem140.Carrier system120 may be any suitable system for transmitting a signal fromvehicle101 toservice management subsystem140.Carrier system120 may also transmit a signal fromservice management subsystem140 tovehicle client101. In one embodiment of the invention,carrier system120 may be a wireless carrier system as is well known in the art.Carrier system120 may be; for example, a transmitter/receiver unit attached tovehicle client101. Alternatively,carrier system120 may be a separate transmitter/receiver carried byvehicle client101.

Communication network130 may be any suitable system for communicating betweenvehicle client101 andservice management subsystem140. In one embodiment of the invention, communication network may be a public switched telephone network (PSTN). Alternatively,communication network130 may be a multiprotocol Internet or Intranet capable or transmitting voice and/or data in either analog or digital form or a combination of both. Alternatively,communication network130 may be a hybrid communication network or virtual network.

Service management subsystem140 may be a system for managing a variety of services to be delivered to or fromvehicle client101. In one embodiment of the invention,service management subsystem140 manages services that can be distributed over a variety of channels. For example, services may be delivered via a live agent, such as a human advisor, or via a virtual agent, such as an interactive computer program. The structure ofservice management subsystem140 may enable services to be delivered in a uniform manner regardless of the channel used for delivery or of the service being delivered.Service management subsystem140 may maintain a consistent subscriber experience and “look and feel” across the products being delivered across the service distribution channels enabled.

FIG. 2 shows one embodiment of a navigation system in accordance with the present invention at200.Navigation system200 may include one ormore navigation clients210,212. Eachnavigation client210,212 may have an in-vehicle navigator221,222.Navigation system200 may also include one or moreroute generation applications251,252.Navigation system200 may also include one ormore coordinate databases253,254.

Navigation clients210,212 may be one or more vehicle clients as described above.

In-vehicle navigator221,222 may be any suitable component ofnavigation client210,212, which may be used to navigatevehicle client210,212. For example, in-vehicle navigator221,222 may be a driver. Alternatively, in-vehicle navigator221,222 may be an automatic system for navigatingvehicle210,212.

Route generation applications251,252 may be any suitable application for calculating maneuver lists of directions between one or more locations. For example,route generation applications251,252 may be any suitable software or hardware programs for managing or calculating routes, portions of route or route coordinates. Route generation applications may include or be able to calculate routes from navigation client's current location to private residences, businesses or recreational facilities. In one embodiment of the invention,route generation applications251,252 are in communication with coordinatedatabases253,254.

Route generation applications251,252 may generate navigation information in any suitable manner. For example,route generation applications251,252 may generate routes using geocoding. That is, theapplication251,252 determines a corresponding latitude and longitude based on an input navigation address. Alternatively,route generation applications251,252 may generate routes using reverse geocoding. That is, theapplication251,252 determines a corresponding navigation address based on input latitude and longitude coordinates.

Coordinatedatabases253,254 may be any suitable databases for storing such location coordinates as latitude and longitude of a variety of locations. These locations may be, for example, points of interest. Coordinatedatabases253,254 may also be a database of street addresses. Coordinatedatabases253,254 may also be a database of routes between points.

Referring now to FIG.3 and FIG.4. FIG. 3 shows a flow diagram of one embodiment of a method for detecting and correcting off-route navigation of a vehicle in accordance with the present invention at300. FIG. 4 is a sequence diagram of one embodiment of a method for detecting and correcting off-route navigation of a vehicle in accordance with the present invention at400.

The client vehicle may upload coordinates identifying its current position and, heading and speed information to the navigation system server150 (block303). The vehicle continues to navigate along aplanned route413 which may have been downloaded from thenavigation system server150. The vehicle may detour off of the plannedroute413 and approach and pass an off-route checkpoint (block305). Crossing the off-route checkpoint may signal a failure to execute an expected maneuver and may for example, trigger an audible or visible alarm. In this embodiment, the crossing of an off-route checkpoint may trigger the construction of a proximity ellipse (block307) by a method known in the art. The area within the proximity ellipse contains nodes and road segments. Using methods know in graph theory, these nodes and road segments can be connected to generate a return path, known in the art as a cycle, that may be navigated to return to a node on theplanned route413. Candidate cycles within the ellipse may be identified (block309) and if acceptable candidate cycles found within this list (block311), the cycle that is closest to the planned route may be selected (block317) and the vehicle may navigate back to a node on theplanned route413. If no acceptable cycles are found in the ellipse, arecovery rectangle418 can be constructed (block313) by using the leftmost focal point of the proximity ellipse as the rightmost point of the rectangle. The major axis length of the recovery rectangle may be predetermined based on various conditions, for example, road density, vehicle speed and navigation server information load. Candidate return path cycles may be identified within this rectangle. The return path cycle that is closest to the navigatingvehicle101 may be selected (block317) and the vehicle may use this cycle to navigate to a node back on the planned route413 (block319). If acceptable cycles are not found in the recovery rectangle (block315), another ellipse may be constructed using the leftmost rectangle point as the rightmost ellipse focal point. The process of identifying candidate cycles and selecting the cycle closest to the travelling vehicle may continue until an acceptable cycle is identified or until another predetermined action is triggered. In some embodiments the number of times that this process is repeated may be predetermined on thenavigation system server150.

Referring now to FIG. 4, before the vehicle begins to navigate, communication may be established withnavigation system server150. Aplanned route413 may be generated using theroute generation applications251,252 and then downloaded from thenavigation system server150 along with a list of off-route checkpoints.Point405 may be the starting point of thevehicle client101 on theplanned route413 and may be theplanned end point419. As shown in theactual route416 the client vehicle may incorrectly turn left at street m425. It may thancross checkpoint415 signaling that it has detoured off of the plannedroute413 and an audible or visual signal may be triggered. Anellipse420 may be constructed by a method known in the art, using the off-route checkpoint location as the rightmost focal point for the ellipse. The major axis can be determined based on various factors. In this embodiment, it is based on the current road density of the navigated road segment of street m425, the navigating vehicle speed and the information load of thenavigation system server150. The area bound by the ellipse contains road segments and nodes which can be connected to form a navigable path. Based on a method known in the art of graph theory, a cycle may be connected road segments and nodes that form a route with its end point being connected to a node onplanned route413. Candidate cycles may be identified within the proximity ellipse by a method known in the art andcycle417 may be the cycle nearest to the current location of the vehicle and may be identified as the innermost acceptable cycle. The vehicle may select thefirst cycle417 as the route to navigate back to the plannedroute413.

Had there been no acceptable cycles found within the ellipse, arecovery rectangle418 may have been constructed. The focal points of the ellipse may be used as the baseline for the construction of the rectangle.

While the embodiments of the invention disclosed herein are presently considered to be preferred, various changes and modifications can be made without departing from the spirit and scope of the invention. The scope of the invention is indicated in the appended claims, and all changes that come within the meaning and range of equivalents are intended to be embraced therein.

Claims (20)

We claim:

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 ofclaim 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 ofclaim 1, further comprising:

predetermining the planned route at the remote generation application; and

downloading the planned route to the vehicle.

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

5. The method ofclaim 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 ofclaim 1, further comprising:

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

7. The method ofclaim 1, further comprising:

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

8. The method ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 9, wherein a rightmost focal point of the proximity ellipse comprises the current vehicle location.

13. The program ofclaim 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 ofclaim 9, further comprising:

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

15. The program ofclaim 9, further comprising:

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

16. The program ofclaim 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 ofclaim 17, further comprising:

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

19. The system ofclaim 17, further comprising:

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

20. The system ofclaim 17, further comprising:

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

means for downloading the planned route to the vehicle.

Images