(12) United States Patent
`Jin et al.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006654683B2
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,654,683 B2
`Nov. 25, 2003
`
`(54) METHOD AND SYSTEM FOR REAL-TIME
`NAVIGATION USING MOBILE
`TELEPHONES
`
`5,528,248 A
`5,579,535 A
`5,610,821 A
`
`6/1996 Steiner et a!.
`11/1996 Orlen et a!.
`3/1997 Gazis et a!.
`
`.............. 342/357
`............... 455/33.1
`............. 364/444.2
`
`(76)
`
`Inventors: HaiPing Jin, 2502 Arrowood La., San
`Jose, CA (US) 95130; Yi-Chung Chao,
`1027 Nova Ct., Milpitas, CA (US)
`95035; Longxue Li, 20875 Valley
`Green Dr. #31, Cupertino, CA (US)
`95014; Ruslan Adikovich Meshenberg,
`1000 Keily Blvd., Santa Clara, CA (US)
`95051; Kentaro Tokusei, 810 Coleman
`Ave. #15, Menlo Park, CA (US) 94025;
`Salman Dhanani, 9634 179th Pl. NE.
`#4, Redmond, WA (US) 98052
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 41 days.
`
`(21) Appl. No.: 09/884,841
`
`(22) Filed:
`
`Jun. 18,2001
`
`(65)
`
`Prior Publication Data
`
`US 2002/0029107 A1 Mar. 7, 2002
`
`Related U.S. Application Data
`
`(List continued on next page.)
`
`FOREIGN PATENT DOCUMENTS
`
`DE
`wo
`
`196 21 424 A1
`99/27742
`
`12/1997
`6/1999
`
`OTHER PUBLICATIONS
`
`Supplementary European Search Report, dated Nov. 14,
`2002, for Application Number Ep 00967228.
`International Search Report, dated Dec. 19, 2002, for Inter(cid:173)
`national Application No. PCT/US02/02323, filed Jan. 24,
`2002.
`International Search Report, dated Mar. 26, 2001, for Inter(cid:173)
`national Application No. PCT/US00/35075, filed Dec. 21,
`2000.
`International Search Report, dated Jan. 4, 2001, for Inter(cid:173)
`national Application No. PCT/US00/27083, filed Sep. 27,
`2000.
`International Search Report, dated Jan. 12, 2001, for Inter(cid:173)
`national Application No. PCT/US00/26921, filed Sep. 27,
`2000.
`
`Primary Examiner-Tan Nguyen
`
`(57)
`
`ABSTRACT
`
`( 63) Continuation-in-part of application No. 09/547,421, filed on
`Apr. 11, 2000, now Pat. No. 6,266,615.
`( 60) Provisional application No. 60/156,225, filed on Sep. 27,
`1999, and provisional application No. 60/211,994, filed on
`Jun. 16, 2000.
`Int. Cl? ................................................ G01C 21/26
`(51)
`(52) U.S. Cl. ........................ 701/207; 701!210; 340/995
`(58) Field of Search ................................. 701/201, 202,
`701!205, 207, 209, 208, 210; 455/456;
`340/990, 995
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,278,424 A * 1!1994 Kagawa ................. 250!559.37
`
`In an Interactive Real-Time Distributed Navigation system
`a method and system is disclosed for implementing a warm
`start/cold start option. Through selection of the warm start
`option, an interactive session for providing navigational
`directions to a user is more quickly established because a
`user's position is assumed not to be ambiguous. A method of
`the invention verifies this assumption. Through selection of
`the cold start option, the method of the invention seeks to
`remove ambiguity in a user's position before providing
`navigational directions. If, however, a user's position is not
`ambiguous, the method of the invention reverts to a warm
`start condition to immediately transmit navigational direc(cid:173)
`tions to the user.
`
`32 Claims, 7 Drawing Sheets
`
`Google 1025
`U.S. Patent No. 9,445,251
`
`

`

