Introduction
Any military professional will attest that understanding terrain is fundamental to planning and conducting operations. Our reliance on maps and other representations of terrain is evident in military products and processes at the tactical, operational, and strategic levels of planning. Today, the relatively widespread availability of digital terrain data (DTD) has enabled high-tech adaptations of map and imagery data for uses such as simulation, command and control (C2), and reconnaissance. However, we have yet to harness the full potential of this resource.
To support many planning tasks, we need to go beyond mapping and visualization to produce task-specific interpretations of terrain data. Geographic information systems (GISs) provide an excellent foundation for producing such visualizations, but these are not sufficient to produce the kinds of terrain analysis needed by military analysts and commanders. We recently demonstrated that artificial intelligence (Al) can help bridge this gap by automatically producing military interpretations of terrain data for trafficability analysis. We believe that the qualitative spatial reasoning techniques used in that application can be extended to address a wide range of military terrain analysis tasks and benefit current and emerging applications such as C2 tools and simulations.

The Problem
Military planners have long understood the need for special-purpose interpretations of map data. Let's consider the overlays produced to describe the environment for the intelligence preparation of the battlefield (IPB). To make effective military use of a traditional map, military intelligence analysts produce overlays depicting military terrain trafficability, potential engagement areas, and key terrain, just to name a few.
For complex tasks such as military planning and operations, these overlays help identify and communicate what is critically important about that terrain (e.g., trafficability for military vehicles) while ignoring unnecessary details. These simplifications enable us to optimize use of maps by describing the environment according to useful distinctions.
Today, many military tasks have been automated and even transformed by modern technology. Digital terrain data have made it possible to conduct computer-based military planning and operations using the digital equivalent of maps. Currently, however, we have not yet realized the digital equivalent of the high-level interpretations of the digital maps-the equivalent of the doctrinal overlays produced in IPB. GIS software allows for storing and manipulating terrain data in general ways, but cannot perform military terrain analysis. As a result, current C2 tools cannot demonstrate the sophisticated understanding of terrain needed by military planners the way an intelligence analyst does using an overlay.

Qualitative Reasoning
There is a wide range of C2 applications, simulation environments, and planning tools being developed and fielded that use digital terrain data for computer-based map displays. All of these applications support some form of reasoning about the impact of that terrain on military operations. Typical determinations include path planning, rates of movement, visibility and fields of fire, and site selection. The common approach is to access the feature coding of GIS primitives (i.e., polygons, arcs, or rasters) in the DTD through a GIS and use the GIS-provided facilities to support the desired determinations. This is a sensible place to start because these systems provide powerful and useful facilities for digital mapping, perform complex transformations of this data, and solve common geospatial problems. However, these GIS computations are quantitative, relying on visualization tools and extensive user interactions to provide the qualitative insights needed in military applications. In contrast, most human reasoning about geographic space appears to reflect a qualitative interpretation of that space.
While valuable contributions will come from many areas of Al, we believe that qualitative reasoning in particular has much to offer. Qualitative representations can depict terrain data that are encoded as many continuous properties into discrete, conceptually meaningful units.
Qualitative spatial representations carve space into regions based on a combination of physical constraints and task-specific constraints. Relative to military trafficability, for example, identifying unrestricted versus restricted areas is useful because of the different effects that such terrain has on the movements of various military units.
Generally, it rarely matters why such areas are restricted or severely restricted. Indeed, such areas may be so designated because they represent an aggregation of smaller areas where trafficability factors result from various terrain features such as vegetation, slope, hydrography, and surface roughness. This corresponds to what a human analyst does when he or she produces a combined obstacle overlay (figure on Page 33).
These qualitative spatial representations describe space according to parameters directly relevant to the required task. These representations often need to be firmly rooted in a quantitative, diagrammatic representation for a variety of technical reasons. Digital terrain data provide this diagrammatic description in a way that is convenient for reasoning systems to access and manipulate. We use this quantitative information (e.g., feature coding of terrain features or specific coordinates of a unit) in qualitative spatial reasoning. For instance, using qualitative spatial descriptions for trafficability helps determine routes in a general way and helps calculate time-distance estimates about travel over those routes (e.g., can they get there in time?).
Using qualitative descriptions also allows computers to perform more human-like reasoning and explanations. In other words, by identifying and using these conceptually meaningful units, computers can become intelligent and articulate, describing, for example, how restricted and severely restricted areas of terrain contribute to the identification of avenues of approach, or potential battle positions.

Proof Of Concept
In studies at Northwestern University, we applied these techniques to trafficability analysis problems as part of the High Performance Knowledge Bases Program. This research, supported by the Defense Advanced Research Projects Agency, shows how GISs can be used to support qualitative spatial reasoning. We automatically generated combined obstacle overlays (COOs) and complex factor overlays (CFOs) to answer terrain analysis and trafficability questions related to planning and conducting military operations. The GIS data represented the terrain in the Straits of Hormuz region. The GIS coding of this terrain data described vegetation, hydrology, slope, and road networks. This array of coverages and the terrain in the area provided an opportunity to test these techniques, and the results are promising.
The CFOs and COOs were used by military personnel to judge correctness and plausibility of trafficability results consistent with U.S. Army practice. In all tested areas, correct CFOs and COOs were created, and trafficability questions (e.g., maximum speed in particular regions) produced correct answers.
Generating CFOs and COOs presented the opportunity to produce qualitative spatial descriptions that correspond to authentic descriptions produced by military analysts. It also allowed modeling of the well-established terrain analysis practices that use those descriptions. A variety of trafficability and path-finding queries, producing authentic results and compelling explanations grounded in qualitative reasoning, were also supported. This demonstrated that qualitative reasoning enables computer systems to produce relevant, high-level descriptions of terrain that support automated reasoning and correspond closely to human understanding of terrain.

Application
Automating the production of COOs and CFOs suggests that many such intelligence tasks that are still done manually can be similarly produced. While military planners currently spend hours or days producing a variety of overlays and estimates for an area of operations, this technique could allow the same descriptions to be produced immediately, on demand. Qualitative descriptions can also provide richer representations of the environment to support higher-fidelity planning and simulations.
Consider a classic military strategy problem in simulation: massed fires. If you assign three units to attack a localized enemy, simulated units will choose paths to get to that enemy and then attack it. Such simulations are susceptible to the problem of naive pathfinding. Suppose the quickest path to the enemy involves a tightly constrained mobility corridor, forcing your units to travel it one at a time (units in column). The enemy, who would have been overwhelmed had your forces converged all at once, can then destroy each of them in turn as they enter the clearing.
Good military planners solve this problem differently. They specify paths that the units will take and specify synchronization constraints (i.e., "using these axes of advance, attack at 0400"). Good communication is essential to good force coordination.

Understanding the impact of terrain on unit movements (provided by overlays in current military planning) is essential in expediting these determinations and enabling efficient communication. We believe computers can use this type of qualitative reasoning to achieve the same effectiveness in communicating between tools and humans, as well as between automated reasoning processes. Providing this type of interaction between a human planner and our map-based tools could provide better support to planning, simulation, and C2.
Conclusion
As computer-based planning, simulation, and C2 mature, sophisticated and natural representations of space will be necessary to make optimum use of terrain descriptions. The research presented in this article represents a promising first step toward the sort of intelligent applications that could be part of future command-post software.