24.4.1   Intuitive Algorithm Development

In analyzing personnel data, for example, table-based representations are much more natural (and useful) than tree-based data structures. Hierarchical data structures are generally more appropriate for representing the organization of a large company than a spatially organized representation. Raster representations of imagery tend to support more intuitive image processing algorithms than do vector-based representations of point, line, and region boundary-based features.

The development of sophisticated machine-based reasoning benefits from full integration of both the semantic and the spatial data representations, as well as integration among multiple representations of a given data type. For example, a river possesses both semantic attributes (class, nominal width, and flow-rate) and spatial attributes (beginning location, ending location, shape description, and depth profile). At a reasonably low resolution, a river’s shape might be best represented as a lineal feature; at a higher resolution, a region-based representation is likely more appropriate.

24.4.2   Efficient Algorithm Performance

For algorithms that require large supporting databases, data representation form can significantly affect algorithm performance efficiency. For business applications that demand access to massive table-based data sets, the relational data model supports more efficient algorithm performance than a semantic network model. Two-dimensional template matching algorithm efficiency tends to be higher if true 2D (map-like) spatial representations are used rather than vector-based data structures. Multiple level-of-abstraction semantic representations and multiple-resolution spatial representations tend to support more efficient problem solving than do nonhierarchical representations.

24.4.3   Data Representation Accuracy

In general, data representation accuracy must be adequate to support the widest possible range of data fusion applications. For finite resolution spatially organized representations, accuracy depends on the data sampling method. In general, data sampling can be either uniform or nonuniform. Uniformly sampled spatial data are typically maintained as integers, whereas nonuniformly sampled spatial data are typically represented using floating-point numbers. Although the pixel-based representation of a region boundary is an integer-based representation, a vector-based representation of the same boundary maintains the vertices of the piecewise linear approximation of the boundary as a floating-point list. For a given memory size, nonuniformly sampled representations tend to provide higher accuracy than uniformly sampled representations.

24.4.4   Database Performance Efficiency

Algorithm performance efficiency relies on the six key database efficiency classes described in the following paragraphs.

24.4.5   Spatial Data Representation Characteristics

Many spatial data structures and numerous variants exist. The taxonomy depicted in Figure 24.8 provides an organizational structure that is useful for comparing and contrasting spatial data structures. At the highest level of abstraction, sampled representations of 2D space can employ either uniform (regular) or nonuniform (nonregular) decompositions. Uniform decompositions generate data-independent representations, whereas nonuniform decompositions produce data-dependent representations.

With certain exceptions (e.g., fractal-like data), low-resolution representations of spatial features tend to be uniformly distributed and high-resolution representations of spatial data tend to be nonuniformly distributed. Consequently, uniform decompositions tend to be most appropriate for storing relatively low-resolution spatial representations, as well as supporting both data registration and efficient spatial indexing. Conversely, nonuniform decompositions support memory-efficient high-resolution spatial data representations.

Hierarchical decompositions of 2D spatial data support the continuum from highly global to highly local spatial reasoning. Global analysis typically begins with relatively low-resolution data representations and relatively global constraints. The resulting analysis products are then progressively refined through higher-resolution analysis and the application of successively more local constraints. For example, a U.S. Interstate road map provides a low-resolution representation that supports the first stage of a route-planning strategy. Once a coarse resolution plan is established, various state, county, and city maps can be used to refine appropriate portions of the plan to support excursions from the Interstate highway to visit tourist attractions or to find lodging and restaurants. Humans routinely employ such top-down reasoning, permitting relatively global (often near-optimal) solutions to a wide range of complex tasks.

Data decompositions that preserve the inherent 2D character of spatial data are defined to be 2D data structures. 2D data structures provide natural spatial search dimensions, eliminating the need to maintain separate search indices. In addition, such representations preserve Euclidean distance metrics and other spatial relationships. Thus, a raster representation is considered a 2D data structure, whereas tuple-based representations of lines and region boundaries are non-2D data structures.

Explicit data representations literally depict a set of data, whereas implicit data representations maintain information that permits reconstruction of the data set. Thus, a raster representation is an explicit data representation because it explicitly depicts line and region features. A vector representation, which maintains only the endpoint pairs of piecewise continuous lines and region boundaries, is considered an implicit representation. In general, implicit representations tend to be more memory-efficient than explicit representations.

Specific feature spatial representations maintain individual point, line, and region features, and composite feature spatial representations store the presence or absence of multiple features. Specific spatial representations are most effective for performing spatial operations with respect to individual features; composite representations are most effective for representing classes of spatial features.

