The PAC-learnability of planning algorithms: Investigating simple planning domains

A framework was presented by Natarajan (B.K. Natarajan, On learning from exercises, in: Computational Learning Theory: Proceedings of the Second Annual Workshop, Morgan Kaufmann, Santa Cruz, CA, 1989, pp. 72–87) for the speedup learning of search algorithms. Speedup learning solves the problem of us...

Full description

Saved in:
Bibliographic Details
Published in:Information sciences 1999-05, Vol.116 (1), p.83-95
Main Authors: Dormer, R.D., MacNish, C.
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A framework was presented by Natarajan (B.K. Natarajan, On learning from exercises, in: Computational Learning Theory: Proceedings of the Second Annual Workshop, Morgan Kaufmann, Santa Cruz, CA, 1989, pp. 72–87) for the speedup learning of search algorithms. Speedup learning solves the problem of using teacher-provided examples to guide the improvement of algorithm efficiency. In this paper we extend their results by identifying two classes, the emonomial and emonotonic domains. We show that, in the Natarajan model, the speedup learning problem is solvable for the latter but not for the former. We outline further promising lines of investigation that may lead to a more comprehensive classification of the difficulty of speedup learning over a range of domains.
ISSN:0020-0255
1872-6291
DOI:10.1016/S0020-0255(98)10095-6