# US 2012/0253664 A1 · Path Determination Using Elevation Data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0253664 A1
- Document ID: US20120253664A1
- Status: Published application
- Kind: A1
- Application number: 13/074,366
- Filed: 2011-03-29
- Published: 2012-10-04
- Earliest claimed: 2011-03-29
- Assignees: Raytheon Company
- Inventors: Juan E. Sandoval; Nicholas I. Sapankevych; Sara R. Lemley
- Web page: https://patentgrep.com/patent/US20120253664A1

## CPC

- G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence)
- H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00)
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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.

### Claim 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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 9)

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.

### Claim 12 (depends on 9)

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.

### Claim 13 (depends on 9)

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.

### Claim 14 (depends on 9)

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.

### Claim 15 (depends on 9)

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.

### Claim 16 (depends on 9)

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.

### Claim 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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 17)

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.

### Claim 20 (depends on 17)

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.
