# US 2012/0253669 A1 · Maritime Path Determination

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

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

## CPC

- G01C 21/203: {specially adapted for water-borne vessels}
- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- 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)

## Abstract

In certain embodiments, determining maritime paths includes accessing a feasibility matrix comprising feasibility values for locations of an area. A feasibility value indicates navigability at a location. One or more non-navigable locations represent one or more barriers. Waypoints around the barriers are determined. A cost matrix comprising cost values is calculated. A cost value indicates a distance between two points of a set of points, where the set of points comprises one or more start points, one or more end points, and the waypoints. Dijkstra's technique is applied to a selected start point and a selected end point to yield a shortest length path between the selected start point and the selected end point.

## Claims

### Claim 1

A method comprising:
accessing a feasibility matrix comprising a plurality of feasibility values for a plurality of locations of an area, each feasibility value indicating navigability at a location, one or more non-navigable locations representing one or more barriers;
determining a plurality of waypoints around the one or more barriers;
calculating a cost matrix comprising a plurality of cost values, each cost value indicating a distance between two points of a set of points, the set of points comprising one or more start points, one or more end points, and the plurality of waypoints; and
applying Dijkstra's technique to a selected start point and a selected end point to yield a shortest length path between the selected start point and the selected end point.

### Claim 2 (depends on 1)

The method of claim 1, further comprising calculating the feasibility matrix by:
accessing a water/land data comprising a plurality of water/land values for the plurality of locations, each water/land value indicating whether there is water or land at a location;
if a water/land value indicates there is water at a location, setting the feasibility value for the location as navigable; and
if a water/land value indicates there is land at a location, setting the feasibility value for the location as non-navigable.

### Claim 3 (depends on 1)

The method of claim 1, the determining the plurality of waypoints further comprising:
selecting one or more waypoints that are closer to the direction towards at least one end point.

### Claim 4 (depends on 1)

The method of claim 1, the determining the plurality of waypoints further comprising:
selecting one or more waypoints that are at least a minimum distance from the one or more barriers.

### Claim 5 (depends on 1)

The method of claim 1, the determining the plurality of waypoints further comprising:
selecting one or more waypoints that are in between two or more barriers.

### Claim 6 (depends on 1)

The method of claim 1, the determining the plurality of waypoints further comprising:
creating a plurality of candidate waypoints surrounding at least one barrier, the at least one barrier associated with one or more candidate start points;
applying Dijkstra's technique to the one or more candidate start points to yield one or more paths; and
discarding any candidate waypoints not used in any of the one or more paths.

### Claim 7 (depends on 6)

The method of claim 6, the creating the plurality of candidate waypoints further comprising:
creating an initial set of candidate waypoints at an initial distance from the at least one barrier; and
repeating the following for a predetermined number of iterations:
creating a current set of candidate waypoints at a current distance from the at least one barrier, the current distance greater than a previous distance from the at least one barrier.

### Claim 8

A system comprising:
one or more memories operable to store a feasibility matrix comprising a plurality of feasibility values for a plurality of locations of an area, each feasibility value indicating navigability at a location, one or more non-navigable locations representing one or more barriers; and
one or more processors operable to:
determine a plurality of waypoints around the one or more barriers;
calculate a cost matrix comprising a plurality of cost values, each cost value indicating a distance between two points of a set of points, the set of points comprising one or more start points, one or more end points, and the plurality of waypoints; and
apply Dijkstra's technique to a selected start point and a selected end point to yield a shortest length path between the selected start point and the selected end point.

### Claim 9 (depends on 8)

The system of claim 8, the one or more processors further operable to calculate the feasibility matrix by:
accessing a water/land data comprising a plurality of water/land values for the plurality of locations, each water/land value indicating whether there is water or land at a location;
if a water/land value indicates there is water at a location, setting the feasibility value for the location as navigable; and
if a water/land value indicates there is land at a location, setting the feasibility value for the location as non-navigable.

### Claim 10 (depends on 8)

The system of claim 8, the determining the plurality of waypoints further comprising:
selecting one or more waypoints that are closer to the direction towards at least one end point.

### Claim 11 (depends on 8)

The system of claim 8, the determining the plurality of waypoints further comprising:
selecting one or more waypoints that are at least a minimum distance from the one or more barriers.

### Claim 12 (depends on 8)

The system of claim 8, the determining the plurality of waypoints further comprising:
selecting one or more waypoints that are in between two or more barriers.

### Claim 13 (depends on 8)

The system of claim 8, the determining the plurality of waypoints further comprising:
creating a plurality of candidate waypoints surrounding at least one barrier, the at least one barrier associated with one or more candidate start points;
applying Dijkstra's technique to the one or more candidate start points to yield one or more paths; and
discarding any candidate waypoints not used in any of the one or more paths.

### Claim 14 (depends on 13)

The system of claim 13, the creating the plurality of candidate waypoints further comprising:
creating an initial set of candidate waypoints at an initial distance from the at least one barrier; and
repeating the following for a predetermined number of iterations:
creating a current set of candidate waypoints at a current distance from the at least one barrier, the current distance greater than a previous distance from the at least one barrier.

### Claim 15

One or more non-transitory computer readable media comprising logic when executed operable to:
access a feasibility matrix comprising a plurality of feasibility values for a plurality of locations of an area, each feasibility value indicating navigability at a location, one or more non-navigable locations representing one or more barriers;
determine a plurality of waypoints around the one or more barriers;
calculate a cost matrix comprising a plurality of cost values, each cost value indicating a distance between two points of a set of points, the set of points comprising one or more start points, one or more end points, and the plurality of waypoints; and
apply Dijkstra's technique to a selected start point and a selected end point to yield a shortest length path between the selected start point and the selected end point.

### Claim 16 (depends on 15)

The media of claim 15, the logic further operable to calculate the feasibility matrix by:
accessing a water/land data comprising a plurality of water/land values for the plurality of locations, each water/land value indicating whether there is water or land at a location;
if a water/land value indicates there is water at a location, setting the feasibility value for the location as navigable; and
if a water/land value indicates there is land at a location, setting the feasibility value for the location as non-navigable.

### Claim 17 (depends on 15)

The media of claim 15, the determining the plurality of waypoints further comprising:
selecting one or more waypoints that are closer to the direction towards at least one end point.

### Claim 18 (depends on 15)

The media of claim 15, the determining the plurality of waypoints further comprising:
selecting one or more waypoints that are at least a minimum distance from the one or more barriers.

### Claim 19 (depends on 15)

The media of claim 15, the determining the plurality of waypoints further comprising:
creating a plurality of candidate waypoints surrounding at least one barrier, the at least one barrier associated with one or more candidate start points;
applying Dijkstra's technique to the one or more candidate start points to yield one or more paths; and
discarding any candidate waypoints not used in any of the one or more paths.

### Claim 20 (depends on 19)

The media of claim 19, the creating the plurality of candidate waypoints further comprising:
creating an initial set of candidate waypoints at an initial distance from the at least one barrier; and
repeating the following for a predetermined number of iterations:
creating a current set of candidate waypoints at a current distance from the at least one barrier, the current distance greater than a previous distance from the at least one barrier.
