Route guidance system and method for use in vehicle navigation

The present invention relates to a method and apparatus for use in a vehicle navigation system in communicating a calculated route to a driver. A particular arrangement to be described below by way of example in illustration of the present invention is concerned with the timing of warning prompts which alert a driver to upcoming manoeuvres.

Vehicle navigation systems employ a variety of methods for communicating a route to a driver. One method employs warning chimes to alert the driver to an upcoming manoeuvre. Another employs a series of voice prompts. The timing of these chimes or voice prompts are crucial to effective route guidance. If a prompt is delayed, the driver may not be able to execute the manoeuvre in a safe and orderly manner. If a prompt is issued too early and a significant amount of time elapses before the vehicle arrives at the manoeuvre location, the driver may not be properly alerted.

Currently available vehicle navigation systems which have warning chimes or voice guidance typically employ a fixed distance at which the driver is warned of an upcoming manoeuvre. That is, once the vehicle is determined to be within a particular distance of a geographical location at which the manoeuvre is to be executed, the system issues the warning chime or the voice guidance prompt. Unfortunately, this method does not account for the often widely varying characteristics of the environment in which the vehicle is operating. For example, if the fixed warning distance is set to provide adequate notice to the driver in a freeway environment where the speed limit is 65 miles per hour, it is likely that it will be too long for a residential area where the speed limit is typically 25 miles per hour.

Moreover, a fixed warning distance may cause confusion by encompassing more than one junction at which similar manoeuvres may be executed. This will almost certainly be the case where the fixed warning distance is set relative to a freeway environment. Because such a warning distance would be relatively long, it would be likely to encompass more than one intersection in a different environment where the average vehicle speed is considerably less such as, for example, in a residential environment. Such confusion is unacceptable if a vehicle navigation system is to guide a driver adequately along a calculated route.

A more flexible approach is therefore needed for communicating warnings of impending manoeuvres to the user of a vehicle navigation system.

A vehicle navigation system to be described below, by way of example in illustration of the invention, communicates warnings of upcoming manoeuvres in a manner which takes into account the conditions under which the vehicle is operating, thereby providing a more flexible approach. Once a route has been calculated, each manoeuvre in the route is communicated to the driver at a warning distance which may be varied according to a variety of factors. In one embodiment to be described below by way of example, the system calculates a warning distance based in part on the current speed of the vehicle. As a result, the warning distance more closely resembles the actual distance required for the driver to react to the manoeuvre instruction in a timely and safe manner.

In another embodiment illustrative of the invention, the system determines the link class of the road upon which the vehicle is currently travelling and selects a warning distance associated with the determined link class. Because the link class of a road corresponds roughly to the speed at which one travels on the road, this method has an effect on the warning distance which is similar to that described above.

In some embodiments, illustrative of the present invention another level of flexibility is added to deal with situations in which road junctions having similar geometries are closely spaced and are likely to cause confusion as to which junction a particular warning prompt refers. Once the system determines a warning distance for a particular upcoming manoeuvre, it then determines whether there are any junctions within the warning distance in advance of the manoeuvre junction which present a similar geometry, i.e., any junction which could be mistaken for the manoeuvre junction. If such a junction is found, the warning distance is adjusted to be less than or equal to the distance between the similar junction and the manoeuvre junction. In a specific embodiment the warning distance is set such that the warning is issued immediately after the vehicle passes the similar junction, thereby avoiding any confusion.

Thus, there will be described below in illustration of the invention, a method and an apparatus for providing route guidance to a user of a vehicle navigation system. A route is generated which corresponds to a plurality of manoeuvres. A warning distance is determined from a particular geographic location associated with a particular manoeuvre, the warning distance being based in part on a variable parameter. A manoeuvre instruction corresponding to the particular manoeuvre is then provided at the warning distance from the particular geographic location.

In one embodiment to be described by way of example in illustration of the invention, the variable parameter is vehicle speed. In another embodiment, the variable parameter is road segment link class. In some embodiments, in which the particular manoeuvre corresponds to a first junction having a first characteristic, and in which a second junction having the first characteristic is within the warning distance, the warning distance is adjusted to an adjusted warning distance. In a more specific embodiment, the distance between the first and second junctions is defined as the first distance and the adjusted warning distance is set to the first distance where the first distance is greater than or equal to the minimum limit. Where the first distance is less than the minimum limit, the adjusted warning distance is set to the minimum limit.

The following description and drawings disclose, by means of examples, the invention which is characterised in the claims, whose terms determine the extent of the protection conferred hereby.