Areal-based representations maintain a region’s boundary and interior. Nonareal-based representations explicitly store only a region’s boundary. Boolean set operations among 2D spatially organized data sets inherently involve both boundaries and region interiors. As a result, areal-based representations tend to support more efficient set operation generation than nonareal-based representations among all classes of spatial features.

Data that are both regular and hierarchical support efficient tree-oriented spatial search. Regular decompositions utilize a fixed grid size at each decomposition level and provide a fixed resolution relationship between levels, enabling registered data sets to be readily associated at all resolution levels. Registered data representations that are both regular and areal-based support efficient set operations among all classes of 2D spatial features. Because raster representations are both regular and areal-based, set intersection generation requires only simple Boolean AND operations between respective raster cells. Similarly, set union can be computed as the Boolean OR between the respective cells.

Spatial representations that are both regular and 2D preserve spatial adjacency among all classes of spatial features. They employ a data-independent, regular decomposition and, therefore, do not require extensive database rebuilding operations following insertions and deletions. In addition, because no separate spatial index is required, re-indexing operations are unnecessary. Spatially local changes tend to have highly localized effects on the representation; as a result, spatial decompositions that are both regular and 2D are relatively dynamic data structures. Consequently, database maintenance efficiency is generally enhanced by regular 2D spatial representations.

Data fusion involves the composition of both dynamic (sensor data, existing fusion products) and static (tables of equipment, natural and cultural features) data sets; consequently, data fusion algorithm efficiency is enhanced by employing compatible data representation forms for both dynamic and static data. For example, suppose the (static) road network was maintained in a nonregular vector-based representation, whereas the (dynamic) target track file database was maintained in a regular 2D data structure. The disparate nature of the representations would make the fusion of these data sets both cumbersome and inefficient. Thus, maintaining static and dynamic information with identical spatial data structures potentially enhances both database association efficiency and maintenance efficiency.

Spatial representations that are explicit, regular, areal, and 2D support efficient set operation generation, offer natural search dimensions for fully registered spatial data, and represent relatively dynamic data structures. Because they possess key characteristics of analog 2D spatial representations (e.g., paper maps and images), the representations are defined to be true 2D spatial representations. Spatial representations possessing one or more of the following properties violate the requirements of true 2D spatial representations:

• Spatial data is not stored along 2D search dimensions (i.e., spatial data stored as list or table-based representations).

• Region representations are nonareal-based (i.e., bounding polygons).

• Nonregular decompositions are employed (e.g., vector representations and R-trees).

True 2D spatial representations tend to support both intuitive algorithm development and efficient spatial reasoning. Such representations preserve key 2D spatial relationships, thereby supporting highly intuitive spatial search operations (e.g., northwest of point A, beyond the city limits, or inside a staging area). Because grid-based representations store both the boundary and the interior of a region, intersection and union operations among such data can be generated using straightforward cell-by-cell operations. The associated computational requirements scale linearly with data set size independent of the complexity of the region data sets (e.g., embedded holes or multiple disjoint regions). Conversely, set operation generation among regions based on non-true-2D spatial representations tend to require combinatorial computational requirements.

Computational geometry approaches to set intersection generation require the determination of all line segment intersection points; therefore, computational complexity is of the order m × n, where m and n are the number of vertices associated with the two polygons. When one or both regions contain embedded holes, dramatic increases in computational complexity can result. For analysis and fusion algorithms that rely on set intersections among large complex regions, algorithm performance can be adversely impacted. Although the use of bounding rectangles (bounding boxes) can significantly enhance search and problem-solving efficiency for vector-represented spatial features, they provide limited benefit for multiple-connected regions, extended lineal features (e.g., roads, rivers, and topographic contour lines), and directional and proximity-based searches.

Specific spatial representations that are explicit, regular, areal, 2D, and hierarchical (or hierarchical true 2D) support highly efficient top-down spatial search and top-down areal-based set operations among specific spatial features. With a quadtree-based region representation, for example, set intersection can be performed using an efficient top-down, multiple-resolution process that capitalizes on two key characteristics of Boolean set operations. First, the intersection product is a proper subset of the smallest region being intersected. Second, the intersection product is both commutative and associative and, therefore, independent of the order in which the regions are composed. Thus, rather than exhaustively ANDing all nodes in all regions, intersection generation can be reformulated as a search problem where the smallest region is selected as a variable resolution spatial search window for interrogating the representation of the next larger region.¹ Nodes in the second smallest region that are determined to be within this search window are known to be in the intersection product. Consequently, the balance of the nodes in the larger region need not be tested.

