Traditional selection criteria for Problem Solving Methods (PSMs) from
libraries concentrate solely on the functionality of these methods, and ignore
their computational performance. We propose the use of anytime performance
profiles to describe the computational behaviour of problem solving methods,
and to use these as additional selection criteria when selecting methods from a
library. A performance profile describes how the quality of the output of an
algorithm gradually increases as a function of the computation time. Such
anytime descriptions of problem solving methods are attractive because they
allow a trade-off to be made between available computation time and
output-quality. It turns out that many problem solving methods found in the
literature have a natural anytime behaviour, which has remained largely
unexploited until now.
In this paper we propose an axiomatic description of performance
profiles. Furthermore, in order to make our proposal feasible for library
builders, we give guidelines on how to organise such axiomatic
descriptions. Finally, we apply our proposal to a number of realistic
problem-solving methods, namely hierarchical classification (used in MDX),
parametric design (methods from XCON and VT), and consistency-based diagnosis
(the GDE-method).