a2, United States Patent
`US 6,175,803 B1
`(10) Patent No.:
`Jan. 16, 2001
`(45) Date of Patent:
`Chowanicet al.
`
`US006175803B1
`
`(54) WEHICLE NAVIGATION ROUTE
`GENERATION WITH USER SELECTABLE
`RISK AVOIDANCE
`
`(75)
`
`Inventors: Andrea Bowes Chowanic, Bloomfield
`Township; David Arthur McNamara,
`Saline, both of MI (US)
`
`5,428,545
`5,452,212
`5,486,822
`5,508,930
`5,610,821
`5,612,882
`5,729,458
`5,802,492 *
`
`6/1995 Maegawaet al.ee 701/210
`wee FOL/211
`9/1995 Yokoyamaetal. ..
`
`.. 340/995
`1/1996 Tenmokuetal. ....
`701/201
`4/1996 Smith, Jr...
`ww. 455/456
`3/1997 Gazisetal. ......
`3/1997 LeFebvreetal.
`we 701/209
`3/1998 Poppen oo...
`w+ 705/400
`9/1998 DeLormeet al. oe 701/200
`
`
`
`(73) Assignee: Ford Global Technologies, Inc.,
`Dearborn, MI (US)
`
`* cited by examiner
`
`(*) Notice:
`
`Under 35 U.S.C. 154(b), the term of this
`patent shall be extended for 0 days.
`
`(21) Appl. No.: 09/128,687
`
`Primary Examiner—William A. Cuchlinski, Jr.
`Assistant Examiner—Yonel Beaulieu
`(74) Attorney, Agent, or Firm—Mark L. Mollon
`
`(57)
`
`ABSTRACT
`
`(22)
`
`Filed:
`
`Aug. 4, 1998
`
`Anavigation system for automotive vehicles generates navi-
`gation routes between an initial
`location and a desired
`(SL) Ute C17 cacccccssscssssssssssssnsessnseseeseensee GO1C 21/00
`destination using a route criteria includingastatistical risk
`index, such as a CAP crime index score. A user of the
`(52) U.S. Cle ceesecscscssscssseessee 701/209; 701/23; 701/25;
`navigation system can customize their own desired risk
`701/26; 701/201; 701/209; 701/211; 73/178 R;
`threshold to be used in optimizing the navigation route. A
`940/988; 940/990; 940/995
`particular route segment with a risk index above a risk
`(58) Field of Search 0... 701/209, 211,
`threshold can be eliminated from potential routes except
`701/208, 23, 25, 26, 117, 201, 202; 340/990,
`when the route segment contains the destination or is a
`995, 988; 73/178 R
`freeway segment. In another embodiment, the weightor cost
`associated with including a route segment in a navigation
`route is adjusted according toits statistical risk index.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,220,507
`
`6/1993 Karson caecsesssssssssessssssssssseeeeee 701/202
`
`4 Claims, 3 Drawing Sheets
`
`13
`
`Display
`
`Manual Inputs
`
`
`
`16
`
`Speech
`Generator
`
`17
`
`
`
`
`
`Navigation Controller
`
` Vehicle
`
`
`
`Position
`
`
`
`Locator
`| Database
`
`
`
`Navigation
`
`17
`
`IPR2017-02022
`Unified EX1007 Page1
`
`IPR2017-02022
`Unified EX1007 Page 1
`
`

`

`U.S. Patent
`
`Jan. 16, 2001
`
`Sheet 1 of 3
`
`US 6,175,803 B1
`
`Display
`
`17
`
`
`Manual Inputs
`
`
`
`
`
`Wireless
`Vehicle
`
`Communcation
`
`
`Position
`
`Link
`
`Locator
`
`25.
`
` 5 2
`
`
`
`EES. =.
`
`IPR2017-02022
`Unified EX1007 Page 2
`
`
`
`Destination Input
`Destination Memory
`System Settings
`
`DESTINATIONINPUT
`Adaress
`Cross Street
`Points Of interest
`
`
`
` MAINMENU
`
`
`
`
`
`
`
`
`
` GUIDANCEDISPLAY
`
`
`ROUTINGOPTIONS
`ADDRESS
`
`
`Map
`Country/State:____
`Shortest Route
`Turn—By— Turn
`Avoid Freeways
`City. ~
`
`
`
`Risk Index
`
`IPR2017-02022
`Unified EX1007 Page 2
`
`

`