If three or more regions are intersected, the product that results from the previous intersection product becomes the search window for interrogating the next larger region. Consequently, whereas the computational complexity of polygon intersection is a function of the product of the number of vertices in each polygon, the computational complexity for region intersection using a regular grid-based representation is related to the number of tuples that occur within cells of the physically smallest region. Composite spatial representations that are explicit, regular, areal, 2D, and hierarchical support efficient top-down spatial search among classes of spatial features.

Based on the relationships between spatial data decomposition classes and key database efficiency classes, a number of generalizations can be formulated:

• Hierarchical, true 2D spatial representations support the development of highly intuitive algorithms.

• For tasks that require relatively low-resolution spatial reasoning, algorithm efficiency is enhanced by hierarchical, true 2D spatial representations.

• Implicit, nonregular spatial representations support representation accuracy.

• Specific spatial representations are most appropriate for reasoning about specific spatial features; conversely, composite spatial representations are preferable for reasoning about classes of spatial features. For example, a true 2D composite road network representation would support more efficient determination of the closest road to a given point in space than a representation maintaining individual named roads. With the latter representation, a sizable portion of the road database would have to be interrogated.

• Finite resolution data decompositions that are implicit, nonregular, nonhierarchical, nonareal, and non-2D tend to be highly storage-efficient.

• Spatial indexing efficiency is enhanced by hierarchical, true 2D representations that support natural, top-down search dimensions.

• Spatially local changes require only relatively local changes to the underlying representation; therefore, database maintenance efficiency is enhanced by regular, dynamic, 2D spatial representations.

• For individual spatial features, database search efficiency is enhanced by spatial representations that are specific, hierarchical, and true 2D, and that support distributed search.

• Search efficiency for classes of spatial features is enhanced by composite hierarchical spatial feature representations.

• True 2D spatial representations preserve spatial relationships among data sets; therefore, for individual spatial features, database association efficiency is enhanced by hierarchical true 2D spatial representations of specific spatial features. For classes of spatial features, association efficiency is enhanced by hierarchical, true 2D composite feature representations.

• For specific spatial features, complex query efficiency is enhanced by hierarchical, true 2D representations of individual features; for classes of spatial features, complex query efficiency is enhanced by hierarchical, composite, true 2D spatial representations.

• Finally, database implementation efficiency is enhanced by data structures that support the distribution of data, processing, and control.

These general observations are summarized in Table 24.1.

24.4.6   Database Design Tradeoffs

Object-oriented reasoning potentially supports the construction of robust, context-sensitive fusion algorithms, enabling data fusion automation to benefit from the development of an effective OODBMS. This section explores design tradeoffs for an object-oriented database that seek to achieve an effective compromise among the algorithm support and database efficiency issues listed in Table 24.1. As previously discussed, the principal database design requirement is support for dynamic, hierarchical spatial reasoning and dynamic, hierarchical semantic reasoning. Consequently, an optimal database must provide data structures that facilitate storage and access to both temporally and hierarchically organized spatial and nonspatial information.

Nonspatial (or semantic) declarative knowledge can be represented as n-tuples, arrays, tables, transfer functions, frames, trees, and graphs. Modern semantic object databases provide effective support to complex, multiple level-of-abstraction problems that (1) possess extensive parent–child relationships, (2) benefit from problem decomposition, or (3) demand global solutions. Because object-oriented representations permit the use of very general internal data structures, and the associated reasoning paradigm fully embraces hierarchical representations at the semantic object level, conventional object databases intrinsically support hierarchical semantic reasoning. Semantic objects can be considered relatively dynamic data structures because temporal changes associated with a specific object tend to affect only that object or closely related objects.

The character and capabilities of a spatial object database are analogous to those of a semantic object database. A spatial object database must support top-down, multiple level-of-abstraction (i.e., multiple resolution) reasoning with respect to classes of spatial objects, as well as permit efficient reasoning with specific spatial objects. Just as the semantic object paradigm requires an explicitly represented semantic object hierarchy, a spatial object database requires an equivalent spatial object hierarchy. Finally, just as specific entities in conventional semantic object databases possess individual semantic object representations, specific spatial objects require individual spatial object representations.

24.5.1   Low-Resolution Spatial Representation

As summarized in Table 24.2, an effective low-resolution spatial representation must possess 10 key properties. With the exception of the composite feature representation property, the low-resolution spatial representation requirements are identical to those of the object representation of 2D space. Whereas a composite-feature-based representation supports efficient spatial search with respect to classes of spatial features, a specific feature-based representation supports effective search and manipulation of specific point, line, and region features. A regular region quadtree possesses all of the properties presented in Table 24.2, column 3.

