COA modelling with probabilistic ontologies

Abstract

-Planning during complex endeavors is a daunting task in many aspects. An important one is the representation of shared intent, which is an open research topic focused on expressing a common picture among different planning systems with distinct languages, and sometimes disparate problem solving methodologies. The common approach is to use a translator between the order/request message and the planning system, which doesn't convey all the elements that are necessary to support the planning task. The present research proposes to address this issue by the use of a semantic layer as an interface among different planning systems, which not only improves interoperability but also provides support for pruning the search space before the information is sent to the planning system. The layer is based on a probabilistic ontology, which provides shared intent description as well as formalization of the operational domain and of the planning problem, including a principled representation of the involved uncertainty. The proposed scheme supports previous analysis of the search space in order to send to the planning system a concise set of tasks that will contribute to reach the desired end state.

I. INTRODUCTION

Complex endeavors are challenging the Command and Control (C2) community with respect to both planning automation and shared intent representation. Both topics are important in order to reach a shared goal during an operation. Because of the collaborative aspect of a joint planning we need to observe the interoperability models in order to provide the level of data representation to be utilised in the planning description.

On the basis of the Organizational Interoperability Maturity Model for C2 (OIMM) [ 1 ], the Levels of Conceptual Interoperability Model (LCIM) [ 2 ], and the Levels of Information Systems Interoperability (LISI) [ 3 ], at least a collaborative level, from an organizational perspective, and a distributed level, from a system perspective, have to be achieved in order to be able to execute a joint planning process [ 4 ]. From a data perspective, the semantic (LCIM) interoperability is needed to provide a collaborative (OIMM) - distributed (LISI) level in the highest capability. The semantic interactive level (LCIM Level 3) means that data is shared through the use of a common reference model and content of the information exchange requests is unambiguously defined (see Figure 1).

Our present research aims to establishing a knowledge representation for improved planning automation that relies on Modeling and Simulation (M&S) interoperability frameworks as its foundational approach. The current major efforts in M&S interoperability are the SISO Coalition-Battle Management Language (C-BML) and the SISO Military Scenario Definition Language (MSDL) [ 5 ] [ 6 ]. They provide restricted semantic interoperability (mostly relying on the eXtensible Markup Language - XML format) which allows Command and Control systems and simulations to interoperate. One of the reasons behind the restricted semantics is that simulations need less information to generate behavior than what is needed to C2 planning. Since both standards aim to support interoperability among systems and simulations based on the structured XML metadata, their representational demands are comfortably restricted to the smaller information set than what is needed for a C2 planning system. Therefore, Command and Control planning systems cannot take full advantage of the available information until a more expressive approach is used to formaly represent it [ 7 ].

The main problem faced by a military planning system is to generate an adequate, feasible, acceptable, and complete plan that is also opportune [ 8 ]. In order to support planning automation it is a good practice to represent knowledge in a way that allows for pruning the search space. As a consequence, algorithms ideally have to work with the minimum knowledge that is necessary to produce solutions. This is especially true for the military domain, in which uncertainty is the norm and a plan is usually comprised by a large number of possible tasks whose interaction must reach the desired effects (end state). Also, each organization involved in the operation may have its own planning system, possibly applying a different problem-solving method.

With the development of a more expressive representation to describe the planning domain and the planning problem, it is expected that a planner will have access to more efficient pruning algorithms. This, in turn, will support the identification of solutions for larger problems, as well as to increase the ability to leverage most of the information available to the decision-making process.

Therefore, developing a knowledge representation model and an associated interoperability model are essential steps towards the automation of the planning activity, which is also a major step towards providing alternative Courses of Action (COA) that are reliable, efficient, and opportune. The present research investigates the use of a semantic planning layer, based on a mid-level task probabilistic ontology description as a technical solution for the contextualization of the planning problem. The proposed approach is depicted in Figure 2.

The proposed semantic layer is being developed to support the use of different planning systems in COA development based on a common context description. Section IV describes the layer in more details.

Semantics are essential to align planning automation with a shared intent, while also providing consistency in planning given the orders and requests issued by different organizations.

