Dependency Network Based Planning, Understanding the True Effects of Plans and Actions Brian Drabble Operations and Information Management Group (OIM), University of Bradford, School of Management, Emm Lane, Bradford, West Yorkshire, BD9 1JL bdrabble@bradford.ac.uk Abstract electrical power (EP) from a substation would impact any This paper describes an approach to intelligent planning physical nodes directly connected to it and have a depend- which employs a dependency network model to reason with ency on EP. While these direct links can be handled by the direct, n-order, cumulative and cascading effects. The de- conditional effects extension to PDDL, the effect(s) of the pendency network is a cyclic graph of nodes (persons, or- loss of EP could propagate beyond the direct links to affect ganizations, locations, resources, concepts, etc.) connected by weighted arcs that define the type and strength of de- nodes 2, 3, 4 or more dependency links away from the im- pendency between a node pair. The network can be em- pacted node. For example, if we have the dependency ployed as part of Mixed Initiative Planning (MIP) architec- chain “telephone exchange  transmission line 1  trans- ture or embedded as a constraint manager inside a fully au- fer station  transmission line 2  substation” and a plan tomated planning architecture. The network can be em- action directly affects the substation then what are the ef- ployed to firstly evaluate both the intended, cumulative and cascading effects of actions and secondly to critique plans to fects on the other nodes if any? This would need a series of identify their over dependence on a node or set of nodes. embedded “For Loop” within the conditional effects to For example, repairing the electrical substation will restore reason out to 2, 3, 4, etc. links but it would not be able to power to the hospital and the traffic light sensors in the area. handle the different nodes and dependencies encountered. The choice of repair teams 1 and 2 to conduct the repairs For example, if the telephone exchange has a backup EP means they are both dependent on two key roads to travel to the repair site. The paper provides details of both planning generator then what is the impact on the exchange of the architectures, an overview of the dependency model and ex- EP loss. If instead the node was a supermarket, then what amples of its use on several scenarios. is the impact. It would require a very large number of schemas to be developed to handle all the possible effects and maintaining them would be an even greater issue. Introduction These effects at a distance are referred to as indirect or This paper describes an approach to intelligent planning n-order effects of an action. N-Order effects can include which employs a dependency network model Drabble indirect, cumulative and cascading ones and can be both (2014, 2015) to reason with direct, n-order, cumulative and desired and undesired. It would be extremely difficult for a cascading effects. A dependency network is a cyclic graph user to write an action description in PDDL that was cable of nodes connected by weighted arcs where the weighted of reasoning over the complete set of situations in which an values represent the strength of the dependency between a action could cause direct and n-order effects amongst a pair of nodes. For example, the dependency of a plane on a group of inter-dependent nodes such as the four above. pilot, a telephone exchange on electrical power, etc. Using The remainder of the paper is as follows. The following a language such as PDDL (2014) action descriptions can three subsections provide details of the dependency net- be developed which describe the direct effects of actions. work function with specific emphasis on how it supports However, PDDL and other language struggle to represent reasoning with action preconditions and effects. The fol- effects which occur over time or are triggered indirectly by lowing sections provide further details of the dependency one or more direct action effects. For example, the loss of network and the use of the dependency network to support both an MIP and automated planning architecture. A sum- mary and future research directions section is as provided. Overview of a Dependency Networks Function be linked to the plant by a supplies relationship and the The purpose of using a dependency network is to handle plant to the customer by a financial support relationship. reasoning with n-order effects and use its analysis in two Given the plant is the only one in the area the dependency different ways. Firstly, to provide a plan critiquing and of the customer on the plant is higher than plant on the constraint management function that aids a user within an customer as it has more than one customer. The same rea- MIP framework. Secondly, to provide a guidance and con- soning applies to the consequence values should either be straint management function within an automated planning reduced by 100%. The ability to handle loops between architecture. An example of the former would be to identi- pairs of nodes or loops comprising multiple nodes allows fy that the plan has an over reliance on a single EP node the network to model feedback. This is where the initial hence making it vulnerable to execution changes. An ex- direct plan effect on a node is magnified by a chain of con- ample of the latter would be to identify that a partial plan sequence values that loops back to the initial plan effect was heavily dependent on using ground assets to move aid nodes. For example, if a power station’s EP output is de- supplies1 hence it would be better to select the “move by graded 30% and this leads to a 40% drop in the amount of air” action to expand a high-level plan node. coal that can be delivered to the plant by rail this would The dependency network does not reason about nodes in lead to less EP being generated and hence even less coal a causal way, hence does not need a user to provide rules being delivered. Eventually, the station’s EP output would to identify changes in the network. Rather it identifies the reach zero due to the feedback loop between EP generation type of relationship between a pair of nodes, its strength and its dependent supply of coal. and the consequence (in terms of the change in the node’s The ability to reason with direct and indirect effects, output, capability2, etc.) should the dependee node be de- looping and feedback within a dependency models pro- graded 100%. For example, EP substation (S1) is depend- vides both human and automated planners with a range of ent on two transmission lines (T1 and T2) to supply it with different ways to affect a node(s) capability. Firstly, a plan EP. If T1 and T2 supply equal amounts of EP to S1 then effect could directly exploit the vulnerability of an actor both links S1  T1 and S1  T2 would be labelled supply node to “seize and arrest” or a physical node’s EP output to and each would have a strength value of 5.0. If T1 was the “repair”. Secondly, a plant’s output of concrete can be primary source and T2 a backup, then the link values modified by exploiting the vulnerability of the dependee would be 10.0 and 0.0 respectively. The consequence value node(s) that supply cement, water or EP. As described ear- is used to propagate the positive or negative 3 effect on a lier if one of these nodes is a critical dependency then only node’s output/capability, etc. as a result of the direct ef- that one needs to be affected to halt concrete production. If fect(s) of a plan. In the case of a 100% loss of the input one of these dependee nodes has dependee nodes itself, provided by T1 then S1’s output would be specified by the (e.g. the substation that provided EP to the transmission input provided from T2. This example shows a simple pass line that supplies the concrete plant) then it could be af- through of a resource (EP) via S1 however, in most cases a fected by a plan action. This allows planners to construct node’s dependent inputs are either transformed or used to plans whose effects occur at one node in a dependency create another output or capability. For example, a machine network but whose intended effect occurs at a node 1, 2, 3, to mix concrete is dependent on inputs of cement and water etc. links away. The ability to identify and affect multiple and on EP to power the machine. If any of these 3 depend- nodes simultaneously provides planners with the capability ent inputs were reduced by 100% then the output of con- to exploit cumulative and cascading effects. The feedback crete would be reduced to zero regardless of the level of example shown in the previous section shows how a plan input provided by the other two. This allows the dependen- can cause an initial small effect on a node that can be mag- cy network to identify the criticality of a dependency and nified to achieve a much larger desired effect either direct- propagate the appropriate values through the network. ly or indirectly. This allows plans to be developed that are extremely well focused while looking to degrade network Dependency Networks for Effects Reasoning performance (insurgents, cyber-hackers) or provide the maximum return when improving performance (aftermath The network allows for nodes to be linked in both direc- of Hurricane Katrina or post conflict reconstruction). tions with different relationships, strength and consequence values. For example, a customer of the cement plant could Dependency Networks for Precondition Reasoning The network allows for the specification of plan precondi- 1 There would be a corresponding n-order effect of a high dependency on tions that are based on a node or node output capability. If the road segments, bridges, etc. that the vehicles travelled along. an action requires 500 gallons of fuel or access to a 2KV 2 Capability, Experience, Skill and Knowledge are non-quantifiable out- puts that have discrete levels “knowledge accountancy expert” transmission line, etc. then these can be specified as an 3 Actions such as Degrade, Dismantle, Dislocate reduce a node’s outputs initiating, maintaining or terminating precondition. The where Repair, Reinstall, Re-initialize increase a node’s outputs. dependency network provides search capabilities to identi- dependent score for each node in a network. The dependent fy whether this can be supplied by a single network node or dependee score for a node allows it to be ranked against or from contributions provided by multiple network nodes. other user selected nodes to identify its importance. The It also provides feedback on any modifications that may be scores can also be used to compare nodes based on the needed in the plan to provide the required level of input. ratio of their dependent or dependee scores. A screenshot For example, the start time window of Action 1 must be from Athena is shown in Figure 1. restricted from the range 3 -6 to 3 in order for it to return sufficient resources needed by the requesting action. Re- strictions can also be placed on open plan variables to stop them using a specific dependency node or nodes. Precondi- tions can identify a specific output or a capability level that a node must possess. For example, a truck has the capabil- ity to provide ground transport or the capacity of the truck to carry 2500lbs of cargo can be shared by multiple transport actions. The network model tracks changes to node outputs/capabilities as action that affect the node(s) are inserted or ordered within a plan. It does this by assert- ing a concept node into the network to represent a high Figure 1: Dependency Model of Frankfurt Airport level or primitive action and links it to the node(s) that satisfy its direct precondition or are impacted by an effect. Figure 1 shows a model of the cargo operations at Frank- furt Airport in terms of the dependencies between the air cargo companies (Lufthansa and Condor) and the groups Dependency Networks and infrastructure of the airport. The analysis displayed A dependency network comprises multiple intra and inter- middle right of Figure 1 shows that the Frankfurt Opera- dependent networks that reflect the Political, Military Eco- tions Support Center (the highlighted blue node) with a nomic, Infrastructural, Informational and Social (PEMSII) score of 310 has almost 25% more importance to the Air- (2016) aspects of the domain being modelled. Examining port functions than the airports Electrical Power Transmis- the interdependencies between nodes helps understand how sion Networks with a score of 241. While the Support Cen- the combined networks function, the most important nodes ter has the greatest dependency score, analysis of the con- overall and most importantly what effects a plan will truly sequence of losing either of these shows that a 100% loss have in a domain. The importance of a node can be identi- of the Transmission Network results in a far greater num- fied through a range of different measures: ber of nodes being affected and by far greater percentage  The cumulative weighted dependency that other change. Figure 2 shows the consequence analysis for the nodes have on it (dependent analysis) change to the Transmission Network as the percentage  The cumulative weighted dependency that a node change to the nodes impacted (displayed middle right). has on other nodes (dependee analysis) Dependency can be stated directly between any pair of nodes in the model and reflects the strength of the depend- ency that one node has on another. The strength of a de- pendency is measured using a scale of 1 – 10 where 1 re- flects a weak dependency and 10 a critical one. The direct dependencies are then used to define a transitive depend- ency between two nodes linked by one or more intermedi- ary nodes. For example, the direct dependency of the con- crete plant on the transmission line that results in the tran- sitive dependency of the plant on the EP substation. It is often the cumulative transitive dependencies that define the Figure 2: Example Consequence Analysis importance of a node and not the usually smaller set of A human or automated planner can use the dependency direct pairwise dependencies. Athena4 provides various and consequence scores to identify which parts of the network analysis algorithms to generate a dependee and model their plan must try to avoid directly affecting and if not what level of change could be acceptable. Secondly, it 4 identifies which dependee nodes of the Transmission Net- Athena is the name of the dependency analysis toolkit, system. works should not be affected directly or indirectly. Thirdly, Vulnerability Analysis: Ranks nodes based on how vul- it aids the planner in prioritizing tasks should weather or nerable they are in terms of their strength of dependencies. other issues affect airport operations. If resources are lim- Identifies which nodes are “easiest” to affect indirectly. ited then repairing, re-energizing the Transmission Net- work will have greater impact on operations than repairing Node Vulnerability: For a selected node, it identifies the damage to the functions of the Operations Center. percentage capability change if the dependee node is de- A planner can also use the model to identify the capa- graded by 100% and is applied to each node dependee. bilities and dependencies of nodes specified in plan pre- conditions or effects. Figure 3 shows the specification of Critical Node Vulnerabilities: For a selected node identi- fies if there is a dependee node that can degrade the select- information associated with the nodes representing the ed nodes capability by 100% and the percentage change to Condor Air Fleet and their Main Hanger. The three boxes the dependee node to achieve the 100% degradation. shown to the left define the capabilities of the Hanger to provide aircraft storage and repair facilities and its depend- Cluster Analysis: Identifies independent sub-networks ency on high voltage EP. The top window on the right de- whose links all have strength equal to or greater than a user scribes the link from the Cargo Fleet to the Hanger describ- specified value. ing the dependencies of the Hanger and the capabilities of the Cargo Fleet. The base of the window shows the defini- The following sections provide details of the use of the tion of the mapping of the dependency of the Hanger on dependency network to support both an automated and the Company. In this case, it is a financial one in that the MIP based view of plan generation. Cargo Fleet has a contract with the Hanger. This also shows the dependency of the Main Hanger on High Volt- Mixed Initiative Planning Architecture age EP which needs to be supplied via another node. Hence even though there is a direct dependency between When employed as part of a MIP based planning architec- the hanger and the aircraft it cannot be used by the planner ture the dependency network supports three primary func- to affect the supply of EP to the hangar. The lower window tions: Task Specification, Plan Development and Plan Cri- describes the link from the Cargo Fleet to the Main Hang- tiquing. Each is described in the following sections. er. This shows the obvious mapping of the hanger’s capa- bilities for repair and storage and the Cargo Fleets depend- Task Specification ency on these capabilities to operate. Task Specification aids the user in deciding what nodes should be the focus of the plan and the desired network behavior to be achieved. As stated earlier a node’s out- put/capability can be affected directly or alternatively indi- rectly by means of changes to one or more of its dependee nodes. Task specification also aids in identifying any nodes that should not be affected by the plan or the effect on them should be minimized. For example, a plan to replace one of the main EP transmission lines should not impact the airport operations center by more than 10%. Once the user has identified the node(s) to be affected a portal inside of Athena allows the user to specify these nodes, the level Figure 3: Example Attribute and Link Definitions of effect on the desired node, direct or indirect influence and any resource constraints. Figure 4 shows an example The dependency network also provides other additional set of specifications for a raid on a suspected insurgent safe insights that can be exploited by the planner. This aids in house by a Special Forces Team. The primary goal is to deciding the priority of goals/tasks and the plan(s) that should be developed to address them. Below is a list of the Raid the safe house and this has already been specified. analysis capabilities provided. The portal shows the specification of a secondary goal to create checkpoints around the area to control ingress and Effects Analysis: Ranks nodes based on the total change in egress of people, vehicles, etc. The task specification is the network if they were degraded 100%. Identifies which then passed to NETPlan planner. nodes have the greatest effect across the network. can use Athena to test different partially or fully developed plan options to understand what effects (desired and unde- sired) the plan has on the network, Essentially, the network acts as the initial state of the planning problem and the user is looking for guidance and feedback as to how well the plan matches against the goals specified. Based on Athe- na’s analysis the user could decide to re-assign tasks to a different resource due to a high dependency score, add an additional resource to reduce dependency or limit the im- pact of an effect, etc. Figure 4: Example Task and Goal Specification Plan Critiquing Once the user has developed the plan to the required level Plan Development of specification it can be imported into the dependency network. This is achieved by mapping the actions to a se- NETPlan provides the user with the ability to develop a ries of arcs that link the resource conducting the actions plan based on the tasks, constraints, etc. specified. Figure 5 and the focus of the action. For example, the action “Raid shows the plan developed for a raid on two safe houses and and Secure Safe House 3 Second Special Forces Team” the construction of the checkpoints to support it. Along the would be translated into an arc between the Second Special top of Figure 5 are a series of green diamonds representing Forces Team and the Safe House. In order to simplify the sub-goals and deadlines by which certain aspects of the mapping process Athena provides a series of ontology plan should be completed. NETPlan uses a timeline based based mapping tools to identify matching items in the plan approach to plan representation where each row describes and network. Figure 7 shows the Athena portal that dis- the actions assigned to the resource. Resource rows can be plays the mapping of the nodes in the plan to those in the related to one another hierarchy and can be “rolled up” and network, A previous step had already dealt with the map- hidden if desired. A user uses NETPlan to manually con- ping of resource names. The second line of the table shows struct plans using the timeline based representation. NET- the entry in the Athena Target column entitled Junction A1 Plan ensures that all time and resource constraints are whereas the corresponding NETPlan target is just A1. maintained and warns the user if any are threatened. The Based on information such as the capability of a road junc- user can then decide to alter the plan themselves or dele- tion can be degraded by blocking or reducing its flow, gate this to NETPlan to re-order or move actions on the Athena was able to deduce this was the probable mapping. resource timeline accordingly. If an incorrect mapping is generated, then the user can override it and Athena updates the ontology appropriately. Figure 7: Mapping from Plan to Network Terms Once all mappings are correct the plan can be imported into the network by means of additional nodes (if the re- Figure 6: Example Plan Development with Network Support source or focus of effect was not already in the network) Any action, resource, goals or sub-goal can be selected and and links. Figure 8 shows the insertion of the links between information regarding the item displayed via a portal. Fig- the Special Forces Team and the Safe house and the subse- ure 6 shows the timing, resource, precondition, effect, etc. quent analysis of the plan effects. The analysis pane shown middle right shows the 100% degradation of the safe house information for the action to Secure Safe House 3. The user and the indirect effects on the other nodes listed. is launched at noon on Friday when people are attending Friday prayers then the unintended consequences of the plan would be potentially significant. The ability to alert a human Special Forces planner as to the sensitivity of the launch time of the plan, was seen as a significant ad- vantage. Their normal training does not involve looking for such interactions and potential conflicts. Automated Planning Architecture When employed as part of an automated planning architec- ture the dependency network can serve the same three pri- mary functions of the MIP approach and provide the ability Figure 8: Action Insertion and Analysis to guide the selection of options for schema selection, vari- This is good plan as it targets the safe house and does not able assignment, precondition satisfaction, etc. Each is cause wide spread secondary effects. However, re-running described in the following sections. the dependency analysis identifies that the node with the Schema and Variable Selection greatest dependency is now North Baghdad SS1hence the The ability to select the appropriate schemas and variables question is why. Figure 9 shows the dependent analysis for that best match the needs of a plan is one of the key aspects SS1 and it identifies that one of its main dependents is the of any automated planning approach. The dependency radio network that the forces manning the roadblocks and model was incorporated into an automated planner called checkpoints are using. As the forces are strongly dependent Minerva to provide direct feedback to the planning algo- on the radio network and the plan is strongly dependent on rithm. This raises several important research questions. the forces then the plan is strongly dependent transitively The first was how to describe the task to the planner in a on the radio network. The importance of SS1 increased due form that captured all the relevant information. Below is a to the dependencies on it from the resources employed in task description that was developed for Minerva. the plan which is something that the plan developer knew nothing about. Identifying potential points of dependency task “SOF Raid”; introduced via a plan helps the user develop plans which vars ?verb = ?(or ?(type dverbs) ?(type rverbs)), are most robust against events (weather, etc.) or the actions ?noun, ?output, ?constraint, ?action, ?mechanism; of others. In this case selecting unit’s dependent on differ- nodes ent radio networks or tasking a unit to protect SS1 during 1 start; the raid to ensure continuity of EP for the radios. 2 finish, 3 action {{Degrade SF3 IC 100 “seizure and occupation”}{({V=Degrade, N=AD, O=TWK and C=50} {V=Degrade, N=IG1, O=Weapons and C=50})}; orderings 1 3, 32; end_task; In the case the task is to Degrade SF3’s (Safe house 3) in- formation conduit (IC) output by 100% and the method to be used is seizure and occupation. Tasks can be specified in terms of a method or in terms of the resource assigned. For example, instead of specifying the seize method the task could specify SOF via Helicopters and have Minerva Figure 9: Plan Critiquing to Identify Weaknesses select the method. The remainder of action 3 is a set of The critiquing process can also identify unintended conse- Meta-data that indicates the path through the dependency quences that the planners may not be aware of due to their networks the plan effects should follow. In this case the training, location or tasking. Dependencies change at dif- aim of seizing the safe house is to degrade by 50% the lo- ferent time of the day, in different locations, etc. One of the cations from which node AD (a person or group) can trans- effects of the raid plan was is to reduce traffic flow in the fer their working knowledge (TWK) and so degrade the locality of the safe houses. The same roads and junctions ability of insurgent group IGI to produce weapons by 50%. are also dependees of the local mosque. Hence if the raid is Essentially by removing SF3 as an information conduit the launched at 2.00am then there are few issues however, if it person AD cannot train people and this should impact on weapons production. The orderings information identifies effects {Status Security_Cordon $RaidLocation} = the task occurs between the start and end of the plan. Mi- complete at 1; nerva uses the same schema layout and structure as O-Plan end_schema; (1999) but it has been heavily modified to deal with the interactions with the dependency network. The schema vars structure describes the schema variables The action {Degrade SF3 IC 100 “seizure and occupa- that are used in the schema definition. There are various tion”} needs to be decomposed into a lower level action. restrictions or constraints placed on the schema variables. Similar to O-Plan, Minerva uses a Partial Order Causal For example, $RaidLocation has to be a physical type node Link approach to plan generation. The following schema in the network and $RaidingForces need to be an actor show one possible way to decompose the task description (person, groups, etc.). In addition, $RaidingForces need to and introduces some of the additional structures that were possess the capability or experience to conduct a Raid at a added to allow interaction with the dependency network. location. A node can be assessed in terms of its output if it is quantifiable (EP, flow rate, etc.,) or in terms of pos- schema ConductRaidtoDegradeLocation; sessing a capability, experience, skill or knowledge to a vars $verb, $percentage, $transport1, $transport2, specified level if it is not quantifiable (supervision, expert $mechanism, $checkpoint, knowledge of painting, etc.). This structure was developed $checkpointsrequired} = ?{type integer} to augment the simple capability and dependency frame- $RaidLocation = ?{type physical} work in Figure 3 to correctly capture these non- $SupportingUnits = ?{type actor, ?{or ?{capability quantifiable aspects of nodes in a form that can be used by “Conduct Ground Operations”}, ?{experience Minerva. The expands pattern matches the task specifica- “Security Operations”}}}, tion in the task schema if the types and constraints on the $RaidingForces = ?{type actor ?{or ?{capability schema variables match. The Meta-data from the task “Raid Location”}, ?{experience “Raid Loca- schema is simply tagged to this schema for checking the tion”}}}; plan does what it is tasked to do. expands {$verb $RaidLocation $output $mechanism The nodes statement describes the next level of the plan $percentage}; hierarchy. In this case the raid action comprises three sub- nodes actions. The first is to insert a “Move $SupportingUnits 1 action $checkpointsrequired Iterate action {Move $transport1 $checkpoint” and “Establish and Man $check- $SupportingUnits $transport1 $checkpoint}, point” action for as many checkpoints that are required in {Establish_and_Man $checkpoint} for the plan. This can be specified by the user or identified by $checkpoint over ?{type poten- Athena based on the level of impact the plan is desired to tial_checkpoints}, achieve. The remaining two actions move the raiding forc- 2 action {Move $RaidingForces via $transport2 to es to the location via a transport and then raid the location. $RaidLocation}, If at the end of the schema expansion a plan schema varia- 3 action {Raid $RaidLocation by $RaidingForces ble has not been assigned a value, then it is converted to a $percentage}; Plan State Variable (PSV). Minerva tags the PSV with all orderings 1  3, 2  3; of the appropriate type and constraint information so it can conditions be assigned later. For example, if there is a high dependen- compute_condition ?{fn_ask “number of cy score on the helicopter nodes in the network then Mi- check points required” ?{or undef ?{type nerva may choose to assign $transport2 to ground based integer}}} = $checkpointsrequired, vehicles so as to not increase the helicopter dependencies. compute_condition ?{fn_mult $check- pointsrequired 5} = $RequiredManpower, Precondition and Effect Analysis compute _condition ?{output “manpower” The conditions structure contains multiple com- $RequiredManpower units} = $Sup- pute_condition statements that result in queries to the de- portingUnits at begin_of self, pendency network. These are preconditions the dependen- compute_condition ?{output “manpower” cy network needs to address. The first identifies the num- 20 units} = $RaidingForces at begin_of ber of checkpoints required and the second identifies the self, total amount of manpower required assuming 5 persons per unsupervised {Location $RaidingForces} = checkpoint. The number of raiders is fixed at 20. Hence the $RaidLocation at 3, dependency network needs to fine one or more nodes that supervised {Status Security_Cordon $raid- have the required attributes as defines in the vars statement location] = complete at 3 from 1; and the required levels of output as described in the pre- conditions. The dependency network may return “No” as it cannot find the required node(s), “Yes” here is a list of Athena tracks changes in the network caused by plan ef- candidates and based on their dependency score they fects and alerts the Minerva if changes threaten a precondi- should be selected as follows or it could return “Maybe”. tion, schema choice, etc. so the planner can take appropri- In the case of Maybe it means there are changes to the ate actions. In this example the plan developed was to man outputs of certain nodes caused by already asserted plan 8 road blocks selected by Athena based on the local street effects and if the following changes are made to the plan layout and to raid 2 safe houses. Minerva inserted the sec- then the resources can be provided. For example, if an ac- ond safe house raid as raiding just one did not achieve the tion is ordered earlier in the plan it will return sufficient desired impact on the TWK output of AD. It also added a resources to allow the schema to be selected. It is essential- third raid to avoid that being used as an alternative when ly a dependency based Modal Truth Criterion based on the the first two were lost. It selected a helicopter insertion state of the dependency network. Minerva can assess each method for the raiders to minimize disruption and selected of the Maybe options and select the one that best suits the current context. Once selected in creates a link between the a 0500am start to avoid other collateral issues. action and the selected dependency node(s) to ensure the correct output level is provided. If the link is broken it is Summary and Future Work treated in the same way as a broken plan precondition. The effects structure describes the changes to a node This paper described the use of a dependency based net- output/capability directly caused by the action. The schema work model to support both an MIP and automated plan- below would be a candidate to expand the Establish and ning architecture. The model provides both human and Man Checkpoint action described in the previous schema. automated planners with the ability to truly assess the im- pact of action effects in terms of the both direct and n- schema EstablishAndManCheckpoints; order ones. This allows plans to be constructed that allow vars $Checkpoint = ?{type physical}, goals to be achieved by directly affecting a node’s output $AssignedUnit = ?{type actor}; or my affecting one or more of its dependees. The ap- expands proach has been applied to a variety of scenarios including Establish_and_Man $Checkpoint $AssignedUnit}; countering insurgencies, disaster and emergency manage- only_use_for_effects ment, logistics, etc. The current Cassandra and Minerva {Checkpoint $Checkpoint} = established; systems are being extended to allow reasoning with un- condition known nodes (those not instantiated to specific value) and compute_condition ?{output “manpower” 5 units} how they could be used to guide the planner as to which = $AssignedUnit during self, aspects of the planning problem to focus on next. Other compute_condition ?{output “electrical power” extensions include reasoning with probabilities with re- 500 units = $checkpoint during self; spect to the presence of a link or node in the network and effects the use of missing dependency information to guide sche- ?{output ?{change “traffic flow” -50 percent- ma and variable selection. age}} = $checkpoint during self; time_windows = 2 hours; References end_schema; PDDL. 2016, Planning Domain Definition Language. The effect statement states the action will result in a 50% https://en.wikipedia.org/wiki/Planning_Domain_Definition_Lang reduction in traffic flow rate during the duration of action uage (during self). This means after the action is complete the PEMSII. 2016, Political, Economic, Military, Social, Infrastruc- effect stops and the flow rate should increase by 50% un- tural and Information model of a system, entity or state http://pmesii.dm2research.com/index.php/Main_Page less another action’s effects impact it directly or indirectly O-Plan: Tate, A., Dalton. J. and Levine, J. 1999. Multi- at the same time. The same type of reasoning also applies Perspective Planning - Using Domain Constraints to Support the to the condition statements. This schema shows a change in Coordinated Development of Plans, O-Plan Final Technical Re- the level of the assigned manpower of 5 units and this will port AFRL-IF-RS-TR-1999-60. . only be allocated from the dependency node identified for Drabble, B. 2015. Dependency Based Analysis to Support Robust the duration of the action. Afterwards the manpower is Schedule Generation, Final Report, Naval Postgraduate School, reallocated back to the unit. The same applies to the need Contract N00244-14-1-0056 NAVSUP, Monterey, CA, USA. for 500V units for the checkpoint which is taken from the Drabble, B. 2014. Modeling C2 Networks as Dependencies, un- EP network as load. Once the action is over the load can be derstanding what the Real Issues Are. In Grant, T. J., R. H. P. Janssen, and H. Monsuur., Network Topology in Command and returned. The use of the self statement in a com- Control: Organization, Operation, and Evolution. pp125-151, pute_condition informs Minerva that the resource is allo- accessed May 21, 2015. DOI: 10.4018/978-1-4666-6058-8. IGI cated and then deallocated back to the dependency node. Global Press.