The results presented in this paper arose from the AirLand Battle Management - Advanced Technology Demonstration project. Although the focus of that project was on demonstrating a system that functioned as a planning aid for use by a division-level commander and staff, some components of the system are relevant to current efforts in simulation to have representations of "intelligent" computer generated forces. This paper discusses one such component used to perform terrain reasoning. Any simulation that models a division-level command post (CP)--whether it be an aggregate level or entity level simulation--can benefit by modeling the planning process that goes on inside the CP. A very important aspect of this planning process is the intelligence preparation of the battlefield (IPB). The discussion in this paper focuses on a terrain representation that facilitates the automation of a portion of the IPB process.
Section 2.0 describes the topological foundation of the terrain representation. Section 3.0 describes the terrain representation itself and provides a small sample of algorithms written that use the representation. The next section provides some background on this work.
A number of Department of Defense research projects have developed command and control decision aid application prototypes based on advanced computing and artificial intelligence (AI) technologies. Some projects, such as the AirLand Battle Management (ALBM) Program--funded by the Defense Advanced Research Projects Agency and the U.S. Army--required specialized hardware platforms (e.g., Lisp machines). The ALBM Advanced Technology Demonstration (ATD) project was a follow-on to the original ALBM project. Its objective was to integrate and extend existing technological developments to demonstrate a limited capability for AI-based command and control decision aids running on Army Common Hardware/Software. The Army's ALBM-ATD developer was the Communications and Electronics Command (CECOM) and the Army's user representative was the Combined Arms Command (CAC). Lockheed Martin - Austin Operations was the prime contractor. The system that was developed during the ALBM-ATD project is called METT_T.
METT_T (the Army acronym for Mission, Enemy, Terrain, Troops, and Time Available) is the ALBM-ATD prototype system for battlefield situation assessment. It is used by the G2 to project the enemy situation and courses of action; and by the G3 to project friendly capabilities and to assess a unit's ability to accomplish its assigned mission. METT_T consists of three subsystems:
The subject of this paper is one of the terrain representations used by the BA subsystem.
One of the goals of the BA subsystem was to act as a decision aid to assist soldiers in a division-level main CP in performing "terrain appreciation" with respect to combat mission planning. One of the BA components that supports this goal is called "AA Generate". AA Generate takes input specifications from the user--at a minimum, start point, end point, and echelon--and searches a specialized terrain database (a "cognitive map") for an AA or mobility corridor (MC) that matches the specifications and provides a minimum transit time from start to end for a force of the given echelon size moving cross-country. Multiple candidate AAs can be generated. The completed AAs or MCs are areas of terrain that can be then compared with respect to various attributes, such as OCOKA (Observation and fields of fire, Cover and concealment, Obstacles, Key terrain, and Avenues of approach). The Terrain Evaluation Module (TEM) geographic information system (GIS) is used within METT_T to perform the comparison.
This section describes a topological polygonal network structure, henceforth referred to simply as a "topology". The particular topology described here is made up of three kinds of objects: nodes, edges, and faces. Roughly, these may be thought of as points, lines, and areas, respectively, with some restrictions. Nodes are used to connect edges, at their ends. Edges, which cannot overlap, bound faces. Faces also cannot overlap and are adjacent to other faces. The topological structure described here conforms to a "level 3 topology" as defined by the "Interim Military Standard Vector Product Format" (see [Ref #9]). In mathematical terminology (from homology theory) nodes, edges, and faces are 0-cells, 1-cells, and 2-cells, respectively. This theory is helpful and its utilization is described in Section 2.4.
For an overview of topological cartographic data structures see [Ref #2], [Ref #3], and [Ref #7]. A detailed examination of the topic can be found in [Ref #4]. A representation very close to the one described in this section is described in [Ref #1].
Figure 1 shows an example topology. All nodes (n), edges (e), and faces (f) are labelled. The attributes of three selected objects are shown in rounded boxes on the right side of the figure.
More will be explained about this figure in the following subsections. For now, though, note that the topology is "connected". That is, there are no "islands". For example, in Figure 1 we would have an island of objects within face, f2, if edge, e6, were removed. Although a topological model can incorporate the concept of islands, for greater tractability, the topology described here assumes connectedness as a property.
Figure 2 shows the topological object model using Object Modeling Technique (OMT) notation [Ref #6].
For any given map described in topological form, a top-level "container object" is needed to hold the nodes, edges, and faces. This object is referred to as a "topology object". In METT_T it contains three lists as shown below:
TOPOLOGY: NDS.....List of nodes EGS.....List of edges FCS.....List of faces
The next three subsections describe the three basic topological objects in more detail.
The attributes of a node are defined as follows:
NODE: ID......Unique identifier COORD...Coordinate for this node EGS.....List of IDs of edges that connect to this node BND-FCS.List of IDs of faces that bound this node (not discussed in this paper) PROPS...List of properties of this node (presently not used)A node has a coordinate and points to the edges that connect to it. The pointing is done via a list of edge IDs (EGS). The edge IDs in the list are sorted in counterclockwise, decreasing azimuthal order, starting with the edge immediately to the left of 12 o'clock. Each edge's azimuth is measured from the node itself to the element of the edge's chain that is immediately adjacent to the node (see the description of edge chains in Section 2.2). For example, note the ordering of the four edges in the node object depicted in Figure 1. By ordering edges in this fashion we facilitate the ability to write a straight forward algorithm for "walking around a face" -- which is a necessity during the construction of a topology.
In METT_T nodes actually have more attributes, but for the most part they are not relevant to the discussion in this paper so they have been left out. The same is true of the other topological objects. One attribute that cannot be left out, though, is the "properties" attribute (PROPS). It is common to all METT_T topological objects and is a useful artifact leftover from the METT_T development phase. It is used as a place to dump information into, which helps avoid having to redefine objects, which in turn requires conversion of an entire topology to the new definition. The PROPS attribute is not used for nodes at this time, but does get used in edges and faces.
Additionally, all topological objects described here have IDs (i.e., unique identifiers). Pointing is done using IDs rather than actual pointers to memory addresses. The reason for this is that, originally, IDs made it easier to debug and save objects to a file. They do slow things down during runtime, however. With some additional work one can set things up to use pointers at runtime and IDs during loading and saving operations; or maybe better yet, build all this on top of an object-oriented database.
The attributes of an edge are defined as follows:
EDGE: ID........Unique identifier START-ND..ID of start node (one end of edge) END-ND....ID of end node (other end of edge) LEFT-FC...ID of face on edge's left side RIGHT-FC..ID of face on edge's right side CHAIN.....List of coordinates that defines the "shape" of the edge PROPS.....List of properties of this edge (e.g., Length, BBox)
An edge points to the nodes that bound its ends: start node (START-ND) and end node (END-ND). An edge also points to the faces on either side of it: left face (LEFT-FC) and right face (RIGHT-FC). Having start and end nodes gives the edge a direction. The left face of an edge is the face that lies on its left side as one travels from the start node to the end node. The other face, of course, is the right face. For an example, look at the edge object described in Figure 1.
Edges also have a chain -- a list of coordinates defining the shape of the edge between its two end nodes. The entire coordinate list for an edge is obtained by appending the start node's coordinate onto the front of the chain and the end node's coordinate onto the end of the chain. If an edge is a straight line between the start and end nodes, then the chain is an empty list. Edges cannot overlap. A chain cannot cross itself or cross any other edge's chain. If two chains must cross, then their edges must each be divided into two new edges with a new node at the point of intersection.
Properties that are stored in an edge's PROPS attribute include the length of the edge and the bounding box (BBOX) of the edge (i.e., upper left and lower right coordinates).
The attributes of a face object are as follows:
FACE: ID......Unique identifier O-RING..List of IDs of edges (outer ring, or boundary) O-DIR...List of outer ring edge directions (0's and 1's that correspond one-to-one with edges in O-RING). They determine how to move along the edges in a counterclockwise direction around the face. BND-NDS.List of IDs of nodes that border this face (not discussed in this paper) PROPS...List of properties of this face (e.g., mobility, BBox)
A face points to a list of edges that make up its outer boundary, also known as its outer ring (O-RING). The edges listed in the outer ring are stored in an order that takes one counterclockwise around the face. A list of 0's and 1's, denoting edge directions is stored in the attribute, outer ring directions (O-DIR). These are used to interpret how one should travel down an edge in order to move in a counterclockwise direction: 0 means move from start node to end node; 1 means move from end node to start node. For example, look at face object, f5, in Figure 1. According to f5's outer ring, (e3, e4), and outer ring directions, (1, 0), to move counterclockwise around f5 start with edge e3 and move from end node (n5) to start node (n6) and then move down edge e4 going from start node (n6) to end node (n5).
Finally, note face, f1, in Figure 1. It represents the area "outside" of the topological map represented by this figure.
In 1752 the mathematician Leonhard Euler (1707-1783) discovered the following very simple geometric fact [Ref #5]: If N, E, and F denote the number of nodes, edges, and faces of a simple polyhedron, then
N - E + F = 2 (EQ 1)
This result is about objects that exist in 2-dimensions. About a century later Henri Poincare (1854-1912) extended the result to n-dimensions. The value computed in (EQ 1) is now called the Euler-Poincare characteristic and is sufficient for the discussion here; however, if one wanted to extend the representation discussed here to 3-dimensions (i.e., to include "volumes") then the Euler-Poincare characteristic is 0:
N - E + F - V = 0 (EQ 2)
Within METT_T this principle is used in the print representation of a topology. For example, a topology called the "Fulda Dry Cogmap" (described below in Section 3.1) has the following print representation:
#(TOPOLOGY: E.C.=2; #NDS=3140; #EGS=5060; #FCS=1922)
The Euler-Poincare characteristic is denoted by E.C. in the representation above. If the E.C. is not 2, then something is wrong with the topology. In effect the E.C. is a "checksum" on the topology and is very useful during its construction. The three other items in the print representation above depict the numbers of nodes, edges, and faces, respectively; 10,122 objects in all.
This section describes a representation of terrain that is designed for automated terrain reasoning about the cross-country mobility of ground maneuver combat units. The representation is based on the topological representation presented in Section 2.0 and is referred to within the METT_T system as a "cogmap". A cogmap is used to automatically derive mobility corridors (MC) and avenues of approach (AA). The following excerpt from [Ref #8] defines AAs and MCs:
"Air and ground avenues of approach are routes by which a force may reach key terrain or an objective. Avenues of approach are evaluated in the following terms: (1) Maneuver support potential, (2) Access to key terrain and adjacent avenues of approach, (3) Degree of canalization, (4) Concealment and cover, (5) Observation and fields of fire, (6) Obstacles. Air and ground mobility corridors are subsets of air and ground avenues of approach. Mobility corridors are areas within the avenue of approach which permit movement and maneuver. They permit friendly and enemy forces to advance or withdraw in doctrinal configuration, and to capitalize on the principles of mass, momentum, shock, and speed."
The cogmap representation used in METT_T attempts to explicitly encode information with respect to items (1), (2) (i.e., adjacent AAs), and (3). To a degree it also contains information with respect to item (6). In addition, a cogmap explicitly represents "mobility areas" which may be joined together to create MCs. MCs are then joined to create AAs.
The other items listed in the excerpt are addressed within METT_T by first using a search process in the AA Generate component that operates over a cogmap to find one or more AAs. Then a separate component is used to evaluate and compare them using detailed digital terrain data and the TEM GIS. AAs created manually by the user may also be included in the evaluation and comparison along with the machine generated ones.
The cogmap representation is conceptually quite simple. The following series of steps provides a very simplified description of a cogmap's construction (see Figure 3 for an example depiction of a cogmap):
Creating a cogmap requires a great deal of information about the terrain, weather, and military units being considered. Under the METT_T project a single large cogmap was constructed for the portion of Germany bounded between 51.2 & 52 degrees North and 8 & 10 degrees East (i.e., the "Fulda Dry Cogmap") -- over 10,000 sq. km. Step 1 of the process described above was done using the U.S. Army Corps of Engineers Waterways Experiment Station (WES) AirLand Battle Environment (ALBE) GIS. An ALBE Tactical Decision Aid (TDA) called the "Off-Road Speed Map" was produced, assuming dry weather and tracked armored vehicles. A great deal of additional processing of the TDA was required to get it into its final topological form. The resulting cogmap--mentioned above in Section 2.4--has 3140 nodes, 5060 edges, and 1922 faces. It is stored in a binary format and occupies 768 Kilobytes of disk space. Its size, information content, and ease of use are the reason for the word "efficient" appearing in the title of this paper.
Step 4 in the previous section leaves some ambiguities with respect to minimum gap generation in a cogmap. The process begins by connecting each pair of NO-GO faces with a minimum gap, as long as the gap's line does not intersect any other face. However, since each NO-GO face has many neighbors, minimum gaps may end up intersecting each other. This situation is remedied by the process shown in Figure 4.
This section provides a little flavor of the kind of algorithms used with the cogmap. Using IDs instead of address pointers makes them a bit more complicated than they should be. Nevertheless, they are still quite simple. The primary algorithm illustrated here (Adjacent_Faces) is the one that finds all cogmap faces that are adjacent to a given face. This algorithm is used in the AA Generate component's search process to help generate "successors" in the search space.
First some utility functions need to be described:
Given an edge, a direction, and a topology, the function, Get_Edge_Outer_Face, returns the left face of an edge if the direction is 1, otherwise it returns the right face.
Get_Edge_Outer_Face(EDGE, DIRECTION, TOPOLOGY) if DIRECTION == 1 return Get_Face(Get_Left_Face(EDGE),TOPOLOGY) else return Get_Face(Get_Right_Face(EDGE),TOPOLOGY).
Given a face and topology that it's in, the function, Get_Face_Boundary, returns a list of edges that form the face's boundary.
Get_Face_Boundary(FACE, TOPOLOGY) for each EDGE_ID in Get_Face_O_Ring(FACE) collect Get_Edge(EDGE_ID, TOPOLOGY) return collection.
Given a face and a topology, the function, Adjacent_Faces, returns the list of adjacent faces.
Adjacent_Faces(FACE, TOPOLOGY) for each EDGE in Get_Face_Boundary(FACE, TOPOLOGY) and for each DIRECTION in Get_Face_O_Directions(FACE) collect Get_Edge_Outer_Face(FACE, TOPOLOGY) remove_duplicates in collection return collection.
This paper has presented a description of a terrain representation that has been used to automatically generate avenues of approach and maneuver corridors for military units moving cross-country in deployed formation. The system as it currently exists is by no means perfect, but it is a start.
There are many people at CECOM, CAC, and Lockheed Martin who deserve thanks for supporting this work, so rather than trying to name them all I will simply name the few who lived and breathed this stuff for many months -- my fellow "FOG (Friends Of Geometry) Society" members: Robert Boone, Dan Mullen, Eliot Shindler, Wade Harper, and Rich McDonald. Thanks also go to Paul Birkel at Mitre Corp.