The paper is divided as follows. Section II provides background on the hierarchical planning process. Section III conveys a brief description of related research addressing automation strategies for operational planning. Section IV addresses the proposed semantic layer, while Section V provides an overview of COA modeling. Section VI describes the COA development based on the adopted methodology, and Section VII concludes this paper with a discussion on the current state of our work.

II. PLANNING PROCESS

The overall research in this work is grounded on the collaborative aspect of joint planning, and aims to support the Joint Operation Planning Process (JOPP) at the operational level of a joint operation [ 9 ]. We chose this process because it involves a joint planning effort within a hierarchical structure with a well established doctrine. Figure 3 shows JOPP from the research development’s point of view. The process was divided into six steps, each one with its own role and task to be achieved. The present paper addresses the third step, namely the uncertainty representation during the process of COA determination. For the purpose of this work, the representation of command intent and the description of causal relations will be considered as given. The remaining steps are beyond the scope of this paper.

The output of the third step, COA determination, is a representation of a Course of Action with a description of the Measures of Performance (MOP), Measures of Effectiveness (MOE), the planning constraints, and the possible states of the environment.

To produce this output, current decision support systems rely on frameworks that generate orders that are evaluated through simulations. The shared intent is developed via a C2 system GUI that normally generates a set of high level orders and requests that are saved to an exchange data model database. M&S frameworks make use of the SISO CoalitionBattle Management Language (C-BML) [ 5 ] message schemata to deliver the command intent, and rely on the SISO Military Scenario Definition Language (MSDL) [ 6 ][ 10 ] to describe the scenario and the operational domain in terms of spatial situation of allocated resources.

The work in [ 11 ] defined an interface between the C2 system’s BML output and a standard semantic planning language as the Planning Domain Definition Language (PDDL) [ 12 ]. In this scheme, the planning system receives a set of orders converted from the BML format into a more generic planning language, which enables the generation of the right context as a planning problem and a planning domain file.

As a result of the adoption of this scheme, many different planning systems have their own "translator" from BML to a PDDL-like language, usually not aggregating any advantage to the planning process since it does not improve planning agility. In our proposal, we focus on applying ontologies to support automated reasoning over the search space as a means to reduce it before sending the context information to the planning system.

In this approach, the planning system receives only the states, methods and operators that are relevant to the construction of a plan. Efficiency is sought that such this plan can only be generated under the defined constraints and preconditions, and must be in conformance to the desired effect.

III. RELATED WORK

Due to the large spectrum of existing initiatives related to interoperability among command and control (C2) systems, as well as among C2 simulation systems, only those of most interest to this study’s context are mentioned here. Initiatives such as the SISO C-BML [ 13 ] [ 14 ] and MSDL [ 6 ] have established the initial structure to support the interoperability among C2 and simulation systems, as well as are setting the standards for addressing the problem of translating the commander’s intent into a format that is suitable for simulation and planning systems. The NATO Modeling and Simulation Group Technical Activity 48 (MSG-048) is evaluating a series of technologies to promote such interoperability and is conducting experiments with multinational C2 and simulation systems since 2006 [ 13 ] [ 14 ].

Another important aspect is to find methods to analyze and evaluate COAs based on effects, as described in [ 15 ]. The Effects Based Operations planning significantly increases the number of alternative plans and the depth of evaluation. Therefore, appropriate metrics must be devised to support principled quantification of their relative merits. Generating plans that are aligned with the commander´s intent is a key aspect that may be achieved by the use of semantics during the order generation process. The study conducted in [ 16 ] presented results in which all planned orders verified by an ontology-based tool have shown inconsistencies. Such consideration indicates the necessity to utilize semantics in the planning phase to minimize the possibility of inconsistencies with the orders generated at the upper level of the command structure.

In the field of ontology generation for tasking planning, the study in [ 17 ] presented an ontology engineering process applicable to such problem. The methodology was straightforward and made explicit the need for breaking down the problem into small pieces, a known strategy in decision theory. The study supports the hypothesis that it is very convenient to manipulate small ontologies that would be integrated later in the process.

Initiatives such as [ 18 ] [ 19 ] describe the use of task ontologies to support pruning before the planning system receives the planning problem and domain. However, they are not pointing to the interoperability in multilateral application frameworks based on the SISO standards.

