Patent Publication Number: US-9846046-B2

Title: Vehicle navigation method and system

Description:
BACKGROUND 
     GPS and other turn-by-turn navigation systems are becoming ever more prevalent as tools for determining a route to a particular destination. For example, a TOMTOM GPS is often a portable GPS that can be moved from vehicle to vehicle. Using satellite GPS signals, it determines where its present location on the globe is. This information is then combined with map and or heading information to determine a route to a selected destination. 
     Some vehicles also have built in GPS, and use, for example, an instrument display screen to display a route and/or directions. In other systems, directions can be spoken by a vehicle system to a driver, in lieu of or in addition to being displayed. 
     In general, GPS systems will determine a present location of a vehicle, determine a map location that corresponds to that present location, a provide directions from there. Of course, if the map data is incomplete or, for example, the vehicle is parked in the middle of a hay field, traditional “map directions” may not be available to the system on which directions to the driver can be based. 
     In addition to these situations, there are many “urban hayfields,” in the form of parking lots, driveways, etc. whose location does not conform to any particular map location in GPS data. One solution would be to program all of these into a GPS map, but since they are prone to change and arise quite often, this may be a difficult task to undertake. 
     Accordingly, GPS systems need some method of “guessing” to determine how a vehicle is to get from a present “unknown” location to a location along a route to be traveled. 
     Additionally, some vehicle-based computing systems, such as the FORD SYNC system, may not store all of the map data in the vehicle, since storage space may be limited and needed for a variety of applications. As a result, relevant data about a certain area to be traveled may be dynamically transmitted in small packets. Since the vehicle may not be holding the entire map of an area, it is also useful to have a method for determining and/or providing directions to a route to be traveled from an unknown location. 
     As one example, if a vehicle is in parking lot  201  shown in  FIG. 2 , there could be a myriad of possibilities for getting to Main St.  209  (from which directions are provided). The system has no way of knowing that the user will take route  219 , and, similarly, the system (using limited bandwidth), may not want to send enough information to cover all possible routes from the parking lot  201  to Main St.  209 . Accordingly, it may be desired to have a method for providing a user with simple directions that do not require total knowledge of all possible routes. 
     SUMMARY 
     In one illustrative embodiment, a vehicle based computing system includes a communication link providing communication between a processor at the vehicle and a nomadic wireless communication device, an audio output controllable by the processor for outputting directions for traveling, and a GPS device capable of determining coordinates of the vehicle and relaying to coordinates to the processor. 
     In this illustrative embodiment, the processor is operable to receive the coordinates from the GPS receiver and transmit the coordinates through the communication link to the nomadic device. The nomadic wireless communication device then transmits these coordinates to a remote network. 
     Also in this embodiment, the processor is operable to receive, through the communication link, map data pertaining to a route to be traveled by the vehicle. The map data includes a recommended starting road. The starting road may be based at least in part on present coordinates of the vehicle as determined by the GPS device. 
     The processor is further operable to provide, through the audio or other output, instructions to travel to a recommended starting road name on which the vehicle is not presently traveling. In other words, if the recommended starting road was “Ford Road,” the vehicle audio system would issue a command such as “proceed to Ford Road.” 
     The processor is further operable to determine if a vehicle whose initial coordinates did not correspond to the recommended starting road is presently located at coordinates corresponding to the recommended starting road. In this instance, the vehicle was in a location for which map data was not available. The system can then determine that the vehicle is, at a given moment, now on the recommended starting road. 
     Next, based at least in part on the correspondence between the present location of the vehicle and recommended starting road coordinates (e.g., without limitation, the vehicle is on the starting road) the processor is operable to output at least initial instructions for the route to be traveled starting from the recommended starting road. 
     In another illustrative embodiment, a vehicle based computing system includes a communication link providing communication between a processor at the vehicle and a nomadic wireless communication device, an audio output controllable by the processor for outputting directions for traveling, and a GPS capable of determining coordinates of the vehicle and relaying to coordinates to the processor through a GPS receiver. 
     In this illustrative embodiment, the processor receives the coordinates from the GPS receiver and transmits the coordinates through the communication link to the nomadic wireless communication device, as in the previous embodiment. 
     The processor may also receive, through the communication link, map data pertaining to a route to be traveled by the vehicle. 
     The map data further includes a plurality of potential locations. The vehicle is likely (based on a calculation made, for example, by the remote network) to be located proximate to one of these potential locations, when the map data is received by the processor. 
     The processor is able to determine, based on GPS coordinates of the vehicle when the map data is received, which potential location most closely corresponds to the vehicle&#39;s location. The processor may also output one or more travel instructions, based at least in part on which potential location the vehicle is located proximate to. 
     In a third illustrative embodiment, a method of determining travel directions for a vehicle includes receiving input corresponding to coordinates and speed of a vehicle. The method also includes calculating how far the vehicle is likely to travel within a predetermined time span, based on at least the received speed input. 
     The method further includes approximating where the vehicle is located on a map based on the coordinates, and determining possible location points to which vehicle can travel on the map within the predetermined time span. This determination is based at least in part on the calculated possible distance of travel. 
     The method includes determining a preferred route of travel to a preselected destination, based at least in part on the coordinates of the vehicle. Also included in the method is determining one or more alternate routes of travel to the preselected destination from at least one of the possible location points. 
     Finally, the method includes transmitting a plurality of travel routes including a preferred route of travel and one alternate route of travel. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows an illustrative vehicle based computer system that may be used to implement the methods described herein and/or may in part contain or interface with the apparatuses described herein; 
         FIG. 2  shows an illustrative example of directing a vehicle from an “unknown” location to a desired route of travel; 
         FIG. 2 a    shows an exemplary process for providing directions from a “non-mapped” location to a desired route of travel; 
         FIG. 3  shows an illustrative example of a micro-route system implementation; and 
         FIG. 4  shows an illustrative example of a process for providing a route using a micro-route system. 
     
    
    
     These figures are not exclusive representations of the systems and processes that may be implemented to carry out the inventions recited in the appended claims. Those of skill in the art will recognize that the illustrated system and process embodiments may be modified or otherwise adapted to meet a claimed implementation of the present invention, or equivalents thereof. 
     DETAILED DESCRIPTION 
       FIG. 1  illustrates an example block topology for a vehicle based computing system  1  for a vehicle  31 . A vehicle enabled with a vehicle-based computing system may contain a visual front end interface  4  located in the vehicle. The user may also be able to interact with the interface if it is provided, for example, with a touch sensitive screen. In another illustrative embodiment, the interaction occurs through, button presses, audible speech and speech synthesis. 
     In the illustrative embodiment 1 shown in  FIG. 1 , one or more processors (e.g. CPU) control at least some portion of the operation of the vehicle-based computing system. Provided within the vehicle, the processor allows onboard processing of commands and routines. Further, the processor may be connected to both non-persistent  5  and persistent storage  7 . In this illustrative embodiment, the non-persistent storage is random access memory (RAM) and the persistent storage is a hard disk drive (HDD) or flash memory. 
     The processor may be provided with a number of different inputs allowing the user to interface with the processor. In this illustrative embodiment, a microphone  29 , an auxiliary input  25  (for input  33 ), a USB input  23 , a GPS input  24  and a BLUETOOTH input  15  are all provided. An input selector  51  may be provided, to allow a user to swap between various inputs. Alternatively, inputs may be automatically selected and/or prioritized. Input to both the microphone and the auxiliary connector is converted from analog to digital by a converter  27  before being passed to the processor for processing. 
     Outputs to the system can include, but are not limited to, a visual display  4  and a speaker  13  or stereo system output. The speaker is connected to an amplifier  11  and receives its signal from the processor  3  through a digital-to-analog converter  9 . Output can also be made to a remote BLUETOOTH device such as a personal navigation device (PND)  54  or a USB device such as vehicle navigation device  60  along bi-directional data streams shown at  19  and  21  respectively. 
     In one illustrative embodiment, the system  1  uses the BLUETOOTH transceiver  15  to communicate  17  with a user&#39;s nomadic device (ND)  53  (e.g., cell phone, smart phone, PDA, etc.). The nomadic device can then be used to communicate  59  with a network  61  outside the vehicle  31  through, for example, communication  55  with a cellular tower  57 . 
     Exemplary communication between the nomadic device and the BLUETOOTH transceiver is represented by signal  14 . 
     Pairing a nomadic device  53  and the BLUETOOTH transceiver  15  can be instructed through a button  52  or similar input, telling the CPU that the onboard BLUETOOTH transceiver will be paired with a BLUETOOTH transceiver in a nomadic device. 
     Data may be communicated between CPU  3  and network  61  utilizing, for example, a data-plan, data over voice, or DTMF tones associated with nomadic device  53 . Alternatively, it may be desirable to include an onboard modem  63  in order to transfer data between CPU  3  and network  61  over the voice band. In one illustrative embodiment, the processor is provided with an operating system including an API to communicate with modem application software. The modem application software may access an embedded module or firmware on the BLUETOOTH transceiver to complete wireless communication with a remote BLUETOOTH transceiver (such as that found in a nomadic device). In another embodiment, nomadic device  53  includes a modem for voice band or broadband data communication. In the data-over-voice embodiment, a technique known as frequency division multiplexing may be implemented when the owner of the nomadic device can talk over the device while data is being transferred. At other times, when the owner is not using the device, the data transfer can use the whole bandwidth (300 Hz to 3.4 kHz in one example). 
     If the user has a data-plan associated with the nomadic device, it is possible that the data-plan allows for broad-band transmission and the system could use a much wider bandwidth (speeding up data transfer). In still another embodiment, nomadic device  53  is replaced with a cellular communication device (not shown) that is affixed to vehicle  31 . 
     In one embodiment, incoming data can be passed through the nomadic device via a data-over-voice or data-plan, through the onboard BLUETOOTH transceiver and to the vehicle&#39;s internal processor  3 . In the case of certain temporary data, for example, the data can be stored in RAM  5  or on the HDD  7  or other storage media until such time as the data is no longer needed. 
     Additional sources that may interface with the vehicle include an onboard compass (not shown), a personal navigation device  54 , having, for example, a USB connection  56  and/or an antenna  58 ; or a vehicle navigation device  60 , having a USB  62  or other connection, an onboard GPS device  24 , or remote navigation system (not shown) having connectivity to network  61 . 
     Further, the CPU could be in communication with a variety of other auxiliary devices  65 . These devices can be connected through a wireless  67  or wired  69  connection. Also, or alternatively, the CPU could be connected to a vehicle based wireless router  73 , using for example a WiFi  71  transceiver. This could allow the CPU to connect to remote networks in range of the local router  73 . 
       FIG. 2  shows an illustrative example of directing a vehicle from an “unknown” location to a desired route of travel. 
     In this illustrative embodiment, a vehicle  203  is located in a parking lot  201  behind a building  211 . The parking lot is not contained in the system map data of the vehicle based computing system (or personal/vehicle navigation devices  54  or  60 ), nor is the parking lot data available for download to the system. 
     The vehicle driver desires to travel the route marked  209 , eventually turning right onto 2 nd  St.  215 . Obviously, it would be a problem for the system to “map” a straight line path to the route  209  from the vehicle  203 , as in this case it would likely run into any number of buildings, curbs, medians, etc. 
     Instead, the system will provide a simple verbal (for example) instruction such as “proceed to Ford Rd.” This can be especially useful if the system does not have a navigation display and cannot visually show the user a representation of the desired road/route. 
     The system may also provide additional direction, such as “proceed North to Ford Rd.” in order to more easily facilitate travel to the recommended starting road  207 . Using these directions, and an onboard compass, a driver can direct the vehicle  203  to exit the parking lot through exit  205 , even if the vehicle computing system and navigation components are unaware of the existence of the exit  205 . 
     Once the vehicle has exited onto the recommended road, the system can then direct the vehicle along path  219  to Main St.  209 , at which point the route  217  can be presented, traveling to 1 st  St.  213  and eventually to 2 nd  St.  215 . 
       FIG. 2 a    shows an exemplary process for providing directions from a “non-mapped” location to a desired route of travel. 
     In this illustrative embodiment, the vehicle based computing system first determines the GPS coordinates of the vehicle  251 . This can be done, for example, by a call from a processor included with the vehicle based computing system to a GPS included in the vehicle (or connected to the processor through a wired or wireless connection). 
     Once the processor has obtained the GPS coordinates, it may also, at least in this embodiment, determine the vehicle heading  253 , using, for example, an onboard compass. The GPS coordinates and the heading (if determined) may be transmitted to a remote network  255 . In this illustrative embodiment, the processor is connected to a nomadic device, such as, but not limited to, a cellular phone. The processor transmits the data to the cellular phone or other nomadic device, and the nomadic device connects to the remote network to complete transmission. 
     The processor then receives a response from the remote network  257 . Again, in this illustrative implementation, the response is transmitted from the network, to the nomadic device, to the processor. 
     According to this illustrative embodiment, the response will contain at least one recommended road to which the vehicle should travel, if the vehicle is not presently on a known road (e.g., without limitation, in a parking lot). 
     There may be a variety of roads to which the vehicle could travel from the parking lot. The remote network (or the processor) may select one based at least in part on the vehicle&#39;s GPS coordinates (those at the time of transmission or the present coordinates) and/or the vehicle&#39;s heading (again, the heading at the time of transmission or the present heading). 
     Since there is a degree of “lag” between the transmission of the coordinates and/or heading and the receipt of a response, a developer may elect to have the network perform the calculation as to which nearby road is desired, or, to better avoid this lag, the developer may elect to have the processor receive several options for roads and then perform the calculation based on real time positioning and heading data. 
     Once a response has been received and a recommended road has been selected, the processor may then instruct the driver of the vehicle as to which road should be accessed to reach the desired route of travel  258 . This instruction can be done, for example, over the vehicle audio system or on a navigational display. 
     The vehicle computing system can then, either once or periodically for some predetermined period of time, compare the GPS location of the vehicle to coordinates corresponding to the recommended road and any other possible known roads  259 . 
     This process can be done in a variety of ways, and the example shown here is meant for illustrative purposes only. The system will also check if the present coordinates correspond to the recommended route  263 , and, if not, then if they correspond to a “known” route (e.g., without limitation, an alternative road). If the coordinates are on neither a recommended or known route, the system may proceed back to step  251 , or, alternatively, for example, continue back to step  259  (not shown) to continue checking coordinates, for a fixed period of time, until a known route is reached, etc. 
     If the vehicle&#39;s present coordinates correspond to a known route that is not the recommended route, the system will find a route to be traveled based on the vehicle&#39;s present location  265 . This determination can be made, for example, by using locally stored map data or by communication with the remote network (if, for example, the local map data is insufficient). 
     Once a route is known, the vehicle will present the next set of directions to the user  267 . 
       FIG. 3  shows an illustrative example of a micro-route system implementation. 
     In at least one illustrative embodiment, data related to a vehicle&#39;s present location is transmitted from a vehicle based computing system to a remote network. However, in this embodiment, the vehicle based computing system doesn&#39;t have a direct connection with the network. Instead, the information is transmitted through a connection with a nomadic device, and the nomadic device provides the communication to the network. Further, this transmission may be done in a data-over-voice manner, such that the bandwidth may be limited. 
     While this method still provides fast communication, there may be a delay of several seconds before the needed information is relayed to the network and back to the vehicle. Since the vehicle may be moving at the time, information about the vehicle&#39;s location when the request was sent to the network may not correspond to the vehicle&#39;s location by the time the response is received. 
     For example, if a vehicle was traveling at 60 miles per hour down a road, and there was a four second delay, then the vehicle would be approximately 352 feet further down the road by the time the response was received. This could present a problem if the exit onto which the vehicle was to turn was only 250 feet down the road when the request was sent. The vehicle could also have turned onto a side road on which it was not previously traveling, etc. 
     In the example shown in  FIG. 3 , the vehicle  301  should travel route  303  to reach an intended destination. That is, under optimal conditions, the vehicle would proceed straight from its present location in the figure at position  301  and turn at location  309 . 
     If, however, there is construction or if the vehicle just turns (because the driver made an unanticipated turn), the instructions for the vehicle now need to be changed. 
     In the example shown, the vehicle driver would initially receive instructions to proceed east on A St. and turn left on 2 nd  Ave. These instructions are received at some point prior to the vehicle reaching the point  301 . 
     At point  301 , the vehicle asks for updated instructions (as part of a regular communication to ensure route integrity, for example). The vehicle is presently traveling at, for example, 30 miles an hour. By the time the instruction request has been sent to the network and a response has been received, the vehicle has deviated from the intended route and is now at position  301   a.    
     If the remote system merely sent back data and instructions for the optimal route (i.e., take A St. to 2 nd  Ave.), a further request would need to be sent to the system based on the new vehicle position. Of course, the vehicle could again change positions while the request was pending, resulting in a stream of directions that arrived possibly too late to be useful. 
     Instead, however, in this illustrative embodiment, the vehicle heading and speed are transmitted along with the GPS coordinates. Using this information, the network can estimate possible positions at which the vehicle could be located by the time the information returns to the vehicle based computing system. 
     In this illustrative example, the system estimates that the vehicle could, based on present speed and heading, be located at  313 ,  311 ,  309  or  307 . Accordingly, directions (or at least map data) from those points to the preferred route of travel are provided to the vehicle based computing system. 
     In this manner, the system can accurately provide directions to the preferred route of travel, regardless of which of the four points the vehicle is closest to. 
     So, for the example shown, the vehicle has moved to position  301   a . Since this location is closest to (and the vehicle is oriented towards) location  311 , the vehicle based computing system will provide the driver with directions to travel along route  305  until it rejoins with the preferred route of travel  303 . The system could also reroute to a destination based on different possible location points. 
     Further, in this illustrative embodiment, possible location points are located in roughly a 180 degree arc in front of the vehicle. This prevents data pertaining to all possible routes in every direction from having to be transmitted to the vehicle based computing system. This is effective if the developer wishes to assume that the vehicle will vary rarely make an unexpected turn of more than 180 degrees. It is, of course, also possible to transmit data pertaining to a wider or narrower possible spectrum of potential locations. 
       FIG. 4  shows an illustrative example of a process for providing a route using a micro-route system. 
     In this illustrative embodiment, the processor of the vehicle based computing system determines the coordinates, speed and heading of the vehicle  401 . The speed and heading information can often be obtain from the vehicle&#39;s CAN bus and is often provided by existing vehicle systems. 
     The GPS coordinates can be obtained from, for example, a built in GPS. They could also be obtained from a GPS connected to the vehicle computing system through a wired or wireless connection. In another illustrative embodiment, a nomadic device such as a cellular phone may provide the GPS coordinates to the vehicle based computing system. 
     Once the coordinates, speed and/or heading are obtained by the processor, the system transmits some or all of this information to a remote network. 
     In this illustrative embodiment, the remote network transmission is done through a connection to a nomadic device. The vehicle based communication system transmits information to the nomadic device, and the nomadic device transmits the information to a remote network  403 . 
     The system then waits for a response from the remote network  405 . 
     Once the remote network is done processing the requested information, the vehicle based computing system receives a response  407 . This response includes one or more projected vehicle location points. These are the points corresponding to the stars in  FIG. 3 . 
     The projected location points are then compared to the actual GPS location of the vehicle at the time the response is received (or at the time the comparison is done, etc.)  409 . Unless the guess by the network was grossly inaccurate, or unless (in this example at least), the vehicle did not turn more than 180 degrees, the vehicle should be proximally located to at least one of the projected location points. 
     Once the system knows which point the vehicle is closest too, directions are then provided from that point. Presumably, local map data may be included with the information, so that, if the vehicle is not directly on the projected point, directions to the point can also be provided if needed. 
     If the vehicle is not in the proximity of one of the projected points, the system may call the network for another set of directions, using the same information. This embodiment is shown by the dashed option in  FIG. 4 . Instead of proceeding directly to providing directions from the closest projected point, the system first checks to see if the present GPS cords are within a tolerance distance of the closest projected point  413 . If not, the system repeats the call to the server, otherwise directions are provided as in the first illustrative embodiment. 
     While various exemplary, illustrative, non-limiting embodiments have been described in detail, those familiar with the art to which this invention relates will recognize various alternative designs and embodiments for practicing the invention, which is only limited by the following claims.