az United States Patent
`US 6,701,251 B2
`(10) Patent No.:
`Mar.2, 2004
`(45) Date of Patent:
`Stefan et al.
`
`
`US006701251B2
`
`(75)
`
`(54) METHOD AND SYSTEM FOR PROVIDING
`MULTIPLE BEGINNING MANEUVERS FOR
`NAVIGATION OFA VEHICLE
`Z
`es
`aang
`.
`Inventors: NadelWeaMaen Se ees
`PHOS
`Se:
`eens: AsO SOwnSs
`Nn oe Gregory B. Stewart, Livonia,
`.
`,
`.
`(73) Assignee: General Motors Corporation, Detroit,
`MI (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`US.C. 154(b) by 0 days.
`
`5,877,708 A *
`3/1999 Hijikata oe. 340/995
`5,878,368 A *
`3/1999 DeGraaf osc 701/209
`
`$001,688 A * 11/1909 Fukushima etal. 701/209
`
`991,
`‘ukushima et al.
`.........
`/
`
`1/2000 Yagyu et al. oo... 701/202
`6,014,607 A *
`3/2000 Maekawa et al. ws... 340/995
`6,034,626 A *
`9/2000 Sugiura ct al. vce 701/201
`6,119,066 A *
`6,134,501 A * 10/2000 OUME cecsssceecessseeeeeeeee 701/209
`
`6,172,641 Bl *
`1/2001 Millington 0.0000... 340/996
`
`6,199,013 B1 *
`3/2001 O’Shea oo...
`ee 340/988
`7/2001 Nimuraetal. ......0....... 340/990
`6,266,613 B1 *
`8/2001 McDonough ............... 701/210
`6,278,942 B1 *
`6,298,305 B1 * 10/2001 Kadabaet al. ...0.0.. 701/200
`
`6,324,472 Bl * 11/2001 O7Shea «eee 340/988
`
`
`............. 701/209
`6,427,119 B1
`7/2002 Stefan et al.
`6,487,496 B2 * 11/2002 Katayama etal. .......... 701/209
`y
`2002/0152024 Al * 10/2002 Stefan wo... 701/209
`
`* cited by examiner
`
`(56)
`
`22 Claims, 5 Drawing Sheets
`
`(21) Appl. No.: 09/837,409
`(22)
`Filed:
`Apr. 18, 2001
`Primary Examiner—Jacques H. Louis-Jacques
`.
`tgs
`(74) Attorney, Agent, or Firm—Anthony Luke Simon
`(65)
`Prior Publication Data
`(57)
`ABSTRACT
`US 2002/0156573 A1 Oct. 24, 2002
`hic
`fi
`‘ons
`.
`Amethod of
`oo,
`Int. Ch?ee GO1C 21/30; G08G 1/123
`(51)
` Pmsthedol generating nayigaticn instructionstora velle’s
`(52) US. Cle ceeccccccccssssseeee MIB: WiP0; Tin,
`is provided. Adestinationof the vehicle is received ata route
`340/989: 340/992: 340/995.19: 340/995.27
`:
`eee
`:
`:
`2
`
`
`
`
`
`
`= generation application.Amaneuver: , , ; list comprising a plu-
`(8) Field of ceeBGADbBHab aahteaane
`rality of navigation instructions is calculated based on a
`990, 995. 989 "901 992 ? 996 ? 995 1 995 19.
`current location of the vehicle and the destination. A distance
`¢
`2223
`?
`?
`9952 ; 995 53 995 7
`threshold is determined based on the current location of the
`we
`ee
`.
`vehicle and the destination. The navigation instructions
`References Cited
`located within the distance threshold are determined and
`transmitted from the route generation application to the
`U.S. PATENT DOCUMENTS
`vehicle. The navigation instructions located within the dis-
`340/988
`sS3ourag9 A.
`© pees Kamala:
`i
`tance threshold are executed at the vehicle. Systems and
`397A ies Beheeel et ale vs. 3Tabes
`programsfor using the method are also provided.
`
`3/1997 Tamai sees...
`vee 340/990
`5,608,635 A *
`
`.....0..0.. 340/988
`5,774,071 A *
`6/1998 Konishi et al.
`
`405
`Receive cail from vehicle
`
`
`
`
`
`
`
`
`
`
`
`
`
`410
`Contact route generation application
`
`445
`Receive destination from vehicle
`
`420
`Calculate maneuvers
`
`422
`Determine distance threshold
`
`425
`Determine maneuvers within distance threshold
`
`430
`Transmit maneuvers within threshold distanceto vehicle
`
`435
`Executefirst n maneuversat vehicle
`
`440
`Transmit remaining maneuvers
`
`450
`Execute remaining maneuvers at vehicle
`
`460
`Execute final maneuverat vehicle
`
` Google Exhibit 1058
`
`Google Exhibit 1058
`Google v. Mullen
`Google v. Mullen
`
`

`

`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 1 of 5
`
`US 6,701,251 B2
`
`FIG.1
`
`

`

`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 2 of 5
`
`US 6,701,251 B2
`
`270
`
`[t
`
`T=y
`
`|
`
`S|
`
`3
`nN
`
`FIG.2 ]|
`
`248
`
`©N
`
`m=
`
`=\ wo
`
`

`

`U.S. Patent
`
`Mar. 2, 2004
`
`Sheet 3 of 5
`
`US 6,701,251 B2
`
`uoyjeojddy
`
`2ge
`
`uonesouas)LSE
`ainoyuoneoddy
`
`uoijesauesy
`
`a}eUuIpsoog
`
`aseqeyep
`
`pGE
`
`aynoy00€€Se
`
`a}eUIpPIOOD
`
`eseqeyep
`
`
`JUSI|QUOHEBHIAENUSI|DUOHEBIAENalIn8\o_/
`ZeoLe=
`
`
`
`
`
`
`
`~
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 2, 2004
`
`Sheet 4 of 5
`
`US 6,701,251 B2
`
`
`
`a}OUaAyeSIGANaUeWHuUleWa!9}NDeXy
`
`
`suaanauewHururewasWwsuel,
`cer SJBANGUBL
`Str SPIGAO}SQUEISIP
`OLP BOIUSAWOM)
`SOP
`
`PJOYSsY}UILYIMSIBANUELUPLUSUEIL
`P[OUSAIU]SOUEISIPLIMSueAnaueUUBUILa}9q
`
`
`BJIYOAjeSJOANQUEWUSJB]NIEXy
`
`
`
`uonjesjddeuonessuebaynosjoe}U05D
`
`SIOIYOAWOUOHeUNSApaAlaoay
`
`Orr
`
`OS
`
`Q[DIU@AJeJAANAUBWJeuayNDexy
`
`O9F
`
`TAY
`
`hs
`
`PlOUSeJY]BOUEISIPSulWE}aq
`
`00P
`
`Py‘Sia
`
`[129AAIBDOy
`
`SLP
`
`OcPY
`
`O}E/NI[eD
`
`
`
`
`
`
`
`

`