`US 6,654,683 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,742,131 A
`5,742,509 A
`5,774,828 A
`5,774,829 A
`5,838,562 A
`5,884,218 A
`5,902,350 A
`5,904,728 A
`5,910,177 A
`5,912,635 A
`5,922,042 A
`5,928,295 A
`5,928,307 A
`5,933,100 A
`5,938,720 A
`5,938,721 A
`5,987,381 A
`6,014,090 A
`6,021,371 A
`
`4/1998 Sprout et a!. ............... 455!456
`4/1998 Goldberg et a!.
`........ 364/449.5
`6/1998 Brunts et a!. ............... 701!210
`6/1998 Cisneros et a!. ............ 701!213
`11/1998 Gudat et a!. .. .. ... ... . 364/424.02
`3/1999 Nimura et a!. .............. 701!208
`5/1999 Tarnai et a!. ................ 701!211
`5/1999 Tarnai et a!. ................ 701!211
`6/1999 Zuber ......................... 701!202
`6/1999 Oshizawa et a!.
`.......... 340/988
`7/1999 Sekine et a!. ............... 701!210
`7/1999 Geier .......................... 701!29
`7/1999 Oshizawa et a!.
`.......... 701!210
`8/1999 Golding ...................... 340/995
`8/1999 Tarnai ........................ 701!209
`8/1999 Dussell et a!. .............. 701!211
`11/1999 Oshizawa ................... 701!209
`1/2000 Rosen et a!. . . . . . . . . . . . . . . . . 340/905
`2/2000 Fultz .......................... 701!200
`
`6,029,069 A
`6,032,098 A *
`6,055,478 A
`6,070,123 A
`6,107,944 A
`6,112,099 A
`6,115,700 A
`6,148,261 A
`6,154,658 A
`6,175,806 B1
`6,175,807 B1
`6,199,045 B1
`6,205,400 B1
`6,208,295 B1
`6,243,657 B1
`6,266,615 B1
`6,269,306 B1
`6,401,035 B2
`6,405,123 B1
`* cited by examiner
`
`2/2000
`2/2000
`4/2000
`5!2000
`8/2000
`8/2000
`9/2000
`11/2000
`11/2000
`1!2001
`1!2001
`3/2001
`3/2001
`3/2001
`6/2001
`7/2001
`7/2001
`6/2002
`6/2002
`
`Takaki ........................ 455!456
`Takahashi et a!.
`.......... 701!210
`Heron ........................ 701!213
`Beyer et a!. . . . . . . . . . . . . . . . . 701!209
`Behr et a!. . . . . . . . . . . . . . . . . . . 340/995
`Ketola ........................ 455/466
`Ferkinhoff et a!. ............ 706/13
`Obradovich et a!. . . . . . . . . 701!208
`Caci ........................... 455/466
`Thuente ...................... 701!213
`Buchler et a!.
`. . . . . . . . . . . . . 701!220
`Giniger et a!. . . . . . . . . . . . . . . . . . 705/1
`Lin ............................ 701!214
`Dogan et a!. ............... 342/378
`Tuck et a!.
`................. 702/150
`Jin ............................. 701!213
`Ibrahim et a!.
`............. 701!214
`Jin ............................. 701!213
`Rennard et a!.
`. . . . . . . . . . . . 701!200
`
`

