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.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention generally relates to generation of tactical routes, and more particularly to a method and system for generating geographic terrain routes that balance speed and exposure to potential threats. 
         [0003]    2. Discussion of the Background 
         [0004]    Soldiers planning tactical routes must ensure that each route allows them to remain concealed from enemy observers yet move quickly at the same time. Creating these routes is a challenging process that requires great effort with no guarantee of desired results. 
         [0005]    First, soldiers must gather intelligence on the terrain to be traversed. Often, this comes in the form of topographic maps, aerial photos, incident reports, previous mission plans, and firsthand knowledge. Soldiers operating in areas with more attention and traffic may receive accurate, up to date maps; others, like Special Forces soldiers operating in remote terrain, may receive local maps that are often highly outdated. Soldiers have helpful acronyms to help them remember what factors to consider when analyzing terrain and gathering intelligence for route planning, such as OCOKA (observation, concealment and cover, obstacles, key terrain, and avenues of approach). Soldiers also analyze the contour lines in topographic maps in an attempt to visualize the lay of the land. Reading contour maps and visualizing terrain is a skill that takes years of training and practice to refine and use properly. Satellites and spy planes flying overhead provide aerial photographs that reveal critical details about the battlefield terrain, such as vegetation, structures, and enemy force composition. 
         [0006]    Next, soldiers use the intelligence gathered to plan a route. Choosing a starting location first, often a forward operating base, combat outpost, or objective rally point, soldiers then plan routes one waypoint at a time. Many soldiers use digital mapping software, either on personal computers or global positioning system (UPS) devices, to place waypoints. Software then connects each subsequent waypoint placed by the soldier with a straight line. In complex terrain, soldiers are forced to look closely at the map, placing waypoints close together so that the connecting lines do not intersect buildings and other obstructions. Often, soldiers spend hours placing hundreds of waypoints in this manner, refining route legs and tweaking waypoints, until the route reaches the destination. At this point, a primary route has been planned, but that is not good enough; on top of that, soldiers will generate at least one more, and typically three more routes to account for contingent and emergency situations. These routes must still be fast and safe to travel but sufficiently different from each other to be expedient in the field. 
         [0007]    Finally, soldiers traverse the route. Sometimes, route traversal will be preceded by a route reconnaissance where one or more scouts observe the avenues of approach used by the route for enemy action or other interesting intelligence. When soldiers finally embark on the route, there is usually no guarantee that the intelligence used to plan the route has not since changed drastically. Knowing this, each soldier ensures that he knows his current position at all times so that he can react quickly if the plan changes. Evidence that the plan can (and often does) change can be found in accounts of the Battle of Mogadishu, Battle for Baghdad, and countless others. 
         [0008]    From the above description of tactical route planning, it is easy to see that planning tactical routes correctly is extremely difficult. Imagine how a soldier&#39;s workflow would look if assisted by a computer software tool for planning tactical routes. First, the amount of time and effort spent analyzing intelligence is decreased because the tool analyzes every single terrain cell. Second, the amount of time and effort spent meticulously dropping hundreds of waypoints for multiple routes is greatly reduced because the tool automatically generates routes. A soldier using that kind of tactical route planning tool would be able to spend less time on detailed planning and more time on other important tasks, such as route reconnaissance or mission execution. 
         [0009]    However, soldiers have not had access to such a tactical route planning tool in the past. While many civilians benefit daily from analogous route planning tools (MapQuest, Google Maps, and Microsoft Streets and Trips) that help them plan fast and short routes along highway networks, soldiers have simply not had access to that kind of tool for military purposes. 
         [0010]    The state of the art 111 tactical route generation suffers from the following important disadvantages: 
         [0011]    Fails to suggest intelligent ground maneuvers. Although the state of the art for path planning and terrain awareness in the field of aviation is well-developed, the state of the art in providing similar tools for ground-based maneuvers is lacking. Few tools currently exists that suggest intelligent schemes of maneuver on the ground that utilize terrain information such as land cover maps and digital elevation models. 
         [0012]    Fails to blend speed and concealment. During tactical movement, soldiers need to move quickly while remaining concealed, taking advantage of fast terrain that also provides sufficient concealment and cover. However, the state of the art commonly generates routes that aim to maximize concealment or speed with no thought as to how these factors could be blended to provide a more usable route. As a result, tactical routes created using state of the art methods often suffer from being too exposed when maximizing speed or too slow when maximizing concealment. 
       SUMMARY OF THE INVENTION 
       [0013]    Therefore, there is a need for a method and system that addresses the above and other problems. The above and other problems are addressed by the exemplary embodiments of the present invention, which generates geographic routes that facilitate tactical movement through surrounding terrain. 
         [0014]    Accordingly, in exemplary aspects of the present invention there is provided a computer-implemented system and method for generating tactically-feasible routes in battlefield terrain including an Intervisibility Analyzer for analyzing propagation of optical lines of sight in a geographic terrain, a Speed Analyzer for analyzing speed of travelers in the geographic terrain, and a Route Generator for generating routes that facilitate tactical movement. 
         [0015]    The Intervisibility Analyzer utilizes a digital elevation model of terrain to compute a populate a database of viewsheds for each point in the model, where each viewshed is a set of other points having optical line of sight to the point. 
         [0016]    The Speed Analyzer determines how fast a traveler may move across varying types of terrain. 
         [0017]    The Route Generator searches the nodes and edges in a graph representing the cost grid to generate the best path between a start and end point. 
         [0018]    Advantageously, the exemplary embodiments include various features that are of particular utility, for example, including suggesting intelligent ground maneuvers. The exemplary embodiments provide to ground soldiers what aviators have had for quite some time: intelligent routing tools that suggest the correct path of travel based on environmental factors like terrain types and visibility. 
         [0019]    In addition, the exemplary embodiments blend speed and concealment during route generation, helping to ensure that soldiers can reach the destination quickly and unobserved. 
         [0020]    In addition, The exemplary embodiments mimic the way soldiers actually plan concealed tactical routes. During tactical movement, soldiers accept exposure to the surrounding area, but with every step, try to minimize the amount of new terrain to which they are exposed. This explains why rounding corners, entering rooms, and coming up over ridges are all dangerous movements; they expose the soldier to large amounts of previously hidden terrain all at once. The exemplary embodiments create routes that minimize the amount of new terrain to which route travelers are exposed during travel and do so by minimizing the sums of the sizes of the unions of the sets of points visible to each route waypoint. This key technique is subtly different and yet vastly superior to any existing technique which tries to minimize the sums of the sizes of the sets of points visible to each route waypoint because it mimics the way soldiers actually plan tactical routes. 
         [0021]    In addition, the exemplary embodiments maximize any advantages in weapons range. Soldiers in tactical environments may sometimes desire to move in open areas where terrain allows them to move quickly and their weapons capabilities are maximized for the areas visible during travel. Soldiers moving in this fashion leverage routes through open areas to stay outside the range of enemy weaponry but inside the range of their own weaponry and visibility. The exemplary embodiments generate routes that allow soldiers to maximize the advantages in range afforded by their weapons and have the capability to generate routes that utilize both highly visible and fast terrain, thereby allowing a soldier to more fully leverage any potential advantages in weapons (e.g., 50 caliber guns) or surveillance (e.g., night vision). 
         [0022]    In addition, the exemplary embodiments create routes that facilitate efficient searching between waypoints. Soldiers in tactical environments may sometimes desire to travel between two waypoints while maximizing the amount of visible terrain per unit of distance travelled. Generating a route like this by hand would be extremely difficult for a human. The exemplary embodiments generate routes that maximize visibility per unit distance travelled and do so by exposing travelers to the largest collective area of terrain while minimizing the distance travelled. 
         [0023]    Still other aspects, features, and advantages are readily apparent from the following detailed description, by illustrating a number of exemplary embodiments and implementations. The present invention is also capable of other and different embodiments, and its several details can be modified in various respects, all without departing from the spirit and scope of the present invention. Accordingly, the drawings and descriptions are to be regarded as illustrative in nature, and not as restrictive. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0024]    The embodiments of the present invention are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which: 
           [0025]      FIG. 1  illustrates an Overall System for Tactical Routing; 
           [0026]      FIGS. 2A&amp;B  illustrate a Cost Generator; 
           [0027]      FIG. 3  illustrates Cost Generator Example; 
           [0028]      FIG. 4  illustrates a Speed Analyzer; 
           [0029]      FIG. 5  illustrates a Speed Analyzer Example 
           [0030]      FIG. 6  illustrates an Intervisibility Analyzer; 
           [0031]      FIG. 7  illustrates an Intervisibility Analyzer Example; 
           [0032]      FIGS. 8A&amp;B  illustrate a Minimum Edge Cost Finder; 
           [0033]      FIG. 9  illustrates a Minimum Edge Cost Finder Example; 
           [0034]      FIG. 10  illustrates a Route Generator; 
           [0035]      FIGS. 11A-E  illustrate a Route Generator Example; 
           [0036]      FIG. 12  illustrates a Cost Evaluator; 
           [0037]      FIG. 13  illustrates a Cost Evaluator Example; 
           [0038]      FIG. 14  illustrates a second Cost Evaluator Example; 
           [0039]      FIGS. 15A-F  illustrate a second Route Generator Example; and 
           [0040]      FIGS. 16A&amp;B  illustrate a second Cost Generator. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0041]    An exemplary embodiment for generating tactical routes is one that minimizes the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain. By minimizing the path&#39;s intervisibility union, travelers are exposed to a minimal amount of previously-unexposed terrain after beginning travel, thereby reducing the risk of encountering enemies in unexposed terrain. By avoiding slow terrain below an arbitrary threshold, travelers can travel at or above the speed threshold at every node on the path, rendering it difficult for enemies to engage the traveler in combat. 
         [0042]    Referring now to the drawings,  FIG. 1  illustrates the system&#39;s main components of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain. The Cost Generator  100  uses speed and visibility information to create a blended cost grid for generating tactical routes. The Minimum Edge Cost Finder  102  searches the edges of a graph to find the minimum cost edge which is used in computing heuristics while generating tactical routes. The Route Generator  104  generates tactical routes. Each of the components has access to a collection of databases. The Map Database  110  contains geographic information including land cover maps, cost surfaces, and graphs. The Map Database  110  is a standard Geographic Information System (GIS) such as Mapinfo by ESRI, Inc. of Redlands, Calif. The Intervisibility Database  108  contains viewsheds where each viewshed is a set of terrain locations having optical line of sight to an observing location. Algorithms for computing viewsheds use digital elevation models (DEMs) of varying resolution and complexity, and these algorithms are well-known to those skilled in the art of terrain analysis. An example of one such algorithm for computing viewsheds is the ESRI Visibility algorithm in the ISurfaceOp package. As such, the Intervisibility Database  108  is populated with pre-computed viewsheds, and the computation of these viewsheds for example, can be performed using ESRI&#39;s “Visibility” function, available on the World Wide Web at webhelp.esri.com/arcgisdesktop/9.1/body.cfm?toeVisable=0&amp;ID=3189&amp;TopicNa me=visibility, and incorporated by reference herein. Also, storing viewsheds for DEMs in an easily-accessible format is non-trivial due to memory complexity; however, methods for doing so are also known to those skilled in the art of terrain analysis. As such, storage of the viewsheds and the architecture and formation of the Intervisibility Database  108  can be performed, for example, using “Analysis and Visualization of Visibility Surfaces”, at www.geocomputation.org/2003/Papers/Caldwell_Paper.pdf, and incorporated by reference herein. The Intervisibility Database  108  is rectified to match the coordinates used in the Map Database  110 . The Capabilities Database  106  contains a traversal matrix for mapping land cover types to traversal speeds and a visibility matrix for mapping visibility parameters to varying observer capabilities. 
         [0043]    The following sections describe in detail the components of the exemplary embodiments. 
         [0044]      FIG. 2  illustrates the Cost Generator  100  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain. The Cost Generator  100  begins at step  200  by retrieving the threshold traversal speed from the Capabilities Database  106 . At step  202 , the Cost Generator  100  retrieves the cost grid from the Map Database  110 . At step  204 , the Cost Generator  100  retrieves the graph from the Map Database  110 . At step  206 , the Cost Generator  100  obtains the list of nodes from the graph. At step  208 , the Cost Generator  100  determines if there are more nodes to evaluate. If not, at step  222 , the Cost Generator  100  stores the now-populated cost grid back to the Map Database  110  and terminates. If so, at step  210 , the Cost Generator  100  gets the current node and proceeds to step  212 . At step  212 , the Cost Generator  100  obtains the node&#39;s speed by passing the node to the Speed Analyzer  212 . At step  214 , the Cost Generator  100  determines whether the node&#39;s speed is below the threshold traversal speed. If so, at step  220 , the Cost Generator  100  sets the node&#39;s corresponding cell in the cost grid to a cost of infinity to indicate the node is impassable and proceeds to step  208 . If not, at step  216 , the Cost Generator  100  obtains the node&#39;s visibility by passing the node to the Intervisibility Analyzer  216  and proceeds to step  218 . At step  218 , the Cost Generator  100  sets the node&#39;s corresponding cell in the cost grid to the visibility and continues evaluating nodes by proceeding to step  208 . At step  222 , the Cost Generator  100  stores the cost grid. Upon termination after step  222 , the Cost Generator  100  will have set the cost of each node&#39;s corresponding cell in the cost grid in the Map Database  110 . The Cost Generator  100  constructs the cost grid to facilitate the Route Generator  104  avoiding nodes having too slow a traversal speed (i.e., traversal speeds below a threshold value). 
         [0045]    To better understand the Cost Generator  100  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain, consider the example in  FIG. 3 . The Cost Generator  100  first retrieves the threshold traversal speed  300  from the Capabilities Database  106 . Next, the Cost Generator  100  retrieves the cost grid  302  from the Map Database  110 . Next, the Cost Generator  100  retrieves the graph  304  from the Map Database  110 . Next, the Cost Generator  100  obtains the node list  306  from the graph  304 . Next, the Cost Generator  100  examines each node in the node list  306 . In this example  300 , the Cost Generator  100  selects node  308  with label 3 at position (0, 2). Next, the Cost Generator  100  passes the node  308  to the Speed Analyzer  212 . The Speed Analyzer  212  returns a speed of 20 kph. Next, the Cost Generator  100  determines that the speed of the node  308 , 20 kph, is not below the threshold traversal speed  300  of 5 kph. Next, the Cost Generator  100  passes the node  308  to the Intervisibility Analyzer  216 . The Intervisibility Analyzer  216  returns a visibility of 4 cells. Next, the Cost Generator  100  sets the corresponding cell  310  with label 3 at position (0,2) in the cost grid  302  to 4 and continues evaluating nodes until termination. In another example, the Cost Generator  100  selects node  312  with label 10 at position (2,1). Next, the Cost Generator  100  passes the node  312  to the Speed Analyzer  212 . The Speed Analyzer  212  returns a speed of 0 kph. Next, the Cost Generator  100  determines that the speed of the node  312 , 0 kph, is below the threshold traversal speed  300  of 5 kph. Next, the Cost Generator  100  sets the corresponding cell  314  with label 10 at position (2,1) in the cost grid  302  to infinity (∞) and continues evaluating nodes until termination. After evaluating each node in the node list  306 . the Cost Generator  100  will have set the costs of each corresponding cell in the cost grid  302 . The Cost Generator  100  then terminates. 
         [0046]      FIG. 4  illustrates the Speed Analyzer  212  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain. The Speed Analyzer  212  begins at step  400  by retrieving the node passed in from the Cost Generator  100 . At step  402 , the Speed Analyzer  212  retrieves the land cover map from the Map Database  110 . At step  404 , the Speed Analyzer  212  retrieves the traversal matrix from the Capabilities Database  106 . At step  406 , the Speed Analyzer  212  queries the land cover map for the node&#39;s terrain type using the node&#39;s position. At step  408 , the Speed Analyzer  212  returns the speed of the terrain type found in the traversal matrix and terminates. Upon termination, the Speed Analyzer  212  has found the speed for the node. Speeds represent how fast a traveler can travel across the terrain represented by the node. 
         [0047]    To better understand the Speed Analyzer  212  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain, consider the example in  FIG. 5 . The Speed Analyzer  212  retrieves the node  500  with label 3 at position (0,2) from the Cost Generator  100 . Next, the Speed Analyzer  212  retrieves the land cover map  502  from the Map Database  110 . Next, the Speed Analyzer  212  retrieves the traversal matrix  504  from the Capabilities Database  106 , Next, the Speed Analyzer  212  queries the land cover map  502  for the terrain type of the node  500  with label 3 at position (0,2). The land cover map  502  indicates that the terrain type of the node  500  with label 3 at position (0,2) is field. Next, the Speed Analyzer  212  queries the traversal matrix  504  for the speed of the field terrain type. The traversal matrix  504  indicates that the speed of the field terrain type is 20 kph. The Speed Analyzer  212  then terminates by returning a speed of 20 kph. In another example, the Speed Analyzer  212  retrieves the node  506  with label 10 at position (2,1) from the Cost Generator  100 . Later, the Speed Analyzer  212  queries the land cover map  502  for the terrain type of the node  506  with label 10 at position (2,1). The land cover map  502  indicates that the terrain type of the node  506  with label 10 at position (2,1) is water. Next, the Speed Analyzer  212  queries the traversal matrix  504  for the speed of the water terrain type. The traversal matrix  504  indicates that the speed of the water terrain type is 0 kph. The Speed Analyzer  212  then terminates by returning a speed of 0 kph. 
         [0048]      FIG. 6  illustrates the Intervisibility Analyzer  216  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain. The Intervisibility Analyzer  216  begins at step  600  by retrieving the node passed in from the Cost Generator  100 . At step  602 , the Intervisibility Analyzer  216  queries the Intervisibility Database  108  for the node&#39;s viewshed V using the node&#39;s position. The viewshed V is a set whose elements comprise the nodes having optical line of sight to the node, and the Intervisibility Database  108  is the record of all such sets. At step  604 , the Intervisibility Analyzer  216  counts the number of elements in V to determine the V&#39;s cardinality (size), |V|. At step  606 , the Intervisibility Analyzer  216  terminates by returning IV as the visibility. Upon termination, the Intervisibility Analyzer  216  has found the visibility for the node. Visibility quantifies the extent to which a traveler is exposed when traveling across the terrain represented by the node. 
         [0049]    To better understand the Intervisibility Analyzer  216  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain, consider the example in  FIG. 7 . The Intervisibility Analyzer  216  retrieves the node  700  with label 7 at position (1,2) from the Cost Generator  100 . Next, the Intervisibility Analyzer  216  queries the Intervisibility Database  108  for the viewshed  702  of the node  700  with label 7 at position (1,2). The Intervisibility Database  108  indicates that the viewshed  702  of the node  700  with label 7 at position (1,2) (2,3), (1,2), (2,2), (1,1)). Next, the Intervisibility Analyzer  216  counts the number of elements in the viewshed  702  to determine the cardinality (size) of viewshed  702 . The Intervisibility Analyzer  216  determines that the visibility is 4. Next, the Intervisibility Analyzer  216  terminates by returning 4. 
         [0050]      FIG. 8  illustrates the Minimum Edge Cost Finder  102  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain. The Minimum Edge Cost Finder  102  begins at step  800  by retrieving the graph as input. At step  802 , the Minimum Edge Cost Finder  102  retrieves the visibility matrix from the Intervisibility Database  108 . At step  804 , the Minimum Edge Cost Finder  102  sets the current minimum edge cost C to the maximum viewshed cardinality indicated by the visibility matrix. At step  806 , the Minimum Edge Cost Finder  102  obtains the list of edges from the graph. At step  808 , the Minimum Edge Cost Finder  102  determines if there are more edges to evaluate. If not, at step  828 , the Minimum Edge Cost Finder  102  returns C. If so, at step  810 , the Minimum Edge Cost Finder  102  obtains the current edge from the graph. At step  812 , the Minimum Edge Cost Finder  102  queries the Intervisibility Database  108  for the viewsheds V I and V 2  of the Edge&#39;s nodes N 1  and N 2  using the nodes&#39; positions. The viewsheds V 1  and V 2  are sets whose elements comprise the nodes having optical line of sight to nodes Ni and N 2  respectively. At step  814 , the Minimum Edge Cost Finder  102  calculates a first difference D  1  by subtracting V 2  from V 1  using set subtraction, as indicated by the following formula: 
         [0000]        D 1= V 1− V 2
 
         [0051]    Dl represents the set of elements in V  1  and not in V 2 . At step  816 , the Minimum Edge Cost Finder  102  counts the number of elements in DI to determine the DI&#39;s cardinality, |D 1 |. At step  818 , the Minimum Edge Cost Finder  102  calculates a second difference D 2  by subtracting V 1  from V 2  using set subtraction, as indicated by the following formula: 
         [0000]        D 2= V 2− V 1
 
         [0052]    D 2  represents the set of elements in V 2  and not V 1 . It is noteworthy that DI may or may not be equal to D 2 . At step  820 , the Minimum Edge Cost Finder  102  counts the number of elements in D 2  to determine the D 2 &#39;s cardinality, |D 2 |. At step  822 , the Minimum Edge Cost Finder  102  tests if |D 1 | or |D 2 | equals 0 (is minimal). If so, the Minimum Edge Cost Finder  102  sets C to 0 at step  824  and returns C at step  828 . If not, at step  826 , the Minimum Edge Cost Finder  102  updates C to the smaller of |D 1 |, |D 2 |, and C, as indicated by the following formula: 
         [0000]        C =Minimum(| D 1|,| D 2| C ) 
         [0053]    At step  808 , the Minimum Edge Cost Finder  102  continues evaluating edges. Upon termination after step  828 , the Minimum Edge Cost Finder  102  will have found C, the smallest possible incremental cost of moving from one node to any adjacent node in any direction. 
         [0054]    To better understand the Minimum Edge Cost Finder  102  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain, consider the example in  FIG. 9 . First, the Minimum Edge Cost Finder  102  retrieves the graph  900  as input. Next, the Minimum Edge Cost Finder  102  retrieves the visibility matrix  902  from the Intervisibility Database  108 . Next, the Minimum Edge Cost Finder  102  sets the current minimum edge cost C to the maximum viewshed cardinality indicated by the visibility matrix  904 . In this example, the observer type is human, so the Minimum Edge Cost Finder  102  sets C to 9. Next, the Minimum Edge Cost Finder  102  obtains the edge list  904  from the graph  900 . Next, in this example, the Minimum Edge Cost Finder  102  selects the edge  900  with label 1 for evaluation. Next, the Minimum Edge Cost Finder  102  queries the Intervisibility Database  108  for the viewshed V 1   908  of the first node of the edge  906 . Next, the Minimum Edge Cost Finder  102  queries the Intervisibility Database  108  for the viewshed V 2   910  of the second node of the edge  906 . Next, the Minimum Edge Cost Finder  102  calculates a first difference D 1  by subtracting V 2  from V 1  using set subtraction as follows: 
         [0000]        DI=V 1− V 2={(0,1),(0,0),(1,0)}|{(0,2),(0,1),(0,0),(1,0)}=φ
 
         [0055]    Dl represents the set of elements in V 1  and not in V 2 ; in this example, V 1  has no elements not in V 2 , so DI is the empty set (φ). Next, the Minimum Edge Cost Finder  102  counts the number of elements in D 1  to determine D 1 &#39;s cardinality, |D 1 |. In this case, |D 1 |=0. Next, the Minimum Edge Cost Finder  102  calculates a second difference D 2  by subtracting V 1  from V 2  using set subtraction as follows: 
         [0000]        D 2= V 2− V 1={(0,2),(0,1),(0,0),(1,0))−{(0,1(0,0),(1,0))={(0,2)}
 
         [0056]    D 2  represents the set of elements in V 2  not in V 1 ; in this example, V 2  has some elements not in V 1 . Next, the Minimum Edge Cost Finder  102  counts the number of elements in D 2  to determine the D 2 &#39;s cardinality, |D 2 |. In this case, |D 2 |=1. Next, the Minimum Edge Cost Finder  102  tests if |D 1 | or |D 2 |equals 0 (is minimal). In this example, |D 1 |=0, so the Minimum Edge Cost Finder  102  sets C to 0 and terminates by returning C. 
         [0057]      FIG. 10  illustrates the Route Generator  104  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain, The Route Generator  104  begins at step  1000  by retrieving the graph as input. At step  1002 , the Route Generator  104  retrieves the cost grid from the Map Database  110 . The Route Generator  104  then executes the A* algorithm  1004 , which finds an optimal path from a start node to an end node. The Route Generator  104  assumes the nodes of the graph  1000  are pre-initialized for use in the A* algorithm  1004 . The A* algorithm  1004  is well known to those skilled in the art, and can be performed, for example, using -Artificial Intelligence, Third Edition” by Patrick Henry Winston, published by Addison-Wesley, which is incorporated by reference herein. Initialization of a graph&#39;s nodes for use in the A* algorithm  1004  is also well-known to those skilled in the art and can be performed, for example, using chapter 5 of the book “Artificial Intelligence, Third Edition” by Patrick Henry Winston, published by Addison-Wesley. 
         [0058]    The Route Generator  104  necessitates inclusion of a union field in each node that stores a union of one or more viewsheds. The Route Generator  104  computes and maintains each node&#39;s union field in the same manner as each node&#39;s key field is normally computed and maintained. Throughout, a node&#39;s union field represents the set union of the viewsheds of the nodes in the path leading up to the node, and a node&#39;s key field represents the cardinality of the node&#39;s union (i.e., the number of nodes in the union). It follows that initialization of the union field for use in the A* algorithm  1004  requires setting the start node&#39;s union field to the start node&#39;s viewshed from the Intervisibility Database  108 , the start node&#39;s key field to the cardinality of the start node&#39;s union field, and the union and key fields for all other nodes to null and zero respectively. It also follows that in the step where the A* algorithm  1004  relaxes a node, both the node&#39;s key and union fields are relaxed as well. In the step where the A* algorithm  1004  considers adjacent nodes, the Route Generator  104  will ignore adjacent nodes having infinite cost as indicated by the cost grid contained in the Map Database  110 . The effect of this modification is that the Route Generator  104  does not include nodes with infinite cost in the optimal path, thereby ensuring that the traversal speeds of each node in the optimal path meets or exceeds a threshold value. It is realized that this modification may cause the Route Generator  104  to report that no route exists. However, alternate exemplary embodiments of the Route Generator  104  may allow nodes having infinite cost into the minimum priority queue, facilitating route generation at the expense of breaking below the speed threshold if no other route exists. At step  1006 , the A* algorithm  1004  calculates the cost from the current node in consideration to the adjacent node in consideration, but substitutes use of the Cost Evaluator  1006  to obtain the cost. The Cost Evaluator  1006  computes the key and union fields for adjacent nodes as well as an estimate used for ordering nodes in the minimum priority queue. At step  1008 , the Route Generator  104  returns the tactical route. 
         [0059]    To better understand the Route Generator  104  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain, consider the example in  FIG. 11 . First, the Route Generator  104  begins by retrieving the graph  1100  as input, which specifies a start node  1106  and an end node  1108 . The Route Generator  104  will generate the optimal path from the start node  1106  with label 7 at position (1,2) to the end node  1108  with label 13 at position (3,0). Next, the Route Generator  104  retrieves the cost grid  1102  from the Map Database  110 . Next, the Route Generator  104  executes the A* algorithm  1004 . In this step, the A* algorithm  1004  configures a node table  1104  and initializes the fields of each node in the table  1104 . Next  1110 , the A* algorithm  1004  begins by examining the start node  1106  with label 7. Next  1112 , the cost of moving from node 7 to each of node 7&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . Since each of node 7&#39;s adjacent nodes are unvisited, all are added to the minimum priority queue, except node  10  which is ignored because it has infinite cost. 
         [0060]    Next  1114 , node 7 is retired and node II is extracted from the minimum priority queue. Next  1116 , the cost of moving from node 11 to each of node 11&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and some of node 11&#39;s adjacent nodes are added to the minimum priority queue. 
         [0061]    Next  1118 , node 11 is retired and node 6 is extracted from the minimum priority queue. Next  1120 , the cost of moving from node 6 to each of node 6&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and some of node 6&#39;s adjacent nodes are added to the minimum priority queue. 
         [0062]    Next  1122 , node 6 is retired and node 16 is extracted from the minimum priority queue. Next  1124 , the cost of moving from node 16 to each of node 16&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 16&#39;s adjacent nodes are added to the minimum priority queue. 
         [0063]    Next  1126 , node 16 is retired and node 14 is extracted from the minimum priority queue. Next  1128 , the cost of moving from node 14 to each of node 14&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 14&#39;s adjacent nodes are added to the minimum priority queue, including node 13, the end node. At this point, a path from the start node  1106  to the end node  1108  has been found: node 7 to 11 to 14 to 13, and the cost of this path is 9. However, since this may not be the optimal path, the algorithm continues searching. 
         [0064]    Next  1130 , node 14 is retired and node 4 is extracted from the minimum priority queue. Next  1132 , the cost of moving from node 4 to each of node 4&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 4&#39;s adjacent nodes are added to the minimum priority queue. 
         [0065]    Next  1134 , node 4 is retired and node 8 is extracted from the minimum priority queue. Next  1136 , the cost of moving from node 8 to each of node 8&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 8&#39;s adjacent nodes are added to the minimum priority queue, 
         [0066]    Next  1138 , node 8 is retired and node 12 is extracted from the minimum priority queue. Next  1140 , the cost of moving from node 12 to each of node 12&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 12&#39;s adjacent nodes are added to the minimum priority queue. 
         [0067]    Next  1142 , node 12 is retired and node 15 is extracted from the minimum priority queue. Next  1144 , the cost of moving from node 15 to each of node 15&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 15&#39;s adjacent nodes are added to the minimum priority queue. 
         [0068]    Next  1146 , node 15 is retired and node 9 is extracted from the minimum priority queue. Next  1148 , the cost of moving from node 9 to each of node 9&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . Node 13 is relaxed from a cost of 9 to a cost of 7, and none of node 9&#39;s adjacent nodes are added to the minimum priority queue. 
         [0069]    Next  1150 , node 9 is retired and node 13 is extracted from the minimum priority queue. Since node 13 was extracted from the queue, the optimal path from start to end has been found and node evaluation terminates. Next, the optimal path  1154  is constructed by following parent pointers starting at node 13. The optimal path  1154  is found to be node 7 to 6 to 9 to 13 with a cost of 7. The optimal path also meets the speed constraint by avoiding use of node 10, the only node with infinite cost in the graph. The Route Generator  104  then terminates by returning the optimal path. 
         [0070]      FIG. 12  illustrates the Cost Evaluator  1006  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain. The Cost Evaluator  1006  begins at step  1200  by retrieving the current node as input. At step  1202 , the Cost Evaluator  1006  retrieves the adjacent node as input. At step  1204 , the Cost Evaluator  1006  queries the Intervisibility Database  108  for the viewshed V of the adjacent node using the adjacent node&#39;s coordinates. At step  1206 , the Cost Evaluator  1006  obtains the current union Ucurrent stored in the current node&#39;s union field. At step  1208 , the Cost Evaluator  1006  calculates the adjacent union Uadjacent as the union of V and Ucurrent as follows: 
         [0000]        U adjacent= V U U current 
         [0071]    At step  1210 , the Cost Evaluator  1006  retrieves the minimum edge cost as input. At step  1212 , the Cost Evaluator  1006  calls the Underestimate Generator  1212  to determine an estimate E of the cardinality of the union of the best path from the adjacent node to the end node. The Underestimate Generator  1212  uses the diagonal distance heuristic, which measures distance accumulated by traveling along both axial and diagonal edges in a graph. The diagonal distance heuristic can be computed using, for example, “An optimal pathfinder for vehicles in real-world digital terrain maps”, at www.student.nada.kth.se/-f93-maj/pathfinder/4.html#1, and incorporated by reference herein. The Underestimate Generator  1212  then multiplies the result of the optimal distance heuristic by the minimum edge cost to obtain the estimate E as follows: 
         [0000]        E =minimum edge cost 1308*Distance estimate 
         [0072]    Those skilled in the art are familiar with the methods used for generating underestimates, namely finding the minimum edge cost in the graph and multiplying it by an underestimate of the distance from the adjacent node to the end node. As such, the Underestimate Generator  1212  will not be described any further herein. Instead, please refer to U.S. Pat. No. 6,963,800 to Milbert, which is incorporated herein by reference. At step  1214 , the Cost Evaluator  1006  sets the estimated route cost Restimated of the adjacent node by summing the result of the Underestimate Generator  1212  and the cardinality of Uadjacent, |Uadjacent|, as follows: 
         [0000]        R estimated= E+|U adjacent| 
         [0073]    At step  1216 , the Cost Evaluator  1006  sets the adjacent route cost Radjacent of the adjacent node to Uadjacent&#39;s cardinality as follows: 
         [0000]        R adjacent=| U adjacent| 
         [0074]    After step  1216 , the Cost Evaluator  1006  terminates. 
         [0075]    To better understand the Cost Evaluator  1006  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain, consider the example in  FIG. 13 . The Cost Evaluator  1006  retrieves the current node  1300  with label 7 at position (1,2) from the Route Generator  104 . Next, the Cost Evaluator  1006  retrieves the adjacent node  1302  with label 3 at position (0,2). Next, the Cost Evaluator  1006  queries the Intervisibility Database  108  for the viewshed  1304  V of the adjacent node  1302  with label 3 at position (0,2). The Intervisibility Database  108  indicates that the viewshed  1304  of the adjacent node  1302  with label 3 at position (0.2) is {(0,3). (1,3), (0,2), (0,1)). Next, the Cost Evaluator  1006  obtains the union  1306  Ucurrent of the current node  1300 . In this example, Ucurrent=1(2,3), (1,2), (2,2), (1,1)}. Next, the Cost Evaluator  1006  computes the adjacent union Uadjacent as follows: 
         [0000]    
       
         
           
             
               Uadjacent 
               = 
               
                 VuUcurrent 
                 = 
                 
                   1 
                    
                   
                     ( 
                     
                       2 
                       , 
                       3 
                     
                     ) 
                   
                 
               
             
             , 
             
               ( 
               
                 1 
                 , 
                 2 
               
               ) 
             
             , 
             
               ( 
               
                 2 
                 , 
                 2 
               
               ) 
             
             , 
             
               
                 ( 
                 
                   1 
                   , 
                   1 
                 
                 ) 
               
                
               1 
                
               u 
                
               
                   
               
                
               1 
                
               
                 ( 
                 
                   0 
                   , 
                   3 
                 
                 ) 
               
             
             , 
             
               ( 
               
                 1 
                 , 
                 3 
               
               ) 
             
             , 
             
               ( 
               
                 0 
                 , 
                 2 
               
               ) 
             
             , 
             
               
                 
                   ( 
                   
                     0 
                     , 
                     1 
                   
                   ) 
                 
                  
                 1 
               
               = 
               
                 { 
                 
                   
                     ( 
                     
                       2 
                       , 
                       3 
                     
                     ) 
                   
                   , 
                   
                     ( 
                     
                       1 
                       , 
                       2 
                     
                     ) 
                   
                   , 
                   
                     ( 
                     
                       2 
                       , 
                       2 
                     
                     ) 
                   
                   , 
                   
                     ( 
                     
                       1 
                       , 
                       1 
                     
                     ) 
                   
                   , 
                   
                     ( 
                     
                       0 
                       , 
                       3 
                     
                     ) 
                   
                   , 
                   
                     ( 
                     
                       1 
                       , 
                       3 
                     
                     ) 
                   
                   , 
                   
                     ( 
                     
                       0 
                       , 
                       2 
                     
                     ) 
                   
                   , 
                   
                     ( 
                     
                       0 
                       , 
                       1 
                     
                     ) 
                   
                 
                 ) 
               
             
           
         
       
     
         [0076]    Next, the Cost Evaluator  1006  retrieves the minimum edge cost  1308  as input. In this example, the minimum edge cost  1308  is 0. Next, the Cost Evaluator  1006  calls the Underestimate Generator to determine an estimate E. In this example, the Underestimate Generator computes E as follows: 
         [0000]        E =minimum edge cost 1308*Distance estimate=0*Distance estimate=0 
         [0077]    Next, the Cost Evaluator  1006  computes the estimated route cost Restimated using E and the cardinality of Uadjacent as follows: 
         [0000]        R estimated=E+| U adjacent|=0+8= 
         [0078]    Finally, the Cost Evaluator  1006  computes the adjacent route cost Radjacent as follows: 
         [0000]        R adjacent=| U adjacent|=8 
         [0079]    Another exemplary embodiment for generating tactical routes is one that maximizes the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain. By maximizing the path&#39;s intervisibility union, travelers are exposed to a maximal amount of previously-unexposed terrain after beginning travel, thereby allowing travelers to exert a surveillance or weapons capability advantage (e.g., range) over enemies in unexposed terrain. By avoiding slow terrain below an arbitrary threshold, travelers can travel at or above the speed threshold at every node on the path, rendering it difficult for enemies to engage the traveler in combat. 
         [0080]    This exemplary embodiment for generating routes that maximize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain defines explicitly-different behavior for only the Cost Evaluator  1006  component, and implicitly-different behavior for the Route Generator  104  component. Also, this exemplary embodiment relies on using inverses of cost values representing union cardinality. A variation on this exemplary embodiment may, instead of taking inverse cost values representing union cardinality, utilize a maximum priority queue far selecting nodes in the A* algorithm  1004 . Such an exemplary embodiment would likely have to abandon using infinite costs to represent slow terrain. Yet another variation on this exemplary embodiment may cease node evaluation after each node adjacent to the end node has been retired. Although such an exemplary embodiment may be unobvious because it is not widely employed in the art, it may reduce the running time of the Route Generator  104  because wasted computation would be avoided. 
         [0081]    To illustrate the behavior of the Cost Evaluator  1006  of the exemplary embodiment for generating routes that maximize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain, refer to  FIG. 12 . At step  1214 , the Cost Evaluator  1006  sets the estimated route cost Restimated of the adjacent node by taking the inverse of the sum of the result of the Underestimate Generator  1212  and the cardinality of Uadjacent, |Uadjacent|, as follows: 
         [0000]        R estimated=1/( E|U adjacent|) 
         [0082]    At step  1216 , the Cost Evaluator  1006  sets the adjacent route cost Radjacent of the adjacent node to the inverse of Uadjacent&#39;s cardinality as follows: 
         [0000]        R adjacent=1 /|U adjacent| 
         [0083]    To better understand the Cost Evaluator  1006  of the exemplary embodiment for generating routes that maximize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain, consider the example in  FIG. 14 . The Cost Evaluator  1006  retrieves the current node  1400  with label 7 at position (1,2) from the Route Generator  104 . Next, the Cost Evaluator  1006  retrieves the adjacent node  1402  with label 3 at position (0,2). Next, the Cost Evaluator  1006  queries the Intervisibility Database  108  for the viewshed  1404  V of the adjacent node  1402  with label 3 at position (0,2). The Intervisibility Database  108  indicates that the viewshed  1404  of the adjacent node  1402  with label 3 at position (0,2) is {(0,3), (1,3), (0,2), (0,1)}. Next, the Cost Evaluator  1006  obtains the union  1406  Ucurrent of the current node  1400 . In this example, Ucurrent={(2,3), (1,2), (2,2), (1,1) Next, the Cost Evaluator  1006  computes the adjacent union Uadjacent as follows: 
         [0000]        U adjacent= V U Ul current={(2,3),(1,2),(2.2),(1,1)) U {(0,3),(1,3),(0,2),(0,1)}={(2,3),(1,2),(2,2),(1,1),(0,3),(1,3),(0,2),(0,1)1 
         [0084]    Next, the Cost Evaluator  1006  retrieves the minimum edge cost  1408  as input. In this example, the minimum edge cost  1408  is 0. Next, the Cost Evaluator  1006  calls the Underestimate Generator to determine an estimate E. In this example, the Underestimate Generator computes E as follows: 
         [0000]        E =minimum edge cost 1408*Distance estimate=0*Distance estimate=0 
         [0085]    Next, the Cost Evaluator  1006  computes the estimated route cost Restimated using E and the cardinality of Uadjacent as follows: 
         [0000]        R estimated=1/( E+|U adjacent|)=1/(0+8)=1/8−0.125
 
         [0086]    Finally, the Cost Evaluator  1006  computes the adjacent route cost Radjacent as follows: 
         [0000]        R adjacent=1 /|U adjacent|=1/8=0.125 
         [0087]    To better understand how the changes to the Cost Evaluator  1006  of the exemplary embodiment for generating routes that maximize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain affect the behavior of the Route Generator  104  of the same exemplary embodiment, consider the example in  FIG. 15 . First, the Route Generator  104  begins by retrieving the graph  1500  as input, which specifies a start node  1506  and an end node  1508 . The Route Generator  104  will generate the optimal path from the start node  1506  with label 7 at position (1,2) to the end node  1508  with label 13 at position (3,0). Next, the Route Generator  104  retrieves the cost grid  1502  from the Map Database  110 . Next, the Route Generator  104  executes the A* algorithm  1004 . In this step, the A* algorithm  1004  configures a node table  1504  and initializes the fields of each node in the table  1504 . Next  1510 , the A* algorithm  1004  begins by examining the start node  1506  with label 7. Next  1512 , the cost of moving from node 7 to each of node 7&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . Since each of node 7&#39;s adjacent nodes are unvisited, all are added to the minimum priority queue, except node 10 which is ignored because it has infinite cost. 
         [0088]    Next  1514 . node 7 is retired and node 3 is extracted from the minimum priority queue. Next  1516 , the cost of moving from node 3 to each of node 3&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . Nodes  2 ,  4 ,  6 , and  8  are relaxed, and none of node 3&#39;s adjacent nodes are added to the minimum priority queue. 
         [0089]    Next  1518 , node 3 is retired and node 6 is extracted from the minimum priority queue. Next  1520 , the cost of moving from node 6 to each of node 6&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . Nodes  2  and  11  are relaxed, and some of node 6&#39;s adjacent nodes are added to the minimum priority queue. 
         [0090]    Next  1522 , node 6 is retired and node 2 is extracted from the minimum priority queue. Next  1524 , the cost of moving from node 2 to each of node 2&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 2&#39;s adjacent nodes are added to the minimum priority queue. 
         [0091]    Next  1526 , node 2 is retired and node 5 is extracted from the minimum priority queue. Next  1528 , the cost of moving from node 5 to each of node 5&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . Node 9 is relaxed, and none of node 5&#39;s adjacent nodes are added to the minimum priority queue. 
         [0092]    Next  1530 , node 5 is retired and node 9 is extracted from the minimum priority queue. Next  1532 , the cost of moving from node 9 to each of node 9&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 9&#39;s adjacent nodes are added to the minimum priority queue. 
         [0093]    Next  1534 , node 9 is retired and node 14 is extracted from the minimum priority queue. Next  1536 , the cost of moving from node 14 to each of node 14&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . Nodes  11  and  13  are relaxed, and some of node 14&#39;s adjacent nodes are added to the minimum priority queue. 
         [0094]    Next  1538 , node 14 is retired and node 15 is extracted from the minimum priority queue. Next  1540 , the cost of moving from node 15 to each of node 15&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . Nodes  11  and  12  are relaxed, and some of node 15&#39;s adjacent nodes are added to the minimum priority queue. 
         [0095]    Next  1542 , node 15 is retired and node 12 is extracted from the minimum priority queue. Next  1544 , the cost of moving from node 12 to each of node 12&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . Node 8 is relaxed, and none of node 12&#39;s adjacent nodes are added to the minimum priority queue. 
         [0096]    Next  1546 , node 12 is retired and node 8 is extracted from the minimum priority queue. Next  1548 , the cost of moving from node 8 to each of node 8&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . Node 4 is relaxed, and none of node 8&#39;s adjacent nodes are added to the minimum priority queue. 
         [0097]    Next  1550 , node 8 is retired and node 4 is extracted from the minimum priority queue. Next  1552 , the cost of moving from node 4 to each of node 4&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 4&#39;s adjacent nodes are added to the minimum priority queue. 
         [0098]    Next  1554 , node 4 is retired and node 11 is extracted from the minimum priority queue. Next  1556 , the cost of moving from node 11 to each of node 11&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 11&#39;s adjacent nodes are added to the minimum priority queue. 
         [0099]    Next  1558 , node 11 is retired and node 16 is extracted from the minimum priority queue. Next  1560 , the cost of moving from node 16 to each of node 16&#39;s adjacent nodes is computed using the Cost Evaluator  1006 . No nodes are relaxed, and none of node 16&#39;s adjacent nodes are added to the minimum priority queue. 
         [0100]    Next  1562 , node 16 is retired and node 13 is extracted from the minimum priority queue. Since node 13 was extracted from the queue, the optimal path from start to end has been found and node evaluation terminates. Next, the optimal path  1566  is constructed by following parent pointers starting at node 13. The optimal path  1566  is found to be node 7 to 3 to 6 to 2 to 5 to 9 to 14 to 13 with a cost of 0.067 (approximating 1/15). The optimal path also meets the speed constraint by avoiding use of node 10, the only node with infinite cost in the graph. The Route Generator  104  then terminates by returning the optimal path. In the exemplary embodiment for generating routes that maximize the path&#39;s intervisibility union while meeting speed constraints by avoiding slow terrain, the Route Generator  104  produces the path having the maximum visibility union per distance travelled. In other words, the ratio of the cardinality of the path&#39;s union to the number of edges in the route is the maximum for any possible route. In this particular example, the Route Generator  104  produced a route with a visibility union size of 15 grid cells using only 7 edges, yielding a ratio of union size to distance traveled of 15/7=2.143, the highest such ratio for any possible route in this example. 
         [0101]    Another exemplary embodiment for generating tactical routes is one that minimizes the path&#39;s intervisibility sum while meeting speed constraints by avoiding slow terrain. By minimizing the path&#39;s intervisibility sum, travelers are exposed to a minimal amount of terrain after beginning travel, thereby reducing the risk of encountering enemies in unexposed terrain. By avoiding slow terrain below an arbitrary threshold, travelers can travel at or above the speed threshold at every node on the path, rendering it difficult for enemies to engage the traveler in combat. This exemplary embodiment omits use of the Minimum Edge Cost Finder  102  and the Cost Evaluator  1006  and modifies the behavior of the Cost Generator  100  of the exemplary embodiment for generating routes that maximize the path&#39;s intervisibility union. 
         [0102]      FIG. 16  illustrates the Cost Generator  100  of the exemplary embodiment for generating routes that minimize the path&#39;s intervisibility sum while meeting speed constraints by avoiding slow terrain. The Cost Generator  100  begins at step  1600  by retrieving the threshold traversal speed from the Capabilities Database  106 . At step  1602 , the Cost Generator  100  retrieves the cost grid from the Map Database  110 . At step  1604 , the Cost Generator  100  retrieves the graph from the Map Database  110 . At step  1606 , the Cost Generator  100  retrieves the visibility matrix from the Intervisibility Database  108 . At step  1608 , the Cost Generator  100  sets the current minimum edge cost C to the maximum viewshed cardinality indicated by the visibility matrix. At step  1610 , the Cost Generator  100  obtains the list of nodes from the graph. At step  1612 , the Cost Generator  100  determines if there are more nodes to evaluate. If not, at step  1628 , the Cost Generator  100  stores the now-populated cost grid back to the Map Database  110 . If so, at step  1614 , the Cost Generator  100  gets the current node and proceeds to step  1616 . 
         [0103]    At step  1616 , the Cost Generator  100  obtains the node&#39;s speed by passing the node to the Speed Analyzer  212 . At step  1618 , the Cost Generator  100  determines whether the node&#39;s speed is below the threshold traversal speed. If so, at step  1620 , the Cost Generator  100  sets the current node cost N in the corresponding cell in the cost grid to infinity to indicate the node is impassable and proceeds to step  1622 . If not, at step  1624 , the Cost Generator  100  obtains the current node&#39;s viewshed V by passing the node to the Intervisibility Analyzer  216  and proceeds to step  1626 . At step  1626 , the Cost Generator  100  sets the current node cost N in the corresponding cell in the cost grid to the cardinality of V, |V|. At step  1622 , the Cost Generator  100  updates C to the smaller of C and the current node cost N, as indicated by the following formula: 
         [0000]        C =Minimum( N,C ) 
         [0104]    After step  1626 , the Cost Generator  100  continues evaluating nodes by proceeding to step  1612 . At step  1628 , the Cost Generator  100  stores the cost grid. At step  1630 , the Cost Generator  100  logs the current minimum cost C. Upon termination after step  1630 , the Cost Generator  100  will have set the cost of each node&#39;s corresponding cell in the cost grid in the Map Database  110 . 
         [0105]    Another exemplary embodiment for generating tactical routes is one that maximizes the path&#39;s intervisibility sum while meeting speed constraints by avoiding slow terrain. By maximizing the path&#39;s intervisibility sum, travelers are exposed to a maximal amount of previously-unexposed terrain after beginning travel, thereby allowing travelers to exert a surveillance or weapons capability advantage (e.g., range) over enemies in unexposed terrain. By avoiding slow terrain below an arbitrary threshold, travelers can travel at or above the speed threshold at every node on the path, rendering it difficult for enemies to engage the traveler in combat. 
         [0106]    The Cost Generator  100  of this exemplary embodiment that maximizes the path&#39;s intervisibility sum differs from that of the exemplary embodiment that minimizes the path&#39;s intervisibility sum in two steps; first, at step  1608 , the Cost Generator  100  sets the current minimum edge cost C to I. Second, at step  1626 , the Cost Generator  100  sets the current node cost N in the corresponding cell in the cost grid to the inverse of the cardinality of V, NI, using the following formula: 
         [0000]        N= 1/| V|   
         [0107]    Other steps of the Cost Generator  100  of this exemplary embodiment that maximizes the path&#39;s intervisibility sum remain the same as those described in the exemplary embodiment that minimizes the path&#39;s intervisibility sum. 
         [0108]    The above-described devices and subsystems of the exemplary embodiments of  FIGS. 1-16  can include, for example, any suitable servers, workstations, PCs, laptop computers, PDAs, Internet appliances, handheld devices, cellular telephones, wireless devices, other electronic devices, and the like, capable of performing the processes of the exemplary embodiments of  FIGS. 1-16 . The devices and subsystems of the exemplary embodiments of  FIGS. 1-16  can communicate with each other using any suitable protocol and can be implemented using one or more programmed computer systems or devices. 
         [0109]    One or more interface mechanisms can be used with the exemplary embodiments of  FIGS. 1-16 , including, for example, Internet access, telecommunications in any suitable form (e.g., voice, modem, and the like), wireless communications media, and the like. For example, employed communications networks or links can include one or more wireless communications networks, cellular communications networks, cable communications networks, satellite communications networks, G3 communications networks, Public Switched Telephone Network (PSTNs), Packet Data Networks (PDNs), the Internet, intranets, WiMax Networks, a combination thereof, and the like. 
         [0110]    It is to be understood that the devices and subsystems of the exemplary embodiments of  FIGS. 1-16  are for exemplary purposes, as many variations of the specific hardware and/or software used to implement the exemplary embodiments are possible, as will be appreciated by those skilled in the relevant art(s). For example, the functionality of one or more of the devices and subsystems of the exemplary embodiments of  FIGS. 1-16  can be implemented via one or more programmed computer systems or devices. 
         [0111]    To implement such variations as well as other variations, a single computer system can be programmed to perform the special purpose functions of one or more of the devices and subsystems of the exemplary embodiments of  FIGS. 1-16 . On the other hand, two or more programmed computer systems or devices can be substituted for any one of the devices and subsystems of the exemplary embodiments of  FIGS. 1-16 . Accordingly, principles and advantages of distributed processing, such as redundancy, replication, and the like, also can be implemented, as desired, to increase the robustness and performance the devices and subsystems of the exemplary embodiments of  FIGS. 1-16 . 
         [0112]    The devices and subsystems of the exemplary embodiments of  FIGS. 1-16  can store information relating to various processes described herein. This information can be stored in one or more memories, such as a hard disk, optical disk, magneto-optical disk, RAM, and the like, of the devices and subsystems of the exemplary embodiments of  FIGS. 1-16 . One or more databases of the devices and subsystems of the exemplary embodiments of  FIGS. 1-16  can store the information used to implement the exemplary embodiments of the present invention. The databases can be organized using data structures (e.g., records, tables, arrays, fields, graphs, trees, lists, and the like) included in one or more memories or storage devices listed herein. The processes described with respect to the exemplary embodiments of  FIGS. 1-16  can include appropriate data structures for storing data collected and/or generated by the processes of the devices and subsystems of the exemplary embodiments of  FIGS. 1-16  in one or more databases thereof. 
         [0113]    All or a portion of the devices and subsystems of the exemplary embodiments of  FIGS. 1-16  can be conveniently implemented using one or more general purpose computer systems, microprocessors, digital signal processors, micro-controllers, and the like, programmed according to the teachings of the exemplary embodiments of the present invention, as will be appreciated by those skilled in the computer and software arts. Appropriate software can be readily prepared by programmers of ordinary skill based on the teachings of the exemplary embodiments, as will be appreciated by those skilled in the software art. In addition, the devices and subsystems of the exemplary embodiments of  FIGS. 1-16  can be implemented by the preparation of application-specific integrated circuits or by interconnecting an appropriate network of conventional component circuits, as will be appreciated by those skilled in the electrical art(s). Thus, the exemplary embodiments are not limited to any specific combination of hardware circuitry and/or software. 
         [0114]    Stored on any one or on a combination of computer readable media, the exemplary embodiments of the present invention can include software for controlling the devices and subsystems of the exemplary embodiments of  FIGS. 1-16 , for driving the devices and subsystems of the exemplary embodiments of  FIGS. 1-16 , for enabling the devices and subsystems of the exemplary embodiments of  FIGS. 1-16  to interact with a human user, and the like. Such software can include, but is not limited to, device drivers, firmware, operating systems, development tools, applications software, and the like. Such computer readable media further can include the computer program product of an embodiment of the present invention for performing all or a portion (if processing is distributed) of the processing performed in implementing the exemplary embodiments of  FIGS. 1-16 . Computer code devices of the exemplary embodiments of the present invention can include any suitable interpretable or executable code mechanism, including but not limited to scripts, interpretable programs, dynamic link libraries (DLLs), Java classes and applets, complete executable programs, Common Object Request Broker Architecture (CORBA) objects, and the like. Moreover, parts of the processing of the exemplary embodiments of the present invention can be distributed for better performance, reliability, cost, and the like. 
         [0115]    As stated above, the devices and subsystems of the exemplary embodiments of  FIGS. 1-16  can include computer readable medium or memories for holding instructions programmed according to the teachings of the present invention and for holding data structures, tables, records, and/or other data described herein. Computer readable medium can include any suitable medium that participates in providing instructions to a processor for execution. Such a medium can take many forms, including but not limited to, non-volatile media, volatile media, transmission media, and the like. Non-volatile media can include, for example, optical or magnetic disks, magneto-optical disks, and the like. Volatile media can include dynamic memories, and the like. Transmission media can include coaxial cables, copper wire, fiber optics, and the like. Transmission media also can take the form of acoustic, optical, electromagnetic waves, and the like, such as those generated during radio frequency (RF) communications, infrared (IR) data communications, and the like. Common forms of computer-readable media can include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, any other suitable magnetic medium, a CD-ROM, CDRW, DVD. any other suitable optical medium, punch cards, paper tape, optical mark sheets, any other suitable physical medium with patterns of holes or other optically recognizable indicia, a RAM, a PROM, an EPROM, a FLASH-EPROM, any other suitable memory chip or cartridge, a carrier wave, or any other suitable medium from which a computer can read. 
         [0116]    Although the exemplary embodiments are described in terms of military applications, the teachings of the exemplary embodiments can be used with any suitable non-military applications, as will be appreciated by those skilled in the relevant art(s). 
         [0117]    While the present invention have been described in connection with a number of exemplary embodiments and implementations, the present invention is not so limited, but rather covers various modifications and equivalent arrangements, which fall within the purview of the appended claims.