Maritime path determination

• US 8,818,712 B2
• Filed: 03/28/2011
• Issued: 08/26/2014
• Est. Priority Date: 03/28/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.
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Nguyen, Bao Long T
• Application Number:
  US13/073,097
• Publication Number:
  US 20120253669A1
• Time in Patent Office: 1,247 Days
• US Class Current: 701/411
• CPC Class Codes: G01C 21/203 Specially adapted for sailing ships
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

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

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;

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;

wherein the determining the plurality of waypoints includes;

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; and

wherein the creating the plurality of candidate waypoints includes;

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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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;

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;

wherein the determining the plurality of waypoints includes;

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; and

wherein the creating the plurality of candidate waypoints includes;

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.

7. The system of claim 6, 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.

8. The system of claim 6, 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.

9. The system of claim 6, 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.

10. The system of claim 6, the determining the plurality of waypoints further comprising:

selecting one or more waypoints that are in between two or more barriers.

11. 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;

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;

wherein the determine the plurality of waypoints includes;

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; and

wherein the create the plurality of candidate waypoints includes;

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.

12. The media of claim 11, 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.

13. The media of claim 11, 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.

14. The media of claim 11, 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.