System and method for generating tactical routes

• US 10,520,327 B2
• Filed: 02/19/2015
• Issued: 12/31/2019
• Est. Priority Date: 07/07/2008
• Status: Active Grant

• Current Assignee: Polaris Industries Incorporated (Polaris Inc.)
• Original Assignee: Polaris Industries Incorporated (Polaris Inc.)
• Inventors: Milbert, Randy L., Freed, Erik S., Estes, Kyle K.
• Primary Examiner(s): Tissot, Adam D
• Application Number:
  US14/626,617
• Publication Number:
  US 20150253145A1
• Time in Patent Office: 1,776 Days
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries

Abstract

A method and system for generating tactical routes includes an intervisibility database pre-populated with pre-computed optical lines of sight between locations or nodes in geographic terrain, an intervisibility analyzer for analyzing propagation of the pre-computed optical lines of sight between the locations or nodes in the geographic terrain, a speed analyzer for analyzing speeds of travelers across the locations or nodes in the geographic terrain, a cost generator for generating a blended cost grid using said intervisibility and speed analyses, and a route generator for generating routes that facilitate tactical movement based on said blended cost grid. The route generator computes intervisibility unions at the locations or nodes in the geographic terrain and minimizing intervisibility unions along the generated route.

Claims

1. A system for generating tactical routes, the system comprising:

a global positioning system having an input operable to receive user input to place one or more waypoints;

the global positioning system further including a system for generating at least one additional waypoint at least partially responsive to the waypoint placed based on the received user input, the system for generating at least one additional waypoint including;

an intervisibility database pre-populated with pre-computed optical lines of sight between locations or nodes in geographic terrain;

an intervisibility analyzer for analyzing propagation of optical lines of sight between locations or nodes in geographic terrain, including generating a viewshed for each node using a position of each node, the viewshed including a set whose elements comprise other nodes having an optical line of sight to each node, and counting the number of the elements in the viewshed to determine a cardinality size of the viewshed as the visibility of each node for quantifying an extent to which a traveler is exposed when traveling across terrain represented by each node;

a speed analyzer for analyzing speeds of travelers across the locations or nodes in the geographic terrain, including retrieving a land cover map and traversal matrix, querying the land cover map for a terrain type for each node using a position of each node, returning a speed of the terrain type found in the traversal matrix representing how fast the traveler can travel across terrain represented by each of the nodes;

a cost generator for generating a blended cost grid using said intervisibility and speed analyses;

a minimum edge cost finder for generating a minimum cost edge using said blended cost grid and configured for searching edges of a graph to find the minimum cost edge used for computing heuristics, the minimum cost edge being the edge with a minimum blended cost between any two adjacent nodes in the graph; and

a route generator for generating routes that facilitate tactical movement based on said blended cost grid and computed heuristics.

2. The system of claim 1, wherein said route generator is further configured for meeting a speed constraint, and further configured for at least one of:

computing intervisibility sums;

computing intervisibility unions;

minimizing intervisibility sums;

minimizing intervisibility unions;

maximizing intervisibility sums per distance traveled; and

maximizing intervisibility unions per distance traveled.

3. The system of claim 1, wherein said route generator is further configured for avoiding slow areas, and further configured for at least one of:

computing intervisibility sums;

computing intervisibility unions;

minimizing intervisibility sums;

minimizing intervisibility unions;

maximizing intervisibility sums per distance traveled; and

maximizing intervisibility unions per distance traveled.

4. A system for generating tactical routes, the system comprising:

a global positioning system having an input operable to receive user input to place one or more waypoints;

the global positioning system further including a system for generating at least one additional waypoint at least partially responsive to the waypoint placed based on the received user input, the system for generating at least one additional waypoint including;

an intervisibility database pre-populated with pre-computed optical lines of sight between locations or nodes in geographic terrain;

an intervisibility analyzer for analyzing propagation of the pre-computed optical lines of sight between the locations or nodes in the geographic terrain;

a speed analyzer for analyzing speeds of travelers across the locations or nodes in the geographic terrain;

a cost generator for generating a blended cost grid using said intervisibility and speed analyses; and

a route generator for generating routes that facilitate tactical movement based on said blended cost grid, the route generator computing intervisibility unions at the locations or nodes in the geographic terrain and minimizing intervisibility unions along the generated route.

5. The system of claim 4, wherein said route generator is further configured for meeting a speed constraint, and further configured for at least one of:

computing intervisibility sums;

minimizing intervisibility sums;

maximizing intervisibility sums per distance traveled; and

maximizing intervisibility unions per distance traveled.

6. The system of claim 4, wherein said route generator is further configured for avoiding slow areas, and further configured for at least one of:

computing intervisibility sums;

minimizing intervisibility sums;

maximizing intervisibility sums per distance traveled; and

maximizing intervisibility unions per distance traveled.

7. The system of claim 4, further comprising:

the intervisibility analyzer configured for generating a viewshed for each node using a position of each node, the viewshed including a set whose elements comprise other nodes having an optical line of sight to each node, and counting the number of the elements in the viewshed to determine a cardinality size of the viewshed as the visibility of each node for quantifying an extent to which a traveler is exposed when traveling across terrain represented by each node, the speed analyzer configured for retrieving a land cover map and traversal matrix, querying the land cover map for a terrain type for each node using a position of each node, returning a speed of the terrain type found in the traversal matrix representing how fast the traveler can travel across terrain represented by each of the nodes;