`U.S. Patent
`
`Jan. 16, 2001
`
`Sheet 2 of 3
`
`US 6,175,803 B1
`
`
`
`Segment /D|Endpoints Attributes Weight
`
`
`
`
`
`
`
`
`
`
`YeS
`
`SF
`
`J2
`
`34
`
`35 36
`
`40
`
`4]
`
`
`
`Indentify Potential Route Segments And
`
`Their Attributes (e.g. Road Type, Length,
`
`
`
`Travel Time, Direction, Toll, Speed Limit)
`
`
` APPLY ROUTING OPTION
`
`
`
`— Remove failing Segments
`- Modify Segment Weights
`— Enable Attribute For Optimization
`
`
`
`Select Segments To Reach
`
`Destination While Optimizing
`42
`Route Criteria
`
`
`
`During Guidance, Display A
`
`_Fae.
`Map Showing Statistical Data
`For Routing Option Selected
`
`
`
`
`
`
`Potential Chain #7
`
`Potential Chain # 2
`
`-
`1
`Seg.
`Seg. 2 |
`
`OF
`Wy
`
`-
`|
`Seg.
`Seg. 2 |
`
`a,
`Wy
`
`Seg. x
`
`-—
`
`tu,
`
`Seg. y ~
`
`ty
`
`PD)
`yy
`SS
`_Pa. oe.
`
`IPR2017-02022
`Unified EX1007 Page 3
`
`IPR2017-02022
`Unified EX1007 Page 3
`
`

`

`U.S. Patent
`
`Jan. 16, 2001
`
`Sheet 3 of 3
`
`US 6,175,803 B1
`
`Statistical
`Data Current
`
`
` Get Risk
`55
`
`Threshold
`
`
` Get Potential
`
`Route Segment
`
`
`
`Segment
`
`Contain Destin-
`ation ?
`
`
`
`56
`
`
`
`Contain A
`
`
` Segment
`
`
`
`
`
`
`Segment
`
`Contain Destin-
`
`ation 7
`
`
`
`
`Segment
`
`Contain A
`
`Highway ?
`
`
`
`
`Convert Segment
`Weight According
`To Statistical
`Risk Index
`
`
`
`_Pans =.
`_ae.
`
`IPR2017-02022
`Unified EX1007 Page 4
`
`IPR2017-02022
`Unified EX1007 Page 4
`
`

