Data processing: vehicles – navigation – and relative location – Navigation – Determination of travel data based on the start point and...
Reexamination Certificate
2002-06-15
2004-02-10
Nguyen, Thu (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Determination of travel data based on the start point and...
Reexamination Certificate
active
06691027
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a method for use in a navigation system for finding a shortest path, and more particularly, to a method for finding a shortest overall path length from the start to the final destination when a user of a navigation system wants to visit many intermediate destinations before the final destination.
BACKGROUND OF THE INVENTION
A navigation system performs travel guidance for enabling a user to easily reach the selected destination. A typical example is a vehicle navigation system. The present invention is not limited to a vehicle navigation system but is applicable to other types of navigation system such as a PDA (Personal Data Assistant), a cellular phone, and other portable navigation devices. However, for the convenience of explanation, the following description is made mainly for the vehicle navigation system.
Such a navigation system detects the position of the vehicle, reads out map data pertaining to an area at the vehicle current position from a data storage medium, for example, a CD-ROM (compact disk read-only memory) or a DVD (digital versatile disc), and displays a map image on a monitor screen (display) while superposing a mark representing the current location of the vehicle on a predetermined portion of the map image. Alternatively, such map data can be provided to the vehicle from a remote server through a communication network such as Internet.
The vehicle position is determined by self-contained navigation sensors (e.g. a distance traveled sensor and a bearing sensor) mounted in the vehicle or by a global positioning system (GPS) including an artificial satellite (satellite navigation). The satellite enables absolute position detection and higher position accuracy than the self-contained navigation sensors. However, the satellite navigation involves a problem of position detection failure such as in a tunnel or a building where the satellite radio signals are obstructed. Therefore, recent navigation systems utilize both self-contained navigation and satellite navigation functions to achieve improved performances.
As the present position of the vehicle changes with the travel of the vehicle, the vehicle current position mark in the map image on the screen is changed accordingly. Alternatively, the map is scrolled while the vehicle current position mark is fixed at a predetermined position, for example, at the center of the image. In either method, the navigation system enables the driver to recognize the map information of the area at the vehicle position at a glance.
When a destination is not set, such a navigation system functions as a locator map which indicates the current location of the vehicle on a map image. When the destination is set, the navigation system starts a route guidance function for setting a guided route from the starting point to the destination. Typically, the route guidance function performs an intersection guidance process in which a monitor screen displays an enlarged intersection diagram and the direction in which the vehicle is to travel while displaying the guide route on a map. When a destination is input, a CPU in the navigation system determines a most suitable guided route from the current vehicle position to the destination and successively stores nodes (expressed in longitude and latitude) constituting the guided route in a memory.
During actual traveling, the node series stored in the memory is searched for a portion of the guided route to be displayed in a map display area of the monitor screen, and the portion of the guided route is highlighted so as to be discriminable from other routes. When the vehicle is within a predetermined distance of an intersection it is approaching, an intersection guidance diagram (an enlarged or highlighted intersection diagram with an arrow indicating the direction in which the vehicle is to turn at the intersection) is displayed to inform a driver of the desired one of roads or directions selectable at the intersection.
FIG. 1A
shows an example of a locator map display containing a vehicle current position mark VCP on a map image
21
. Typically, a navigation system shows the street on which the vehicle is running in the map image
21
and a name of the street such as “W 190TH ST” in an information box
23
on the monitor screen. Other information such as a north pointer NP, a map scale and a current time may also be illustrated on the display screen. In this manner, the locator map display shows the current position of the vehicle on the map image, however, it does not perform the route guidance function because the destination is not set in the navigation system.
FIG. 1B
shows an example of route guidance display which performs the route guidance function. The route guidance display is activated after specifying the destination. In addition to the map image
21
similar to the locator map of
FIG. 1A
, this example further shows an arrow indicating the direction (left) in which the vehicle is to turn at the intersection in a guidance information box
22
at the top of the screen. The guidance information box
22
also shows a name of the street “PRAIRIE AVE” which intersects with the current street “W 190TH ST” and a distance to the intersection. Thus, the navigation system indicates that the vehicle should make a left turn at the intersection with “PRAIRIE AVE”.
Typically, the current street “W 190TH ST” and the left side of the street “PRAIRIE AVE” will be highlighted in the map image
21
. Further, such route guidance is accompanied by voice instructions. If the direction of travel in the next intersection is left, the navigation system gives spoken guidance such as “turn left at the next intersection”. In this example, an information box
24
at the bottom of the display screen includes information regarding the remaining distance to the final destination and an estimated time to reach the final destination.
In order to be guided by the route guidance mode such as shown in
FIG. 1B
, a destination must be specified in the navigation system so that the system can find one or more routes to get to the destination.
FIGS. 2A-2C
show examples of display shown on the monitor screen during the operation of inputting the destination.
By operating a menu key, a main menu screen
25
such as shown in
FIG. 2A
is displayed on the navigation system and a menu item “Destination” is selected from the main menu. This allows the navigation system to display an “Enter Destination by” screen
27
as shown in
FIG. 2B
for specifying an input method for selecting the destination. The “Enter Destination by” screen
27
lists various methods for selecting the destination including “Address” for specifying the city and address of the destination, “Intersection” for specifying the names of two streets in the city which intersect with one another, and “Point of Interest” for selecting the programmed destination based on the name, category or telephone number.
Other methods in the “Enter Destination by” screen
27
include “Recent Route” for specifying the destination based on the recent destinations saved in the navigation system, “Address Book” for selecting the address of the destination out of the addresses stored in the system, and “Today's Plan” for specifying two or more destinations in the navigation system. For example, when a user wants to go to several destinations before the final destination, the navigation system calculates an efficient order and routes to such destinations.
When selecting, for example, the “Address” in
FIG. 2B
, the navigation system displays an “Enter Street Name” screen such as shown in FIG.
2
C. The screen of
FIG. 2C
is basically a key board
38
for inputting the city and address in an address input box
37
on the monitor screen. The user inputs the street name and number in the address input box
37
through the key board
38
.
After inputting the destination, the navigation system determines a route to the destination based on, for example, the shortest way to reach the destination, the route using many freeways
Alpine Electronics Inc.
Muramatsu & Associates
Nguyen Thu
LandOfFree
Method and apparatus for finding shortest overall path of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for finding shortest overall path of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for finding shortest overall path of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3342629