a minimum edge cost finder for generating a minimum cost edge using said blended cost grid and configured for searching edges of a graph to find the minimum cost edge used for computing heuristics, the minimum cost edge being the edge with a minimum blended cost between any two adjacent nodes in the graph; and

the route generator configured for generating routes that facilitate tactical movement based on said blended cost grid and computed heuristics.

8. A method for generating tactical routes, the method comprising:

providing a global positioning system having an input operable to receive user input to place one or more waypoints;

the global positioning system further including a system for generating at least one additional waypoint at least partially responsive to the waypoint placed based on the received user input, the system for generating at least one additional waypoint performing;

pre-populating an intervisibility database with pre-computed optical lines of sight between locations or nodes in geographic terrain;

analyzing with an intervisibility analyzer propagation of the pre-computed optical lines of sight between the locations or nodes in the geographic terrain;

analyzing with a speed analyzer speeds of travelers across the locations or nodes in the geographic terrain;

generating with a cost generator a blended cost grid using said intervisibility and speed analyses; and

generating with a route generator routes that facilitate tactical movement based on said blended cost grid, the route generator computing intervisibility unions at the locations or nodes in the geographic terrain and minimizing intervisibility unions along the generated route.

9. The method of claim 8, further comprising meeting a speed constraint with said route generator, and at least one of:

computing intervisibility sums with said route generator;

minimizing intervisibility sums with said route generator;

maximizing intervisibility sums per distance traveled with said route generator; and

maximizing intervisibility unions per distance traveled with said route generator.

10. The method of claim 8, further comprising avoiding slow areas with said route generator, and at least one of:

computing intervisibility sums with said route generator;

minimizing intervisibility sums with said route generator;

maximizing intervisibility sums per distance traveled with said route generator; and

maximizing intervisibility unions per distance traveled with said route generator.

11. The method of claim 8, further comprising:

generating with the intervisibility analyzer a viewshed for each node using a position of each node, the viewshed including a set whose elements comprise other nodes having an optical line of sight to each node, and counting the number of the elements in the viewshed to determine a cardinality size of the viewshed as the visibility of each node for quantifying an extent to which a traveler is exposed when traveling across terrain represented by each node;

retrieving with the speed analyzer a land cover map and traversal matrix, querying the land cover map for a terrain type for each node using a position of each node, returning a speed of the terrain type found in the traversal matrix representing how fast the traveler can travel across terrain represented by each of the nodes;

generating with a minimum edge cost finder a minimum cost edge using said blended cost grid and configured for searching edges of a graph to find the minimum cost edge used for computing heuristics, the minimum cost edge being the edge with a minimum blended cost between any two adjacent nodes in the graph; and

generating with the route generator routes that facilitate tactical movement based on said blended cost grid and computed heuristics.

12. A computer program product for generating tactical routes, and including one or more computer readable instructions embedded on a tangible, non-transitory computer readable medium, and configured to cause one or more computer processors to perform the steps of:

pre-populating an intervisibility database with pre-computed optical lines of sight between locations or nodes in geographic terrain;

analyzing with an intervisibility analyzer propagation of the pre-computed optical lines of sight between the locations or nodes in the geographic terrain;

analyzing with a speed analyzer speeds of travelers across the locations or nodes in the geographic terrain;

generating with a cost generator a blended cost grid using said intervisibility and speed analyses; and

generating with a route generator routes that facilitate tactical movement based on said blended cost grid, the route generator computing intervisibility unions at the locations or nodes in the geographic terrain and minimizing intervisibility unions along the generated route.

13. The computer program product of claim 12, further comprising meeting a speed constraint with said route generator, and at least one of:

computing intervisibility sums with said route generator;

minimizing intervisibility sums with said route generator;

maximizing intervisibility sums per distance traveled with said route generator; and

maximizing intervisibility unions per distance traveled with said route generator.

14. The computer program product of claim 12, further comprising avoiding slow areas with said route generator, and at least one of:

computing intervisibility sums with said route generator;

minimizing intervisibility sums with said route generator;

maximizing intervisibility sums per distance traveled with said route generator; and

maximizing intervisibility unions per distance traveled with said route generator.

15. The computer program product of claim 12, further comprising:

generating with the intervisibility analyzer a viewshed for each node using a position of each node, the viewshed including a set whose elements comprise other nodes having an optical line of sight to each node, and counting the number of the elements in the viewshed to determine a cardinality size of the viewshed as the visibility of each node for quantifying an extent to which a traveler is exposed when traveling across terrain represented by each node;

retrieving with the speed analyzer a land cover map and traversal matrix, querying the land cover map for a terrain type for each node using a position of each node, returning a speed of the terrain type found in the traversal matrix representing how fast the traveler can travel across terrain represented by each of the nodes;

generating with a minimum edge cost finder a minimum cost edge using said blended cost grid and configured for searching edges of a graph to find the minimum cost edge used for computing heuristics, the minimum cost edge being the edge with a minimum blended cost between any two adjacent nodes in the graph; and

generating with the route generator routes that facilitate tactical movement based on said blended cost grid and computed heuristics.