Gilmour et al. [ 20 ] present a solution using a semantic layer in multilateral frameworks to generate plans in accordance with a military ontology. However, the work focus purely in the semantic interoperability of tasks, and does not address the interoperability issue among different planning systems. Thus, in addition to a semantic layer, an ontology extension to support different planning systems has to be established, since each system is likely to have its specific language and a problem-solving method.

The work in [ 21 ] is closer to our approach and differs with respect to the implementation and to the ontology integration. While the authors developed a series of military ontologies in OWL language [ 22 ], our focus is on achieving interoperability with the reuse of existing ontologies. Another difference is our concern in representing uncertainty in a explicit and principled way, so our approach does address uncertainty representation and reasoning through a mid-level task probabilistic ontology.

IV. SEMANTIC PLANNING LAYER

Different hierarchical levels have to produce a joint operational plan, so different types of planning systems may be utilized throughout the operational campaign. The operational level works with higher level tasks (activities) and is not aware of the exact unity that will handle the task and achieve its desired effect, but it does know which effects will interfere with the desired end-state.

Effects modeling thus play a key role in determining which activities have to be executed in order to achieve the desired effects. It helps improving the tactical level task decomposition by ensuring that only the tasks with higher probabilities to lead to the desired goal effect will be planned at the lower level of the hierarchical chain.

To develop an approach that might handle the effects-based modeling we are proposing a Semantic Planning Layer, which is depicted in Figure 4. As can be seen in the figure, the Semantic Planning Layer is made of a Task Probabilistic Ontology, an Activities Reasoning Module, and a Planning Context Definition Module.

1) Task Probabilistic Ontology: In order to model the effects and to translate it into a lower level task decomposition, it will be necessary to develop a task ontology that can handle uncertainty. From our perspective, activities are tasks that are more abstract and need to be broken down into smaller tasks until reaching a primitive one. It is also necessary to describe the shared intent in a way that it can be related as desired effects and activities. This is the main reason of our interest in generating a BML ontology description.

Another important description is the domain ontology that will formalize the planning domain specification and interface with other domain descriptions. We are aiming to both describing the hierarchical planning concepts as well as to relate it with the COA description process. The end result will be a better description of the way the activities will be structured in phases and the establishment of a view from the operational perspective.

The mid-level Task Probabilistic Ontology is composed by four ontologies: BML Ontology (BML), Application Domain Ontology (ApplicationDomain), Planning Ontology (HPlanner), and COA Ontology (COA). It is being developed using the PR-OWL probabilistic ontology language [ 23 ] and aims to describe the connection between each ontology as well as the causal relations between the main concepts considered during pre-planning reasoning.

The constituent ontologies can be existing ones, which can come from the literature, gold standards, or a particular implementation. The basic premise is that an upper/mid-level ontology describing the core task planning information, and having principled support for uncertainty representation and reasoning will be capable to comprehensively convey all the necessary domain information for planning purposes.

Figure 5 depicts a partial view of the concepts described in the mid-level probabilistic ontology. The hierarchical planner ontology is a specialization of the planning ontology and can be more detailed if needed by a specific problem-solving method. In this scheme, mapping concepts among and between constituent ontologies can be seen as a way of ensuring interoperability from one problem domain to another (eg., from the BML-described commander intent to the Planning domain). 2) Activities Reasoning: The activities reasoning module executers four main steps:

Pull BML/MSDL campaign level orders - This step utilizes an already available BML service and no development will be made; Identify the activities to be planned through the probabilistic task ontology and by the analyst criteria (defined threshold for each phase (MOE)); Generate Situation Specific Bayesian Networks (SSBN) [ 24 ] to support the activities inference; and Export the activities list to be described by the Planning Context definition module;

After a succession of queries, a list with the selected activities will be sent to the Planning Context Definition module. The proposed algorithm is showed below:

3) Planning Context Definition: The planning context definition is the process of establishing the problem context to be submitted to the planning system. It is composed by three activities:

Planning Domain definition - After receiving the activities list the module will identify methods that decompose the activities and the operators; Planning Problem definition - The planning problem consists of the tasks to be decomposed and the initial state declared on the MSDL message; and

PDDL files generation.

