\documentclass{sig-alternate}
\usepackage{wrapfig,cite,url,times}
\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}

\conferenceinfo{ICSE PROMISE Workshop}{2008 Leipzig, Germany}
%\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{
Optimization of Non-linear Design Models
%\titlenote{Submitted to the PROMISE 2008 workshop on repeatable SE experiments.
%%A draft version of this paper may be downloaded fro
%\url{http://menzies.us/pdf/08keys.pdf}
%}
}

\numberofauthors{2}
\author{
% 1st. author
\alignauthor
Omid Jalali, Gregory Gay, Tim Menzies\\
       \affaddr{West Virginia University}\\
       \affaddr{Morgantown, WV, USA}\\
       \email{ojalali@mix.wvu.edu}\\
	\email{greg@4colorrebellion.com}\\
       \email{tim@menzies.us}
% 3rd. author
\alignauthor
Martin Feather\\
       \affaddr{Jet Propulsion Laboratory,}\\
       \affaddr{California Institute of Technology,}\\
       \affaddr{Pasadena, California, USA}\\
       \email{martin.s.feather@jpl.nasa.gov}
}
\date{6 May 2008}

\maketitle
\begin{abstract}
SA's Jet Propulsion Laboratory has provided us with a set of five of their real-world requirements models, created using the 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 technique called KEYS, which identifies both the optimal solutions and the key factors leading to those solutions.

	While KEYS is an exciting new technique for optimizing the solutions for these models, it is unimportant if it does not improve on the results of classically accepted methods. This paper presents a series of experiments pitting KEYS against a classic stochastic search (Simulated Annealing), a state-of-the art local search (MaxWalkSat), and a powerful graph search (A*). 

\end{abstract}
%
%XXX search-based SE
%
% holte: simplicity first
%
% fails on non boolean ranges. amxsat?
%
%XXX other methods, maxwalksat, linear programming.
%
%XXX introduce keys during tar3
%XXX ita from annals paper
%XXX from itar to keys. knowledge comilation
%
%XXX why make it faster?
%	1) not fast enough. success reeds greater expecations
%	2) interactive design support : 2 second rule
%	3) new geenration of stochastic sat solvers~\cite{http://www.cs.rochester.edu/u/kautz/walksat/Maxwalksat20.tgz), markov logics~\cite{rich05} to try
%
% A category with the (minimum) three required fields
%\category{H.4}{???????Information Systems Applications}{Miscellaneous}
%A category including the fourth, optional field follows...
%\category{D.2.8}{??????Software Engineering}{Metrics}[complexity measures, performance measures]

%\terms{?????Delphi theory}

%\keywords{??????ACM proceedings, \LaTeX, text tagging}

\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, our DDP models strive to find the {\em least} costly project options that {\em most} increases the chance to obtain more requirements. Without these models, it would be far more difficult to achieve this non-linear optimization.

	Understandably, past success with these model-based tools ~\cite{fea02a,me03c,feather08} has led to high expectations from the user community. However, this is a potential problem. These models are becoming larger and larger. As requirements change, the users would like to reanalyze their past decisions.  Although many tools exist to  solve for that optimal pairing, they are too slow to handle these future models. With our current tools, we expect to fall off of a computational cliff in the near future. 

	Prior experiments with simulated annealing~\cite{feather08} and treatment learning~\cite{fea02a} took minutes to hours to terminate. Accordingly, we are concerned with finding {\em faster} techniques that meet or exceed the solution requirements for these models. Several of the techniques that we explored, including KEYS and astar, represent massive improvements in the time taken to find solutions. 

	We will spend the rest of this paper discussing DDP models; prior work; the KEYS technique; Simple Simulated Annealing; MaxFunWalk; astar; and comparison experiments done on all of these techniques. We hope to provide a clear picture of current experiments in model-based Software Engineering and provide a template for future experiments. 

\section{Defect Detection and Prevention}

The "Defect Detection and Prevention" tool~\cite{corn01,feather08} provides a powerful ontology for representing the design process. These models allow for the representation of the goals, risks, and risk-removing mitigations that belong to a specific project. For this reason, the DDP tool is heavily used at JPL to organize knowledge acquisition and decision making sessions with the NASA experts.

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 takes the engineering requirements of a project and maps them to a series of "risks." These risks are a representation of any of the factors that could prevent a goal from being reached. 
The third set of information contained in a DDP model is the set of mitigations, measures that may be implemented in order to alleviate risks. With this information, the stakeholders of a project can explore and choose a cost-effective set of mitigations that allows the most requirements to be met. This information can influence the entire design process and may lead to a more efficient development cycle.

\begin{figure}
~\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. The key ones are \textit{impacts},
each one of which is a quantitative estimate of the proportion of a requirement that would be lost should a risk occur, and
\textit{effects}, each one of which is a quantitative estimate of the proportion by which a risk would be reduced were a
mitigation to be employed (the ontology is also able to capture the phenomenon of a mitigation making some risks \textit{worse}).
\item \textit{Part-of relations}
structure the collections of requirements, risks and mitigations; 
\ei

~\hrule~
\caption{DDP's ontology}
\label{ddpont}
\end{figure}
\begin{figure}
\begin{center}
~\hrule~
\includegraphics[width=3.5in]{arrt.pdf}
\end{center}

{\small 
\bd
\item[Faces] denote requirements;
\item[Toolboxes] denote mitigations; 
\item[Skulls] denote risks;
\item[Conjunctions] are marked with one arc; e.g. \textit{require1} if
\textit{require2} and \textit{require3}. 
\item[Disjunctions] are marked
with two arcs; e.g. \textit{fault1} if \textit{fault2} or \textit{fault3}.
\item[Numbers] denote weights; e.g. \textit{action5}
 reduces the contribution of \textit{fault3} to \textit{fault1}, \textit{
fault1} reduces the impact of \textit{require5}, and \textit{action1}
reduces the negative impact of \textit{fault1}. 
\item[Oval] denotes
structures that are expressible in the latest version of the JPL
semantic net editor (under construction).
\ed
}
~\hrule~
\caption{A semantic net of the type used at JPL}%~\cite{fea01}} 
\label{arrt}
\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{arrt}.

The models created through this process (see Figure~\ref{ddpont}) may appear to be too weak for useful reasoning. 
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. 
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.

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

\section{Common Properties}

All of the algorithms that we use in this experiment share a couple of common properties. All of them use the same model format, and all except for one (SimpleSA) use 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}


