Some Mathematical Structures Underlying Efficient Planning

Logical Formalization of Commonsense Reasoning

Volume

Papers from the 2003 AAAI Spring Symposium

Contents

We explore antimatroids, also known as shelling structures, a construct used to formalize when greedy (local) algorithms are optimal, as well as their relation to the strong measure of progress P introduced in (Parmar 2002b). We begin with an example from the map coloring domain to spark the reader’s intuitions, and then move towards a more general application of shelling to the strong measure of progress. We also introduce some extensions of shelling to planning on a different level. Macro-operators are another kind of mathematical structure that help give efficient and easy-to-understand plans, but we must be careful how we use them when defining strong measures of progress.