24.5.2   High-Resolution Spatial Representation

An effective high-resolution spatial representation must possess the 10 properties indicated in the last column of Table 24.2. Vector-based spatial representations clearly meet the first four criteria. Because they use nonhierarchical representations of specific features and employ implicit piecewise linear representations of lines and region boundaries, vector representations also satisfy properties 5–7. Changes to a feature require a modification of the property list of a single feature; therefore, vector representations tend to be relatively dynamic data structures. A representation of individual features is self-contained, so vector representations can be processed in a highly distributed manner. Finally, vector-based representations inherently provide high precision. Thus, vector-based representations satisfy all of the requirements of the high-resolution spatial representation.

24.5.3   Hybrid Spatial Feature Representation

Traditionally, spatial database design has involved the selection of either a single spatial data structure or two or more alternative, but substantially independent, data structures (e.g., vector and quadtree). Because of the additional degrees of freedom it adds to the design process, the use of a hybrid spatial representation offers the potential for achieving a near-optimal compromise across the spectrum of design requirements. Perhaps the most straightforward design approach for such a hybrid data structure is to directly integrate a multiple-resolution, low-resolution spatial representation and a memory-efficient, high-resolution spatial representation.

As indicated in Figure 24.9, the quadtree data structure can form the basis of an effective hybrid data structure, serving the role of both a low-resolution spatial data representation and an efficient spatial index into high-accuracy vector representations of point, line, and region boundaries. Table 24.3 offers a coarse-grain evaluation of the effectiveness of the vector, raster, pixel boundary, region quadtree, and the recommended hybrid spatial representation based on the database design criteria. Table 24.4 summarizes the key characteristics of the recommended spatial object representation and demonstrates that it addresses the full spectrum of spatial data design issues.

24.7.1   Problem-Solving Approach

This section outlines a hierarchical path-planning algorithm that seeks to develop one or more routes between two selected locations for a wheeled military vehicle capable of both on-road and off-road movement. Rather than seeking a mathematically optimal solution, we strive for a near-optimal global solution by emulating a human-oriented approach to path selection and evaluation.

In general, path selection is potentially sensitive to a wide range of geographical features (i.e., terrain, elevation changes, soil type, surface roughness, and vegetation), environmental features (i.e., temperature, time of day, precipitation rate, visibility, snow depth, and wind speed), and cultural features (i.e., roads, bridges, the location of supply caches, and cities). Ordering the applicable domain constraints from the most to the least significant effectively treats path development as a top-down, constraint-satisfaction task.

In general, achieving high quality global solutions requires that global constraints be applied before more local constraints. Thus, in stage 1 (the highest level of abstraction), path development focuses on route development, considering only extended barriers to ground travel. Extended barriers are those cultural and man-made features that cannot be readily circumnavigated. As a natural consequence, they tend to have a more profound impact on route selection than smaller-scale features. Examples of extended features include rivers, canyons, neutral zones, ridges, and the Great Wall in China. Thus, in terms of the supporting database, first-stage analysis involves searching for extended barriers that lie between the path’s start and goal state.

If an extended barrier is discovered, candidate barrier-crossing locations (e.g., bridges or fording locations for a river or passes for a mountain range) must be sought. One or more of these barrier-crossing sites must be selected as candidate high-level path subgoals. As with all stages of the analysis, an evaluation metric is required to either prune or rank candidate subgoals. For example, the selected metric might retain the n closest bridges possessing adequate weight-carrying capacity. For each subgoal that satisfies the selection metric, the high-level barrier-crossing strategy is reapplied, searching for extended barriers and locating candidate barrier-crossing options until the final goal state is reached. The product of stage 1 analysis is a set of coarse resolution candidate paths represented as a set of subgoals that satisfy the high-level path evaluation metrics and global domain constraints.

Because the route is planned for a wheeled vehicle, the existing road network has the next most significant impact on route selection. Thus, in stage 2, road connectivity is established between all subgoal pairs identified in stage 1. For example, the shortest road path or the shortest m road paths are generated for those subgoals discovered to be on or near a road. When the subgoal is not near a road or when path evaluation indicates that all candidate paths provide only low-confidence solutions, overland travel between the subgoals would be indicated. Upon completion of stage 2 analysis, the coarse resolution path sets that have been developed during stage 1 will be refined with the appropriate road-following segments.