One of the measures that we have taken to improve the runtimes of previous experiments is to use a method called {\em knowledge compilation}. 
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, 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.

This 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.

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.


\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 = 1 - \frac{\sqrt{((1-\overline{cost})^2 + \overline{att}^2}}{\sqrt{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{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}[!h]
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure SimpleSA
2. M:= set of mitigations
3. SCORE:= score of M
4. while K < KMAX && SCORE < MINSCORE
                 //minScore is a constant score (threshold)
5.    find a neighbor N close to M
6.    NSCORE:= score of N
7.    if NSCORE> SCORE
8.        M:= N
9.        SCORE:= NSCORE
10.   else if prob(SCORE,NSCORE,K, temp(K, KMAX)) > RANDOM)
11.       M:= N
12.       SCORE:= NSCORE
13.   K++
14. end while
15. return M
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for SimpleSA}
\label{fig:simplesa}
\end{figure}

It is important to note that SimpleSA is the only one of our algorithms to not use Euclidean distance as a scoring heuristic. Instead, SimpleSA uses a linear combination of cost and attainment:
\begin{equation}\label{eq:ps}\small
SCORE = costFactor * cost + attFactor * attainment
\end{equation}
where costFactor and attFactor are set by the user (defaults are 0 and 1 respectively).

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. 

\section{MaxFunWalk}

The boolean satisfiability problem is a well-known one in computer research circles. 
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}[!h]
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure MaxFunWalk
2. for I:=1 to MAX-TRIES
3.    S:=A randomly generate assignment of mitigations
4.    for J:=1 to MAX-CHANGES
5.        if SCORE satisfies THRESHOLD return
6.        C:= a random selection of mitigations from S
7.        with probability P
8.            flip a random setting in C
9.        with probability (P-1)
10.           flip a setting in C 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. 

\section{astar}

The A* graph search algorithm should be a familiar one to anyone involved with the video game industry or the Artificial Intelligence field. 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}[!h]
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure astar
2. S:= Starting assignment of mitigations
3. C[0]:= Add starting position to closed list
4.
5. while END:= false
6.    N:=list of neighbors
7.    for each N
8.        if N is not in C
9.            G:=distance from start
10.           H:=distance to goal
11.           F:=G+H
12.           if F<BESTF
13.               BESTN:=N
14.   end for
15.   S:= BESTN
16.   C[++]:=Add new state to closed list
17.   if STUCK
18.       END:= true
19. end while	
20. return S
\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. 
\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.  

