\documentclass{llncs}
\usepackage{wrapfig,cite,url,times,graphicx}
\newcommand{\aive}{{\"aive}}

\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}

\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}


 \newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
 \newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
 \newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

\begin{document}

%\CopyrightYear{2008} % Allows default copyright year (200X) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.

\title{
Better Optimization of Non-linear Requirements Models
}

\author{Omid Jalali\inst{1} \and Tim Menzies\inst{1} \and Gregory Gay\inst{1} \and Martin Feather\inst{2}}
\authorrunning{Jalali et al.}
\institute{West Virginia University, Morgantown, WV, USA,\\
\email{ojalali@mix.wvu.edu, tim@menzies.us, gregory@csee.wvu.edu},\\ 
\and Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA, USA, \\
\email{martin.s.feather@jpl.nasa.gov}}

\maketitle
\begin{abstract}
NASA's Jet Propulsion Laboratory has provided us with a set of five of their real-world requirements models, created using the Defect Detection and 
Prevention (DDP) tool. 
These models represent the requirements that a development group would want to achieve, the risks that could prevent these requirements from being met, and mitigations that could alleviate those risks. We are concerned with choosing the correct mitigations to achieve the highest attainment at the lowest cost.

	While the optimization of nonlinear factors is a thoroughly studied problem, the identification of the key factors leading to 
those optimizations is not. Through experimentation, we have developed a novel Bayesian technique called KEYS, 
which identifies both the optimal solutions and the key factors leading to those solutions, as well as cost-benefit tradeoffs and partial solutions. 
KEYS is over 60,000 times faster than prior model optimization methods. 

Our prior work ~\cite{promise08} only offered results for KEYS. In this paper, we will
perform a series of experiments to benchmark KEYS against a set of standard search algorithms.
These algorithms include a classic stochastic search (Simulated Annealing), a state-of-the art local search (MaxWalkSat), and a standard graph search (A*). 

\end{abstract}

\pagestyle{plain}
\section{Introduction}

Model-based design is a well-accepted software engineering technique.  Sendall and Kozacaynski made the case that "using concepts closer to the problem domain ..." via modeling~\cite{sendall03} can lead to increased productivity and reduced time-to-market. According to Hailpern and Tarr, model-based design "imposes structure and common vocabularies so that artifacts are useful for their main purpose in their particular stage in the life cycle"~\cite{hailpern06}. Model-based Software Engineering has become the norm at large organization such as Microsoft~\cite{greenfield04}; Lockheed Martin ~\cite{waddington03}; the Object Management Group~\cite{brown06}; and NASA's Jet Propulsion Laboratory~\cite{feather08}.

	The argument for their use is simple. Such models can be examined to reveal combinations of options that might otherwise be missed. 
For example, at NASA, large teams use "Defect Detection and Prevention" (DDP) ~\cite{corn01,feather08} models to find the {\em least} costly project options that {\em most} increase the chance to obtain more requirements. 
Without these models and automatic tools to analyze them, it would be far more difficult to achieve this non-linear optimization.

\begin{figure}[!h]
\centering
\includegraphics{pie.png}
\caption{The number of variables seen in the data dictionary of JPL systems models} 
\label{fig:variables}
\end{figure}

Prior experiments with simulated annealing~\cite{feather08} and treatment learning~\cite{fea02a} took minutes to hours to terminate.
This is a potential problem. Success with these model-based tools ~\cite{fea02a,me03c,feather08} has led to high expectations from the user community.
The models created by the community are rapidly becoming larger and larger. 
\fig{variables} shows the trend in the number of variables in the JPL system models. This growth rate is alarming, as inference times grow exponentially with the number of variables.
Additionally, as requirements change, the users generally would like to reanalyze their past decisions.  
Although many tools exist to analyze these models, they are too slow to handle the models that we expect to see in the near future. With our current tools, we expect to fall off of a computational cliff as the number of variables grows. 

Accordingly, we are concerned with finding {\em faster} techniques that meet or exceed the solution requirements for these models. 
Nielson found that users are most productive when response time is less than one second and 
that they will stop paying attention if those response times are longer than ten seconds ~\cite{nielson97}.
We seek a tool that will fall in that ideal response-time window.  
Our theory is that by exploiting certain {\em key} variables, we may surpass the computational barrier. 
Setting these key variables reduces the option space in larger models to a more manageable size. 
Several of the techniques that we explored, including KEYS and astar, represent massive improvements in the time taken to find solutions. 

The rest of the paper is structured as follows: a discussion of DDP models; search-based Software Engineering techniques to optimize these models; the KEYS algorithm; and the experiments performed to compare these techniques. We hope to provide a clear picture of current experiments in model-based Software Engineering and prepare a template for future experiments. 
This paper extends prior work ~\cite{promise08} by presenting improvements on the KEYS algorithm, providing benchmarks against standard techniques, and reaching better solutions. 

\section{Defect Detection and Prevention}

In a typical design session at the NASA Jet Propulsion Lab, a dozen (or more) designers refine and extend a single evolving design document. 
These designers are NASA's top experts in guidance, propulsion, communication, science, and other fields. 
Such an expert is a scarce resource who is needed for many tasks across the NASA organization. 
Hence, we must use these experts' time in the most cost-effective manner possible. 
Therefore, we seek tools that provide interactive design advice in a timely manner, ideally in time for the experts to assess multiple options during a single meeting. 
Such a tool would enable the teams to spend more time exploring a high-level trade space instead of laboriously elaborating one specific design in order to understand the consequences of various decisions.

The "Defect Detection and Prevention" (DDP) tool ~\cite{corn01,feather08} provides a succinct ontology for representing this design process. These models allow for the representation of the goals, risks, and risk-removing mitigations that belong to a specific project. 
The DDP systems design tool was designed to better support interactive team-based design at JPL. 

\begin{figure}[!h]
~\hrule~\\

DDP assertions are either:

\bi
\item \textit{Requirements} (free text) describing the objectives
and constraints of the mission and its development process; 
\item \textit{Weights} (numbers) associated with requirements, reflecting
their relative importance; 
\item \textit{Risks} (free text) are
events that damage requirements; 
\item \textit{Mitigations}: (free
text) are actions that reduce risks; 
\item \textit{Costs}: (numbers) effort associated with mitigations, and repair costs for
correcting Risks detected by Mitigations; 
\item \textit{Mappings}: directed edges between
requirements, mitigations, and risks that capture quantitative relationships among them. 
\item \textit{Part-of relations}
structure the collections of requirements, risks and mitigations; 
\ei

