N15A-T017 TITLE: Graph Grammars for Naval Essential Tasks

TECHNOLOGY AREAS: Information Systems

ACQUISITION PROGRAM: Data Focused Naval Tactical Cloud EC, Distributed Common Ground Station

OBJECTIVE: Develop an innovative graph grammar approach to machine understanding and fulfillment of standard Navy/Marine Corp essential mission tasks that captures relevant conditions and predicts measures of performance.

DESCRIPTION: The transformation of Big Data access to enhanced tactical level decision making remains an unfulfilled vision. While the Naval services maintain conceptional models for missions and the associated essential tasks forces must be able to plan and conduct (1,2), these models are not semantically mapped to a data representation of the conditions that affect measures of effectiveness. Such a mapping is complex given that for each task, there are associated conditions that must be set and measures of effectiveness that must be achieved. Conditions relevant to the conduct of mission tasks include the physical environment, military environment and civil environment (3). The physical environment includes information about land, sea, air and space. The military environment includes information on the mission; forces; Command, Control, Communications, Computers (C4); intelligence; deployment; movement and maneuver; firepower; protection; sustainment; threat and conflict. The civil environment includes information about political polities, culture and the economy. For any force operating in any area, information about conditions relevant to the set of essential tasks can be expressed as a "big knowledge graph". This graph can be produced by data enrichment capabilities allowed to operate against all available data stores.

This topic will enable the development a capability, using graph grammars, to quickly write a graph transform from a "big knowledge graph" that describes a mission and relevant conditions in a way that enables the calculation of mission measures of effectiveness. These graph transformations may require use of graph grammars to transform a large graph to an embedded space having a much lower graph dimensionality that captures the key nodes/edges relevant to a mission and its conditions(4). A mature product may require a user interface that allows graph transformations to be generated by staffs of commanders at all levels with limited programming expertise. Once a mission is assigned and mapped to an embedded information graph space, that transformed graph then needs to be sent to all reachable information sources (local and reach-back) in order to populate the graph model with information. The use of graph grammars has already been used within the development community for a wide variety of analytic tasks including information retrieval (5), but for this topic, deeper mission semantics will be required. Some of the concepts involved in the definition of missions and conditions will also require innovation in structured grammars beyond the current state-of-the-art in order to specify concepts that involve high order graph structures with time/space/context constraints on nodes/edges. The use of graph grammars for concepts, while not as mature as structured text grammars, is an emerging discipline with a body of prior art (6). Once a mission/condition graph transform is completed, the system also needs to be able to assess graph completeness in order to assess mission readiness and project likely measures of performance.

For Phase I, offerors may use any publically available RDF (data triples) data sets about places containing a large number of edge relationships. One example is U.S. census data which is available at http://datahub.io/dataset/2000-us-census-rdf. To demonstrate progress, the performer may want to assume that a program is planned that intends on improving some aspects of life in communities (e.g. reduce crime, improve economic conditions) and present a logical model about what initial conditions would enhance the predicted measures of effectiveness of the program and what initial conditions would reduce measures of effectiveness. This model should be entered through a user friendly interface and allow subset of the node types to be included in the model. Performers should not use graphs that are completely populated. While performers are free to demonstrate progress in other ways, all Phase I efforts should mature a technical approach to using graph grammar to identify relevant subgraphs and to measure the distance of each from a graph that captures the dependence of measures of effectiveness on conditions. Rya is the preferred triple data store, but other open source or government owned options are acceptable.

The specific technical challenges associated with this topic include: 1) Transform a large and high dimensionality data structure to mission/condition relevant graphs, 2) Use these graph transformations as a means to communicate data needs to distributed information sources, 3) Collapse collected information into a final graph for a mission, and 4) Translate the information content of mission graphs to a set of mission measures of performance.

PHASE I: During the Phase I effort, performers are expected to identify a technical approach consistent with the goal of reducing the technical risk associated with building a working prototype during a Phase II. For a bounded set of missions and conditions, show graph transformation, automated information collection and content assessment. Begin work on mapping specific mission graph content to mission measures of effectiveness. Conclude with a proof of concept demonstration using open source data that shows technical risk retirement. Phase II plans should also be provided to include key component technological milestones and plans for testing and validation of the proposed system and its components.

