Maritime Path Determination

• US 20120253669A1
• Filed: 03/28/2011
• Published: 10/04/2012
• 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.
• Granted Patent: US 8,818,712 B2
• Time in Patent Office: Days
• US Class Current: 701/467
• 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; 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.

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

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

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.

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

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

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

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

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

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

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.

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

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

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

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

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