`

`112
`
`• FOR EXAMPLE,
`UP .LINK OR OTHER
`WIRELESS ISPs
`
`DISTRIBUTED l
`
`NAVIGATION
`SERVERS
`
`/
`
`• • • • •
`
`DISTRIBUTED
`NAVIGATION
`SERVERS
`
`112
`
`·WIRELESS
`PHONES OR PDAs
`WITH POSmON
`CAPABIUTY
`
`INTERACTIVE REAL TIME DISTRIBUTED NAVIGATION SYSTEM-ARCHITECTURE A
`FIG.1
`
`d •
`\Jl
`•
`~
`~ ......
`~ = ......
`
`z
`0
`~
`N
`~Ul
`
`N c c
`
`~
`
`'JJ. =-~
`~ .....
`'"""' 0 ......,
`
`-..J
`
`e
`rJ'l
`-..a-..
`a-..
`(It
`~
`0..,
`00
`~
`~
`N
`
`

`

`102
`
`10L1
`
`110
`I
`
`112
`I
`
`DIRECT r---J DISTRIBUTED
`
`NAVIGATION
`SERVERS
`
`LINKS
`
`-
`
`INTERACTIVE REAL TIME DISTRIBUTED NAVIGATION SYSTEM-ARCHITECTURE 8
`
`·WIRELESS
`PHONES OR PDAs
`WITH POSITION
`CAPABILI1Y
`
`FIG.2
`
`d •
`'J).
`•
`~
`~ ......
`~ = ......
`
`z
`0
`~
`N
`~Ul
`
`N c c
`
`~
`
`'JJ. =(cid:173)~
`~ .....
`N
`0 ......,
`-..J
`
`e
`rJ'l
`-..a-..
`a-..
`(It
`-..~
`a-..
`00
`~
`~
`N
`
`

`

`U.S. Patent
`
`Nov. 25, 2003
`
`Sheet 3 of 7
`
`US 6,654,683 B2
`
`TX DIRECTIONS
`TO CLIENT
`/
`322
`
`CLIENT TX } POSITION INFO ~ 302
`SERVER RX
`.
`
`--304
`
`y
`QUERY DB ~ 306
`
`GENERATE LIST
`
`~308
`
`CONSOLIDATE LIST
`
`~310
`
`SERVER TX } LIST
`CLIENT RX
`
`~312
`
`USER SELECT
`
`-- 314
`
`S~~ ~}SELECTION - -
`
`316
`
`CALCULATE LOCATION - -
`
`318
`
`~--~N~~~y--~
`
`~~320
`
`FIG.3
`
`

`

`U.S. Patent
`
`Nov. 25, 2003
`
`Sheet 4 of 7
`
`US 6,654,683 B2
`
`POSITION
`INFO.
`302
`
`DISPLAY
`CANDIDATES
`
`USER
`SELECTION
`314
`
`PROMPT USER WITH
`NAV. INSTRUCTIONS
`322
`
`~
`
`102
`
`GENERATE
`CANDIDATE LIST
`308
`
`CONSOUDATE
`UST
`310
`
`CALCULATE
`LOCATION
`304
`
`QUERY
`DATABASE
`306
`
`FIG.4
`
`(
`112
`
`

`

`VOICE OR/ AND TEXT
`
`GRAPHICS
`
`-
`
`- -
`
`• YOU ARE APPROACHING
`GROVE AVE, IN ABOUT 5
`MINUTES (OR 200 YARDS)
`YOU SHOULD TURN RIGHT
`
`\
`
`J
`
`\
`
`I
`
`/
`
`. "'\I"\...
`
`'< ~ .,d,
`
`I
`
`I_~/ ~"~~504
`
`'""' ~ ~
`
`502
`
`•IF YOU ARE ON
`EL CAMINO REAL, SAY OR
`PUSH "1"
`·IF YOU ARE ON ALMA
`SAY OR PUSH "2"
`
`INTERACTIVE REAL TIME DISTRIBUTED NAVIGATION SYSTEM-USER END FUNCTIONS
`FIG.5
`
`d •
`\Jl
`•
`~
`~ ......
`~ = ......
`
`z
`0
`~
`N
`~Ul
`
`N c c
`
`~
`
`'JJ. =(cid:173)~
`~ .....
`Ul
`0 ......,
`-..J
`
`e
`rJ'l
`-..a-..
`a-..
`(It
`-..~
`a-..
`00
`~
`~
`N
`
`

`

`U.S. Patent
`
`Nov. 25, 2003
`
`Sheet 6 of 7
`
`US 6,654,683 B2
`
`F< ~-------------'
`
`Select: Cold/Warm
`Start?
`
`602
`
`Position Info:
`Client TX, Server RX
`
`612
`
`,
`
`Warm
`
`TX Directions
`To Client
`
`604
`
`No
`
`Ambiguous Position?
`
`Position Info:
`Client TX, Server RX
`
`Yes
`
`614
`
`606
`
`Remove Ambiguity .._ __ _..:.Y...:::e.::..s--<
`of Position
`
`Ambiguous Position?
`
`1
`
`616
`
`No
`
`608
`
`TX Directions
`To Client
`
`TX Directions
`To Client
`
`TX Directions
`To Client
`
`618
`
`620
`
`610
`
`FIG. 6
`
`

`

