\documentclass[twocolumn]{article}
\usepackage{graphicx,lineno,cite,lastpage,url,
            alltt,fancyheadings}

%\renewcommand{\baselinestretch}{1.67}

%\newenvironment{tip}{\medskip\par\noindent
%  \begin{equation}
%   \begin{minipage}{.9\textwidth}}{%
%  \marginpar{\spsfbox{check.eps}}}\end{minipage}\end{equation}}

\newenvironment{prol}{\medskip\par\noindent
  \begin{equation}\footnotesize\begin{minipage}{.9\textwidth}\begin{alltt}}{%
  \end{alltt}\end{minipage}\normalsize\end{equation}}

\newenvironment{prolog}{\medskip\par\noindent
          \footnotesize\begin{alltt}}{%
        \end{alltt}\normalsize}


%\documentclass[emtex]{article}
%\documentclass[a4paper,emtex]{article}
%\usepackage{epsfig,cite,varioref,makeidx,boxedmin,
%            alltt,array,fancyheadings,lastpage,epsf,epic,ecltree}

%\renewcommand{\baselinestretch}{1.67}

%\columnsep 0.35in

% \columnsep 0.25in
% \topmargin -1.1in
%\textwidth 15.95cm

%%%%%% begin standard timm latex macros

\newcommand{\home} {
Deptartment of Artificial Intelligence, \\
School of Computer Science and Engineering,\\
University of New South Wales, PO Box 1,\\ 
Kensington, Sydney, Australia, 2033\\
\small
{\tt
timm@cse.unsw.edu.au}\\
\small
{\tt  http://www.cse.unsw.edu.au/$\sim$timm}
\normalsize}

\newenvironment{tip}{\medskip\par\noindent
  \begin{equation}
        %\epsfbox{rhand.eps}
	\begin{boxedminipage}{.9\textwidth}}{%
        \end{boxedminipage}
  \end{equation}}


%\newenvironment{tip}{\medskip\par\noindent
%  \begin{equation}
%   \begin{minipage}{.9\textwidth}}{%
%  \marginpar{\spsfbox{check.eps}}}\end{minipage}\end{equation}}


