> ![](media/image1.png){width="2.7506944444444446in"
> height="0.42986111111111114in"}
>
> Operated for the U.S. Department of Energy by
>
> **Sandia Corporation**
>
> Albuquerque, New Mexico 87185-1110

*date:* April 28, 1999

*to:* Sabina Jordan (MS 0780)

*from:* William Hart (MS 1110)

*subject:* Opportunities for using Parallel Learning Algorithms on the
Next Generation Security Simulation Project

### Abstract

> The memo provides an overview of the different ways that parallelism
> can be exploited to solve learning problems associated with the Next
> Generation Security Simulation (NGSS) project. We begin with an
> overview of the goals of the NGSS project and then discuss the types
> of learning problems that need to be solved to model human behavior in
> the NGSS simulator. We cast these learning problems as optimization
> applications and discuss their characteristics. Finally, we discuss
> four different opportunities for exploiting large-scale parallelism
> for these optimization problems and describe current progress and
> future directions for using Sandia's parallel computing resources for
> this project.

# Introduction

> The NGSS project aims to develop a PC-based simulation tool that can
> be used to evaluate the security of sensitive sites. This tool is
> specifically targeted at security assessment for sites that use a
> limited number of personnel to maintain a defensive policy that can
> react to assaults from a small team of attackers. The simulation model
> includes basic elements of movement and small arms combat (e.g. small
> arms fire). To simplify the simulator, movement is constrained to a
> graph; agents can lie at any position along edges of the graph or at
> nodes of the graph. The simulation also includes special actions by
> associating them with their effect (e.g. a special action can be
> initiated to destroy a specific wall).
>
> An important component of the NGSS simulator is the behavior that is
> used to define the actions of the individuals that are attacking and
> defending a site. For defenders, the simulator needs to effectively
> model the behavior of individuals involved in both routine defensive
> policies, as well as defensive maneuvers that are in response to an
> attack. Defenders need to engage in combat while achieving broad
> strategic goals such as denying access to a site or capturing all
> attackers. For defenders, the simulator needs to effectively model the
> behavior of individuals that are evading or overcoming defensive
> barriers (e.g. sensors or doors). Further, attackers need to be able
> to engage in combat while achieving broad strategic goals such as
> penetrating a site or defending an escape route for other team
> members.

# Learning Problems

> The NGSS team has adopted a machine learning approach to model the
> behavior of defenders and attackers in the NGSS simulator. Modeling
> human behavior is a daunting task, but preliminary studies with
> small-scale combat simulations suggest that limited tactical behaviors
> can be learned with standard machine learning techniques. In these
> scenarios, individuals are modeled by agents that use information
> about the state of the simulation to guide their decisions in the next
> time step. For example, we have applied genetic programming (GP)
> methods to simple combat scenarios with no physical barriers. In these
> scenarios, GP generates agent controllers that quickly move agents
> towards a goal while evading defending agents.
>
> In this report we will not delve into the specifics of different
> approaches for solving these machine learning problems. In general,
> these types of learning problems can described as *supervised
> learning* problems, where the goal is to find parameters for an agent
> that matches a set of training data. In the context of security
> assessment, we can easily generate a large set of training data using
> the security simulation. The behaviors of agents can be scored during
> or after each simulation, giving an overall score for the agent
> parameters across all training trials. This combined score can then be
> used to guide the search for better agent parameters.
>
> Although the problem for finding attacker and defender behaviors can
> itself be viewed as a supervised learning problem, this problem is
> certainly too difficult to solve all at once. Consequently, we have
> decomposed this problem into several learning subproblems. In
> particular, we are evaluating ways of breaking up the agent behaviors
> into different domains that can be learned independently. For example,
> coordinating behaviors to achieve broad strategic goals can be
> separated from the control needed to achieve limited tactical
> objectives. Thus we expect that there will be many independent or
> loosely related learning problems that need to be solved to build an
> effective model of human behavior for the NGSS simulator.

# Learning and Optimization