~\hrule~
\caption{DDP's ontology}
\label{ddpont}
\end{figure}

DDP might be thought of as a more complicated form of the mainstream decision support approach Quality Function Deployment (QFD)~\cite{akao90}. Like in the QFD approach, DDP sets a series of requirements or goals. However, DDP sets itself apart with its basis, a quantitative, probabilistic approach inspired by risk assessment techniques. This approach is why we believe that DDP is useful for studying the requirements needs of a wide variety of technologies, including software, hardware and combinations of the two.
DDP is based on the following principles:
\bi
\item {\em Earlier is Better:} The case for "earlier is better" is well established. Fark et al. ~\cite{fa07} noted that "80\% of all design decisions are taken in the first 20\% of the design time." Design tools that do not operate early in the lifecycle can only affect a small portion of the remaining decisions.
Not only is earlier design critical, but rapid improvement of those designs is also crtical. 
Fixing defect costs exponentially more the longer those defects remain in the system. Boehm and Papaccioa dvise that reworking software
is cheaper earlier in the life cycle "by factors of 50 to 200." ~\cite{boehm88}
\item {\em Use Risk-driven SE:} In risk-driven SE ~\cite{boehm86}, there are three primary modeling constructs. The engineering {\em requirements} are mapped to a series of {/em risks},  a representation of any of the 
factors that could prevent a goal from being reached. 
{\em Mitigations} are measures that may be implemented in order to alleviate risks. 
Hence, our DDP tool is a visual editor of a model with node types reflecting these three constructs. During interactive sessions, DDP displays its model on a projector where teams and designers review and entend the network.
This information can influence the entire design process and may lead to a more efficience development cycle.
\item {\em Use Value-based SE:} DDP is also a {\em value-based SE} ~\cite{bi05} tool where the {\em benefits} of a design variant are weighed against their {\em cost}. Each mitigation in DDP has an associated cost so that DDP can 
guide and optimize decision making. For example, on a fixed budget, DDP can find the cheapest mitigations that retire the most risks and hence
allow for the obtainment of the most requirements. 
DDP can repeat this pocess for different cost levels to generate a cost-benefit trade-space diagram.  
\ei 

\begin{figure}
\begin{center}
\includegraphics[width=4.5in]{fig2.png}
\end{center}
\caption{An example of a model formed by the DDP tool} 
\label{fig:DDPexample}
\end{figure}

The process by which DDP is employed is as follows:

\bi
\item 6 to 20 experts are gathered together for short, intensive knowledge
acquisition sessions (typically, 3 to 4 half-day sessions). These
sessions \textit{must} be short since it is hard to gather together
these experts for more than a very short period of time. 
\item The DDP tool supports a graphical interface for the rapid entry of the
assertions. Such rapid entry is essential, time is crucial and no tool should slow the debate. 
\item Assertions from the experts are expressed using an ultra-lightweight decision ontology (e.g. see Figure~\ref{ddpont}).
The ontology \textit{must} be ultra-lightweight since: 
\bi
\item Only brief assertions can be collected in short knowledge acquisition
sessions. 
\item If the assertions get more elaborate, then experts
may be unable to understand technical arguments from outside their
own field of expertise. 
\ei
\ei

The result of these sessions is a model of influences connecting
project requirements to risks to possible mitigations; see
Figure~\ref{DDPexample}.

The models created through this process (see Figure~\ref{ddpont}) may appear to be too weaker than those created by UML. 
Practice has proven this assertion to be false. After repeated sessions with the DDP tool, it has been shown that this ontology is rich enough to structure and guide debates between NASA experts. 

The DDP tool has been applied to over a dozen applications, including such advanced technologies as 
\bi
\item a computer memory device; 
\item gyroscope design; 
\item software code generation; 
\item a low temperature experiments apparatus; 
\item an imaging device;
\item circuit board like fabrication; 
\item micro electro-mechanical devices; 
\item a sun sensor; 
\item a motor controller;
\item photonics; and 
\item interferometry. 
\ei

Clear project improvements have been seen from these DDP sessions. Cost savings have in at least two sessions have exceeded \$1 million, while savings of over \$100,000 have resulted in others. Cost savings are not the only benefits of these DDP sessions. 
Numerous design improvements suck as savings of power of mass have come out of DDP sessions.
Likewise, a shifting of risks has been seen from uncertain architectural ones to more predictable and manageable ones. 
At some of these meetings, non-obvious significant risks have been identified and subsequently mitigated. The DDP tool can be used to document all of this information and the decision making process of these studies. Because of these reasons, DDP remains in use at JPL:

\bi
\item not only for its original purpose (group decision support);
\item but also as a design rationale tool to document decisions. 
\ei

It is important to note that DDP is not just a software design tool. Software and hardware are frequently designed together at JPL. The DDP tool is better viewed as a {\em software systems engineering} tool where the interactions between hardware and software, and the possible incompatibilities, can be quickly explored.

\section{Common Properties}

The rest of this paper will discuss various algorithms designed to find an optimal solution to the DDP models. 
All of the algorithms that we use in this experiment share a couple of common properties. All of the techniques use the same model format and the same scoring heuristic. 

\subsection{Model Format}

\begin{figure}[!h]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|c|c|} \hline
Model&LOC&Objectives&Risks&Mitigations\\ \hline
model1.c&  55  &3         &2    &2          \\ \hline
model2.c& 272   &1         &30   &31         \\ \hline
model3.c& 72   &3         &2    &3         \\ \hline
model4.c& 1241   &50        &31   &58         \\ \hline
model5.c&1427    &32        &70   &99         \\ \hline
\end{tabular}
\end{center}
\caption{Details of Five DDP Models. }
\label{fig:ddpModels}
\end{figure}

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
include "model.h"

#define M_COUNT 2
#define O_COUNT 3
#define R_COUNT 2

struct ddpStruct
{
    float oWeight[O_COUNT+1];
    float oAttainment[O_COUNT+1];
    float oAtRiskProp[O_COUNT+1];
        float rAPL[R_COUNT+1];
    float rLikelihood[R_COUNT+1];
    float mCost[M_COUNT+1];
    float roImpact[R_COUNT+1][O_COUNT+1];
    float mrEffect[M_COUNT+1][R_COUNT+1];
};

ddpStruct *ddpData;

void setupModel(void)
{
    ddpData = (ddpStruct *) malloc(sizeof(ddpStruct));
    ddpData->mCost[1]=11;
    ddpData->mCost[2]=22;
    ddpData->rAPL[1]=1;
    ddpData->rAPL[2]=1;
    ddpData->oWeight[1]=1;
    ddpData->oWeight[2]=2;
    ddpData->oWeight[3]=3;
    ddpData->roImpact[1][1] = 0.1;
    ddpData->roImpact[1][2] = 0.3;
    ddpData->roImpact[2][1] = 0.2;
    ddpData->mrEffect[1][1] = 0.9;
    ddpData->mrEffect[1][2] = 0.3;
    ddpData->mrEffect[2][1] = 0.4;
}