PHASE II: Produce a prototype system based on the preliminary design from Phase I. The Phase II prototype should support a diverse set of Naval missions and conditions and automate the assessment of mission measures of effectiveness. A Phase II performer will be provided data by the Government. An offeror may assume that the prototype system will need to run as a distributed application in cloud architecture against billion node graphs. Phase II deliverables will include a working prototype of the system, software documentation including a user�s manual and a demonstration involving operational data or accurate surrogates of operational data.

PHASE III: Produce a system capable of deployment and operational evaluation. The system should consume available operational and open source data sets and focus on areas/missions that are of interest to specific transition programs or commercial applications. The final system needs to have an easy to use man-machine interface. The software and hardware should be modified to operate in accordance with guidelines provided by transition sponsor.

PRIVATE SECTOR COMMERCIAL POTENTIAL/DUAL-USE APPLICATIONS: Internet search engines would benefit from the maturation of data retrieval based on concept graph grammars. Currently, information retrieval is limited to word searches with some support to graph searches. Information retrieval by subject, delivered without redundancy, would transform information delivery.

REFERENCES:
1. Marine Corps Task List, 1 January 2014. Available at: www.mccdc.marines.mil/Units/MarineCorpsTaskList.aspx

2. Carpenter, J. D., "Using Mission Essential Task Lists as a Basis for Mission-Based Operational Test Planning". Unpublished. Available at: www.dtic.mil/ndia/2007test/Carpenter_SessionD2.pdf

3. OPNAVINST 3500.38A/MCO 3500.26_/USCG COMDTINST M3500.1A 1Oct 2002; Available at:
http://www.google.com/url?url=http://www.mccdc.marines.mil/Portals/172/Docs/MCTL/MCTL%2520Conditions.doc&rct=j&frm=1&q=&esrc=s&sa=U&ei=6JotVJrxOOblsAT04IGADQ&ved=0CBQQFjAA&sig2=yjV9fRYq_OXSLNk8fblaBg&usg=AFQjCNFtO-nygA9QbN-DaQjrI5SpbjcjzA

4. Fahmy. H., Blostein D., "A Survey of Graph Grammars: Theory and Applications": Department of Computing and Information Science Queen�s University,Kington, Ontario, Cananda: Available at:
www.researchgate.net/publication/3513859_A_survey_of_graph_grammars_theory_and_applications

5. Jonyer, I, Holder, L., Cook, D., "Concept Formation Using Graph Grammars": Department of Computer Science and Engineering University of Texas at Arlington: Available at:
ailab.uta.edu/old_site/subdue/papers/JonyerMRDM02.pdf

6. Liu, Y. "Graph-Based Learning Models for Information Retrieval: A Survey" Available at:
www.cse.msu.edu/~rongjin/semisupervised/graph.pdf

7. Ehrig, H, "Introduction to Graph Grammars with Application to Semantic Networks" Computers Math Applic., Vol., 23, No 6-9, pp.557-572, 1993.

KEYWORDS: Graph Analysis, Graph Grammars, Information Science, Modeling, Predictive Analysis, Human Machine Interface, Concept Modeling

** TOPIC AUTHOR (TPOC) **

DoD Notice:   Between December 12, 2014 and January 14, 2015 you may talk directly with the Topic Authors (TPOC) to ask technical questions about the topics. For reasons of competitive fairness, direct communication between proposers and topic authors is not allowed starting January 15, 2015 , when DoD begins accepting proposals for this solicitation.

However, proposers may still submit written questions about solicitation topics through the DoD's SBIR/STTR Interactive Topic Information System (SITIS), in which the questioner and respondent remain anonymous and all questions and answers are posted electronically for general viewing until the solicitation closes. All proposers are advised to monitor SITIS (15.A Q&A) during the solicitation period for questions and answers, and other significant information, relevant to the STTR 15.A topic under which they are proposing.

If you have general questions about DoD STTR program, please contact the DoD SBIR/STTR Help Desk at (866) 724-7457 or webmail link.