%\newcommand{\changequote}[1]{\let\origchn\chaptername
%\renewcommand{\chaptername}{\strut
%\rlap{\hbox to \linewidth{\hfill\vtop to 0pt{\hbox{#1}\vss}}}\origchn}}


%\newcommand{\marginlabel}[1]
%	{\mbox{}\marginpar{\raggedleft\hspace{0pt}#1}}



%\newcommand{\max}{{\em max}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}

\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bi}{\begin{itemize}}

\newcommand{\ei}{\end{itemize}}
\newcommand{\kl}{\my{KL}}
\newcommand{\src}[1]{Listing \ref{#1}}
\newcommand{\fig}[1]{Figure~\ref{#1}}
\newcommand{\around}[1]{\<\<Insert \fig{#1} around here\>\>}
\newcommand{\ilabel}[1]{\index{#1}\label{#1}}
\newcommand{\code}[1]{{\small\sf{\sc{#1}}}}
\newcommand{\htfour}{\code{HT4}}

\newcommand{\etal}{\mbox{{\em~et.~al.}}}
\newcommand{\tion}[1]{\S\ref{#1}}
\newcommand{\btion}[1]{(\S\ref{#1})}
\newcommand{\btip}{~\\\sl\marginpar{\Huge{$\dag$}}}
\newcommand{\etip}{~\\\rm}


\newcommand{\PROC}{{\underline {\sffamily procedure}}}
\newcommand{\DO}  {{\underline {\sffamily begin}}}
\newcommand{\FOR}{{\underline {\sffamily for}}}
\newcommand{\OD}{{\underline {\sffamily end}}}
\newcommand{\IF}{{\underline {\sffamily if}}}
\newcommand{\THEN}{{\underline {\sffamily then}}}
\newcommand{\TO}{{\underline {\sffamily to}}}
\newcommand{\IN}{$\in$}
\newcommand{\ZIP}{$\emptyset$}
\newcommand{\INTERSECTS}{$\cap$}

%\newsavebox{\fminibox}
%\newlength{\fminilength}
%\newenvironment{fminipage}[1][\linewidth]
% {\setlength{\fminilength}{#1}%
%\addtolength{\fminilength}{-2\fboxsep}%
%\addtolength{\fminilength}{-2\fboxrule}%
%\begin{lrbox}{\fminibox}\begin{minipage}{\fminilength}}
% {\end{minipage}\end{lrbox}\noindent\fbox{\usebox{\fminibox}}}

%%%%%% end standard timm latex macros

%%%%%% fancies

%\lhead[\fancyplain{}{\sl\rightmark}]{\fancyplain{}{\sl\leftmark}}
\lhead[\fancyplain{}{\sl\rightmark}]{\fancyplain{}{~}}
\rhead[\fancyplain{}{\sl \leftmark}]{\fancyplain{}{\sl \rightmark}}
\rhead[\fancyplain{}{\sl \leftmark}]{\fancyplain{}{~}}
\cfoot{}
\chead{}
\lhead{}
\rhead{}
\rhead[]{\sl page~\thepage~of~\pageref{LastPage}}
\lhead[{\sl page~\thepage~of~\pageref{LastPage}}]{}
\footrulewidth 0pt
\headrulewidth 0.4pt

%%%%%% fancies
\newcommand{\avin}{{$\overline{|\my{IN}}|$}}
\newcommand{\avout}{{$\overline{|\my{OUT}}|$}}
\newcommand{\raone}{{\sc RA-1}}
\newcommand{\ratwo}{{\sc RA-2}}
\newcommand{\HT}{{\program HT4}}
\newcommand{\class}[1]{\sffamily {\small #1}}
\newcommand{\cc}[1]{\class{#1}}
\newcommand{\program}[1]{{\bf {\sc #1}}}
\newcommand{\p}[1]{{\program #1}}
\newcommand{\tool}{{\program TICK}}
\newcommand{\kup}[2]{${\tt #1}_{{\tt #2}{\tt up}}$}
\newcommand{\kdown}[2]{${\tt #1}_{{\tt #2}{\tt down}}$}

\newcommand{\lang}{{\tool}-L}
\newcommand{\expert}{{\tool}-E}


\newcommand{\my}[1]{{\tt #1}}
\newcommand{\nth}[2]{{\tt #1[#2]}}
\newcommand{\mth}[3]{{\tt #1[#2,#3]}}

\newcommand{\myy}[2]{{\tt #1.#2}}
\newcommand{\myset}[1]{{\tt\{#1\}}}
\newcommand{\myyy}[3]{\tt #1.#2.#3} 
\newcommand{\goes}[2]{{${\tt #1}\rightarrow{\tt #2}$}}
 \newcommand{\direct}[2]{{\tt #1}\(\stackrel{++}{\rightarrow}\){\tt #2}}
\newcommand{\inverse}[2]{{\tt #1}\(\stackrel{--}{\rightarrow}\){\tt #2}}
\newcommand{\rarrow}{{$\rightarrow$}}

\newcommand{\best}{\my{BEST}}
\newcommand{\dogl}{\my{G}}
\newcommand{\fx}{\my{FX}}
\newcommand{\kla}{\my{KL-A}}
\newcommand{\klb}{\my{KL-B}}
\newcommand{\rdf}{\my{RDF}}
\newcommand{\rdra}{\my{RD-RA}}
\newcommand{\rdr}{\my{RDR}}


\title{Ripple-Down Rationality:
A Framework for Maintaining PSMs}
\author{Tim Menzies and Ashesh Mahidadia
\thanks{
Workshop on Problem-solving Methods for Knowledge-based Systems in
Connection with the Fifteenth International Joint Conference on
Artificial Intelligence (IJCAI-97) Nagoya, Japan, during August 23-25,
1997}\\
Artificial Intelligence Department, School of Computer Science \&
Engineering,\\
University of NSW, Sydney, Australia, 2052;\\
Email: \footnotesize
{\tt \{timm|ashesh\}@cse.unsw.edu.au};
\normalsize
URL:
\footnotesize
{\tt http://www.cse.unsw.edu.au/$\sim$\{timm|ashesh\}}
\normalsize
}

\date{\today}
\begin{document}

\maketitle 

\thispagestyle{empty} \pagestyle{fancy}

%\linenumbers
%\modulolinenumbers

\begin{abstract}
Knowledge-level (\kl) modeling can be characterised as {\em theory
subset extraction} where the extracted subset is consistent and
relevant to some problem.  Theory subset extraction is a synonym for
Newell's principle of rationality, Clancey's model construction
operators, and Breuker's components of expert solutions.  In an
abductive framework, a PSM is the extraction controller and is
represented by a suite of \best\ inference assessment operators. Each
\best\ operator is a single-classification expert system which {\tt
accept}s or {\tt cull}s a possible inference.  PSMs
can therefore be maintained by ripple-down-rules,
a technique for maintaining  single-classification expert
systems.  
\end{abstract}

\section{Introduction}

Newell's knowledge-level (\kl) approach modeled
intelligence~\cite{newell82} as a search for appropriate {\em
operators} that convert some {\em current state} to a {\em goal
state}. Domain-specific knowledge are used to select the operators
according to {\em the principle of rationality}; i.e. an intelligent
agent will select an operator which its knowledge tells it will lead
the achievement of some of its goals.

We can characterise expert systems maintenance as the controlled
revision of the state space and the rationality operators.  The state
space is modeled as a directed graph of literals.
Inference is controlled by an abductive~\btion{sec:abd} inference
engine which select portions of the graph which are relevant to a
problem.  Within the abductive inference engine are sets of
domain-specific \best\ assessment operators which implement the
principle of rationality; i.e. they select the preferred inference(s)
from the set of available inferences.  In an abductive knowledge-level
framework, problems solving methods (PSMs) are sets of \best\
operators~\btion{sec:abkl}. Such abductive PSMs 
operationalise Clancey's system model construction operators
which build a situation-specific model and Breuker's 
components of solutions~\btion{sec:others}.
On a continuum 
between standard PSMs and systems like \code{SOAR}, this
abductive PSM approach is closer to \code{SOAR} than (e.g.)
KADS~\btion{sec:klaklb}.

The key observation which sparked this paper as follows. Each such
\best\ operator is a single classification expert system which
classifies proposed inferences as {\tt cull} or {\tt
accept}. Ripple-down-rules (\rdr) are a technique that 
works well for maintaining single classification expert
systems~\btion{sec:scrdr}.
While they are poor at representing
KADS-style PSMs~\btion{sec:probsrdr}, they
could be used in an abductive framework to maintain the \best\
operators~\btion{sec:rdra}.
That is, we could maintain abductive PSMs
with \rdr.
Two premises of this approach is that
the knowledge base includes
inference preference criteria~\btion{sec:eg}
and that 
we have some mechanism for maintaining the functions
used
in the \best\ operators (e.g. using ripple-down-functions or \rdf,
\tion{sec:rdf}). 
We call this combination of abduction and ripples for \kl\ modeling
{\em ripple-down-rationality} or {\rdra}.
{\tt RD-RA}
has several advantages over
current PSM technology including maintenance,
the ability to compare different expert
system frameworks, and support for conflict resolution in requirements
modeling~\btion{sec:discuss}.

\section{Abduction}

This section gives our standard short overview on
abduction~\btion{sec:abd};
discusses its application to  knowledge level
modeling~\btion{sec:abkl};
contrasts abductive \kl\ with standard \kl\
approaches~\btion{sec:klaklb};
and
comments on the computational complexity of abduction~\btion{sec:complex}.
This section summarises material from other papers~\cite{me96a,me96b}.

\subsection{An Overview of Abduction}\label{sec:abd}

Elsewhere~\cite{me96a}, we have given a detailed overview of abductive
research.  Here,
we offer an approximate characterisation of abduction as the search
for consistent subsets of some background theory that are relevant for
achieving some goal. If multiple such subsets can be generated, then a
\best\ assessment operator selects the preferred subset(s) (or
{\em worlds}, \my{W}).
For
example, consider our graph-theoretic \code{HT4} abductive inference
engine~\cite{me96a,me96b,me97a}.  \code{HT4} determines what
\my{OUT}put goals can be reached from using the \my{IN}puts shown in a
knowledge base like \fig{fig:kb}.  In that Figure, \direct{x}{y}
denotes that {\tt y} being {\tt up} or {\tt down} can be explained by
{\tt x} being {\tt up} or {\tt down} respectively and \inverse{x}{y}
denotes that {\tt y} being {\tt up} or {\tt down} could be explained
by {\tt x} being {\tt down} or {\tt up} respectively.
Observe the apparent
conflict in the middle of \fig{fig:kb} on the left-hand-side:  author
1 believes {\tt a}~\(\stackrel{--}{\rightarrow}\)~{\tt c} while author
2 believes {\tt a}~\(\stackrel{++}{\rightarrow}\)~{\tt c}. We will
return
to this apparent conflict later~\btion{sec:discuss}.

\begin{figure}[b]
\begin{center}
\includegraphics[width=2.5in]{model.png}
%{\hfill\epsfbox{model.eps}\hfill}~\\
\my{IN}~=\myset{aUp, bUp}\\
\my{OUT}=\myset{dUp, eUp, fDown}
\end{center}
\caption{A knowledge base. Edges are labeled with the author
of that edge; e.g. author 1 and 2.}\label{fig:kb}
\end{figure}

\begin{figure}[t]
\begin{center}
\includegraphics[width=3in]{worlds.png}
%{\hfill\epsfbox{worlds.eps}\hfill}~\\
\end{center}
\caption{Two generated worlds from \fig{fig:kb}.
Edges are labeled with the author
of that edge; e.g. author 1 and 2.}\label{fig:worlds}
\end{figure} 

\code{HT4} can find the following proofs \my{P}
connecting \my{OUT}s to
\my{IN}s: \\
\nth{P}{1} = {\tt aUp \rarrow\ xUp   \rarrow\ yUp   \rarrow\ dUp};\\
\nth{P}{2} = {\tt aUp \rarrow\ cUp   \rarrow\ gUp   \rarrow\ dUp};\\
\nth{P}{3} = {\tt aUp \rarrow\ cUp   \rarrow\ gUp   \rarrow\ eUp};\\
\nth{P}{4} = {\tt bUp \rarrow\ cDown \rarrow\ gDown \rarrow\ fDown};\\
\nth{P}{5} = {\tt bUp \rarrow\ fDown}.\\
These proofs may contain assumptions, i.e. literals  that
are not known \my{FACTS}.  Continuing the example of
\fig{fig:kb}, if \my{FACTS} is the union of \my{IN} and \my{OUT}, then
\myset{xUp,yUp,cUp, cDown, gUp, gDown} are assumptions.  If we can't
believe that a variable can go {\tt up} and {\tt down} simultaneously,
then we can declare \myset{cUp, cDown, gUp, gDown}
to be conflicting
(denoted \myy{A}{c}). 
\fig{fig:kb} shows us that
{\tt g} is fully dependent
on {\tt c}. Hence
the key conflicting assumptions are \myset{cUp,
cDown} (denoted {\em base controversial assumptions} or \myy{A}{b}).
We can used \myy{A}{b} to find consistent belief sets called worlds
\my{W}.  A proof \nth{P}{i} is in \nth{W}{j} if that proof does not
conflict with the environment \nth{ENV}{j} (an environment is a
maximal consistent subset of \myy{A}{b}).  In our example,
\nth{ENV}{1}=\myset{cUp} and \nth{ENV}{2}=\myset{cDown}\footnote{The connection of \code{HT4} to
DeKleer's ATMS system~\cite{deKleer86} is
explored elsewhere~\cite{me96a}}.  
Hence,
\nth{W}{1}=\{\nth{P}{1}, \nth{P}{2}, \nth{P}{3}, \nth{P}{5}\} and
\nth{W}{2}=\{\nth{P}{1} \nth{P}{4} \nth{P}{5}\} (see
\fig{fig:worlds}). Note that while inconsistencies
may be detectable within the knowledge base, each world is guaranteed
to be consistent.

\subsection{Abduction and the Knowledge Level}\label{sec:abkl}

Abduction generates worlds. Which is the \best\ world?
We have argued previously~\cite{me96a} that:
\be
\item
The  answer is problem-specific.
\item
\kl\ modeling is a synonym for the careful selection of the
\best\ assessment operators.
\ee

To demonstrate these two points, consider an agent watching the
traversal of a search space represented as a directed
graph connecting
literals.
What information does our agent need to 
to decide if a possible inference is \best?
We define five levels of \best:

Level 1 {\em vertex-level \best}: If our agent can only ``see'' one edge ahead of the current search,
then they could make a {\em vertex-level}
\best\ decision. For example, if we are implementing a
\code{MYCIN}-style certainty factor kludge~\cite{buch84},
then our agent could decide to avoid all edges with a certainty factor of
less than 0.2. That is, those edges are {\tt cull}ed  since they are
not \best.

Level 2 {\em proof-level \best}:
If our agent can ``see'' what the {\em vertex-level} agent
can see {\em and} can query the
current proof tree up to the current edge, then it could make a {\em
proof-level} choice. Our proof-level agent could {\tt cull} an edge 
in the following three cases:
\be
\item
The new edge means that the
proof would contain ``too many assumptions'' (defined according to
some domain-specific criteria). 
\item
The edge contains a literal that
is incompatible with literals currently on the proof.
\item
The edge would introduce a loop in the current proof.
\ee

Level 3 {\em proofs-level \best}:
If our agent can ``see'' what the {\em proof-level} agent can see {\em
and} can query all the other proofs generated up until now, then it
could make a {\em proofs-level} choice. For example, classic AI search
algorithms such as best-first and beam-first search\footnote{In
best-first, the cost of traversal to this point is added to a
heuristic guess on what it would cost to use each possible edge to
continue on to some goal.  The edges are then sorted by increasing
combined cost.  The search then proceeds in that order. In beam-first,
after the sort, only the top {\em N} items are explored where {\em N}
is
the ``width'' of the beam search~\cite{norvig92}.}  are proofs-level
\best\ operators.

Level 4 {\em world-level \best}:
Suppose our agent ``sees'' that a generated
world explains all of the \my{OUT} set. It could declare this world 
to be \best\ and halt the generation of any other worlds.

Level 5 {\em worlds-level \best}: When our agent can ``see'' multiple worlds,
it could make a comparative evaluation of the different worlds.

A variety of knowledge-level tasks 
can be implemented via
an appropriate selection of 
\best\ assessment operators~\cite{me96a} and careful construction
of the \my{IN}put and \my{OUT}put sets:
prediction~\btion{sec:predict},
diagnosis and probing~\btion{sec:dia}, 
classification~\btion{sec:class},
explanation and tutoring~\btion{sec:expl}, 
qualitative reasoning~\btion{sec:qr}, 
planning and monitoring~\btion{sec:plan},
validation~\btion{sec:valid},
amongst other~\btion{sec:others}.

\subsubsection{Prediction}\label{sec:predict}

{\em Prediction} is the process of seeing what
will follow from some events \my{IN}. Given  a theory represented
as a directed graph with vertices \my{V},
then we can find all the non-input
vertices reachable from \my{IN} by making
$\my{OUT}~\subseteq~\my{V}~-~\my{IN}$ (note that \my{IN} and \my{OUT}
are just subsets of \my{V}).   
A efficient case for prediction is when \my{IN} is
smaller than all the roots of the graph and some {\em interesting
subset} of the vertices have been identified as possible reportable
outputs (i.e. $\my{OUT}~\subset~\my{V}~-~\my{IN}$).

\subsubsection{Diagnosis and Probing}\label{sec:dia}

It is well-known that diagnosis is an abductive
process~\cite{pople73,
console91,reggia85}.
Parsimonious {\em set-covering diagnosis}~\cite{reggia83} 
uses a \my{BEST} that favors worlds that explain the most things, with
the smallest number of diseases (i.e. maximise $\nth{W}{x}~\cap~\my{OUT}$
and minimise $\nth{W}{x}~\cap~\my{IN}$). 

The opposite of set-covering diagnosis is {\em consistency-based
diagnosis}~\cite{reiter87,console91} where
all worlds consistent with the current observations are
generated.
Computationally, this is equivalent to {\em prediction}~\btion{sec:predict},
with 
$\my{OUT}~=~\my{V}~-~\my{IN}$.  

In Reiter's variant
on consistency-based diagnosis~\cite{reiter87}, all predicates
relating to the behaviour of a theory component \nth{V}{x} assume a
test that \nth{V}{x} in not acting {\tt  AB}normally; i.e.
$\neg{\tt AB}(\nth{V}{x})$. \myy{BEST}{REITER} is to favour the worlds
that contain the least number of {\tt AB} assumptions.

A related task to diagnosis is {\em probing}. When exploring different
diagnosis, an intelligent selection of tests (probes) can maximise the
information gain while reducing the testing cost~\cite{dekleer87}. In
this abductive framework, 
we would know to favor probes of \myy{A}{b} over probes of
\myy{A}{c} over probes of non-controversial assumptions.

\subsubsection{Classification}\label{sec:class}

{\em Classification} is just a special case of prediction with the
{\em interesting subset} set to the vertices representing the possible
classifications.  The and-or graph of a classification theory
would include edges (i) from class attributes to the proposition that
some class is true; and (ii) from sub-classes to super-classes
(e.g. if {\tt emu}
then {\tt bird}).  \myy{BEST}{CLASSIFICATION} could favors the worlds
that include the most-specific classes~\cite{poole85} (e.g. {\tt emu}
is better than {\tt bird}).

\subsubsection{Explanation and Tutoring}\label{sec:expl}

If we have a profile of our users comprising
vertices
familiar to the user and the edges representing processes that the
user is aware of, then we can build an {\em explanation} and 
{\em tutoring
system}.
\myy{BEST}{EXPLANATION} could favors the worlds
with the largest intersection to this user profile.  That is, we
return the
world(s) that the user is most likely to understand.
We base this explanation proposal on analogous
work by Paris~\cite{paris89}. 

Further, suppose we can assess that the \my{BEST} explainable
world was somehow sub-optimum.
We could then make a
entry is some log of teaching goals that we need to educate our user
about the edges which are not in their \my{BEST} 
explainable world but are in other, more optimum, worlds.

\subsubsection{Qualitative Reasoning}\label{sec:qr}

The above abductive inference engine
was developed from a {\em qualitative reasoning}
algorithm for neuroendocrinology~\cite{fecosm89b}.
A fundamental property of such systems
is their indeterminacy which generate alternative values for
variables.
These
alternatives and their consequences must be considered separately.
Abduction can maintain these alternatives in separate worlds.

\subsubsection{Planning and Monitoring}\label{sec:plan}

{\em Planning} is the search for a set of actions
that convert some
current state into a goal state. 
Given a set of actions, we could partially
evaluate them into the dependency graph they propose between
literals. \myy{BEST}{PLANNING} could favor the world(s) with the
least cost (the cost of a world is the maximum cost of the proofs in
that world).
If we augment each edge with the identifier of the
action(s) that generated it, then we could report the 
\my{BEST} worlds as the union of the actions that generated the \my{BEST}
worlds.  

Once generated, the \my{BEST} planning worlds could be passed
to a {\em monitoring} system. As new information comes to light, some of
these assumptions made by our planner
will prove to be invalid. Hence, some of our worlds (a.k.a. plans) 
will also be
invalid.
The remaining plans represent the space of
possible ways to achieve the desired goals in the current situation. 

\subsubsection{Validation}\label{sec:valid}

{\em Validation}: For
example, let the {\em cover} of a world be its overlap with the
\my{OUT} set.  The cover of \nth{W}{1} and \my{OUT} in
\fig{fig:worlds} is \myset{dUp,eUp,fDown} and the cover \nth{W}{2} and
\my{OUT} is \myset{dUp,fDown}; i.e. \myy{\nth{W}{1}}{cover}=3=100\% and
\myy{\nth{W}{2}}{cover}=2=67\%.  The maximum cover is 100\%;
i.e. their exist a set of assumptions (\myset{cUp}) which let us
explain all of \my{OUT}.  A worlds-level \best\ operator that returns
the world with maximum cover is a validation procedure which answers
the following question: ``how much of the known behaviour of X can be
reproduced by out model of X?''.  This abductive validation procedure
has faulted theories published in the
international peer-reviewed literature. Interesting, we have found
these faults using the data published to support those 
theories~\cite{me97a}.
We have argued elsewhere~\cite{me96a,me96b} that this is the
non-naive implementation of KBS validation since it handles three certain
interesting cases:
\be
\item
If not all variables in the theory are measured,
then this
procedure can still validate the theory. 
The procedure will take the
necessary assumptions to prove some member of \my{OUT}
and mutually exclusive assumptions are managed in separate worlds.
\item
If a theory is globally inconsistent, but contains
local portions that are consistent and useful for explaining some
behaviour, we can find those portions.  
\item
In the situation where no
current theory explains all known behaviour, competing theories can be
assessed by the extent to which they cover known behaviour. Theory
{\em X} is definitely better than theory {\em Y} if theory {\em X}
explains far more behaviour than theory {\em Y}.
\ee

\subsubsection{Others}\label{sec:others}

We believe that abduction provides a comprehensive picture of
declarative knowledge-based systems (KBS) inference.  Apart from the
problem solving methods discussed here, we also believe that abduction
is a useful framework for intelligent decision support
systems~\cite{me95g}, diagrammatic reasoning~\cite{me94}, single-user
knowledge acquisition, and multiple-expert knowledge
acquisition~\cite{me95}.  Further, abduction could model certain
interesting features of human cognition~\cite{me95a}.  Others argue
elsewhere that abduction is also a framework for natural-language
processing~\cite{ng90},  visual pattern
recognition~\cite{poole90a}, analogical reasoning~\cite{falk90},
financial reasoning~\cite{hamscher90}, machine
learning~\cite{hirata94} and case-based reasoning~\cite{leake93}.

We have argued~\cite{me96a} that abduction is such a general procedure
since it operationalises the {\em theory subset extraction} process
that Breuker~\cite{breuker94} and Clancey~\cite{clancey85,clancey92}
argue is at the core of expert systems.  Clancey offers a two-layered
extraction process (qualitative model to situation-specific model)
while Breuker offers a four-layered view of the components of
solutions in an expert system (generic domain model to case model to
conclusion to argument structure).  Our approach is more general than
Clancey's since it makes explicit certain assumptions which are only
tacit in Clancey's approach. For example, Clancey assumes that the
best world uses the fewest number of \my{IN}s~\cite[p331]{clancey85}.
We have shown above that this is not universally true.  As to
Breuker's proposal, his components of solutions sounds to us like
three recursive calls to a single inference procedure.  In his view,
all expert system tasks use an {\em argument structure} which is
extracted from a {\em conclusion} which is in turn extracted from a
{\em case model} which is in turn extracted from a {\em generic domain
model}. Note that, in all cases, each sub-component is generated by
extracting a relevant subset of some background theory to generate a
new theory (i.e. abduction).

\subsection{\kla\ and \klb}\label{sec:klaklb}

This section discusses two variants on the \kl\ approach: \kla\
(e.g. \code{SOAR}) and \klb\ (e.g. KADS).

Newell's own exploration of the \kl\ lead to a general rule-based
language called \code{SOAR}~\cite{rosen93} which was the basis for the
problem-space computational model (PSCM) \cite{yost89}. Programming
\code{SOAR} using the PSCM involves the consideration of multiple,
nested problem spaces.  Whenever a ``don't know what to do'' state is
reached, a new problem space is forked to solve that problem. Newell
concluded that the PSCM was the bridge between \code{SOAR} and true
\kl\ modeling~\cite{newell91, newell93}.

We distinguish between PSCM (which we term \kla) and \klb, a
\kl-modeling variant which groups together a set of authors who argue
for basically the same technique; e.g. Clancey's model construction
operators~\cite{clancey92}, Steels' components of
expertise~\cite{steels90}, Chandrasekaran's task analysis, SPARK/
BURN/ FIREFIGHTER~\cite{marques92} and KADS~\cite{weil92}\footnote{See
the {\em Related Work} section of~\cite{weil92} for a discussion of
the differences in these techniques}. The fundamental premise of \klb\
is that a knowledge base should be divided into domain-specific facts
and domain-independent problem solving methods.  Such problem-solving
strategies are implicit in \kla.  The observation that a PSCM system
is performing (e.g.) classification is a user-interpretation of a
single inference procedure (operator selection over a problem space
traversal)~\cite{yost89}.

Like all single-world logic devices, \code{SOAR} {\tt cull}s possibilities
at the local-choice level.  By definition, local-choice systems cannot
delay their decisions on options till later in the computation when
more information is available.  For example, experiments with adding
abductive inference to \code{SOAR} relied on an interface to an
external abductive theorem prover. In Steier's \code{CYPRESS-SOAR/
RAINBOW} system, \code{SOAR} production rules modeled control
decisions, while the \code{RAINBOW} abductive inference engine
generated possible designs~\cite{steier93}.  In our approach, a \kl\
agent has the facility to delay choice decisions till the path, paths,
world, or worlds-level. Our multiple worlds device can explicitly
represent all the options. Hence, a \kl\ agent is free to reflect more
fully over the choices.

Our abductive PSM approach is clearer nearer to \kla\ than \klb.  Like
\code{SOAR}, our framework uses a single inference procedure
(abduction).  The connection of our approach to \klb\ in general and
KADS in particular is explored elsewhere~\cite{me96a,me97g}. In
summary, KADS offers a variety of designs for a range of inference
devices (e.g.~\cite{benj95}) for expert systems. 
We prefer the use of a single inference device (abduction). 
Our research goal is
(i)~the description of the minimal architecture necessary to \kl\
abduction; and (ii)~a maintenance framework for that minimal
architecture.


\subsection{A Note on Complexity}\label{sec:complex}

One drawback with abduction is that it is slow.
Selman \& Levesque show that even when only one abductive
explanation is required and the theory is restricted to be acyclic,
then abduction is NP-hard~\cite{sellev90}.  Bylander {\em et. al.}
make a similar pessimistic conclusion~\cite{by91}.  Computationally
tractable abductive inference algorithms (e.g.~\cite{by91,eshghi93})
typically make restrictive assumptions about the nature of the theory
or the available data. Such techniques are not applicable to arbitrary
theories. Therefore, it is reasonable to question the practicality of
abduction for medium to large theories. 

While the complexity of \my{BEST} is operator specific, we can make
some general statements about the computational cost of \my{BEST}.  At
a procedural level, assessment operators at level \my{i} can be used
to restrict the search space for operators at level \my{i+1}.  {\em
Vertex} or {\em proof-level} assessment reduce the complexity of the
search space traversal (since not all paths are explored).  {\em
Worlds-level} assessment is a search through the entire space that
could be relevant to a certain task.  Hence, for fast runtimes, do not
use worlds-level assessment.  However, for some tasks (e.g. the
validation task~\tion{sec:valid}) worlds-level assessment is
unavoidable.  Elsewhere we have shown that level 5 (worlds-level)
abduction is practical for the sizes of knowledge bases we see in
contemporary practice~\cite{me96b}.  Hence, we are confident that an
abductive system that uses
some lower level assessment operators
will operate in acceptable runtimes.

\section{Ripple-Down-Rules}

We argued above~\btion{sec:abkl} 
that a variety of knowledge level
tasks can be expressed a single abductive inference
procedure, plus some customisable \best\ inference assessment
operators.
We will argue below~\btion{sec:rdra}
that we can maintain PSMs by maintaining the suite of
\best\ operators. That
section will use a technique called ripple-down-rules (or \rdr).
This section describes \rdr. We focus only on single classification
\rdr\ since that is all that is
required for {\rdra}. Multiple classification
\rdr\ is discussed elsewhere~\cite{kang95}.

\subsection{An Overview of Single Classification \rdr}\label{sec:scrdr}

Standard software engineering and knowledge engineering typically
assumes that prior to building a system, an extensive analysis stage
develops a design for the system.  Compton reports experiments with a
completely reversed approach.  In \rdr, there is no analysis
period.  KA in an \rdr\ system consists only of fixing faulty
rules using an {\em unless} patch attached at the end of a rule
condition.  Patches are themselves rules which can be recursively
patched. Experts can never re-organise the tree; they can only
continue to patch their patches. If a new case motivates a new
patch, that this case is stored with the new patch. 
Such cases are called {\em cornerstone cases}.
Compton argues
that these (\rdr) trees model the context of knowledge
acquisition. When a case is processed by an \rdr\ tree, its context is
the set of cases in the patches exercised by the new case.  When
looking for new patches, experts can only choose from the {\em
difference} of the attributes in the current case and the 
attribute value tests (called {\em features})
exercised down to the current faulty rule.

\begin{figure}
\begin{center}
\includegraphics[width=3in]{rdr.png}
%{\hfill\epsfbox{rdr.eps}\hfill}~\\
\end{center}
\caption{A \rdr\ knowledge base}\label{fig:rdr}
\end{figure}

For example, \fig{fig:rdr} shows the rule {\tt if a\&b then x1}
patched several times. At runtime, the final conclusion is the
conclusion of the last satisfied rule. At maintenance time, when
fixing deficient knowledge, an {\em unless} patch is added beneath the
incorrectly last-satisfied rule. Only the {\em logic delta} is added in
the new rule since the system cannot get to this rule without first
satisfying the logic from the root to this rule. So, in \fig{fig:rdr},
if {\tt x2} is the correct conclusion when {\tt a\&b\&c} is true, but
incorrect when {\tt c} is false, we add the logic delta {\tt c} to a
patch rule in the {\em unless} branch beneath {\tt rdr1}.

\begin{figure}
\footnotesize
\begin{center}
\begin{tabular}{|c|c|c|}\hline
{\bf \rdr\ rule} & {\bf If} & {\bf Then} \\\hline
1 & a \& b \& not c       & x1 \\\hline
2 & a \& b \& c           & x2 \\\hline
3 &  a \& b \& not c \& d & x3 \\\hline
\end{tabular}
\end{center}
\caption{The flattened rule set of  \fig{fig:rdr}.}\label{fig:flat}
\end{figure}

{\tt RDR} applies the maxim {\em si fractum non sit, noli id
reficere}\footnote{If it ain't broke, don't fix it.} and
``freezes'' knowledge that has proven satisfactory in the past.
Logic deltas
are only added
to new knowledge. This {\em frozen knowledge principle}
simplifies
maintenance. To see this, consider the {\em flattened rule set} we can
generate from \fig{fig:rdr} in \fig{fig:flat}. In the flattened rule
set, one rule is generated for each \rdr\ path. Most rule-based expert
systems would maintain their knowledge in flattened rule sets such as
\fig{fig:flat}.  In such a conventional rule-based expert system, a
patch can extend over many rules. Repeating our above example, the
patch on the {\tt x1} error requires an edit to one \rdr\
rule {\tt rdr1}
and the creation of another \rdr\ rule
{\tt rdr2}. Further, the new logic refers
to {\tt c} which is a new concept that must be propagated down to all
related rules (e.g. {\tt rdr3}). The more related rules, the more
edits.  As the knowledge base grows, so to does the number of related
rules and the number of rules that may require editing after a
change~\cite{gross93}.  By contrast, in \rdr, existing knowledge is
frozen and we only {\em extend} the knowledge base.


The BNF of an \rdr\ is shown in \fig{fig:bnfrdr}\footnote{In 
the BNF
variant used here, words starting in lower case represent
terminals. Terminals that are variables start with an underscore;
e.g.  \underline{{\tt if}} is a non-variable terminal while
 \underline{{\tt \_name}} is a variable
storing some string entered by the user.  Words starting with upper
case are nonterminals. Nonterminals are expanded with the form {\tt
NonTerm ::= Rhs}. A {\tt Rhs} can use the following symbols.  Square
brackets {\tt []} surround optional items; a vertical line ({\tt |})
separates alternatives; curly brackets {\tt \{\}} surround items that
can repeat many {\em zero} or more times; and curly brackets followed
by a plus {\tt \{\}+} surround items that can repeat {\em one} or more
times.}. 
{\tt After, unless} and {\tt else}
links are optional.
Only patched \rdr rules will get {\tt else} and 
{\tt unless} links. If an {\tt RDRnode} points to another {\tt
RDRnode},
then we may optionally store a {\tt after} link as a back pointer
(for efficiency reasons). Note a {\tt Function} is
a pair of {\tt <Oracle, body>} where the {\tt body} is called
as a side effect of passing {\tt argument}s to a {\tt NamedOracle}. 
If the keyword {\tt cache} is included in the {\tt Function}
definition, then the results of calling the 
{\tt body} the first time is simply returned if ever it is called
again.


\begin{figure}
\begin{prolog}
RDR         ::= RDRnode | RDFnode
RDRnode     ::= rdr   _id
                [after RDR]
                if     Condition
                       then _conclusion
                       since Cornerstone
                       [unless RDR]
                [else  RDR]
Condition   ::= [not] Feature  \{and Condition\}+
               | [not] Feature  \{or Condition\}+
Feature     ::= Oracle says Comp than _value
Oracle      ::= NamedOracle(_argument \{,_argument\})
NamedOracle ::= _namedOracle
Function    ::= toCall  Oracle
                perform [cache] _body
Comp        ::= >=|>|<>|=|<|<=
Cornerstone ::= Feature \{and Feature\}
\end{prolog}
\caption{BNF for {\rdr}.
{\tt RDFnode}s are discussed later~\btion{sec:rdf}.}\label{fig:bnfrdr}
\end{figure}

{\tt RDR} trees are a very low-level representation. {\tt RDR}
rules cannot assert
facts that other \rdr\ rules can use. In no way can a \rdr\ tree be called a
model in a \kl\ sense.  Further, the \rdr\ formalism
makes no commitment to tree structures that are optimal. An \rdr\ tree
can contain repeat tests, redundant knowledge, and its sub-trees can
overlap each other semantically.  Despite these apparent drawbacks,
\rdr\ has produced large working expert systems in routine daily use.
In practice the \rdr\ trees are only twice as big as the optimum
tree~\cite{gaines92a} and runtimes have never been an issue.  It may
be somewhat misguided to attempt to optimise an \rdr\ tree to (e.g.)
remove the redundancies or separate the overlaps. The important
feature of an \rdr\ tree is that is it optimised for
maintenance. Alternative representations may run faster, but incurs
the penalty of more complicated maintenance.

In practice, \rdr\ appears to work very well, at least for single
classification problems.  For example, the PIERS system at
St. Vincent's Hospital, Sydney, models 20\% of human biochemistry
sufficiently well to make diagnoses that are 99\%
accurate~\cite{preston93}. \rdr\ has succeeded in domains where
previous attempts, based on much higher-level constructs, never made
it out of the prototype stage~\cite{patil81}. Further, while large
expert systems are notoriously hard to maintain~\cite{vandebrug86},
the no-model approach of \rdr\ has never encountered maintenance
problems. System development blends seamlessly with system maintenance
since the only activity that the \rdr\ interface permits is patching
faulty rules in the context of the last error. For a 2000-rule \rdr\
system, maintenance is very simple (a total of a few minutes each
day).  Compton argues that his process of ``patching in the context of
error'' is a more realistic KA approach than assuming that a human
analyst will behave in a perfectly rational way to create some initial
correct design~\cite{compton90}.

\subsection{Limits to \rdr}\label{sec:probsrdr}

This section argues that, in terms of {\rdra}, \rdr\ has two
significant limits: representing functions performing
the  feature extraction and representing
PSMs.

{\em Representing feature extractors}: An \rdr\ rule queries values
extracted from the functions performing
the feature extraction  which summarise the
environment.  For example, an \rdr\ rule might say {\tt if age=old
then\ldots} where {\tt age} is a {\tt Function}
 that assigns labels 
such as {\tt old} to
continuous values such as {\tt age}.  
The change control for these functions is not
controlled by logic patches in a \rdr\ tree; i.e. \rdr\ does not
address the issue of maintaining functions (though see Preston's work~\cite{preston92}
for an interesting approach to customising feature extraction functions). 

{\em Representing PSMs}: Before a \rdr\ tree executes, the feature
extractor
{\tt Function}s
find 
all the features in a case. The delta logic is constructed via
computing the difference between the case features and the features
found in the rules along the path to the faulty rule. Consequently,
\rdr\ is focused on the details of the specific case at hand.  PSMs
may not be expressible with respect to the specific problem at
hand. For example, consider an \rdr\ tree maintaining taxi driver
knowledge. Our student taxi driver may learn many tricks about
navigating from Sydney to Canberra through specific streets.  However,
in an \rdr\ framework, she may never learn the generalised PSM: ``open
the map, find your current location, find your destination, compute
the shortest distance path from here to there''. More generally,
to date, 
the {\tt Function}s called in {\rdr} {\tt Conditions}
do not access the meta-level
reasoning used in problem solving. 

These representational problems are a particular drawback for
{\rdra}. The abductive PSMs described in~\tion{sec:abkl} are not
defined with respect to the particulars of the problem at hand.
Rather, the \best\ operators are defined with respect to meta-level
reflection on the current status of the inference.  To resolve these
problems, we will need a library of feature extractor {\tt Function}s
 that can access
the internal data structures of the inference engine.  Further, we
will need to offer a maintenance strategy for those {\tt Function}s.  We return
to this point below when we discuss
ripple-down-function~\btion{sec:rdf}.

\section{An Architecture for Ripple-Down-Rationality}\label{sec:rdra}

This section \rdra, our marriage of  abduction to ripples
to \kl\ modeling.
After considering
an  extended example
of our framework~\btion{sec:eg}, we will see that we need some tool
for maintaining the rule conditions~\btion{sec:rdf}.

\subsection{{\tt RD-RA}: An Example}\label{sec:eg}

\begin{figure}
\begin{prolog}
sydneyDiseases contains 1,2.

1  : timm says
if      suburb='bondi' and 
        temperature > 40 and
        pain.location = 'tummy' and
        observed = 'sand rash on tummy'
then    conclusion = 'sand allergy secondary to
                      too much surfing'.

2 : ashesh says 
if      temperature > 40 and
        pain.location = 'tummy' and
        observed = 'sand rash on tummy'
then    conclusion = 'too much groveling'.
\end{prolog}
\caption{A knowledge base.}\label{fig:tarules}
\end{figure}

Suppose we are maintaining some {\tt
version} of a knowledge base \my{KB}
such as \fig{fig:tarules}. This knowledge base contains a
set of statements, each tagged with their {\tt author}.

\begin{prolog}
KB            ::= _version contains \{Statement\}+
Statement     ::= _id : _author says _contents
\end{prolog}


We make no commitment to the form of the {\tt contents}.
However, we do require that some {\tt compiler()} can convert that 
\my{KB} into a {\tt Theory}\footnote{i.e. {\tt Theory=compile(KB)}}
comprising:

\bi
\item
A directed graph connecting {\tt Feature}s.
\item
A library of known/desired behaviour (called the {\tt Goal}s);
\item
{\tt Prefer}ence criteria for deciding between different goals;
\ei

\begin{figure} 
\begin{prolog}
Theory        ::= _version contains Graph 
                  for \{Goal\}+ using PSM
PSM           ::= RDR
Goal          ::= input \{Vertex\}+ output \{Vertex\}+
Graph         ::= \{Vertex\}+ \{Edge\}
Edge          ::= from Vertex to Vertex
Vertex        ::= And | Or 
Or            ::= from Vertex Feature
And           ::= from Vertex \{and Vertex\} 
                  type AndType
AndType       ::= full | partial
\end{prolog}
\caption{BNF for \rdra}\label{fig:tkb}
\end{figure}

The BNF of a {\tt Theory} is shown in \fig{fig:tkb}.  
The PSM is modeled as an \rdr\ tree controlling the \best\ operators.
The \my{IN}put
and \my{OUT}put sets are generated from the {\tt Goal}s.  An {\tt Or
Vertex} can be traversed if any of its parents can be traversed. As we
cross an {\tt Or Vertex}, its {\tt Feature} test is applied which, in
turn, may executes a {\tt Function body} (recall
\fig{fig:bnfrdr}). That is, procedural side-effects can be coded into
{\tt Or Vertex} traversal.  An {\tt And Vertex} can only be traversed
if some its parents can all be traversed. There are two {\tt
AndTypes}. A {\tt full And} requires all its parents to be
traversable. A {\tt partial And} will try all its parents but only
strictly needs one parent to be traversable. 


\begin{figure}
\begin{center}
\includegraphics[width=3in]{ruleg.png}
%{\hfill\epsfbox{ruleg.eps}\hfill}~\\
\end{center}
\caption{A search 
space generated from~\fig{fig:tarules}.
Edges are labeled with their authors; e.g.
{\em t}={\tt timm} and {\em a}={\tt ashesh}.}\label{fig:ruleg}
\end{figure} 

The BNF of \fig{fig:tkb} is compatible with at least with two common
styles of expert systems: frames and rules.  Frame systems can be
implemented using {\tt Partial And}s connecting slots to frame
names. That is, if we can match slot contents, then we can reason back
to a frame.  Rules can be compiled into an {\tt and-or} graph
connecting rule left-hand-sides to rule right-had-sides.  For example,
the rules of \fig{fig:tarules} could be compiled into the graph of
\fig{fig:ruleg}.  Note that:
\bi
\item
If the rule
right-hand-sides are used in
other rules, then these connect to other rule left-hand-sides;
i.e. graphs like \fig{fig:tarules} would be deeper that just 1 edge.
\item
Observe the use of {\tt PartialAnd}s in \fig{fig:tarules}. 
If we have
only some of the evidence contributing to (e.g.) {\tt
tooMuchGroveling},
then with {\tt PartialAnd}s we can still explore this potential
conclusion. 
\ei

\begin{figure}
\begin{prolog}
prefer(Worlds,World,Proofs,Proof,Edge1,Edge2);

rdr  0 
if	true 
then	true;

rdr 11 after 0
if      previouslySeenEdges(World1,X1) and
        previouslySeenEdges(World2,X2) and
        bigger1(X1,X2)
then    cull(World2);

rdr 34 after 0
if      seenBefore(Edge1) and
        not seenBefore(Edge2)
then    cull(Edge2);

bigger1(Big, Small) :- Big > Small.
\end{prolog}
\caption{{\tt Prefer}ence criteria.}\label{fig:preferkb}
\end{figure}

\fig{fig:preferkb} shows some {\tt Prefer}ence criteria expressed in
\rdr\ format (recall \fig{fig:bnfrdr}).  The {\tt
Worlds,World,Proofs,Proof,Edge1,Edge2} variables are generated from
the {\tt Graph} search space and are passed in at runtime 
by
the
abductive inference engine when it has some choices to evaluate.
Suppose we were implementing an explanation
system~\btion{sec:expl}.  {\tt Rdr0} is the obligatory \rdr\ root
node where \rdr\ inference begins.  {\tt Rdr11} prefers worlds
containing edges which have appeared in previous explanations;
i.e. this system seeks to explain \my{OUT}puts using concepts the user
is already familiar with. Note that {\tt rdr11} is a worlds-level
{\best} and can be optimised using {\tt rdr34}, a vertex-level
\best~\btion{sec:complex}. {\tt Rdr34} performs a local cull of edges
which have never been seen before. 

\begin{figure}
\begin{prolog}
prefer(Worlds,World,Proofs,Proof,Edge1,Edge2);
...

rdr 67 after 34
if      timesSeen(Edge1,X1) and
        timesSeen(Edge2,X2) and
        bigger2(X1,X2)
then    cull(Edge1);

rdr 99 after 67
if      fromDoctor(Edge1) and
        fromMister(Edge2)
then    cull(Edge2).

bigger2(Big, Small) :- Big > 2*Small

% ashesh is slow at writing up his phd
mister(ashesh). 
% timm teases ashesh about this
doctor(timm).   
\end{prolog}
\caption{Refined {\tt Prefer}ence criteria.
\fig{fig:preferkb} is included into line 2 of this figure.}\label{fig:preferkb1}
\end{figure}

Suppose
our knowledge engineer enters \fig{fig:preferkb} and \fig{fig:tarules}
into the \rdra\ environment,
ran some cases, and found the conclusions
unacceptable. 
Patches were then made to the PSM to generate
\fig{fig:preferkb1}.  {\tt Rdr34} was been patched by another
vertex-level {\best} in {\tt rdr67}. In the case where we have seen
{\em both} {\tt Edge1} and {\tt Edge2}, but have seen {\tt Edge2}
twice as often as {\tt Edge1}, then we cull {\tt Edge1}. Lastly, in
{\tt rdr99}, it was decided that if a PhD graduate wrote {\tt Edge1},
then it must be true! Hence, in the case of all the conditions of
{\tt rule1} and {\tt rule2} being true in \fig{fig:tarules},
then we would conclude that surfing was the problem.

The example of \fig{fig:preferkb} illustrates some interesting points.
Firstly, the flattened rule set from \fig{fig:preferkb} and
\fig{fig:preferkb1} would contain conditions containing combinations
of \best\ operators at different levels (in the case above: worlds and
vertex-level). At the lowest-level of an abductive inference engine,
the above preference criteria must be executed at every inference
step.  Clearly, we need an optimiser lest our abductive inference
crawls to a halt. While clever optimisations are possible, we are
currently exploring the following simple optimisation strategy.  In
the case of flattened preference rules containing a mix of operators
at different levels, then the \best\
operator is assigned to the highest level.
 This optimisation strategy should  work well in the
special case where the operators are all at the same low-level.  In
our example above, we would have vertex-level {\best}s appearing in
separate flattened rules to the worlds-level {\best}s. The optimiser
would assign the vertex-level {\best}s to the local propagation level
of the abductive inference engine and the worlds-level {\best}s to the
subsequent worlds assessment.

Secondly, note the changing of the definition of {\tt bigger/2}.  {\tt
Rdr11} defines {\tt bigger} to be a straight numerical comparison
while {\tt rdr67} defines {\tt bigger} to be twice as big as the
``big'' defined in {\tt rdr11}.  Feature extractor {\tt Function}s like {\tt
bigger/2} (and indeed, {\tt previouslySeenEdges/2, seenBefore/2,
timesSeen/2, fromDoctor/1, fromMister/1}) need to be maintained. {\tt
RDR} has no mechanism for maintaining functions used in
conditions. Hence ripple-down-functions~\btion{sec:rdf}.

\subsection{Ripple-Down-Functions}\label{sec:rdf}


This section describes ripple-down-functions
({\rdf})~\cite{me92k}, an extension to
\rdr. {\tt RDF} enforces the disciplined
evolution of {\tt Function}s that perform
feature extractors. Using an \rdr tree the
scope of change of a {\tt Function}
is limited to the \rdr\ rules written {\em
after}
the revision of a construct at a particular time.
The definition of the {\tt Function}
in existing knowledge does not change.

If we adopt the \rdr\ frozen knowledge
principle~\btion{sec:scrdr} for condition {\tt Function}s,
then if follows that the definition of a function
should be split each time an {\tt Function}
refinement is
made. In terms of {\rdr}, we should add a {\tt FunctionFrame}
 stack
which stores
the order in which new \rdr\ rules were added to the \rdr\ tree.
Each entry is this list contains  a {\tt FunctionFrame} which stores
the definitions of {\tt Function}s. When an \rdr\
 rule needs a definition of a
procedure,
it finds its own reference in the function stack and searches back
towards {\tt frame0}.
At each {\tt FunctionFrame}, it checks 
for
a definition of the required procedure. If found, the search
stops and the found {\tt Function} is executed. 

We can optimise this representation. We need only add a new {\tt
FunctionFrame} when a {\tt Function}
 definition changes. Whenever a new \rdr\ rule is created, a
pointer could be added from this \rdr\ rule to the {\tt FunctionFrame}.  The
lookup of all the {\tt Function} definitions in the new \rdr\ rule could be done at
\rdr\ rule creation time thus avoiding having to do this lookup at runtime.

\begin{figure}
\begin{center}
\includegraphics{rdf.png}
%{\hfill\epsfbox{rdf.eps}\hfill}~\\
\end{center}
\caption{\rdf = \rdr\ plus a {\tt FunctionFrame} stack (top right).}\label{fig:rdf}
\end{figure} 
 
Continuing the \rdr\ example of \fig{fig:rdr}, suppose the {\tt Function} {\tt
b} is found to be faulty in the case of {\tt a\&b\&e}.  A new \rdr\
rule
{\tt rdr4} is added to our \rdr\ tree. The resultant tree (and the
pointers into the function stack) is shown in \fig{fig:rdf}.

\begin{figure}
\begin{prolog}
RDFnode       ::= RDRnode thatUses FunctionFrame
FunctionFrame ::= \{parent FunctionFrame\} \{Feature\}+
\end{prolog}
\caption{BNF for {\rdf}.}\label{fig:bnfrdf}
\end{figure}

In terms of BNF, \rdf\ is only a small extension to {\rdr}.
An {\tt RDFnode} is an {\tt RDRnode}, plus a pointer into a
{\tt FunctionFrame}.
Each {\tt FunctionFrame} stores a pointer to a parent 
{\tt FunctionFrame} (see \fig{fig:bnfrdf}). 
A {\tt FunctionFrame}
stores {\tt Oracle}s (recall \fig{fig:bnfrdr}).
Within a {\tt FunctionFrame}, no {\tt Oracle name}
is repeated.
However, {\tt Oracle name}s can repeat in different {\tt
FunctionFrames}.
For example, in \fig{fig:rdf}, {\tt b/0} was defined in
two {\tt FunctionFrame}s.

\section{Discussion}\label{sec:discuss}

Our approach has several advantages over conventional knowledge
engineering methodologies. Firstly, this framework is stronger on
maintenance than other approaches.  We have defined a maintenance
regime which integrates into our single abductive \kl\ device.
Maintaining a range of different inference devices (e.g. like those
used in KADS) is inherently more complicated.

Secondly, in our framework, we can perform comparative evaluations
of different approaches. Consider two interesting comparisons:
\bi
\item
{\rdra} vs {\rdr}: Our framework lets knowledge engineers work
at the level of specific data items 
or at a more general PSM level (contrast {\tt rdr99} in
\fig{fig:preferkb1} with {\tt rdr11} in \fig{fig:preferkb}).
When offered that choice, if knowledge engineers only ever work at the
specific example level (e.g. using {\best}s like {\tt rdr99}),
then that would make us suspect that {\rdr} is
more useful than {\rdra}.
\item
{\rdra} vs {\kla}:  Our framework lets knowledge engineers work
at the single-world level or the multiple world level (contrast {\tt
rdr11}
with {\tt rdr34} in \fig{fig:preferkb}). 
When offered that choice, if knowledge engineers only ever work at the
single-world level (e.g. using {\best}s like {\tt rdr34}), then 
that would make us suspect that {\kla} is
more useful than {\rdra}.
\ei

Thirdly, \rdra\ addresses
a known problem with {\rdr}. 
The \rdr\ representation is optimised for maintenance, not human reflection.
Consequently, they are hard to read.
Various techniques have been explored for reverse engineering a
browsable model from an \rdr\ tree. Lee extracts casual models from
{\rdr}s~\cite{lee96}; Richards extracts exception
graphs~\cite{richards97}; and Edwards explores reflection tools for
\rdr\ trees~\cite{edwards96}.
None of these approaches allow the knowledge engineer to initialise
the \rdr\ trees with existing knowledge. In our approach, knowledge
engineers can write text files like \fig{fig:tarules} and
\fig{fig:preferkb1} and then check them into the maintenance
environment.  Further, they can then check the knowledge out of the
maintenance environment in which case new text files in the format of
\fig{fig:tarules} and \fig{fig:preferkb1} are written.
That is, 
while standard \rdr\ is a replacement of existing
knowledge engineering approaches,
our approach can usefully 
augment existing knowledge engineering
approaches.

Fourthly, the abductive  approach 
described here
can be extended from maintenance to conflict resolution
in requirements analysis.  Requirements modelling (RM) researchers such
as Easterbrook~\cite{easter91b},\newline
Finkelstein\etal~\cite{fink94}, and Nuseibeh~\cite{nus97} argue that
we should routinely expect specifications to reflect different and
inconsistent viewpoints.  The software specification problem then
becomes one of managing these different viewpoints.  In current
methodologies, handling and resolving different viewpoints is a
time-consuming and costly process. If these different viewpoints are
poorly managed, the specifications have to be repeatedly reworked or
the runtime system has to be extensively modified.  

Our approach could
be used for conflict resolution.  Let us reconsider \fig{fig:kb} and
the author labeling on the edges of that graph.  Recall the apparent
conflict in the middle of \fig{fig:kb} on the left-hand-side: author
1 believes {\tt a}~\(\stackrel{--}{\rightarrow}\)~{\tt c} while author
2 believes {\tt a}~\(\stackrel{++}{\rightarrow}\)~{\tt c}.  In terms
of conflict resolution, the worlds in \fig{fig:worlds} tell us several
things. Firstly, author 1's edges can be found in two worlds;
i.e. with respect to the task \my{IN}= \myset{aUp, bUp} and \my{OUT}=
\myset{dUp, eUp, fDown}, a single author's opinions are inconsistent.
Secondly, both author 1 and author 2's edges exist in the same
consistent world (\nth{W}{1}); i.e.  the apparent conflict of authors
1 \& 2 did not matter for this task.  Thirdly, author 1 should review
their opinion that {\tt a}~\(\stackrel{--}{\rightarrow}\)~{\tt c}
since that proved to explain less of the required behaviour that
author 2's option that {\tt a}~\(\stackrel{++}{\rightarrow}\)~{\tt c}.

This abductive approach has technical advantages over other conflict
resolution approaches.
One striking feature of other systems that support
multiple-worlds
(e.g. Cake~\cite{rich92},Telos~\cite{plex93})
is their implementation complexity\footnote{
Rich \& Waters especially
comment on the complexity of their hetrogenous
architecture~\cite{rich92}.}
We have found that it
easier to build efficient implementations
~\cite{me96a, me96b}
using the above graph-theoretic approach than using
purely logical
approaches (e.g.~\cite{hun97}).
Easterbrook's {\program Synoptic} tool only permits comparisons of two
viewpoints~\cite[p113]{easter91b}.
Abduction can compare $N$ viewpoints.
Also,
Easterbrook~\cite{easter91b}  lets users enter their requirements into
an explicitly labeled
viewpoints which he assumes are internally consistent. We have no
need for this restrictive (and possibly overly-optimistic)
assumption.
Abduction
can handle inconsistencies within the opinions of a
single user. 

Further,
our multiple-worlds
reasoner  is not the JTMS-style~\cite{doyle79} approach used in
  other conflict recognition and management systems
  (e.g.~\cite{rich92}).  A JTMS searches for a single
  set of beliefs.  Hence, by definition, a JTMS can only represent a
  single viewpoint. Our approach is more like the
ATMS~\cite{deKleer86}
than a JTMS.
An ATMS maintains all consistent belief sets. We
  believe that an ATMS approach is better suited to RM conflict
  management since the different belief sets are available for
  reflection. 


\section{Conclusion}

We have characterised knowledge level modeling as an abductive
process and PSMs as suites of {\best} operators to operationalise
the principle of rationality. 
We have further characterised
PSM maintenance as the controlled evolution of the {\best} operators
via ripple-down-functions. That is:

\begin{center}
PSM maintenance = abduction + \rdr\ + {\rdf}.
\end{center}

This abductive approach to PSMs
is closer to the \kla\ view 
of knowledge level modeling than the \klb\ approach of (e.g.) KADS
and, apart from its maintenance advantages, permits
comparative
analysis of expert systems approaches and conflict resolution in
requirements modeling. 

\bibliographystyle{abbrv} 
\bibliography{refs} 

\end{document} 