`

`US 6,175,803 B1
`
`1
`VEHICLE NAVIGATION ROUTE
`GENERATION WITH USER SELECTABLE
`RISK AVOIDANCE
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates in general to route genera-
`tion in vehicle navigation systems, and, more specifically, to
`route selection criteria including user selectable routing
`options suchasa statistical risk index which allowsthe user
`to avoid or minimize the correspondingstatistical risk along
`the generated route.
`Vehicle navigation systems have become well known
`wherein a map database is used to provide navigational
`assistance to the driver of a vehicle. Based upon a current
`location and a desired destination, a navigation computer
`generates an optimum route between the two points. The
`route may then be displayed visually for the driver. Turn-
`by-turn instructions and/or a description of the route may be
`given visually and/or aurally.
`Various techniques have been developed for constructing
`a route which is the most desirable according to predeter-
`mined optimization criteria. Typically, the map database is
`comprised of route segments, each segment connecting two
`endpoints or intersections. One widely used method for
`determining an optimal route is the Dijkstra method wherein
`each route segment in the map database has an associated
`cost or weight. The total weight of various potential routes
`between the current location and the destination are calcu-
`lated and compared so that a route may be selected with the
`lowest overall weight.
`In prior art systems, the optimization criteria is typically
`comprised of either the shortest route or the fastest route. In
`addition, selections have been provided for avoiding
`freeways, maximizing use of freeways, or avoiding
`tollways, for example. Thus, a route segment may have a
`plurality of weights and/or other attributes associated withit.
`For example, there may be a distance weight and a travel-
`time weight associated with a particular route segment. The
`generated route may be optimized using the various avail-
`able weights according to the drivers preferred optimization.
`In addition, many prior art systems allow the driver to
`specify a specific route segment
`to be eliminated from
`consideration for use in a route, such as when a road is
`closed for construction or there is an error in the database.
`Nevertheless, drivers have had little control over route
`optimization criteria or how they are applied.
`Navigation systems may be used to help a driver navigate
`through areas with which they are not familiar. Other than
`knowing that a route is optimized for distance,
`time or
`avoiding freeways or tollways, etc., the user of a prior art
`navigation system has not knownthe prevailing risk char-
`acteristics of the areas through which the route passes.
`
`SUMMARYOF THE INVENTION
`
`navigation route includes a plurality of route segments
`selected from a database of route segments. The database
`includes respective attributes associated with respective
`
`FIG. 1 showsa navigation system for a vehicle including
`a navigation controller 10 having a navigation engine 11 and
`a navigation database 12. A man-machine interface (MMI)
`13 includes a visual display, such as an LCD matrix display,
`and manual inputs, such as push buttons or a keypad. The
`man-machine interface may also include a speech recogni-
`tion unit 14 connected to a microphone 15 and to navigation
`controller 10 for identifying spoken input from a user. A
`speech generator 16 may also be connected to navigation
`controller 10 in order to generate audible navigation instruc-
`tions to the user. A vehicle position locator 17 is coupled to
`navigation controller 10 for supplying the current vehicle
`position. Locator 17 may be comprised of a global position-
`ing system (GPS) receiver, vehicle movement sensors, and/
`or other known vehicle location means. The navigation
`system may also include a wireless communication link 18
`coupled to navigation controller 10 for receiving remotely
`supplied navigation or traffic data, for example.
`An overall method of operation of a navigation system is
`shownin FIG. 2. In step 20, the current vehicle location is
`determined and a user inputs their desired destination
`through manual or spoken inputs. A route is generated in
`The present invention has the advantage of providing
`step 31 for traveling from the current location to the desired
`advanced navigation route generation employing route opti-
`destination. In step 22, route guidance is provided to the
`mization usingastatistical risk index. The user may estab-
`driver so that turning instructions may be followed along the
`60
`lish a customized risk threshold for their individually opti-
`route. During route guidance, the position of the vehicle is
`mized navigation route.
`monitored to coordinate delivery of turning instructions and
`for detection of movement off the planned route. If an
`In one aspect, the present invention provides a method of
`off-route condition is detected, then an off-route routine is
`generating a navigation route for a motor vehicle wherein
`the route connects an initial location with a destination. The
`conducted in step 23 which may include recalculation of a
`new route in step 21.
`Aseries of display menus is shown in FIG. 3 for utilizing
`the risk index route generation method of the present inven-
`
`2
`route segments. Theattributes includea statistical risk index
`that has been measured and indexed to respective route
`segments. A route criteria is established which is to be
`optimized over the navigation route. The route criteria
`includes the statistical risk index. Total weights are com-
`pared according to the route criteria for various potential
`navigation routes. The navigation route is selected as one of
`the potential navigation routes for which the routing criteria
`is substantially optimized.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram showing elements of a navi-
`gation system employing the present invention.
`FIG. 2 is a flowchart showing the overall operation of a
`navigation system which may incorporate the present inven-
`tion.
`
`FIG. 3 shows successive display menus for controlling a
`navigation system according to the present invention.
`FIG. 4 is a diagram showing the structure of a route
`segment in a map database.
`FIG. 5 is a flowchart showing a method of operation of the
`present invention.
`FIG. 6 is a flowchart showing one embodiment for
`applyingthe statistical risk index to route generation accord-
`ing to the present invention.
`FIG. 7 shows the total weight comparison for different
`potential routes.
`FIG. 8 is a flowchart showing an embodiment for modi-
`fying route segment weights according to thestatistical risk
`index of the present invention.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`IPR2017-02022
`Unified EX1007 Page 5
`
`IPR2017-02022
`Unified EX1007 Page 5
`
`

`