`U.S. Patent
`
`Nov. 25, 2003
`
`Sheet 7 of 7
`
`US 6,654,683 B2
`
`Wireless
`Device
`102
`
`....
`....
`
`..
`_ ...
`
`VoiceXJv.IL
`Interpreter~rovvser
`702
`
`..
`..
`
`Serv let Engine
`704
`
`_...
`...
`
`Servlet
`706
`
`FIG. 7
`
`

`

`US 6,654,683 B2
`
`1
`METHOD AND SYSTEM FOR REAL-TIME
`NAVIGATION USING MOBILE
`TELEPHONES
`
`This application is a continuation-in-part of Ser. No.
`09/547,421 Apr. 11, 2000 U.S. Pat. No. 6,266,615 and
`claims benefit of No. 60/156,225 Sep. 27, 1999 and claims
`benefit of No. 60/211,994 Jun. 16, 2000.
`
`I. FIELD OF THE INVENTION
`
`This invention relates to navigation systems and location
`based information delivery. Specifically, this invention
`relates to a method and system for delivering interactive and
`real-time navigational information using distributed naviga(cid:173)
`tion information processing and mobile telephones.
`
`II. BACKGROUND OF THE INVENTION
`
`Many navigation systems are based on satellite-based
`global positioning system (GPS) devices which have been
`applied in automobile navigation systems, see, e.g., U.S. Pat.
`Nos. 5,938,720, 5,928,307, 5,922,042, 5,912,635, 5,910,
`177, 5,904,728, 5,902,350, all incorporated herein by refer(cid:173)
`ence for all purposes. Such automobile navigation systems,
`however, are expensive and inconvenient to use. Many such
`systems are further not appropriate for walking. Therefore,
`there is a great need in the art to incorporate navigation
`systems in personal handheld devices.
`However, there are several technical obstacles that pre(cid:173)
`vent the incorporation of navigational capabilities in hand(cid:173)
`held devices for providing turn-by-turn real-time navigation
`services. One such obstacle is the amount of geographic data
`needed to provide reasonably detailed navigational informa(cid:173)
`tion. Small handheld devices include cellular phones, per(cid:173)
`sonal digital assistants, or computers, however, the amount
`of embedded memory is limited and is impractical to store
`a large amount of geographic information. In existing auto(cid:173)
`mobile navigation systems, GPS systems are employed to
`provide information about the location and movement of a
`user. Geographic information is usually stored in a geo- 40
`graphic mapping database stored on a CD-ROM, hard-disk
`drive device or other large capacity storage medium.
`Another obstacle is that the lack of information process(cid:173)
`ing power of small devices such as those mentioned above.
`For example, the information processing power of a cellular 45
`telephone is typically provided by an embedded micropro(cid:173)
`cessor with limited memory. While the information process(cid:173)
`ing power of embedded microprocessors is generally
`increasing, such processors are still not suitable for proces(cid:173)
`sor intensive real-time navigational tasks.
`An additional obstacle is the insufficient location accuracy
`provided by current technology. Initial sources of inaccuracy
`of the GPS based systems, for example, are either imposed
`by the U.S. Department of Defense through Selective Avail(cid:173)
`ability (S/ A), other sources of error are due to atmospheric 55
`and timing errors limiting the accuracy of a single GPS
`receiver to +!-50 meters. Methods exist which can be used
`to enchance accuracies to +/-5 meters. Such methods
`include Enhanced GPS systems (i.e., SnapTrack) and net(cid:173)
`work based system (i.e., Truepoint). These methods use a 60
`known position, such as a survey control point, as a refer(cid:173)
`ence point to correct the GPS position error. These methods
`of correcting GPS positions are referred to as Differential
`GPS or DGPS. The DGPS corrections can be applied to the
`GPS data in real-time using data telemetry (radio modems). 65
`Toward expanding the use of DGPS, the United States and
`Candian Coast Guard are establishing a series of radio
`
`20
`
`2
`beacons to transmit the DGPS corrections for accurate
`navigation along the Great Lakes, the Mississippi River and
`tributaries, the Gulf Coast, and the Eastern and Western
`coasts of North America. However, such radio beacons are
`5 not available to consumers traveling in most inland loca(cid:173)
`tions.
`Location information that is ambiguous due to a number
`of factors discussed above makes navigational systems
`difficult to develop. For example, if the user is driving in a
`10 downtown area with streets spaced close together, a GPS
`location within +/-50 meters is not adequate to give turn(cid:173)
`by-turn directions. The GPS location information is thus
`considered ambiguous and inappropriate for navigation sys(cid:173)
`tems. In other situations, a GPS location within +/-50 meters
`15 is adequate for navigation purpose. For example, if a user is
`driving on a highway in a remote area without any nearby
`exits, the GPS location is sufficient for calculating further
`navigation directions. Thus, in such a situation, the GPS
`location is not ambiguous.
`Current automobile GPS navigation systems make use of
`other sensors, such as accelerometers, speedometers, etc.
`plus some sophisticated filtering technology to improve the
`accuracy of a navigational system (see, e.g., U.S. Pat. No.
`5,912,635, previously incorporated by reference for all
`25 purposes). In addition, many automobile-based navigational
`systems use map-aiding technology as well. However, for a
`navigational system implemented using handheld devices
`such as cellular telephones, it is impractical to have the
`handheld devices connected to external sensors, especially
`30 when the device is used while walking.
`Accordingly, it would be desirable to provide a naviga(cid:173)
`tional system that provides accurate navigational instruc(cid:173)
`tions. It would further be desirable to provide a navigational
`system that can be implemented on an existing infrastructure
`and is adaptable to new infrastructures as they become
`available.
`It would further be desirable to provide a navigational
`system that can be implemented on handheld devices with
`limited computational power as well as devices with
`enhanced computational power.
`It would further be desirable to provide a navigational
`system that can make use of many forms of real time
`information to provide accurate location calculations as well
`as optimal navigation paths.
`
`35
`
`III. SUMMARY OF THE INVENTION
`These and other objects are provided for by a system and
`method for interactive real-time distributed navigation. In an
`50 embodiment of the invention, a user advantageously makes
`use of an often under-utilized sensor-a user's eyes. Toward
`reducing an ambiguity associated with a location derived
`from a positional sensor, the present invention prompts for
`and utilizes a user's input. In an embodiment, a consolidated
`list of candidate locations are presented to a user. A user's
`selection from such list is then used to correct for errors in
`other position detecting sensors.
`In another embodiment of the invention, an enhanced and
`simplified dynamic real-time navigation system is provided
`based upon distributed computing and database systems. In
`such a manner, wireless devices with limited computational
`power interact with distributed servers that execute any
`necessary intensive processing. In another embodiment,
`geographic map information databases are advantageously
`stored on distributed servers with large storage capacity.
`In another embodiment, depending upon the capability of
`a user's device, data storage and navigation calculation load
`
`

`

