Beacon Navigation GmbH v. Volvo Car Corporation et al

Filing 1

COMPLAINT filed with Jury Demand against Volvo Cars Corporation, Volvo Cars of North America LLC. - Magistrate Consent Notice to Pltf. ( Filing fee $ 350, receipt number 0311-957360.) - filed by Beacon Navigation GmbH. (Attachments: # 1 Exhibits A - C, # 2 Civil Cover Sheet)(dzs, ) Modified on 10/12/2011 (dzs, ).

EXHIBIT A

EXHIBIT B

EXHIBIT C

111111

United States Patent

[19]

1111111111111111111111111111111111111111111111111111111111111
US005878368A

[11]

DeGraaf

[45]

[54]

Inventor:

[73]

5,465,088
5,475,387
5,513,110
5,521,826
5,568,390
5,612,882
5,638,280
5,684,704
5,712,788
5,717,593
5,729,458
5,731,978

NAVIGATION SYSTEM WITH USER
DEFINABLE COST VALUES

[75]

Assignee: Magellan DIS, Inc., Rochester Hills,
Mich.

[ * ] Notice:

Brent L. DeGraaf, Canton, Mich.

This patent issued on a continued prosecution application filed under 37 CFR
1.53(d), and is subject to the twenty year
patent term provisions of 35 U.S.c.
154(a)(2).

[21]
[22]

Filed:

[51]
[52]
[58]

[56]

Sep. 13, 1996
6

Int. CI. ....................................................... G06G 7/78
U.S. CI. .......................... 701/209; 701/201; 701/210;
73/178 R; 340/990; 340/988
Field of Search ..................................... 701/200, 201,
701/202, 208, 209, 210, 212, 215, 216,
213, 211, 25, 26; 340/988, 990, 995; 73/178 R
References Cited
U.S. PATENT DOCUMENTS
4,086,632 4/1978 Lions ......................................
5,031,104 7/1991 Ikeda et al. .............................
5,220,507 6/1993 Kirson .....................................
5,289,195 2/1994 Inoue . ... ... ... ... .... ... ... ... ... ... ......
5,311,173 5/1994 Komura et al. .........................
5,369,588 11/1994 Hayami et al. .........................
5,371,678 12/1994 Nomura ..................................
5,406,490 4/1995 Braegas. ... ... ... .... ... ... ... ... ... ......
5,428,545 6/1995 Maegawa et al. ......................

701/210
701/209
701/202
701/208
701/208
701/209
701/210
701/209
701/201

11/1995
12/1995
4/1996
5/1996
10/1996
3/1997
6/1997
11/1997
1/1998
2/1998
3/1998
3/1998

5,878,368
*Mar. 2, 1999

Braegas ................................... 340/905
Matsumoto ............................... 701/25
Fujiita et al. ........................... 701/207
Matsumoto ............................. 701/208
Hirota et al. ............................ 701/209
LeFebvre et al. ...................... 701/209
Nishimura et al. ..................... 701/209
Okazaki .................................. 701/201
Liaw et al. .............................. 701/209
Gvili ....................................... 701/207
Poppen ...................................... 701/25
Tamai et al. ............................ 701/201

Primary Examiner-Jacques H. Louis-Jacques
Attorney, Agent, or Firm-Howard & Howard
[57]

Appl. No.: 713,627

Patent Number:
Date of Patent:

ABSTRACT

A navigation system permits the user to designate certain
roads or areas to avoid when planning a route. The navigation system generally includes a database of road segments
and a cost associated with the road segments, such as
estimated time of travel across that road segment and
estimated length of travel across that road segment. The
navigation system determines a route from a selected beginning point to a desired destination by evaluating the cost of
the road segments to be traveled in several potential routes
and recommends the potential route having the lowest total
cost. The user can selectively modify the cost of selected
road segments to indicate a preference or avoidance of such
roads. By increasing the cost of a road segment, the navigation system is less likely to recommend a potential route
which includes that road segment. Similarly, by decreasing
the cost of a selected road segment, the navigation system is
more likely to recommend a potential route which includes
that road segment.
26 Claims, 3 Drawing Sheets

u.s.

Patent

20~
34

Mar. 2, 1999

5,878,368

Sheet 1 of 3

32

36

22

fFig - 1

24
TURN RIGHT ON
13 MILE RD

DISTANCE TO TURN:

fFig-3

1.3 MI

78

d

•
rJl
•

50

52

~
~

EDIT CONGESTED ROADS/
PERSONAL PREFERENCE

PLAN ROUTE

157

ROUTING CRITERIA

56
99

96

SELECT DES TINA TlON FROM:

128

~

158

~

!"l

TIME VS DISTANCE
CONSIDERA TION

L4 II

' - ' .... \on

SELECT
SECOND
ROAD

168

~

n.....

PLAN ROUTE
TO:
~ADDRESS

INPUT
ADDRESS
170

I

=

i

INPUT STARTING PT.

,

~
.....
.....

[I I-II~H

EST. TIME
ONLY

+NEAREST

~N

'""'"
\C
\C
\C

DISC ..
ONLY

PT.

'JJ.

FREEWAY USAGE
172

132-----11

~

=-

Lill nTI1~H

o
....,

LEAST

[QK]

MOST

~
~

.....
N

~

VEH. STATIONARY
TOLL ROAD USAGE

4 I I I I I IJ~ H

178

L
LEAST

182----J EDIT ROUTE LIST
ADD TO CONGESTED ROADS

fFig-2
186

136

[QK]

MOST

Ul
....

00
""-l

00
....

~

0\
00

u.s. Patent

5,878,368

Sheet 3 of 3

Mar. 2, 1999

176

PLAN ROUTE

~
DETERMINE POTENTIAL
ROUTES

~19 4

~
FACTOR CONGESTION
LEVELS

~19 6

~
FACTOR HIGHWA Y
PREFERENCE/AVOIDANCE

~19 8

~
FACTOR TOLL ROAD
PREFERENCE/AVIODANCE ~20 o
~.

DETERMINE LOWEST TIME
COST POTENTIAL ROUTE

~2 02

~
DETERMINE LOWEST DISTANCE
COST POTENTIAL ROUTE
~ 204

~
EVALUATE TIME
DISTANCE

V.

~20 6

~
SELECT RECOMMENDED
~20 8
ROUTE

fFig-4

5,878,368
1

2

includes a "cost" for each road segment, such as estimated
time of travel across that road segment and estimated length
of travel across that road segment. A beginning point relative
BACKGROUND OF THE INVENTION
to the database of roads is input from a position determining
5 device, such as a GPS system, or is input by the user,
This invention generally relates to navigation or route
utilizing a mouse, keyboard or joystick. The user then selects
guidance systems that can be tailored to a user's particular
a desired destination relative to the database of roads. The
wishes.
user selectively adjusts the cost for selected road segments
Navigation systems generally provide a recommended
or groups of road segments. When the navigation system
route from a starting point to a desired destination. Generally 10 determines a route from the selected beginning point to the
the starting point and desired destination are selected from
desired destination, the navigation system evaluates the cost
a large database of roads stored in a mass media storage,
of the road segments to be traveled in several potential
such as a CD ROM, which includes the roads in the area to
routes and recommends the potential route having the lowest
be traveled by the user. The navigation system can be located
total cost.
in a personal computer or can be installed in a vehicle. If the 15
Because the user can selectively modify the cost of
navigation system is installed in a vehicle, the starting point
selected road segments, the user can indicate a preference or
is typically the current position of the vehicle, which can be
avoidance of such roads which will be considered by the
input from an associated positioning determining device,
navigation system when planning a route. For example, if
such as a GPS (Global Positioning System) receiver.
the cost of a road segment is increased, the navigation
The navigation system determines a route from the start- 20 system is less likely to recommend a potential route which
ing point to the destination utilizing an algorithm wellincludes that road segment. Similarly, if the cost of a
known to those in the art and currently in use in many
selected road segment is decreased, the navigation system is
navigation systems. Usually there are many potential routes
more likely to recommend a potential route which includes
between the selected starting point and the desired destinathat road segment.
tion. The navigation system selects a recommended route 25
Adjusting the cost of selected road segments can have
based upon certain "cost" values associated with each segmany potential applications. First, by increasing the cost of
ment of road in the road database. These cost values include
certain road segments selected by the user, the user can
the length of the road segment and the estimated time of
indicate the road segments that the user desires to avoid,
travel through the road segment. The navigation system
because the user believes these road segments to be conselects the potential route with the lowest total cost to be the 30 gested or in an unsafe area. Alternatively, the navigation
recommended route. Depending upon the predetermined
system can include a data receiving device which receives
algorithm of the navigation system, the navigation system
information regarding congested road segments and autowill recommend the route with the shortest total length, the
matically updates congestion level values associated with
lowest total time, or some weighted average of length and
each road segment.
35
time.
By categorizing each road segment into a road type, such
The recommended route is then displayed to the user as a
as highway, toll road, etc., the user can modify the cost of
map showing the starting point and desired destination and
selected types of roads, thereby indicating a preference for
highlighting the recommended route. Preferably, if the navihighways or toll roads or an aversion to highways or toll
gation system is installed in a vehicle, the navigation system
roads. Further, by modifying the estimated time of travel of
displays the current position of the vehicle and turn-by-turn 40 road segments differently than the estimated length of travel
instructions to the driver, guiding the driver to the selected
of road segments, the user can adjust the preference for a
destination.
route having a low estimated time of travel or a low
Some drivers prefer to avoid certain roads that they
estimated distance of travel.
believe to be congested or certain areas that they believe to
be unsafe. Some drivers may have a preference or aversion 45
BRIEF DESCRIPTION OF THE DRAWINGS
for particular types of roads such as highways or toll roads.
The above, as well as other advantages of the present
Further, a route which is the shortest distance is sometimes
invention, will become readily apparent to those skilled in
preferred, while a route which is the lowest total time of
the art from the following detailed description of a preferred
travel is preferred at other times.
50 embodiment when considered in the light of the accompaCurrent navigation systems have several limitations in
nying drawings in which:
how they select a potential route as the recommended route.
FIG. 1 is a schematic of the navigation system of the
The known navigation systems permit the driver to select
present invention installed in a vehicle having a position
one of the following preferences: fastest route; shortest
route; use highways; avoid highways. However, the known 55 determining device;
FIG. 2 is a flow chart of the navigation system of FIG. 1;
systems do not permit the driver to adjust a weighting factor
to be given to these preferences; nor can the driver adjust a
FIG. 3 is a screen of the display of the navigation system
of FIG. 1 illustrating a route guidance instruction;
balance between the fastest and shortest routes. Further, the
known navigation systems do not permit the user to desigFIG. 4 is a flow chart of the Route Planning routine in
nate selected areas or roads to avoid or to adjust a 60 FIG. 2.
preference/aversion factor of the road or area.
DETAILED DESCRIPTION OF A PREFERRED
SUMMARY OF THE INVENTION
EMBODIMENT
NAVIGATION SYSTEM WITH USER
DEFINABLE COST VALUES

The present invention provides a navigation system which
permits the user to modify the cost of roads when planning
a route. The navigation system generally includes a database
of roads to be traveled by a user. Each road in the database

65

The navigation system 20 of the present invention is
shown schematically in FIG. 1. The navigation system 20
includes a CPU 22 connected to a display 24, such as a high
resolution LCD or flat panel display. The CPU 22 is also

5,878,368

3

4

selects a road in step 108 by entering the first few letters of
connected to an input device 26, such as a mouse or
keyboard. Alternatively, the display 24 can be a touch screen
the road name and then selecting the road from an alphadisplay. The navigation system 20 further includes a databetized list. If the user elects to add a road in another area,
base 28 connected to the CPU 22. The database 28 is a mass
the user must first select a state in step 110 and a city or area
media storage device, such as a CD ROM which includes a 5 in step 112.
map of all of the roads in the area to be traveled by the user.
After selecting a road in step 108, the user selects a
Each road in the database is divided into road segments,
particular road segment or segments in step 114 such that the
each having an associated set of cost values, which indicate
congested area includes a road segment between selected
the "cost" of traveling that road segment. For example, the
cost values include the length of the road segment, the 10 exits, a single exit, a single intersection, the entire road
within a city, the entire road within an area, etc. If the user
estimated time to travel the road segment, the type of road
has not selected a road segment which is a one way street,
(i.e. highway, secondary road, toll road, one way, etc.), and
the user can select to edit the congestion level in a single
congestion level.
direction or in both directions in step 116. The congestion
The navigation system 20 can, but need not, be installed
level is then set in step 103.
in a vehicle 32. The navigation system 20 can be used in
conjunction with position-determining devices, such as a 15
If the user elects to delete items from the congested road
GPS system 34, a gyroscope 36, a compass 38, and a wheel
list in step 96, a list of all roads, cities, areas, or road
speed sensor 40, all connected to the CPU 22 [connections
segments for which a congestion level has been set, is
not shown for simplicity]. Such position determining
displayed. Utilizing the mouse 26, the user selects an item or
devices are well known and are commercially available.
items to be deleted from the congested road list. The user can
Preferably, a combination of these position determining 20 utilize this adjustment to select or not select roads, geodevices is utilized. The navigation system 20 further
graphic areas, etc. that the user wishes to avoid or use for
includes a data receiver 42, such as a radio receiver for
purely personal reasons. The display at step 96 may include
receiving up-to-date broadcast information regarding the
the legend "Edit Personal Preference", or a separate election
congestion levels of area road segments. Congestioncan be add to the system for personal preference. The user
monitoring devices are known and currently used to auto- 25
would increase the congestion value for an area or road that
matically monitor the congestion levels of certain road
he wishes to avoid. Also, the system could include a display
segments, typically near intersections. Preferably, informaor "Personal Preference" that can be adjusted and then used
tion regarding congestion from the congestion-monitoring
similarly to the congestion value.
devices is broadcast to the surrounding area and received by
The user can also elect to edit the congestion levels in step
the data receiver 42. The data receiver 42 sends the con- 30
99, in which case the entire list of roads, road segments,
gestion information to the CPU 22, which stores the updated
cities, and areas is displayed. The user selects an item from
congestion information. Alternatively, many radio stations
the list utilizing the mouse 26, and sets the congestion level
broadcast information regarding the congestion levels of
for that item in step 103.
area road segments. This congestion information can be
added manually by the user to the CPU 22.
If the user elects to edit the routing criteria 56 from the
35
The operation of the navigation system 20 is shown in
main menu 50, the user can modify the time/distance factor
FIG. 2. For purposes of illustration, the navigation system 20
in step 128 utilizing the mouse 26. Preferably, the user
of the present invention will be described as installed in a
selects one of at least 7 levels for the time/distance factor.
vehicle 32 having position determining devices. At powerThe time/distance factor is a value to be multiplied by an
up, the navigation system 20 preferably begins in the main 40 estimated time of travel to weight it for comparison against
menu 50, which informs the user that he may elect to plan
an estimated length of travel. The lowest level, levell,
would preferably have a time/distance factor of zero miles
a route 52, edit congested roads 54, or edit routing criteria
per hour, indicating an absolute preference for the route
56.
having the lowest estimated time of travel, rather than
By selecting to edit congested roads in step 54, the user
can delete items from the congested road list in step 96, add 45 shortest length of travel. The highest level, level 7, would
preferably have a time/distance factor of 1000 miles per
items to the congested road list in step 98, or edit the
hour, indicating an almost absolute preference for the lowest
congestion levels in step 99. If the user elects to add items
length of travel route, rather than the lowest estimated time
in step 98, the display 24 prompts the user to select a road
of travel route. The middle level, level 4, would preferably
segment from a local area, a road segment in another area,
or all road segments in an area. Utilizing the mouse 26, if the 50 have a time/distance factor of 45 miles per hour, indicating
a medium preference between the route having the lowest
user wishes to add all road segments in an area to the
estimated time of travel and the road having the lowest
congested road list, the user selects a state in step 100 and
estimated length of travel. The other levels would have
a city or area in step 102. The user then sets the congestion
intermediate time/distance factors.
level in step 103. Preferably, the congestion level is selected
from at least 3 levels and most preferably 14 levels. 55
From the routing criteria menu 56, the user can elect to
Preferably, the lowest congestion level assigns a congestion
modify the highway preference/avoidance factor in step 132.
value of 1.0, signifying no known congestion. Level 14, the
The highway preference/avoidance factor multiplies the cost
highest level, would assign a congestion level on the order
of any highways in potential routes. Preferably, the display
of 10,000, indicating an almost absolute avoidance, unless
24 displays at least 7 levels to the user, which can be selected
there is no alternate route, such as if the destination or 60 using the mouse 26. The middle level, level 4, would have
beginning point is located on that road segment. Preferably,
a highway preference/avoidance factor of 1.0, indicating no
the congestion value for each level increases approximately
preference or avoidance of highways. Levell, avoidance,
by a factor of 1.7, such that the congestion value is assigned
would preferably have a highway preference/avoidance facby level 2 is 1.7, level 3 is 2.89, level 4 is 4.9 and level 5 is
tor of 1000, indicating an almost absolute total avoidance of
8.35, etc.
65 highways. Level 7, preference, would preferably have a
If the user elects to add a road segment in the immediate
highway preference/avoidance factor of 0.2, indicating a
area surrounding the present vehicle location, the user
preference for highways, by effectively decreasing the cost

5,878,368

5

6

of highways by a factor of 5. Preferably, the navigation
180. As the user scrolls up and down through the road
system 20 further includes the data receiver 42 which
segments in the recommended route list, a graphical image
of the recommended maneuver (i.e., turn right or turn left)
receives information regarding congested road segments in
is displayed adjacent the route list. In step 182, the user can
the surrounding area and sends the congestion information
to the CPU 22, where the congestion levels of the appro- 5 edit the route list by selecting one of the segments in the
priate road segments are updated. Alternatively, or in
recommended route list. In step 186, the user adds the
addition, the data receiver 42 can be a standard radio which
selected road segment from the recommended route list to
receives local broadcasts regarding the congestion levels of
the congested roads list. In step 190, the user sets the
congestion level for the selected road segment. Preferably, if
area road segments, in which case the user could manually
update the congestion levels for the appropriate road seg- 10 the item was not previously on a congested road list, the
ments.
congestion value is set to 1.7. If the road segment was
already on the congested road list, the congestion value is
From the routing criteria menu 56, the user can also elect
multiplied by 1.7 in step 190. If the user edits the route list,
to modify the toll roads preference/avoidance factor in step
the navigation system 20 must replan the route in step 176,
136. Preferably, the display 24 displays to the user at least
7 levels for the toll road preference/avoidance factor, which 15 utilizing the new cost values. If the vehicle 32 is moving, the
navigation system 20 will then proceed to step 178, where
can be selected utilizing the mouse 26. The middle level,
the display 24 will display turn-by-turn route guidance
level 4, would have a toll road preference/avoidance factor
instructions to the driver. As shown in FIG. 3 the display 24
of 1.0, indicating no preference or avoidance of toll roads.
preferably displays a map of the immediate area showing the
Levell, avoidance, would preferably have a toll road/
avoidance factor of 10, indicating an avoidance of toll roads 20 present position of the vehicle and the next maneuver in the
recommended route.
so long as the cost is otherwise increased by less than a
factor of 10. Level 7, preference, would preferably have a
The Route Planning routine 176 is shown in detail in FIG.
4. First, the CPU 22 determines potential routes from the
toll road preference/avoidance factor of 0.2, indicating a
preference for toll roads so long as the cost is not otherwise
beginning point to the desired destination in the road dataincreased by a factor of 5. The remaining levels would have 25 base 28 in step 194. In step 196, the CPU 22 multiplies the
cost of each road segment by the congestion level for that
appropriately scaled intermediate factors.
road segment if the congestion level has been set. For
If the user elects to plan a route 52, the navigation system
example, if one of the road segments in one of the potential
20 inputs a starting point relative to the database 28 in step
routes from the starting point to the selected destination
157. If the navigation system 20 includes a position determining devices, the current position of the vehicle 32 is 30 includes a congestion value of 1.7, the length and estimated
time of travel for that road segment are multiplied by 1.7.
input as the starting point for the route to be planned.
Otherwise the user selects a starting point utilizing the
In step 198, the CPU 22 multiplies the cost of each road
segment which is a highway by the highway preference/
display 24 and mouse 26. Preferably the user types in the
first few letters of the name of the road and then selects the
avoidance factor. If the user has defined a preference/
starting point road from a list of roads. The user then selects 35 avoidance value for highways, the cost (time and length) of
the highway road segments in the potential routes are
an intersection or address as a beginning point.
multiplied by the highway preference/avoidance value. If
The navigation system 20 then inputs the destination. In
highways are preferred, the highway preference/avoidance
step 158, the user selects a destination from the local area
value is less than 1, thereby reducing the length and estisurrounding the current vehicle position or from all areas. If
the user wishes to select a destination from a local area, the 40 mated time of travel for purposes of estimating the "cost" of
travelling highways. If the highway preference/avoidance
user selects a road as the destination to which the route will
value is greater than 1, the length and estimated time of
be guided in step 160. Otherwise the user must first select a
travel of highway road segments will be increased, thereby
state in step 162 and a city or area in step 164. In step 166,
the navigation system 20 requests whether to plan the route 45 increasing the "cost" of highway road segments.
In step 200, the CPU 22 multiplies the cost of any
to a specific intersection of the selected road in step 168, a
potential road segments which are toll roads by the toll road
specific address on the selected road in step 170 or the
preference/avoidance factor. Again, a value less than one
nearest point on the selected road in step 172.
would reduce the effective cost of travelling toll roads,
In step 176, the navigation system 20 plans a route from
the starting point to the selected destination utilizing the 50 thereby indicating a preference for toll roads. A value greater
than one would increase the effective cost of toll roads,
roads in the database 28. The navigation system 20 evaluates
thereby indicating an aversion to toll roads.
the total cost of a plurality of potential routes between the
In step 202, the CPU 22 selects the potential route which
starting point and selected destination. The navigation syshas the lowest total time cost, after factoring in the aforetem 20 selects the potential route from the starting point to
the selected destination which has the lowest total cost as 55 mentioned user preferences. Similarly, in step 204, the CPU
22 selects the potential route which has the lowest distance
modified by the user in the Route Planning routine 176,
cost, after factoring in the afore-mentioned user preferences.
described more fully below.
In step 206, the CPU 22 compares the lowest time cost
If the vehicle 32 is moving when the route planning
potential route with the lowest distance cost potential route.
routine 176 is completed, the display 24 of the navigation
system 20 displays route guidance information in step 178. 60 The time cost of the lowest time cost route is multiplied by
the time/distance factor to convert it to a distance to be
Preferably, the navigation system 20 displays "turn-by-turn"
compared to the distance cost in the lowest distance cost
information to the driver, i.e., the display 24 displays a map
potential route.
of the immediate area showing the present position of the
In step 208, the CPU 22 selects the route with the lower
vehicle and the next maneuver in the recommended route. If
the vehicle 32 is stationary at the time the route planning 65 distance cost, after converting the time of the lowest time
routine 176 is complete, the display 24 preferably displays
cost route to distance utilizing the time/distance factor. For
example, at levell, the time/distance factor would be set to
a list of the road segments in the recommended route in step

5,878,368
7

8

zero, in which case the lowest time cost potential route
recommended road segments other than said selected at least
one road segment.
would always be selected over the lowest distance cost
8. The navigation system of claim 1 further including a
route. At level 4, each hour in the lowest time cost route
memory storing each selected road segment for which the
would be converted to 45 miles, indicating a medium
balance between the shortest route and the quickest route. At 5 cost has been adjusted and the associated adjusted cost of
said selected road segment, wherein said beginning point is
level 7, each hour in the lowest time cost route would be
a first beginning point, said destination is a first destination
converted to 1000 miles, which would effectively ensure that
and said route is a first route, said system for determining a
the lowest distance route would have a lower cost than the
route determining a second route from said database of roads
lowest time cost route, indicating a strong preference for the
10 between a second beginning point different from said first
shortest route rather than the quickest route.
beginning point and a second desired destination based upon
Preferably, the settings selected by the user are stored and
said adjusted cost of each said selected road segment as
are utilized when the user plans the next route to a new
stored in said memory.
destination. Optionally, the navigation system 20 can reset
9. The navigation system of claim 8 wherein each said
the congestion levels, highway preference/avoidance, toll
15 selected road segment and its associated adjusted cost is
road preference/avoidance and time v cost factor when the
further associated with a user.
navigation system 20 is turned off, or when the destination
10. The navigation system of claim 1 wherein said road
is reached.
segments each have an associated road type, said user input
In accordance with the provisions of the patent statutes,
device selecting a road type and adjusting the cost for all
the present invention has been described in what is consid20 road segments of said selected type.
ered to represent its preferred embodiment. However, it
11. The navigation system of claim 10 wherein said road
should be noted that the invention can be practiced othertype includes freeways.
wise than as specifically illustrated and described without
12. The navigation system of claim 1 wherein said user
departing from its spirit or scope.
input device selects between decreasing and increasing the
What is claimed is:
25 cost of said selected road segment.
1. A navigation system comprising:
13. A navigation system comprising:
a database of road segments to be travelled by a user, said
a database of road segments to be travelled by a user, said
database including a cost associated with each said road
database including a cost associated with each said road
segment;
segment, said road segments each having a time cost
a system for selecting a beginning point relative to said 30
and a distance cost;
database of roads;
a system for selecting a beginning point relative to said
a user input device for selecting a desired destination
database of roads;
relative to said database of roads, said user input device
a user input device for selecting a desired destination
manually selecting at least one of said road segments
relative to said database of roads;
and adjusting said cost of said at least one selected road 35
a system for adjusting said cost of at least one selected
segment; and
road segment of said plurality of road segments utiliza system for determining a route from said database of
ing said user-input device; and
roads between said beginning point and said desired
a system for determining a route from said database of
destination based upon said adjusted cost of said
roads between said beginning point and said desired
selected at least one road segment.
40
destination based upon said adjusted cost of said
2. The navigation system of claim 1 wherein said user
selected road segment, said system for determining a
input device enters the first few letters of said selected road
route comparing the time cost of a first road segment
segment, said user input device selecting said selected road
with a distance cost of a second road segment and
segment from a list of road segments including said first few
recommending a route based upon a time/distance
45
letters.
weighting factor, said user input device adjusting said
3. The navigation system of claim 1 wherein said user
time/distance weighting factor.
input device selects a city and adjusts the cost for a plurality
14. The navigation system of claim 13 wherein said road
of road segments in said selected city.
segments each have an associated road type, said system for
4. The navigation system of claim 1 wherein said user
adjusting said cost adjusting the cost for all road segments
input device selects from at least three values in order to 50 of a selected type.
adjust said cost of said at least one selected road segment.
15. A method for planning a route including the steps of:
5. The navigation system of claim 1 wherein said system
a) selecting a beginning point relative to a database of
for adjusting said cost includes a system for receiving
roads;
congestion information, said congestion information includb) selecting a destination relative to said database of
55
ing identification of a congested area.
roads;
6. The navigation system of claim 1 wherein said user
c) manually selecting a road segment from said database
input device selects a road segment to avoid, said system for
of roads;
adjusting said cost increasing the cost for said selected road
d) adjusting a cost associated with said selected road
segment to avoid.
segment; and
7. The navigation system of claim 1 wherein said system 60
e) determining a route from said database of roads from
for determining a route recommends a plurality of recomsaid beginning point to said destination based upon said
mended road segments in said route, said user input device
adjusted cost of said selected road segment.
selecting at least one, but not all, of said plurality of
16. The method for planning a route according to claim 15
recommended road segments, said user input device selectively editing the cost of said selected at least one of said 65 wherein said step c) further includes the steps of:
entering the first few letters of the name of said selected
recommended road segments, said system for determining a
road segment;
route determining a second route including said plurality of

