Ontology for the Intelligence Community 2009 (OIC 2009) 1 Course of Action Planning Ontology Timothy P. Darr, Ph. D., Perakath Benjamin, Ph. D. and Richard Mayer, Ph.D.  phases that are tailored to a specific domain. Abstract²T his paper describes an ontology to support course Qualitative MOPs and MOEs are used to describe plan of action (C O A) planning that provides an extensible framewor k states and outcomes. It is often the case that objectives are for modeling C O A plans consistent with A rmy and M arine Corp defined not in terms of fixed numeric quantities or ranges, but doctrine. T his ontology is structured into a core ontology that rather in qualitative terms such as: "reduce the number of includes definitions of common C O A planning concepts (activities, phases, outcomes, measures-of-performance, attacks against coalition forces", or "increase the level of measures-of-effectiveness, etc.), and multiple domain-specific activity in the central market during daylight hours." ontologies that extend the core ontology for specific types of plans The Deep Maroon1 ontology currently supports two types of (stability operations, counterinsurgency planning, infor mation reasoning: (i) utility-theoretic preferential or preference operations planning, etc.). A preference relation between reasoning and (ii) goal-directed forward and backward descriptions of the " plan state " using measures-of-effectiveness is chaining reasoning. introduced to allow subject-matter experts to specify a ranking over plan activities or phases from a specific H uman Social Preference reasoning provides a way to rank-order states C ulture Behavior (HSC B) perspective. T hese preferences can be from the perspective of a given community group used in the planning process to identify or prune black holes and (counterinsurgents, insurgent group, religious or ethnic group, blind alleys. etc.). An inference algorithm can use these preferences to reason about assessment of how a given activity will be Index Terms²Course of A ction Planning, Information perceived and can assist a planner in the identification of black O perations, Counterinsurgency Planning, Utility T heory, Preferential Reasoning, Q ualitative Reasoning. holes or blind alleys2. Goal-directed forward and backward chaining reasoning I. INTRODUCTION provides a way to reason about the desired trajectory of the plan over time (forward chaining), and given an end state, T HIS paper presents the initial design of a Course-of- Action ontology (COA-Ontology) that can be used to support course of action (COA) planning. This ontology determine a set of starting states that would result in that end state (backward chaining). In forward chaining, the sequence of activities that are available at each plan state can be applies to the COA planning processes defined for the United determined by matching activity preconditions with the States Army and Marine Corps for multiple domains, to current state and asserting the new state that results from the include stability operations planning [1], counterinsurgency application of the activity. In backward chaining, the possible planning [2] and information operations planning [3]. The core states that can achieve a given outcome are determined, ontology includes definitions of the common concepts and followed by the activities that can achieve that state. properties for defining COA plans, including: COAs, COA Interleaving forward and backward chaining with preference- activities, COA phases, measures-of-performance (MOP) and based filtering helps to mitigate the complexity of developing measures-of-effectiveness (MOE). and analyzing realistic plans3. The COA-Ontology consists of multiple sub-ontologies, each of which contains a small number of concepts and A. Ontology Design Goals properties and can easily be integrated into other ontologies. The design of the COA-Ontology strives to achieve For example, we have defined a measure-of-effectiveness extensibility, flexibility and reuse. Our experience is that (MOE) ontology that can be imported as a standalone many ontologies are monolithic and cumbersome; making ontology into other ontologies for the purpose of providing a them difficult to understand and difficult to reuse. An example common definition for representing MOEs. The urban of what the authors believe is a concise, well-defined ontology Counterinsurgency (COIN) ontology is an example of how to extend the core ontology to define activities, MOP, MOE and 1 The name coined for this system by analogy to the DARPA Deep Green force-on-force planning and execution management initiative [7] and the IBM This work was supported by the Office of Naval Research under Contract Deep Blue chess system. 2 N00014-09-C-0334. In the context of a COA plan, a black hole is a state that once you get Timothy P. Darr is a Research Scientist at Knowledge Based Systems into, you can never get out of. An example of a black hole is an activity that Incorporated, College Station, TX 77840 USA (corresponding author to leads to an inflammatory situation such as civil war or increased intra-militia provide phone: 979-574-3189; e-mail: tdarr@kbsi.com). violence. A blind alley is a state that is unproductive in that there is no Perakath Benjamin is Vice President for Research at Knowledge Based feasible next state or no path to a goal state. Unfortunately, in the COIN Systems Incorporated, College Station, TX 77840 USA (e-mail: context blind alleys often turn into black holes as you may not be able to pbenjamin@kbsi.com). retrace to an earlier state. 3 Richard Mayer is President of Knowledge Based Systems Incorporated, How the complexity is mitigated in this way is beyond the scope of this College Station, TX 77840 USA (e-mail: rmayer@kbsi.com). paper. Ontology for the Intelligence Community 2009 (OIC 2009) 2 is the W3C geospatial ontology [4]. This ontology consists of branch-and-sequence as shown in the establish civil control only two concepts (geo:SpatialThing, geo:Point), and five phase6. properties (geo:alt, geo:lat, geo:long, geo:lat_long,   The forward chaining reasoning supported by the COA- geo:location): the minimal amount of ontological Ontology can be used to reason from the initial state information to represent a geospatial region. From this represented by the candidate COA on the left-hand side, to the ontology, more specific geospatial regions such as polygons, activities that are possible at that state, to intermediate states ellipses, and points can be defined by extending this geospatial that are achieved by each activity, to an end-phase outcome. ontology. The same reasoning is possible treating each end-phase The COA-Ontology design principles are as follows4 outcome as an initial state. The backward chaining reasoning x Ontologies should have a well defined purpose and supported by the COA-Ontology can be used to determine support a well-defined set of use cases; what activities can achieve the end-phase outcome, backward x Ontologies should include the minimal number of through the states that enable the activities back to the initial concepts and properties to support the purpose; state on the left-hand side. x Ontologies should strive to be more than a simple taxonomy of domain concepts; and x When possible, allow for importing / exporting concepts and properties from / to other ontologies. We realize that the design principles described above can be very subjective, but we believe that they are useful as a starting point for ontology design. The purpose of the COA-Ontology is as follows: x To represent COA plans that can be incorporated into other tools / applications, or to be used as a communication medium for the plans across systems. x To represent concepts in the Human Social Culture Fig. 1 COA Planning Ontology Context Behavior (HSCB) modeling domain so that COAs may be assessed in a reusable, computer-process-able format Fig. 2 illustrates the identification of black holes and blind from the perspective of multiple interested alleys in a COA plan. Using the preference knowledge communities. specified by an SME for a particular community segment, an inference engine can identify activities and outcomes as B. Paper Organization infeasible or uncertain, respectively. This has the potential to The remainder of this paper is organized as follows. Section significantly reduce the search space as black holes and blind II defines the COA planning problem context. Section III alleys are pruned from consideration or identified for further describes the structure of the COA-Ontology family of investigation. ontologies. Section IV outlines the representation of measures- of-performance and measures-of-effectiveness. Section V describes the representation of COAs. Section VI describes the representation of preferences. Section VII describes inference support in COA-Ontology. Section VIII outlines conclusions and opportunities for future work. II. PROBLEM CONTEXT This section describes the context that the COA-Ontology supports. Fig. 1 shows a simplified example of a stability operations COA plan. This figure shows one of three possible COAs that are proposed to achieve a commander's objective5. Fig. 2 COA Planning Inference Support This COA consists of three phases: establish security, establish civil control and restore essential services. Each III. ONTOLOGY STRUCTURE phase is terminated by an outcome that serves as a milestone This section describes the structure of the COA-Ontology. for measuring progress of the plan. Each phase contains a Fig. 3 shows the structure of the core ontology and an sequence of activities that are performed to achieve the end- extension of the core ontology to support urban COIN COA phase outcomes. The activities can be sequential, as shown in planning. This organization allows users to import or use only the establish security and restore essential services phases; or those elements that are required for a given application, promoting flexibility and reuse. 4 Similar to the principles defined in [8]. 5 6 Per doctrine, three COAs are typically presented to the commander for It is also possible to have concurrent activities, though not shown in the approval. figure. Ontology for the Intelligence Community 2009 (OIC 2009) 3 The solid arrows represent ontology imports within the core This class has the property hasTimeStamp to indicate and urban coin ontologies. The dotted arrows across the core / the time at which the measurement was collected. urban COIN boundary represents ontology imports from the The measures-of-effectiveness ontology (measures-of- urban COIN ontology to the core ontology. effectiveness.owl) contains the definition of measures of effectiveness. According to COIN doctrine [2], a measure of effectiveness is defined as "a criterion used to assess changes in system behavior, capability, or operational environment that is tied to measuring the attainment of an end state, achievement of an objective, or creation of an effect." MOEs in the COA-ontology define the commander's objective (end- of-COA outcome), objectives to be achieved at the end of each COA phase, and objectives to be achieved after each COA activity is applied at a given state. The MOEs depend on a set of MOPs. The MOE ontology includes two classes: x Measure-­of-­Effectiveness - a subclass of COA-­ Fig. 3. HENIOMAP Core Ontology Structure Variable that represents a measure-of-effectiveness. The core ontology consists of six sub-ontologies contained This class has the property influencingMOP that defines the set of MOPs that influence the MOE. An in six OWL files that define the most general concepts and properties. The core ontology is completely self-contained and MOE can be views as a function that takes as input a set can be used as the basis for more specific COA planning of MOPs and generates a measure. The influencingMOP defines the arguments to the function. ontologies, promoting extensibility. The urban COIN ontology shown at the right of the figure is one such extension of the x COA-­Outcome - a subclass of IO-­Thing that represents core ontology. an objective or outcome. This class has the property The common ontology (common.owl) contains definitions hasMOE that defines the MOEs that describe the of general concepts and properties that are common to COA outcome. planning. The common ontology includes four classes: The activities ontology (activities.owl) contains the x IO-­Thing - a subclass of owl:Thing that is used to definition of a COA activity. The activities ontology includes attach properties and relationships that are common to a single class: all classes in the ontology. x COA-­Activity - a subclass of IO-­Thing that represents x COA-­Variable - a subclass of IO-­Thing that represents an activity within a COA phase. This class has four a variable that can describe some feature of a domain. properties: preconditionMOP, postconditionMOP, A measure-of-performance or measure-of-effectiveness previousActivity, subsequentActivity, and is a subclass of COA-­Variable. This class has two hasActivityOutcome. The preconditionMOP and postconditionMOP properties are used to define the properties: hasValue and hasValueDirection. The hasValue property is the actual value of the variable precondition MOP for applying the activity and the and can be one of the standard types (xsd:integer; state that results from applying the activity, xsd:float, etc.) as well as a qualitative value (see respectively. The previousActivity and subsequentActivity properties are used to define a below). sequence of activities to perform within a COA phase. x Qualitative-­Direction - a subclass of owl:Thing that represents a qualitative description (increasing, The activityOutcome property is the outcome that decreasing, stable) of the direction or trajectory of an results from applying the activity. COA variable. The course-of-action ontology (COA.owl) contains the definition of a COA. The COA ontology includes two classes: x Qualitative-­Values - subclass of owl:Thing that x Course-­of-­Action - a subclass of IO-­Thing that represents qualitative values (HIGH, MEDIUM, LOW, etc.). represents a COA. This class has two properties: hasPhases and hasOutcome. The hasPhases property The measures-of-performance ontology (measures-of- performance.owl) contains the definition of measures of defines the phases within the COA. The hasOutcome performance. According to COIN doctrine [2], a measure of property defines the commander's objective for the performance is defined as "a criterion to assess friendly COA. actions that is tied to measuring task accomplishment." MOPs x COA-­Phase - a subclass of IO-­Thing that represents a in the COA-ontology are effectively state variables that are COA phase. This class has four properties: used to define the pre- and post-conditions for an activity and hasNextPhase, hasPrevPhase, hasActivities and to be used as inputs to the calculation of MOEs. The MOP hasOutcome. The hasNextPhase and hasPrevPhase ontology includes a single class: properties are used to define a sequence of phases x Measure-­of-­Performance - a subclass of COA-­ within a COA. The hasActivities property defines the Variable that represents a measure of performance. Ontology for the Intelligence Community 2009 (OIC 2009) 4 activities within the COA phase. The hasOutcome property defines the outcome of the COA phase. The preferences ontology (preferences.owl) contains the definition of preferences over COA outcomes. A preference in this context is a relation between two outcomes in which one of the outcomes is preferred to the other outcome, given the perspective of a specific human social culture behavior (HSCB) perspective. These preferences are typically asserted by an SME while role playing a specific HSCB perspective or community group. For example, in an agricultural community in which there is little or no electricity, a COA whose outcome involves restoration of economic self-sufficiency via the Fig. 4. Measures of Performance and Effectiveness activity of building or restoring a canal system for crop irrigation, will be preferred to a COA in which the same A. Exa mple - Urban C OIN outcome is achieved via the activity of providing electrical Fig. 5. shows example MOPs and MOEs from the COIN power to the local market. The preference ontology contains a domain [2]. In this example, there is a single MOP, force single class: density; two MOEs, establish presence and increase level of x Preference-­Relation - a subclass of IO-­Thing that security; and a single outcome, increase level of security. represents the pairwise preference between two Force density is a measure of the amount of force in a given outcomes from the perspective of a specific community area. The establish presence MOE is a qualitative measure of group. This class has two properties: lessPreferred the amount of presence of U.S. and Host Nation (HN) forces and morePreferred. The lessPreferred property in a given area. This could range from military patrols (U.S. refers to the outcome that is less preferred from the only or U.S. and HN) or the establishment of police stations or perspective of the community group. The outposts. The reduce reaction time is a statistical measure of morePreferred property refers to the outcome that is the amount of time it takes to respond to a significant event in more preferred from the perspective of the community the area of interest (AOI). Each of these MOEs are a function group. of the force density, as well as other "state variables" (not KBSI is currently developing capabilities to reason about shown) contained in an Intelligence Preparation of the preferences of this kind using the application of Imprecisely Battlefield (IPB) such as the AOI, force structure and human Specified Multi-Attribute Utility Theory (ISMAUT) [5]. terrain in the AOI. The µincrease level of security¶ outcome is Preferences are used to model HSCB perspectives for the a qualitative objective that measures whether or not there was purpose of supporting the decision maker(s) and COA an increase in the level of security in a given area. This planner(s) in COA development, war gaming, comparison and objective is described by the MOEs, establish presence and decision making. reduce reaction time. IV. MEASURES-OF-PERFORMANCE AND MEASURES-OF- EFFECTIVENESS This section illustrates the relationship between MOPs and MOEs in more detail, as shown in Fig. 4. The namespaces for each of the ontologies are defined in the lower left of the diagram. An MOP has a unique timestamp and a value with a qualitative direction. An MOE is a specialization of an MOP with a set of MOPs that represent the arguments to a function that calculates the value of the MOE, given the values of the influencing MOPs. An outcome is described by one or more MOEs. Fig. 5. COIN MOPs and MOEs V. COURSES OF ACTION This section illustrates the relationship between COAs, COA phases, COA activities, outcomes and MOPs, as shown in Fig. 6. The namespaces for each of the ontologies are defined in the lower left of the figure. A COA consists of one Ontology for the Intelligence Community 2009 (OIC 2009) 5 or more phases. Each phase has an outcome and consists of a relationship between two outcomes, one of which is preferred sequence of activities and may have a previous and next to the other assuming a specific HSCB perspective. phase. Each activity has MOP pre- and post-conditions and an outcome. The precondition MOPs must be satisfied in order for the activity to be applied. Whenever the activity is performed, the postcondition MOPs are -determined. A. Exa mple - Urban C OIN Fig. 7 shows an example of a partial COA from the COIN domain [2]. Many of the details are missing, particularly the precondition and postcondition MOPs as described previously. In this example, there is one COA, two COA phases (one with Fig. 8. Preferences an outcome shown) and three COA activities. The COA, labeled COA-1 has an establish security phase and an restore VII. INFERENCE essential services phase, consistent with COIN and stability This section describes the inference supported by the COA- operations planning [1,2]. The establish security phase has an ontology. increase level of security outcome as described in the previous A. Class Subsumption section. The establish security phase consists of activities for establishing access points, performing a census and As much as possible, the COA-Ontology utilizes class establishing barriers. In this particular COA, the establish subsumption via Description Logics (DL) based class access points activity is succeeded by the perform census and definitions [6]. This section illustrates the COA ontology establish barriers activities, which can be performed in using an example from the COIN domain [2]. parallel. Fig. 9 shows a subsumption axiom for the MOP concept. This axiom states that every MOP is a concept such that there exists a hasValue relationship with an integer, float, boolean or qualitative value, and there exists a hasValueDirection relationship with a Qualitative-­Values concept, and there is a hasTimeStamp relationship with an integer. ‫ ݔ׊‬ ‫ݕ׌‬, ‫ ݖ‬ ݄ܽ‫݁ݑ݈ܸܽݏ‬ሺ‫ݔ‬, ‫ݕ‬ሻ ‫ ר‬൫‫݀ݏݔ‬: ݅݊‫ݎ݁݃݁ݐ‬ሺ‫ݕ‬ሻ ‫݀ݏݔ ש‬: ݂݈‫ݐܽ݋‬ሺ‫ݕ‬ሻ ‫݀ݏݔ ש‬: ܾ‫݈݊ܽ݁݋݋‬ሺ‫ݕ‬ሻ ‫݊݋݉݉݋ܿ ש‬: ܳ‫ ݁ݒ݅ݐܽݐ݈݅ܽݑ‬െ ܸ݈ܽ‫ݏ݁ݑ‬ሺ‫ݕ‬ሻ൯ ‫݊݋݉݉݋ܿ ר‬: ݄ܽ‫݊݋݅ݐܿ݁ݎ݅ܦ݁ݑ݈ܸܽݏ‬ሺ‫ݔ‬, ‫ݖ‬ሻ ‫݊݋݉݉݋ܿ ר‬: ܳ‫ ݁ݒ݅ݐܽݐ݈݅ܽݑ‬െ ܸ݈ܽ‫ݏ݁ݑ‬ሺ‫ݖ‬ሻ ‫݌݉ܽݐܵ݁݉݅ܶݏ݄ܽ ר‬ሺ‫ݔ‬ሻ ՜ ‫ݏ݂݀ݎ‬: ‫ݔ(݂ܱݏݏ݈ܾܽܿݑݏ‬, ‫ ݁ݎݑݏܽ݁ܯ‬െ ‫݂݋‬ Fig. 6. Courses of Action െ ܲ݁‫)݁ܿ݊ܽ݉ݎ݋݂ݎ‬ Fig. 9. MOP Subsumption Axiom B. Preferential Dominance The concept of preferential dominance is important to reasoning about preferences as it allows outcomes to be pruned very efficiently, thereby reducing the computational complexity, at very little cost, of searching through potentially very large outcome spaces. Intuitively, one outcome GRPLQDWHV DQRWKHU RXWFRPH LI LW LV ³EHWWHU´ WKDQ WKH RWKHU outcome along all the values of the variables that describe the outcomes. Fig 10 shows the axiom for value dominance. The atLeastAsGoodAs relation is the greater-than-or-equal-to operator for numeric values. For qualitative values, this Fig. 7. COIN COA relation GHILQHGDSSURSULDWHO\IRUH[DPSOHD³+,*+´YDOXHLV ³DW OHDVW DV JRRG DV´ D 0(',80 YDOue if the objective is to VI. PREFERENCES maximize the value of that variable. This section illustrates the relationship between preferences and outcomes, as shown in Fig. 8. A preference is a pairwise Ontology for the Intelligence Community 2009 (OIC 2009) 6 ‫݁݋݉׊‬1, ݉‫݁݋‬2, ‫ݒ‬1, ‫ݒ‬2  (‫ݏ݂݀ݎ‬: ‫݂ܱݏݏ݈ܽܥܾݑݏ‬ሺ݉‫݁݋‬1, ‫݁ݎݑݏܽ݁ܯ‬ െ ‫ ݂݋‬െ ‫ݏݏ݁݊݁ݒ݅ݐ݂݂ܿ݁ܧ‬ሻ ‫ݏ݂݀ݎ ר‬: ‫݂ܱݏݏ݈ܾܽܿݑݏ‬ሺ݉‫݁݋‬2, ‫ ݁ݎݑݏܽ݁ܯ‬െ ‫݂݋‬ െ ‫ݏݏ݁݊݁ݒ݅ݐ݂ܿ݁݁ܧ‬ሻ ‫݁ݑ݈ܸܽݏ݄ܽ ר‬ሺ݉‫݁݋‬1, ‫ݒ‬1ሻ ‫݁ݑ݈ܸܽݏ݄ܽ ר‬ሺ݉‫݁݋‬2, ‫ݒ‬2ሻ ‫ݏܣ݀݋݋ܩݏܣݐݏܽ݁ܮݐܽ ר‬ሺ‫ݒ‬1, ‫ݒ‬2ሻ ՜ ‫ݏ݁ݐܽ݊݅݉݋ܦ݁ݑ݈ܽݒ‬ሺ݉‫݁݋‬1, ݉‫݁݋‬2ሻ) Fig. 10. Value Dominance Axiom Fig 11 shows the axiom for outcome dominance. Dominance is defined for MOEs first and then outcome dominance is derived by reasoning over the set of MOEs that describe each outcome. One outcome dominates another outcome if each MOE that describes the first outcome dominates the second outcome. Any outcome that is dominated by another outcome can be pruned from a search space, since it would never be chosen as there is a better or more preferred outcome. ‫݋׊‬1, ‫݋‬2, ݉‫݁݋‬1, ݉‫݁݋‬2  (‫ݏ݂݀ݎ‬: ‫݋(݂ܱݏݏ݈ܽܥܾݑݏ‬1, ‫ܣܱܥ‬ െ ܱ‫ݏ݂݀ݎ ר )݁݉݋ܿݐݑ‬: ‫݋(݂ܱݏݏ݈ܽܥܾݑݏ‬2, ‫ܣܱܥ‬ െ ܱ‫݋(݁݋ܯݏ݄ܽ ר )݁݉݋ܿݐݑ‬1, ݉‫݁݋‬1) ‫݋(݁݋ܯݏ݄ܽ ר‬2, ݉‫݁݋‬2) ‫݁݋݉(ݏ݁ݐܽ݊݅݉݋ܦ݁ݑ݈ܽݒ ר‬1, ݉‫݁݋‬2) ՜ ‫݋(ݏ݁ݐܽ݊݅݉݋ܦ݁݉݋ܿݐݑ݋‬1, ‫݋‬2) Fig 11. Outcome Dominance VIII. CONCLUSION AND FUTURE WORK This paper has described the preliminary design and of an ontology for describing COAs and some inference rules for using preferential reasoning to prune the space of possible outcomes. KBSI is in the process of implementing this ontology and using it to reason about COAs that have significant HSCB characteristics. More information about the COA ontology, including access, can be obtained by contacting the authors. REFERENCES [1] "Stability Operations", Headquarters of the Department of the Army, Field Manual No. 3-07 (FM 3-07), October 2008. [2] "Counterinsurgency", Headquarters Department of the Army, Field Manual No. 3-24 (FM 3-07), Headquarters Marine Corps Combat Development Command Department of the Navy, Marine Corps Warfighting Publication No. 3-33.5 (MCWP 3-33.5), December 2006. [3] "Information Operations: Doctrine, Tactics, Techniques and Procedures", Headquarters Department of the Army, Field Manual No. 3-13 (FM 3-13), November 2003. [4] http://www.w3.org/2003/01/geo/wgs84_pos [5] White, C. C., et al  ³$ PRGHO RI PXOWL- attribute decision making and trade-RII ZHLJKW GHWHUPLQDWLRQ XQGHU XQFHUWDLQW\´ ,((( 7UDQVDFWLRQV on Systems, Man and Cybernetics, Vol. SMC-14, No. 2, pp. 223-229, 1984. [6] The Description Logic Handbook: Theory, Implementation, and Applications, Baader, F. and Calvanese, D. and McGuinness, D. L. and Nardi, D. and Patel-Schneider P. F. (eds), Cambridge University Press, 2007. [7] Surdu, J. R. and Kittka, K., The Deep Green concept. In Proceedings of the 2008 Spring S i mulation Multiconference (Ottawa, Canada, April 14 - 17, 2008). Spring Simulation Multiconference. The Society for Computer Simulation International, San Diego, CA, 623-631. 2008. [8] *UXEHU 75 ³7RZDUG SULQFLSOHV IRU WKH GHVLJQ RI RQWRORJLHV XVHG IRU NQRZOHGJHVKDULQJ´ International Journal of Human-Computer Studies, Vol. 43, Issues 4-5, November 1995, pp. 907-928.