AAAI Publications, Nineteenth International Conference on Automated Planning and Scheduling

Font Size: 
Exploiting N-Gram Analysis to Predict Operator Sequences
Christian Muise, Sheila McIlraith, Jorge A. Baier, Michael Reimer

Last modified: 2009-10-16

Abstract


N-gram analysis provides a means of probabilistically predicting the next item in a sequence. Due originally to Shannon, it has proven an effective technique for word prediction in natural language processing and for gene sequence analysis. In this paper, we investigate the utility of n-gram analysis in predicting operator sequences in plans. Given a set of sample plans, we perform n-gram analysis to predict the likelihood of subsequent operators, relative to a partial plan. We identify several ways in which this information might be integrated into a planner. In this paper, we investigate one of these directions in further detail. Preliminary results demonstrate the promise of n-gram analysis as a tool for improving planning performance.

Full Text: PDF