`Sheet 5 of 5
`
`US 6,701,251 B2
`
`U.S. Patent
`
`Mar.2, 2004
`
`FIG.5
`
`

`

`US 6,701,251 B2
`
`1
`METHOD AND SYSTEM FOR PROVIDING
`MULTIPLE BEGINNING MANEUVERS FOR
`NAVIGATION OF A VEHICLE
`
`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 of providing multiple beginning instruc-
`tions for navigating the vehicle from a route generator.
`
`10
`
`BACKGROUND OF THE INVENTION
`
`Currentlyit is possible to navigate a vehicle, such as a car,
`using a database onboardthe car that includes directions and
`coordinates for various locations. For example, the database
`may include existing directions and coordinates for the
`entire United States. Such a navigation system is sometimes
`called an autonomousnavigation system.
`In existing autonomous navigation systems,the directions
`for navigating the vehicle are generated by a processor,
`which is also on board the vehicle. The processor accesses
`the database and calculates directions based on the current
`location of the vehicle and the intended destination. Autono-
`
`mous navigation systems are typically very expensive.
`Additionally, these autonomous systems becomeeasily out-
`dated as the coordinates and locations and points of interest
`stored in the database become outdated. Onealternative to
`autonomous navigation systems is to communicate with a
`server that can calculate a navigation route and transmitit to
`the vehicle. Typically, in such a server-based system, the
`current location of the vehicle is determined by the server
`using Global Positioning Systems and software. Dead reck-
`oning systems such as gyroscopesor the use of vehicle speed
`pulses may also be used to help determine the current
`location of the vehicle. The destination is also indicated to
`
`20
`
`25
`
`30
`
`35
`
`the server
`
`2
`instructionsis calculated based on a current location of the
`vehicle and the destination. A distance threshold is deter-
`mined based on the current location of the vehicle and the
`destination. The navigation instructions located within the
`distance threshold are determined and transmitted from the
`route generation application to the vehicle. ‘The navigation
`instructions located within the distance threshold are
`executed at the vehicle. At least one remaining maneuver
`may be transmitted from the route generation application
`while the vehicle executes the navigation instructions
`located within the distance threshold. The at
`least one
`
`remaining maneuver may also be executed at the vehicle.
`The distance threshold may be based on a speed of the
`vehicle or on road density information. The maneuver list
`may also be based on a speed of the vehicle or on road
`density information.
`Another aspect of the present invention provides a navi-
`gation system including at
`least one route generation
`application, which calculates a maneuverlist comprising a
`plurality of navigation instructions. The route generation
`application further determines a distance threshold and
`preliminary navigation instructions that lie within the dis-
`tance threshold. The system also includesat least one service
`manager in communication with the route generation appli-
`cation and a vehicle, which is operatively adapted to execute
`the navigation instructions. The service manager may trans-
`mut the preliminary navigation instructions from the route
`generation application to the vehicle.
`The system also includes at least one database in com-
`munication with the route generation application, the data-
`base comprising location coordinates. The system also
`includesat least one navigation interface in communication
`with the vehicle operatively adapted to receive the naviga-
`tion instructions. The system also includes at
`least one
`communication interface in communication with the
`
`vehicle, the communication interface operatively adapted to
`transmit information from the vehicle.
`
`the server, for example, by user-input. Then,
`Another aspect of the present invention provides a com-
`generates a route based on these two points.
`puter usable medium including a program for generating
`This server-based process may be very time consuming.
`navigation instructions for a vehicle. The program includes
`Sometimes, the process of downloading the maneuverlist
`computer program code that receives a destination of the
`from the vehicle’s current location to the destination may
`vehicle and computer program codethat calculatesalist of
`take a significant amount of time if the maneuver list is
`navigation instructions based on a current location of the
`extensive. This mayresult in missed maneuvers or invalid
`vehicle and the destination. The program also includes
`routes as the vehicle continues beyond the original location
`computer program code that determines a distance thresh-
`upon which the maneuverlists were based. For example, a
`old. The program also includes computer program codethat
`vehicle maypass thefirst maneuver before the instruction to
`determines navigation instructions located within the dis-
`navigate the first maneuver is downloaded. Moreover, cur-
`tance threshold and transmits these instructions to the
`rent server-based navigation systems do not provide off-
`route detection, i.e. an indication that the vehicle has gone
`off the route indicated by the maneuverlist. Additionally,
`current server-based navigation systems do not provide
`off-route correction. That is, because the database is not on
`board, there is a time lag between the time when a vehicle
`goes off-route and when the vehicle receives new maneuver
`instructions. This time lag may occur, for example, because
`the vehicle has to send a new request for a corrected route
`to the server based on a newcurrentlocation.
`
`40
`
`45
`
`vehicle. The program also includes computer program code
`that executes the navigation instructions located within the
`distance threshold at the vehicle. The program also includes
`computer program codethat transmits at least one remaining
`maneuver to the vehicle while the vehicle executes the
`navigation instructions located within the distance threshold.
`The program also includes computer program code that
`executes the at least one remaining maneuverat the vehicle.
`The program also includes computer program code that
`determines the distance threshold based on a speed of the
`vehicle or on road density information. The program also
`includes computer program code that determines the navi-
`gation instructions based on a speedofthe vehicle or on road
`density information.
`Another aspect of the present invention provides a system
`of gencrating navigation instructions for a vehicle. The
`system may include meansfor receiving a destination of the
`vehicle at a route generation application, means for calcu-
`lating a mancuver list based on a current location of the
`
`It would be desirable therefore to provide a method for
`generating instructions for navigating a moving vehicle that
`overcomes the above.
`
`60
`
`SUMMARYOP THE INVENTION
`
`Oneaspect of the present invention provides a method of
`generating navigation instructions for a vehicle. A destina-
`tion of the vehicle is received at a route generation appli-
`cation. A mancuverlist comprising a plurality of navigation
`
`65
`
`