5,878,368

9
selecting said road segment from a list of road segments
having said first few letters.
17. The method for planning a route according to claim 15
further including the steps of:
associating an estimated time of travel with said road
segment;
associating a length of travel with said road segment; and
adjusting the cost of a road segment proportionally to its
estimated time of travel or estimated length of travel.
18. The method for planning a route according to claim 15
further including the steps of:
selecting a time/distance factor for evaluating the cost of
potential routes between said beginning point and said
desired destination;
selectively adjusting said time/distance factor; and
determining a route from said database of roads from said
beginning point to said desired destination based upon
said time/distance factor, said estimated time of travel
and said length of travel.
19. The method for planning a route according to claim 15
further including the steps of:
determining a present position relative to said database of
roads; and
selecting said present position relative to said database of
roads as said beginning point.
20. The method for planning a route according to claim 15
further including the steps of:
displaying a list of road segments for which the cost has
been adjusted;
selecting said selected road segment from said list of road
segments; and
adjusting the cost of said selected road segment.
21. The method for planning a route according to claim 15
wherein said step d) includes the step of decreasing the cost
of said selected road segment.
22. The method for planning a route according to claim 15
wherein said step d) includes the step of selecting between
increasing or decreasing the cost of said selected road
segment.
23. A method for planning a route including the steps of:
a) selecting a beginning point relative to a database of
roads;
b) selecting a destination relative to said database of
roads;
c) adjusting a cost associated with a selected road segment
in said database of roads; and
d) selecting a time/distance factor for evaluating the cost
of potential routes between said beginning point and
said desired destination;
e) comparing the estimated time of travel of a first
potential route with the length of travel of a second
potential route utilizing said time/distance factor;