After receiving the task list, the module has to describe the tasks with the constraints, the current state, and the proposed goal. Such description will then be translated into a PDDLlike format. Finally, the resulting files will be submitted to a domain-independent planning system that will address the planning problem. As depicted in Figure 4, the output are the two PDDL formatted files describing the Domain Problem and the Planning Problem.

V. COA MODELING

Military operations are generally described by phases and activities at the operational level, which are then translated into tasks at the tactical level. The development of Courses of Action follows a decomposition model in the Effects-Based Operations (EBO) paradigm [ 25 ]. The modeling effort aims to express a cause-effect relationship from the perspective of activities that will produce outcomes.

Figure 7 shows an example of a phase decomposed into activities and tasks. The arrangement of both the activities and the tasks may be serial, parallel or a combination of both. The task decomposition is a process used in hierarchical planning systems [ 26 ] [ 27 ]. In our approach, different hierarchical planning systems can receive shared intents and generate different plans that adhere to a mid-level ontology, based on their own problem-solving methods. Hierarchical planning systems were selected because they build plans by hierarchical decomposition that correspond to task models of human task performers. In that way, the generated plans will meet with human approval [ 28 ].

So, in our modeling we describe the COA in terms of phases, activities, tasks, and effects. Figure 8 shows the cumulative effects model we are using to generate queries about the planned tasks. Before sending activities to the planning effort, it is possible to identify the ones that are most important to reach the desired phase’s outcome.

The process of COA modeling demands a comprehensive method to develop the different ontologies to be utilized in the semantic layer. Our approach relies on ontologies for describing and updating the necessary information to support a planning cell from a military organization in acquiring and maintaining a high-level situational awareness. This requires a formal representation of concepts about time, space, actions, effects, resources, and uncertainty over a dynamic future.

Traditional ontologies do not have built-in mechanisms for representing or inferring with uncertainty, requiring extensions with new classes, subclasses, and properties that support uncertainty representation and reasoning. The PR-OWL probabilistic ontology language [ 23 ] and its newest version PROWL 2 [ 29 ] are written in OWL [ 22 ] and provide a consistent framework for representing and reasoning in domains with uncertainty.

The mathematical basis for PR-OWL is Multi-Entity Bayesian Networks - MEBN, which integrates first order logic with Bayesian probability. MEBN provides adequate formal support for representing a joint probability distribution over situations involving unbounded numbers of entities interacting in complex ways [ 24 ]. This is a major requirement to achieve principled representation of the multiple, multi-modal sensor input and their compounded interactions. MEBN represents domain information as a collection of inter-related entities and their respective attributes. Knowledge about attributes of entities and their relationships is represented as a collection of repeatable patterns, known as MEBN Fragments (MFrags).

A set of MFrags that collectively satisfies first-order logical constraints ensuring a unique joint probability distribution is a MEBN Theory (MTheory). As in any Bayesian approach, a MEBN model includes the a priori knowledge stored in local probability distributions. The inference process is triggered by one or more queries, which trigger a reasoner that applies Bayesian inference to calculate the marginal distributions.

During a campaign, as new information accrues, this process is used to calculate the posterior probabilities that represent the best knowledge possible to support new planned actions given the information available at the decision time.

VI. COA DEVELOPMENT

The COA development starts with the analysis of the activities to be delineated as tasks to the tactical level. Thus, it is necessary to have the operational description of the outcomes in order to reason about the associated likelihoods of reaching the desired effects.

In our model we describe the phases, activities, and effects that will produce the desired end state in a backwards description of the plan. That is, from the desired effect back to the task to be executed as seen in Table I.

The information received from the operational level establishes the COA description and the Domain description. The Domain ontology captures all the information regarding the physical aspects of the operation, and will be utilized to describe the scenario situation. The Effects, Activities and Tasks are described as individuals in our COA ontology (see Figure 9).

During the ontology construction we can use the modeling depicted in Figure 8, showing the cumulative effects to support the phase’s outcome reasoning. This part of the ontology can be modelled through the probabilistic representation available in PR-OWL. Basically, we model the causal relations in the same way a depicted in Figure 8, establishing a joint probability distribution that will allow reasoning on the available information regarding the current operation situation.

