`US 6,654,683 B2
`(10) Patent No.:
`(12)
`Jin et al.
`(45) Date of Patent:
`Nov. 25, 2003
`
`
`US006654683B2
`
`(76)
`
`(54) METHOD AND SYSTEM FOR REAL-TIME
`TELEPHONESNS MOBILE
`TELEPHONES
`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 EROS)
`Ave. #15, Menlo Park, CA (US) 94025;
`Salman Dhanani. 9634 179th Pl. NE.
`#4. Redmond WA (US) 98052
`,
`,
`Subject to any disclaimer,the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b)
`by 41 days.
`(b)
`by
`¥
`
`(*) Notice:
`
`(21) Appl. No.: 09/884,841
`(22)
`Filed:
`Jun. 18, 2001
`.
`oo,
`Prior Publication Data
`US 2002/0029107 Al Mar. 7, 2002
`Related U.S. Application Data
`
`(65)
`
`6/1996 Steiner et al. ww... 342/357
`5,528,248 A
`
`3/1997 Garis et al.sos
`610821 A
`azis etal. ww...
`.
`3,610,
`ti
`d
`t
`.
`List
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`jot? Al
`*1999
`OTHER PUBLICATIONS
`
`wo
`
`Suppemery European Search Report, dated Nov. 14,
`2002, or Application Number Ep 00967228.
`International Search Report, dated Dec. 19, 2002, for Inter-
`national Application No. PCT/US02/02323, filed Jan. 24,
`2002.
`International Search Report, dated Mar. 26, 2001, for Inter-
`pavional Application No. PCT/US00/35075, filed Dec. 21,
`:
`International Search Report, dated Jan. 4, 2001, for Inter-
`national Application No. PCT/US00/27083,filed Sep. 27,
`International Search Report, dated Jan. 12, 2001, for Inter-
`national Application No. PCT/US00/26921, filed Sep. 27,
`2000.
`Primary Examiner—Tan Nguyen
`(57)
`ABSTRACT
`
`(60)
`
`(63) Continuation-in-partof application No. 09/547,421,filed on
`Apr. 11, 2000, now Pat. No. 6,266,615.
`Provisional application No. 60/156,225, filed on Sep. 27,
`Toeangrovisional application No. 60/211,994,filed on
`7?
`,
`(SL) Ute C0 eee eecessesscsseeseesseseeneeneeneens GOI1C 21/26
`(52) U.S. Ch. eens 701/207; 701/210; 340/995
`(58) Field of Search 2.0.0... 701/201, 202,
`701/205, 207, 209, 208, 210; 455/456;
`340/990, 995
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`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-
`tions to the user.
`
`5,278,424 A *
`
`1/1994 Kagawa ....... ee 250/559.37
`
`32 Claims, 7 Drawing Sheets
`
`Cold
`
`Select: Cold/Warm
`Start?
`23
`
`Warm
`
`
`
`
`
`
`Remove Ambiguity §,
`of Position
`
`Yes
`
`616
`
`TX Directions
`To Client
`
`
`
`
`
`TXDirections
`To Client
`
`Position Info:
`Client TX, Server RX
`612
`604
`—_____¥
`Pasition Info:
`Ambiguous Position?
`Client TX, Server RX
`606
`
`i|
`
`
`TX Directions
`To Client
`
`EM
`
`AmbiguousPosition?
`No.
`608
`
`TXDirections
`To Client
`
`620
`
`610
`
`Google 1024
`U.S. Patent No. 9,445,251
`
`Google 1024
`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 Sproutet al. cee 455/456
`4/1998 Goldberg et al.
`........ 364/449.5
`
`6/1998 Brunts et al... 701/210
`............ 701/213
`6/1998 Cisneroset al.
`11/1998 Gudatet al. 00.0... 364/424.02
`
`3/1999 Nimura et al. «0.0... 701/208
`5/1999 Tamaiet al. oo... 701/211
`5/1999 Tamai et al. oe 701/211
`
`6/1999 Zuber o..eeeecrerreerreereees 701/202
`.......... 340/988
`6/1999 Oshizawa et al.
`7/1999 Sekine et al. we. 701/210
`
`++ 701/29
`TI999 Geter o.rseeeeeeseee
`7/1999 Oshizawa et al. «......... 701/210
`8/1999 Golding ........ ee 340/995
`8/1999 Tama ...eeserererrerererreees 701/209
`
`
`.............. 701/211
`8/1999 Dussell et al.
`11/1999 Oshizawa .......
`ee 701/209
`
`1/2000 Rosenetal. w.c.ccceee 340/905
`
`
`2/2000 PulltZ ......ccceeeceeeeteeeeeee 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 Bl
`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
`
`2/2000 Takaki ...........ccceseeeeeees 455/456
`2/2000 Takahashiet al.
`.......... 701/210
`4/2000 Heron vissececsceseseseesssees 701/213
`w. 701/209
`5/2000 Beyeretal.
`
`...cceccceeee 340/995
`8/2000 Behret al.
`8/2000 Ketola ....cccceceeeees 455/466
`... 706/13
`9/2000 Ferkinhoff etal.
`
`11/2000 Obradovich etal. ........ 701/208
`11/2000 Cac o..eecceseeereeeees 455/466
`.. 701/213
`1/2001 Thuente......
`
`1/2001 Buchleret al.
`............. 701/220
`3/2001 Ginigeret al.
`...scesceceoe 705/1
`3/2001 Lin veeccecsecsesee
`.. 701/214
`
`3/2001 Doganet al. we. 342/378
`6/2001. Tuck et al. v.eeeeeeeee 702/150
`F201 Tih cecccccccccscesecseeseeseeeee 701/213
`
`7/2001 Ibrahim etal. .......0.0... 701/214
`6/2002 Jin accecccereeeees 701/213
`6/2002 Rennard et al.
`........... 701/200
`
`* cited by examiner
`
`
`
`U.S. Patent
`
`Nov.25, 2003
`
`Sheet 1 of 7
`
`US 6,654,683 B2
`
`GALNEIYLSIA
`
`NOLLVOIAYN
`
`SYSANSS
`
`cbb
`
`YSHLOYONITdN
`
`
`
`“TIdWVX3YO4-
`
`
`
`SdSISSSTIYIM
`
`fanaaina},a-—
`
`SSITAYIM
`
`SUsUaVO
`
`Q3LNGILSIC
`
`NOILLVOIAVN
`
`cbh
`
`SMAANAS901vOl
`
`
`
`¥JYNLOSLIHONY—-WSISASNOLWOIAVNCSLAIYLSIGSWLLWSSALLOVYSINI
`
`
`
`
`
`Old
`
`S¥Ud40SSNOHd
`
`SSITSUIM°
`
`NOLUSOdHIIM
`
`ALND
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Nov.25, 2003
`
`Sheet 2 of 7
`
`US 6,654,683 B2
`
`SUIANaS=
`
`obbOb
`
`
`
`
`9FYMIDALHONY-WSISASNOWVOIAVNGALNGIMLSIJWILTVSSALOVYSINIAS
`NOLLWOIAWN|||AneRiisid193410SSTTaUIM//
`
`SyNTsuaya&
`
`:NOWISOdHUMCOsS¥dYOS3NOHd
`
`
`
`~POlZOL
`
`SOL
`
`O69
`QoGSg
`
`09,
`
`SSTTaMIM«
`
`ANIA
`
`
`
`
`U.S. Patent
`
`Nov. 25, 2003
`
`Sheet 3 of 7
`
`US 6,654,683 B2
`
`CLIENT TX
`
`cent I|POSITION INFO,
`
`302
`
`N
`
`“AMBIGUOUS
`
`304
`
`TX DIRECTIONS
`TO CLIENT
`
`322
`
`
`
`
`
`
`CLIENTTl
`
`
`
`193 RO
`
`y
`
`QUERY DB
`
`GENERATE. LIST
`
`CONSOLIDATE LIST
`
`SERVER TX
`
`CLIENT pst
`
`USER SELECT
`
`SERVER RX SELECTION
`
`CALCULATE LOCATION
`
`AMBIGUOUS
`
`306
`
`308
`
`310
`
`312
`
`314
`
`316
`
`318
`
`
`
`U.S. Patent
`
`Nov. 25, 2003
`
`Sheet 4 of 7
`
`US 6,654,683 B2
`
`POSITION
`INFO.
`302
`
`DISPLAY
`CANDIDATES
`
`PROMPT USER WITH
`NAV.
`INSTRUCTIONS
`322
`
`310
`
`GENERATE
`CANDIDATELIST
`308
`
`CONSOLIDATE
`LIST
`
`CALCULATE
`LOCATION
`304
`
`FIG.4
`
`112
`
`
`
`U.S. Patent
`
`Nov.25, 2003
`
`Sheet 5 of 7
`
`US 6,654,683 B2
`
`v0S
`
`
`
`
`
`SOIHdvYdLXALGNY/YOFOIA
`
`ONIHOVOUddYSYNOA-
`
`
`IHOIYNYNLCINOHSNOA
`
`
`
`
`(SGMVA00%YO)SSLANINSINOGYNI‘SAVJAON9
`
`20%
`
`SALOVUSINI uaHSAdYOAYS
`
`SNOLLONNGNAYSSN-W3LSASNOLVOIAVNCSLNEIMLSICSWLLTWdY
`
`
`
`
`
`
`
`YOAVS“TWsdONINVO14
`
`NO3uV¥NOAale
`
`Gold
`
`VNTYNOSuvNOAAle
`
`utyHSAd
`
`
`
`
`
`U.S. Patent
`
`Nov. 25, 2003
`
`Sheet 6 of 7
`
`US 6,654,683 B2
`
`
`
`
`Select: Cold/Warm
`Start?
`
`
`
`
`Position Info:
`TX Directions
`
`To Client
`
`Client TX, Server RX
`
`
`Position Info:
`
`
` Ambiguous Position?
`Client TX, Server RX
`
`
`
`
`
`
`
` Remove Ambiguity
`of Position
`
`Ambiguous Position?
`
`
`
`
`TX Directions
`TX Directions
`TX Directions
`To Client
`
`To Client
`To Client
`
`
`618
`
`620
`
`610
`
`FIG. 6
`
`
`
`U.S. Patent
`
`Nov. 25, 2003
`
`Sheet 7 of 7
`
`US 6,654,683 B2
`
`704 Device | Interpreter/Browser
`
`Servlet Engine
`
`Servlet
`706
`
`Wireless
`
`102
`
`VoiceXML
`
`702
`
`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-
`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-
`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-
`vent the incorporation of navigational capabilities in hand-
`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-
`tion. Small handheld devices include cellular phones, per-
`sonal digital assistants, or computers, however, the amount
`of embedded memoryis limited and is impractical to store
`a large amount of geographic information. In existing auto-
`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-
`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-
`ing power of small devices such as those mentioned above.
`For example, the information processing powerof a cellular
`telephone is typically provided by an embedded micropro-
`cessor with limited memory. While the information process-
`ing power of embedded microprocessors is generally
`increasing, such processorsare still not suitable for proces-
`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-
`ability (S/A), other sources of error are due to atmospheric
`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-
`work based system (i.e., Truepoint). These methods use a
`known position, such as a survey control point, as a refer-
`ence point to correct the GPS position error. These methods
`of correcting GPS positions are referred to as Differential
`GPS or DGPS. The DGPScorrections can be applied to the
`GPSdatain real-time using data telemetry (radio modems).
`Toward expanding the use of DGPS, the United States and
`Candian Coast Guard are establishing a series of radio
`
`2
`the DGPS corrections for accurate
`beacons to transmit
`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
`not available to consumers traveling in most inland loca-
`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
`downtown area with streets spaced close together, a GPS
`location within +/-50 meters is not adequate to give turn-
`by-turn directions. The GPS location information is thus
`considered ambiguous and inappropriate for navigation sys-
`tems. In other situations, a GPS location within +/—50 meters
`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
`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
`when the device is used while walking.
`Accordingly, it would be desirable to provide a naviga-
`tional system that provides accurate navigational instruc-
`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.
`II. SUMMARY OF THE INVENTION
`
`These and other objects are provided for by a system and
`methodfor interactive real-time distributed navigation. In an
`embodimentof 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 suchlist is then used to correct for errors in
`
`other position detecting sensors.
`In another embodimentof 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
`
`wn
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`
`
`US 6,654,683 B2
`
`3
`are dynamically distributed between the server and the
`device. In an embodiment, a user sends a request to navigate
`from a currentlocation (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-
`mation relating to a first small geographic area to the user’s
`device. Once the user movesoutof the first small geographi-
`cal area, the information will be updated by the servereither
`at the request of the user’s device or initiated by the server
`based upon the location of the user.
`Anotheraspect of the invention provides navigation guid-
`ance based on real-timetraffic conditions. Thetraffic infor-
`mation can be obtained from a group of navigational service
`users, by observing their speeds and making comparisons
`with the nominalstreet 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
`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 embodimentof the invention provides directions
`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 meantime,if not
`necessary, the communication link can be released to reduce
`the servertraffic.
`
`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-
`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
`such that a navigational session is immediately provided to
`the user.
`
`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-
`tecture A (Internet);
`FIG. 2 is a schematic showing another embodimentof the
`Interactive Real-time Distributed Navigation System- Archi-
`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;
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`FIG. 6 is a flowchart of a method for providing warm
`start/cold start options in an Interactive Real-time Distrib-
`uted Navigation System; and
`FIG. 7 is a schematic showing an embodiment for gen-
`erating voice code at runtime in an Interactive Real-time
`Distributed Navigation System.
`
`V. DETAILED DESCRIPTION OF THE
`EMBODIMENTS
`
`Reference will now be made in detail to the preferred
`embodiments of the invention, examples of which are illus-
`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
`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 componentof a navigation system is the determi-
`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-
`sional information that completely define the exact position
`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-
`tion may contain information that is not sufficient to com-
`pletely define the position of an object. Broadly defined
`location, as used herein, also may include speed,
`time,
`direction of movement, etc. of an object.
`Oneskilled in the art would appreciate that the format of
`location informationis not critical to some embodiments of
`the invention. For example, in some embodiments,location
`information is presented in the formatof (x, y), where x and
`y are two ordinates define the geographic location of an
`object, 1.e., a user.
`FIG. 1 showsan architecture for an Interactive Real-Time
`Distributed Navigation System in accordance with a pre-
`ferred embodiment. The various componentsandtheir inter-
`action will now be described. It is to be understood that
`wherelike 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,
`wireless Personal Digital Assistant (PDA), personal com-
`puter or other suitable device having wireless communica-
`tions capability. Wireless device 102 is equipped with posi-
`tioning capability that takes the form of, for example, global
`positioning systems (GPS), emergency 911 (E911)location,
`or someother positioning systems as they becomeavailable.
`One skilled in the art will appreciate that
`the present
`invention is not limited to any particular positioning tech-
`nology. In an embodiment, wireless device 102 is manufac-
`tured with built-in positioning capabilities Advantageously,
`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.
`
`
`
`US 6,654,683 B2
`
`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-
`rates the user’s sensory capabilities within the invention.
`User interface 105 is used to allow user interaction with
`
`electromechanical components of the invention. Such inter-
`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-
`mation to a user by meansof audible signals or through text
`messages displayed on wireless device 102, embodiments of
`the invention makeuse of audible sound producing devices,
`as well as, text displaying devices. Where a text displaying
`device is used, enhanced performanceis 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. Oneofskill in the
`art realizes that many more implementationsare 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-
`tributed navigation servers 112 to be described further
`below. Examples of wireless carrier 104 include cellular
`telephone carriers, satellite communicationscarriers or glo-
`bal positioning system carriers.
`In achieving wireless
`connectivity, wireless carriers provide an existing infrastruc-
`ture for the wireless devices and distributed navigation
`servers. In an embodiment, GPS is used along with the
`government imposedselective 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-
`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.
`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, amongothers,
`provide the services necessary to practice the invention.
`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
`limited to GSM, TDMA, CDMA,provide higher data
`throughput. At the time of the invention, CDMAprovides
`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
`appropriate for these and many other transmission tech-
`niques. In an embodiment of the invention, wireless carrier
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`104 receives analog or digital information from the wireless
`device 102 and directs such information to other compo-
`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, amongothers, wireless carriers,
`ISPs, or other telecommunications providers. In an embodi-
`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
`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
`servers 112 store street map information and pointofinterest
`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
`location specific information such as real-timetraffic infor-
`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
`map database, real-timetraffic 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
`first route becomesless 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-
`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-
`version functions such as between HDML or WML to
`HTMLandvice 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 embodimentto the function of gateway 106 and
`network 108 of FIG. 1. The direct
`link architecture is
`applicable where Internet infrastructure is not well estab-
`lished orfast response is desired for user navigation or other
`location specific information services. Ilustratively, T1,
`FrameRelay, 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 showssteps of an interactive real-time distributed
`navigation system in accordance with a preferred embodi-
`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-
`cussed with reference to FIG. 1. At step 304 a determination
`is madeas to whether the position information is ambiguous.
`If the position information is not ambiguous,
`the server
`determines properdirections 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 GPSreceivers can provide location informa-
`tion accurate to within a range of approximately 50 meters,
`1.¢., an inaccuracy of around 50 meters. There are a number
`of knownfactors that may affect the accuracy of a location
`determination. Weather conditions may affect the accuracy
`of a GPSlocation determination. In an embodimentof 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
`characteristics of the positioning device and other factors
`including weather and transmission conditions.
`Whetheror 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;
`recent traveling history; and map accuracy.
`In general, the more accurate a location, theless likely it
`is ambiguous. The attributes of a road network, such
`direction, turns, etc., can be useful in removing ambiguity.
`Illustrations are helpful: if one is traveling in on a highway
`in a remote area without any exits, a location associated with
`error of around 50 meters is not ambiguous for navigation
`purpose, because the navigation direction will be “going
`along the highway”. Contrastingly, a location associated
`with an error of 50 meters is ambiguousif the location is
`within a business district of a downtown urban area where
`street blocks are less than 10 meters away. In an embodiment
`of the invention, whether a location is ambiguous is also
`dependent upontraffic regulations andtraffic conditions. For
`example, if there are only two roads (Road A and B) within
`the range of a location (location+/—error), where the user is
`travelling at a speed of 55-80 miles/hr and road A has speed
`limit of 25 miles per hour, the location is unambiguous for
`the purpose of navigation because the user’s location can be
`determined to be on Road B with a high degree of confi-
`dence.
`
`Auser’s recenttravel history is utilized in an embodiment
`of the invention to reduce ambiguity,
`for example, by
`performing a pattern recognition analysis ofthe user’s travel
`history within a particular area. IIlustratively, a user’s travel
`history may be recorded or logged over a predetermined
`time and used in an auto-regressive manner.
`Returning to the discussion of FIG. 3, if at step 304, the
`position information is determined to be ambiguous, further
`novel steps are taken to remove ambiguity of position
`information. With the received ambiguous position infor-
`mation in conjunction with an associated error for a par-
`ticular positioning system in use, a query is made of a map
`database at step 306. From the query at step 306, a list is
`generated at step 308 of various candidate locations. In an
`embodimentof the invention, the candidate locations of step
`308 are associ