In stage 3, overland paths are developed between all subgoal pairs not already linked by high-confidence, road-following paths. Whereas extended barriers were associated with the most global constraints on mobility, nonextended barriers (e.g., hills, small lakes, drainage ditches, fenced fields, or forests) represent the most significant mobility constraints for overland travel. Ordering relevant nonextended barriers from stronger constraints (i.e., larger barriers and no-go regions) to weaker constraints (i.e., smaller barriers and slow-go regions) will extend the top-down analysis process. At each successive level of refinement, a selection metric, sensitive to progressively more local path evaluation constraints, is applied to the candidate path sets. The path refinement process terminates when one or more candidate paths have been generated that satisfy all path evaluation constraints. Individual paths are then rank-ordered against selected evaluation metrics.

Whereas traditional path development algorithms generate plans based on brute force optimization by minimizing path resistance or other similar metric, the hierarchical constraint-satisfaction-based approach just outlined emulates a more human-like approach to path development. Rather than using simple, single level-of-abstraction evaluation metrics (path resistance minimization), the proposed approach supports more powerful reasoning, including concatenated metrics (e.g., maximal concealment from one or more vantage points plus minimal travel time to a goal state). A path that meets both of these requirements might consist of a set of road segments not visible from specified vantage points, as well as high-mobility off-road path segments for those sections of the roadway that are visible from those vantage points. Hierarchical constraint-based reasoning captures the character of human problem-solving approaches, achieving the spectrum from global to more local subgoals, producing intuitively satisfying solutions. In addition, top-down, recursive refinement tends to be more efficient than approaches that attempt to directly generate high-resolution solutions.

24.7.2   Detailed Example

This section uses a detailed example of the top-down path-planning process to illustrate the potential benefits of the integrated semantic and spatial database discussed in Section 24.6. Because the database provides both natural and efficient access to both hierarchical semantic information and multiple-resolution spatial data, it is well suited to problems that are best treated at multiple levels of abstraction. The tight integration between semantic and spatial representation allows effective control of both the search space and the solution set size.

The posed problem is to determine one or more good routes for a wheeled vehicle from the start to the goal state depicted in Figure 24.11. Stage 1 begins by performing a spatially anchored search (i.e., anchored by both the start and goal states) for extended mobility barriers associated with both the cultural and the geographic feature database. As shown in Figure 24.12, the highest level-of-abstraction representation of the object representation of space (i.e., the top-level of the pyramid) indicates that a river, which represents an extended ground-mobility barrier, exists in the vicinity of both the start and the goal states. At this level of abstraction, it cannot be determined whether the extended barrier lies between the two points.

The pyramid data structure supports highly focused, top-down searching to determine whether ground travel between the start and the goal states is blocked by a river. At the next higher-resolution level, however, ambiguity remains. Finally, at the third level of the pyramid, it can be confirmed that a river lies between the start and the goal states. Therefore, an efficient, global path strategy can be pursued that requires breaching the identified barrier. Consequently, bridges, suitable fording locations, or bridging operations become candidate subgoals.

If, however, no extended barrier had been discovered in the cells shared by the start and the goal states (or in any intervening cells) at the outset of stage 1 analysis, processing would terminate without generating any intervening subgoals. In this case, stage 1 analysis would indicate that a direct path to the goal is feasible.

Whereas conventional path-planning algorithms operate strictly in the spatial domain, a flexible top-down path-planning algorithm supported by an effectively integrated semantic and spatial database can operate across both the semantic and the spatial domains. For example, suppose nearby bridges are selected as the primary subgoals. Rather than perform spatial search, direct search of the semantic object (River 1) could determine nearby bridges. Figure 24.13 depicts attributes associated with that semantic object, including the location of a number of bridges that cross the river. To simplify the example, only the closest bridge (Bridge 1) will be selected as a candidate subgoal (denoted SG_1,1). Although this bridge could have been located via spatial search in both directions along the river (from the point at which a line from the start to the goal state intersects River 1), a semantic-based search is more efficient.

To determine if one or more extended barriers lie between SG_1,1 and the goal state, a spatial search is reinitiated from the subgoal in the direction of the goal state. High-level spatial search within the pyramid data structure reveals another potential river barrier. Top-down spatial search once again verifies the existence of a second extended barrier (River 2). Just as before, the closest bridging location, denoted as SG_1,2, is identified by evaluating the bridge locations maintained by the semantic object (River 2). Spatial search from Bridge 2 toward the goal state reveals no extended barriers that would interfere with ground travel between the SG_1,2 and the goal state.