`

`US 6,701,251 B2
`
`3
`vehicle and the destination, the maneuver list comprising a
`plurality of navigation instructions and meansfor determin-
`ing a distance threshold based on the current location of the
`vehicle and the destination. The system may also include
`means for determining navigation instructions located
`within the distance threshold and meansfor transmitting the
`navigation instructions located within the distance threshold
`from the route generation application to the vehicle.
`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 schematic diagram of one embodiment of a
`navigation subsystem in accordance with the present inven-
`tion;
`FIG. 4 is a flow diagram of one embodimentof a method
`for generating navigation information for a vehicle in accor-
`dance with the present invention; and
`FIG. 5 is a sequence diagram of one embodiment of a
`method for generating navigation information for 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 inven-
`tion at 100. The system 100 may include one or more vehicle
`clients 10, one or more carrier systems 20, one or more
`communication networks 30, one or more service manage-
`ment subsystems 40 and one or more navigation subsystems
`50. The service management subsystems 40 may comprise
`one or more service managementapplications 42 and one or
`more service managers 44. The navigation subsystems 50
`may comprise one or more route applications 51, 52 and one
`or more coordinate databases 53, 54.
`Navigation subsystem 50 may be a system for generating
`routes to be delivered to vehicle client 10 and for receiving
`route information from vehicle clicnt 10. Navigation sub-
`system 50 may be connected with or in communication with
`service management subsystem 40. Service management
`subsystem 40 may be used to manage the delivery of
`information to or from navigation subsystem 50 to other
`parts of system 100. 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 subsystem 50 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 reccive information from vehicle clicnt 10. In
`
`one embodimentof the invention, navigation subsystem 50
`comprises one or more route applications 51, 52 and one or
`more coordinate databases 53, 54. For cxample, route appli-
`
`10
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`cations 51, 52 may be any suitable software application for
`generating route information or otherwise processing route
`information. Coordinate databases 53, 54 may be anysuit-
`able databases for storing route information, such as location
`coordinates.
`
`Vehicle client 10 may be any suitable vehicle. The vehicle
`may be an automobile or a passenger-carrying unit, for
`example, a bus or train. Alternatively, vehicle client 10 may
`be an occupant of the vehicle or any suitable client device
`contained in the vehicle.
`In one embodiment of the
`invention, vehicle client 10 is a mobile or portable device
`equipped to communicate with service management sub-
`system 40.
`Carrier system 20 may be any suitable system for trans-
`mitting a signal from vehicle 10 to service management
`subsystem 40. Carrier system 20 mayalso transmit a signal
`from service management subsystem 40 to vehicle client 10.
`In one embodiment of the invention, carrier system 20 is a
`wireless carrier system as is well known in the art. Carrier
`system 20 may be, for example, a transmitter/receiver unit
`attached to vehicle client 10. Alternatively, carrier system 20
`may be a separate transmitter/receiver carried by vehicle
`client 10.
`
`Communication network 30 may be any suitable system
`for communicating between vehicle client 10 and service
`management subsystem 40.
`In one embodiment of the
`invention, communication network is a public switched
`telephone network (PSTN). Alternatively, communication
`network 30 may be a multiprotocol Internet or intranet
`capable of transmitting voice and/or data in either analog or
`digital form or a combination of both. Alternatively, com-
`munication network 30 may be a hybrid communication
`networkor virtual network. Service management subsystem
`40 may be a system for managinga variety of services to be
`delivered to or from vehicle client 10. In one embodiment of
`
`the invention, service management subsystem 40 manages
`services that are distributable over a variety of channels. For
`example, services may be delivered via a live agent, such as
`a humanadvisor, orvia a virtual agent, such as an interactive
`computer program. The structure of service management
`subsystem 40 may enable services to be delivered in a
`uniform mannerregardless of the channel used for delivery
`or of the service being delivered. Service management
`subsystem 40 may maintain a consistent subscriber experi-
`ence and “look and feel” across the products being delivered
`across the service distribution channels enabled.
`
`Service management subsystem 40 may be any suitable
`hardware or software configuration, or combination of hard-
`ware and software that is configured to standardize each
`service being delivered via the subsystem 40 and to stan-
`dardize each channelof delivery. In one embodiment of the
`invention, service management subsystem 40 standardizes
`each service and channel using personalization information
`from vehicle client 10. Thus, service management sub-
`system 40 may have a commonprofile mechanism across
`the services being delivered independent of the service
`distribution channel(live agent, virtual agent, web channel,
`speech channel) and of the service (news, weather, sports,
`stocks, etc.). In one embodiment of the invention, service
`management subsystem comprises one or more application
`components 42 and one or more service managers 44. For
`example, application 42 may be any suitable software appli-
`cation for managing one or more services. Service managers
`44 maybe any suitable hardware and/or software configu-
`ration or structure for executing applications 42.
`FIG. 2 shows another embodiment of a system for pro-
`viding services to a vehicle in accordance with the present
`
`

