Quantitative Methods in Defense and National Security 2007

Hierarchical High Level Information Fusion Using Graph Structures, Subgraph Matching and State Space Search
Moises Sudit, (University at Buffalo), sudit@eng.buffalo.edu,
Rakesh Nagi, (University at Buffalo), nagi@buffalo.edu, and
Kedar Sambhoos, (University at Buffalo), kps6@buffalo.edu


An enormous amount of research has been conducted in the area of multi-sensor data fusion. Under the Joint Directors of Laboratories (JDL) five-level data fusion model, Level 1 on Object refinement seems to have received the most attention. Level 1 processing functions include: data alignment, association, tracking, and identification. Less mature are Level 2 processing, situation assessment, which seeks a higher level of inference above level 1 processing, and Level 3 processing (for military or intelligence fusion systems) which performs threat assessment. The purpose of threat assessment is to determine the inherent threat of a situational state estimate using an inferential process. Level 2 processing (Situation Assessment) attempts to create an understanding of the knowledge of objects, their characteristics, relationships among objects and cross force relations. Situational assessment is the process of providing understanding to a decision-maker about a situation, including people, objects, events, and the environment. At the lowest level, assessment systems track information about relationships, movement, and classification. More sophisticated systems include understanding of the context, estimation of intent, and, ultimately, adaptation of the system to its particular environment.

The intent of this presentation is to show enhancements in Level 2 and 3 fusion capabilities through a new class of models and algorithms using graph structures. The problem today is not often lack of data, but instead, lack of information and data overload. Graph matching algorithms helps us solve this problem by identifying meaningful patterns in volumous amounts of data to provide information. In this paper we investigate a classical graph matching technique of subgraph isomorphism. A complete implementation of a heuristic approach (since the problem under consideration is NP-Hard) using an inexact isomorphism technique has been used. The heuristic approach is called Truncated Search Tree algorithm (TruST), where state space of the problem is constrained using breath and depth control parameters. The breath and depth control parameters are then studied using design of experiment based inferential statistics. Finally, a software implementation of the procedure has been completed with very encouraging empirical results.

Graph Matching is a classical optimization approach that has been studied for a number of years and for which at least two independent graphs are required. The first graph is called a Data Graph (also Input Graph), which contains all the sensor information gathered on a specific domain of interest. The second graph is called a Template Graph (also Template or Pattern), which describes a predefined information signature which is of relevance to an analyst. In general the Template Graph is much smaller than the Data Graph and the objective is to investigate the syntactic and semantic occurrence of Template Graph in the DataGraph.

The primary objective of this work is the progression of Level 2/3 fusion of informational content to obtain an advanced multi-intelligent system for hierarchical high level decision making processes. The goal of the proposed work is to develop an information integration mechanism to simplify human decision making solving operational problems. As technology continues to advance, and the proliferation of sensors in all platform increases, human decision makers are being overwhelmed with data. In summary, we use attributed graph models to represent situations in Level 2 and 3 Fusion. Graph matching is invoked to determine if a situation of interest to the analyst exists in a scenario. A Truncated Search Tree heuristic is developed to perform graph matching. A Maritime Domain example will be shown where hierarchical information fusion will be tested.

Take me back to the main conference page.