Figure 10 shows a MEBN fragment with only the effects portion of the ontology. The MFrag shows the structure, but not the individuals in the knowledge base. Resident nodes (yellow ovals in the figure) are the actual random variables that form the core subject of the MFrag. Context nodes (green pentagons in the figure) are boolean random variables representing conditions that must be satisfied to make the probability distribution of an MFrag valid. The reasoning occurs by executing a query to support the analysis during the tactical COA development. Thus, given a new set of effects to be reached, one can query the knowledge base for which task might have the greatest influence on a specific effect.

Using the data in Table I we can identify the impact from the Air Superiority phase on the accumulated effect. This takes into account the change in the quantity of a given task from a specific activity. We have modeled the knowledge base with two scenarios:

One task as the attack in the C2 Comm (Attack_C2Comm_03Bravo), two tasks as SEAD missions (SEAD_AAA_01Alfa), and one task as the attack in the Radar site (Attack_Radar_02Bravo). See Figure 11; and Two tasks as the attack in the C2 Comm (Attack_C2Comm_03Bravo), two tasks as SEAD missions (SEAD_AAA_01Alfa), and one task as the attack in the Radar site (Attack_Radar_02Bravo). See Figure 12.

In performing this analysis, one can assess the impact of another attack mission over the C2 Communications facilities with an expected increasing in the accumulated effect by 3.18%. This analysis capability allows for not only to decomposing the activities into tasks as expected for a planning algorithm, but also to identify the activities to be decomposed that will support the expected effect for each phase of the campaign. In the example, the answered query ?hasAccomplishedPhaseGoal (Phase1_Air_superiority_COA_02A) has not reached yet the 60% level defined threshold and other activities will be selected in order to generate the minimum expected outcome for the desired effect based on the model.

VII. CONCLUSION AND FUTURE WORK

The present work involves using a probabilistic ontology language (PR-OWL) to support task analysis and to provide a mid-level ontology as part of a layer between the intent description and the planning system that has to generate a Course of Action. Our approach aims to establish a knowledge representation layer to facilitate pruning the search space. It also verifies the activities that have to be sent to the planner in order to generate the plan that will contribute to reach the desired end state of the campaign.

As future work we have identified the need of improving the effects model to also show the secondary effects produced by the primary effects caused by activities. We also intend to fully implement the semantic layer and to integrate a planning system that is capable to take advantage of the approach. Finally, we plan to test and evaluate our results via a simulation testbed, which is current in development in a shared effort between the GMU C4I Center and the Brazilian Instituto Tecnológico de Aeronáutica.

The SSBN of the first scenario. The cumulative effect is 53.24%.

The SSBN of the second scenario. The cumulative effect is 56.42%

References

[1] T. Clark . and R. Jones , “ Organisational interoperability maturity model for c2,” in Proceedings of the 1999 Command and Control Research and Technology Symposium ., United States Naval War College. Newport: ommand and Control Research Program (CCRP) , June 1999 .

[2] A. Tolk and J. A. Muguira , “ The Levels of Conceptual Interoperability Model (LCIM),” in Proceedings IEEE Fall Simulation Interoperability Workshop . IEEE CS Press, 2003 .

[3] D. o. D. C4ISR Interoperability Working Group, “ Levels of information systems interoperability ,” C4ISR Architectures Working Group, March 1998 . [Online]. Available: http://www.c3i.osd.mil/org/cio/i3/

[4] L. S. Winters , M. M. Gorman , and A. Tolk , “ Next generation data interoperability: It's all about the metadata ,” Fall Simulation Interoperability Workshop, Fall Simulation Interoperability Workshop, September 2006 , orlando, FL.

[5] S. I. S. Organization , C-BML- PDG - Coalition-Battle Management Language , Simulation Interoperability Standards Organization (SISO) Std ., April 2011 .

[6] --, SISO-REF- 015 -2006 Military Scenario Definition Language (MSDL), Simulation Interoperability Standards Organization (SISO) Std ., September 2006 .

[7] A. Tolk and C. L. Blais , “Taxonomies, ontologies, and battle management languages - recomendations for the coalition bml study group ,” Spring Simulation Interoperability Workshop, Spring Simulation Interoperability Workshop, April 2005 , san Diego.

