% This is "sig-alternate.tex" V1.7 MARCH 2007
% This file should be compiled with V2.1 of "sig-alternate.cls" MARCH 2007
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.1 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.1) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@acm.org)
% ===============================================================
%
% For tracking purposes - this is V1.7 - MARCH 2007

\documentclass{sig-alternate}
\newcommand{\aive}{{\"aive}}
\usepackage{times}
%-- Begin patch area for accents in 'Author Block' area - may be needed by some authors / but not all
\DeclareFixedFont{\auacc}{OT1}{phv}{m}{n}{12}   % Needed for "Author Block" accents - Patch by Gerry 3/21/07
\DeclareFixedFont{\afacc}{OT1}{phv}{m}{n}{10}   % Needed for "Author Block" accents in the affiliation/address line - Patch by Gerry 3/21/07
%--
\usepackage{color,cite,tricks}
\usepackage{url,amssymb}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\hmm}[1]{{\underline {\bf #1}}}
\begin{document}
%
% --- Author Metadata here ---
\conferenceinfo{IWLU'07}{Atlanta, Georgia, USA}
\CopyrightYear{2007} % 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.
% --- End of Author Metadata ---

\title{On the Value of Stochastic Abduction\\(if you fix everything, you lose fixes for everything else)}
\numberofauthors{2} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{ 
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Tim Menzies, \\Oussama Elrawas, Dan Baker\\
       \affaddr{Lane Dept. CSEE}
       \affaddr{West Virginia University, USA}\\
       \email{tim@menzies.us}.
	\email{oelrawas@mix.wvu.edu}
\email{danielryanbaker@gmail.com}
% 2nd. author
\alignauthor
Jairus Hihn\\Karen Lum\\
       \affaddr{Jet Propulsion Laboratory}\\
       \affaddr{California, USA}\\
       \email{jairus.hihn@jpl.nasa.gov}
       \email{karen.t.lum@jpl.nasa.gov}
}
      % There's nothing stopping you putting the seventh, eighth, etc.
% author on the opening page (as the 'third row') but we ask,
% for aesthetic reasons that you place these 'additional authors'
% in the \additional authors block, viz.
\date{\today}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle

% A category with the (minimum) three required fields
%\category{D.2.9}{Software Engineering}{Effort Estimation}
%A category including the fourth, optional field follows...


\pagestyle{plain}
%\section{Introduction}

%In the $21^{st}$ century, it is common place to
%find
%large complex
%software systems running on multiple platforms being
%being maintained and extended by international communities, interacting only via electronic means:
%e.g. ECLIPSE or  the continually evolving LINUX project(s).
%Decades of research
%has yielded tools and techniques that allow even a single individual
%to built complex software: e.g. Stallman \& EMACS
%or Torvalds \& LINUX (v1.0) 
%or
%Matsumoto \&  RUBY.  
%None of this would have been possible with decades of research into automating, simplifying, and improving
%common software engineering (SE) tasks. 
%
%Having addressed the {\em generation} problem 
%the focus of the automated  SE community
%has changed.
%Traditionally, uncertainty is viewed as a  bad thing.
%For example, if the manager
%of a software project confessed to not knowing some detail
%of their project, they might be forced into extensive analysis
%or prototyping to resolve that unknown.
%Also, a truism of safety crtical systems is that uncertainty in the form
%of nondeterminsim
%should be avoided at all costs~\cite{leven95}.
%
%To be sure,
%there are times when unceratinty is dangerous. 
%The software controller of the ascent stage of a manned
%spacecraft should  be a deterministic algorithm with guaranteed
%performance properties. Using anything else at this stage of the
%mission is as crazy as   {\em not} using (say) random search to assist
%in on-board diagnosis when the craft is (a)~in deep space and (b)~in
%deep trouble and (c)~it takes too long to ask for help from ground
%control.
%
%While  aspects of some domain remain fluid, it is
%possible to explore the decision space to find a better set of
%decisions. 
%A premature commitment to particular
%decisions, without extensive exploration, can be quite detremental.
%If the  range of possible decisions is fixed to a single set decision,
%then our ability to effect further optimizations disappears.  To
%put that another way:
% {\em
%if you fix everything, you lose  fixes for  everything else.  }
%
%More generally, we argue that uncertainty exploration is a core process
%within many tasks. 
%For some years~\cite{me95}, we used {\em abduction}
%as a framework for exploring uncertainty. The computational overheads
%of that method forced its  abondonment. However,
%recent success with stoachasitc pre-processing
%now make us more optimistic about the utility of abduction.
%Our implementation looks nothing like an
%abdictive theorem prover (for example,
%there is no assumption of declarative clausal representations). Rather,
%our proposed architecture is more like deKleer's original vision of the ATMS~\cite{deKleer86}:
%i.e. a intelligent working memory that stores and reflects on the results of some seperate
%inference procedure.
%

\section{Introduction}

Back in the 1980s, the model-based diagnosis (MBD)
community explored qualitative representations~\cite{will91}. 
Since they are not overly-specific,
such representations can be quickly collected in a new domain. Indeed, in domains where information
is limited, there may be no alternative to qualitative representations since their is not enough
information to build precise quantitative theories.

Qualitative theories are inherently   nondeterministic~\cite{kuipers86} but, argued MBD researchers,
they can
generate a wider range of options for  diagnosis and repair. 
Creative solutions
can sometimes be found in larger space of possible qualitative
 behaviors than in the tighter space of precise quantitative behaviors.
To  put that another way:\begin{quote}{\em If you fix everything, you lose  fixes for everything else.} \end{quote}


Previosuly, we have explored tools for searching models containing uncertainities~\cite{me95}.
Standard quantitative sensitivity analysis~\cite{kleijnen97}
 may be inappropriate 
for non-linear theories or theories containing inconsistency predicates.
Motivated by work on qualitative simulation and non-montonic logics, we
defined those tools in terms of logical  abduction~\cite{me95a}. 
Given 
a theory $T$ and a goal $G$, the abductive problem is to find assumptions $A$ that lead to the goal,
without causing inconsistencies~($\perp$): 
\begin{eqnarray}
T \wedge A& \vdash &G\\
T \wedge A& \not\vdash& \perp
\end{eqnarray}
Informally, equation (1) is saying ``do something'' and equation (2) is saying ``but don't do dumb things''.

In the general case, equations (1) and (2)
leads to the generation of multiple worlds $W$ of belief where each world is characterized
by  incompatible assumptions (and no world is a subset of a large world w.r.t. size). 
Worlds are also called {\em extensions} in Reiter's default logic~\cite{reiter80}, {\em scenarios} in Poole's THEORIST system~\cite{poole88},
or envisionments in the ATMS~\cite{deKleer86}.

In our HT4 abductive algorithm~\cite{me95}, a preference predicate $best$ selects 
the subset of preferred worlds. Elsewhere~\cite{me96a}, 
we
have argued that a wide-range of knowledge-level tasks can be implemented via different $best$ predicates. For example:
\bi
\item Diagnosis prefers worlds that contain the greatest number of faults,
with fewest root causes (ideally, one).
\item Planning prefers worlds with the least cost to traverse;
\item Explanation prefers the worlds with the largest intersection with concepts the user has already learned;
\item Monitoring requires caching the generated worlds, pruning any world that contradicts any incoming data.
In this framework, at any time, the remaining worlds contain  the set of possible remaining plans.
\item For other applications of abduction, see~\cite{kakas98,will92,russo01,reggia85,me96a,me97a,me97i,me97m,pople73,me99g,orourke90,poole88,poole93g}.
\ei
That is, once you have a good way to explore uncertainty, you have an engine
that can handle a very large number of tasks

While the generality of the above framework was compelling, that
research floundered on the computational cost of abduction.  With
no inconsistency checks, abduction takes  linear time for propositional
theories~\cite{dowl84}.  However, the inconsistency check makes
abduction computation NP-hard~\cite{by91}.  Experimentally, HT4's
runtimes proved to be exponential on model size and never scaled
to anything larger than medium-sized models.

Recent success with stochastic methods have made us revisit
abduction. We offer one case study here where a heuristic pre-processor 
reduces a potentially exponential time process to  linear time. The results
are preliminary (from just one set of models) but they are promising enough
to motivate further exploration.

\section{``Collars'' Variables}

Surprisingly,
our abductive reasoner produce surprisingly few worlds. Or, to be more precise,
it produces worlds that contain similar sets of goals. For example, in one study, the number of goals reached in any
randomly selected world was nearly the same as the maximum number of goals found in any world~\cite{me99g}.

We first suspected this was a quirk of the model used in that study.
However, it turns out to be a general result.
A repeated conclusion in AI is that the behavior of 
a large system is determined by a very small number of key
variables,
which we call the {\em collar}~\cite{me06a} variables.
Collars have been discovered and rediscovered
in AI many times, and given different names including 
{\em variable subset selection}~\cite{kohavi97}, % doesn't quite agree with "Collars", but I don't know how to fix it (do)
{\em narrows}~\cite{amarel86},
{\em master-variables}~\cite{crawford94}, 
 {\em back doors}~\cite{williams03}, minimal envisionments~\cite{deKleer86}, just to name a few.
Note that if the collar contains just a few variables,   then few worlds will be generated: just one for every consistent setting
to the collar variables.

Analogous results have been reported in software engineering literature.
Observe that if a system is controlled by its collar, and the collar variables are few
in number, then a stochastic sampling of the system will soon {\em saturate}; i.e. no new states will
be found after exploring the combinations of the settings to the collar variables,
Saturation has been observed in the knowledge engineering and software engineering literature:
\bi
\item
Horgan \& Mathur~\cite{horgan96} document systems were most
program paths get exercised early with little further improvement
as testing continues.
\item
With Owen \& Cukic~\cite{me02d} and Goa et.al.~\cite{goa06},
we have shown that the number of new states found in a stochastic  
search of a formal model quickly saturates.
\item
Mutation testers often report that a small sample of their
mutations\footnote{A {\em mutant} of a program is a syntactically
valid but randomly selected variation to a program; e.g. swapping
all plus signs to a minus sign.}
perform just as well
as a much much larger number of mutations~\cite{michael97,wong95,budd80,acree80}.
\item
Druzdzel~\cite{druzdel94} studied
a diagnosis application for monitoring 
patients in intensive care. Although 
the software had 525,312 possible 
internal states, the application reached 
few of them at runtime: one of the 
states occurred 52 percent of the time, 
and 49 states appeared 91 percent of 
the time. 
\ei

Not only is saturation a repeated result, it can be
shown mathematically
that  it is the
expected behavior of any system of variables~\cite{me03l,druzdel94}. 
Druzdel observes that
if software has $n$ variables, each with its own
assignment probability distribution of $p_i$, then the probability
that  software will fall into a particular state is
\begin{center}
\mbox{\(p=p_1p_2p_3...p_n=\prod^n_{i=1} p_i .\)}
\end{center}
\noindent
By taking logs of both sides, this equation becomes
\begin{center}
\mbox{\(\mbox{ln}~p = \mbox{ln}\prod^n_{i=1}p_i=\sum^n_{i=1}\mbox{ln}~p_i\)}.
\end{center}
The asymptotic behavior of such a sum of random variables
is addressed by the central limit theorem.
In the case
where we know very little about software, $p_i$ is uniform and many
states are possible. However, the {\em more} we know about  software
the more varied the individual distributions.
Given
enough variance
in the individual priors and conditional probabilities or
$p_i$, the expected case is that the frequency with which
we reach states will exhibit a
log-normal distribution; i.e. a small fraction of states can be
expected to cover a large portion of the total probability space; and
the remaining states have practically negligible probability~\cite{druzdel94}.
If the reachable states are few, then the deltas between them (the collar settings)
are also few.

\section{Exploiting the Collars}

In summary, while abduction is {\em theoretically} slow, it need not be slow
{\em in practice}.
The trick is to reverse the usual abductive procedure of, e.g. the ATMS~\cite{deKleer86}.
The ATMS was designed as a working memory 
that stores the conclusions of a separate inference engine.
Inferences are passed to the ATMS along with a 
{\em justification} (a conjunction) for each inference. These
justifications were then woven into a subsumption network, the roots
of which are the  assumptions that select the different
set of reachable beliefs (and we would call those root assumptions
the collar settings).
In that approach, the collars are found after the inference.
\[
inference \rightarrow collars \rightarrow  worlds
\]
An alternative is to find the collars
{\em before}
the inference.
\begin{equation}\label{eq:peek}
peek\rightarrow collars \rightarrow worlds \rightarrow inference
\end{equation}
The results of \S2 suggest that  a stochastic sampling method
could {\em peek} at the  reachable
states (via some Monte Carlo simulation).
If each of the $n\in N$ peeks
is scored by some domain-specific predicate, then
the collars can then be identified as the variables with {\em
very different
frequency in the high scoring samples than in the low scoring samples}.

One world exists for each consistent set of settings to the collars.
Since worlds are internally consistent,
inference within them can be very fast. Williams et.al
report that  setting the collar variables (which they call 
{\em backbones}~\cite{williams03}) can reduce exponential time 
inferences to polynomial time.


If inference takes time $k$,
then after $peek$ing, \eq{peek}
 takes time $O(k*2^C)$ where $C$ is the number of
ranges the collars. Since the number
$C$ is often much less than the 
total
number of ranges in the entire theory, this is a win. 
However,
it is still an exponential time process.

We show below that, given a certain kind of
$best$ predicate, it is possible to reduce \eq{peek} to
$O(k)$. If  $peek$ing sorts the collar settings from best to worst,
the worlds and inference can be explored using a greedy search that
stops when the next world scores little better than the previous one.
  
 
\section{Case Study}
This case study is based on the STAR algorithm.
A summary of STAR is offered below. For full details, see~\cite{me07f}.
STAR's current implementation explores three software process models:

\bi
\item
The COQUALMO software defect predictor~\cite[p254-268]{boehm00b};
\item
The  COCOMO software effort predictor~\cite[p29-57]{boehm00b}; 
\item
The THREAT   predictor for software project effort \& schedule overrun~\cite[284-291]{boehm00b}.
\ei

In standard practice, these models are tuned to  local data.
Unfortunately, 
   the data required for
   such local tuning is difficult to obtain, especially across multiple
   organizations~\cite{me06d}.  This is due to  the business sensitivity associated
   with the data as well as differences in how the metrics are defined,
   collected and archived.  In many cases the required data has not been
   archived at all.  For example, after two years we were only able to
add 7 records to our NASA wide software cost metrics repository.

After decades of research, the space of possible local tunings
is well defined. The above three models contain relationships between (e.g.) software
process decisions and defect removal. These are linear equations, defined by a
 slope $m$,
and features learned from the domain $\{a,b\}$.
Varying $\{a,b,m\}$ across the space of known tunings will
sample the space of possible behaviors.




\begin{figure}[!t]
\begin{center}
\scriptsize
\begin{tabular}{c|lrr|lr}
       &\multicolumn{3}{c|}{ranges}      &\multicolumn{2}{c}{values}\\\hline
project&feature&low&high&feature&setting\\\hline
&prec&1&2&data&3\\
OSP:&flex&2&5&pvol&2\\
Orbital&resl&1&3&rely&5\\
space&team&2&3&pcap&3\\
plane&pmat&1&4&plex&3\\
&stor&3&5&site&3\\
&ruse&2&4&&\\
&docu&2&4&&\\
&acap&2&3&&\\
&pcon&2&3&&\\
&apex&2&3&&\\
&ltex&2&4&&\\
&tool&2&3&&\\
&sced&1&3&&\\
&cplx&5&6\\
&KSLOC&75&125\\
\hline
&prec&3&5&flex&3\\
OSP2 &pmat&4&5&resl&4\\
&docu&3&4&team&3\\
&ltex&2&5&time&3\\
&sced&2&4&stor&3\\
&KSLOC&75&125&data&4\\
&&&&pvol&3\\
&&&&ruse&4\\
&&&&rely&5\\
&&&&acap&4\\
&&&&pcap&3\\
&&&&pcon&3\\
&&&&apex&4\\
&&&&plex&4\\
&&&&tool&5\\
&&&&cplx&4\\
&&&&site&6\\
\hline
&rely&3&5&tool&2\\
JPL &data&2&3&sced&3\\
flight&cplx&3&6&&\\
software&time&3&4&&\\
&stor&3&4&&\\
&acap&3&5&&\\
&apex&2&5&&\\
&pcap&3&5&&\\
&plex&1&4&&\\
&ltex&1&4&&\\
&pmat&2&3&&\\
&KSLOC&7&418&&\\
\hline
&rely&1&4&tool&2\\
JPL &data&2&3&sced&3\\
ground&cplx&1&4&&\\
software&time&3&4&&\\
&stor&3&4&&\\
&acap&3&5&&\\
&apex&2&5&&\\
&pcap&3&5&&\\
&plex&1&4&&\\
&ltex&1&4&&\\
&pmat&2&3&&\\
&KSLOC&11&392&&\\
\end{tabular}
\end{center}
\caption{Four case studies.}\label{fig:cases}
\end{figure}

Another source of variability in the model behavior are the input features. 
\fig{cases} shows the range of those inputs for the four case studies explored in this paper:
\bi
\item OSP is the GNC component of NASA's 1990s {\em Orbital Space Plane} experiment;
\item OPS2 is a later version of OSP;
\item Flight and ground systems reflect typical ranges seen at NASA's Jet Propulsion Laboratory. 
\ei

The inputs of \fig{cases}  are explained in \fig{emsf2}. All these features can range over \mbox{$1\le x\le 6$}.The input features
 either {\em ranges} (a space of options)
or are  fixed to one {\em value}; e.g.  line one of \fig{cases} says:
\bi
\item
the $prec$ input is constrained to \mbox{$prec \in \{1,2\}$} 
\item
the $data$ input is fixed to $data=3$.
\ei

\begin{figure}
\begin{center}
{\scriptsize
\begin{tabular}{l|r@{:~}l|}\cline{2-3}
scale   &prec & have we done this before?\\
factors &flex & development flexibility \\
(exponentially        &resl & any risk resolution activities?\\
 decrease       &team &  team cohesion\\
 effort)       &pmat & process maturity\\\hline
upper  &acap & analyst capability\\
(linearly       &pcap & programmer capability\\
 decrease      &pcon & programmer continuity\\
effort)       &aexp &  analyst experience\\
       &pexp &  programmer experience\\
       &ltex &  language and tool experience\\
       &tool &  tool use\\
       &site &  multiple site development\\
       &sced & length of schedule   \\\hline
lower &rely &    required reliability  \\
(linearly      &data &   secondary memory  storage requirements\\
increase      &cplx &  program complexity\\
effort)      &ruse &  software reuse\\
      &docu &   documentation requirements\\
      &time &   runtime pressure\\
      &stor &   main memory requirements\\
     &pvol &    platform volatility  \\\cline{2-3}
\end{tabular}}
\end{center}
\caption{{
The COCOMO~II scale factors and effort multipliers.}}\label{fig:emsf2}
\end{figure}

\fig{cases} does not mention all the  possible
inputs.  For example, COQUALMO has inputs for
use of {\em automated analysis}, {\em peer
reviews}, and {\em execution-based testing tools}. For all inputs
not mentioned in \fig{cases}, values are picked at random
$1 \le x \le 6$.

STAR's  simulated annealer explores the possible inputs and $\{m,a,b\}$
values looking for constraints to these ranges that  minimizes effort ($Ef$) and defects ($De$) and
threats ($Th$). More precisely, the simulated annealer tries to minimize the {\em energy function}:
\begin{equation}\small\label{eq:eng}
E=\left(\sqrt{\overline{Ef}^2 + \overline{De}^2 + \overline{Th}^2}\right) / \sqrt{3}
\end{equation}
Here, $\overline{x}$ is a normalized value 
$0 \le \frac{x - min(x)}{max(x) - min(x)} \le 1$. 
Hence, our energy ranges $0 \le E \le 1$ and
{\em lower} energies are {\em better}.

The simulated annealing creates  a log showing what attribute  are associated with higher or lower energies.
STAR's forward select algorithm sorts those ranges in increasing order of associated energy. Then, for the controllable input features $C$,
STAR imposes the top $1 \le X \le C$ ranked ranges and re-runs COCOMO, COQUALMO, and THREATS 1000 times.
The median energy  seen in those 1000 runs is collected. 
Let $Min$ be some value $1 \le Min \le C$ associated with minimum median energy seen in the above forward select experiment.
A {\em policy} are all the ranges see in $1 .. Min$.

It is insightful to compare the effects of STAR's policies with more traditional methods. SCAT and 2CEE are 
effort estimation tools developed in-house by the authors
at JPL.
Both SCAT and 2CEE accept inputs like \fig{cases}
and output a range of effort estimates. SCAT uses fixed $\{a,b\}$ values (derived from historical logs of JPL systems) while
2CEE derives ranges for $\{a,b\}$ based on historical data.
Neither of these models vary $m$;
rather, they reuse the  $m$ values proposed from Boehm~\cite{boehm00b}. 


\begin{figure}[!b]
\begin{center}
\includegraphics[width=2.5in]{median.pdf}
\end{center}
\caption{Effort estimations from two standard methods
(SCAT, 2CEE) and STAR.}\label{fig:results}
\end{figure}

\fig{results} compares the median effort estimate predictions found by in SCAT, 2CEE, and STAR (defect and threat estimates are not shown since SCAT and 2CEE
only contain effort models). 
In one case, all the estimates were similar (OSP2) but for the others,
STAR's forward select found input ranges that greatly reduced the developed effort:
e.g. for ground systems, STAR's preferred inputs yielded estimates that were 6.4
and 5.4 times smaller than SCAT or 2CEE, respectively.

When we first saw these results, we suspected a bug.
Then we realized that unlike SCAT and 2CEE, STAR doesn't just make estimates.
STAR also tries to minimize those estimates. The impact of altering the input
ranges can be quite dramatic. 
\fig{coceffects} 
shows the known relative productivity effects
of changing project features.
The product of those productivity effects shows the total impact of
decisions regarding inputs on effort estimation:
\begin{quote}
11,022.4 = 3.53 * 2.38 * 1.63 * 1.54 * 1.53 * 1.52*1.51 * 1.51 * 1.5 *
1.49 * 1.46 * 1.43 * 1.43 * 1.43 * 1.42 * 1.4 * 1.39 * 1.33 *
1.31 * 1.29 * 1.32 * 1.26.
\end{quote}
That is, if projects were free to do anything at all,  the process decisions
of \fig{emsf2} can change total effort by three orders of magnitude.
STAR was only able to reduce the cost of building (e.g.) JPL's ground systems
by a factor of $\approx 6$ since \fig{cases} constrained the space of possible choices.


\begin{figure}[!t]
\scriptsize
\begin{center}
\begin{tabular}{l@{}|l@{~}r@{~}l}
%& & relative\\
id & features  & relative weight\\\hline
1&Personnel/team capability  & 3.53	&\rule{17mm}{2mm}\\
2&  Product complexity & 2.38&	\rule{12mm}{2mm}\\
3& Time constraint & 1.63&	\rule{8mm}{2mm}\\
4&    Required software reliability & 1.54&	\rule{8mm}{2mm}\\
5&    Multi-site development   &	1.53&	\rule{7mm}{2mm}\\
6&       Doc. match to life cycle  & 	1.52	&\rule{7mm}{2mm}\\
7&  Personnel continuity  &	1.51&	\rule{7mm}{2mm}\\
8&  Applications experience & 1.51	&\rule{7mm}{2mm}\\
9& Use of software tools & 1.50	&\rule{7mm}{2mm}\\
10& Platform volatility & 1.49&	\rule{7mm}{2mm}\\
11& Storage constraint & 1.46&	\rule{7mm}{2mm}\\
12& Process maturity  &	1.43	&\rule{7mm}{2mm}\\
13&    Language \& tools experience  &	1.43	&\rule{7mm}{2mm}\\
14&     Required dev. schedule & 1.43	&\rule{7mm}{2mm}\\
15&Data base size & 1.42&	\rule{7mm}{2mm}\\
16&  Platform experience & 1.40&	\rule{7mm}{2mm}\\
17&     Arch. \& risk resolution  &	1.39&	\rule{7mm}{2mm}\\
18&  Precedentedness  &	1.33&	\rule{6mm}{2mm}\\
19&  Developed for reuse  	&1.31	&\rule{6mm}{2mm}\\
20& Team cohesion  &	1.29&	\rule{6mm}{2mm}\\
21&    Development mode   &	1.32	&\rule{6mm}{2mm}\\
22& Development flexibility &	1.26	&\rule{6mm}{2mm}\\
\end{tabular}
\end{center}
\caption{Relative effects  on development effort.
Data from
a regression analysis of 161 projects~\protect\cite{boehm00a}.  
}\label{fig:coceffects}
\end{figure}
\section{Discussion}
\fig{results} illustrates the same effect reported in the introduction
by the
model-based diagnosis community.
Creative solutions
can sometimes be found in a
large space of possible behaviors (STAR)
than in a tighter space of more precisely defined behaviors (SCAT, 2CEE).

These results show how the
premature fixing of the options can prevent an analysis from proposing
novel fixes. For example, observe that:
\bi
\item
 In \fig{cases}, OSP2's fixed
values are more extensive that the other three cases.
\item
In \fig{results}, STAR reduced the effort by the least amount of the other case studies.
\ei
We speculate that if STAR had been applied earlier in the life cycle of OSP2, then
a different and cheaper project could have been selected.

STAR is an abductive inference engine. The theory $T$ is
the combined COCOMO, COQUALMO, THREAT models.
The assumptions $A$ of Equations 1 and 2 are the {\em policies}
found by STAR's forward select. 
The $best$ predicate
that selects the preferred worlds is the energy function of \eq{eng}
that ranks the ranges.
If $k$ is the time required to run COCOMO,COQUALMO, and THREAT,
then STAR runs in $O(k)$ time using its greedy search down the ranked list
of ranges.
Hence, STAR runs fast (under 10 seconds for the simulated annealing and forward select
for each of the test cases in \fig{cases}).
 

Our previous implementation of this approach was called 
the TAR3 {\em treatment learner}~\cite{me03e}.
A treatment learner finds a minimal contrast set that distinguishes
desired from undesired outcomes.
With Feather, we have
used treatment learning~\cite{fea02a} to find the key decisions within 
requirements models.
Treatment learning assumes that there is very little control of the 
device generating the training data. STAR was designed
assuming a fine-grained integration between the data generator
and the learner. 

There is much to recommend STAR over TAR3.
STAR generated all our case study results
in 
less than a minute. A similar range ranking,
by TAR3,
would 
require 
20 to 30 minutes to 
generate feature range rankings. 
 whose $peeks$ rank the 
rank collar settings in a best to worst order.

STAR looks nothing like a logical theorem prover.
In this case study, for example, STAR watched over a procedural system
and not a system represented as a set of clauses.
As observed by Kakas et.al.~\cite{kakas01} abduction is a 
{\em knowledge-level}
inference procedure~\cite{newell82} which, under the hood, can be implemented by any number of symbol-level heuristic
methods. 

\section{Conclusion}

Traditionally, uncertainty is viewed as a  bad thing.
To be sure,
there are times when unceratinty is dangerous. 
The software controller of the ascent stage of a manned
spacecraft should  be a deterministic algorithm with guaranteed
performance properties. Using anything else at this stage of the
mission is as crazy as   {\em not} using (say) random search to assist
in on-board diagnosis when the craft is (a)~in deep space and (b)~in
deep trouble and (c)~it takes too long to ask for help from ground
control.

Previously, we have explored uncertainty analysis in an abductive framework but
that work floundered on the compuational cost of abduction.
Recent success with a stochastic pre-processor to find the ``collar'' variables
suggest that
we can return to researching abduction as a general
framework for software engineering and knowledge engineering.

For future work, we need to check the generality of the STAR algorithm. COCOMO, COQUALMO, and THREAT
are simple models and a more general STAR framework might require more intricate
forward selection methods or more some alternative to simulated annealing.
For example,
Kakas has explored linear optimization as a symbol-level engine for abduction. Another candidate 
method might be the cross-entropy method~\cite{rubinstein04}.

\bibliographystyle{abbrv}

{\small
\bibliography{refs}}  % sigproc.bib is the name of the Bibliography in this case
\end{document}
\appendix
\section{Obtaining and Using STAR1}
   These instructions should support a LINUX and CYGWIN install of STAR1.
In the event of technical difficulties, please contact the first two
authors (Menzies or Elrawas).

{\scriptsize
\begin{verbatim}
bash -i
[ ! -d "$HOME/bin" ] && mkdir $HOME/bin
export PATH="$PATH:$HOME/bin"
wget http://unbox.org/wisp/tags/STAR/1.0/STAR_1.0.zip
unzip STAR_1.0.zip
make  # requires gcc
cd ~/STAR
cd eg
./1  | tee osp2.out | less
./2  | tee osp.out  | less
\end{verbatim}
}

To run STAR1  on projects other than OSP or OSP2:
\bi
\item Copy and edit
one of the projects files
in\newline \verb+~/STAR/STAR_projects+. 
\item
Note that you will have to
edit {\em both} a x.ranges and x.values file.
\item
Then copy and edit (e.g.) \verb+~/STAR/eg/1+ to point to
your edited project details.
\ei

\end{document}