In the drawings:- <ul id="ul0001" list-style="none" compact="compact"><li>Fig. 1 is a block diagram of a vehicle navigation system which is suitable for use with the present invention,</li><li>Fig. 2 is a graph of warning distance vs. vehicle speed,</li><li>Fig. 3 is a diagram for use in illustrating a particular method of operation of a system,</li><li>Fig. 4 is a diagram for use in illustrating another method of operation of a system,</li><li>Fig. 5 is a diagram for use in illustrating yet another method of operation of a system, and</li><li>Fig. 6 is a flowchart.</li></ul>

Arrangements to be described below, in illustration of the invention are suitable for use with apparatus described in commonly assigned United States Patents No. 5,345,382 to Kao for CALIBRATION METHOD FOR A RELATIVE HEADING SENSOR, No. 5,359,529 to Snider for ROUTE GUIDANCE ON/OFF-ROUTE STATE FILTER, No. 5,374,933 to Kao for POSITION CORRECTION METHOD FOR VEHICLE NAVIGATION SYSTEM, and No. 5,515,283 to Desai et al. for METHOD FOR IDENTIFYING HIGHWAY ACCESS RAMPS FOR ROUTE CALCULATION IN A VEHICLE NAVIGATION SYSTEM.

Fig. 1 is a block diagram of a specific embodiment of a vehicle navigation system 100 for use with an arrangement illustrative of the present invention. Sensors 112 and 114 and GPS receiver 118 are coupled to computing means 120 through a sensor/GPS interface 122. In typical embodiments, mileage sensor 112 is an odometer, and angular velocity sensor 114 includes a gyroscope, or a differential odometer coupled to the wheels of the vehicle. A global positioning system (GPS) data receiver 118 is provided for receiving signals from, for example, a satellite-based navigation system. Data from a sensor/GPS interface 122 is transmitted to a CPU 124, which performs calibration, signal processing, dead-reckoning, vehicle positioning, and route guidance functions. A database containing map information may be stored in a database medium 126, with software directing the operation of computing means 120 stored in a main memory 128 for execution by the CPU 124. The memory 128 may include a read-only memory (ROM), or a reprogrammable non-volatile memory, such as a flash memory or an SRAM. A system RAM 130 permits the reading and the writing of the information necessary to execute such software programs. A database medium 126 may be a non-volatile memory, a hard disk drive, a CD-ROM, or an integrated circuit in which digitized map information has been stored. An output controller 132, which may include a graphics controller, receives data processed by the CPU 124 and transmits the data to display console 140 which includes an output communicator 134, usually having a display screen with associated audio electronics and audio speakers. The driver may input data, such as a desired destination, through a user interface 136, typically being a keyboard.

The map database stored in the database medium 126 preferably includes positional data such as, for example, latitude and longitude coordinates, to describe road intersections or nodes, road segments, landmarks and points of interest, and other geographical information. The database may further include data representing characteristics of roads or places on the map, such as road and place names, road features such as dividers, one-way restrictions, surface, speed limit, shape, elevation, and other properties. In specific embodiments illustrative of the invention, the map database includes cost values associated with individual nodes and road segments. These cost values correspond to the estimates of the time intervals for traversing the respective node or segment. Node cost values take into consideration such information as, for example, whether a vehicle would encounter oncoming traffic, thus delaying a left turn manoeuvre. Segment costs reflect road segment characteristics such as speed limit and segment length, both of which affect the travel time along the segment. Also associated with each road in the map database is a link class which relates to the category or type of the road. For example, the highest level category of the hierarchy is the link class FREEWAY. The lowest level includes the link classes FRONTAGE and MISC which include, for example, frontage roads and alleys.

A vehicle navigation system for use with arrangements illustrative of the present invention is operable to generate a route from a source location to a destination according to a variety of different methods. Some examples of such methods are described in the U.S. patents which have been referred to above. In addition, further methods for route generation which may be employed in conjunction with the present invention are described in a commonly assigned, copending U.S. Patent Application Serial No. <u>08</u>/           for ROUTE GENERATION IN A VEHICLE NAVIGATION SYSTEM, filed on ____________ 1996.

