RESIN: A RESource bounded INformation Gathering System for Visual Analytics

PI: Anita Raja

RA: Jia Yue, Zhiyong Guo, Evan Liu 

Collaborators:  Professor Bill Ribarsky, UNCC, Professor Ashok Goel, Georgia Tech, Professor Jing Yang, UNCC

Sponsor: DHS

Knowledge gathering and investigative tasks in open environments are very complex because the problem-solving context is constantly evolving, and the data may be incomplete, unreliable and/or conflicting. These tasks are time critical and typically involve identifying and tracking multiple hypotheses; gathering evidence to validate the correct hypotheses and eliminating the incorrect ones. Visual analytics is the science of applying reasoning and analysis techniques to large, complex real-world data for problem solving using visualizations.

In RESIN, we designed and developed a mixed-initiative reasoning agent that will assist investigative analysts in foraging tasks and performing predictive analysis using blackboard-based reasoning, visualization and an intelligent user interface. The agent leverages sequential decision making and an AI blackboard system to support hypothesis tracking and validation in a highly uncertain environment. The reasoning process involves the sequential execution of multiple knowledge sources, gathering large amounts of evidence, reasoning about incomplete and contradictory information, and supporting hypothesis tracking. The agent is also equipped with the ability to adapt its processing to available resources, deadlines and their current problem-solving contexts. Moreover, one notable characteristic of this agent is that it is equipped with technologies to predict the impact of future events by first determining the missing information in current events and then identifying the event occurrence trends based on the historical events captured in the global terrorism database.

Predictive Analytics in RESIN

The hypothesis we plan to validate is: Given a current event, it is possible to predict future events by first determining the missing information about the current event and then determining the event trends based on the historical events captured in the global terrorism database. We also want to identify the impact level of the future events. The specific problem solving process can be summarized as the following three phases:

Sample Terrorism Event

Fig1: Predictive Problem

Phase1- Category Prediction (CP) : To predict the missing or unknown category information (group name) based on the current event.

Phase2- Event Occurrence Prediction (EOP) : To predict the event occurrence of a certain group as identified from phase1 using the time series analysis on the historical data.

Phase3- Event Impact Level prediction (EILP) : To predict the impact level of future events by the pre-defined rules and exponential smoothing method based on the occurrence trends of that group from phase 2

RESIN's Reasoning Process

The RESIN agent consists of an AI Blackboard, a TÆM.S. task structure library, a Markov Decision Process (MDP)solver and heterogeneous knowledge sources (KSs). The AI Blackboard contains current goals and reasoning results from processing existing information, which includes raw data, various problem-solving states, and partial solutions. TÆM.S. is an abstraction of the low-level execution model and captures uncertainty in outcome distributions. The MDP is a probabilistic model, which captures the essence of sequential decision processes, and is used to compute policies that identify, track, and plan to resolve confidence values associated with blackboard objects. The KSs are independent specialist computational modules that contain the domain knowledge needed to solve a problem.

RESIN's control flow

Fig2: RESIN's control flow

As shown in Figure 2, the problem-solving process is initiated when the Human User posts a goal on the AI Blackboard and this action triggers the agent (Step 1). The goals are domain-dependent and can be split into smaller sub-goals. For example, one sub-goal is to predict the missing information of an input vector containing the partial information about a single terrorist incident. Based on the blackboard's preprocessed result, the TÆM.S. task structure modeler generates an appropriate task structure and translates it to the MDP solver for action assessment (Step 2). Using dynamic programming, the MDP solver computes the optimal policy based on resource constraints (e.g. deadline) and generates the best action, which will trigger appropriate methods to perform predictive analysis (Step 3). Through a built-in user interface, the agent enables the user to interact with the visual analytics tools supporting the mixed-initiative problem solving process, to validate the initial RESIN results and to post their results back to the AI blackboard (Step 4). Using these visualization results as well as previous analysis results, the blackboard will then propagate the evidence information and verify a specific hypothesis with an associated confidence value.

Multi-level Blackboard Database

RESIN's AI blackboard is a global shared repository containing problems, elementary data, a set of partial solutions, contributed information, and other data, which is available to all KSs and serves as a communication medium. It is the kernel of this reasoning agent, providing a reasoning approach for the information that has been discovered and produced. It contains four different levels: Goal, Hypothesis, Concept, and Data, in order of decreasing levels of abstraction. The Goal level stores the goal of the problem and resolution information. The Hypothesis level contains concepts which are represented in the Concept level. The Data level contains the data/evidence gathered to (in) validate the various hypotheses. The layered hierarchy allows for explicit modeling of concurrent top-down and bottom-up processing, while maintaining a clear evidential path for supporting and contradictory information. The information at a given level is derived from the level(s) below it, and it in turn supports the hypothesis at higher levels.

Multi-Level Blackboard Database

Fig3: Blackboard Data Structure

RESIN in Action

The problem solving process is initiated when the human user posts a goal on RESIN's blackboard, and this action triggers the RESIN agent. The goal is to predict the impact level and count occurrence of incidents perpetrated by a certain group or groups which has perpetrated the current terrorist incident.Given a particular deadline for the problem solving process, RESIN will assist the analyst in performing the predictions for the unknown group name (CP), the occurrence trend for this particular group (EOP), as well as the impact level for future events (EILP).

                                               Fig4: RESIN's Control Panel                                                                                                          Fig5: Runtime Views

Empirical Evaluations

This experiment is based on a training set of 2700 incidents selected from the GTD, and for each task we use the same ten incidents from a test set, with different deadlines from 30 to 70 (ranging from a very tight to a loose deadline). Duration describes the amount of time that the action will take to execute. Different applications have different notions of the basic unit of time. The deadline is the hard constraint by which the overall task has to be completed.There are ten users involved in the experiments with access to the GTD tool. Each user will determine the confidence values towards initial predictions, with values from -0.9 (strongly disagree and dispute the result) to 0.9 (strongly agree and accept the result) through interactions with MAP_VIEW and TEMPORAL_VIEW .We compare the predictive performance of the MDP policy and a Deterministic Schedule (DS) for task structures under different deadlines. DS is a deterministic process scheduler that builds a static schedule with the highest possible quality.

RESIN's CP Performance

Fig6: RESIN's CP Performance

We also use the monthly data from January 1970 through December 1996 as the training set to create the model on which to predict the occurrences of terrorist attacks from January 1997 through December 1997.

RESIN's EOP PerformanceRESIN's EOP Performance

Fig7: Resin's EOP Performance

 

This work is supported by the grant to establish the Regional Visual Analytics Center (RVAC) at UNC Charlotte and Georgia Tech. Professor Ribarsky's presentation on the vision of the RVAC can be found here.

Links:

Publications:

.