ECAI-2000 Conference Paper

[full paper]

Describing Problem Solving Methods using Anytime Performance Profiles

Annette ten Teije, Frank van Harmelen

We propose the use of anytime performance profiles to describe the computational behaviour of problem solving methods. 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, we give a fixed schematic form for these 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).

Keywords: Knowledge Acquisition, Verification and Validation of Knowledge-Based Systems, Resource-Bounded Reasoning

Citation: Annette ten Teije, Frank van Harmelen: Describing Problem Solving Methods using Anytime Performance Profiles. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.181-185.