Once a route has been generated according to any of a variety of methods, the system begins to communicate manoeuvre instructions to the driver. Each manoeuvre instruction is communicated at a variable warning distance in advance of the location of the upcoming manoeuvre. The warning distance may be determined according to different embodiments of the invention. In one method, the warning distance for a particular manoeuvre instruction is set according to the link class associated with the road on which the vehicle is travelling as it approaches the corresponding manoeuvre. For example, Table 1 shows warning distances for different link classes according to a specific embodiment illustrative of the invention. <tables id="tabl0001" num="0001"><table frame="all"><title>Table 1.</title><tgroup cols="2" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><thead valign="top"><row rowsep="1"><entry namest="col1" nameend="col2" align="center"><b>Warning distance table</b></entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="center">Road Segment Link Class</entry><entry namest="col2" nameend="col2" align="center">Warning distance (ft.)</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">Freeway</entry><entry namest="col2" nameend="col2" align="right">2112</entry></row><row><entry namest="col1" nameend="col1" align="left">Expressway</entry><entry namest="col2" nameend="col2" align="right">1214</entry></row><row><entry namest="col1" nameend="col1" align="left">Artery</entry><entry namest="col2" nameend="col2" align="right">1003</entry></row><row><entry namest="col1" nameend="col1" align="left">Street</entry><entry namest="col2" nameend="col2" align="right">792</entry></row><row><entry namest="col1" nameend="col1" align="left">Frontage</entry><entry namest="col2" nameend="col2" align="right">528</entry></row><row><entry namest="col1" nameend="col1" align="left">Ramp</entry><entry namest="col2" nameend="col2" align="right">1214</entry></row><row><entry namest="col1" nameend="col1" align="left">Connector</entry><entry namest="col2" nameend="col2" align="right">528</entry></row><row><entry namest="col1" nameend="col1" align="left">Miscellaneous</entry><entry namest="col2" nameend="col2" align="right">528</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">Access</entry><entry namest="col2" nameend="col2" align="right">528</entry></row></tbody></tgroup></table></tables>

In another method, the warning distance for a particular manoeuvre instruction is determined in part with reference to the current speed of the vehicle. In a specific embodiment, the warning distance is given by:<maths id="math0001" num="(1)"><math display="block"><mrow><msub><mrow><mtext>d</mtext></mrow><mrow><mtext>w</mtext></mrow></msub><msub><mrow><mtext> = d</mtext></mrow><mrow><mtext>max</mtext></mrow></msub><msub><mrow><mtext>; v</mtext></mrow><mrow><mtext>a</mtext></mrow></msub><msub><mrow><mtext> &gt; v</mtext></mrow><mrow><mtext>max</mtext></mrow></msub></mrow></math><img file="EP0836074A2_D0001.tif" /></maths><maths id="math0002" num="(2)"><math display="block"><mrow><msub><mrow><mtext>d</mtext></mrow><mrow><mtext>w</mtext></mrow></msub><msub><mrow><mtext> = d</mtext></mrow><mrow><mtext>min</mtext></mrow></msub><msub><mrow><mtext> + [(d</mtext></mrow><mrow><mtext>max</mtext></mrow></msub><msub><mrow><mtext>-d</mtext></mrow><mrow><mtext>min</mtext></mrow></msub><msub><mrow><mtext>) · (v</mtext></mrow><mrow><mtext>a</mtext></mrow></msub><msub><mrow><mtext>-v</mtext></mrow><mrow><mtext>min</mtext></mrow></msub><msub><mrow><mtext>)]/(v</mtext></mrow><mrow><mtext>max</mtext></mrow></msub><msub><mrow><mtext>-v</mtext></mrow><mrow><mtext>min</mtext></mrow></msub><msub><mrow><mtext>); v</mtext></mrow><mrow><mtext>max</mtext></mrow></msub><msub><mrow><mtext> ≥ v</mtext></mrow><mrow><mtext>a</mtext></mrow></msub><msub><mrow><mtext> ≥ v</mtext></mrow><mrow><mtext>min</mtext></mrow></msub></mrow></math><img file="EP0836074A2_D0002.tif" /></maths><maths id="math0003" num="(3)"><math display="block"><mrow><msub><mrow><mtext>d</mtext></mrow><mrow><mtext>w</mtext></mrow></msub><msub><mrow><mtext> = d</mtext></mrow><mrow><mtext>min</mtext></mrow></msub><msub><mrow><mtext>; v</mtext></mrow><mrow><mtext>a</mtext></mrow></msub><msub><mrow><mtext> &lt; v</mtext></mrow><mrow><mtext>min</mtext></mrow></msub></mrow></math><img file="EP0836074A2_D0003.tif" /></maths> where <ul id="ul0002" list-style="none" compact="compact"><li>d_w is the warning distance;</li><li>d_min is the minimum limit;</li><li>d_max is the maximum limit;</li><li>v_a is the current vehicle speed;</li><li>v_min is a minimum speed below which the warning distance is the minimum limit; and</li><li>v_max is a maximum speed above which the warning distance is the maximum limit.</li></ul> In various other specific embodiments d_min is 528 feet, d_max is 2640 feet, v_min is 25 miles per hour, and v_max is 70 miles per hour. Using these numbers, equations (1)-(3) may be plotted as shown in Fig. 2 with the horizontal axis representing vehicle speed and the vertical axis representing warning distance. As shown, below 25 mph the warning distance is constant at 0.1 miles (528 feet). Between 25 and 70 mph the warning distance varies according to equation (2). Finally, above 70 mph the warning distance is constant at 0.5 miles (2,640 feet).