`

`US 6,701,251 B2
`
`5
`invention at 200. Vehicle-directed service system 200 may
`include a subscriber 210 and a service management appli-
`cation 240. In the embodiment shown in FIG.2, the service
`management subsystem may be in connection with a com-
`munication network 230, such as the Internet. Service man-
`agement application 240 mayalso be in communication with
`service applications or other service management sub-
`systems. For example, in FIG. 2, service management sub-
`system 240 is also in communication with a subsystem for
`processing route information shown at 251. Service man-
`agement subsystem 240 mayalso be in communication with
`a web-based service application or other web-based service
`management systems or webservers. For example, in FIG.
`2, service management application 240 is in communication
`with a web channel 260.
`
`In one embodimentof the invention, service management
`application may include an in-vehicle component 245. This
`in-vehicle component maybe located in, or on or may be in
`communication with vehicle client 210. In one embodiment
`of the invention, the in-vehicle component 245 mayinstall
`a software algorithm, based on the type of call originated
`through a voice command,in order to optimize the talk path
`to subscriber managementapplication 240. System 200 may
`also allow the subscriber to connect to a live administrator
`or advisor 270 through a spoken command acknowledged
`through the subscriber management application 240 voice
`user interface (VUI).
`In one embodimentof the invention, subscriber 210 may
`have VUI access 222 through a PSTN 220. This may serve
`as the primary end user interface to service management
`application 240. This VUI access may allow subscribers in
`their vehicles equipped in accordance with the present
`invention to access a variety of services. For example,
`subscribers 210 may request route information or travel
`information or may provide information about their route,
`using voice commands in a conversational manner.
`Furthermore, the subscriber may havethe ability to interrupt
`or suspend the session if required. In one embodimentof the
`invention, connections are made to the service management
`application 240 through the public telephone system. In one
`embodimentof the invention, subscriber 210 may gain audio
`access to subscriber management application 240 by acti-
`vating an in-vehicle speech recognition application. This
`speech recognition application may allow the subscriber to
`place hands-free cell phone calls.
`Subscriber 210 may also have graphical user interface
`(GUI) access 232 through a communication network 230,
`such as the Internet. Such an interface may allow subscribers
`to access a variety of Internet and communication network-
`based services in accordance with the present invention. For
`example, subscriber 210 may access emailvia this interface.
`In one embodiment of the invention, subscribers connect to
`the service managementapplication 240 throughthe Internet
`230 using standard Web browsers.
`Subscriber 210 may also have GUI access through a web
`channel 260. This interface may be used by subscribers to
`access a variety of services. For example, subscriber 210
`may maintain one or more user profiles using web channel
`260. Subscriber 210 may also set up user-related rules such
`as e-mail consolidation and filtering rules. This interface
`mayalso be uscd to access sclected content services. Vehicle
`data, such as diagnostic codes and messages, can be con-
`solidated and displayed using web channel 260. As with
`other components of system 200, information entered or
`accessed via web channel 260 may then be incorporated into
`new products and services for presentation over other chan-
`nels in communication with service management subsystem
`
`6
`240. The subscribers 210 may connect to the web channel
`260 using standard Web browsers. In one embodimentofthe
`invention, standard web channel software interacts with the
`service management application to update subscriber pro-
`files and/or to obtain informationofinterest. In one embodi-
`ment of the invention, the web channel 260 interface uses a
`dedicated connection to the service management system
`240.
`
`10
`
`System 200 may also include one or more administrators
`270. Administrator 270 may use GUI access to manage
`service management system 240 and information related to
`system 200. Administrator 270 may be, for example, a live
`advisor available to advise subscriber 210. Administrator
`
`270 may also be, for example, an individual maintaining or
`administering service management subsystem 240. In one
`embodiment of the invention, administrator 270 accesses
`service management subsystem 240 via subscriber manage-
`ment subsystem 250. For example, administrator 270 may
`send configuration and subscriber information to service
`management system 240. Administrator 270 may also
`receive notifications of interesting events within system 200.
`In one embodimentof the invention, subscriber management
`subsystem 250 uses a dedicated connection between admin-
`istrator 270 and service management system 240.
`As seen in FIG. 2, system 200 may also include one or
`more message servers 234. These messages may be, for
`example, voice or text or e-mail mail messages. In one
`embodimentof the invention, message servers 234 commu-
`nicate with service management application 240 via Internet
`230. Thus, subscribers 210 may reccive incoming email
`messages from, and send outgoing e-mail messages to,
`external mail transport agents using any suitable messaging
`protocol as is well known in the art. Message servers 234
`may also be usedto retrieve subscribers’ e-mail from outside
`mail storage servers for consolidation into their e-mail
`accounts connected to system 200.
`As seen in FIG. 2, system 200 may also include one or
`more news and or sports feeds 236. In one embodiment of
`the invention, feeds 236 are provided by a network news
`contentprovider. Feeds 236 may be used to receive and store
`audio news and sports stories for playback to interested
`subscribers 210. The primary interface between the speech
`channel and news content provider 236 may be via the
`Internet 230. In one embodimentof the invention,a satellite
`feed 246 serves as a backup mechanism.
`As seen in FIG. 2, system 200 may also include one or
`more weather services 248.
`In one embodiment of the
`invention, the services are provided by any suitable weather
`reporting service. Weather services 248 may be used to
`receive and store regional and local weather information for
`playback to interested subscribers 210. Furthermore,
`the
`weather content can be delivered based on the vehicle
`location by coordinating the weather zone with the vehicle
`GPS location. The weather service 248 and/or content feed
`maybe co-located with the service managementsystem 240.
`System 200 mayalso include one or morefinance services
`238. For example, stock quotes may be provided to the
`subscriber. Any suitable finance technology may be used to
`provide these services to interested subscribers.
`In the
`embodiment of FIG. 2, the finance information is obtained
`al the ime of the request through Internet attached content
`sources or dedicated connections 230 as is known in the art.
`
`System 200 may also include other services to be deliv-
`ered in addition to news, weather, sports and finance services
`as described above. For example, yellow pageslistings,
`special interest content (c.g., movie or restaurant revicws),
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`US 6,701,251 B2
`
`7
`travel
`content related to the location of the vehicle (e.g.
`profiles of nearby tourist attractions) or content related to
`navigation of the vehicle mayall be delivered via system
`200.
`
`FIG. 3 shows one embodimentof a navigation system in
`accordance with the present invention at 300. Navigation
`system 300 may include one or more navigation clients 310,
`312. Each navigation client 310, 312 may have an in-vehicle
`navigator 321, 322. Navigation system 300 mayalso include
`one or more route generation applications 351, 352. Navi-
`gation system 300 mayalso include one or more coordinate
`databases 353, 354.
`Navigation clients 310, 312 may be a vehicle client as
`described above.
`
`In-vehicle navigator 321, 322 may be any suitable com-
`ponentof navigation client 310, 312 which may be used to
`navigate vehicle client 310. 312. For example, in-vehicle
`navigator 321, 322 may be a driver. Alternatively, in-vehicle
`navigator 321, 322 may be an automatic system for navi-
`gating vehicle 310, 312.
`Route generation applications 351, 352 may be any suit-
`able application for calculating maneuver lists of directions
`between one or more locations. For example, route genera-
`tion applications 351, 352 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 applications 351, 352 are in
`communication with coordinate databases 353, 354.
`Route generation applications 351, 352 may generate
`navigation information in any suitable manner. For example,
`route generation applications 351, 352 may generate routes
`using geocoding. That is, the application 351, 352 deter-
`mines a corresponding latitude and longitude based on an
`input navigation address. Alternatively,
`route generation
`applications 351, 352 may generate routes using reverse
`geocoding. That is, the application 351, 352 determines a
`corresponding navigation address based on input latitude
`and longitude coordinates.
`Coordinate databases 353, 354 may be anysuitable data-
`bases for storing such location coordinates as latitude and
`longitude of a variety of locations. These locations may be,
`for example, points of interest. Coordinate databases 353,
`354 may also be a database of street addresses. Coordinate
`databases 353, 354 mayalso be a database of routes between
`points.
`FIG. 4 showsa flow diagram of one embodiment of a
`method for generating navigation information in accordance
`with the present invention at 400.
`As seen at block 405, a call may be received from vehicle
`client 310, 312. For example, this call may be a request
`transmitted from the vehicle indicating a request for direc-
`tions. Alternatively, the call may comprise a transmission of
`the coordinates of the vehicle. As described above, the call
`may be one or more voice commands from vehicle client
`310, 312. For example, service management subsystem 40
`may communicate with vehicle client 310, 312 via a VUI or
`GUL.
`
`As seen at block 410, the route generation application
`351, 352 may be contacted. This contact may occur, for
`example, via a service management subsystem as described
`above. Alternatively, vehicle client 310, 312 may contact the
`route generation application directly.
`As seen at block 415, the vehicle’s destination may be
`reccived from the vehicle clicnt 310, 312. This may take the
`
`10
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`form of a requestfor a particular destination from the service
`management subsystem and a response from the vehicle
`client. Alternatively, this may take the form of a request from
`route generation application 351, 352 and a response from
`the vehicle client. kor example, vehicle client 310, 312 may
`provide a destination to route generation application 351,
`352. Vehicle client 310, 312 may provide the destination via
`any suitable means,
`for example, voice commands.
`Alternatively, an in-vehicle hardware component as
`described above may automatically transmit the destination.
`The destination mayalso be determined from a pre-stored
`address book, for example, an address book stored in any
`suitable place within system 100, 200 that
`includes the
`current destination of the vehicle. Thatis, the vehicle client
`310, 312 mayindicate that the destination is “Home”and the
`actual coordinates may already be pre-stored for example, in
`the vehicle, in a database in communication with the vehicle
`client or in a database in communication with the route
`
`generation application.
`As seen at block 420, route generation application may
`then calculate a list of maneuvers to be navigated from the
`current location of the vehicle client 310, 312. These maneu-
`vers may be, for example, maneuvers to be navigated in
`order to reach the destination indicated at block 415. These
`
`maneuvers or navigation instructions may be calculated
`using any standard methods. In one embodiment of the
`invention,
`the maneuvers are calculated based on graph
`theory or are based on a shortest path algorithm, such as
`Dijkstra’s algorithm. Alternatively, the maneuverlist may be
`calculated based on an A* algorithm which includes heu-
`ristics or other information for pointing the vehicle in the
`appropriate direction.
`The maneuvers may be calculated by determining the
`current location and calculating to the destination location.
`Alternatively, the maneuvers may be calculated using the
`destination location and calculating to the current location.
`Alternatively, the maneuvers may be calculated by first
`using the current location and calculating to an x maneuver,
`where x may be any number. Alternatively, the maneuvers
`may be calculated by using an x maneuver and calculating
`to the current
`location. For example,
`the A* algorithm
`utilizes an evaluation function to determine the shortest
`
`
`
`distance from the navigation client’s starting location to a
`destination. As another example, a variant of Djikstra’s
`algorithm calculates maneuvers in a forward and backward
`direction and, beginning at the first maneuver point, calcu-
`lates to the current location by probing outall road sections
`and intersections. Alternatively, the maneuvers may becal-
`culated using a main maneuver point (such as, but not
`limited to, the first maneuverpoint or the x maneuverpoints)
`and calculating to the destination while the destination is
`also being calculated towards the current or starting point.
`The maneuvers may be calculated such that the destination
`is used to help eliminate alternate paths as an appropriate
`path is