Path Determination Using Elevation Data

• US 20120253664A1
• Filed: 03/29/2011
• Published: 10/04/2012
• Est. Priority Date: 03/29/2011
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Sandoval, Juan E., Sapankevych, Nicholas I., Lemley, Sara R.
• Granted Patent: US 9,127,948 B2
• Time in Patent Office: Days
• US Class Current: 701/438
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00

Abstract

In certain embodiments, path determination includes receiving terrain elevation data comprising elevation values for locations of an area, where each elevation value indicates an elevation at a location. One or more gradient matrices are calculated from the elevation values. Each gradient matrix comprises gradient values corresponding to the locations. Traversable segments are determined from the gradient matrices, and a path is determined from the traversable segments.

Claims

1. A method comprising:

receiving terrain elevation data comprising a plurality of elevation values for a plurality of locations of an area, each elevation value indicating an elevation at a location;

calculating one or more gradient matrices from the plurality of elevation values, each gradient matrix comprising a plurality of gradient values corresponding to the plurality of locations;

determining a plurality of traversable segments from the one or more gradient matrices; and

determining a path from the plurality of traversable segments.

2. The method of claim 1, the calculating one or more gradient matrices further comprising calculating a gradient matrix in a direction by repeating the following for each value of at least a subset of the elevation values:

calculating a gradient for the each value in the direction.

3. The method of claim 1, the calculating one or more gradient matrices further comprising:

calculating a first gradient matrix in a first direction; and

calculating a second gradient matrix in a second direction.

4. The method of claim 1, the calculating one or more gradient matrices further comprising:

calculating a first gradient matrix in a first direction and a second gradient matrix in a second direction; and

combining the first gradient matrix and the second gradient matrix to yield a combined gradient matrix.

5. The method of claim 1, the determining the plurality of traversable segments further comprising:

identifying one or more gradient values that are less than a maximum gradient value, the one or more gradient values corresponding to one or more locations; and

designating one or more segments at the one or more locations as traversable segments.

6. The method of claim 1, the determining the path further comprising performing the following until an ending location has been reached:

identifying one or more reachable locations for a current location according to the traversable segments;

selecting a most preferable reachable location; and

setting the selected location as the next current location.

7. The method of claim 1, the determining the path further comprising performing the following until an ending location has been reached:

placing one or more reachable locations for a current location according to the traversable segments in a list in an order of preference;

selecting a most preferable reachable location according to the order; and

setting the selected location as the next current location.

8. The method of claim 1, the determining the path further comprising selecting a most preferable reachable location according to the order:

selecting a location in a preferred direction;

selecting a location adjacent to the preferred direction; and

selecting a location perpendicular to the preferred direction.

9. A system comprising:

one or more interfaces operable to receive terrain elevation data comprising a plurality of elevation values for a plurality of locations of an area, each elevation value indicating an elevation at a location; and

one or more processors operable to;

calculate one or more gradient matrices from the plurality of elevation values, each gradient matrix comprising a plurality of gradient values corresponding to the plurality of locations;

determine a plurality of traversable segments from the one or more gradient matrices; and

determine a path from the plurality of traversable segments.

10. The system of claim 9, the calculating one or more gradient matrices further comprising calculating a gradient matrix in a direction by repeating the following for each value of at least a subset of the elevation values:

calculating a gradient for the each value in the direction.

11. The system of claim 9, the calculating one or more gradient matrices further comprising:

calculating a first gradient matrix in a first direction; and

calculating a second gradient matrix in a second direction.

12. The system of claim 9, the calculating one or more gradient matrices further comprising:

calculating a first gradient matrix in a first direction and a second gradient matrix in a second direction; and

combining the first gradient matrix and the second gradient matrix to yield a combined gradient matrix.

13. The system of claim 9, the determining the plurality of traversable segments further comprising:

identifying one or more gradient values that are less than a maximum gradient value, the one or more gradient values corresponding to one or more locations; and

designating one or more segments at the one or more locations as traversable segments.

14. The system of claim 9, the determining the path further comprising performing the following until an ending location has been reached:

identifying one or more reachable locations for a current location according to the traversable segments;

selecting a most preferable reachable location; and

setting the selected location as the next current location.

15. The system of claim 9, the determining the path further comprising performing the following until an ending location has been reached:

placing one or more reachable locations for a current location according to the traversable segments in a list in an order of preference;

selecting a most preferable reachable location according to the order; and

setting the selected location as the next current location.

16. The system of claim 9, the determining the path further comprising selecting a most preferable reachable location according to the order:

selecting a location in a preferred direction;

selecting a location adjacent to the preferred direction; and

selecting a location perpendicular to the preferred direction.

17. One or more computer readable media comprising logic when executed operable to:

receive terrain elevation data comprising a plurality of elevation values for a plurality of locations of an area, each elevation value indicating an elevation at a location;

calculate one or more gradient matrices from the plurality of elevation values, each gradient matrix comprising a plurality of gradient values corresponding to the plurality of locations;

determine a plurality of traversable segments from the one or more gradient matrices; and

determine a path from the plurality of traversable segments.

18. The media of claim 17, the calculating one or more gradient matrices further comprising calculating a gradient matrix in a direction by repeating the following for each value of at least a subset of the elevation values:

calculating a gradient for the each value in the direction.

19. The media of claim 17, the determining the plurality of traversable segments further comprising:

identifying one or more gradient values that are less than a maximum gradient value, the one or more gradient values corresponding to one or more locations; and

designating one or more segments at the one or more locations as traversable segments.

20. The media of claim 17, the determining the path further comprising performing the following until an ending location has been reached:

placing one or more reachable locations for a current location according to the traversable segments in a list in an order of preference;

selecting a most preferable reachable location according to the order; and

setting the selected location as the next current location.