As depicted in Figure 24.14, the first stage of the path development algorithm generates a single path consisting of the three subgoal pairs (start, SG_1,1), (SG_1,1, SG_1,2), and (SG_1,2, goal) satisfying the global objective of reaching the goal state by breaching all extended barriers. Thus, at the conclusion of stage 1, the primary alternatives to path flow have been identified.

In stage 2, road segments connecting adjacent subgoals that are on or near the road network must be identified. The semantic object representation of the bridges identified as subgoals during the stage 1 analysis also identify their road association; therefore, a road network solution potentially exists for the subgoal pair (SG_1,1, SG_1,2). Algorithms are widely available for efficiently generating minimum distance paths within a road network. As a result of this analysis, the appropriate segments of Road 1 and Road 2 are identified as members of the candidate solution set (shown in bold lines in Figure 24.14).

Next, the paths between the start state and SG_1,1 are investigated. SG_1,1 is known to be on a road and the start state is not; therefore, determining whether the start state is near a road is the next objective. Suppose the assessment is based on the fuzzy qualifier near shown in as Figure 24.15. Because the detailed spatial relations between features cannot be economically maintained with a semantic representation, spatial search must be used. Based on the top-down, multiple-resolution object representation of space, a road is determined to exist within the vicinity of the start node. A top-down spatially localized search within the pyramid efficiently reveals the closest road segment to the start node. Computing the Euclidean distance from that segment to the start node, the start node is determined to be near a road with degree of membership 0.8.

Because the start node has been determined to be near a road, in addition to direct overland travel toward Bridge 1 (start, SG_1,1), an alternative route exists based on overland travel to the nearest road (subgoal SG_2,1) followed by road travel to Bridge 1 (SG_2,1, SG_1,1). Although a spectrum of variants exists between direct travel to the bridge and direct travel to the closest road segment, at this level of abstraction only the primary alternatives must be identified. Repeating the analysis for the path segment (SG_1,2, goal), the goal node is determined to be not near any road. Consequently, overland route travel is required for the final leg of the route.

In stage 3, all existing nonroad path segments are refined based on more local evaluation criteria and mobility constraints. First, large barriers, such as lakes, marshes, and forests, are considered. Straight-line search from the start node to SG_1,1 reveals the existence of a large lake. Because circumnavigation of the lake is required, two subgoals are generated (SG_3,1 and SG_3,2) as shown in Figure 24.14, one representing clockwise travel and the other counter-clockwise travel around the barrier. In a similar manner, spatial search from the start state toward SG_2,1 reveals a large marsh, generating, in turn, two additional subgoals (SG_3,3 and SG_3,4).

Spatial search from both SG_3,3 toward SG_2,1 reveals a forest obstacle (Forest 1). Assuming that the forest density precludes wheeled vehicle travel, two more subgoals are generated representing a northern route (SG_3,5) and a southern route (SG_3,6) around the forest. Because a road might pass through the forest, a third strategy must be explored (road travel through the forest). The possibility of a road through the forest can be investigated by testing containment or generating the intersection between Forest 1 and the road database.

The integrated spatial/semantic database discussed in Section 24.6 provides direct support to containment testing and intersection operations. With a strictly vector-based representation of roads and regions, intersection generation might require interrogation of a significant portion of the road database; however, the quadtree-indexed vector spatial representation presented permits direct spatial search of that portion of the road database that is within Forest 1.¹ Suppose a dirt road is discovered to intersect the forest. As no objective criterion exists for evaluating the best subpath(s) at this level of analysis, an additional subgoal (SG_3,7) is established. To illustrate the benefits of deferring decision making, consider the fact that although the length of the road through the forest could be shorter than the travel distance around the forest, the road may not enter and exit the forest at locations that satisfy the overall path selection criteria.

Continuing with the last leg of the path, spatial search from SG_1,2 to the goal state identifies a mountain obstacle. Because of the inherent flexibility of a constraint-satisfaction-based problem-solving paradigm, a wide range of local path development strategies can be considered. For example, the path could be constrained to employ one or more of the following strategies:

1. Circumnavigate the obstacle (SG_3,8)

2. Remain below a specified elevation (SG_3,9)

3. Follow a minimum terrain gradient (SG_3,10)

Figure 24.16 shows the path-plan subgoal graph following stages 1–3. Proceeding in a top-down fashion, detailed paths between all sets of subgoals can be recursively refined based on the evaluation of progressively more local evaluation criteria and domain constraints. Path evaluation criteria at this level of abstraction might include (1) the minimum mobility resistance, (2) minimum terrain gradient, or (3) maximal speed paths.