[8] DoD, Joint Operation Planning, joint publication 5 ed., Joint Publication Library, USA, august 2011 . [Online]. Available: http://www.dtic.mil/doctrine/new_pubs/jp5_0.pdf

[9] J. Publication , Command and Control of Joint Air Operations, January 2010 . [Online]. Available: http://www.dtic.mil/doctrine/new_pubs/jp3_ 30 .pdf

[10] (2011, September) Simulation interoperability standards organization . SISO. [Online]. Available: http://www.sisostds.org/Home.aspx

[11] M. Nazih and U. Schade, “ Einsatz der battle management language zur befehligung von einheiten in einem simulationssystem,” FKIE- Bericht , Tech. Rep. 174 , 2009 , wachtberg:FGAN.

[12] D. McDermott , M. Ghallab , A. Howe , C. Knoblock , A. Ram , M. Veloso , D. Weld , and D. Wilkins , “ PDDL - the planning domain definition language - version 1.2,” Yale Center for Computational Vision and Control, Tech. Rep ., October 1998 .

[13] J. Pullen , M. Hike , S. Levine , A. Tolk , and C. Blais , “ Joint battle management language (jbml) - us contribution to the c-bml pdf and nato msg-048 ta ,” presented at the IEEE European Simulation Interoperability Workshop , June 2007 .

[14] J. Pullen , D. Corner , N. Cordonnier , M. Mennane , L. Khimeche , O. M. Mevassvik , A. Alstad , U. Schade , M. Frey , N. d. Reus, P. d. Krom, N. LeGrand, and A. Brook , “ Adding reports to coalition battle management language for nato msg - 048 ,” in Joint SISO/SCS European Multiconference, Instambul, Turkey, July 2009 .

[15] C. Egan and J. Reaper , “ Course of action scoring and analysis , ” presented at the 12th International Command and Control Research and Technology Symposium, DOD CCRP. Newport , RI , USA: CCRP Publications, June 2007 .

[16] D. Gilmour and Z. M. Zhang , “ Determining course of action alignment with operational objectives,” presented at the Command and Control Research and Technology Symposium: The state of the art of the practice , June 2006 .

[17] A. Frantz and M. Franco , “ A semantic web application for the air tasking order,” presented at the 10th International Command and Control Research and Technology Symposium: The Future of C2 , June 2005 .

[18] B. Chandrasekaran , J. R. Josephson , and V. R. Benjamins , “ Ontology of tasks and methods ,” 1998 .

[19] A. F. Martins and R. D . A. Falbo, “ Models for representing task ontologies .”

[20] D. Gilmour , L. Krause , L. Lehman , B. McKeever , and T. Stirtzinger, “ Scenario generation to support mission planning , ” 2006 Command and Control Research and Technology Symposium , 2006 .

[21] I.-C. Hsu , Y. K. Tzeng , Y. J. Cheng, and D.-C. Huang, “ Semanticbased military scenario generation for mission planning , ” Journal of Convergence Information technology , vol. 6 , no. 4 , pp. 123 - 134 , April 2011 .

[22] W3C . (2004, February) Owl web ontology language . W3C Recommendation . [Online]. Available: http://www.w3.org/TR/owlfeatures/

[23] P. C. G. da Costa , “ Bayesian semantics for the semantic web , ” Ph.D. dissertation , George Mason University, 2005 .

[24] K. B. Laskey. ( 2007 , December) Mebn: A language for firstorder bayesian knowledge bases . Online. [Online]. Available: http://ite.gmu.edu/ klaskey/papers/Laskey_MEBN_Logic.pdf

[25] E. A. Smith , Effects Based Operations: Applying Network Centric Warfare in Peace, Crisis and War , DoD, Ed. CCRP, 2002 .

[26] Q. Yang , Intelligent planning: a decomposition and abstraction based approach . London, UK: Springer-Verlag, 1997 .

[27] M. Ghallab , D. Nau , and P. Traverso , Automated Planning Theory and Practice . Amsterdam: Elsevier/Morgan Kaufmann, 2004 .

[28] R. P. Goldman , “ Ontologies and planners a statement of interest ,” 2004 .

[29] R. Carvalho , “ Probabilistic ontology: Representation and modeling methodology , ” Ph.D. dissertation , George Mason University, 2011 .