> The learning problems discussed in the previous section generally
> involve a search method that explores a space of agent parameters to
> find a better (or sufficiently good) model of agent behavior. For
> example, GP searches through a space of tree structures that represent
> control programs for agents. Methods like GP are examples of
> *optimization* algorithms, which are general-purpose search
> algorithms. Optimization is a convenient way to cast these learning
> algorithms because the use of a general-purpose optimization method
> highlights the domain-dependent characteristics of the learning
> problem.
>
> The learning problems that we have considered to model agent behaviors
> in the NGSS simulator have the following characteristics:

1.  [Mixed continuous-discrete parameter domains]{.underline}: Learning
    techniques like GP involve a search of both combinatorial parameters
    like the program tree as well as continuous parameters like the
    real-valued constants used in the tree. Other learning paradigms
    like neural networks have similar characteristics when you consider
    the structure of the neural network in addition to the real-valued
    weights in a given neural network.

2.  [High dimensional search space]{.underline}: The number of inputs
    that can be provided to an agent in the NGSS simulation can easily
    exceed 100. Consequently, any nontrivial learning framework needs to
    consider several hundreds of search parameters to process these
    inputs.

3.  [Randomized objective]{.underline}: The NGSS simulator involves
    random events, particularly when small-arms fire is used during
    combat. Further, there may be some advantages to using randomized
    behavior in agents to make them less predictable by their opponents.
    Both of these factors contribute to randomization in the total
    objective that is used for optimization.

4.  [Expensive function calculations]{.underline}: The calculation of
    the objective function for learning with the NGSS simulator will be
    expensive for many learning problems simply because of the expense
    involved with running the NGSS simulator multiple times. Getting
    accurate estimates of the value of a set of agent parameters many
    involve averaging over many simulations, and each simulation may be
    long.

5.  [Variable cost function calculations]{.underline}: The amount of CPU
    resources used to compute the objective function for a given set of
    agent parameters can vary for many reasons. Randomization can
    introduce different simulation paths that have different lengths.
    Further, different initial configurations of a given scenario may
    result in different simulation lengths.

6.  [Nondifferentiable objective function]{.underline}: The objective
    function is not differentiable (i.e. does not have gradient
    information) since it involves discrete parameters and it is
    randomized.

7.  [Constraints]{.underline}: We expect that there will exist
    constraints on the set of agent parameters. For example, finding a
    *smallest* set of agent parameters is often desirable to ensure that
    the optimizer does not "over-learn" the set of training examples.

> These optimization characteristics need to be considered when
> selecting the optimization method for machine learning. Unfortunately,
> these characteristics define a particularly difficult class of
> optimization problems. Thus it is particularly important that the
> learning problem is carefully defined. Further, exploiting parallel
> computing resources is an important step to solving large learning
> problems in a timely manner.

# Opportunities for Parallelism

> There are many opportunities for exploiting parallelism for the types
> of optimization problems that were described in the previous section.
> We describe four ways that optimization can be exploited for NGSS
> learning problems.

1.  [Parallelized Simulations]{.underline}: Parallelizing the NGSS
    simulator is the most basic way that parallelization can be
    introduced. However, we do not expect that this will be a
    particularly effective use of parallel resources because the
    simulators are too small. Although a simulation may run through many
    time steps, there are a limited number of activities (like agent
    decisions) that can be computed simultaneously. Consequently, these
    simulations are inherently sequential.

2.  [Parallelization of the Function Evaluation]{.underline}: The
    objective function calculation for these learning problems involves
    the evaluation of a set of parameters across multiple trials.
    Consequently, it is natural to parallelize the objective function
    calculation by independently evaluating the parameters on different
    trials in parallel. Figure 1 illustrates how this parallelism can be
    accomplished with a basic master-slave algorithm. In this
    calculation, the parameters, , are sent to the slave processes, and
    the cost of the objective function, ~~, is returned so the
    master process can compute the total function evaluation. Since the
    simulation calculations may vary in length, the master process must
    dynamically send the slave processes new trials to evaluate.
    However, this overhead is minimal when compared to the total cost of
    each simulation.

> ![](media/image2.wmf)
>
> Figure 1. Illustration of a master-slave algorithm that distributes
> the calculation of the trials in a single objective function
> calculation.

