US007 149625B2
`
`(12) United States Patent
`Mathews et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,149,625 B2
`Dec. 12, 2006
`
`(54) METHOD AND SYSTEM FOR DISTRIBUTED
`NAVIGATION AND AUTOMATED
`GUIDANCE
`
`(76) Inventors: Michael B. Mathews, 10725 - 126th
`P1. NE., Kirkland, WA (US) 98033;
`Poul T. Lomholt, PMB 256 - 2373
`NW. 185th, Hillsboro, OR (US) 97.124;
`William A. Littlewood, 438
`Massachusetts Ave., Apt. 416,
`Arlington, MA (US) 02474
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 379 days.
`(21) Appl. No.: 10/158,223
`(22) Filed:
`May 29, 2002
`
`(*) Notice:
`
`(65)
`
`Prior Publication Data
`US 2003 FOO60973 A1
`Mar. 27, 2003
`
`Related U.S. Application Data
`(60) Provisional application No. 60/295,084, filed on May
`31, 2001.
`(51) Int. Cl.
`(2006.01)
`GOIC 2L/30
`(2006.01)
`GOIC 2L/32
`(52) U.S. Cl. ...................... 701/209; 701/200; 701/201;
`701/213: 340/995
`(58) Field of Classification Search ................ 701/209,
`701/200, 201, 205, 96; 73/178.12: 340/991,
`340/993,995.18,995.2,995.24
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`5,331,561 A * 7/1994 Barrett et al. ............... 701 (205
`5,504,482 A * 4, 1996 Schreder ................ 340,995.13
`5,625,556 A * 4/1997 Janky et al. ................... TO1f1
`5,802,492 A * 9/1998 DeLorime et al. ........ 455,456.5
`
`5,810,392 A * 9/1998 Gagnon ...................... 180,268
`5,865,463 A * 2/1999 Gagnon et al. .......... 280/730.2
`5.948,040 A * 9/1999 DeLorime et al. ........... TO1,201
`5,951,620 A * 9/1999 Ahrens et al. ....
`... 701 (200
`5,955,973 A * 9/1999 Anderson .........
`... 340.988
`5,971.432 A * 10/1999 Gagnon et al. ...
`... 180,268
`5,987,381 A * 11/1999 Oshizawa .........
`... TO1,209
`5.991,676 A * 11/1999 Podoloff et al. ...
`... 177,144
`6,009,403 A 12, 1999 Sato .............................. 705/6
`6,070,124. A * 5/2000 Nimura et al. .............. TO1,211
`6,075.467 A *
`6/2000 Ninagawa ......
`... 340,995.14
`6,076,041 A
`6/2000 Watanabe ................... TO1,211
`6,104.338 A
`8/2000 Krasner ................. 342,357.06
`6,158,768 A * 12/2000 Steffens et al. ............. 180,237
`6,169,515 B1* 1/2001 Mannings et al. ....... 342,357.1
`6.216,086 B1* 4/2001 Seymour et al. ............ TO1,202
`
`
`
`(Continued)
`Primary Examiner Cuong Nguyen
`(74) Attorney, Agent, or Firm—Christensen O'Connor
`Johnson Kindness PLLC
`
`(57)
`
`ABSTRACT
`
`The present invention provides for distributed navigation
`and route guidance using networked computing devices. A
`computing device may host one or more navigation func
`tional components. The location of a navigable object is
`sensed and communicated to associated navigation compo
`nents in a communication network. The navigation compo
`nents collectively provide guidance information to a navi
`gable object controller. A navigable object controller directs
`the movement of an navigable object using guidance infor
`mation to keep it on a specified route. The navigable object
`controller interacts with the distributed navigation system
`through an interface, which provides the appropriate pre
`sentation of guidance information and functions for the
`particular type of navigable object controller (e.g., human
`machine interface, or system to system). The present inven
`tion provides the structures and methods for a flexible
`navigation and guidance system Supporting a variety of
`network capabilities and computing devices using the same
`Software implementation.
`
`51 Claims, 16 Drawing Sheets
`
`Navigation
`foration
`
`
`
`66 TA
`point of
`Interest
`
`route Maneuve
`
`Point of interest (POI)
`orWaypoint
`
`Route Marker
`
`Navigable Physical Object
`dynamic Element
`
`Rosafa Structure
`
`Route Header
`(Route 1D, Time Generated, Source)
`
`Ordered elements
`e1(loc, type,...)
`e2(loc, type,...)
`
`der slees
`
`Additional information
`(street data, events, preferences,...)
`
`Hyundai Exhibit 1019, Page 1 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`US 7,149,625 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`- I -
`
`-
`
`- - - - - - - - - - - - - -
`
`6/2001 Friederich et al.
`6,249,742 B1
`9/2001 Robare et al.
`6,292,745 B1
`R. 39
`stal
`6,359,571 B1
`3/2002 Endo et al.
`6,370,539 B1
`4/2002 Ashby et al.
`6,401,034 B1* 6/2002 Kaplan et al. .............. TO1,209
`6,553,130 B1 * 4/2003 Lemelson et al. .......... 382/104
`6,553,308 B1 * 4/2003 Uhlmann et al. ........... TO1,208
`
`28Of735
`
`6,577,937 B1 * 6/2003 Shuman et al. ............... TO1/48
`6,597,983 B1* 7/2003 Hancock ........
`701, 200
`6,628,233 B1* 9/2003 Knockeart et al. ....... 342/357.1
`2002/O120374, A1* 8, 2002 Douros et al. ...
`... 701/29
`2002/0173907 A1* 11/2002 Ando ......................... TO1,209
`ck
`2003/015.1501 A1* 8, 2003 Teckchandani
`et al. ..................... 340,426.19
`
`3/2003 Tanaka et al. ............. 340, 5.64
`
`2003/0043019 A1
`
`
`
`* cited by examiner
`
`Hyundai Exhibit 1019, Page 2 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`US 7,149,625 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Hyundai Exhibit 1019, Page 3 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`Dec. 12, 2006
`
`Sheet 2 of 16
`
`US 7,149,625 B2
`
`102 101
`
`NPO Controller
`(Person, automated - - - - - - - -
`System)
`
`Navigable Physical
`Object (NPO)
`
`
`
`105-
`
`106
`
`
`
`
`
`
`
`
`
`Navigation
`Guidance
`interface
`
`Guidance
`Component
`
`
`
`
`
`Navigation Management
`Component
`
`Physical
`Location
`Sensor
`
`gateway
`
`Caching
`Component
`(optional)
`
`
`
`
`
`
`
`221
`
`
`
`
`
`Wide Area NetWork
`includes:
`Wireless NetWorks
`Internet,
`Proprietary networks
`
`109
`
`
`
`network
`
`Navigation
`Service
`Component
`
`Point-Of-interest
`Services
`Component
`
`
`
`
`
`Figure 2
`
`Mapping and
`Geocoding
`Services
`Component
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Hyundai Exhibit 1019, Page 4 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`Dec. 12, 2006
`
`Sheet 3 of 16
`
`US 7,149,625 B2
`
`332
`
`321
`
`
`
`
`
`V222222
`
`3O2
`
`105
`
`103
`
`331
`
`320
`
`
`
`1 O6
`
`
`
`
`
`
`
`Mobile Computing Device
`
`interface 1
`Guidance
`
`107
`
`Sensor
`
`Cache
`-
`106
`
`
`
`
`
`330
`
`107
`
`303 ()
`
`304
`
`Navigation
`Services Comp.
`
`Point-Of-interest
`Services Comp.
`
`Mapping and
`Geocoding Services
`Comp.
`
`Figure 3
`
`Hyundai Exhibit 1019, Page 5 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Hyundai Exhibit 1019, Page 6 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`Dec. 12, 2006
`
`Sheet 5 of 16
`
`US 7,149,625 B2
`
`504
`
`503
`
`
`
`
`
`Cellphone willocation
`SenSO
`(Auditory interface)
`
`Wireless Device
`W/location sensor
`
`Thin client
`devices with
`browser
`capabilities O
`lightweight
`applets:
`Cell-phones,
`PDAs, Pagers,
`etc.
`
`Wireless Voice
`NetWOrk
`
`502
`
`
`
`
`
`Telephony
`interface Server
`
`
`
`Wireless Data
`NetWOrk
`
`501
`
`Guidance Server
`
`Nav / Tracking
`Server
`
`
`
`External Server(s)
`
`GIS Server(s)
`
`Figure 5
`
`Hyundai Exhibit 1019, Page 7 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`Dec. 12, 2006
`
`Sheet 6 of 16
`
`625 B2
`149
`US 7,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`9 eun61-I
`
`Hyundai Exhibit 1019, Page 8 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`Dec. 12, 2006
`
`Sheet 7 of 16
`
`US 7,149,625 B2
`
`% 6
`
`OU
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`1 eun61-I
`
`Hyundai Exhibit 1019, Page 9 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`Dec. 12, 2006
`
`Sheet 8 of 16
`
`625 B2
`149
`US 7,
`
`} | } | | | | | | | | | | | | | | } |
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`• • • • • • • • • • • • ? ? ? ? ? ? = * * * * • •
`
`8
`
`:
`
`:
`
`:
`
`P
`
`as well as are as are see was as a s- as are as as as a -a as a c
`
`e
`
`- - - - - - - -
`
`€ 1,8
`
`Hyundai Exhibit 1019, Page 10 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`US 7,149,625 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Hyundai Exhibit 1019, Page 11 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`Dec. 12, 2006
`
`Sheet 10 of 16
`
`US 7,149,625 B2
`
`is asses sea
`
`J?Aneue W
`
`as as as
`
`6
`
`906
`
`rews
`
`900!, Ou
`
`906
`
`
`
`eO? ?un61-I
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Hyundai Exhibit 1019, Page 12 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`Dec. 12, 2006
`
`Sheet 11 of 16
`
`US 7,149,625 B2
`
`
`
`
`
`q0), eun61
`
`
`
`øyens ?ueue? pexoeil|- slov
`
`
`
`
`
`Hyundai Exhibit 1019, Page 13 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`U.S. Patent
`
`Dec. 12, 2006
`
`Sheet 12 of 16
`
`US 7,149,625 B2
`
`60
`
`goy | 90ueplnº
`
`
`
`
`
`
`
`
`
`Hyundai Exhibit 1019, Page 14 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Hyundai Exhibit 1019, Page 15 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Hyundai Exhibit 1019, Page 16 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Hyundai Exhibit 1019, Page 17 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Hyundai Exhibit 1019, Page 18 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`US 7,149,625 B2
`
`1.
`METHOD AND SYSTEM FOR DISTRIBUTED
`NAVIGATION AND AUTOMATED
`GUIDANCE
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This application claims the benefit of U.S. Provisional
`Application No. 60/295,084, filed date May 31, 2001.
`
`FIELD OF THE INVENTION
`
`The invention generally relates to a system and method
`for providing navigation and automated guidance to a
`mobile user, and more particularly to a system and method
`of loosely coupled modules cooperatively providing navi
`gation and automated guidance to a mobile user.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`15
`
`2
`devices such as portable/laptop computers and PDAs (per
`Sonal digital assistants) can be used to provide navigation
`information so long as they have a location sensor (e.g.,
`GPS) and a wireless connection. These types of systems
`provide the same general functionality as an autonomous
`system but delegate the processor-intensive route calculation
`and map functions to the server, which can provide these
`functions for multiple devices concurrently. Off-board navi
`gation creates low-cost, highly portable navigation and
`guidance solutions.
`A typical navigation scenario using off-board navigation
`comprises the following steps. Using a client device, a user
`specifies selection criteria for a route, including one or more
`destinations, the type of route (e.g., fastest, shortest, Scenic),
`and other personal preferences. A client device transmits the
`route request to the navigation server, which calculates the
`route between the client device's current location and the
`specified destinations. Additionally, other interactions
`between the system and user may be required to resolve any
`information not understood by the server, Such as an
`improper address entry or a point-of-interest selection. Fol
`lowing a Successful route calculation, the information is
`delivered to the client device, which either displays the
`resulting navigation information to the user or processes the
`information by a local guidance function on the client
`device.
`Though off-board navigation systems represent a sig
`nificant step over autonomous navigation systems, they tend
`to be very limited in their usefulness as they operate only in
`areas with wireless communications. Implementations of
`these systems have resulted in highly proprietary data and
`communications protocols in order to move information
`efficiently between the client device and server. As a result,
`these systems are fairly inflexible and support only a limited
`number of configurations, devices, and features. In addition,
`these systems are unable to degrade gracefully when com
`munications break down, as they rely heavily upon the
`server for continuous navigation information.
`A problem with both types of navigation systems is their
`tendency to be limited to a single user or a single navigation
`activity. Both lack the ability to incorporate other navigation
`activities, such as tracking information or guidance infor
`mation, where other individuals or systems may coordinate
`navigation together to achieve a common result.
`Though both types of navigation systems provide useful
`guidance and navigation functions, they are limited by
`platform requirements and propriety implementations. There
`is a need to blend and balance the two approaches to form
`a distributed Solution that can operate in both configurations
`as well as others, thereby gaining their respective advan
`tages. With the proliferation of the Internet and associated
`wireless Internet, a more distributed and platform-indepen
`dent approach is needed wherein the navigation systems
`core functions are defined and implemented Such that the
`communications and platform requirements are encapsu
`lated and isolated. This will allow the system to be defined
`and operated in a logical configuration without explicit
`knowledge of the physical configuration. There is a further
`need for the system to adapt, and to Support intermittent
`communications, where one or more parts of the navigation
`system may be unable to communicate with the other parts,
`yet still provide their designated function. In addition, the
`system should be robust and degrade gracefully in the event
`of unexpected problems.
`A useful advance over current systems that is needed
`would be a navigation system that is dynamically config
`urable and deployable across various types of devices using
`
`25
`
`30
`
`35
`
`Navigation systems have been developed to provide route
`and geographical information for directing a mobile user to
`one or more destinations. These systems are typically being
`delivered in two primary forms: a self-contained autono
`mous configuration, and a mobile client and fixed server
`configuration using some wireless communications means.
`An autonomous navigation system provides a single unit
`comprising a map database, location sensor, user interface,
`and guidance functions. These types of systems provide
`everything that is needed to provide navigation and auto
`mated guidance in one package without any external data or
`support. This configuration benefits in terms of robustness in
`that, being autonomous, it can operate almost anywhere for
`which it has map data. Recent advances have augmented
`these types of systems with real-time information, such as
`traffic, events, and road construction information using
`wireless data communications. These systems have begun to
`proliferate in Europe, Japan, and in the U.S., but have been
`slow to become standard equipment due to the expense of
`each system, most costing S1500 or more.
`40
`While these systems provide a high-quality navigation
`experience, they are limited by their relative high cost, and
`by the currency of their information. The primary drawback
`of autonomous navigation systems is the need to have all
`map and geographic information integrated as part of the
`45
`system. This information is typically stored on a CD-ROM
`or DVD depending upon the detail and geographic region
`covered, and must be updated periodically to stay current
`with changes in the road network as well as to provide new
`points of interests. By storing the information in the navi
`gation system, the cost of the system is higher due to the
`extra physical equipment and processing requirements.
`Additionally, the data has a tendency to go out of date. These
`systems also tend to be bulky and not well suited for
`non-vehicular navigation and guidance. Such as pedestrian
`navigation.
`In response to the limitations of autonomous navigation,
`another type of navigation system was developed, termed
`off-board navigation, in which a server houses the map and
`route calculation functions, such that client devices using
`wireless communications can access the latest map and other
`navigation-related information without needing to store
`large amounts of data locally. By locating the information
`centrally, the data is much more easily maintained and
`integrated with other dynamic data, Such as traffic and road
`construction information, when compared to autonomous
`systems. Using this off-board configuration, low-cost
`
`50
`
`55
`
`60
`
`65
`
`Hyundai Exhibit 1019, Page 19 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`US 7,149,625 B2
`
`3
`standard networking technologies. Both the software imple
`mentation and data formats should be defined using open
`standards such as JAVA, C++, and XML, such that they
`provide maximal platform independence and integration
`flexibility. The navigation system would also Support mul
`tiple device configurations where the navigation system
`functions are deployed on three or more devices.
`Another useful advance would be to provide navigation
`functionality where multiple parties coordinate navigation
`activities. Navigation information for one user would be
`shared and integrated in navigation information for other
`parties, and provide enabling scenarios such as follow-the
`leader, fleet dispatch, and tracking. There is a need to
`provide relative guidance, where one vehicle or navigable
`object is guided with respect to another navigable object.
`Yet another useful advance over prior art would be a
`navigation system that is easy to extend and integrate with
`other systems without requiring significant engineering and
`development. A method and system for distributed naviga
`tion and automated guidance that solves the preceding
`problems and addresses the specified needs would be a
`useful and novel advance over the prior art.
`
`SUMMARY OF THE INVENTION
`
`The present invention provides a method and system for
`distributed navigation and automated route guidance using a
`plurality of networked computing devices. A navigation and
`guidance system comprising well-formed components are
`integrated using standardized distributed networking proto
`cols, wherein the physical connection and integration are
`managed by a plurality of host computing platforms and a
`communication network. In particular, the present invention
`defines a navigation session, in which a plurality of navi
`gation components operate to provide navigation and guid
`ance information for a navigable object. The session serves
`to provide a common context between components. All
`navigation and guidance activities are conducted within the
`Scope of a session, in which each navigation component
`provides a specific function, and interacts with other com
`40
`ponents in a peer-to-peer manner. The primary components
`of the presently preferred form of the distributed navigation
`system include a navigation guidance interface, a physical
`location sensor, a guidance component, a navigation man
`agement component, a caching component, and a navigation
`45
`services component. Depending on a particular configura
`tion, selected ones of these components are deployed on
`various computing platforms, creating a distributed naviga
`tion system on the required functions and performance.
`One aspect of the present invention provides a method
`comprising obtaining navigation and guidance information
`in which the navigation state is shared jointly by the navi
`gation system components. A route definition, comprising
`one or more destinations, describes certain destinations
`using symbolic names Such as "current location”, “current
`direction', and symbolic places such as “home” and
`“office'. The method defines the process for calculating and
`deploying routes and other navigation information, in which
`each navigation component is updated according to the
`configuration managed by the navigation session. The
`method attempts to minimize network transactions by taking
`advantage of cached information when available.
`Another aspect of the present invention provides a method
`for distributed automated guidance, wherein the guidance
`component can be configured to operate locally or remotely
`with respect to the navigation interface component. Depend
`ing upon the network configuration, the guidance compo
`
`50
`
`55
`
`60
`
`65
`
`10
`
`15
`
`25
`
`30
`
`35
`
`4
`nent may be deployed locally with respect to the physical
`location sensor and navigation guidance interface, wherein
`the components can interact with little or no latency or delay
`of feedback. In another configuration, the guidance compo
`nent may operate remotely from the navigation guidance
`interface and physical location sensor, wherein the naviga
`tion guidance interface is required to operate independently
`of the guidance component using predicted events and state
`information. In the remote configuration, the guidance com
`ponent is periodically updated Such that predicted events can
`be updated with respect to the current navigation state. The
`predicted events and state information are formatted in a
`manner that reduces navigation guidance interface process
`ing, where simple trigger conditions, such as time or place,
`are used to execute the predicted events.
`In yet another aspect of the present invention, a method is
`provided for coordinating navigation State information
`between a plurality of Sessions, wherein a first navigation
`session shares navigation state information with other navi
`gation sessions within the same group. The coordination of
`session information provides a useful means for providing
`navigation and guidance information relative to a dynamic
`object, such as another vehicle. Further, sharing navigation
`state information provides a means to track and coordinate
`common data between a plurality of related navigation
`sessions. As will be better understood from the following
`discussion of a preferred embodiment, the present invention
`provides a flexible configuration and communication abili
`ties using the same software adaptable to a wide variety of
`operating environments.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The foregoing aspects and many of the attendant advan
`tages of this invention will become more readily appreciated
`as the same become better understood by reference to the
`following detailed description, when taken in conjunction
`with the accompanying drawings, wherein:
`FIG. 1 is a functional block diagram illustrating the
`generalized logical configuration of a distributed navigation
`and guidance system, in which the primary components are
`connected through a communication network.
`FIG. 2 is a functional block diagram illustrating in more
`detail one possible logical network configuration of the
`functional components defined FIG. 1. The diagram shows
`the navigation system components connected using one
`local area network (LAN) in conjunction with a wide area
`network (WAN).
`FIG. 3 is a deployment diagram showing an illustrative
`example of two possible physical configurations using the
`logical functional model described in FIG. 2.
`FIG. 4 is a functional block diagram illustrating in more
`detail one possible logical network configuration of the
`functional components defined in FIG. 1. The diagram
`shows the distributed navigation system components con
`nected using a WAN and a high-speed network, wherein the
`guidance component is remotely located with respect to the
`navigation interface component and physical location sen
`SO.
`FIG. 5 is a deployment diagram showing an illustrative
`example of two possible physical configurations using the
`logical functional model described in FIG. 4.
`FIG. 6 is a structural diagram illustrating the various types
`of information and structures used in a route definition.
`
`Hyundai Exhibit 1019, Page 20 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`US 7,149,625 B2
`
`5
`FIG. 7 is a multiple-object, process flow diagram illus
`trating the primary steps for defining, generating, and
`retrieving a route within the structure of the distributed
`navigation system.
`FIG. 8 is an activity diagram illustrating the actions and
`processes for performing automated guidance in a distrib
`uted navigation system.
`FIG. 9 is a process flow diagram illustrating the general
`ized steps for providing distributed automated guidance.
`FIGS. 10a and 10b are process flow diagrams illustrating
`in more detail the steps for updating guidance status, includ
`ing predictive guidance information.
`FIG. 11 is a sequence diagram showing one illustrative
`example of automated guidance in which the navigation
`system is configured as shown in FIG. 2.
`FIGS. 12a and 12b are sequence diagrams showing one
`illustrative example of automated guidance in which the
`guidance component is remotely operated with respect to the
`navigation guidance interface as shown in FIG. 4.
`FIG. 13 is a block diagram showing the relationship
`between navigation sessions and the navigation services
`component.
`FIG. 14 is an activity diagram illustrating the actions and
`processes for coordinated navigation and guidance informa
`tion between a plurality of navigation sessions and a navi
`gation services component.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`10
`
`15
`
`25
`
`30
`
`6
`devices and networking capabilities, optimizing the deploy
`ment of navigation functions.
`FIG. 1 shows the logical configuration of the navigation
`functional components. The NPO's 101 physical location is
`sensed by a physical location sensor 103, which periodically
`communicates physical location information to other navi
`gation components via a computer network 104. The physi
`cal location sensor 103, such as a device coupled to a GPS,
`determines the position, speed, heading, and data measure
`ment quality at Some designated time. The physical location
`information may also include other information useful for
`monitoring various characteristics of the NPO, including
`sensor status and NPO information. These characteristic
`data include GPS constellation status and measurement
`quality, vehicle gas mileage, vehicle fuel level, network
`connectivity, and network performance data. The computer
`network 104 comprises a standardized means for computing
`devices to communicate information to other computing
`devices without regard for the physical transport details. In
`the preferred embodiment of the present invention the
`computer network 104 is a TCP/IP based network, with each
`device having a logical IP address that uniquely identifies
`the computing device. The navigation functional compo
`nents 103, 105, 106, 107, 108, and 109 communicate with
`each other using an application protocol that defines the
`connection method and message formats used. One embodi
`ment of the navigation application protocol uses SOAP
`(Simple Open Access Protocol) and XML (eXtensible
`Markup Language), wherein information is communicated
`between navigation functional components using well
`known Internet integration standards. Using SOAP and
`XML documents provides complete platform independence.
`Other application protocols include RPC, CORBA, and
`JAVARMI. The computer network 104 may be comprised of
`one or more physical networks including local area networks
`(LAN) such as an Ethernet, wide area networks (WANs)
`Such as the Internet, and wireless data networks such as
`CDPD, GSM ISDN, and GPRS. In the preferred embodi
`ment of the present invention, the navigation components
`are defined such that network integration issues are encap
`sulated and independent of the functional behavior. Also in
`the preferred embodiment, functions can interact without
`explicit knowledge of the network or devices on which the
`functions are hosted. Many common programming environ
`ments provide this type of distributed computing capability
`such as JAVA, CORBA, and Microsoft COM+, where
`Software components are defined using well defined inter
`faces, and details of network communication are managed
`by the platform through various means. With these distrib
`uted Software technologies, the present invention benefits
`from a simplified implementation without the loss of gen
`erality or platform independence.
`The NPO 101, as shown in FIG. 1, is controlled by an
`NPO controller 102, which interacts with the distributed
`navigation system through a navigation guidance interface
`105, which provides the access functions for working with
`the various navigation and guidance features. The naviga
`tion guidance interface 105 may incorporate the necessary
`elements to support one or more NPO controller types. The
`navigation management component 106 provides the means
`to manage and encapsulate common navigation functions
`independent of the navigation guidance interface 105,
`including configuration and session management, event
`notification, and commonly used utilities. The guidance
`component 107 provides automated guidance features,
`wherein one or more navigation components receive guid
`ance events regarding an NPO. The guidance component
`
`The present invention provides distributed navigation and
`automated route guidance using a plurality of networked
`computing devices, in which a computing device may host
`one or more navigation functional components. The physical
`location of a navigable physical object (NPO) is sensed and
`35
`communicated to one or more associated navigation com
`ponents using a data network, wherein the navigation com
`ponents perform their designated function for the purposes
`of providing guidance information to an NPO controller. An
`NPO controller directs the movement of an NPO and uses
`40
`guidance information to keep the NPO on a specified route.
`Types of NPO controllers include human or electronic
`devices capable of interpreting guidance information. The
`NPO controller interacts with the distributed navigation
`system through a navigation guidance interface, which pro
`vides the appropriate presentation of guidance information
`and functions for the particular type of NPO controller (e.g.,
`human-machine interface, or system to system). In particu
`lar, the present invention provides the structures and meth
`ods for a flexible navigation and guidance system supporting
`a variety of network capabilities and computing devices
`using the same software implementation.
`Operational Configuration
`
`45
`
`50
`
`In the present invention, the functional components of a
`navigation and automated guidance system are integrated
`using network protocols such that the physical Software
`deployment need not be explicitly defined. Users of the
`system work with the navigation components in the context
`of a session Such that each navigation component can
`manage a particular aspect of the navigation state with
`respect to a particular session. The navigation functional
`components communicate with each other in a peer-to-peer
`fashion in accordance with the session configuration infor
`mation. Using this approach, the system configuration can
`be altered as needed to support different types of computing
`
`55
`
`60
`
`65
`
`Hyundai Exhibit 1019, Page 21 of 35
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`US 7,149,625 B2
`
`7
`107 generates guidance status information in response to
`changes in the information provide by the physical location
`sensor 103. Guidance status information can be generated in
`two modes: real-time or predicted events. The selected mode
`of automated guidance depends on the particular session
`configuration. A caching component 108 may be included in
`Some navigation system configuration, where data originat
`ing from a navigation services component 109 may be
`cached by the caching component 108 in order to improve
`system performance in situations of low network data rates
`and low reliability. The caching component 108 enables
`components 105, 107, 106, and 103 to operate indepen
`dently of the navigation services component 109 for a
`certain period. The navigation services component 109
`provides navigation information, NPO tracking functions,
`and integration of other data and services commonly asso
`ciated with navigation and guidance. The navigation ser
`vices component 109 encapsulates the means to access and
`use navigation information as needed by the other naviga
`tion components 103, 105, 106, 107, and 108. In the
`preferred embodiment of the present invention, one instance
`of the navigation services component 109 is shared by
`multiple sessions and instances of the other navigation
`components.
`By defining the navigation system this way, and requiring
`that the navigation functional components communicate
`with each other using a distributed networking technology