Referent Tracking for Command and Control Messaging Systems Shahid Manzoor, Werner Ceusters and Barry Smith Center of Excellence in Bioinformatics & Life Sciences, University at Buffalo 701 Ellicott Street, Buffalo NY, 14214 smanzoor@buffalo.edu, ceusters@buffalo.edu, phismith@buffalo.edu. Abstract – The Joint Battle Management Language (JBML) uncertain, conflicting and erroneous, either because of is an XML-based language designed to allow Command and misinterpretations committed by friendly agents or Control (C2) systems to interface easily with Modeling and falsifications introduced through counter-intelligence Simulation (M&S) systems. While some of the XML-tags defined activities, this distinction is crucial. in this language correspond to types of entities that exist in reality, others are mere syntactic artifacts used to structure the In this paper we show how a realism-based ontology, messages themselves. Because these two kinds of tags are not combined with a rule language, can be used to make these formally distinguishable, JBML messages in effect confuse data distinctions explicit and to store the contents of JBML with what the data represent. In this paper we show how a messages in a Referent Tracking System (RTS) in a format realism-based ontology combined with a rule language can be that mimics the structure of reality. used to make these distinctions explicit. The approach allows storage of the contents of JBML messages in a Referent In [2] we demonstrated how an RTS, i.e. a system that Tracking System in a format that mimics the structure of reality forces assertions to be expressed by means of statements that thereby providing an aid to message validation. use globally unique and singular identifiers for each referent Index Terms - Realism-Based Ontology, Command and mentioned [3] and that are structured according to the Control, Referent Tracking, JBML principles outlined in Basic Formal Ontology [4], may help the Intelligence Community to share information unambiguously. Here, we report on further enhancements of I. INTRODUCTION our prior work to integrate XML-based information systems The Joint Battle Management Language (JBML) was with RTS, using JBML as a specific example. We describe a designed in response to the growing need to interface prototype application that uses a realism-based ontology to Modeling and Simulation (M&S) systems with Command, parse JBML messages and that provides reasoning facilities Control, Communications, Computers, Intelligence, for the validation of the data. The application works by (1) Surveillance, and Reconnaissance (C4ISR) systems in order generating identifiers for all the real-world entities and their to provide the user with capabilities that support operational relationships that are mentioned in given messages, and (2) functions including Course of Action (COA) Development storing these identifiers in an RTS. and Analysis, mission rehearsal, and execution monitoring [1]. Its main benefit is that it overcomes the interoperability problem caused by the use of unstructured “free text” within II. ONTOLOGY-BASED PROCESSING OF MILITARY MESSAGES the operational C2 messages that are passed within C4ISR An RTS is an ontology-based database which uses globally systems, specifically for the most critical C2 information: the unique identifiers (called IUIs) to represent: (1) instances commander’s intent, orders and directives. While suitable for (spatiotemporal particulars, including people, commands, interpersonal communication, free text is inadequate for use places, events), (2) the relations that hold between such by simulations and robotic or software-based components. instances, (3) the (potentially multiple) names that are assigned to such instances, and (4) the universals or classes JBML is highly structured and the majority of its XML- that such instances instantiate [2, 3, 4]. The RTS thereby tags (or ‘elements’) are given very intuitive labels. Yet, the provides a framework for the logically coherent formulation language generally suffers from the problem that while some of assertions made about any of the given entities, including of the tags denote generic entities in reality that are those types of assertions contained in C2 messaging. instantiated by the referents denoted by the elements’ contents in a specific message, other tags provide information about An example of a military message in JBML is shown in the message structure itself, rather than what the message is Listing 1. The message represents a mission that is assigned about. Because these two kinds of tags are not formally to an army unit with identifier ‘2TF A TEAM’. The army unit distinguishable, JBML messages confuse data with what these has to move between points whose coordinates are given data represent. This does not need to be a problem if the data under the WhereValue element in the XML. In the prototype are always an accurate representation of reality. But in an implementation here described, assertions about entities are intelligence context, where large amounts of data are inserted in the RTS as triples, for example: IUI-1004 instanceof MilitaryMission and thus no messages have as yet been processed, the RTS IUI-1005 instanceof MilitaryUnit database contains no information. As more and more IUI-1004 missionAssignedTo IUI-1005 messages are processed, the RTS becomes populated with IUI-1005 currentPostionAt IUI-1014 successively more IUIs and with corresponding statements about the relationships between the referents of these IUIs. The first triple represents a statement to the effect that the Knowledge obtained through parsing earlier messages is used entity IUI-1004 instantiates the universal MilitaryMission; the to improve parsing of new messages, to check the consistency second triple a statement to the effect that the entity IUI-1005 of the information provided in new messages, and so forth. instantiates the universal MilitaryUnit; the third triple represents a statement to the effect that the mission with The whole process is carried out in four steps. identifier IUI-1004 is assigned to the military unit with identifier IUI-1005. The fourth triple represents a statement to A. Step 1: Structural Analysis of XML the effect that the current position of IUI-1005 is location In the first step, a military message is parsed with the goal IUI-1014. of detecting entities referred to and the relations between We have developed a prototype ontology for command and them, as shown in Fig. 2. The nodes of the graph correspond control systems called ‘C2-Test-Ontology’, which uses a to putative entities within the domain of the message, while subset of UCore SL, an ontology designed to support the the edges correspond to relations. Nodes without a prefix are Universal Core data schema [5], to link the JBML tags from entities named explicitly in the message. Nodes with the “rts:” the military messages to UCore SL. The ontology tells us prefix are generated on the basis of the XML-structure of the what data elements in a military message refer to what kinds message. Some of them will correspond to real entities, but of real world entities (e.g. ArmyUnit, MilitaryMission) and others are inserted as a side-effect of the oddities of the XML what relationships obtain between them. syntax. It is one of the tasks of our application to turn the resultant distorted view of reality into a realistic picture which We have also developed a Middleware program which conforms to good ontological principles [6]. parses military messages, and – drawing on knowledge contained in the C2-Test-Ontology – communicates with the In the first step, the middleware does not use any RTS and a rule-based reasoner to assign IUIs to the entities knowledge from the UCore SL or C2-Test ontologies. Rather mentioned in the messages. The architecture of our system is it iterates over the XML structure of the message using a shown in Fig. 1. When the middleware runs for the first time, depth first iteration strategy, in which each XML element is viewed as a relation between possible entities. The iteration leads to the creation of a new graph in which the software creates nodes automatically without contacting the RTS. As 2TF A TEAM an example, the XML element ‘’ is not explicitly labeled in the message above. It is immediately followed by MOVE , which is also not explicitly labeled. What is the relation between these two elements? The message provides no answer to this question. Our application in this first step assigns IUI identifiers to Task and GroundTask. By using ontologies in later steps, it will become possible to 48.9100583 arrive at more determinate representations. 39.9570562 0.0 Command & Control System 48.9056792 Sends JBML XML Message Ontology 39.9891024 0.0 Rules Middleware Communicate With RTS To Assign IUI Reasoner Referred in XML Message RTS Fig. 1: Command & Control Application Integration with RTS Listing 1: An Example of a JBML Message rts:1004 jbml:StartWhen rts:1015 rts:1015 jbml:WhenTime rts:1016 rts:1016 jbml:StartTimeQualifier “NLT” rts:1016 jbml:DateTime “110800ZAUG2025” Listing 2: Triples representation generated while analyzing the message in Listing 1 example ‘rts:1015’ and ‘rts:1016’ denote the same time, and ‘rts:1011’ and ‘rts:1012’ denote the same particular location. In line with the Referent Tracking principles, such duplicate identifiers must be removed. Inspection reveals that some triples, such as rts:1001 jbml:OrderPush rts:1002 rts:1002 Task rts:1003 rts:1003 jbml:GroundTask rts:1004 are defective from an ontological point of view and these too must be removed. A task, for example, is clearly not a relationship. This restructuring cannot however be achieved computationally in this step, because the XML framework does not provide explicit information sufficient to ensure the ontological soundness of the representation. We have therefore built another service, executed in step 2 below, which translates information implicit in the XML structure of a message into explicit assertions. Fig. 2: Graph generated in the first step of the middleware B. Step 2: Shallow translation of XML To achieve ontologically correct information of this sort we The entities and their relations shown in the graph in Fig. 2 use a variant of the Jena rule-based reasoning language [7] to are represented in the middleware by means of triples. The formulate rules stating the conditions for adding or removing first triple in the graph is: assertions in the graph. rts:1001 jbml:OrderPush rts:1002 We employ for this purpose forward-chaining reasoning The first and last terms of this triple denote entities, while the rules, each consisting of (1) a body and (2) a head. The middle term denotes the relationship between these entities. former specifies the set of patterns which triples in the message graph must match if they are to be capable of being As a further example, the triples representation for the node transformed into triples that are ontologically well-formed. rts:1004 and its relations with rts:1015 and its descendents are The latter consists of a set of ontologically well-formed shown in Listing 2. triples into which the triples in the set specified in (1) to be This graph does not yet provide a representation which is translated. faithful to reality in terms of the logical and ontological We distinguish four different types of rules: principles on which UCore SL and our C2-Test-Ontology are based. Clearly, some nodes in the figure denote genuine • If a rule name is prefixed with ‘ded_’ (for entities, including: deduction), then it is a deduction rule as described above. rts:1004, a particular military ground mission • If a rule name is prefixed with ‘red_’ (for reduction), rts:1005, a particular military unit, then the rule removes the triples matched against the rts:1015, a particular time pattern in part (1) of the rule and adds the triple set rts:1012, a particular location. in part (2). Moreover some nodes are such that they are unique instance • If a rule name is prefixed with ‘map_’ (for mapping) identifiers, as is required by Referent Tracking principles. then it assigns appropriate IUIs to entities that are However, the graph also contains many violations of these mentioned repeatedly in the message. principles. Some nodes denote in a non-unique way; for • If a rule name is prefixed with ‘val_’ (for Since the rule is of type ‘reduction’, the four triples are validation), then its goal is to check for removed from the military message triple set, and the inconsistencies in the data and to provide following three triples are inserted instead: corresponding notification to the receiver of the rts:1004 c2:StartWhen rts:1015 message. rts:1015 ro:instanceof c2:TimeEvent Our middleware provides distinct services for each of the rts:1015 c2:NoLaterThan “110800ZAUG2025” rule types described above. The first represents the assertion that the mission with An example of a deduction rule is: identifier #1004 starts at time event #1015. The second represents the assertion that entity #1015 instantiates the [ded_1 (?x jbml:Task ?y) (?y jbml:GroundTask ?z) TimeEvent universal from the C2-Test-Ontology, and the -> (?z ro:instanceof c2:MilitaryMission)] third represents the assertion that the time event #1015 occurs which asserts that if (i) for two putative entities the ‘Task’ at a time point which is not later than the time specified by the relationship holds and if (ii) the target-entity of this relation “110800ZAUG2025” date-time stamp. The execution of rule stands in a ‘GroundTask’ relation with a third entity, then (iii) red_7 shows (1) how redundant entities and their relations can the first two entities are erroneous artifacts generated in step be removed from military messages in such a way that (2) an 1, while the third entity is a MilitaryMission in the terms of ontology can be used to infer automatically assertions about our C2-Test-Ontology. Note that the issue here is not whether the entities in the real world which are referred to in these this specific rule is correct. What we are offering here are messages. examples. Crafting the needed set of rules for JBML and Note that in this second step, the middleware executes only other XML-based languages is a task which needs to be rules of types 1) and 2). Execution of deduction and reduction performed when once the general strategy has been rules over the triple set whose visualization is shown in Fig. 2 formulated and tested. then yields a new triple set whose visualization is shown in Here ‘ded_1’ is the name of the rule. Variables are prefixed Fig. 3. This new triple set conforms to sound logical and by ‘?’ and serve as placeholders for the actual terms in the ontological principles; specifically: there is here no matched triples in their respective places. The following are redundancy, and all nodes and edges in the graph are triples that match the conditions of the rule above: ontologically well-formed. (rts:1002 jbml:Task rts:1003) (rts:2003 jbml:GroundTask rts:1004), Each node of the graph whose label is prefixed with ‘rts:’ where variables in the rule bind terms in the matched triples contains the IUI of an entity referred to in the message, as as follows: ?x = rts:1002, ?y = rts:1003, ?z = rts:1004. follows: Under the head part of the rule, the software inserts the - #1004 denotes a particular military mission triple ‘rts:1004 ro:instanceof c2:MilitaryMission’, where the - #1015 denotes the particular TimeEvent when term ‘ro:instanceof’ denotes the instanceof relation from the mission #1004 must start Relation Ontology (‘ro’) [8], and the term - #1005 denotes the military unit that must perform ‘c2:MilitaryMission’ denotes the MilitaryMission universal mission #1004 taken from the C2-Test-Ontology (‘c2’). - #1009 denotes the line along which the #1005 unit has to move An example of a reduction rule is: - #1014 and #1012 denote distinct points [red_7: (?x jbml:StartWhen ?y) corresponding to the start and end of the #1009 line. (?y jbml:WhenTime ?z) (?z jbml:StartTimeQualifier "NLT") C. Step 3: Entity Tracking and Semantic Verification (?z jbml:DateTime ?l) In the third step, rules prefixed with ‘map_’ are executed -> (?x c2:StartWhen ?y) over the triple set that results from step 2. The middleware (?x ro:instanceof c2:TimeEvent) first checks whether the RTS is empty. If it is, there cannot be (?x c2:NoLaterThan ?l)] any duplicate entries and the triple set is simply inserted into The body of this rule is matched by the following set of the RTS and processing stops. However, if the RTS is not triples, generated from the message shown in Listing 2 . empty, then the middleware program continues to execute this step to. Suppose the middleware receives a second military rts:1004 jbml:StartWhen rts:1015 message (shown in Fig. 4) and that the RTS database contains rts:1015 jbml:WhenTime rts:1016 the triples shown in Fig. 3. Here, the military unit named rts:1016 jbml:StartTimeQualifier “NLT” ‘2TF A TEAM’ is assigned the IUI rts:2005. However, in the rts:1016 jbml:DateTime “110800ZAUG2025” RTS used in the message analysis system there is already a Fig. 3: Visualization of Ontologically Articulated Content of the XML message in Listing 1 Fig. 4: Second Military Message after Processing via Step 2 Fig. 5: Second Movement Mission as Described in the 2nd Example Message military unit whose name is ‘2TF A TEAM’, to which the IUI This rule instructs the middleware to search for matching rts:1005 has already been assigned. triples in the incoming message, in this case returning the triple: The Referent Tracking principles state that if the military unit in the second message is the same as the one referred to rts:2005 jbml:UnitID “2TF A TEAM” already in the RTS, then it should continue to be denoted by the IUI rts:1005. It is this conformity to Referent Tracking As ‘?x’ refers to an entity (whose IUI is to be determined), principles that is achieved by the mapping rules. the middleware replaces the IUI in the triple found by ?x. The above triple is thus transformed into the following: A mapping rule whose conditions are satisfied by the incoming second message is: ?x jbml:UnitID “2TF A TEAM” [map_1: (?x jbml:UnitID ?a) -> entity_found(?x)] The map_1 rule now instructs the middleware to search for a corresponding triple in the RTS which returns, in this case: rts:1005 jbml:UnitID “2TF A TEAM” strategies in relation to incoming messages on the basis of information obtained through earlier messages. The benefit of As a result, rts:2005 is replaced by rts:1005 in all using middleware along with rules built on the basis of a well- corresponding triples in the new message. The final output is structured ontology such as our C2-Test-Ontology (itself an shown in Fig. 5. extension of UCore SL), is that, if changes occur, for example At this stage, all triples of the incoming message are in in the format of the military messages or in our understanding accordance with the RT principles, and the message triples of military reality, changes will need to be made only in the are ready to be inserted into the RTS database in addition to rules and ontologies, and the need for further software the triple (rts:1005 jbml:UnitID “2TF A TEAM”) which is changes will thus be reduced. Another benefit of this already present. architecture is that the system can be re-used with other information systems pertaining to other Communities of At the end of these steps, an unambiguous representation of Interest (CoI). The only changes we need to make are: (1) the data – at least in terms of the C2-Test-Ontology – is building an appropriate ontology for each new CoI, (2) obtained, and additional reasoning over the data now becomes writing a new parser to analyze the information coming from possible. the corresponding information system, and (3) defining appropriate rules for that domain. D. Step 4: Reasoning to Validate Incoming Messages In this step, data validation rules are executed over the RTS We also did not use rules that provide alternative database used by the middleware to check for any interpretations of inconsistent data. Note for instance that the inconsistencies that may arise when inserting the content of inconsistency as concerns the location of the 2TF A TEAM the new message into the RTS. discussed above might result from a false assumption about which entity the name ‘2TF A TEAM’ in fact denotes – either Imagine a scenario under which the RTS is in the state perhaps it denotes different units in different messages, or shown in Fig. 3, and now the triples shown in Fig. 5, because in some messages typing errors have been made. corresponding to a new planned mission for the 2TF A TEAM, are ready to be inserted. The new mission involves The approach can be used not only to reason with messages the movement of the team from location #2012. Because the in given formats, but also to integrate messages with different new starting position is different from the current position of formats. Future work should be based on fully axiomatized the unit as recorded in the database, it is not possible for the forms of the various ontologies. The C2-Test-Ontology military unit to carry out the mission unless the starting point should also be dramatically extended to include not only can be reached in due time. In this case, the middleware will JBML, but relevant content from JC3IEDM, and NIEM with provide an alert warning of potential inconsistency of the the objective of creating fully automatized interoperability data. corridors, establishing a model for further work not only on more comprehensive collections of messages, but also on To perform the reasoning necessary for such an alert to be information of other types. generated, rules of type 4 are executed. The middleware executes these rules by communicating with the RTS and the REFERENCES reasoner. If the middleware finds any inconsistency as defined [1] J. Mark Pullen, Andreas Tolk, and C. Blais, "Joint Battle Management in a rule of type 4 (_val) then it generates warning messages. Language (JBML) -US Contribution to the C-BML PDG and NATO MSG-048 TA," in IEEE European Simulation Interoperability Workshop One rule used in this reasoning scenario is: Genoa, IT, 2007. [2] W. Ceusters and S. Manzoor, "How to track absolutely everything?," in val_1 (?a c2:missionAssignedTo ?b) Ontologies and Semantic Technologies for the Intelligence Community. (?a jbml:WhatCode ?c) Frontiers in Artificial Intelligence and Applications: IOS Press (?b c2:CurrentLocation ?d) Amsterdam, 2009, (in press). (?l jbml:missionAssigndTo ?b) [3] S. Manzoor, W. Ceusters, and R. Rudnicki, "Implementation of a Referent Tracking System," International Journal of Healthcare (?l jbml:WhatCode ?c) Information Systems and Informatics, vol. 2, pp. 41-58, 2007. (?b c2:StartingFrom ?o) [4] W. Ceusters and B. Smith. Strategies for Referent Tracking in Electronic notEqual(?a, ?l) Health Records. J Biomed Inform. 2006 Jun;39(3):362-78. notEqual(?d, ?o) [5] The Universal Data Core, Army Net-Centric Data Strategy (ANCDS), -> (?a error:inconsistentWith ?l) http://data.army.mil/datastrategy_universal_core.html, (2009). [6] K. Munn and B. Smith (eds.), Applied Ontology: An Introduction, Frankfurt/Lancaster: ontos, 2008, 342 pp. III. CONCLUSION [7] HP Labs Semantic Web Research, "Jena- A Semantic Web Framework for Java," 2009. We are currently in a phase in which the middleware [8] B. Smith, W. Ceusters, B. Klagges, J. Köhler, A. Kumar, J. Lomax, C. component is able to process several sample types of Mungall, F. Neuhaus, A. L. Rector, and C. Rosse, "Relations in incoming messages and to perform a number of reasoning biomedical ontologies," Genome Biology, vol. 6, p. R46, 2005.