An Interactive Planner for Tank Squadron Assaults

Abstract
A planner has been developed for planning assault tasks for a group of tanks. This planner is
intended for use in training novice commanders and for planning the actions of a group in
simulations. Because the notion of a correct solution varies widely between subject matter experts
and may depend on information unavailable to the planner an interactive approach has been taken.
The resulting system carries out analysis of the terrain to gauge its suitability for the assault and
applies a set of constraints to identify a solution appropriate to the terrain. At any stage the user
may override the automated planning and either select their own preferred solution or alter the
planning parameters to produce solutions more acceptable to their needs. The resulting system can
therefore be used as a fully automated planner, a user assistant, or simply as an input device for
the user’s plan. To achieve this it was necessary to provide graphical output of the results of each
planning stage and to model the progress of planning and the level of authority delegated by the
user for each step.
1. Introduction
Computer Generated Forces (CGF) are used in
battlefield simulations for training exercises, as
well as for operational analysis. The use of CGF
reduces the number of human operators required
and so reduces training costs, hence there is a desire
to increase the amount of automation. This requires
a computer to be able to plan complex activities.
However, users of planning systems tend to prefer
those that allow them to influence the planning over
systems which operate as a black-box 1.
Therefore our work has been to investigate how an
existing fully automated planner can be modified to
produce an interactive, or mixed initiative, planner.
The Broad Agents 2system developed between
1994 and 1998 at DERA Malvern in POPLOG
contains an automated planner for tank squadron
assaults 3. It incorporates terrain reasoning in
order to produce a plan to attack a specified
objective, within a defined area of operation
(typically 8km by 4km). The algorithms contained
in the original planner have been extracted and reimplemented
in Java. This should aid reuse since
Java is more widely used than POPLOG. Some
refinements and corrections have also been made. The
main planning control algorithm has been changed to
enable user interaction. It is a constraint-based planner
that relaxes the constraints according to a schedule
determined dynamically (described in section 3.4) until
a valid plan is found.
2. The Planning Task
A squadron typically consists of 9 to 12 tanks
organised into 3 troops. A squadron assault requires the
co-ordinated action of two groups of tanks. The first is
the fire support group (typically one third of the
squadron, i.e. one troop) whose role is to pin the enemy
down by firing onto the objective. The second is the
assault group, which takes a concealed route to a formup
position before breaking cover to attack the enemy.
The attack route should ideally be perpendicular to the
line of fire of the fire support group. This maximises
the length of time the support group can fire before it
has to stop due to the risk of hitting one of the assault
tanks as they approach the objective. The fire support
position should be within effective weapons range of
the objective. It should be a suitable position for a
troop to deploy hull down1 to the enemy, and there
should be concealed route to a hidden ‘form up’
point (FUP) close to the support position. The
position should be reasonably close to the unit's
current position to avoid lengthy travel.
Enemy Position
Fire Support Position
Fire Support
Axis代写英国硕士论文
N Assault Approach
0 1 2Km
Area of Responsibility
Figure 1. Assault Example.
An example is shown in Figure 1 with a fire support
position at the edge of a valley in the centre of the
map and an assault group approaching the objective
from the Northwest, using a nearby ridge as cover.
The planning task is therefore to generate a suitable
fire support position, with a form up point, and an
associated assault position where the assault group
will form up before launching their attack. For the
purposes of this planner we have assumed that the
enemy position is known and is about 500m square
and that the attacking squadron is at a single known
starting point.
3. Planning Algorithm
The planning process benefits from the fact that
there is a reasonably well defined set of potential
solutions. Once the area of interest has been
defined and discretised (typically by sampling the
heights every 100m) the proportion of positions
that are acceptable is relatively small. The principal
problem is the lack of an established way of
comparing the merits of different positions.
Personal preferences of well qualified subject
matter experts may lead to radically different
solutions.
The solution we have adopted is therefore to
provide the system with the ability to analyse
potential positions on the map for use as either fire
1 ‘Hull down’ means positioned so that only the
turret of the tank is visible, the hull being protected
from enemy fire by the ground directly in front of
the tank.
support or assault positions by producing a number of
cost maps related to different criteria. Cost maps relate
the value of each sampled location on the map to a
particular assessment criterion. These criteria represent
the factors thought to be important by subject matter
experts, such as concealment from view. Each point
can therefore be rated relative to others for each
criterion and the system is then able to select the fire
support and assault positions based on this analysis.
The planning process can therefore be viewed as a
constraint based one. Each criterion provides a
constraint on the possible positions that might provide
a solution. These constraints can also be used to
provide an ordering over possible solutions so that a
final decision can be made. For example a constraint
on the distance from the fire support position to the
objective could filter out any point not within 500m of
the optimum range and provide an ordering over the
acceptable points with those closest to the optimal
range being preferred. One of the constraints, the angle
between the fire support and the assault position, links
the two positions and its application depends upon
whether one of the two points has been identified and
fixed (either by the user or by the automated planner).
The planning process, whether carried out
automatically or by the user, consists of a number of
stages. First the basic terrain analysis needs to be
carried out, identifying how much of the area of
interest is exposed to the enemy and how much is
concealed. A route map is also generated to calculate
the cost of reaching each point from the starting
location, this includes remaining concealed as much as
possible. Further processing is done by the automated
system to try to identify which locations have the
potential to give good hull down fire positions for the
support group. Once this has been done positions
suitable for the fire support position and assault
position can be identified. This may be done in either
order depending on the preference of the user. The
automated system defaults to identifying a support
position first since this involves more complex
calculations.
The positions are identified by applying the various
constraints until only a few points remain and then
picking between them based on one of the ordering
criteria. In the case where the initial constraints do not
give any possible solutions some of the constraints
must be relaxed or removed until an acceptable
solution is found. This relaxation of constraints may
follow a fully automated schedule, described below, or
be controlled by the user.
3.1 Initial processing
In order to determine the fire support and assault
points the planner has to analyse the terrain to
construct a number of cost/constraint factors. To
determine hull down positions, the planner
constructs two inter-visibility maps. The first
determines what the enemy can see (to find
concealed positions). The second determines
positions that can see the enemy. Figure 2 shows
the terrain profile for the terrain shown in Figure 1
in the area of responsibility. The area marked at the
top of the map represents the enemy location and the
point near the bottom is the force’s current location.
From the diagram it can be seen that the enemy are
situated on high ground. Approximately 2km in front of
them a river valley runs across the friendly direction of
approach. The blue force is situated in the valley
behind a hill that conceals them from the enemy.
Figure 3 shows the exposure to view from the enemy
area of all other points on the terrain. This provides an
estimate of the total extent of coverage an enemy force
could achieve. The scale represents how well each
position can be observed, darker points represent
positions which can be seen better and from more
positions in the enemy area. White areas are concealed.
The exposure map represents the aggregation of the
visibility from all the positions within the enemy area.
During the construction of these visibility maps, a
heuristic line-of-sight (LOS) calculation is used to
improve performance. A feature of this heuristic is that
the visibility of intermediate points along the ray is
generated. Thus to obtain the visibility of all points
along a line, only one LOS call is required.
Figure 4 shows how visible the enemy area is from
other terrain points. Again, darker spots indicate
positions that can see more of the enemy area and are
therefore more likely to be useful. Note that this map
is very similar to Figure 3. The interesting points occur
at the limit of what the enemy can observe; this is
Figure 2. Terrain Profile.
Figure 3. Visibility from the enemy area
where the visibility becomes asymmetrical. These
maps are the basis for further processing by the
automated system to generate candidate positions
and filters related to constraints. They are also very
useful for a user as they give an insight into the
problem, revealing the extent to which the enemy
position can see and fire into the surrounding area.
The planner must also consider the availability of
routes to possible fire support or assault locations.
As there are a number of points to be considered
and these points could change from re-planning; it
is more efficient to build a complete route matrix
for the terrain area than to generate routes
separately for each point. Dijkstra’s algorithm is
used to generate a route matrix taking into account
gradient, distance, and concealment. Two
constraints can prevent a position being considered,
the gradient being too steep for vehicles to travel
over or the point being too exposed to the enemy.
Exposure at long range is discounted to represent
the fact that exposure a long way from the enemy is
generally more acceptable than exposure when
closing in on the enemy position. This maximum
exposure threshold can be altered as one of the
filters described below. Routes that meet the
exposure and gradient constraints are given a cost
value depending on a weighted combination of
distance travelled and exposure to the enemy.
Figure 5 shows the route calculated for this
example, positions in white indicate ground which is
either too steep to drive up, or too exposed to the
enemy. Darker areas have a higher cost. This shows
that most routes pass through the narrowest portion of
exposure, to the centre right of the area.
3.2 Producing fire support candidates
A user may well operate solely from the information
contained in the exposure and visibility maps but the
automated system needs to process them further before
it can generate fire support points. The maps it derives
from these basic visibility maps are used to generate
and filter candidate points, the parameters used can be
adjusted to generate or reject more points.
To generate fire support candidates three cost maps are
used. The first, known as the weighted map, identifies
single positions with a potential to be ‘hull down’ and
therefore be part of a supporting fire position. This
map is calculated by combining the exposure (e) and
visibility (v) using a weighting factor (w) using the
following equation:
weighted map value = (max(0,v-we))v(1-we)
The resulting value is non zero only for points whose
exposure is less that the visibility of the enemy area
multiplied by the weighting factor and assigns high
values to well concealed points with good visibility of
the enemy position. The resulting map with w = 1 is
Figure 4. Visibility of the enemy area. Figure 5. Route Matrix.
shown in Figure 6. Note that a range cut-off has
been applied to reduce the number of calculations.
The weighted value gives a good indication of
individual points that would make suitable tank
fighting positions. Suitable fire support positions
should contain both a reasonable number of points
and points with high quality (good visibility and
low exposure). This is because fire support will be
given by several tanks, each of which should ideally
have a number of alternate firing positions within
the area.
The automated system identifies areas with a
number of high quality hull down locations by
making the (quality) map shown in Figure 7. This
represents the number of points in the weighted
map above a quality threshold within a region. To
identify those regions that have a large number of
potential points the average of the weighted map
values within a region are calculated as shown in
Figure 8. This shows a large number of positions
where there would be some (fairly low quality)
points and a few places where many more points
are available. These quality and quantity maps are
used as the basis for the generation and filtering of
fire support candidates described below.
Figure 8. Average fire support value for a
group ("quantity map").
Figure 6. Potential individual fire support
positions ("weighted map").
Figure 7. Points close to high quality fire
support positions ("quality map").
3.3 Producing assault position candidates
Potential points for assault form up positions are
generated by a simple process based on the
visibility map. The system locates the cover break
points, places where vehicles would be concealed
from the objective but the next closest point to the
objective is exposed. If an area big enough to
assemble the assault group behind this point is also
concealed the centre of the area is marked as a
potential assault position. Positions that do not have
a trafficable route direct to the objective are
rejected. The candidates are shown in Figure 9.
3.4 Applying the constraints
The fire support position candidates are filtered by
a number of constraints. The quality map is
produced using a quality threshold and the quantity
map with an appropriate threshold gives another
filter. The concealment weight used to generate the
weighted map can also be considered to be a
relaxable constraint. If it is changed then the quality
and quantity maps must be re-generated. The points
are also filtered by range (points must be within an
allowed value of the optimum range to the
objective). Further filtering is applied by checking
for the existence of a concealed form up point close
to the selected fire support area with a route to it that
has a low level of exposure to the enemy. Additionally,
if an assault point has been selected an angle constraint
can be applied limiting positions to be within a
specified number of degrees away from the 90 degree
optimum relative to the assault position. In most cases
the most pessimistic filter settings will remove all
possible candidates, indicating that a compromise must
be made by relaxing some of the constraints.
The automated constraint relaxation schedule operates
by attempting to identify the problems which are
causing the plan to be unacceptable and either relaxing
the appropriate constraint or, if that is not possible,
relaxing another constraint which will increase the
possible option set and hopefully provide an acceptable
option. Each constraint therefore has a nominal starting
value and a minimum (or least restrictive) value.
The algorithm first generates the maximal set of points
that could be considered (shown in Figure 10). This is
effectively the result of applying all the filters in series
with the filters set to their least restrictive possible
values. If the result is the empty set then no solution is
possible; otherwise the resulting set of all points which
could conceivably produce a working plan is used as
the starting point for further calculations. The
Figure 9. Assault Form Up Position candidates,
shown in black over the exposure map.
Figure 10. All possible Fire Support Positions,
shown in black over the terrain profile.
Generated by setting every constraint to its
minimum value.
automatic constraint relaxation scheme operates by
first running all the filters in parallel to identify the
most restrictive filter (the one with the fewest
possible candidates as output). The constraint
applied by this filter is relaxed if it is not already
set to its least restrictive value. If the most
restrictive filter cannot be further relaxed the next
most restrictive filter is tried until one which can be
relaxed is found. The filters are then re-applied in
series to see if there are now some candidate
solutions admitted by the new constraint set. Once
some options are available the automated system
ranks the points by quality (see Figure 7) and
selects the point with the highest value as a fire
support point.
This represents a very simple search for a solution
in the space of possible constraints; each constraint
is treated equally with no consideration of how
important they are in the domain.
After selecting the fire support position the assault
form-up position is chosen (if it has not been
already). First the set of assault candidates is
filtered by applying the angle constraint which
ensures that the two points are as close as possible
to being perpendicular with respect to the objective.
The angle constraint can be relaxed to its minimum
value. The remaining candidates are ranked using a
combination of the route cost to that point and the
weighted distance to the objective. This favours the
selection of points that are close to the objective but
easy to reach from the start. The first point in the
ranked list is selected.
If an assault form up position cannot be selected for
the chosen fire support position, even after relaxing
the angle constraint, then an alternative fire support
position is selected from the filtered candidates that
have been ranked by quality.
4. User interaction
There are a number of ways in which a user can
operate the system. They may choose to select the
points themselves, based on the cost maps
calculated by the system. Or they may choose to
use varying degrees of advice from the automated
planner. The user can examine potential fire
support and assault positions and may choose to
"lock" them indicating that the automated planner
may not change this particular choice. The user
may then choose to let the system select the
"unlocked" positions, by running the automated
constraint based planner. The user can choose to
allow the system the freedom to relax the
constraints or they may require it to simply report
the failure and allow the user the freedom to adjust the
constraints as they see fit.
The key requirement for user interaction is that the user
has the ability to investigate the problem in their own
way and to mould the solution to suit their own
preferences. To allow the user to do this the system
must supply a number of tools that allow the user to
gather information about the problem on which to base
their decisions. These tools take several forms.
Primarily the user is presented with a map-based
display showing the area of interest for the operation.
Figure 11. Graphical plan output.
This shows the lie of the land in a contour plot and
the positions of the enemy (objective) and friendly
forces (start). Once some points have been
generated the critical points in the plan (Fire
support position, assault form up position and
support form up position) and routes to them are
displayed. This is shown in Figure 11. The user can
gain information about particular locations
(displayed in a separate window - see Figure 12)
and they can choose to fix the selection of some of
the points or move them themselves. Once a
candidate plan has been generated a separate
window displays a textual description and critique
of the plan. This indicates the important features of
the plan and allows the user to quickly identify any
outstanding concerns they may have. A sample
output is shown in Figure 13.
Additionally the user may access cost maps, or
filtered candidate solutions that give a graphical
display of the relative merits of different positions. The
cost maps are those described above, and shown in
Figures 3 to 8 while the filtered candidate solutions are
the potential fire support or assault positions after the
application of specific filters. This can provide
valuable feedback to the user on which constraints are
causing trouble and may need to be relaxed. The user
can control the values used in the filters by using the
panel shown in Figure 14.
4.1 Representation of planning process.
The intention behind the new implementation was to
permit its use as a fully automated planner and as an
evaluation tool under user control with a varying
amount of control taken by the user. This required the
clear representation of what had been done and by
whom as well as a clear notion of who had control for
each step, the user or the planning system.
The three main points to be chosen (the assault form up
and the fire support position with its own form up
location) can be locked in place by the user. If any of
these points are not locked then the planner will choose
what it considers to be the best. Therefore the locking
of points will change how the planner operates in terms
of selecting points. For example, if the fire support
position is locked but the corresponding fire support
form up position is not, then the planner must go
through a number of calculations in order to choose
one that is concealed and suitably close. The user can
also specify whether the planner should choose the fire
support position before the assault form up position, or
vice versa.
The other way that the user can guide the planner is to
interact with the filters that apply the constraints. For
each filter the user can indicate whether the planner has
the authority to relax the associated constraint(s). The
Figure 12. Information window showing values
for the selected FSP (see Figures 11 & 13).
Figure 13. Textual description of a plan
Figure 14. Constraint value controls, showing
initial values.
user can also change the initial values for the
constraints and so change the order of exploration
of the search space. This is particularly useful when
the user feels that relaxing one constraint rather
than another will yield a better result. After each
run of the planner the user can reset the values used
by the filters.
Each run of the planner will lead to the production
of a plan, or failure to do so. Success may require
several relaxation steps. Currently there is no way
for the user to choose which constraint is relaxed at
each step without indicating that every constraint
cannot be relaxed, and then relaxing one by hand
and re-running the planner.
5. Related Work
TRIPS (the Rochester Interactive Planning System)
5is a fully functional problem-solving assistant in
a logistics domain. It is used by a human manager
to collaboratively produce plans for crisis
situations. It consists of three groups of
components. The first allows for multi-modal
interaction, parsing input into communicative acts
and converting output into both graphics and
speech. The second group deals with dialogue
management and includes a Conversational Agent
and a Problem-Solving Manager, which interfaces
to the third group, specialised reasoners. Treating
interaction as a dialogue provides context for rules
in the Conversational Agent, which identify
possible interpretations of user input and plan a
response to each. Our system performs the same
role as a specialised reasoning component in the
TRIPS framework, we do not have complex parsing
and problem management layers although it could
be an interesting extension to our work to interact
in such a way. We rely on the user interacting via
the map, dialogue boxes and the mouse for input
and have a simple map display and a fixed format
reply dialogue. We have found it useful to
incorporate a model of the planning process and
how much the automated system can do without the
user, as TRIPS does.
Agents are often used to represent users interacting
with planners 6,1and although it is not
constructed as one at the moment we could
consider re-configuring the planner as an agent
planning community. The main advantage of this
would be in the ability to re-use parts of the
planner, such as the concealment map generator
and route finder, in other planning systems. One
difficulty with this is in the radically different
response times and needs of users and automated
systems. It has been suggested by Payne et al 1that
agents representing such planning components need to
be able to describe how they can interact with a user so
that appropriate agents for the way a user intends to
interact with the system can be identified.
6. Discussion and Future Work
The system described has taken a previously closed
planner and opened it up to user input and
involvement. This has been successful in not only
providing a fast automated planner but in providing a
tool to support understanding of the problem by the
user. We have found it valuable to have the
visualisation tools to help understand the problem and
for evaluating the performance of the automated
planning components.
The resulting planning system has been shown to a
subject matter expert and the planning output was rated
as very satisfactory. It was felt that users would find it
a big step from current paper map and pencil
approaches to a computer supported option but that the
ability to change the level of control would help user to
understand the system.
We intend to re-integrate the new planner with our
agents 4to enable them to execute a plan generated
by this system. This may require additional capabilities
to assign appropriate vehicles to each group and to
specify the way in which the assault is to be coordinated.
7. References
1Payne, T. R., Sycara, K. and Lewis M. Varying
the User Interaction within Multi-Agent Systems.
Proceedings of the 4th International Conference
on Autonomous Agents, June 2000, Barcelona,
Spain, pp 412-418. ACM press ISBN 1-58113-
230-1
2Hepplewhite, R. T. and Baxter, J. W. Planning
and Search Techniques to Produce Terrain
Dependent Behaviours. Proceedings of the 7th
CGF Conference, May 1998. Orlando Florida
3Baxter, J. W. and Hepplewhite, R. T. ‘Real Time
Planning and Execution for a Hierarchy of
Battlefield Simulation Agents’ Proceedings of
16th UK Workshop on Planning and Scheduling,
December 1997, ISSN 1368-570 pp 145-152
4Baxter, J. W. and Horn, G. S. 2000.
Representing and Executing Group Tasks.
Proceedings of the 9th CGF Conference May
2000 Orlando, Florida pp. 443-449. ISBN 1-
930638-07-6
5Ferguson, G. and Allen, J. F. TRIPS: An
Integrated Intelligent Problem Solving
Assistant. Proceedings of the 15th National
Conference on Artificial Intelligence
(AAAI98), July 1998, Madison Wisconsin,
pp. 567-572 ISBN 0-262-51098-7
6Decker, K. Coordinating Human and
Computer Agents. In W. Conen, and G.
Neumann, editors, Coordination technology for
Collaborative Applications - Organizations,
Processes, and Agents. LNCS #1364, pages 77—
98, 1998. Springer-Verlag.
8. Acknowledgements
This work was funded by Technology Group 5 (Human
Sciences and Synthetic Environments) of the MOD’s
Corporate Research Programme.
© British Crown Copyright 2000 / DERA
Reproduced with the permission of the controller of
Her Britannic Majesty’s Stationery Office