=Paper=
{{Paper
|id=Vol-18/paper-10
|storemode=property
|title=Describing Problem Solving Methods Using Anytime Performance Profiles
|pdfUrl=https://ceur-ws.org/Vol-18/10-tenteije.pdf
|volume=Vol-18
}}
==Describing Problem Solving Methods Using Anytime Performance Profiles==
https://ceur-ws.org/Vol-18/10-tenteije.pdf
Describing Problem Solving Methods
using Anytime Performance profiles
Annette ten Teije and Frank van Harmelen
Department of AI
Faculty of Science
Vrije Universiteit Amsterdam
annette,frankh @cs.vu.nl
our proposal to a number of realistic problem-
solving methods, namely hierarchical classifica-
Abstract tion (used in MDX), parametric design (methods
from XCON and VT), and consistency-based di-
Traditional selection criteria for Problem Solving
agnosis (the GDE-method).
Methods (PSMs) from libraries concentrate solely
on the functionality of these methods, and ignore
their computational performance. We propose the
1 Motivation
use of anytime performance profiles to describe One of the major themes in the literature on problem-
the computational behaviour of problem solving solving methods (PSMs) of the past half decade has been
methods, and to use these as additional selection the so-called applicability problem: how to decide which
criteria when selecting methods from a library. A PSMs are applicable to a given task. Solving this problem
performance profile describes how the quality of is essential for delivering some of the promises made about
the output of an algorithm gradually increases as PSM, in particular library construction and re-usability.
a function of the computation time. Such anytime Solving the applicability problem boils down to identifying
descriptions of problem solving methods are at- a set of properties of PSMs in such a way that these prop-
tractive because they allow a trade-off to be made erties can be used to select the appropriate methods from a
between available computation time and output- library.
quality. It turns out that many problem solving The literature contains many proposals on how to de-
methods found in the literature have a natural any- scribe properties of PSMs, and we will not try to give a
time behaviour, which has remained largely unex- systematic overview of them. Many of the proposals are
ploited until now. mentioned in [BPG96]. That paper synthesises all the dif-
In this paper we propose an axiomatic descrip- ferent proposals and defines three categories of applicabil-
tion of performance profiles. Furthermore, in ity conditions1: teleological conditions (= does the goal of
order to make our proposal feasible for library the PSM match with the current task at hand) epistemolog-
builders, we give guidelines on how to organise ical conditions2 (= knowledge requirements of the PSM)
such axiomatic descriptions. Finally, we apply and pragmatic conditions (= requirements on the interac-
Supported by the Netherlands Computer Science Research Founda- tion of the PSM with its environment).
All of the proposals on applicability conditions in the lit-
tion with financial support from the Netherlands Organisation for Scien-
tific Research (NWO), project: 612-32-006 erature regard a PSM as a functional I/O relation between
The copyright of this paper belongs to the papers authors. Permission to
domain knowledge and goal, and formulate the method se-
copy without fee all or part of this material is granted provided that the lection criteria in terms of this I/O relation: (a) does the
copies are not made or distributed for direct commercial advantage. goal of the PSM match the current task at hand, and (b)
Proceedings of the IJCAI-99 workshop on does the available domain knowledge match the knowl-
Ontologies and Problem-Solving Methods (KRR5) edge requirements of the PSM. Much of the more recent
Stockholm, Sweden, August 2, 1999 1 We prefer the term applicability conditions over the term assump-
(V.R. Benjamins, B. Chandrasekaran, A. Gomez-Perez, N. Guarino, M. tions, since the properties concern conditions that must be tested, and not
Uschold, eds.) assumptions which can be assumed.
2 later named ontological conditions in [FB98]
http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-18/
A. ten Teije, F. van Harmelen 10-1
work on characterising PSMs still focuses exclusively on the quality of the output of the algorithm varies as a func-
so-called “competence”3 of the PSM [WAS98]. This
the tion of the computation time. The quality measure of the
also holds for [FS98], which emphasises more than most output may be any characteristic of the result of an al-
the importance of computational behaviour besides only gorithm that we find significant. One anytime algorithm
the functional I/O relation. Even that paper does not give could have several performance profiles tracking different
a concrete proposal for how to describe the computational attributes of the results it returns. A performance profile
behaviour. The same holds for [FB98], which describes in is typically given in the form of a graph that plots output
some detail the effect that various conditions have on the quality against runtime.
computational behaviour of some diagnostic methods, but It is clear that anytime behaviour of PSMs is desirable.
this analysis is all done informally, with no proposal on Such PSMs are usable even when there is insufficient time
how to describe the computational behaviour of a method. to compute complete solutions. This is often the case given
This leaves an entire dimension of PSM applicability the intractable nature of typical tasks for PSMs. Also,
conditions uncovered in the literature: how should the per- such PSMs are applicable in real-time situations when the
formance of a PSM be described so that it can be used as an available computation time is often short and not known
applicability condition? There are good reasons why per- in advance. Thirdly, they offer the user the possibility to
formance description of PSM has been left as an open ques- trade solution-quality against computation time, making
tion in the Knowledge Engineering literature: as argued in the PSMs more widely applicable when selected from a li-
[FS98], the standard worst case complexity measures from brary.
computer science are not very helpful for PSMs, since a Perhaps surprisingly, anytime PSMs occur frequently.
significant part of PSMs are of a heuristic nature, and the Many PSMs in the literature turn out to have an anytime
worst case complexity describes only the case when the nature, even when they were not developed with this pur-
heuristics do not apply. One of the few attempts at describ- pose in mind. We have analysed the PSMs from a modern
ing average case complexity is [SB95], but this approach textbook on knowledge-based systems [Ste95], and have
requires detailed knowledge on the expected heuristic be- found that many of the methods discussed there have any-
haviour of all of the subtasks of a PSM, which does not time behaviour. This will be illustrated in section 5, where
seem very realistic in practice. we discuss examples which are all taken from this textbook,
Instead, in this paper we propose the use of so-called many of which are used in realistic KBS applications.
anytime performance profiles [DB88] to describe the com- The study of anytime algorithms is fairly recent, and
putational behaviour of PSMs (see section 2). Tradition- started with the introduction of the notions of anytime al-
ally, such performance profiles are given in the form of gorithm and performance profile by [DB88]. Subsequently,
graphs which are obtained empirically by executing the work has been done on combining and compiling anytime
PSM. We propose an axiomatic description of performance components from libraries using performance profiles (e.g.
profiles (section 4). Furthermore, in order to make our pro- [ZR96]). Also, work has been done by a variety of people
posal feasible for library builders, we give guidelines on on special purpose anytime algorithms for various applica-
how to organise such axiomatic descriptions (section 4): tion areas (e.g planning [BD89; DB88], diagnosis [Pos93],
our descriptions always consist of the same four elements, search ([Kor90]) and scheduling [BD94]).
each of which must be filled in by the library-builder when Boddy [Bod91] identifies a number of families of algo-
characterising method performance. Finally (section 5), we rithms which often have anytime algorithms: numerical ap-
apply our proposal to a number of realistic problem-solving proximation, heuristic search, probabilistic algorithms (eg
methods, namely for hierarchical classification, parametric Monte Carlo methods), probabilistic inference (eg belief
design (methods from XCON and VT), and consistency- networks), and discrete symbolic processing. We deal with
based diagnosis (the GDE-method). algorithms from this last family. These algorithms often
add or remove elements to finite sets representing an ap-
proximate answer, and gradually reduce the difference be-
2 What is anytime reasoning?
tween that set and a set representing the correct answer.
Anytime algorithms are defined as algorithms that return [Zil96] gives a number of desirable properties of any-
some answer for any allocation of computation time, and time algorithms:
are expected to return better answers when given more time
[BD89]. This is in contrast with traditional algorithms 1. Interuptability: the algorithm can be stopped at any-
which guarantee a correct output only after termination, time and provide some answer.
and no guarantees are given for any intermediate results. 2. Monotonicity: the quality of the result is a non-
The behaviour of an anytime algorithm is described by a decreasing function of the computation time.
performance profile. A performance profile describes how 3. Measurable quality: the quality of an approximate re-
sult can be determined precisely.
3 i.e. the functional I/O relation 4. Diminishing returns: the improvement in solution
A. ten Teije, F. van Harmelen 10-2
quality is largest at the early stages of computation, the postconditions are guaranteed to hold on the output of
and it diminishes over time. the PSM (ie. the functionality of the PSM is achieved). Un-
5. Consistency: for a given amount of computation time like traditional pre/postcondition frameworks however, our
on a given input, the quality of the result is always the conditions are gradual. To be more precise, our pre- and
same. postconditions each have an additional parameter. Partial
6. Recognisable quality: the quality of an approximate orderings are defined on these parameters that describe the
result can be easily determined at run-time. degree to which the conditions are fulfilled, with the min-
7. Preemptability: the algorithm can be suspended and imal element signifying completely fulfilled conditions.
resumed with minimal overhead. The two most important proof obligations in this frame-
work for the description of anytime PSMs are as follows4 :
Notice that the first two properties constitute the defini-
tion of anytime algorithms as given at the start of this sec- a first proof obligation is to show how a change in ful-
tion, and are therefore required, rather than desirable. The fillment of the preconditions causes a change in ful-
third and fourth property are also applicable to the anytime fillment of the postconditions;
descriptions of PSMs that we propose in this paper. The A second proof obligation shows that completely ful-
fifth property (consistency) is also (but trivially) applicable filled preconditions imply completely fulfilled post-
since we only deal with deterministic computation. Only conditions.
the last two properties are not applicable to our work for
the following reasons: Recognisable quality is not appli- In order to apply this framework to anytime PSMs, we
cable since we are not dealing with dynamic monitoring must decide on the partial orderings defining gradual ful-
of algorithms, and therefore this property is not relevant. fillment of pre- and postconditions. For the ordering on
Preemptability is not applicable, since in our analysis algo- the preconditions, we obviously choose the amount of run-
rithms are only stopped, and never resumed. time available to the PSM. Because the minimal element
of this ordering must correspond with completely fulfilled
3 Describing gradual properties of PSMs preconditions, we choose the maximally required runtime
as the minimal element, and larger elements under the or-
The motivating question for this paper as given in the in- dering correspond with ever less computation time(!). Be-
troduction was: how should the performance of a PSM be cause runtime cannot be less then 0, the elements range
described so that it can be used as an applicability condi- from complete runtime (the minimal element) down to 0.
tion? As the ordering on the postconditions, we take whatever
Instead of the empirically obtained quality-performance quality measure is taken as characteristic of the result of
graphs used for this purpose in the literature, we aim for the algorithm. The second Zilberstein property guarantees
an analytic treatment of the performance profiles in the that a suitable ordering can be defined on this characteristic.
form of an axiomatic description. This has the advantages The third Zilberstein property demands that this must be a
of not needing expensive and unreliable empirical perfor- measurable value.
mance observations, and of giving more insight in the ac- As mentioned before, a performance profile plots out-
tual behaviour of the PSM. It also fits better with exist- put quality against runtime. The two axes of such a graph
ing approaches of describing applicability condition in the now correspond exactly with our two measures: the pre-
Knowledge Engineering literature. condition measure (runtime) as x-axis, and the postcondi-
The second Zilberstein property above states that the tion measure (output quality) as y-axis (see the figures later
output quality is a gradual property of the available com- in this paper).
putation time. In [vHtT98], we have proposed a general
framework for describing gradual properties of the output
of PSMs as a function of gradual properties of their input.
4 Guidelines for anytime descriptions
If we regard computation time as a special “input param- Describing applicability criteria for PSMs is one of the
eter” to the PSM, anytime PSMs become a special case of hardest tasks when building a PSM library. These crite-
what can be described in our proposed framework for grad- ria must accurately capture both the preconditions and the
ual properties of PSMs. functionality of the PSMs in the library. The accuracy of
In this section we briefly summarise our framework for
4 [vHtT98] defines three more proof obligations, but these are less rel-
describing gradual properties of PSMs. In the next sec-
evant when applying the framework to describe anytime behaviour: one
tions, we will use this framework for the description of per- proof obligation corresponds exactly with Zilbersteins second property
formance profiles of PSMs. (and therefore holds by definition for anytime algorithms); a second obli-
The framework for gradual properties of PSMs that is gation concerned the relation between gradual and completely fulfilled
preconditions, which in the current case simply means that after enough
described in [vHtT98] is based on a traditional pre- and
runtime, the complete solution is computed; finally, the usual correctness
postcondition description of PSMs: given that the precon- property must be shown for the PSM but this time with respect to the
ditions hold on the input of a PSM, then after termination, gradual versions of the pre- and postconditions.
A. ten Teije, F. van Harmelen 10-3
these descriptions is crucial for the later ability to retrieve Growth rate: The amount of increase in quality at each
appropriate elements from the library.
the step during the computation. This increase in quality
This task is already hard in current PSM libraries where can be constant at each step, but may also vary dur-
the applicability conditions only have the form of “labels”, ing the computation (as stated in the fourth Zilberstein
intended to be understood by human users, but without any property: diminishing returns).
further formal semantics. The task becomes even harder
when applicability conditions take the form of complex ex- End condition: The amount of runtime needed for the
pressions in a formal language suited for automatic manip- method to achieve its full (ie. traditional) function-
ulation (as proposed in e.g. [BPG96]). ality. After this point, the quality of the output no
Our proposal to use performance profiles of PSMs longer increases, since the maximum quality has been
threatens to make this task even harder: in our own studies achieved.
we have found that formulating gradual pre- and postcon-
ditions is even harder than formulating traditional pre- and In [GtTvH99] we have put forward the hypothesis that this
postconditions, since the gradual versions require an even scheme of four axioms would be suitable to describe a wide
more detailed analysis of the behaviour of the PSM than is class of anytime behaviours. One of the results of this paper
already required for traditional applicability criteria. is the confirmation of this hypothesis, by showing that this
The hardest steps in describing gradual pre- and post- scheme can be used to describe the anytime behaviour of a
conditions are: (1) defining a suitable ordering on the pre- number of different and realistic PSMs from the literature.
condition; (2) defining a suitable ordering on the postcon-
ditions; and perhaps most difficult of all (3) defining the 5 Example anytime descriptions of PSMs
actual gradual functionality of the PSM (ie its gradual post-
conditions) given some gradual pre-conditions. In this section we will apply the above scheme for describ-
The good news is that when applying our general frame- ing performance profiles of PSMs to a number of concrete
work to anytime performance we can make some of these PSMs. These methods are all described in a modern KBS
choices in advance (so they don’t have to made by the li- textbook [Ste95; Part III].
brary builder), and we can give a structured schema for First we discuss three methods for a classification task.
some of the descriptions that must be supplied by the li- The first two examples (linear candidate confirmation and
brary builder. linear candidate confirmation with forward filtering) are
The choices concerning the preconditions disappear al- theoretical and simple, and are meant to introduce our pro-
together: We always simply add the available runtime as posal. The third (hierarchical classification) is more realis-
an additional parameter, and apply the obvious ordering to tic, and similar to the method used in the MDX system for
this parameter 5 . diagnosing liver diseases [CM83]. We will then turn to the
task of parametric design, and discuss the methods used in
What remains is the formulation of the postconditions
the XCON system (constraint clustering) [McD82] and in
(ie. the gradual functionality of the PSM as a function of in-
the VT systems (propose and revise) [MSM88]. Finally, we
creasing runtime). We have found that this formulation can
discuss the GDE method for the task of consistency-based
always be structured in the same way. To describe the any-
diagnosis [Rei87; dKW87].
time functionality, four axioms are needed, each of which
describes a different aspect of the anytime behaviour, as
follows: 5.1 The classification task
In a classification task, we are given a set of candidate
Initial behaviour: The initial period during which the be-
classes and a set of observed properties of a particular indi-
haviour of the method is constant. Many anytime
vidual, and we must compute which candidate classes sat-
algorithms start producing some output immediately,
isfy the classification criterion on the given properties. The
but the example in section 5.3 shows that some meth-
details of the classification criterion can vary, and are not
ods need an initial “startup period” before they start
relevant to our discussion (see [Ste95; Ch. 7] for the def-
producing intermediate output.
inition of various classification criteria such as candidates
which explain, match or cover the given observations).
Growth direction: This is the direction in which the qual-
Slightly more formally, the task CLASSIFICATION has
ity of the intermediate output changes with increas-
as inputs a set of candidate classes Cs and a set of observa-
ing runtime. The second Zilbertstein property (mono-
tions Obs, and must compute all classes from Cs that satisfy
tonicity) guarantees that quality increases, and this ax-
the classification criterion on Obs:
iom states what is meant by “increase”.
5 While noting that the minimal element corresponds with the maxi-
CLASSIFICATION Cs Obs
mum runtime, as explained in the previous section Ci Ci Cs criterion Ci Obs
A. ten Teije, F. van Harmelen 10-4
5.2 Linear candidate confirmation (MC1) 5.3 Linear confirmation with forward filtering (MC2)
A trivial PSM for the classification task is to iterate over all This method is equal to MC1, but first applies an initial for-
candidate classes, and add them to the output if they satisfy ward reasoning step, in which some of the observations are
the classification criterion6 7 : used to filter the set of possible candidates. The method
MC1 is applied to the resulting candidate set. An assump-
MC1( n, Cs,Obs): tion of this method is that the additional cost of the filter
output = 0/ step is outweighed by the reduction in cost of applying the
candidates = Ci | Ci Cs i n
linear confirmation step to a smaller candidate set. Fur-
for Ci candidates
do if criterion(Ci,Obs)
thermore, it assumes that the forward filtering step only
then output = output+Ci removes candidates which are not solutions to the classi-
done fication problem (ie the filtering step is sound). Instead of a
return output single set of observations, MC2 receives two sets of obser-
vations as input, one to be used in the forward filtering step,
The algorithm MC1 is as given without the additional the other to be used in the candidate confirmation step:
boxed text. If the boxed text is added to the code, we ob-
tain an anytime version of MC1 that we will indicate with MC2( n, Cs,Obs1 ,Obs2 ):
MC1a 8 . As mentioned above, the additional parameter n output = 0/
signifies the available runtime (ie the algorithm terminates candidates = Ci |Ci filter(Cs,Obs1)
after n steps), and is used as the ordering on the precondi- i n
tions. As ordering on the postconditions (= quality measure for Ci candidates
of the output) we will use the subset ordering on the out- do if criterion(Ci,Obs2 )
then output = output+Ci
put set.
done
Following the guidelines from the previous section, the return output
gradual functionality of MC1a can now be specified as fol-
lows: Following the guidelines from the previous section, the
MC1-initial: Initially (with zero runtime) no solutions are gradual functionality of MC2a can now be specified as fol-
computed: lows:
MC1a 0 Cs Obs 0/ MC2-initial: Unlike MC1, MC2 does not immediate pro-
duce intermediate solutions, since it first completes
MC1-direction: The solution set only grows (and never the forward filtering step. If n f indicates the duration
decreases): of the filtering step, then:
MC1a n Cs Obs MC1a n Cs Obs n & nf " MC2a n Cs Obs1 Obs2 ' 0/
MC1-rate: Each additional computation step adds at most
MC2-direction: similar to [MC1-direction].
one solution9:
MC2-rate: similar to [MC1-rate].
MC1a n 1 Cs Obs MC1a n Cs Obs 1
MC2-end: The total required runtime of MC2 is the sum
MC1-end: After considering all candidates, we have ob- of the two stages. The duration of the filtering step is
tained the full functionality: n f , and the duration of the confirmation stage is deter-
n! Cs #" MC1a n Cs Obs $ MC1 Cs Obs mined by the number of candidates that remain after
the filtering step:
Assuming a uniform distribution of the solutions over
the candidate set, the theoretically derived performance n ! f ilter Cs Obs1 n f "
profile determined by these axioms is shown in figure 1a10 . MC2a n Cs Obs1 Obs2 ( MC2 Cs Obs1 Obs2
6 This method is called MC1 in [Ste95; Ch. 7].
7 The languages used for both program code and specifying axioms are
The performance profile determined by these axioms is
close to those used in the KIV interactive program verifier. We expect that
shown in figure 1b. It shows a constant increase in quality
all the formal definitions in this paper can be easily transcribed in the KIV (similar to MC1), but only after an initial period needed for
system [Rei95]. It should then be possible to provide machine-verified the filtering step.
proofs for all the result in this paper. The assumption that the costs of the filter step must be
8 This same box-notation is used for the other algorithms in this paper.
9 the notation % S % is used for the size of a set S outweighed by the savings can now also be stated more pre-
10 Our graphs are plotted as continuous functions, but in reality the in- cisely. The costs of the filtering step is n f , the savings equal
creases in output quality are stepwise. the reduction in the candidate set: Cs f ilter Cs Obs .
A. ten Teije, F. van Harmelen 10-5
|MC1(Cs,Obs)| |MC2(Cs,Obs1,Obs2)|
|MC3(Cs,Obs)|
|filter(Cs,Obs)|+n_f
|Cs| n_f maxdepth(Tree)
Fig. (a) Fig. (b) Fig. (c)
Figure 1: Performance profile of MC1, MC2 and MC3.
The assumption holds when n f & Cs ) f ilter Cs Obs . MC3-initial: Initially, all candidates are still potential so-
This can also be written as n f f ilter Cs Obs & Cs . lutions:
Now notice that this states precisely that the end time of
MC2 is less then the end time of MC1 (see axioms [MC1- MC3a 0 Tree Obs $ leaves Tree
end] and [MC2-end]).
MC3-direction: an extra computation step can only de-
5.4 Hierarchical classification (MC3) crease the set of potential solutions:
The first realistic PSM that we will discuss is hierarchi- MC3a n 1 Tree Obs ' MC3a n Tree Obs
cal classification (used among others in the MDX system
[CM83]). This method no longer does a linear traversal of MC3-rate: Taking b as the branching factor of the tree,
the candidate set. Instead, the candidate set is organised as and assuming that at each level of the tree, at least 1 of
the leaves of a tree. The nodes in this tree are “abstract the abstract classes satisfies the criterion, and assum-
classes”, representing abstractions of sets of candidates. ing a balanced tree, then each step reduces the candi-
The PSM recursively descends down the tree, at each level date set by a factor b:
deciding if the abstract classes still satisfy the observations.
If yes, the method continues to descend down that part of MC3a n Tree Obs
MC3a n 1 Tree Obs !
the tree, if no, the entire tree below the abstract class is b
pruned. At each step of the PSM, the intermediate solution
is the set of all candidates (= all leaves) that can be found MC3-end: MC3 needs as many steps as there are levels in
under the currently considered abstract classes. the tree
n ! maxdepth Tree "
MC3( n, Tree,Obs):
MC3a n Tree Obs ' MC3 Tree Obs
output = leaves(Tree)
current = Tree
next = [] Notice that for candidate classes of exponential size
d=1 (which occur for multi-class classification), both MC1 and
while current + * 0/ d n MC2 require exponential runtime (since they perform a
do for c current linear traversal of the exponential candidate set), while
do if not criterion(c,Obs) MC3 only requires linear runtime (namely the depth of the
then output = output - leaves(c) tree, axiom [MC3-end]). This is all consistent with known
else next = next + children(c) results about the complexity of hierarchical classification
done [GSC87].
current = next
next = 0/ Using the performance profiles
d = d+1
done We have now defined anytime performance profiles for
return output three different classification methods. We give three exam-
ples how these profiles help us with selecting methods from
The gradual functionality of MC3 can be characterised a library. First, the profiles tell us how we can trade compu-
as follows: tation time for solution quality. For example, fig 1c shows
A. ten Teije, F. van Harmelen 10-6
that the increase in quality of MC3 (ie the decrease in the This partial ordering can be used to determine an execution
,
candidate set) is exponential while for MC1 and MC2 this order of the steps. The inputs of the XCON method are
linear. If it is important to quickly obtain a good approx- a list of constraint clusters and the set of parameters. The
imation of the final solution, then MC3 is more attractive order in the list of clusters is assumed to respect the partial
than MC1 or MC2. dependency-ordering among the clusters.
Secondly, we see from the performance profiles that The XCON method simply iterates over the constraints
MC1 and MC2 are incomplete (but sound) approximations clusters, solves each cluster separately (no details for this
of the final solution. The intermediate solutions of MC3 step are given in the definition below), and adds the assign-
on the other hand are unsound approximations of the final ments found for each step to the current output:
solution, since the profile of MC3 approaches the solutions
from above, rather than from below. XCON( n, Ps,[Cs1 ,...,Csk ]):
Thirdly, we see that not all methods start to produce ap- output = 0/
proximate solutions immediately. If such a property is im- for i=1 to min(n, k )
portant (e.g. in a setting where some solution is always do CurrentPs = relevant(Ps,Csi)
required but no guarantees can be given on the available S = (Pi ,Vi ) | Pi CurrentPs
runtime), then MC2 is unattractive. consistent(Cs,S)
output = output + S
done
5.5 The parametric design task
return output
We now turn to a very different type of task, namely the
task of parametric design. In this task we are given a set of The gradual functionality of XCON can be characterised
parameters and a set of constraints, and have to compute an as follows:
assignment for each parameter such that these assignments
are consistent with the given constraints. XCON-initial: Initially no assignments have been com-
Slightly more formally: puted.
PARAMETRIC-DESIGN Ps Cs $ S with
XCONa 0 Ps 21 Cs1 2-3-4- 56$ 0/
S Pi Vi Pi Ps $ consistent Cs S .-
In the next two sections, we give two problem solving XCON-direction: The set of assignments that is com-
methods for performing this parametric design task. puted grows monotonically.
5.6 Param. design by constraint clustering (XCON)
XCONa n Ps 1 Cs1 7-4-3- 58:9
XCON [McD82] is a method for parametric design based XCONa n 1 Ps 1 Cs1 7-4- 58
on a particular organisation of constraints. The constraints
are divided in clusters. The constrains within a cluster have XCON-rate: The maximal number of new assignments
much mutual dependencies, but no dependencies exist with for a cluster is the number of relevant variables of the
constraints in other clusters. This makes it possible to solve constraints in that cluster. This is a maximum, since
the problem in separate steps, with backtracking occuring some parameters might have been computed in earlier
only within each step (namely per cluster), and not between steps (clusters). Because of the assumption of inde-
steps. An example of such steps in the XCON application pendency between steps, such assignments never vio-
(configuring VAX mainframe computers for Digital) are: late the constraints of the current step.
1. make the order complete
2. configure the set of components for the CPU cabi- XCONa n 1 Ps 1 Cs1 7-4- 58 ;
net(s) XCONa n Ps 1 Cs1 7-4- 58 < = relevant Ps Csn > 1
3. configure the set of components for the Unibus cabi-
net(s) XCON-end: The complete functionality is obtained after
4. configure the panels for the Unibus cabinet(s) k steps, with k the number of constraint clusters in the
5. configure the spatial layout of the cabinets input.
6. configure the cabling
These are ordered as follows: n! k" XCONa n Ps 1 Cs1 7-4-4 Csk 58$
XCON Ps 21 Cs1 7-4-3 Csk 56
/ 2 0
1 0" 5 "/ 6 These axioms determine the performance profile, as
shown in figure 2a. The graph shows a stepwise increase of
3 " 4 the output quality in k steps.
A. ten Teije, F. van Harmelen 10-7
|XCON(Pars,[Cons1,...,Consk])| |P&R(Pars,Cons)|
k |Pars|
Fig (a) Fig (b)
Figure 2: Performance profile of XCON and P&R
5.7 Parametric design by propose and revise (P&R) puted.
Another well known method to obtain the functionality of P&Ra 0 Ps Cs 0/
parametric design is Propose & Revise (P&R). The P&R
method iterates over the set of parameters. In each step, P&R-direction: Unlike XCON, the set of assignments
P&R takes a new parameter and proposes a likely value does not grow monotonically in P&R, but the set of as-
for that parameter. This new assignment becomes part of signed parameters does (assigned parameters might be
the current partial design. If this partial design is consis- revised). The set Pi Pi Vi P&Ra n Ps Cs @ con-
tent with the constraints, a next step can be taken. If the tains all parameters that have been assigned a value
partial design violates the constraints then the partial de- after n steps. The monotonic growth is then:
sign will be revised such that it becomes consistent with
Pi Pi Vi P&Ra n Ps Cs @A
the constraints. After fixing the partial design the process
Pi Pi Vi P&Ra n 1 Ps Cs
continues with the next parameter.
P&R-rate: P&R iterates over the set of parameters, there-
P&R( n, Ps,Cs): fore each step yields exactly one additional assigned
output = 0/
parameter:
for i=1 to min(n, |Ps| )
do Vi = propose(output,Pi) Pi Pi Vi P&Ra n 1 Ps Cs
output = output = (Pi ,Vi ) Pi Pi Vi P&Ra n Ps Cs 1
if ? consistent(Cs,output)
then output = revise(Cs,output) P&R-end: The method needs as many steps as there are
done parameters:
return output
n! Ps #" P&Ra n Ps Cs P&R Ps Cs
This method uses domain knowledge in the propose step
and in the revise step, whereas the XCON method uses do- These axioms determine the performance profile, as
main knowledge in the way the constraints are clustered. shown in figure 2b. The set of assigned parameters grows
For XCON we used the set of assignments as the quality at a constant rate during the computation.
measure for the computation. This same measure cannot be Concerning axiom [P&R-direction]: This axiom allows
used for P&R. Unlike XCON, P&R assignments in earlier that partial assignments are not a subset of the final as-
steps might have to be revised in later steps. As a result, the signments (ie partial assignments are allowed to be un-
set of assignments does not grow monotonically, violating sound). However, in the VT application which used the
the second Zilberstein property. For this reason, we use an- P&R method, it turns out that the domain knowledge used
other quality measure for P&R, namely the set of assigned in the propose step is so good that revision is almost never
parameters instead of the set of assignments (ie parame- needed: on test-cases with 1000-2000 parameters (and
ters plus their values). This set does grow monotonically, therefore as many propose steps), there were only some 10-
since parameters might be revised, but once assigned, a pa- 20 violations (and therefore as many revision steps), ie only
rameter is never left without a value in later stages of the 1% of the proposed values were wrong [MSM88]. Thus,
compuation. although the soundness of XCON’s approximations (ex-
pressed by XCON’s axiom [XCON-direction]) cannot be
P&R-initial: Initially no assignments have been com- guaranteed for P&R, in practice P&R comes very close.
A. ten Teije, F. van Harmelen 10-8
Using the performance profiles GDE-initial: Initially no diagnoses are computed.
Again, the performance profiles for the different methods GDEa 0 SD Obs E 0/
can be used for selecting the methods from a library. It fol-
lows from axioms [XCON-end] and [P&R-end] that P&R
GDE-direction: For every diagnosis from step n, there
divides the process in Ps steps, and XCON in k steps
will be a superset diagnosis in step n 1, in other
(k the number of constraint clusters). Since every clus-
words: individual diagnoses grow monotonically dur-
ter will assign at least one additional parameter, we have
ing the computation:
Ps ! k, so P&R divides the process in much smaller steps
then XCON. If it is important that new solutions are pro- D GDEa n SD Obs
duced at a constant rate during the computation process
"GF : D D D GDEa n 1 SD Obs
D
(e.g. because of interface requirements with users or other
programs), then P&R is more attractive from an anytime
GDE-rate: Unfortunately, we have not been able to esti-
perspective. mate by how much individual diagnoses grow when
the maximum size of the conflict sets increases by 1.
5.8 The consistency based diagnosis task
Thus, in the following expression, we have no value
In consistency-based diagnoses [Rei87] we are given a the- for m.
ory describing the intended behaviour of a system (called
the system description, SD), and some observations of the D GDEa n SD Obs 7
systems actual behaviour, Obs. A diagnosis problem exists D GDEa n 1 SD Obs 2
when Obs is inconsistent with SD (ie. the system is ob- D 9 D
served not to function as intended). The goal is to compute "H D D ! m
a minimal set of components Diag which can ”explain” the
abnormal behaviour, ie. assuming that these components GDE-end: Again unknown. We have not been able to give
are abnormal suffices to make Obs again consistent with a reasonably sharp upperbound on the maximum size
SD. of the conflict sets that is required to compute all di-
agnoses. Of course, after some value k, the algorithm
DIAGNOSIS SD Obs B Diag will compute no more diagnoses (since all have been
such that consistent SD C Obs Diag computed), but we do not know the value of k:
5.9 The GDE method n! k" GDEa n SD OBS I GDE SD Obs
The best known PSM for this method is the GDE method
[dKW87]: It first computes so called conflict-sets. A Because of the unknown parameters in axioms [GDE-
conflict-set is a set of components which, given the obser- rate] and [GDE-end], we are not able to give a graphical
vations, can not all be correct, ie at least one component in rendition of the performance profile for the GDE method.
each conflict set must be part of the diagnosis. After having
computed all minimal conflict-sets, GDE then uses these 6 Conclusions & Future Work
conflict-sets to compute so called hitting-sets. A hitting-
Conclusions In the KE literature, libraries of PSMs have
set is a set of components that contains at least one ele-
been indexed using functional descriptions and knowledge
ment from every conflict-set. It follows that each minimal
requirements. In this paper, we have proposed the use of
hitting-set is a diagnosis.
non-functional properties (in our case anytime performance
Pos [Pos93] has shown how this can be turned into an
profiles) as a library index for PSMs.
anytime algorithm, namely by only computing the minimal
We have given axiomatic descriptions of anytime be-
conflict-sets sets up to a maximum size n instead of com-
haviour of PSMs. This is unlike existing work on anytime
puting all minimal conflict-sets, and then computing all
algorithms, which obtains performance profiles by simula-
minimal hitting sets for this limited collection of conflict-
tion and measurement. Such empirically obtained profiles
sets. This anytime version of GDE is as follows:
are dependent on the quality of the simulations, which are
GDE( n, SD,Obs):
often expensive, and also not very reliable since they de-
Cs = all minimal conflict-sets C pend on the particular input distribution used for the simu-
with D C D n lations. On the other hand, our axiomatic descriptions are
output = all minimal hitting sets for Cs often limited to giving an upper- or lower-bound on the
return output rate of the quality improvement, whereas empirical perfor-
mance profiles do obtain values for the improvement rate.
The gradual functionality of GDE can be characterised In order to make it easier for library builders to give ac-
as follows: tual performance profiles for the PSMs in their libraries, we
A. ten Teije, F. van Harmelen 10-9
have given guidelines for constructing such an axiomatic behaviour of realistic PSMs.
J
descriptions: each description should consist of four state-
ments, describing initial behaviour of the PSM, direction of References
quality change, rate of quality of change per time unit and
the time at which the optimal output quality is obtained. [BD89] M. Boddy and T. Dean. Solving time-dependent
This regularity in the description of the dynamic behaviour planning problems. In Proceedings IJCAI–89, De-
of PSMs confirms a hypothesis put forward in our earlier troit, Michigan USA, August 1989.
work [GtTvH99].
[BD94] M. Boddy and T. Dean. Deliberation schedul-
Our axiomatic description of performance profiles is ing for problem solving in time-constrained environ-
based on our earlier and more general proposal for describ- ments. Artificial Intelligence, 67:245–285, 1994.
ing gradual properties of PSMs [vHtT98]. It turns out that
performance profiles can be described in our framework for [Bod91] M. Boddy. Anytime problem solving using dy-
describing gradual properties. This was not obvious before- namic programming. In Proceedings of the ninth Na-
hand because the framework must be used in a slightly non- tional conference on artificial intelligence AAAI–91,
standard way. It was designed to deal with functional prop- pages 738–743, 1991.
erties (I/O-pre/post-conditions), while anytime behaviour
is a non-functional property (concerning also the computa- [BPG96] V. R. Benjamins and C. Pierret-Golbreich. As-
tion time, and not only the I/O relation). sumptions of problem-solving methods. In N. Shad-
Future Work In the axioms in this paper, we give only bolt, K. O’Hara, and G. Schreiber, editors, Lecture
upper- or lowerbounds for the rate of quality improvement Notes in Artificial Intelligence, 1076, 9th European
(the third axiom in our general scheme), in particular when Knowledge Acquisition Workshop, EKAW-96, pages
these rates are based on the quality of heuristic knowledge. 1–16, Berlin, 1996. Springer-Verlag.
Instead of such upper- and lowerbounds, we would like
to give more precise expected values for the improvement [CM83] B. Chandrasekaran and S. Mittal. Deep versus
rate, based on the quality of the heuristic. For example, in compiled knowledge approaches to diagnostic prob-
MC1 the solution set increases with at most one element lem solving. International Journal of Man-Machine
each computation step. However, it is easy to see that as- Studies, 19:425–436, 1983.
suming a uniform distribution of solutions over candidate [DB88] T. Dean and M. Boddy. An analysis of time-
set, the expected rate of increase one element for each k dependent planning. In Proceedings of the seventh
steps (k the number of candidates divided by the number National conference on artificial intelligence AAAI–
of solutions). Furthermore, using a heuristic ordering of 88, pages 49–54, Saint Paul, Minnesota, 1988.
the candidate set, we can expect one additional element for
each k n steps, with k n a increasing function of n. We [dKW87] J. H. de Kleer and B. C. Williams. Diagnos-
have currently no formal framework in which to express ing multiple faults. Artificial Intelligence, 32:97–130,
these and similar statements. 1987.
We would also like to study which anytime behaviour is
more attractive under which circumstances. For example, [FB98] D. Fensel and R. Benjamins. The role of as-
it is clear that dividing a given runtime in a large number sumptions in knowledge engineering. International
of small steps is more attractive than dividing it in a small Journal on Intelligent Systems (IJIS), 13(8):715–748,
number of large steps (compare XCON, fig 2a and P&R, 1998.
fig 2b). Less clear is the question whether the behaviour of
[FS98] D. Fensel and R. Straatman. The essense of
MC2 is more attractive than MC1 (because MC2 uses less
problem-solving methods: Making assumptions for
total runtime) or whether MC1 is more attractive than MC2
gaining efficiency. International Journal of Human-
(because its quality increase is more evenly divided over
Computer Studies (IJHCS), 48(2):181–215, 1998.
the computation time). To our knowledge, the literature on
anytime algorithms has not tackled this question until now. [GSC87] A. Goel, N. Soundarajan, and B. Chandraseka-
Finally, in [GtTvH99] we have developed some simple ran. Complexity in classificatory reasoning. In AAAI–
techniques for proving dynamic properties of KBS, and we 87, pages 421–425, 1987.
used the interactive theorem prover KIV [Rei95] to verify
a simple PSM (in fact, MC1). All the formal definitions [GtTvH99] P. Groot, A. ten Teije, and F. van Harmelen.
in this paper (both program code and axioms) have been Formally verifying dynamic properties of knowledge
given in a syntax already very close to that used in the KIV based systems. In Proceedings 11th European Work-
systems. We expect that our techniques can be applied to shop on Knowledge Acquisition, Modeling, and Man-
verify the axiomatic anytime descriptions given in this pa- agement (EKAW ’99), Lecture Notes in Artificial In-
per, yielding machine-assisted formal proofs of the anytime telligence. Springer Verlag, 1999.
A. ten Teije, F. van Harmelen 10-10
[Kor90] R. Korf. Real-time heuristic search. Artificial In-
telligence, 42(2):189–212, 1990.
[McD82] J. McDermott. R1: A rule-based configurer of
computer systems. Artificial Intelligence, 19:39–88,
1982.
[MSM88] S. Marcus, J. Stout, and J. McDermott. VT: An
expert elevator designer that uses knowledge-based
backtracking. AI Magazine, Spring:95–111, 1988.
[Pos93] A. Pos. Time-constrained model-based diagnosis.
Technical report, University of Twente, department of
computer science, 1993. Master’s thesis.
[Rei87] R. Reiter. A theory of diagnosis from first princi-
ples. Artificial Intelligence, 32:57–96, 1987.
[Rei95] W. Reif. The KIV-approach to Software Verifica-
tion. In M. Broy and S. Jähnichen, editors, KORSO:
Methods, Languages, and Tools for the Construction
of Correct Software – Final Report. Springer LNCS
1009, 1995.
[SB95] R. Straatman and P. Beys. A performance model
for knowledge-based systems. In Proceedings of Eu-
ropean Symposium on the Validation and Verification
of Knowledge Based Systems (EUROVAV’95), pages
253–263, Adeiras, June 1995. Université de Savoie,
Chambér.
[Ste95] M. Stefik. Introduction to Knowledge-Based Sys-
tems. Morgan Kaufmann, 1995.
[vHtT98] F. van Harmelen and A. ten Teije. Characteris-
ing approximate problem-solving by partial pre- and
postconditions. In Proceedings of ECAI’98, pages
78–82, Brighton, August 1998.
[WAS98] B. Wielinga, J. Akkermans and A. Schreiber.
A competence theory approach to problem solving
method construction. Internat. Journal of Human-
Computer Studies, special issue on problem-solving
methods, 49(4), 1998.
[Zil96] S. Zilberstein. Using anytime algorithms in in-
telligent systems. Artificial Intelligence Magazine,
fall:73–83, 1996.
[ZR96] S. Zilberstein and S.J. Russell. Optimal compo-
sition of real-time systems. Artificial Intelligence,
82(1–2):181–213, 1996.
A. ten Teije, F. van Harmelen 10-11