Travelling course searching apparatus for vehicle

• US 5,475,387 A
• Filed: 01/06/1995
• Issued: 12/12/1995
• Est. Priority Date: 06/23/1992
• Status: Expired due to Term

• Current Assignee: Honda Giken Kogyo Kabushiki Kaisha (Honda Motor Company)
• Original Assignee: Honda Giken Kogyo Kabushiki Kaisha (Honda Motor Company)
• Inventors: Matsumoto, Yoshiyuki
• Primary Examiner(s): Swarthout, Brent
• Assistant Examiner(s): TONG, NINA C
• Application Number:
  US08/369,876
• Time in Patent Office: 340 Days
• Field of Search: 340/990, 340/995, 364/424.01, 364/436, 364/437, 364/438, 364/449
• US Class Current: 340/990
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments

Abstract

Disclosed is a vehicle travelling searching apparatus for finding an optimal course between two points preset on a road map by searching optimal partial course components on the basis of digitized road map data by use of a synthetically evaluating function including a plurality of travelling-cost-related variable parameters, changing over weight coefficients of the parameters or the function itself to adequate coefficients or function for each partial searching condition.

Claims

1. A vehicular travel course searching apparatus for identifying a course connecting two selected points on a road map depicted on a display screen by using selected functions for evaluating a course of travel, said functions including parameters representing a plurality of travelling costs including at least a travelling distance cost and a road width cost, each parameter having a variable weight coefficient, said course searching apparatus comprising:

a signal processing unit electronically coupled to a display, a data entry device, a travel path memory, and a memory read-out device, said memory read-out device being electronically coupled to a road map data memory; and

said signal processing unit including

first processing means for identifying a main course formed by a main road between two points adjacent to said selected points, said first processing means processing data of a main road map using a first selected function for evaluating a travelling course and being initialized such that increased weight is assigned to a road width cost parameter; and

second processing means for identifying course components connecting, respectively, said selected points with said identified main course, said second processing means processing data representing a detailed local road map using a second selected function for evaluating a travelling course, and being initialized such that increased weight is assigned to a distance cost parameter.

2. A machine implemented process for identifying an optimal path of travel between two locations represented by first and second points on a road map, said process comprising the steps of:

retrieving a first digital representation of said road map from a memory, said first digital representation of said road map having a first degree of detail;

identifying a first hierarchical path between said first and second points using a first path evaluation algorithm, said first path evaluation algorithm comprising a first multiple variable travel evaluation function including a plurality of variables of a first weighting;

storing data representative of a plurality of nodes of said first hierarchical path within said memory;

retrieving a second digital representation of said road map and said data representative of said first hierarchical path from said memory, said second digital representation of said road map having a second degree of detail exceeding said first degree of detail; and

identifying a second hierarchical path between said first and second points using a second path evaluation algorithm, said second hierarchical path including at least said nodes of said first hierarchical path, and said second path evaluation algorithm comprising a second multiple variable travel evaluation function including a plurality of variables of a second weighting.

3. The machine implemented process of claim 2, wherein said first and second multiple variable travel evaluation functions include the same variables, but wherein said variables of said respective functions have different weightings.

4. A machine implemented process for identifying a path of travel between two locations represented by first and second points on a road map, said process comprising the steps of:

retrieving a first representation of said road map from a memory, said first representation of said road map having a first degree of detail;

identifying a first path between said first and second points using a first path evaluation algorithm, said first path evaluation algorithm comprising a first multivariable travel evaluation function including a plurality of variables of a first weighting;

dividing said first path into a plurality of contiguous path segments;

retrieving local representations of said road map corresponding to each of said contiguous path segments from said memory; and

identifying local paths based upon said contiguous path segments using one or more local path evaluation algorithms, each said local path evaluation algorithm including a plurality of variables of selected local weightings.

5. A travel path identification system comprising:

a memory means for storing data representative of a road map; and

a microcomputer aided signal processing unit;

said microcomputer aided signal processing unit being programmed

to retrieve from said memory means data of a first hierarchy representing a first node set comprising said road map;

to identify first and second nodes of said first node set, said first and second nodes being the nodes of said first node set nearest to a start point and a target point, respectively, of indicated travel;

to identify a first order path between said first and second nodes using a first path evaluation function;

to retrieve from said memory means data of a second hierarchy representing a second node set comprising said road map;

to identify first and second nodes of a second node set which are nearest to said start point and said target point respectively; and

to identify second order paths between said first nodes of said first and second node sets and between said second nodes of said first and second node sets using a second path evaluation function having a weighting of variables different from said first path evaluation function.

6. A course searching apparatus for identifying an optimal course connecting two selected points on a road map depicted on a display screen, said course searching apparatus processing a path evaluation function which includes at least two parameters, each parameter having a variable weighting coefficient, and said apparatus comprising:

means for processing data representing said road map in a first routine, using said path evaluation function, to identify an optimal main course comprised of one or more main roads between said selected points, and for processing said data representing said road map in a second routine, using said path evaluation function, to identify an optimal local course between each of said selected points and respective end points of said main course; and

means for selectively and independently adjusting said weighting coefficients of said parameters of said path evaluation function such that said weighting coefficients may differ when said optimal main course and said optimal local course are identified.

7. The course searching apparatus of claim 6 wherein said at least two parameters comprise at least a road width cost parameter and a distance cost parameter.

8. A navigational system for a vehicle comprising:

a road map data memory for storing for storing digitized road map data;

a memory read-out device electronically coupled to said road map data memory for selectively retrieving road map data corresponding to a selected area of travel from said road map data memory;

a microcomputer-aided signal processing unit electronically coupled to said memory read-out device and being programmed

to retrieve from said memory read-out device a first digital representation of said selected area of travel, said first digital representation comprising a representation of said selected area of travel having a first degree of detail;

to identify a first hierarchical path between a first and second point within said selected area of travel using a first path evaluation algorithm, said first path evaluation algorithm comprising a first multiple variable travel evaluation function including a plurality of variables of a first weighting;

to store data representative of said first hierarchical path within a travel path memory;

to retrieve from said memory read-out device a second digital representation of said selected area of travel, said second digital representation comprising a representation of said selected area of travel having a second degree of detail exceeding said first degree of detail;

to identify a second hierarchical path between said first and second points using a second path evaluation algorithm, said second hierarchical path including at least the nodes of said first hierarchical path, and said second path evaluation algorithm comprising a second multiple variable travel evaluation function including a plurality of variables of a second weighting;

a display electronically coupled to said microcomputer-aided signal processing unit for displaying a graphic representation of said selected area of travel; and

a data entry device electronically coupled to said microcomputer-aided signal processing unit for providing data defining said first and second points to said microcomputer-aided signal processing unit.

9. The navigational system of claim 8 wherein said first digital representation of said selected area of travel comprises a representation of highways within said selected area of travel, and wherein said second digital representation of said selected area of travel comprises a representation of local roads within said selected area of travel.