Annals of Mathematics and Articial Intelligence manuscript No. (will be inserted by the editor) The Skyline Algorithm for POMDP Value Function Pruning

Abstract We address the pruning or ltering problem, encountered in exact value iteration in POMDPs and elsewhere, in which a collection of linear func-tions is reduced to the minimal subset retaining the same maximal surface. We introduce the Skyline algorithm, which traces the graph corresponding to the maximal surface. The algorithm has both a complete and an iterative version, which we present, along with the classical Lark’s algorithm, in terms of the basic dictionary-based simplex iteration from linear programming. We discuss computational complexity results, and present comparative experiments on both randomly-generated and well-known POMDP benchmarks