3.  [Independent Calculation of Function Evaluations]{.underline}: Since
    the value of the objective function depends only on the search
    parameters, the optimization method can parallelize the evaluation
    of independent function evaluations. For example, in each iteration
    of GP a set of new points is generated, each of which can be
    independently computed since the GP generates the entire set at
    once. Figure 2 illustrates how this parallelism can be accomplished
    with a basic master-slave algorithm. The only difference from the
    master-slave method described in Figure 1 is that the slaves send
    the result of the entire function evaluation back to the master.

> ![](media/image3.wmf)
>
> Figure 2. Illustration of a master-slave algorithm that distributes
> the calculation of independent objective functions.

4.  [Parallelized Optimization Method]{.underline}: Parallelizing the
    optimization method beyond the parallel calculation of independent
    function evaluations can be achieved for a variety of optimization
    methods. In particular, heuristic methods like evolutionary
    algorithms, and multistart global optimization methods can be
    parallelized by extending the basic search strategy. For example,
    evolutionary algorithms like GP can be parallelized using an "island
    model" in which independent GP processes are run with a modest
    amount of communication to coordinate their total search. Also,
    hybrid algorithms that combine global and local optimizers can be
    parallelized by running independent local optimizations
    simultaneously.

> It is important to note that these four modes of parallelism can be
> combined to form levels of parallelism in the same way as the levels
> of parallelism used by the DAKOTA toolkit. For example, Figure 3
> illustrates how the parallelization of independent function
> evaluations and the parallelization of function evaluations can be
> combined to distribute the *total* calculation of a set of function
> evaluations.
>
> ![](media/image4.wmf)
>
> Figure 3. Illustration of the use of two levels of parallelism. Dark
> points represent master processors that coordinate the calculation of
> trials on the light points (a set of processors denoted by the dashed
> lines). The dark points also serve as slaves to the large dark offset
> point, which runs the optimizer.

# Current Progress and Perspectives

Because of the natural parallelism in GP and other evolutionary
algorithms, we have focused on the third type of parallelism. We have
implemented a GP within the SGOPT optimization library using SGOPT
abstract evolutionary algorithm class hierarchy. This class hierarchy
implicitly employs parallelization of function evaluation calls;
parallelization is achieved when the underlying hardware supports it. We
reimplemented the master-slave protocol used by SGOPT to dynamically
distributed the function evaluations based upon the demand from the
slave processors. This type of master-slave algorithm can accommodate
variability in the objective function cost more readily than the
previous implementation in SGOPT, which statically distributed all of
the function evaluation calculations to the available processors. We
have tested this parallel optimization capability using a parallel GP to
solve simple toy problems on a network of workstations. This code will
easily port to other parallel computing environments at Sandia since the
MPI communication standard was used to parallelize the optimizer.

The amount of parallelism that can be exploited in methods like the
parallel GP is limited because there are natural serial bottlenecks in
optimizers. Consequently, we are considering designs for using multiple
levels of parallelism that combine parallelized function evaluations or
parallelized optimizers or both. We are presently focused on
parallelized function evaluations because this is likely to provide the
most scalable form of parallelism. We are also considering parallel
hybrid algorithms to distribute the evaluation of independent local
searches in a hybrid GP. We expect that hybrid GPs will be needed to
effectively optimize the continuous constants in GP trees.

We have also considered parallel optimizers like the island-model GP.
However, these methods do not scale well to large numbers of processors
because the weak communication that they use is not sufficient to
coordinate a search among many processes. However, a multistart method
*would* effectively scale since it explicitly avoids this form of
coordination. Thus we are also considering multistart GPs for various
learning applications.

# Discussion

> It is clear that there are many opportunities for using parallelism
> for the learning applications related to the NGSS project. In all
> cases, parallelism can be achieved across a wide range of computing
> platforms. Further, parallel methods can be designed which have
> excellent performance on high-performance parallel computing platforms
> like ASCI Red and Cplant.
>
> However, one limiting factor concerns the development environment for
> the NGSS simulation. High-performance computing platforms generally
> provide an UNIX-like operating environment. Unfortunately, this
> environment does not provide the set of tools that are available
> within an MS Windows environment. Consequently, the use of
> high-performance parallel computing platforms requires the development
> of a separate simulation code for the parallel architectures. We
> expect that this will not lead to inconsistent agent behaviors between
> the two simulation codes since the simulators can be benchmarked on
> simple examples.