Some embodiments also include a feature by means of which a chime is sounded after the manoeuvre instruction has been given at the warning distance to alert the driver that the manoeuvre must be executed almost immediately. The chime sounds may be set to sound at a location which is a fixed distance from the manoeuvre location, e.g., 300 feet. Alternatively, the chime distance may vary in a manner similar to the warning distance.

As mentioned above, even where the warning distance to a manoeuvre junction has been determined with reference to the environment in which the vehicle is operating, confusion may yet arise because one or more junctions with similar geometries lie within the warning distance. Such a situation is illustrated by the diagram of Fig. 3. As the driver proceeds along road 302 towards the next manoeuvre i.e., a right turn at location A, the system determines an original warning distance 304 according to one of the embodiments described above. If, however, the system determines that another junction exists within warning distance 304 at which the driver may also execute a right turn, i.e., location B, the warning distance is adjusted to the distance between location B and location A, i.e., distance 306. The system also sounds a chime at distance 308 where the vehicle is nearly on top of the manoeuvre. In yet another specific embodiment, if the adjusted warning distance would be less than a minimum warning distance, the warning distance is set to the minimum warning distance. In an even more specific embodiment, each link class has a minimum warning distance associated therewith.

Alternatively, where the system detects an intermediate junction such as location B, the originally determined warning distance is retained, but the substance of the warning is changed. Thus, for example, if the warning was originally to state "Turn right at next intersection", it is changed to state "Turn right at second intersection".

Another warning feature is provided in some embodiments to give the driver additional advance notice of an upcoming manoeuvre. In freeway environments, drivers must often traverse several lanes of traffic moving at high speeds in order to exit. Because the distance required to execute such a manoeuvre typically depends upon more than just the vehicle's speed, an additional voice prompt is provided which allows the driver to begin changing lanes well in advance of the desired exit. Fig. 4 shows a pre-warning distance 402 from an exit 404 on a freeway 406 at which the driver is provided with a voice prompt stating "Prepare to exit". Subsequently, at a warning distance 408 from exit 404, the driver receives the manoeuvre instruction "Next exit on the right". Pre-warning distance 402 may be set in a variety of ways. In one embodiment it includes some multiple of warning distance 408. In another embodiment, each link class has a fixed pre-warning distance associated therewith.

Fig. 5 shows a situation in which a pre-warning is issued at a distance 502 from a desired exit 504 and a similar exit 506 precedes exit 504. As with the example of Fig. 4, a warning distance 508 is determined. However, because the system detects the existence of exit 506, the warning distance is adjusted to a new warning distance 510 at which location a warning is issued stating "Next exit on the right".

Fig. 6 is a flowchart 600 which illustrates the operation of another particular embodiment illustrative of the present invention. Initially, a route between a source location and a destination is generated according to any of a variety of methods (step 602). The route includes a plurality of contiguous road segments and a plurality of manoeuvres to be executed by the driver. The manoeuvres are sequentially communicated to the driver via a display console and audio speakers. Between manoeuvres, the system determines at what point to communicate the next manoeuvre to the driver. To facilitate this determination, the system either determines the current speed of the vehicle and/or the link class of the road on which the vehicle is currently travelling (step 604). The warning distance is then determined (step 606) using the vehicle speed or the link class depending upon which of the above-described embodiments is employed.

The system then determines whether there is a junction within the warning distance which is similar to the manoeuvre junction (step 608). If such a junction exists, the system determines the distance between the two junctions, i.e., the first distance, (step 610), and whether the first distance is less than a minimum limit (step 612). The minimum limit may be a fixed value, or it may vary according to the current link class. If the first distance is greater than or equal to the minimum limit, the warning distance is set to the first distance (step 614). If, however, the first distance is less than the minimum limit, the warning distance is set to the minimum limit (step 616).

The system then determines the current position of the vehicle (step 618). If no intermediate junction is found in step 608, the system moves directly to step 618. The system then determines whether the current vehicle position is within the warning distance (step 620). If not, the system continues to update the vehicle position until it is. If the current vehicle position is within the warning distance, the system issues a manoeuvre instruction voice prompt to the driver (step 622). If the destination has been reached (step 624) , the procedure ends. If not, the system repeats the procedure with reference to the next manoeuvre.

While particular embodiments illustrative of the invention have been described by way of example, it will be understood that variations and modifications thereof, as well as other embodiments are possible within the scope of the appended claims.

For example, the embodiments have been described primarily with regard to the timing of voice guidance prompts. However, it will be understood that other warning arrangements, for example, the timing of warning chimes may be used.