Traditional path-planning algorithms generate global solutions by using highly local nearest-neighbor path extension strategies (e.g., gradient descent), requiring the generation of a combinatorial number of paths. Global optimization is typically achieved by rank ordering all generated paths against an evaluation metric (e.g., shortest distance or maximum speed). Supported by the semantic/spatial database kernel, the top-down path-planning algorithm just outlined requires significantly smaller search spaces when compared to traditional, single-resolution algorithms. Applying a single high-level constraint that eliminates the interrogation of a single 1 km × 1 km resolution cell, for example, could potentially eliminate search-and-test of as many as 10,000, 10 m × 10 m resolution cells. In addition to efficiency gains, due to its reliance on a hierarchy of constraints, a top-down approach potentially supports the generation of more robust solutions. Finally, because it emulates the problem-solving character of humans, the approach lends itself to the development of sophisticated algorithms capable of generating intuitively appealing solutions.

In summary, the hierarchical path development algorithm

1. Employs a reasoning approach that effectively emulates manual approaches

2. Can be highly robust because constraint sets are tailored to a specific vehicle class

   

   FIGURE 24.16
   Path development graph following (a) stage 1, (b) stage 2, and (c) stage 3.

3. Is dynamically sensitive to the current domain context

4. Generates efficient global solutions

The example outlined in this section demonstrates the utility of the database kernel presented in Section 24.6. By facilitating the efficient, top-down, spatially anchored search and fully integrated semantic and the spatial object search, the spatial/semantic database provides direct support to a wide range of demanding, real-world problems.

24.8.1   Introduction

Conventional sensors typically generate systematic (if imperfect) location descriptions, be they range cells, error ellipses, or angle- or range-only measurements. Humans, however, tend to describe locations in a nonsystematic fashion. Although semantic location descriptions tend to be somewhat ambiguous, they often prove entirely satisfactory and even preferred for communicating concepts to other humans. When a human says that he met a friend at the intersection of Riverdale Rd and Sycamore St, in front of First Virginia Bank, or along the road that runs past the American Embassy, another person familiar with the area would have little trouble placing these locations. Ambiguous natural language descriptions, however, tend to be problematic when the objective is support to an automated multisource fusion system.

Because natural language effectively encourages vague descriptions of locations, capturing the essence of this vagueness in a rigorous fashion is essential. From its inception in the 1960s, fuzzy set theory² has sought to support language understanding and semantic reasoning. Quite apart from fuzzy set theory and its formalisms, the notion of assigning mathematical meanings to adjectives and adverbs such as tall, fast, and near seems quite natural. Although arguments persist that probability theory can credibly handle the concept of vagueness, for many people, it takes a significant intuitive leap to go from semantic vagueness (mostly red, fairly tall, reasonably handsome) to a probability of occurrence space. We sidestep both the theoretical and the philosophical arguments associated with fuzzy set theory and focus instead on a practical implementation of mixed crisp and fuzzy spatial reasoning.

By their very nature, crisp spatial modifiers such as inside, outside, to the west of, and higher are absolute qualifiers. Although their meaning may depend to some extent on the referenced features, it is not tied to problem context. The concept of outside a building (in other words, NOT building) leaves little room for interpretation. The same cannot be said about near a building. Near is clearly a context-sensitive modifier/qualifier that may be highly dependent on the object class (e.g., near a building vs. farm vs. a town vs. a country), as well as on other aspects of the problem.

To manage and manipulate mixed crisp and fuzzy features, it is convenient to transform one or both representations into a common space.

• Crisp descriptions can be fuzzified.

• Fuzzy descriptions can be transformed into crisp (Boolean-like) descriptions.

• Both crisp and fuzzy representations can be transformed into a new space that better supports mixed representation analysis.

The first two approaches alter the precision of the data sets, whereas the last approach need not.

An example of the latter approach that shows promise indexes crisp descriptions of points, lines, and regions using a hierarchical regular decomposition referred to as the quadtree-indexed vector representation.¹ In this representation, a point feature is indexed by one quadtree cell. A line feature is indexed by a collection of adjacent quadtree cells, whereas a region feature is indexed by the set of quadtree cells that cover both the region boundary and its interior. Fuzzy features are indexed identically and then modified to accommodate generalizations such as near and not near.

