Some Mathematical Structures Underlying Efficient Planning

Aarati Parmar

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.