Scenario
Engagement Co-ordination Planning
Knowledge Elicitation
Technical Approach
Implementation
The EC Architecture
The SSA (Situation
Similarity Assessor) Agent
Innovation
Evaluation and Further Development
One of the most important planning tasks carried out by the commander is the planning of a coordinated engagement on a hostile force. Constructing and maintaining engagement co-ordination plans concerns allocation of resources to identified engagement tasks. A plan co-ordinates the use of resources in time and space besides making sure that various constraints are satisfied.
Plan construction is a pro-active activity where the objective is to inflict on a hostile force so much damage that it is no longer able to execute its mission successfully. The construction of EC plans is a very complex task and today commanders usually revert to standing tactical procedures and pre-planned plans. To support construction of engagement co-ordination plans, a multi-agent system has been designed and implemented. It assists the commander in constructing and maintaining plans. Agents use constraint satisfaction techniques in combination with uncertainty reasoning to support plan construction, while case-based reasoning is used for continuous assessment of a plan. An engagement co-ordination plan at this level of detail is tightly coupled to a detailed description of a tactical situation.
The scenario is a coastal anti-invasion scenario, where a landing force is heading towards the coast of Norway. Details of the scenario were agreed with the military to ensure military correctness.
An FPB squadron leader is given the role of Officer in Tactical Command (OTC) for the defending force. The mission objective is to prevent penetration and landing of enemy forces in his area of responsibility. To achieve his objective, he must engage the landing force and cause them so much damage that they fail to complete their mission. The objective of the landing force is to seize control in a suitable area, called the amphibious objective area, where they can disembark personnel and equipment. The OTC is responsible for generating and maintaining an engagement plan that coordinates the activities of the subordinate units participating in the attack.
The commander constructs an engagement co-ordination plan that specifies:
1. Engagement location, i.e. when/where the engagement will take place.
The Engagement location is decided at an early stage of the scenario.
2. Engagement tasks.
Engagement tasks constitutes the units in the hostile force that should be engaged, and the corresponding level of damage necessary.
3. The coordinated engagement plan.
The commander allocates resources to the selected engagement tasks.
The figure below shows an example of an EC plan displayed graphically to the user. The dashed lines indicate an engagement task allocated to a vessel within own force, and the line itself represent the missile trajectory. The label associated with the missile trajectory tells the type and number of missiles to be used on the trajectory.
Graphical presentation of an EC plan
An Engagement represent the fact that an enemy vessel is selected as a target with a required neutralisation probability. An EC plan contains a number of Engagements. Each Engagement may be elaborated into Engagement Allocations (allocation of a target to own vessels). Furthermore each Engagement Allocation may be further elaborated into Trajectories (the trajectories to be used by a vessel against a target).
The level of abstraction in a plan which is only elaborated down to Engagement Allocations is higher than the level of abstraction in a plan which is elaborated down to Trajectories.
The figure below gives an abstracted graphical description of what constitutes an EC plan.
EC Plan Representation
In order to acquire the military knowledge encapsulated within the facility, we conducted a series of interviews and scenario runs with military experts. The interviews covered the parts of the scenario relevant to engagement planning and the experts explained their reasoning while constructing EC plans. Besides, developers asked questions that made the experts explain explicitly the knowledge they applied. Additionally, we studied military procedures to complete our knowledge base. The figure below outlines the entire development process.
The Knowledge Elicitation and Prototyping Process
The knowledge acquired was initially expressed in natural language and categorised as constraints and uncertainty relationships. The textual description made it easy for experts to validate the knowledge.
The Informal constraints were formalised in predicate calculus and implemented as ILOG Solver constraints. The implemented constraints are traced via the formalised constraints back to the informally stated constraints. The uncertainty relationships are represented in Bayesian networks. For the implementation the VBS (Valuation Based System) has been used. VBS is able to represent and reason over probabilities in a Bayesian network. The dependencies in the networks are traced back to the informal uncertainty relationships.
Combining CSP and uncertainty reasoning
We contemplated an number of approaches to the integration of CSP and uncertainty reasoning and ended up with the following strategy. The uncertainty reasoning tool is used to compute the probabilities that a weapon of a specific type will hit a target of a specific type delivered from a specific platform using a specific trajectory. A constraint satisfaction technique is used to find an Engagement Coordination Plan that satisfy a number of hard constraints, including that the probabilities of neutralising the targets should exceed the specified limits. Since the reasoning techniques are applied in a sequence the combination of the techniques does not add to the complexity. To our knowledge this combination of the two reasoning techniques is novel.
Representation of position information
For the target allocation service a qualitative representation of spatial information was chosen. The representation is used to reason about valid trajectory entrance directions and thus, since the trajectories are geometrically constrained, valid allocations of engagements to own units. A qualitative representation has certain advantages. It focuses on essential distinctions and eliminates unnecessary details. Furthermore, spatial relations can be inferred or composed based on known spatial relations and spatial axioms, that is, inherent structural properties of the spatial domain. Finally, a qualitative representation of spatial information is also plausible as a cognitive model. For the EC domain a significant part of the spatial knowledge acquired and formalised was of the qualitative type.
Constraint Relaxation
Soft constraints are defined as constraints that do not necessarily need to be satisfied for a plan but are merely preferences. Hard constraints on the other hand are constraints which always need to be satisfied.
There are a number of different approaches to constraint relaxation. The approach we selected is to express the soft constraints as an objective function. A Boolean decision variable is associated with each constraint and the objective function is linked to the number of satisfied constraints. The objective function is maximised using a standard maximization algorithm. Constraints can be prioritised by weighting their impact on the objective function. The algorithm then works as follows.
Search for a solution as defined by the goal
For each solution found add the constraint that the value of the objective function must be higher for the following solution.
The solution found is the first solution which maximizes the number of constraints satisfied. An alternative to maximizing the number of constraints satisfied would be to minimize the number of constraints violated.
Search efficiency
The time used to find a solution, or determine that no solutions exist, depends on several factors. The most important are the number of vessels involved in the engagement, the constraints put on the missile trajectories, and the choice of the required neutralization probabilities.
The representation of the engagement problem in terms of problem variables, constraints and goals, is very important to the search efficiency. We made alterations to the representation of the goals which the search algorithm tries to satisfy and gained 10% performance.
Introduction of heuristic constraints gave the single most important contribution to increased search efficiency. On the WAP used, the search time was reduced to about one tenth of the original, i.e a reduction in search time by roughly 90%
Completing incomplete Engagement Coordination Plans
An EC plan may contain all the Engagement Allocations which are required with respect to the targets required neutralisation probabilities or only a subset. If it only contains a subset it is incomplete at one level of abstraction (with respect to Engagement Allocations). The user is free to provide a plan at any level of abstraction and completeness. The planner will provide a plan which is detailed and complete at all levels of abstraction. The incomplete and abstract plan provided by the user act as constraints on the final plan to be generated by the planner.
Optimizing EC Plans
Originally we introduced an objective function which maximizes the number of constraints satisfied. The final version of the EC Planner also contains objective functions for minimizing number of missiles used and maximizing target neutralisation probabilities. When these two objective functions are used all soft constraints are transformed to hard constraints since the optimization only makes sense when all soft constraints are obeyed. After the initial time used to find the first solution the user may at any time ask to get the best plan found so far. Furthermore, a plan found at any time is guaranteed to be an improvement of the previous plan found with respect to the optimization criteria selected by the user.
Comparing tactical situations
Monitoring the current tactical situation with respect to changes significant to an EC plan, we must be able to compare situations along characteristics which are important for a plan. Establishing the similarity between tactical situations is considered analogous to an indexing problem in case-based reasoning.
The similarity between tactical situations is expressed by a similarity function, which applies weights to the attributes of the situation to according for their significance in constructing EC plans, i.e. significant attributes are given high weights. The similarity function returns a numeric value in the range 0 to 1, 1 representing the perfect match. To calculate the similarity between tactical situations a Minkovski like function is used to calculate similarity between multivalued symbols, ordinal symbols, or taxonomies while Euclidean similarity is used on integers and real numbers.
Using the FUN approach the specification is described as a functional organisation of agents, i.e a Functional Unit (FUN). The figure below visualises the FUN established for the EC facility. The arrows indicate the direction of service requests.
The Engagement Coordination FUN
At this stage we are only concerned with the service responsibilities of the roles. Each service provided should be possible to trace back to requirements. Below follows a short description of the EC FUN specification, explaining the figure above:
The Commander is responsible for deciding when to construct a new plan, when to replan, and when/where to perform the engagement. The role is also responsible for the final plan and that it is communicated to subordinate units. Within the FUN the commander only uses services of the other roles.
The Planner possess the knowledge that makes him capable of constructing an EC plan. It requires a tactical situation and a partial plan as input.
The Archiver provide services for browsing an archive of plans and plan elements, creating of new plans and for storing and retrieving plans.
The Situation Assessor maintains plans. It provide services for monitoring tactical situations and notifying the client when it becomes significantly different from the situation planned for. Besides, it can locate the situation within the archive with most resemblance to the current situation.
The other roles within the figure are not part of the EC FUN, but provide services required by the FUN.
The Terrain Analyser provides services related coverage analysis and shortest path.
The Picture Compiler provide services related to the current WAP.
The EC Architecture
The next step is to develop agents with the necessary capabilities to play the roles within the FUN. The figure below shows the agents playing the roles of the EC FUN. All agents live within the CABLE environment and cooperate using the service mechanism. FIONA is the framework used for construction and implementation of the HCI.
The EC Agent Architecture
The mapping from roles to agents and the agents are described below:
The Engagement Coordination User Interface Agent (ECUIA)
The ECUIA is the agent that present results of plan construction on DOHP layers and provide dialogues necessary for the user to access and use EC facility services.
The EC Planner
The EC Planner plays the role of the planner. It provides the services for completion and elaboration of EC plans.
The Situation Similarity Assessor (SSA)
The SSA agent takes the role of Situation Assessor. It provides services used to assess tactical situations.
The EC Archiver
Provides and maintains a persistent archive of plans and corresponding information.
This community of agent represents an instance of the EC FUN, i.e. the EC Planner.
The figure below illustrates a client requesting the EC Planner to construct an EC plan. The client provide the planner with description of the situation to plan for. The arrow from the EC planner to the client indicates an EC plan is returned.
The EC Planner Agent
The EC Planner assists construction of engagement coordination plans. The EC Planner does not posses knowledge about when to construct an EC plan, but how to construct an EC plan. Its clients must decide when is the best time for construction of a plan.
The SSA (Situation Similarity Assessor) Agent
The figure below illustrates the SSA agent monitoring the perceived situation with respect to the situation planned for.
The SSA Agent
The objective is to support maintenance of EC plans. All comparisons and evaluations of situations are based on attributes significant to construction of EC plans. Each time the perceived situation changes, the SSA calculates the similarity function and returns a similarity report to its client. The value contained in the similarity report indicates the significance of that change with respect to the situation planned for. In the EC facility the client is the ECUIA, which presents similarity reports as a graph. The graph shows the value of the similarity report as a function of time. The client, i.e. the commander is responsible for deciding whether it is necessary to construct a new EC plan.
InnovationIn current CMSs (Combat Management Systems) there is or no automated support for constructing and maintaining EC plans. Today it is mostly carried out using manual means, i.e. browsing publications and using paper maps. The complexity of the task combined with the time available often leaves the commander with no option but to rely on pre-planned engagement plans or standing tactical procedures. The plans and procedures are often vague on how to attack complex AAW organisations.
The services provided by the EC facility support tasks difficult to perform manually in stressful and time-constrained situations. The system acts like a personal assistant, providing the skills necessary to execute tasks that commanders find difficult or tedious in the given circumstances, e.g. finding a plan that satisfies a large set of constraints. It helps the commander retain the initiative in the operation by being pro-active.
The commander is always responsible for making decisions while the assistant would provide advice. The behaviour of the assistant can be adjusted to the commander’s personal liking, e.g. the commander can adjust the priority of soft constraint.
Evaluation and Further Development
For the RTP to be successful it was important to focus on technology that coincide with the long-term needs of the industry and the military. Besides, the technology developed and demonstrated must be mature enough for being exploited operationally and commercially. The general objectives of the naval material commands are to:
reduce working expenses and maintenance costs,
improve exploitation of resources, and
increase the operational tempo.
Industry must develop technology that they can exploit commercially. The objectives of the material commands and the industry are mutually dependent. For the technology developed within GRACE to survive it must to some degree meet both. In the figure below we have tried to capture the relationships between technological capablities and maturity, the military benefits provided, and the probability for the technology to survive.
Working with the EC facility we have been able to show promising results both from a technological perspective and from a military perspective. What remains is to market these result to senior company management, other research and development projects, and potential customers.
Evaluation framework
The evaluation of the EC facility shows great potential for further exploitation. In that context we would like to pay tribute to the naval experts from the naval material command in Norway, we have had at our disposal through the project. They have, through discussions, execution of scenarios, reviewing of documents, and user testing, provided invaluable support. We believe this is a guarantee for the knowledge and the functionality of the facility to be very close to what the military needs to construct EC plans. This is also the feedback received from the user test carried out with respect to the evaluation of the facility.
Regarding the techniques applied within the facility the evaluation also shows promising results. The techniques are useful on complex decision problems where deterministic real-time behaviour is not strictly necessary. The facility is able to provide an acceptable solution well within the available time interval.
At the moment we are also discussing the possibility of having a version of the EC facility at the Naval tactical training school in Norway. This possibility was proposed as a result of the user testing performed on the EC facility. Using the facility at the tactical training school they will be able to evaluate the tool in operational use. Furthermore, they will get a feeling for the possibilities provided and to decide what is required by the commander to use the facility. Today they have no automated support for this kind of problem and the facility therefore represents a giant leap to them.
Another significant project within the Norwegian navy where we intend to use the results of GRACE is in the purchase of new frigates. These frigates will be equipped with an advanced CMS, where the mission planning support will be an important component. Knowledge about the military planning domain and of the technology that can be used to realise planning support tools are essential. With respect to exploitation of the advanced technology demonstrated within GRACE, this is more appropriate in time than the FPB project. Already, concepts and functionality for mission planning support from GRACE have been incorporated into the requirement specification and the high-level design for the CMS onboard the frigates. Whether we are able to get the Navy to acknowledge the level of sophistication of the GRACE facilities remain to be seen. One important factor is how we are able to market the results of projects like GRACE, i.e. its relevance and the military benefits achieved, the development and maintenance costs of the technology, and the extent of training required before they are able to use it properly.
The next generation of submarines within the Norwegian navy is also an interesting project with respect to exploitation of results from GRACE. This project is at a very early stage and it is too early to know very much about the concrete requirement of what planning support is relevant, but it is very likely that there are results from GRACE that can be used.
Finally, as part of the analysis work for the future development of a Command and Control system for the Norwegian Navy a demonstrator will be built showing future possibilities for acquisition, establishment and communication of maritime situation pictures.
 |
 |
 |
| Produced by: Peter Martin / Russell Gordon /
Mike Pockney Updated: 30 March 1999 Copyright Logica 1999 |
 |