\subsection{Setting astar's "Goal"}

Like several of our other algorithms, the user may give astar some sort of ideal goal. However, astar's goal setting is fundamentally different from the others. Part of astar's optimality is that it underestimates the distance to the goal. 
Because of this, and because of the fact that the exact nature of the mitigations limits the number of reachable states, the astar algorithm will never actually reach a goal. Therefore, it makes more sense to treat the goal as a compass direction. We could never reach a state with a cost of 0 and an attainment of 300, but this would be a perfectly valid goal to set for the astar algorithm. It will travel in the direction of that solution and find the best end state that it can reach. 

\begin{figure}[!h]
\begin{center}
\includegraphics[width=2.3in]{searcharc-2D.pdf}
\end{center}
\caption{Arc formed along the edge of the search space} 
\label{fig:searcharc}
\end{figure}

While a 0 cost and high attainment (dependent on the model) goal was set for most of our experiments, interesting results were still found from other goals. By first setting a goal with negative cost, then a goal with negative cost and negative attainment, 
we were able to plot out the edges of our search space. 
The results of this rough mapping can be seen in figure ~\ref{searcharc} 
We are not actually concerned with mapping out our search space for this experiment; however, the astar tool could be used in other experiments for this very purpose. 

\section{KEYS}

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. 

The data miners used on our DDP models were the TAR2 and TAR3
{\em treatment learners}~\cite{hu02,fea02a,me02c,me03c,me03j,clark05,greenwald06,feather08}. 
The premise of such treatment learning is that within the space of possible
decisions, there exist a small number of $key$ decisions that
determine all others. 
The KEYS algorithm is similar to the previous treatment learners, but utilizes a few tricks to achieve a much faster runtime. 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\}$.

\subsection{Theoretical Evidence}

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.

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. 

\subsection{Empirical Evidence}
There is a large amount of empirical evidence for the validity of these theoretical predictions.
Keys, collars and clumps have been widely reported (albeit by different names).
A sample of those empirical results are offered below (for more, see~\cite{me03l}):

{\em Keys:} 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. 

{\em Clumps:} Druzdzel~\cite{druzdel94}
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.  

{\em Collars:} 
Williams et.al.~\cite{williams03} discuss how
to use keys  (which they call ``back doors'') to optimize search.
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.

\subsection{The KEYS Algorithm}

The previously used TAR3 learner generated hundreds
of treatments, then pruned all but the best $M$. KEYS is an
experiment in building one rule per variable, with no post-pruning. 
Therefore, KEYS represents a massive runtime improvement over TAR3. 
There are two main components to KEYS - a greedy search and the BORE ranking heuristic.

\subsubsection{Greedy Search}
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 mitigation value is 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.  

\subsubsection{BORE = \underline{B}est \underline{Or} \underline{R}est}

The lift calculation used by TAR3 is a heuristic measure with no theoretical basis. It can favor
treatments based on very small portions of the training set. 
KEYS replaces the lift heuristic with an alternative Bayesian ranking measure, better founded in theory, with a 
support measure.

BORE~\cite{clark05} assumes that the output scores are divided into two classes - 
one class for $best$ outcomes and one for the $rest$.
In such two-class systems, TAR3's lift calculation
can be replaced with a search for mitigation values that have a high probability
of belonging to the $best$ set.

BORE 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 incredibly tiny. 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}.

\subsection{Result Comparisons}

\begin{figure}[!b]
\begin{center}
\includegraphics{WithLabel/2/AStar.pdf}
\includegraphics{WithLabel/2/KEYS.pdf}
\includegraphics{WithLabel/2/MaxFunWalk.pdf}
\includegraphics{WithLabel/2/SA.pdf}
\end{center}
\caption{Results on Model 2} 
\label{fig:res2}
\end{figure}

\begin{figure}[!b]
\begin{center}
\includegraphics{WithLabel/4/AStar.pdf}
\includegraphics{WithLabel/4/KEYS.pdf}
\includegraphics{WithLabel/4/MaxFunWalk.pdf}
\includegraphics{WithLabel/4/SA.pdf}
\end{center}
\caption{Results on Model 4} 
\label{fig:res4}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{WithLabel/5/AStar.pdf}
\includegraphics{WithLabel/5/KEYS.pdf}
\includegraphics{WithLabel/5/MaxFunWalk.pdf}
\includegraphics{WithLabel/5/SA.pdf}
\end{center}
\caption{Results on Model 5} 
\label{fig:res5}
\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{res2}, ~\fig{res4}, and ~\fig{res5}. Attainment is along the x-axis and cost (in thousands) is along the y-axis.

These graphs give a clear picture of the results obtained by our four algorithms. We can easily rule out SimpleSA. 
While it performs well enough on Model 2, its results on Models 4 and 5 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. 
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& 0.011   &0.053         &0.115   \\ \hline
MaxFunWalk& 0.122   &0.429   &0.398         \\ \hline
SimpleSA& 1.090   &2.620        &3.690  \\ \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 the clear winner when looking at time to execute. Even on the largest model, astar is over twice as fast as its nearest competitor, KEYS. 


\subsection{Internal Convergence}

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

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

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

If astar and KEYS obtains somewhat similar results  and astar is twice as fast, 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. 

For both algorithms, cost improvements are dramatic for about 20 rounds, 
after which they tend to stabilize. astar hits a minimal cost point earlier than KEYS, but seems to go back up a little bit as attainment rises.
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. 

\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 TAR3. 
KEYS and astar both yielded cost-attainment results that met or exceeded those of TAR3 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. 

\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.

\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/keys/1.0}\newline\url{http://unbox.org/wisp/tags/astar/1.0}}. 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}