Figure 24.17a shows the indexing cells for all buildings (crisp features) in a sample data set. Figure 24.17b depicts the selected fuzzy set near function, and Figure 24.17c shows the indexing cells that represent 100% near all buildings. Figure 24.18 depicts indexing cells and the road cells plus the 100% near cells for a simple road network. Figure 24.19 shows the combined road and building data set, as well as results of selected mixed Boolean and fuzzy set operations. Because all analysis relies on indexing space operations, the accuracy of the underlying data is not altered in any way. Because of the regular and area-based nature of the quadtree decomposition, both indexing space search and set operation generation tend to be efficient.

An additional complication of using natural language input is that automated approaches must be able to translate from vague semantic location descriptions to formal indexed spatial representations. Examples include near a park, in front of a named building, between two buildings, across the street from a named location, away from road intersections, not far from the center of town. To emphasize the need to translate from semantic location descriptions to more traditional formal spatial representations, consider the example shown in Figure 24.20. All eight locations described in the left-hand box refer to roughly the same region of space. Although the reader can readily verify this assertion, inferring the similarity of this set of descriptions using strictly semantic-based reasoning approaches would be a significant challenge.

In terms of fusion applications, sample capabilities of a mixed Boolean and fuzzy reasoning system would include the ability to represent:

Crisp representations

Inside (a polygon)

On the border (of a polygon)

Inside and on the border (of a polygon)

Semantic/fuzzy set representations

Near/along (directional 360° to highly focused)

Not near (directional 360° to highly focused)

Operators between feature layers (plus concatenation between products)

AND/intersection

OR/union

Operations within a single layer

AND (e.g., find intersections of specified (all) roads)

Search selected data layers (find feature classes)

Near a selected point

Within a spatial window (defined by arbitrary combinations of set of operations)

Derived operators (derived from combinations of base operations)

Between

Around

In front of, behind

Across from

24.8.2   Extended Operations

Extended operations are either derivable from the base operations or require specialized functions. Between and across the street are two examples. Figure 24.21a depicts the result of ANDing two directional nears that effectively creates the concept between. Across the street from the Bank requires multiple layers of reasoning. The first step involves determining the closest road to the named building (near Bank AND all roads). If the building happened to be near multiple roads, the query result would be ambiguous, generating two or more possible road instantiations. (It is worth noting that this kind of ambiguity would exist whether the query was handled by a human or by a machine.) Assuming just one road is closest, the road cells directly in front of the bank are determined (near Bank AND Road 1). Across Road 1 from the Bank is then generated by region growing from these select road cells, but only on the opposite side of the road from the Bank as depicted in Figure 24.21b. Choosing Road 2 rather than Road 1 results in the solution shown in Figure 24.21c.

Relevant context can fall across a spectrum from highly local to highly global. As an example of more global context support, suppose a message refers to a grocery store and a specified road (Road 9) but gives no indication to either the address or the name of the establishment. As long as the supporting GIS contains the named road (Road 9) and identifies all building classes, candidate building(s) can potentially be identified.

Search building layer (grocery store) near Road 9.

If more than one grocery store is discovered, it might be helpful to apply other heuristics to narrow the selection, for example, weight selections closest to where an individual being tracked lives or weight based on candidate’s ranking in the key location database.

Even when weaker constraints are provided, it might still be possible to provide useful products. Suppose a suspect is reported to have entered the large building at the intersection of Jennifer and Vine Streets. The desired road intersection can be found by ANDing the two named roads. A near filter (spatial window) center on the discovered road intersection would then be applied to the building database. Depending on the relative size of all discovered buildings, the query might produce one or more candidates. In the worst case, if all the buildings happened to be roughly the same size, four alternative hypotheses would result. Once again, other context constraints can be applied to rank-order the candidates. If the two largest buildings near the intersection, for example, happened to be a movie theater and a lady’s dress shop, the movie theater might be the more likely candidate. If the observation contained the additional qualification that the building was north of the intersection, only a single building might satisfy the constraint set.

Even when location descriptions are highly ambiguous, some level of automated support might still be possible. Suppose an observation stated that a man ran out of the bank and disappeared in the nearby city park. Intersecting near city parks with near commercial banks is likely to generate only a small number of bank matches. If the bank had been further described as being along a street lined by restaurants, intersecting the resultant regions with near all restaurant districts is likely to further narrow the candidate list.

Exploitation of ambiguous information possibly resident in different databases assembled for different purposes has a wide range of possible applications. The development of a generic context support capability that handles natural language location translation and flexible manipulation of mixed Boolean and fuzzy spatially organized constraints appears to be a realistic objective. Beyond serving a wide range of applications, such a system could offer a systematic approach for managing spatial uncertainty.