Abstract:
A method of and apparatus for generating an alternate route for a system to travel to a predetermined destination are described. The method comprises determining a velocity of a system traveling along a primary route; and generating an alternate route to the primary route if the system velocity is below a predetermined motion threshold. A navigation system for generating an alternate route to a destination includes a motion sensor for detecting the navigation system velocity along a primary route and a controller coupled with the motion sensor. The controller receives a motion signal indicating navigation system motion and generates an alternate route to the primary route responsive to the motion signal indicating navigation system motion different from a predetermined motion threshold value.

Description:
FIELD  
       [0001]     The disclosed embodiments relate to automatic determination of route guidance information.  
       BACKGROUND  
       [0002]     Existing vehicle navigation systems receive position information signals from one or more on-board sensors and determine a position of the vehicle. For example, some navigation systems receive global positioning system (GPS) signals transmitted from orbiting satellites and calculate a position of the vehicle with respect to the satellites.  
       SUMMARY  
       [0003]     The present embodiments provide a mechanism for the automatic determination of route guidance information to a user.  
         [0004]     A method embodiment of generating an alternate route for a system to travel to a predetermined destination includes determining a velocity of a system traveling along a primary route; and generating an alternate route to the primary route if the system velocity is below a predetermined motion threshold.  
         [0005]     A system embodiment for generating an alternate route to a destination includes a motion sensor for detecting the navigation system velocity along a primary route and a controller coupled with the motion sensor. The controller receives a motion signal indicating navigation system motion and generates an alternate route to the primary route responsive to the motion signal indicating navigation system motion different from a predetermined motion threshold value.  
         [0006]     Still other advantages of the embodiments will become readily apparent to those skilled in the art from the following detailed description, wherein the preferred embodiments are shown and described, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the embodiments. 
     
    
     DESCRIPTION OF THE DRAWINGS  
       [0007]     The present invention is illustrated by way of example, and not by limitation, in the figures of the accompanying drawings, wherein elements having the same reference numeral designations represent like elements throughout and wherein:  
         [0008]      FIG. 1  is a high level block diagram of a vehicle including a vehicle navigation system;  
         [0009]      FIG. 2  is a process flow diagram of a process according to an embodiment;  
         [0010]      FIG. 3  is a high level block diagram of a processing device usable in conjunction with an embodiment;  
         [0011]      FIG. 4  is a process flow diagram according to another embodiment;  
         [0012]      FIG. 5  is a prompt window according to an embodiment;  
         [0013]      FIG. 6  is a process flow diagram according to another embodiment;  
         [0014]      FIG. 7  is a settings window according to an embodiment;  
         [0015]      FIG. 8  is a settings window according to another embodiment; and  
         [0016]      FIG. 9  is a process flow diagram according to another embodiment.  
     
    
     DETAILED DESCRIPTION  
       [0017]     As described in detail below,  FIG. 1  depicts a vehicle  100  including a navigation system  101  having a navigation controller  102 , a navigation sensor  104 , and a user interface (UI) device  106 . UI device  106  receives user entered commands and information and generates audio/visual information for viewing/hearing by the user responsive to navigation controller  102 . Navigation sensor  104  generates and transmits position information to navigation controller  102  responsive to receipt of position signals. Navigation controller  102  receives position information from navigation sensor  104  and user entered commands from UI device  106  and determines a route from the present location of vehicle  100  to a user-specified destination.  
         [0018]     In some embodiments, navigation sensor  104  is one of a satellite-based, ground-based, self-contained, and/or a combination thereof. Some example sensor systems usable with embodiments include global positioning system (GPS), Loran, very high frequency (VHF) omni-directional range (VOR), VOR/distance measuring equipment (DME), non-directional beacon (NDB), and an inertial reference system (IRS).  
         [0019]     In accordance with an embodiment, navigation system  101  executing a sequence of instructions (as described more fully below in conjunction with  FIG. 2 ) determines that vehicle  100  has slowed or stopped for a time period exceeding a predetermined timeout value during traversal of a route to a user-specified destination. For example, vehicle  100  may have encountered stopped or slowed traffic, a road blockage, an emergency situation, and other situations in which the vehicle is unable to proceed/slowed along the guided route provided by navigation system  101 . After determining slowing or stopping of vehicle  100 , navigation system  101  prompts the user to decide whether the navigation system should determine an alternate route to reach the user-specified destination from the current location of the vehicle along the previously determined route. If the user requests navigation system  101  to determine an alternate route (also referred to as replanning), the system determines the alternate route based on the current position of the vehicle, the user-specified destination, and an inability of the vehicle to traverse all or a portion of the remaining portion of the previously determined route.  
         [0020]     In a further embodiment and in response to the user request, navigation system  101  determines more than one alternate route to reach the user-specified destination from the current location of the vehicle along the previously determined route. Navigation system  101  causes UI device  106  to display one or more of the determined alternate routes to the user for selection.  
         [0021]     In another embodiment, after determining slowing or stopping of vehicle  100 , navigation system  101  automatically determines one or more alternate routes to reach the user-specified destination from the current location of the vehicle along the previously determined route. As above, navigation system  101  causes UI device  106  to display one or more of the automatically determined alternate routes to the user for selection.  
         [0022]     After selection of an alternate route by the user in accordance with at least one of the above embodiments, navigation system  101  provides route guidance information to the user using UI device  106  based on the determined alternate route.  
         [0023]     As briefly described above,  FIG. 1  depicts a vehicle  100  including navigation system  101  comprising navigation controller  102  connected with navigation sensor  104  and UI device  106 . Navigation sensor  104  receives position information signals and calculates and transmits the vehicle position to navigation controller  102 . Navigation controller  102  receives the vehicle position from navigation sensor  104  and causes UI device  106  to display the vehicle position to a user. For example, UI device  106  displays a map depicting the vehicle position and current heading to the driver of vehicle  100 . Additionally in some instances, UI device  106 , responsive to input from navigation controller  102 , displays route guidance information to the user regarding how to reach a predetermined destination specified by the user using the UI device. Optionally, UI device  106  uses audio instructions in addition to, or in place of, visual instructions to supply the route guidance information.  
         [0024]     During operation, navigation system  101  provides audio and visual route guidance information to the user to direct the user to reach a predetermined destination position. The user follows the provided route guidance information, e.g., audible turn-by-turn instructions, and causes the vehicle to travel along a route determined by navigation controller  102  to reach the user&#39;s destination. During traversal of the route, navigation controller  102  continuously and/or periodically monitors the vehicle position based on receipt of position information from navigation sensor  104 . By performing map matching and/or one or more other techniques, navigation controller  102  updates a stored position value of the vehicle and causes UI device  106  to update the displayed information and generate audible information provided to the user.  
         [0025]      FIG. 2  depicts a high level process flow diagram of a portion  200  of a sequence of instructions executed by navigation controller  102  according to an embodiment. Navigation controller  102  is a processing device, e.g., a processor, an application specific integrated circuit, or a computer system or other device capable of executing a sequence of instructions.  FIG. 3  described in detail below depicts a navigation controller  102  on which an embodiment may be implemented.  
         [0026]     Navigation controller  102  executing a sequence of instructions, e.g., stored in a memory such as memory  306 , proceeds to step  202  and causes UI device  106  to provide route information to the user based on an existing determined route to the user-specified destination. Navigation controller  102  proceeds to step  204  and determines, based on received position information signals from navigation sensor  104 , whether the motion of vehicle  100  differs from, e.g., falls below, a predetermined vehicle motion threshold. That is, navigation controller  102  determines if vehicle  100  has stopped or slowed during traversal of a determined route.  
         [0027]     If the outcome of the step  204  determination is negative, i.e., the vehicle is traveling at a velocity meeting or exceeding the predetermined vehicle motion threshold, the process flow proceeds to return to step  202  and continue displaying and providing route guidance information to the user. If the outcome of the step  204  determination is positive, i.e., the vehicle is traveling at a velocity below the predetermined vehicle motion threshold, the process flow proceeds to step  206  and a timer is started.  
         [0028]     During execution of process step  206 , navigation controller  102  determines, based on received position information signals from navigation sensor  104 , whether the motion of vehicle  100  continues to differ from, e.g., falls below, the predetermined vehicle motion threshold. If the motion threshold is met or exceeded by vehicle  100 , navigation controller  102  stops (and optionally resets) the timer execution and the flow of control proceeds to return to step  202 . For example, the user may temporarily stop or slow vehicle  100  due to travel conditions and then return to traveling speed.  
         [0029]     If the timer expires, i.e., the timer meets or exceeds a predetermined timeout value, and vehicle  100  has not exceeded the predetermined vehicle motion threshold, the vehicle is determined to have stopped or slowed for an excessive amount of time and the user is prompted regarding an alternate route determination.  
         [0030]     According to the  FIG. 2  embodiment, navigation controller  102  proceeds to step  208  in response to the motion of vehicle  100  falling below the predetermined vehicle motion threshold for the predetermined timeout value. In step  208 , navigation controller  102  determines (replans) an alternate route for vehicle  100  to reach the user-specified destination without continuing along at least a portion of the currently traversed route. That is, navigation controller  102  determines an alternate route for the user to travel which avoids the current route conditions. The process flow of navigation controller  102  proceeds to return to step  202  and the controller causes UI device  106  to display route and/or provide guidance information to the user in accordance with the determined alternate route.  
         [0031]      FIG. 4  depicts a variation on the  FIG. 2  embodiment in which a process flow  400  similar to process flow  200  is executable by navigation controller  102 . Navigation controller  102  executes the process flow  400  as in execution of process flow  200  until the expiration of the timer at step  206 . In accordance with  FIG. 4 , instead of transitioning directly to step  208  the process flow proceeds to step  402  and navigation controller  102  causes UI device  106  to prompt the user to decide whether to cause the controller to determine an alternate route to the user-specified destination.  
         [0032]     If the user responds positively to UI device  106  in response to step  402 , the process flow proceeds to step  208  and navigation controller  102  executes the steps (process steps  208 ,  202 ) as described above with respect to  FIG. 2 . If the user responds negatively to UI device  106  in response to step  402 , the process flow proceeds to return to step  202  and display the original route and/or provide route guidance information to the user based on the original route.  
         [0033]      FIG. 5  depicts an exemplary prompt window  500  displayed by UI device  106  to the user at step  402  ( FIG. 4 ) in order to prompt the user to decide whether to cause the controller to determine an alternate route as described above. Prompt window  500  includes a text box  502  for prompting the user to decide whether navigation controller  102  should determine an alternate route. In the  FIG. 5  embodiment, text box  502  prompts the user to choose a distance to avoid in replanning the route. Selection of a close window box  504  by the user causes navigation controller  102  to receive a negative response at step  402  ( FIG. 4 ) and proceed to return to step  202  in process flow  400 . Prompt window  500  also includes four radio buttons  506 - 509  corresponding to distances defining the length of an alternate route detour which navigation controller uses to plan the alternate route. That is, navigation controller  102  determines an alternate route to reach the user-specified destination by planning a detour of a given length, specified by user selection of one of the radio buttons  506 - 509 , from the current location of navigation system  101 .  FIG. 5  depicts a user selection (by way of a dashed line around radio button  506  and a changed display status of radio button  506 ) of a 3 mile detour.  
         [0034]     Selection of radio button  509  causes an additional input screen (not shown) to be displayed by UI device  106  to enable the user to enter a user-specified value for the detour length. The user-specified detour length is displayed in custom text box  510  after entry.  
         [0035]     A route button  512  enables a user to positively respond to the prompt generated at step  400  ( FIG. 4 ) and thereby cause navigation controller  102  to determine an alternate route based on a selected detour length as specified by one of radio buttons  506 - 509 . A cancel button  514 , similar to close window box  504 , enables the user to respond negatively to the step  402  ( FIG. 4 ) prompt and cause navigation controller  102  to proceed to return to step  202  in process flow  400 .  
         [0036]     In another embodiment, UI device  106  displays a prompt (not shown), e.g., a button, text, or other indicator, on an existing screen in place of generating a separate prompt window  500 . Selection of the displayed prompt by the user causes generation of a positive user response to navigation controller  102  and subsequent processing according to the user response.  
         [0037]      FIG. 6  depicts a variation on the  FIG. 2  embodiment in which a process flow  600  similar to process flow  200  is executable by navigation controller  102 . Navigation controller  102  executes process flow  600  as in execution of process flow  200  until the determination of an alternate route at step  208 . In accordance with  FIG. 6 , instead of transitioning directly to return to step  202  the process flow proceeds to step  602  and navigation controller  102  causes UI device  106  to prompt the user to decide whether to use the determined alternate route.  
         [0038]     If the user responds positively by way of appropriate manipulation of UI device  106 , navigation controller  102  proceeds to step  202  and displays the route and/or provides route guidance information to the user based on the determined alternate route. If the user responds negatively using UI device  106 , navigation controller  102  proceeds to step  202  and displays the route and/or provides route guidance information to the user based on the existing route.  
         [0039]     In an embodiment, navigation controller  102  determines more than one alternate route and presents one or more of the determined alternate routes to the user via UI device  106  and requests the user to select one of the alternate routes or continue using the existing route, similar to the above-described process.  
         [0040]      FIG. 7  depicts a settings window  700 , referred to as a preferences window, enabling a user to specify particular parameter values to be used by navigation controller  102  according to some embodiments. Settings window  700  includes the text box  502  for prompting the user to manipulate UI device  106  to receive user entered preference values. Settings window  700 , similar to prompt window  500 , includes the four radio buttons  506 - 509 , as well as, custom text box  510  for receiving user entry of detour distance preferences. In an embodiment, use of radio buttons  506 - 509  and text box  510  in settings window  700  may obviate the need for such buttons in prompt window  500  and thereby further simplify the interface of the prompt window.  
         [0041]     Manipulation of an enable checkbox  702  causes UI device  106  to generate a signal to navigation controller  102  to enable the detour processing described herein. If enable checkbox  702  is not activated, navigation controller  102  does not perform detour processing determination. If enable checkbox  702  is activated, navigation controller  102  performs detour processing according to a described embodiment.  
         [0042]     Selection of alert timeout button  704  causes an additional input screen (not shown) to be displayed by UI device  106  to enable the user to enter a user-specified value for the predetermined timeout value. The user-specified predetermined timeout value is displayed in alert timeout button  704  after entry. In some embodiments, after selection of alert timeout button  704  by a user, UI device  106  presents one or more predetermined timeout values for user selection. In further embodiments, UI device  106  displays the predetermined timeout values for selection by the user similar to the detour length values presented using radio buttons  506 - 509  and text box  510  and similar functionality.  
         [0043]     Responsive to user selection of a save button  706 , UI device  106  causes navigation controller  102  to store the user-specified settings entered using settings window  700 , e.g., store the settings to memory  306 .  
         [0044]      FIG. 8  depicts a variation on the  FIG. 7  settings window in which a settings window  800  further includes a motion threshold value button  802  to be displayed by UI device  106  to enable the user to enter a user-specified value for the predetermined motion threshold value. The user-specified predetermined motion threshold value is displayed in motion threshold value button  802  after entry. In some embodiments, after selection of motion threshold value button  802  by a user, UI device  106  presents one or more predetermined motion threshold values for user selection. In further embodiments, UI device  106  displays the predetermined motion threshold values for selection by the user similar to the detour length values presented using radio buttons  506 - 509  and text box  510  and similar functionality.  
         [0045]      FIG. 9  depicts a further embodiment of a process flow  900  in which a vehicle  100  traveling along a road, e.g., a street, highway, freeway, path, or other unplanned route, slows or stops due to road conditions and navigation controller  102  determines an alternate route as described above. In particular in accordance with the  FIG. 9  embodiment, navigation controller  102  executes step  902  to display the position of vehicle  100  using UI device  106  based on position information signals from navigation sensor  104 . As in the  FIG. 2  embodiment, navigation controller  102  proceeds to step  904  and determines, based on received position information signals from navigation sensor  104 , whether the motion of vehicle  100  differs from, e.g., falls below, a predetermined vehicle motion threshold. That is, navigation controller  102  determines if vehicle  100  has stopped or slowed.  
         [0046]     If the outcome of the step  904  determination is negative, i.e., the vehicle is traveling at a velocity meeting or exceeding the predetermined vehicle motion threshold, the process flow proceeds to return to step  902  and continues displaying and providing route guidance information to the user. If the outcome of the step  904  determination is positive, i.e., the vehicle is traveling at a velocity below the predetermined vehicle motion threshold, the process flow proceeds to step  206  and a timer is started as described above with respect to  FIG. 2 .  
         [0047]     According to the  FIG. 9  embodiment, if the step  206  timer expires and vehicle  100  has not exceeded the predetermined vehicle motion threshold, the vehicle is determined to have stopped or slowed for an excessive amount of time and navigation controller  102  determines an alternate route. For example, navigation controller  102  determines an alternate route to detour vehicle  100  for the predetermined detour distance and routes the vehicle back to the current road at the next available location, e.g., returns the vehicle to the freeway at the next available on-ramp.  
         [0048]     Process flow  900  continues to be executed by navigation controller  102  as described above with respect to  FIG. 2 . After completing the detour, navigation controller  102  proceeds to return to step  902 . Additional embodiments similar to the other embodiments described above, e.g.,  FIGS. 4 and 6 , are also usable in conjunction with the  FIG. 9  embodiment.  
         [0049]      FIG. 3  depicts a high level block diagram of a processing device, e.g., navigation controller  102 , usable in conjunction with the above-described embodiments and upon which an embodiment may be implemented.  
         [0050]     Navigation controller  102  includes a bus  302  or other communication mechanism for communicating information, and a processor  304  coupled with the bus for processing information. Navigation controller  102  also includes a memory  306 , such as a random access memory (RAM) or other dynamic storage device, coupled to the bus  302  for storing settings values, e.g., motion threshold values, timeout values, data, and instructions to be executed by processor  304 . Memory  306  also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor  304 . Memory  306  may also include a read only memory (ROM) or other static storage device coupled to the bus  302  for storing static information and instructions for processor  304 . A storage device (not shown), such as a magnetic disk or optical disk, may be provided and coupled to bus  302  for storing data and instructions.  
         [0051]     Navigation controller  102  is coupled via bus  302  to UI device  106 , such as a flat panel, cathode ray tube, or other display device, input device, including alphanumeric and function keys, and other types of user interaction devices, such as a mouse, a trackball, cursor direction keys, or other device for communicating information and command selections to processor  304 .  
         [0052]     Embodiments are related to the use of navigation controller  102  to determine alternate routes responsive to detection of certain conditions. According to an embodiment, navigation controller  102  operates in response to processor  304  executing sequences of instructions contained in memory  306  in response to input received via navigation sensor  104  and/or UI device  106 , or a communication interface  308 . Such instructions may be read into memory  306  from another computer-readable medium, such as a storage device (not shown).  
         [0053]     However, the computer-readable medium is not limited to devices such as a storage device. For example, the computer-readable medium may include a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a compact disc-read only memory (CD-ROM), any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, a random access memory (RAM), a programmable read only memory (PROM), an electrically programmable ROM (EPROM), a FLASH-EPROM, any other memory chip or cartridge, a carrier wave embodied in an electrical, electromagnetic, infrared, or optical signal, or any other medium from which a computer can read. Execution of the sequences of instructions contained in the memory  306  causes the processor  304  to perform the process steps described above. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with computer software instructions to implement the invention. Thus, embodiments are not limited to any specific combination of hardware circuitry and software.  
         [0054]     Navigation controller  102  also includes a communication interface  308  coupled to bus  302 . Communication interface  308  provides a two-way data communication and may include wired and wireless links.  
         [0055]     A network link  310  provides data communication through one or more networks to other data devices. For example, network link  310  may provide a connection through communication network  312  to a host computer  314  or to data equipment operated by a communication service provider. Network link  310  uses electrical, electromagnetic, or optical signals which carry digital data streams. The signals through the network and the signals on network link  310  and through communication interface  308 , which carry the digital data to and from navigation controller  102 , are exemplary forms of carrier waves transporting the information.  
         [0056]     Navigation controller  102  can send messages and receive data, including program code, through the network(s), network link  310  and communication interface  308 . In an Internet example, a computer system  314  might transmit a requested code for an application program through communication network  312 , network link  310 , and communication interface  308 . In accordance with an embodiment, one such downloaded application provides for determining an alternate route based on certain conditions.  
         [0057]     The received code may be executed by processor  304  as it is received, and/or stored in memory  306 , or other non-volatile storage for later execution. In this manner, navigation controller  102  may obtain application code in the form of a carrier wave.  
         [0058]     It will be readily seen by one of ordinary skill in the art that the disclosed embodiments fulfill one or more of the advantages set forth above. After reading the foregoing specification, one of ordinary skill will be able to affect various changes, substitutions of equivalents and various other embodiments as broadly disclosed herein. It is therefore intended that the protection granted hereon be limited only by the definition contained in the appended claims and equivalents thereof.  
         [0059]     For example, audio generation of prompts and interactive voice response and/or voice recognition may be used in place of or in addition to user physical manipulation of an interface mechanism such as a display or keyboard/mouse/trackball/touch sensitive pad.