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.