`US 6,654,683 B2
`
`4
`FIG. 6 is a flowchart of a method for providing warm
`start/cold start options in an Interactive Real-time Distrib(cid:173)
`uted Navigation System; and
`FIG. 7 is a schematic showing an embodiment for gen(cid:173)
`s erating voice code at runtime in an Interactive Real-time
`Distributed Navigation System.
`
`V. DETAILED DESCRIPTION OF THE
`EMBODIMENTS
`
`3
`are dynamically distributed between the server and the
`device. In an embodiment, a user sends a request to navigate
`from a current location (or point A) to point B. A server, after
`receiving the request (including destination information)
`and user's location, the system of the present invention
`generates a global navigation route across several small
`geographic areas. The server then sends navigational infor(cid:173)
`mation relating to a first small geographic area to the user's
`device. Once the user moves out of the first small geographi-
`cal area, the information will be updated by the server either 10
`at the request of the user's device or initiated by the server
`based upon the location of the user.
`Another aspect of the invention provides navigation guid(cid:173)
`ance based on real-time traffic conditions. The traffic infor(cid:173)
`mation can be obtained from a group of navigational service
`users, by observing their speeds and making comparisons
`with the nominal street speed limits in a map database. This
`traffic information assists the system to determine an optimal
`route for its users in real-time. At each juncture, the system
`will dynamically determine an optimal path to get to the 20
`destination based on the traffic information. The best route
`can be defined based on the user's request, for example, it
`can be either time or gas consumption which will be
`minimized.
`Another embodiment of the invention provides directions 25
`in a queue ahead of time. This is particularly important for
`wireless device navigation because of the small screen. For
`example, the server prompts, either by voice or text, "you
`are going to see University Ave. in about 5 minutes (or 500
`yards), where you should turn right." In the mean time, if not
`necessary, the communication link can be released to reduce
`the server traffic.
`Yet another embodiment of the invention provides for
`warm/cold start operation. In a warm start situation, a
`position is assumed not to be ambiguous such that a navi(cid:173)
`gational session is immediately provided to a user. In such
`a warm start situation, however, a method is provided for
`assuring that a warm start session is appropriate. Where
`appropriate, the warm start session continues. Where not
`appropriate, the warm start session reverts to methods for
`removing ambiguity of a user's location. Where a cold start
`session is selected, a method of the invention checks
`whether conditions for a warm start are met. Where warm
`start conditions are met, a user's position is not ambiguous 45
`such that a navigational session is immediately provided to
`the user.
`
`30
`
`Reference will now be made in detail to the preferred
`embodiments of the invention, examples of which are illus(cid:173)
`trated in the accompanying drawings. While the invention
`will be described in conjunction with the preferred
`embodiments, it will be understood that they are not
`15 intended to limit the invention to these embodiments. The
`invention is intended to cover alternatives, modifications
`and equivalents, which may be included within the spirit and
`scope of the invention as defined by the appended claims.
`As will be appreciated by one of skill in the art, the
`present invention may be embodied as a method, data
`processing system or program products. Accordingly, the
`present invention may take the form of navigation systems,
`navigation methods, navigation devices, navigation
`software, etc. Software written according to the present
`invention is to be stored in a form of computer readable
`medium, such as memory, or CD-ROM, to be transmitted
`over a network, and executed by a processor.
`A key component of a navigation system is the determi(cid:173)
`nation of the location (or position) of a user. It is intended
`that the term location (referred to herein as the measurement
`of a geographic location) includes information related to the
`position of an object. A location may contain three dimen(cid:173)
`sional information that completely define the exact position
`35 of an object. In some embodiments, a location may contain
`two dimensional information to define an object in a two
`dimensional space. In some additional embodiments, a loca(cid:173)
`tion may contain information that is not sufficient to com(cid:173)
`pletely define the position of an object. Broadly defined
`40 location, as used herein, also may include speed, time,
`direction of movement, etc. of an object.
`One skilled in the art would appreciate that the format of
`location information is not critical to some embodiments of
`the invention. For example, in some embodiments, location
`information is presented in the format of (x, y), where x and
`y are two ordinates define the geographic location of an
`object, i.e., a user.
`FIG. 1 shows an architecture for an Interactive Real-Time
`Distributed Navigation System in accordance with a pre-
`so ferred embodiment. The various components and their inter(cid:173)
`action will now be described. It is to be understood that
`where like numerals are used in different figures, such like
`numerals refer to the same item. Wireless device 102 may
`take the form of a cellular telephone, satellite telephone,
`ss wireless Personal Digital Assistant (PDA), personal com(cid:173)
`puter or other suitable device having wireless communica(cid:173)
`tions capability. Wireless device 102 is equipped with posi(cid:173)
`tioning capability that takes the form of, for example, global
`positioning systems (GPS), emergency 911 (E911) location,
`60 or some other positioning systems as they become available.
`One skilled in the art will appreciate that the present
`invention is not limited to any particular positioning tech(cid:173)
`nology. In an embodiment, wireless device 102 is manufac(cid:173)
`tured with built-in positioning capabilities Advantageously,
`65 wireless device 102 does not need to carry map information,
`can carry a predetermined amount of map information,
`depending on the wireless device's 102 storage capability.
`
`IV. BRIEF DESCRIPTION OF THE DRAWINGS
`
`The accompanying drawings, which are incorporated in
`and form a part of this specification, illustrate embodiments
`of the invention and, together with the description, serve to
`explain the principles of the invention:
`FIG. 1 is a schematic showing an embodiment of the
`Interactive Real-time Distributed Navigation System- Archi(cid:173)
`tecture A (Internet);
`FIG. 2 is a schematic showing another embodiment of the
`Interactive Real-time Distributed Navigation System- Archi(cid:173)
`tecture B (Direct links);
`FIG. 3 is a flowchart of a method for navigation according
`to the invention;
`FIG. 4 is a schematic showing a method for navigating
`according to the invention;
`FIG. 5 is a schematic showing one embodiment of the
`Interactive Real-time Distributed Navigation System- User
`end;
`
`

`

`US 6,654,683 B2
`
`5
`
`5
`Such a system is described as a distributed system and will
`be further discussed below.
`In an embodiment, the capabilities of wireless device 102
`are enhanced through interfacing with modular attachments.
`A major function of wireless device 102 is to provide an
`interface between the invention and a user. Furthermore; as
`will be described more fully below, wireless device 102
`provides a user interface 105 for displaying graphical,
`textual or audible information. User interface 105 incorpo(cid:173)
`rates the user's sensory capabilities within the invention. 10
`User interface 105 is used to allow user interaction with
`electromechanical components of the invention. Such inter(cid:173)
`action is used to improve the positioning accuracy of the
`invention where interaction achieved through text, graphics
`or audible signals are within the scope of the invention.
`Because wireless device 102 is capable of relaying infor(cid:173)
`mation to a user by means of audible signals or through text
`messages displayed on wireless device 102, embodiments of
`the invention make use of audible sound producing devices,
`as well as, text displaying devices. Where a text displaying
`device is used, enhanced performance is achieved through a
`wireless device 102 capable of displaying several lines of
`text. An enhanced video display is also appropriate for
`wireless device 102 as maps and enhanced directional
`information are displayed on such devices. In another
`embodiment, wireless device 102 is directionally oriented
`through gyroscopic or geomagnetically enhancements,
`which are then used by the device or server to provide real
`time position and orientation information. One of skill in the
`art realizes that many more implementations are possible for
`wireless device 102 without deviating from the teachings of
`the invention.
`As further shown in FIG. 1, wireless carrier 104 provides
`wireless connectivity between wireless device 102 and dis(cid:173)
`tributed navigation servers 112 to be described further
`below. Examples of wireless carrier 104 include cellular
`telephone carriers, satellite communications carriers or glo(cid:173)
`bal positioning system carriers. In achieving wireless
`connectivity, wireless carriers provide an existing infrastruc(cid:173)
`ture for the wireless devices and distributed navigation
`servers. In an embodiment, GPS is used along with the
`government imposed selective availability. One with skill in
`the art will understand that where such limitation is
`removed, the present invention can further be enhanced.
`Because of the adaptive interaction with the user, informa(cid:173)
`tion ranging from general to very specific is relayed to the
`user for a wide range of navigational applications.
`While keeping within the teachings of the invention
`wireless carrier 104 provides positioning information such
`as through GPS, E911 or other positioning systems. 50
`Alternatively, positioning information is obtained through a
`third party and is then used by wireless carrier 104. For
`example, wireless service resellers, wireless internet service
`provides (ISPs), or satellite wireless carriers, among others,
`provide the services necessary to practice the invention. 55
`Importantly, wireless throughput and bandwidth continues
`to increase-through the advent of digital transmission and
`through other techniques. Analog (i.e., AMPS) systems
`provide for a certain level of service. However, more
`advanced digital transmission techniques, such as, but not 60
`limited to GSM, TDMA, CDMA, provide higher data
`throughput. At the time of the invention, CDMA provides
`the highest throughput of information, however, it is
`expected that wireless technology will further be developed.
`Because of its broad application, the present invention is 65
`appropriate for these and many other transmission tech(cid:173)
`niques. In an embodiment of the invention, wireless carrier
`
`6
`104 receives analog or digital information from the wireless
`device 102 and directs such information to other compo(cid:173)
`nents of the invention. Similarly, wireless carrier 104
`receives information from components of the invention and
`then directs such information to wireless device 104.
`As shown in FIG. 1, wireless carrier 104 is connected to
`gateway 106 which provides an interface to network 108.
`Gateway 106 is provided by, among others, wireless carriers,
`ISPs, or other telecommunications providers. In an embodi(cid:173)
`ment of the invention, network 108 is the Internet. The
`Internet provides advantages because it is a widely distrib-
`uted network reaching many areas of the world. In another
`embodiment, network 108 is implemented as a proprietary
`network. By implementing a specialized network, network
`15 108 may be customized to provide minimal latency and
`optimal performance.
`As shown in FIG. 1, a plurality of distributed navigation
`servers 112 are incorporated as part of the invention by
`communicating using network 108. Distributed navigation
`20 servers 112 store street map information and point of interest
`information and further perform processing tasks. In this
`manner, wireless device 102 is not burdened with carrying
`all the necessary information for proper navigation. In an
`embodiment, distributed navigation servers 112 also process
`25 location specific information such as real-time traffic infor(cid:173)
`mation. In an embodiment, traffic information is obtained
`from a group of navigation service users. By observing and
`comparing their positions, speeds and times, and making
`further comparisons with nominal street speed limits in a
`30 map database, real-time traffic information is generated and
`then used by the invention. At each juncture towards a
`destination, the system dynamically determines the optimal
`route for a particular user responsive to ever changing
`conditions. For example, where due to changed conditions a
`35 first route becomes less optimal, a second route is generated
`and presented to a user. An optimal route is determined in
`several ways depending on a user's preference. For example,
`an optimal route can be based on minimum time, minimum
`distance or minimum consumption of fuel. Processor inten-
`40 sive functions such as navigation guide algorithms are
`processed by distributed navigation servers 112 so as to
`reduce the computational burden on wireless device 102. As
`part of the processing function of distributed navigation
`servers 112, in an embodiment, these servers provide con-
`45 version functions such as between HDML or WML to
`HTML and vice versa.
`An alternative embodiment for the system architecture of
`the present invention is shown in FIG. 2. As shown in FIG.
`2, wireless device 102, wireless carrier 104 and distributed
`navigation servers 112 are substantially the same as
`described for FIG. 1. Direct links 110, however, provide an
`alternative embodiment to the function of gateway 106 and
`network 108 of FIG. 1. The direct link architecture is
`applicable where Internet infrastructure is not well estab(cid:173)
`lished or fast response is desired for user navigation or other
`location specific information services. Illustratively, T1,
`Frame Relay, etc. linked by a LAN or WAN are appropriate
`for direct links 110. In another embodiment, direct links 110
`are implemented as dedicated lines. Alternatively, direct
`links 110 are implemented as hard wired connections
`between wireless carrier 104 and distributed navigation
`servers 112 where wireless carrier 104 and distributed
`navigation servers 112 are collocated in a central office.
`FIG. 3 shows steps of an interactive real-time distributed
`navigation system in accordance with a preferred embodi(cid:173)
`ment. At step 302 a client transmits position information to
`a server and a server receives such information. In an
`
`

`

`US 6,654,683 B2
`
`7
`embodiment, the client is a device such as wireless device
`102 discussed with reference to FIG. 1. The server is a
`device such as distributed navigation server 112 also dis(cid:173)
`cussed with reference to FIG. 1. At step 304 a determination
`is made as to whether the position information is ambiguous.
`If the position information is not ambiguous, the server
`determines proper directions to a destination which are then
`transmitted by the server and received by the client at step
`322.
`A location contains various degrees of inaccuracies. For
`example, most GPS receivers can provide location informa(cid:173)
`tion accurate to within a range of approximately 50 meters,
`i.e., an inaccuracy of around 50 meters. There are a number
`of known factors that may affect the accuracy of a location
`determination. Weather conditions may affect the accuracy
`of a GPS location determination. In an embodiment of the
`invention, a location, in addition to information defining the
`position of an object, is also associated with an estimated
`error and a range. One of skill in the art appreciates that the
`error of a positioning system is estimated based upon the 20
`characteristics of the positioning device and other factors
`including weather and transmission conditions.
`Whether or not a location is ambiguous may be dependent
`upon many factors including, but not limited to: the accuracy
`associated with the location; attributes of a road network; 25
`recent traveling history; and map accuracy.
`In general, the more accurate a location, the less likely it