We describe TELLUSPLAN, an intelligent assistant for the problem of bargaining between user goals and system resources in the integration of terrain databases from separate source databases. TELLUSPLAN uses nondeterministic methods from artificial intelligence and a detailed cost model to infer the most reasonable compromise with the user's needs.
Acknowledgements: This work was supported by the Army Artificial Intelligence Center through TRADOC Analysis Command, Monterey.
This paper appeared in the 1998 Command and Control Research and Technology Symposium, Monterey CA, June 1998, 481-486.
Accurate modeling of real-world terrain is important to military planning and resource management. A rapidly increasing number of terrain databases are available, including information about elevation, visual appearance, significant cultural features, and surface covering. Having this information at a fine level of detail is essential to good planning and construction of convincing virtual realities.
Unfortunately, there is not much compatibility between the many available terrain databases. While the Defense Mapping Agency follows standards, many other databases use widely different formats. Data item formats, final formats, directory formats, and data-finding software all differ between terrain-database products. This would not be so bad if modeling and simulation applications could be furnished from a single data source. But this is rarely possible: Broad coverage of the world (like DTED level 1, the Defense Mapping Agency 100-meter elevation database (DMA, 1994)) is generally available only at a coarse resolution. Builders of good simulation and planning systems typically want a considerably finer resolution than this, and are willing to use specialized and ad-hoc databases. This is aided by the fact that areas of the world likely to be of special interest to many analysts already have considerable data for them.
Thus constructing a terrain database for a simulation or planning application usually requires assessing the tradeoffs between several available database sources and actions we can apply to them. One database may have fine resolution but fail to cover all of the region of interest (as with DTED level 2 and Level 3 databases). The missing data could then be interpolated from coarser-resolution databases, but the result will have "seams". Or the user's region might be expanded or contracted for easier handling, to conform to known database partition lines or to make the region square. Or the user's region might be were subdivided into equal-sized regions that could be treated separately using perhaps different data sources. (Hardis and Sureshchandran, 1995) describes a tool providing variety of such actions that a user could exploit; (Polis et al, 1994) describes some more sophisticated actions involving database content analysis. Deciding between these possibilities involves quantitative judgments. The variety and number of the options is quickly becoming bewildering with the increasing number of databases available, particularly for inexperienced system builders. So we have developed an intelligent tool that analyzes and summarizes the options, and presents them in simplified form for user approval.
TELLUSPLAN is an intelligent front-end for the TELLUS system (Baer et al, 1995; Baer, 1995) for building terrain databases. It is written in Quintus Prolog. TELLUSPLAN interacts with the user and obtains from them key information about their needs and wants for an output database. It then calls upon the existing TELLUS interface to handle the more mundane and more mathematical details, and to actually construct the output database. TELLUSPLAN interacts with TELLUS in three ways. First, TELLUSPLAN asks TELLUS about the available data of a particular type for a particular region of the world. This information includes reports of gaps in the data, an important issue with image data such as the Control Image Base (CIB) data. Second, TELLUSPLAN must find out from TELLUS the geographical partitioning of the world that the databases use, since it is generally desirable to exploit this when possible, and it differs considerably between databases. Third, after bargaining has been completed, TELLUSPLAN must send TELLUS a complete specification of what the user wants to do, in terms of the databases desired, regions desired, output resolution and other parameters desired, and operations desired. For this we have extended a script language originally designed as a macro facility for TELLUS. The script language helps ensure a cleaner design and a clear division of labor between TELLUSPLAN and TELLUS.
Input to TELLUSPLAN is deliberately kept simple (see example in Figure 1). The user gives five numeric parameters: latitude and longitude bounds of an (approximately) rectangular box surrounding the region of interest, and the resolution, the distance between successive postings of data in both north-south and east-west directions. We use latitude and longitude because they are the most natural way for users to specify a terrain area, but they have the disadvantage of entailing non-integer proportionality, except at the equator, between north-south and east-west extent when the latitudes and longitudes are integers. The user must then specify the kinds of data desired in the output database; currently we support elevation data, image data, and feature data. Finally, the user must answer certain yes/no questions to guide the general direction of reasoning for TELLUSPLAN to consider. Answers are cached so the same answer can be used in many ways without re-asking the question. Figure 2 shows the script file for the underlying TELLUS system that was generated by the interaction in Figure 1.
TELLUSPLAN uses a heuristic branch-and-bound search to find the best solution to the problem of approximating the user's specifications in a database. Branch-and-bound is used because of the number of qualitatively different "bargaining ploys" or ways to accommodate a user, each with different costs as we shall discuss below; and branch-and-bound automatically checks for multiple routes to a state and saves the cheapest. Nondeterministic specification of these search options helped simplify the design of TELLUSPLAN, since it enabled us to isolate in rules the conceptual ploys used by system designers when bargaining about their needs. Use of branch-and-bound also enabled us to reuse a problem-independent program derived from a program in Chapter 10 of (Rowe, 1988). This program requires declarative specifications for state transitions (successors), costs of successors, search termination conditions, state-pruning conditions, and management of yes/no questions asked the user.
The bargaining ploys include:
1. Selection of a particular database at its own resolution to obtain one of the desired forms of output data (elevation, image, or feature). This requires agreement by the user to change their resolution specification, but has the advantage of avoiding interpolation. (Unfortunately, however, the useful CIB database has a nonstandard resolution of ten meters.)
2. Selection of a particular database, but interpolating it to the user-specified resolution. The quality of the outcome depends on the interpolation.
3. Change of the resolution to a "standard" value, a power of 4 in meters. Many databases have such resolutions, so later interpolation may then be avoidable.
4. Change of the resolution to exactly entail a "standard" value for the dimension (or number of postings in one direction) of the database (or sub-databases, if it has partitioned). We have three standard dimensions: 4096, 1024, and 256. This simplifies the final phases of database construction, but usually entails a nonstandard value for the resolution.
5. Expansion or contraction of a dimension of the region of interest to make it approximately "square" (or have an equal number of postings in the north-south and east-west directions). Doing this can simplify later analysis since most databases store terrain in square areas.
6. Expansion of the region of interest to a natural segmentation for a particular output format. For instance, the STD representation (Baer, 1995) partitions the surface of the earth into regions of 11.25 degrees in latitude and longitude from the equator and the Greenwich Meridian. This can simplify later use of the database, but it may entail dramatic expansion of small regions of interest (as the 1025% expansion proposed in Figure 1).
7. Partition of the region of interest into near-square subregions in a two-dimensional array structure. This is helpful when the user specifies a very large region or a rectangular region not close to a square.
8. Selection of standard values for both the resolution and database dimension (see ploys 3 and 4), the nearest such values to the user specification, expanding or contracting the region of interest as necessary. This has the advantages and disadvantages of both options 3 and 4.
In Figure 1, the best solution found was to increase the resolution from 16 to 28 and to expand slightly the boundaries of the area of interest; this solution used bargaining ploys 1, 5, and 8 above.
A key feature of our approach is the assignment of costs to bargaining ploys. Our experience with neural networks suggested that the form of cost functions did not usually matter much if they were approximately the right shape. So we have opted for relatively simple cost functions not necessarily provably related to human psychology. For instance, if the ratio of the old resolution to the new resolution is R, we assign a cost to changing the resolution of 0.05+(R*(R-1)*(R-1)). This function has a local minimum of 0.05 at R=1 since any interpolation can distort the data, even a small one; it has a local maximum of 0.2481 at R=0.3333, since interpolations to larger resolutions are generally good but still entail some digitization effects; and it increases unboundedly for R>1, since interpolations to finer resolutions are unsatisfactory for the most part, and increasingly unsatisfactory as the resolution gets finer.
Our formula for the cost of changing the dimension of the database is 0.01+((R-1)*(R-1)/R) where $R$ is the ratio of the old dimension to the new. This formula is small near 1 and increases monotonically in both directions to reflect the increasing undesirability of big dimension changes. For expanding the region of interest in one direction we use the cost (1/R)-1, where R is the ratio of the old length to the new length, but for shrinking the region we use (R*R)-1 since that loses data and is more serious. For partitioning, the cost is logarithm of the average of the number of partitions added in the north-south and east-west directions; we use the logarithm because we do not want to unfairly penalize applications involving large regions of interest.
These costs are then summed for all the bargaining ploys used in a sequence of state transitions, but with a user-controllable weighting scheme. The weighting is used to rank the different kinds of costs -- resolution changes, dimension changes, region-boundary changes, and partitioning changes -- relative to one another. The user may set these weights before beginning or may accept defaults. Note that even a single ploy may require the weighted addition more than one cost; for instance, ploy 8 usually requires changing resolution, dimension, and region boundary simultaneously.
Questions are asked the user before proposing ploys. Since the same question may be important in several ploys, caching of answers is important. An interesting issue arises in that a cached answer to a numerically different question may be sufficient to answer a new question. For instance, if the user has agreed that it is acceptable to increase resolution by 20%, there is no need later to ask if it is acceptable to increase resolution by 10%. This also applies to stretching and shrinking the region of interest, changing its dimension, and partitioning the data.
Search terminates when the user has selected all the database sources, has created near-square regions of definition, and has selected an acceptable value for the dimension of the output databases (a "goal" state). The state is presented to the user for final approval. If the user accepts it, the state is passed to the script-generation phase and the script is passed to TELLUS. If the user does not accept it, search is resumed and the next-best goal state is found, and so on. Constructing the script requires confirming some output format choices with the user. Inferences are made from previous decisions to simplify the questioning. For instance, "relief" shading of the output database is preferred to "elevation" shading if the resolution is greater than 16 meters.
W. Baer, et al, Global Terrain Database Design for Realistic Imaging Sensor Simulation. 13th DIS Workshop on Standards for the Interoperability of Distributed Simulations, vol. 1, Orlando, FL, September 1995.
W. Baer, Terrain Data Base Creation System. Technical Report, Nascent Computer System, Carmel Valley, CA, 1995.
Defense Mapping Agency, List of Products.
K. C. Hardis and S. Sureshchandran, Terrain Database Correlation Testing Within Database Generation Systems for DIS. 13th DIS Workshop on Standards for the Interoperability of Distributed Simulations, Orlando, FL, September 1995.
M. F. Polis, S. J. Gifford, and D. M. McKeown, Automating the Construction of Large Scale Virtual Worlds. Proceedings of the 1994 ARPA Image Understanding Workshop, November 1994, Monterey, CA.
N. Rowe, Artificial Intelligence through Prolog. Englewood Cliffs, NJ: Prentice-Hall, 1988.
Give latitude of lower left corner: 35
Give longitude of lower left corner: -122
Give latitude of upper right corner: 36
Give longitude of upper right corner: -121
Give spacing between points in meters: 16
Do you want elevation data? (y/n) y
Do you want image data? (y/n) n
Do you want feature data? (y/n) n
Can I extend the north-south range by 1025%? (y/n) n
Is it ok to partition the region into 2 by 1 subregions? (y/n) y
Can I reduce the north-south range by 19%? (y/n) y
Can I extend the east-west range by 23%? (y/n) y
Can I extend the north-south range by 63%? (y/n) y
Can I reduce the east-west range by 39%? (y/n) n
Can I use the database dted1? (y/n) y
Can I interpolate the database dted1 to resolution 16? (y/n) y
Can I adopt the resolution 100 of the database dted1? (y/n) n
Can I use the database dted2? (y/n) n
Can I use the database dem? (y/n) n
OK to have output dataset(s) as 4096 by 4096? (y/n) y
OK to change resolution to 16? (y/n) y
Can I reduce the north-south range by 41%? (y/n) n
Is it ok to partition the region into 2 by 2 subregions? (y/n) y
Can I reduce the north-south range by 28%? (y/n) n
Can I interpolate the database dted1 to resolution 14? (y/n) n
Can I extend the north-south range by 591%? (y/n) n
Can I interpolate the database dted1 to resolution 28? (y/n) y
Can I interpolate the database dted1 to resolution 23? (y/n) y
17 incompletely examined state(s) and 477 examined state(s)
I find a solution with cost 24.4081:
Vertices in latitude and longitude degrees: [34.9839,36.0161,-122.134,-120.866]
Resolution in meters: 28
Number of separate database creations: [1,1]
Data types: [dted1]
Exception list: []
Is that solution acceptable? (y/n) y
For database dted1 on region [3.498390348390348E+01,3.601609651609652E+01,
-1.221339352394845E+02,-1.208660647605155E+02,], can I use directory /DMA_DATA? (y/n) y
Do you want output format fhl? (y/n) y
Do you want caster storage? (y/n) n
Figure 1: Example interaction with TELLUSPLAN.
#Script file generated by Rowe planner program
source dted1 = /DMA_DATA
format=fhl
storage=blocking
projection=utm
resolution=28
dimension=4096
projection=utm
format=fhl
storage=caster
shading=relief
latitude=34.9839
longitude=-122.134
dataset { name=test }
Figure 2: Script file output of TELLUSPLAN for the interaction in Figure 1.