`US 6,175,803 B1
`
`3
`tion. AMAIN MENU25includesselections for destination
`input, destination memory, and system settings. The plan-
`ning of a navigational route begins with selection of the
`“destination input” choice. Next, a DESTINATION INPUT
`menu 26 appears where the format of the destination input
`is chosen from choices of address, cross-street, or points of
`interest. Assuming that the “address” choice is selected, an
`ADDRESSmenu 27is presented for allowing textual input
`of a country/state, city, and/or address of the destination.
`Other appropriate menus would be used for inputting the
`destination in terms of cross-streets or points of interest.
`After the destination has been specified, a ROUTING
`OPTIONS menu 28is presented to allow user selection of
`various routing options to be considered during route gen-
`eration. For example, the user may select between a shortest
`route, a route avoiding freeways, or a risk index route
`calculation.
`
`4
`index within the route optimization itself, such as either
`including or excluding a risk index weight factor in the
`calculation of total weight for any potential route using the
`Dykstra method.
`In step 42, the route segments are selected which reach the
`destination while optimizing the route criteria or
`total
`weight. In order to maximize the amount of risk index
`information conveyed to a user, a map may optionally be
`displayed during the route guidance phase in step 43 show-
`ing the statistical data (i.e., numerical risk index) associated
`with each route segment whenthe risk index routing option
`has been selected.
`
`10
`
`15
`
`The first embodiment of step 41 (i.e., removing failing
`route segments according to the risk index) is shown in
`greater detail in FIG. 6. Since statistical risk data, such as
`crime assessment data, may change overtime,a test is made
`in step 50 to determine whetherthe statistical data is current.
`Preferably, the database (whether contained on a CD ROM
`The risk index preferably is comprised ofastatistical risk
`or downloaded over the wireless communication link)
`index such as a crime assessment indexed to the geographic
`area containing each respective route segment in the data-
`includes a date field showing when the data was compiled.
`base. For example, statistics compiled by law enforcement
`If a predetermined amount of time has passed since the
`compilation of the database (e.g., one year), then an “old
`agencies can be used to generate a numeral score as a
`measure of the rate of predetermined crimes in a geographic
`data” warning is displayed in step 51 to so notify the user.
`area. In the U'S., this type of data is compiled and marketed
`The user is given an option to continue using the available
`by CAP Index, Inc., based upon a weighted average of
`data in step 52. If the user chooses not to use the data then
`offenses listed in FBI uniform crime reports. When “risk
`the process is exited. Otherwise, the user may continue and
`index”is selected in ROUTING OPTIONS menu 28, the
`a risk threshold is identified in step 53.
`user may be prompted to input a risk threshold indicating
`A predetermined risk threshold may be employed in step
`what
`level of risk index is desired to be avoided. The
`53 which has been stored within the navigation controller.
`numerical scores may preferably be scaled relative to a
`Alternatively, the user may be prompted to input a custom-
`national average in order to make the meaning of a risk
`ized risk threshold. In step 54, a potential route segmentis
`threshold more understandable. For example, CAP Index,
`obtained. A check is made in step 55 to determine whether
`Inc., scales risk index scores so that the national average
`the segment contains the desired destination. If it does, then
`falls at a score of 100. A risk of half the national average
`a jump is made to step 59 where a check is made to
`would thus correspondto a risk threshold of 50, for example.
`determine if there are more potential route segments to be
`Other statistical risks which could be employed in the
`examined. If there are more segments, then a return is made
`present
`invention include other data such as emergency
`to step 54; otherwise the process is done and further con-
`(police or ambulance)
`response time,
`likelihood of
`ventional steps of route generation are employed.
`congestion, or accidentrates.
`If the segment did not contain the destination in step 55,
`Once a navigation route is determined in accordance with
`then a check is made in step 56 to determine whether the
`the routing options,
`the display presents a GUIDANCE
`segment contains a highwayor freewayattribute. Thus, even
`DISPLAY 29 which mayinclude a navigation map and/or
`though a highway segment may pass through an area with a
`turn-by-turn navigation instructions as the vehicle
`high value for its crime assessment risk index, highway
`progresses along the determined navigation route.
`segments are not affected by the high index. Since freeways
`are the fastest
`traveling roads with the least amount of
`One format for containing information of a route segment
`in a database is shown in FIG. 4. In addition, the database
`stopping, they might be considered potentially safer even
`though they pass through an area with a high risk index for
`may include graphical information or data point plots (not
`crimes. Thus, if the segment is a highway, a jump is made
`shown) for the map display. A route segment may include a
`to step 59 to check for more route segments.If the segment
`segment ID 30 and end points 31 and 32. The plurality of
`does not contain a highway, then a comparison is made in
`attributes 33-36 may also be employed, such as data flags
`step 57 betweenthe risk index of the route segment and the
`indicating whether the route segment is a highway,atoll
`risk threshold identified in step 53. If the risk index of the
`road, or a one-way street. One or more weights 37 are stored
`segmentis greater than the threshold, then the route segment
`in the database for identifying a time cost and a distance cost
`is eliminated from the potential navigational routes in step
`associated with the route segment, for example.
`58. Then a check is made in step 59 for further route
`An overall method of the present invention for including
`a risk index in the overall route selection criteria is shown in
`segments.
`FIG. 7 shows a typical example for comparing total
`performance weights for various potential navigation routes.
`Thus, a potential chain of navigation routes #1 includes a
`segment 1 with its corresponding weight w,, a segment 2
`with its weight w,, and up to a segmentx with its weight w,,.
`The total cost or weight of potential chain #1 is the sum of
`weights w, through w,, and equals a total cost T,. Likewise,
`a potential chain #2 contains a different set of route segments
`up to a segment y with its weightw,,. The total weight or cost
`of potential chain #2 is the sum of individual weights and
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`In step 40, potential route segments and their
`FIG. 5.
`attributes are identified which may possibly be included in
`the finally selected navigation route. In step 41,
`the risk
`index routing option selected by the user is applied to the
`database. Three alternative embodiments are shownin FIG.
`1,
`including 1) removal from consideration of segments
`failing the routing option, 1.e., those having a risk index
`higher than the risk threshold, 2) modifying the route
`segment weights by a factor determined in response to the
`risk index, or 3) enabling or disabling an attribute or risk
`
`60
`
`65
`
`IPR2017-02022
`Unified EX1007 Page 6
`
`IPR2017-02022
`Unified EX1007 Page 6
`
`