10
f) determining a route from said database of roads from

5

10

15

20

25

30

35

40

45

50

said beginning point to said desired destination based
upon said time/distance factor, said estimated time of
travel and said length of travel.
24. A method for planning a route including the steps of:
a) selecting a beginning point relative to a database of
roads;
b) selecting a destination relative to said database of
roads;
c) selecting a road segment to avoid;
d) increasing the cost of said road segment;
e) comparing said increased cost for said road segment to
avoid with a cost of an alternative route not including
said road segment; and
f) determining a route from said database of roads from
said beginning point to said destination based upon said
increased cost.
25. The method for planning a route according to claim 24
further including the steps of:
displaying a first route comprising a plurality of road
segments from said beginning point to said destination;
selecting one of said plurality of road segments as a road
segment to avoid; and
determining a second route to said destination from said
position of said vehicle, said second route not including
said road segment to avoid.
26. A method for planning a route including the steps of:
a) selecting a beginning point relative to a database of
roads, said database of roads having a plurality of road
segments;
b) selecting a destination relative to said database of
roads;
c) associating a time cost with each said road segment;
d) associating a distance cost with each said road segment;
e) selecting a first time/distance factor;
f) selecting a first recommended route from said beginning point to said destination based upon said time cost
of said road segments, said distance cost of said road
segments and said first time/distance factor;
g) changing said first time/distance factor after said step
f) to a second time/distance factor; and
h) selecting a second recommended route from said
beginning point to said destination based upon said
time cost of said road segments, said distance cost of
said road segments and said second time/distance
factor, said second recommended route including at
least one road segment not included in said first recommended route.

* * * * *