void model(float *cost, float *att, float m[])
{
    float costTotal, attTotal;
    ddpData->rLikelihood[1] = ddpData->rAPL[1] * (1 - m[1] * ddpData->mrEffect[1][1]) 
				* (1 - m[2] * ddpData->mrEffect[2][1]);
    ddpData->rLikelihood[2] = ddpData->rAPL[2] * (1 - m[1] * ddpData->mrEffect[1][2]);
    ddpData->oAtRiskProp[1] = (ddpData->rLikelihood[1] * ddpData->roImpact[1][1]) 
				+ (ddpData->rLikelihood[2] * ddpData->roImpact[2][1]);
    ddpData->oAtRiskProp[2] = (ddpData->rLikelihood[1] * ddpData->roImpact[1][2]);
    ddpData->oAtRiskProp[3] = 0;
    ddpData->oAttainment[1] = ddpData->oWeight[1] * (1 - minValue(1, ddpData->oAtRiskProp[1]));
    ddpData->oAttainment[2] = ddpData->oWeight[2] * (1 - minValue(1, ddpData->oAtRiskProp[2]));
    ddpData->oAttainment[3] = ddpData->oWeight[3] * (1 - minValue(1, ddpData->oAtRiskProp[3]));
    attTotal = ddpData->oAttainment[1] + ddpData->oAttainment[2] + ddpData->oAttainment[3];
    costTotal = m[1] * ddpData->mCost[1] + m[2] * ddpData->mCost[2];

        *cost = costTotal;
        *att = attTotal; 
}

\end{verbatim}}
~\hrule~
\caption{A trivial DDP model}
\label{fig:ddpExample}
\end{figure}