`

`US 6,175,803 B1
`
`5
`equals T,. The potential chain with the lower total weight T,
`or T, is the optimized route and would be selected as the
`final navigation route.
`According to the second embodimentof step 41 in FIG.
`5, the segment weights can be modified pursuant to the risk
`index prior to comparing the total performance weight of
`each potential chain. Such a method is shown in FIG. 8 in
`greater detail. This method is similar to the method shown
`in FIG. 6 and identical reference numbers are used for
`corresponding steps of the method. The method of FIG. 8
`differs in that a risk threshold is not used and route segments
`are nottotally eliminated from consideration. Thus,if a route
`segmentis found not to contain the destination in step 55 and
`not to be a highway in step 56,
`then the initial weight
`associated with the route segment is converted according to
`the statistical risk index. Preferably, the conversion is such
`that
`the weight associated with the route segment
`is
`increased relative to larger statistical risk indices. In this
`way, the cost of including a segment in a potential route is
`greater if the statistical risk index showsa relatively greater
`risk. A linear formula may be used which modifies each
`individual weight directly according to the corresponding
`risk index. Alternatively, the individual weights could be
`adjusted by predetermined amounts depending upon which
`of a plurality of predetermined rangesthe corresponding risk
`index falls into.
`
`Regarding the third embodiment of step 41 in FIG. 5, a
`separate, additional weight value correspondingto the sta-
`tistical risk index can be stored in the database correspond-
`ing to each route segment. The Dijkstra method or other
`optimization technique used is modified to either take into
`accountor not take into account the additional weight value
`in determining total weights.
`Whatis claimedis:
`
`5
`
`15
`
`20
`
`25
`
`30
`
`35
`
`6
`numerical weight for a respective route segment, said
`method comprising the steps of:
`
`specifying said destination;
`selecting routing options from a group of routing options,
`wherein said group includes a shortest distance option,
`a fastest route option, and a risk index option, wherein
`said selected routing options define a routing criteria to
`be optimized over said navigation route;
`modifying said respective weights in response to said
`statistical risk index for each respective route segment
`if said risk index option is selected;
`selecting a chain of said route segments as said navigation
`route, said chain substantially optimizing said routing
`criteria as compared to other potential chains of said
`routing segments betweensaid initial location and said
`destination, said optimizing of said routing criteria is
`determined by forming sumsof weights corresponding
`to each potential chain of route segments from said
`initial location to said destination and selecting a chain
`of route segments having a substantially lowest one of
`said sums; and
`guiding a driver of said motor vehicle along said naviga-
`tion route.
`
`2. The method of claim 1 further comprising the steps of:
`specifying a risk threshold; and
`eliminating route segments from inclusion in said chain of
`route segments wheneversaid statistical risk index is
`greater than said risk threshold, except if said route
`segment includes said destination.
`3. The method of claim 1 further comprising the steps of:
`specifying a risk threshold; and
`eliminating route segments from inclusion in said chain of
`route segments wheneversaid statistical risk index is
`greater than said risk threshold, except if said route
`segment includes said destination or has an attribute
`designating said route segment as a highway.
`4. The method of claim 1 wherein said statistical risk
`
`1. A method of navigating a motor vehicle along a
`navigation route connecting an initial
`location with a
`destination, said navigation route including a plurality of
`route segments selected from a database of route segments,
`said database including respective attributes associated with
`40
`respective route segments, said attributes includingastatis- index is comprised of crimestatistics.
`
`tical risk index that has been measured and indexed to
`*
`*
`*
`*
`*
`
`respective route segments, each said attribute determining a
`
`IPR2017-02022
`Unified EX1007 Page 7
`
`IPR2017-02022
`Unified EX1007 Page 7
`
`