A prototype-based method for classification with time constraints: a case study on automated planning

The main goal of Nearest Prototype Classification is to reduce storage space and retrieval time of classical Instance-Based Learning (IBL) algorithms. This motivation is higher in relational data since relational distance metrics are much more expensive to compute than classical distances like Euclidean distance. In this paper, we present an algorithm to build Relational Nearest Prototype Classifiers (RNPCs). When compared with Relational Instance-Based Learning (Relational IBL or RIBL) approaches, the algorithm is able to dramatically reduce the number of instances by selecting the most relevant prototypes, maintaining similar accuracy. The number of prototypes is obtained automatically by the algorithm, although it can also be bound by the user. In this work, we also show an application of RNPC for automated planning. Specifically, we describe a modeling task where a relational policy is built following an IBL approach. This approach uses the decisions taken by a planning system as learning examples. We show that when the number of learning examples is reduced with RNPC, the resulting policy is able to scale up better than the original planning system.