Route generating device

• US 5,787,233 A
• Filed: 03/26/1996
• Issued: 07/28/1998
• Est. Priority Date: 03/28/1995
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Akimoto, Shinji
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US08/624,740
• Time in Patent Office: 854 Days
• Field of Search: 364/449.3, 395/10, 395/81
• US Class Current: 706/45
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A route generating device has an elevation map memory storing elevation data for subareas defined by division of an operations zone. A gradient map creating section calculates gradient data based on the elevation data and creates a gradient map from the gradient data. An obstruction region extracting section extracts an inclination obstruction region based on the gradient map. A traveling route generating section obtains a travelable region based on the inclination obstruction region. All possible traveling routes is calculated based on the travelable region. A route evaluating section evaluates the traveling routes and selects an optimum route from the current position to the destination. The gradient map is created based on the elevation data, it is possible to generate an optimum route without three dimensional obstruct such as a fall, a tumble and any other inability in movement of the movable object.

Claims

1. A route generating device comprising:

an elevation map memory storing elevation data of subareas which are defined by division of an operations zone of a movable object;

an input unit reading the elevation data from the elevation map memory;

a gradient map creating section calculating gradient data based on the elevation data read from the map memory so as to create a gradient map;

an obstruction region extracting section extracting an inclinational obstruction region on the basis of the gradient map, said inclinational obstruction region having a gradient enough to hinder a movement of the movable object;

a route generating section determining a travelable region on the basis of the inclinational obstruction region for going around obstructions so as to calculate possible traveling routes on the basis of the travelable region for avoiding the obstructions;

a route evaluating section evaluating the traveling routes calculated in the route generating section so as to select an optimum route from a current location of the movable object to a destination; and

an output unit outputting the optimum route selected in the route evaluating section.

2. A route generating device according to claim 1, further comprising a natural obstructions map memory storing position data of a natural obstruction region occupied by a natural obstruction to the movable object, and a region composite section superposing the inclinational obstruction region and the natural obstruction region so as to create a composite obstruction region, said route generating section determining said travelable region on the basis of the composite obstruction region.

3. A route generating device according to claim 2, further comprising an artificial structures map memory storing position d ata of an artificial structure which the movable object can use, wherein said route generating section is capable of superposing said travelable region and said artificial structure so as to calculate the possible traveling route through the artificial structure.

4. A route generating device according to claim 1, wherein said elevation map memory stores a n elevation of a southwestern end of said subarea as said elevation data, said gradient map creating section being capable of calculating a gradient of said subarea to an eastern, a northern and a northeastern subareas.

5. A route generating device according to claim 1, wherein said obstruction region extracting section is capable of interpolating the gradients of adjacent ones of said subareas in terms of a straight line and of extracting as said inclinational obstruction region a subarea which is related to the gradient over a maximum movable gradient.

6. A route generating device according to claim 1, wherein said route evaluating section is capable of calculating an arc length as an index of a shortest traveling route and an arc gradient as an index of a degree of difficulty in a movement, and weighting said arc length and said arc gradient so as to select the optimum route.

7. A route generating device according to claim 1, wherein said route evaluating section is capable of calculating an arc length as an index of a shortest traveling route and a vertical variation between opposite arc ends as an index of ups and downs of the traveling route, and weighting said arc length and said vertical variation so as to select the optimum route.

8. A route generating device according to claim 1, wherein said route evaluating section is capable of calculating an arc length as an index of a shortest traveling route, an arc gradient as an index of a degree of difficulty in a movement and a vertical variation between opposite arc ends as an index of ups and downs of the traveling route, and weighting said arc length, said arc gradient and said vertical variation so as to select the optimum route.