Multiple layer road memory storage device and route planning system

• US 5,285,391 A
• Filed: 08/05/1991
• Issued: 02/08/1994
• Est. Priority Date: 08/05/1991
• Status: Expired due to Term

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Smith, Bernard C. Jr., Link, Laura J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Park, Collin W.
• Application Number:
  US07/740,347
• Time in Patent Office: 918 Days
• Field of Search: 364/443, 364/444, 364/449, 340/990, 340/995
• US Class Current: 701/200
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering

Abstract

A route planning system (10) uses a computer (11) and stored road data to calculate a desired route to a destination. Road data is stored in a multiple layer road map data memory (13) in hierarchical multiple layers (17, 18, 19), each layer defining roadways by stored road segments (1S1-3S7) which extend between nodes (135-365)that correspond to roadway intersections. A first or lower layer (17) of road data designates a large number of first layer vehicle roadways while a second or higher level layer (18 or 19) of road data designates only some of the large number of first layer roadways as second layer roadways. Preferably, stored second layer road segments (2S1-2S17 or 3S1-3S7) extend between intersections of the roadways designated in the second layer rather than between intersections of roadways in the second layer with roadways or road segments not designated in the second layer but designated in the first layer. Preferably, at least some of the second layer road segments (2S1-2S17 or 3S1-3S7) are equivalent to the combination of several road segments (1S1-1S52)stored in the first layer. The road map data memory (13) and route planning system (10) minimize storage requirements for road data while speeding up the route planning process.

Claims

1. A multiple layer road memory storage device comprising:

a road memory means for storing therein road data defining fixed roadways located in a predetermined geographical area, wherein said road data is hierarchically stored in multiple layers in said memory means,

said memory means including a first portion for storing a first detailed layer of road data designating a large number of first layer roadways of various categories and their intersections with each other, each stored first layer roadway is defined at least by individual stored first layer road segments which extend between stored first layer nodes that correspond to each of said first layer roadway intersections,

said memory means also including a second portion for storing a second higher level layer of road data designating only some of said large number of first layer roadways as second layer roadways and designating second layer roadway intersections between each of said second layer roadways,

wherein each of said stored second layer roadways is defined at least by individual stored second layer road segments each of which represents a portion of one of said second layer roadways and each of which extends between stored second layer nodes which correspond to intersections of roadways designated in said second layer with other roadways designated in said second layer regardless of intersections of first layer road segments corresponding to said portions of said roadways represented by said stored second layer road segments with roadways/road segments designated in said first layer but not in said second layer, and wherein each of said stored second layer nodes, corresponding to an intersection of said stored second layer roadways, directly corresponds to one of said stored first layer nodes corresponding to an intersection of said stored first layer roadways;

wherein at least some of said stored second layer road segments are equivalent to a combination of several of said road segments stored in said first layer, and wherein said some of said stored second layer road segments have a road segment length equivalent to a road segment length of said combination of said segments in said first layer.

2. A multiple layer road memory storage device according to claim 1 wherein each of said road segments stored in said first and second layers has two end points between which the road segment extends, and each stored road segment includes stored end node data defining the location of two node points corresponding to said two end points of each of said road segments.

3. A multiple layer road memory storage device according to claim 2 wherein some of said node points in said first layer correspond to node points in said second layer.

4. A multiple layer road memory storage device according to claim 3 wherein some of said node points in said first layer correspond to shape points in said second layer, wherein said second layer shape points are located within a road segment in said second layer but do not correspond to any end point of a road segment in said second layer.

5. A multiple layer road memory storage device according to claim 3 wherein some of said node points in said first layer have no corresponding road segment node points in said second layer.

6. A multiple layer road memory storage device according to claim 3 wherein all of said node points in said second layer correspond to node points in said first layer.

7. A multiple layer road memory storage device according to claim 1 wherein said stored road data for each of said stored road segments in said first and second layers includes a segment ID for each stored road segment and the length of said stored road segment.

8. A multiple layer road memory storage device according to claim 7 wherein said stored road data includes, for each of said road segments in any of said first and second layers, node data defining the location of node points at each end of said road segment.

9. A route planning system comprising:

a road memory means for storing therein road data defining fixed roadways in a predetermined geographical area, and

a route planning computer means coupled to said road memory means for receiving said road data and using it to determine a desired route to a destination via said fixed roadways,

wherein said road data is hierarchically stored in said memory means and is stored as a first detailed layer designating a large number of first layer roadways of various categories and their intersections with each other, each stored first layer roadway is defined at least by individual stored first layer road segments which extend between stored first layer nodes that correspond to each of said first layer roadway intersections, and said road data is also stored in said memory means as a second higher level layer having data designating only some of said large number of first layer roadways as second layer roadways and data designating second layer roadway intersections between each of said second layer roadways, wherein said second layer of road data defines said second layer roadways by individual second layer road segments each of which represents a portion of one of said second layer roadways and each of which extends between intersections of roadways in said second layer with other roadways in said second layer regardless of intersections of first layer road segments corresponding to said portions of said roadways represented by said stored second layer road segments with roadways/road segments designated in said first layer but not in said second layer, and wherein said route planning computer uses at least said second layer road segments, as stored in said second layer, in determining said desired route, and wherein each of said stored second layer nodes, corresponding to an intersection of said stored second layer roadways, directly corresponds to one of said stored first layer nodes corresponding to an intersection of said stored first layer roadways;

wherein at least some of said road segments stored in said second layer and used by said route planning computer are equivalent to a combination of several of said road segments stored in said first layer, and wherein said some of said stored second layer road segments have a road segment length equivalent to a road segment length of said combination of said road segments in said first layer.

10. A route planning system according to claim 9 wherein each of said road segments stored in each of said first and second layers has two end points between which the road segment extends and each stored road segment includes end node data defining the location of two node points corresponding to said two end points of each of said road segments.

11. A route planning system according to claim 10 wherein said route planning computer means includes means for searching for all road segments in said second layer which include a predetermined node point in said second layer.

12. A route planning system according to claim 11 wherein some of said node points in said first layer correspond to node points in said second layer.

13. A route planning system according to claim 12 wherein some of said node points in said first layer correspond to shape points in said second layer, wherein said second layer shape points are located within a road segment in said second layer but do not correspond to any end point of a road segment in said second layer.

14. A route planning system according to claim 12 wherein some of said node points in said first layer have no corresponding road segment node points in said second layer.

15. A route planning system according to claim 12 wherein all of said node points in said second layer correspond to node points in said first layer.

16. A route planning system according to claim 12 wherein said route planning computer means also includes means for searching for all road segments in said first layer which include a predetermined node point in said first layer.