Algorithms and Limits for Compact Plan Representations
  Compact representations of objects is a common concept in computer science.
Automated planning can be viewed as a case of this concept: a planning instance
is a compact implicit representation of a graph and the problem is to find a
path (a plan) in this graph. While the graphs themselves are represented
compactly as planning instances, the paths are usually represented explicitly
as sequences of actions. Some cases are known where the plans always have
compact representations, for example, using macros. We show that these results
do not extend to the general case, by proving a number of bounds for compact
representations of plans under various criteria, like efficient sequential or
random access of actions. In addition to this, we show that our results have
consequences for what can be gained from reformulating planning into some other
problem. As a contrast to this we also prove a number of positive results,
demonstrating restricted cases where plans do have useful compact
representations, as well as proving that macro plans have favourable access
properties. Our results are finally discussed in relation to other relevant
contexts.