Discrete models (like DDP) are generally not suitable for numeric optimization. 
The non-continuous nature of these models leads to `cliffs'' where the behavior of a
system can change dramatically.
Hence, in our previous work ~\cite{promise08},
we applied data mining techniques
to find the desired low-cost, high attainment pairing. 

Knowledge compilation is a technique where certain information is compiled into a target language.
Previous work with knowledge compilation has focused on compilation languages utilizing CNF equations, state machines, or BDD~\cite{darwiche02,biere99:bmc}.
None of these made sense for our experiments [XXXXX]. We instead compiled the DDP models into a structure used by the C programming language.

These compiled models are used to rapidly answer a large number of queries while the main program is running ~\cite{selman96knowledge,darwiche02}.
This pushes a large percentage of the computational overhead into the compilation phase. This cost is amortized over time as we increase the number of on-line queries. 
Some of the algorithms that we use make thousands of calls to these DDP models; therefore, the runtime increase from knowledge compilation is significant.
For example, the original DDP tool was written in Visual Basic. Converting those models to the pre-compiled C structures provided a 130x increase in speed.

Knowledge compilation is useful for more than just runtime optimization, it has actually made some of this research possible in the first place.
This method allows JPL to retain their proprietary information. 
In turn, this has given researchers outside of JPL access to their models.
For our experiments, JPL ran the knowledge compiler and passed West Virginia University models like those shown in \fig{ddpExample}. These models have been anonymized to remove proprietary information while still maintaining their computational nature.
JPL could assure its clients that any project secrets would be safe while allowing outside researchers to perform valuable experiments.

Our knowledge compilation process stores a flattened form of the DDP requirements tree. In standard DDP:
\bi
\item 
Requirements form a tree;
\item
The relative influence of each leaf requirement is computed via
a depth-first search from the root down to the leaves.  
\item
This computation is repeated each time the relative influence of a requirement is required.
\ei
In our compiled form, the computation is performed once 
and added as a constant to each reference of the requirement.

For example, here is a trivial DDP model
where  {\tt mitigation1} costs \$10,000 to apply and each requirement is of equal
value (100): 
\[\overbrace{mitigation1}^{\$10,000} \underbrace{\rightarrow}_{0.9} risk1 \rightarrow
\left< \begin{array}{c} \overbrace{\rightarrow}^{0.1} (requirement1=100) \\ 
\underbrace{\rightarrow}_{0.99} (requirement2=100) \end{array} \right.\]
(The other numbers show the impact of mitigations on risks, and risks
on requirements).

The knowledge compiler converts this trivial DDP model into {\tt setupModel} and {\tt model} functions 
similar to those in \fig{ddpExample}.
The {\tt setupModel} function is called once and sets several constant values. 
The {\tt model} function is called whenever new cost and attainment values are needed.
The topology of the mitigation network is represented as terms in equations within these functions. 
As our models grows more complex, so do these equations. For example,
our biggest model, which contains 99 mitigations, generates 1427 lines of code (see \fig{ddpModels}).

\subsection{Scoring Method}

When the {\tt model} function is called, a pairing of the total cost of the selected mitigations and the number of reachable requirements (attainment) is returned. 
All of our algorithms (except for SimpleSA, which is explained in its own section) then use that information to obtain a "score" for the current set of mitigations. 
The two numbers are normalized to a single score that represents the distance to a {\em sweet spot} of maximum attainment and minimum cost: 
\[
score = \sqrt{\overline{cost}^2 + (\overline{att}-1)^2}
\]

Here, $\overline{x}$ is a normalized value 
$0 \le \frac{x - min(x)}{max(x) - min(x)} \le 1$. 
Hence, our scores ranges $0 \le s \le 1$ and
{\em higher} scores are {\em better}.

\section{Algorithms}
\subsection{SimpleSA}

Simulated Annealing is a classic stochastic search algorithm. It was first described in 1953~\cite{metropolis53} and refined in 1983 ~\cite{kirkpatrick83}. 
The algorithm's namesake, annealing, is a technique from metallurgy, where a material is heated and cooled in controlled bursts. The heat causes the atoms in the material to 
wander randomly through different energy states and the cooling process increases the chances of finding a state with a lower energy than the starting position.

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure SimpleSA
2. MITIGATIONS:= set of mitigations
3. SCORE:= score of MITIGATIONS
4. while TIME < MAX_TIME && SCORE < MIN_SCORE
                 //minScore is a constant score (threshold)
5.    find a NEIGHBOR close to MITIGATIONS
6.    NEIGHBOR_SCORE:= score of NEIGHBOR
7.    if NEIGHBOR_SCORE > SCORE
8.        MITIGATIONS:= NEIGHBOR
9.        SCORE:= NEIGHBOR_SCORE
10.   else if prob(SCORE,NEIGHBOR_SCORE,TIME, temp(TIME, MAX_TIME)) > RANDOM)
11.       MITIGATIONS:= NEIGHBOR
12.       SCORE:= NEIGHBOR_SCORE
13.   TIME++
14. end while
15. return MITIGATIONS
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for SimpleSA}
\label{fig:simplesa}
\end{figure}

Each round, SimpleSA "picks" a neighboring set of mitigations. To calculate this neighbor, a function traverses the mitigation settings of the current state and randomly flips those mitigations (at a 5\% chance). 
If the neighbor has a better score, SimpleSA will move to it and set it as the current state. If it isn't better, the algorithm will decide whether to move to it based on the mathematical function:
\begin{equation}\label{eq:ps}\small
prob(w,x,y,temp(y,z)) = e^{((w-x) * \frac{y}{temp(y,z)})}
\end{equation}
\begin{equation}\label{eq:ps}\small
temp(y,z) = \frac{(z-y)}{z}
\end{equation}
If the value of the {\tt prob} function is greater than a randomly generated number, SimpleSA will move to that state anyways. 
This randomness is the very cornerstone of the Simulated Annealing algorithm. The "atoms" will jump around randomly until they are cooled and stabilized.
The algorithm will continue to operate until the number of tries is exhausted or a score meets the threshold requirement. 

\subsection{MaxFunWalk}

The boolean satisfiability problem is a well-researched Computer Science problem. 
WalkSat is a local search method designed to address this problem ~\cite{selman96, kautz96}. MaxWalkSat, in particular, is a variant of WalkSat that applies weights to each clause in a conjunctive normal form equation. While we are not addressing satisfiability in this paper, the general algorithm has applications for our work. Previously, the authors have wondered if a MaxWalkSat-inspired algorithm would improve the results of KEYS ~\cite{promise08}. Thus, a generalization of MaxWalkSat was a natural choice for the list of algorithms to benchmark the KEYS technique against. In our form, we use the set of mitigations instead of a CNF equation, and the score generated by cost and attainment is the weight.   

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure MaxFunWalk
2. for TRIES:=1 to MAX-TRIES
3.    SELECTION:=A randomly generate assignment of mitigations
4.    for CHANGED:=1 to MAX-CHANGES
5.        if SCORE satisfies THRESHOLD return
6.        CHOSEN:= a random selection of mitigations from SELECTION
7.        with probability P
8.            flip a random setting in CHOSEN
9.        with probability (P-1)
10.           flip a setting in CHOSEN that maximizes SCORE
11.    end for
12. end for
13. return BESTSCORE
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for MaxFunWalk}
\label{fig:MWF}
\end{figure}


The MaxFunWalk procedure is simple. When run, the user supplies an ideal cost and attainment. This setting is normalized, scored, and set as a goal threshold. If the current setting of mitigations satisfies that threshold, the algorithm terminates. MaxFunWalk begins by randomly setting every mitigation. From there, it will attempt to make a {\em single} change until the threshold is met or the allowed number of changes runs out (100 by default). 
A random subset of mitigations is chosen and a random number P between 0 and 1 is generated. The value of P  will decide the form that the change takes:
\bi
\item P$<=$0.3: A stochastic decision is made. A setting is changed completely at random within subset C.
\item P$>$0.3: Local search is utilized. Each mitigation in C is tested until one is found that improves the current score.
\ei

If the threshold is not met by the time that the allowed number of changes is exhausted, the set of mitigations is completely reset and the algorithm starts over. This measure allows the algorithm to avoid becoming trapped in local maxima. However, in practice, resets seemed to have little value for finding better solutions. 
If the threshold is never met, MaxFunWalk will reset and continue to make changes until the maximum number of allowed resets is exhausted. At that point, it will return the best settings found. 

As an additional measure to improve the results found by MaxFunWalk, a heuristic was implemented to limit the number of mitigations that could be set at one time. If too many are set, the algorithm will turn off a few in an effort to bring the cost factor down while minimizing the effect on the attainment. 

\subsection{astar}

The A* graph search algorithm is widely used in the video game or the Artificial Intelligence fields.
 A* is a best-first pathfinding algorithm that uses distance and cost to find the best path to the goal ~\cite{hart68}. The algorithm has been proven to be optimal for a given scoring heuristic ~\cite{dechter85}, and has seen widespread use in multiple fields ~\cite{pearl84,norvig03,stout97,hui04}. 
Our use of Euclidean distance as a scoring heuristic made a very natural transition to the pathfinding of A*. 

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure astar
2. CURRENT_POSITION:= Starting assignment of mitigations
3. CLOSED[0]:= Add starting position to closed list
4.
5. while END:= false
6.    NEIGHBOR_LIST:=list of neighbors
7.    for each NEIGHBOR in NEIGHBOR_LIST
8.        if NEIGHBOR is not in CLOSED
9.            G:=distance from start
10.           H:=distance to goal
11.           F:=G+H
12.           if F<BEST_F
13.               BEST_NEIGHBOR:=NEIGHBOR
14.   end for
15.   CURRENT_POSITION:= BEST_NEIGHBOR
16.   CLOSED[++]:=Add new state to closed list
17.   if STUCK
18.       END:= true
19. end while	
20. return CURRENT_POSITION
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for astar}
\label{fig:astar}
\end{figure}

Our implementation of A*, called astar, allows for two possible starting configurations. Like all of the other algorithms used for this experiment, astar can randomly make assignments to each mitigation. This was the setting used for most of our experiments. However, A* is a deterministic algorithm. Given a {\em fixed} starting position and an {\em unchanging} search space, it should always come up with the same final answer. To test this, our astar technique can be set to start from a fixed state where cost and attainment are both equal to 0. 

The astar algorithm keeps a {\em closed} list in order to prevent backtracking. We begin by adding the starting state to the closed list. Each "round," a list of neighbors is populated from the series of possible states reached by making a change to a single mitigation. 
If that neighbor is not on the closed list, two calculations are made: 
\bi
\item G = Distance from the start to the current state plus the additional distance between the current state and that neighbor.
\item H = Distance from that neighbor to the goal (an ideal spot, usually 0 cost and a high attainment determined by the model). 
\ei
The {\em best} neighbor is the one with the lowest F=G+H. The algorithm "travels" to that neighbor and adds it to the closed list. 
Part of the optimality of the A* algorithm is that the distance to the goal is underestimated. 
Thus, the final goal is never actually reached by astar. 
Our implementation terminates once it gets stuck, i.e. unable to find a better state, for a total of ten rounds. This number was chosen to give ample time for astar to become "unstuck" if it hits a corner early on.  

\section{KEYS}

The premise of the KEYS algorithm is that within the space of possible
decisions, there exist a small number of $key$ decisions that
determine all others. 
We will first explore the theory of "keys," then we will explain the KEYS algorithm. 

\subsection{What are ``keys''?}

Within a model, there are chains of {\em reasons} that link inputs to the desired goals.
As one might imagine, some of the links in the chain clash with others. 
Some of those clashes are most upstream, they are not dependent on other clashes. 
In the following chains of reasoning 
the clashes are $\{e \neg e\}$, 
$\{g \neg g\}$ 
\& $\{j,\neg j\}$;
item the most upstream clashes 
are
$\{e \neg e\}$, 
\& $\{g \neg g\}$, 
\[\begin{array}{r@{}l@{}l}
&a \longrightarrow b \longrightarrow c \longrightarrow d \longrightarrow e\\
input_1 \longrightarrow  &f \longrightarrow g \longrightarrow h \longrightarrow i \longrightarrow j & \longrightarrow goal\\
input_2 \longrightarrow  &k \rightarrow \neg g \longrightarrow l \longrightarrow m \rightarrow \neg j & \longrightarrow goal\\
&n \longrightarrow o \longrightarrow p \longrightarrow q \longrightarrow
\neg e
\end{array}
\]
In order to optimize decision making about this model, we must first decide about these {\em upstream clashing reasons}.
We refer to these decisions as {\em the collars} as they have the most impact on the rest of the model.

Returning to the above reasoning chains,
any of $\{a, b, ..q\}$ are subject to discussion.
However, most of this model is completely irrelevant to the task of
$input_i\vdash~goal$. For example, 
the $\{e, \neg e\}$ clash is
unimportant to the decision making process
as no reason uses $e$ or $\neg e$. 
In the context of reaching some $goal$ from 
$input_i$, the only important discussions are
the clashes $\{g,\neg g,j,\neg j\}$.
Further, since $\{j, \neg
j\}$ are fully dependent on $\{g,\neg g\}$, then the core decision
must be about variable $g$ with two disputed values: true and
false. 

We call 
$g$ 
the {\em collar} since it restricts the entire model.
The collar may be internal to a model and so may not be directly controllable. We refer to the controllable variables that can influence the collar as a model's $keys$
In the previous example, those keys are $input_i$.

Using the keys to set the $collars$ reduces the number of reachable states within the model. 
Formally, the reachable states reduce to
the cross-product of all of the ranges of the collars.
We call this the $clumping$ effect, only a small fraction of the possible states are reachable.
The effects of clumping can be quite dramatic.
Without knowledge of these chains and the collar, the above model has $2^{20} > 1,000,000$ possible consistent states.
However, in the context of 
$input_i\vdash~goal$,
those 1,000,000 states clumps to just the following two states: 
$\{input_1,f,g,h,i,j,goal\}$ or
$\{input_2,k,\neg g,l,m,\neg j,goal\}$.
In the related work section, we show examples of keys in other research work. 

\subsection{The KEYS Algorithm}

[XXXX - motivation for KEYS, R. Clark reference]
There are two main components to KEYS - a greedy search and the BORE ranking heuristic.

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure KEYS
2. while FIXED_MITIGATIONS != TOTAL_MITIGATIONS
3.    for I:=1 to 100
4.       SELECTED[1...(I-1)] = best decisions up to this step
5.       GUESSED = random settings to the remaining mitigations
6.       INPUT = SELECTED + GUESSED
7.       SCORES= SCORE(INPUT)
8.    end for   
9.    for J:=1 to NUM_MITIGATIONS_TO_SET 
10.      TOP_MITIGATION = BORE(SCORES)       
11.      SELECTED[FIXED_MITIGATIONS++] = TOP_MITIGATION 
12.   end for  
13. end while          
14. return SELECTED
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for KEYS}
\label{fig:KEYS}
\end{figure}

KEYS
searches a space of $M$ 
mitigations over the course of 
$M$ ``eras''. 
Initially, the entire set of mitigations is set randomly. 
During each era, one more
mitigation is set to $M_i=X_j$, $X_j \in \{true,false\}$. 
Each era $e$ generates
a set $<input,score>$ as follows:
\be
\item[1a:]
$Selected[1{\ldots}(e-1)]$ are settings from previous eras.
\item[1b:]
	$Guessed$ are randomly selected values for unfixed mitigations.  
\item[1c:]
	$Input = selected \cup guessed$.
\item[1d:]
Call {\tt model} to compute $score=ddp(input)$;
\ee
After 100 repeats of steps 1a,1b,1c,and 1d:
\bi
\item[2:] The 100 $score$s are divided into 10\% $best$ and 90\% $rest$. 
\item[3:]
The mitigation values in the $input$ sets are then scored using BORE
(described below).
\item[4:]
The top ranked mitigations (the default is one, but the user may fix multiple mitigations at once) are fixed and stored in $selected[e]$.\ei
KEYS then moves to the era $e+1$ and repeats steps 1,2,3,4.
KEYS stops
when every mitigation has a setting.  

KEYS ranks mitigations by combining a novel Bayesian ranking measure, better founded in theory, with a 
support measure.
BORE ~\cite{clark05} divides numeric scores seen over $K$ runs and stores the top 10\%  in $best$ and the remaining 90\% scores in the set $rest$. 
It then computes the probability that a value is found in $best$
using
Bayes theorem.
The theorem uses
evidence $E$ and a prior probability $P(H)$ for
hypothesis $H\in\{best, rest\}$,
to calculate a  posteriori  probability
$P(H|E)=P(E|H) P(H)\; /\; P(E)$.
Such simple  Bayes classifiers are often called ``n\aive'' since they assume
independence of each variable. 
Domingos and Pazzani have shown
that the independence assumption is a problem in a vanishingly small percent
of cases~\cite{domingos97optimality}. This explains the repeated
empirical result that seemingly n{\aive} Bayes classifiers perform as well
as other more sophisticated schemes (e.g. see Table~1 in~\cite{domingos97optimality}).

When applying the theorem, {\em likelihoods}
are computed from observed
frequencies. These likelihoods are then normalized to create
probabilities (this normalization cancels out $P(E)$ in Bayes theorem).
For example, after $K=10,000$ runs are divided into  1,000 {\em best} solutions and 9,000
{\em rest}, the  value \mbox{$mitigation31=false$} might appears 10 times in the $best$ solutions, but only
5 times in the $rest$. Hence:\newline
\begin{minipage}{1.0\linewidth}
{\scriptsize
\begin{eqnarray}\nonumber
E&=& (mitigation31=false)\\\nonumber
P(best)&=&1000/10000 = 0.1\\\nonumber
P(rest)&=&9000/10000 = 0.9\\\nonumber
freq(E|best)&=&10/1000 = 0.01\\\nonumber
freq(E|rest)&=&5/9000 = 0.00056\\\nonumber
like(best|E)&=&freq(E|best) \cdot P(best)=0.001\\\nonumber
like(rest|E)&=&freq(E|rest) \cdot P(rest)= 0.000504\\\label{eq:ten}
P(best|E)&=& \frac{like(best|E)}{like(best|E) + like(rest|E)}=0.66
\end{eqnarray}}
\end{minipage}\newline
Previously~\cite{clark05},
we have found that  Bayes theorem
is a poor ranking heuristic
since it is easily distracted by low frequency evidence.
For example, note how
the probability of $E$ belonging to the best class
is moderately high even though its support is very low; i.e. $P(best|E)=0.66$ but
$freq(E|best) = 0.01$. 

To avoid the problem of unreliable low frequency evidence, we augment \eq{ten}
with a support term.
Support should $increase$ as the frequency of a value $increases$,  i.e. 
$like(best|E)$ is a valid support measure.
 Hence, step 3 of our greedy search ranks values  via
\begin{equation}\label{eq:ps}\small
P(best|E) * support(best|E) = \frac{like(best|E)^2}{like(best|E) + like(rest|E)}
\end{equation}

\section{Results}

Each of our algorithms were run on the five JPL requirements models.
As shown in \fig{ddpModels},
models one and three are very small. Therefore, we will focus on  models two, four, and five
which were more interesting.
Model 4 was discussed in~\cite{me03n} in detail. 
The largest, model5 was processed previously by DDP/TAR4~\cite{fea02a}, which took over forty minutes to compute.

\subsection{Result Comparisons}

\begin{figure}
\begin{center}
\begin{tabular}{|p{2.5cm}|r|r|r|}\hline
Algorithm&Model 2&Model 4&Model 5\\ \hline
astar&  \includegraphics{WithLabel/2/AStar.pdf} & \includegraphics{WithLabel/4/AStar.pdf} &  \includegraphics{WithLabel/5/AStar.pdf} \\ \hline
KEYS (1 mitigation per round) &  \includegraphics{WithLabel/2/KEYS.pdf} & \includegraphics{WithLabel/4/KEYS.pdf} & \includegraphics{WithLabel/5/KEYS.pdf} \\ \hline
KEYS (previous+1 mitigation per round) 	& \includegraphics{WithLabel/2/KEYS-L.pdf} & \includegraphics{WithLabel/4/KEYS-L.pdf} & \includegraphics{WithLabel/5/KEYS-L.pdf}\\ \hline
MaxFunWalk& \includegraphics{WithLabel/2/MaxFunWalk.pdf} & \includegraphics{WithLabel/4/MaxFunWalk.pdf} & \includegraphics{WithLabel/5/MaxFunWalk.pdf} \\ \hline
SimpleSA& \includegraphics{WithLabel/2/SA.pdf} & \includegraphics{WithLabel/4/SA.pdf} & \includegraphics{WithLabel/5/SA.pdf} \\ \hline
\end{tabular}
\caption{Results on three models (Cost, in thousands, on y-axis, Attainment on x-axis)}
\end{center}
\label{fig:modelResults}
\end{figure}

We ran each of our algorithms 1000 times on each model. This number was chosen because it yielded enough data points to give a clear 
picture of the span of results. At the same time, it is a low enough number that we can generate a set of results in a fairly short time span. 
The results are pictured in ~\fig{modelResults}. Attainment is along the x-axis and cost (in thousands) is along the y-axis.
We also chose to run two variants of KEYS. The first is the standard configuration, where a single mitigation is fixed in place each round.
The second variant sets mitigations incrementally. It sets a single mitigation during the first round, two during the second, etc.

These graphs give a clear picture of the results obtained by our four algorithms. We can easily rule out SimpleSA. 
Its results on all three models are all over the search space
The stochastic nature of the algorithm leads to wild, uncontrollable results that are all over the map. 
MaxFunWalk fares a little better, but it can be pretty easily ruled out as well. 
The additional cost-control factor in MaxFunWalk restricts the "result cloud" that forms in the larger models, but it did nothing to restrict the results on Model 2. 
In general, there is entirely too much variance for MaxFunWalk to be a valid solution. Even if the variance is ignored, the results from MaxFunWalk and SimpleSA just aren't very good.

The remaining two algorithms, astar and KEYS both do fairly well. As expected, their results are nearly identical on Model 2. 
The smaller number of possible final states would logically lead to similar results. 
On Models 4 and 5, astar shows higher variance than Keys. 
Likewise, allowing KEYS to set multiple mitigations each round causes more variance than when only a single mitigation is fixed.
When given similar goals (low cost, high attainment), the astar algorithm does tend towards slightly lower cost results than KEYS. 
The results are similar enough that, depending on their leanings, a project head might lean towards one or the other. 
However, the fact that KEYS has less variance in its final results is what gives it the advantage here. 
The astar search will, in the worst case, find a different result for every starting position. 
That KEYS finds similar results despite the different starting positions gives it a powerful stability guarantee.  

\subsection{Runtime Analysis}

\begin{figure}[!h]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|} \hline
Algorithm&Model 2&Model 4&Model 5\\ \hline
astar&  0.003  &0.017         &0.048    \\ \hline
KEYS (1 mitigation per round) & 0.011   &0.053         &0.115   \\ \hline
KEYS (previous+1 per round) 	&0.006  &0.018 		&0.038 \\ \hline
MaxFunWalk& 0.122   &0.429   &0.398         \\ \hline
SimpleSA& 0.577   &1.258        &0.854  \\ \hline
\end{tabular}\newline
\end{center}
\small{* All runtimes in seconds}
\caption{Table of Runtimes}
\label{fig:runtimes}
\end{figure}

In order to obtain our runtimes for each of these algorithms, we ran them 100 times and took the average of times. 
Numbers were obtained from the "real" time value given by the Unix {\tt times} command. 

All of these algorithms are clear improvements over past work with treatment learning. The TAR3 learner took 40 minutes to compute Model 5. However, it is still pretty easy to rule out both SimpleSA and MaxFunWalk. On Model 2, SimpleSA took 363 times as long to run as astar. 
Given the fact that astar and KEYS obtain far better results than the other two, the longer runtimes are inexcusable. 
The astar algorithm is over twice as fast as its nearest competitor, KEYS, in its default state. However, if KEYS is told to set an incremental number of mitigations per round (e.g. it sets one in round one, two in round two, etc), we see a huge improvement in runtime.  
This improved runtime in KEYS does come at a price, the variance in the final results will increase as the number of mitigations set per round increases. 
Thus, it is up to the user to find the appropriate level of trade-off between speed and variance. 

\subsection{Internal Convergence}

If astar and KEYS obtains somewhat similar results and are similar in time to run, why recommend KEYS? 
We recommend KEYS because it contains a stability guarantee. ~\fig{in2}, ~\fig{in4}, and ~\fig{in5} show the internal decisions made during one run.
For KEYS, at $era=0$, all of the mitigations in the model are set at random. During each subsequent era, one more mitigation is locked down.
The lines in each of these plots show the median and spread seen in the 100 calls to the {\tt model} function during each round. We define median as the 50th percentile and spread (the measure of deviation around the median) as (75th percentile - median). 
The astar algorithm only has one line because it only makes one decision each round, it chooses the "best" neighbor and moves on. 

\begin{figure}
\begin{center}
\includegraphics[width=4.5in]{model2-median-spread.pdf}
\end{center}
\caption{Internal Decisions on Model 2} 
\label{fig:in2}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=4.5in]{model4-median-spread.pdf}
\end{center}
\caption{Internal Decisions on Model 4} 
\label{fig:in4}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=4.5in]{model5-median-spread.pdf}
\end{center}
\caption{Internal Decisions on Model 5} 
\label{fig:in5}
\end{figure}

For both algorithms, cost improvements are dramatic for about 20 rounds, 
after which they tend to stabilize. As we can see in the plots, the spread is generally quite small compared to the median. This indicates that our median estimates 
are good descriptions of the tendencies of the models.
We can cut KEYS off at any point and have a good idea of whether or not it is making good decisions, how the cost and attainment are related, and which mitigations are locked down. 
If a NASA expert wanted a set of mitigations that would have the largest effect when set, they could cut KEYS off after a certain number of rounds and obtain that set. 
astar has no such stability guarantee. If astar makes a bad decision, there is no information that will prevent that in the future. As single mitigations are not locked down, the algorithm remains unpredictable during the endgame, where KEYS makes fewer and fewer decisions. 
[XXXX]

\section{Discussion}

Every one of the algorithms that we have proposed and examined in this paper 
represent a massive improvement in speed over the previous treatment learning work.
However, runtimes are less important than results. In that area, both SimpleSA and MaxFunWalk
can be rules out. Our KEYS and astar algorithms, on the other hand, represent 
the pinnacle of results that can be achieved by examining these models. They actually hit the very corner of the cost-attainment pairings
that can be found in the DDP models.

Earlier ~\cite{promise08}, the authors advocated KEYS as an embodiment of the 
``simplicity-first'' recommendations of Holte~\cite{holte93}. 
Sophistication is unimportant if simpler methods perform as well as complex methods.
Holte found that extremely small trees were often as accurate as more complex trees. 
He cautioned the machine learning community to benchmark against simpler methods.

This point still holds, all of our methods are far less sophisticated than our prior rule-based learner. 
KEYS and astar both yielded cost-attainment results that met or exceeded those of the previous work while running orders of magnitude faster.
Rather, we should revise our original statement. Sophistication is unimportant if simpler methods perform as well as complex methods while yielding some sort of stability guarantee. SimpleSA, MaxFunWalk, and astar are all simpler methods than KEYS. Perhaps they are too simple. 
Perhaps there is some threshold point where, at one side, simple methods beat complex methods; on the other end, those methods are too simple to use.

We advocate the use of KEYS not only because it is competitive with TAR3, but because it offers a stability guarantee that the other algorithms in this paper do not.
 We attribute much of the  success of KEYS to 
the presence of $keys$ in the DDP models, those variables that
control everything else.  These key variables were exploited by KEYS using two methods:
\be
\item[1.] BORE finds promising keys with high probabilistic support;
\item[2.] KEYS' greedy search sets the most promising key,
before exploring the remaining options.
\ee
This also adds a stability factor throughout the operation of the algorithm. As more and more variables get locked down, KEYS finds itself unable to make a decision that could throw off the results. If KEYS is cut off at any point, a user would know what decisions had been made and the effect of those decisions. 
A project lead could find the minimal set of keys to set for the greatest effect by looking at the mitigations fixed during the first few rounds. 

Our algorithms are still not fast enough. Our current methods are more than enough for current models, 
but they are not quite good enough to deal with the projected future models. 
It is possible that the effects of Moore's Law will give our current techniques just enough of a boost,
but it is still worth investigating further optimizations. 

\section{Related Work}

\subsection{Keys}

Our Keys theory (ie. that the behavior of a large system is determined by a very small number of key variables) is not a new finding in the fields of Artifical Intelligence of Software Engineering. Keys have been discovered and rediscovered in AI many times. 
Elsewhere ~\cite{me03l}, we have documented dozens of papers that have reported this effect.
Often, the "key effect" has been reported under different names including {\em narrows, master-variables, backdoors,} and {\em feature subset selection},

Theoretically, clumps and collars are logically   
the expected average case properties of any model. 
Menzies \& Singh~\cite{me03l} 
previously computed the odds of a system selecting solutions
to goals using complex, or simpler, sets of preconditions.
In their
simulations, they found that a system will naturally select for tiny
sets of preconditions (a.k.a. the keys) at a very high probability.

Amarel ~\cite{Amarel86} observed that search problems contain narrow sets of variables or collars that must be used in any solution.
In such a search space, what matters is not so much how you get to these collars, but what decision you make when you get there.
Amarel defined macros encoding paths between {\em narrows}, effectively permitting a search engine to jump between them.

Druzdel~\cite{druzdel94} represented a model
as the product of
distributions of the model's variables,
Given  enough  variance in the individual priors 
and conditional probabilities of the variables, the 
frequency of model states will exhibit a 
log-normal distribution. Such a system would show the clumping effect; a small 
fraction of the states would cover a large portion of the total 
probability space, with the remaining states being negligible. 
He studied one piece of software
where the reached states were a vanishingly small fraction of the set of possible states.
In one diagnosis system 
with a total of
525,312 possible internal 
states, he found that there were a total of 49 states that were reached 91\% of the time and one one state was ever reached 52\% of the time.  

Numerous researchers have examined {\em feature subset selection}; 
i.e. what happens when a data miner deliberately 
ignores some of the variables in the training data. For example, Kohavi and John~\cite{kohavi97} 
showed in numerous datasets that as few as 20\% of the variables are $key$- the remaining
80\% of variables can be ignored 
without degrading a learner's classification accuracy. 

Williams et.al.~\cite{williams03} discuss how
to use keys  (which they call ``back doors'') to optimize search.
Contraining these back doors also constrains the rest of the program. 
So, to quickly search a program, they suggest imposing some set values on the key variables.
They showed that setting the keys
can reduce
the solution time of certain hard problems from exponential to polytime- provided that the
keys can be cheaply located- an issue on which Williams et.al. are curiously silent.

Crawford and Baker ~\cite{crawford94} compared the performance of a complete TABLEAU prover to a very simple randomized search engine called ISAMP.
Both algorithms assign a value to one variable, then infer some consequence of that assignment with forward checking. If contradictions are
detected, TABLEAU backtracks while ISAMP simply starts over and re-assigns other variables randomly. Incredibly, ISAMP took {\em less}
time than TABLEAU to find {\em more} solutions using just a small number of tries. Crawford and Baker hypothesized
that a small set of {\em master variables} set the rest and that solutions are not uniformly distributed throughout the search space.
TABLEAU's depth-first search sometimes drove the algorithm into regions containing no solutions. 
On the other hand, ISAMP's randomized sampling effectively searches in a smaller space.

\subsection{Model-driven Software Engineering}

Anthropologists have argued that the ability to build abstract models is what gives homo sapiens their competitive edge.
For almost as long as Software Engineering has existed, software engineers have developed models in order to gain insight about a concept.
In his article, "What Models Mean" ~\cite{seidewitz03},
Seidewitz describes the interactions and relationships between the
concepts of a model. He asserts that "a model's meaning has two aspects:
the model's relationship to what's being modeled and to other models derivable from it. Carefully considering both aspects can help us
to understand how to use models to reason about the systems we build..."
These are the aspects of a model's meaning that are focused on in {\em model-based} software engineering.

Model-based Software Engineering is becoming increasingly important.
The Object Management Group (OMG) has recently adopted a {\em model-driven architecture} framework with goals of "portability, interoperability,
and reusability through architectural seperation of concerns." ~\cite{omg03}
OMG uses the established standards of UML, the Common Warehouse Metamodel, and the Meat-Object Factory
to provide system interoperability in a vendor-neutral form ~\cite{brown06}. Microsoft has been devloping a {\em Software Factory} that utilizes models in order to automate the software development process ~\cite{greenfield04}. 
At Lockheed Martin, engineers have developed an integrated modeling method
called {\em Model Centric Software Development} that uses "automated
generation of partial implementation artifacts," reverse engineering
to integrate legacy assets, and model verification and checking ~\cite{waddington03}

The importance of the model-driven approach is not limited to software
design and UML. Many tools exist for modeling, some examples include
distributed agent-based simulations~\cite{clancey96a}, discrete-event 
simulations~\cite{law00,harrell00,kelton02,raffo05b,raffo05c}, 
continuous simulation (also called system dynamics)~\cite{hamid91,sterman00},
state-based simulation (including petri net and data flow approaches)
~\cite{akhavi93,harel90,martin00}, hybrid-simulation (combining discrete
event simulation and systems dynamics)~\cite{martin01,donzelli01,setamanit07},
logic-based and qualitative-based methods~\cite[chapter
20]{bratko01}~\cite{iwasaki89}, and rule-based
simulations~\cite{mi90}. 

One can find these models being used in the requirements phase(ie. 
the DDP tool described earlier), design refactoring using patterns ~\cite{france03}, software integration~\cite{denno03}, 
model-based security~\cite{jurjens06}, and performance assessment~\cite{bals04}.

Models are useful because humans can review, audit, and improve an explicit
representation of their systems.
However, as models grow in complexity, it becomes difficult
for a manual analysis to reveal all their subtleties. 
Hence, many researchers have proposed support environments to
help explore the increasingly complex models that engineers are
developing. Gray et al ~\cite{gray06} have developed the Constraint-Specification
Aspect Weaver (C-Saw), which uses aspect-oriented approaches ~\cite{filman04}
to help engineers in the process of model transformation.
Cai and Sullivan ~\cite{cai05} describe a formal method and tool called
{\em Simon} that "supports interactive construction of formal models,
derives and displays design structure matrices... and supports
simple design impact analysis." 
Other tools of note are lightweight formal methods such as ALLOY ~\cite{jackson02}
and SCR~\cite{heitmeyer02} as well as various UML tools that allow
for the execution of life cycle specifications 
(e.g. the CADENA scenerio editor ~\cite{child06}).

Our work utilizes a simpler ontology. Large groups, like those at NASA JPL, like this simplicity. 
We don't yet know how to mix ourtechniques withm ore complex ontologies like UML.

\subsection{Search-based Software Engineering}

The field of {\em Search-based Software Engineering} augments Model-based SE with {\em meta-heuristic} techniques like genetic algorithms, simulated annealing, and others to explore a model. Such heuristic methods are not complete; however, as Clarke et al remark, "...software engineers
face problems which consist, not in finding {\em the} solution,
but rather, in engineering an {\em acceptable} or {\em near-optimal solution} from a large number of alternatives." ~\cite{clarke03}

Search-based SE is most often used to optimize software testing ~\cite{jones96a,jones98,pargas99,tracey98}, but it has had applications in 
numerous other areas. With Martin Feather, we have used search-based
SE for requirements analysis ~\cite{feather03}.
Other researchers~\cite{harman02,lutz01} use genetic algorithms to
examine ways of modularizing software~\cite{clarke03} or develop effort estimators ~\cite{aguilar01,dolado00,dolado01}.
In all, Rela~\cite{rela04} lists 123 publications where search-based methods
have been applied to the above applications as well as others such as
automatic synthesis of software defect predictors, assisting in component design, developing multiprocessor schedules, re-engineering old systems into better ones, and searching for compiler optimizations.

To use a search-based approach, software engineers have to reformulate their problem by:
\bi
\item Finding a {\em representation of the problem} that can be 
symbolically manipulated (e.g. simulated or mutated). 
Such representations always exist with model-based SE. In our work, DDP is the representation of the problem
\item
Defining a {\em fitness function} (a.k.a. ``utility function'''' or
``objective function''); i.e.
an ``oracle'' that
scores a model configuration. Current model-based SE methods rarely offer
such a function (exception: formal methods that generate temporal constraints). In our experience, generating such a fitness function is
usually possible, albeit requiring days of work with the domain experts~\cite{me99j}. Our fitness function is the calculation of cost and attainment. 
\item 
Determining an appropriate set of {\em manipulation operators} 
to select future searches based on the prior
searches~\cite{harman01}.  Our manipulation operators are the various algorithms that we employ. 
\ei

\section{External Validity}

Our model examples come from software systems engineering at NASA's Jet Propulsion Laboratory (JPL).
Our use of JPL models injects a sampling bias into our results. Therefore, it is important to consider the generality of lessons learned from JPL: 
\bi
\item JPL conducts large software system design tasks for complex systems (e.g., software for satellites, ground systems to process the information transferred back from the satellites, etc.).  
An in-house team of over a hundred developers works on these systems, sometimes augmented with teams from external contractors or other NASA centers. 
JPL's managers face the same challenges as other managers; e.g. handling large teams with a wide range of talent and domain experience, all the while reacting appropriately to budget cuts and project redirections.  
\item We assert that industry could learn much from JPL systems engineering practices.  
A manager in a conventional project has a "delivery date", which often can be renegotiated with the client depending on what functionality is ready, changing business conditions, etc.  
A JPL software development manger, on the other hand, has fixed deliverable dates dictated by celestial mechanics in addition to the usual demanding programmatic constraints. Those dates may either be the launch date of the satellite or date at which the satellite will encounter the science event it is meant to process (for instance, the date when the satellite passes through the tail of a comet). Such dates are non-negotiable. JPL systems engineering methods have evolved to meet the demands of delivering complex systems, right when they are required for delivery. 
\ei

\section{Future Work}

While all of our algorithms are very fast, it is unclear if they will be sufficient for future models with more and more variables.
It may go without saying, but if you give a user a more powerful tool, they will build more elaborate designs.
The incredible advances made over previous treatment learning work may not be enough for some of the models being
generated at JPL today.

Therefore, there is still value in experimenting with other algorithms. 
One possible project would be to improve astar. Implementation of hash tables as well as other optimization tricks could make the astar search even faster. At the same time, we could enhance astar  with the BORE heuristic found in KEYS. 
If astar could be given the stability guarantee of KEYS while maintaining its runtime advantage,
we could potentially address far more complex models. 

If we want to scale KEYS to fit models with a more complex ontology, 
then some modifications will be required.
All of our algorithms have been designed to work with binary variables. They do very will with these binary mitigations; however, in other work,
we have seen disappointing
results with models containing variables with larger ranges.

KEYS could have value in other formats. In this paper, we adapted MaxWalkSat to work with our models.
Perhaps we could apply KEYS in reverse. Stochastic SAT solvers such as MaxWalkSat or the Markov Logic reasoning within ALCHEMY ~\cite{rich05}
could be biased by KEYS to find $key$ variables within the CNF clauses.
The effects of such an optimization
could be dramatic- recall from the above discussion that Williams et.al.~\cite{williams03}
reported that setting ``back doors'' (the keys) can reduce the solution time of hard problems
from exponential time to polytime.

[XXXX]

\section{Summary}
\noindent
In this experiment, we have:
\bi
\item
Described the DDP requirement models as well five public-domain, real-world examples of these models; 
\item
Described four new methods to optimize those models;
\item
Benchmarked those techniques against each other;
\item
Found the the KEYS algorithm yields the results with the least variance and an additional stability guarantee;
\item 
Offered some suggestions on future work, including: improved astar, KEYS with support for non-binary variables, and using KEYS to influence other algorithms.
\ei

All the software used in this study 
is  free for download and use\footnote{See 
\url{http://unbox.org/wisp/tags/ddpExperiment/install}}. We encourage other authors to download and experiment with our code. We also recommend that other authors offer their results in such a repeatable and improvable manner.

\bibliographystyle{abbrv}
\bibliography{refs} 
\end{document}
