  Human behavior is inherently hierarchical, resulting from the decomposition
of a task into subtasks or an abstract action into concrete actions. However,
behavior is typically measured as a sequence of actions, which makes it
difficult to infer its hierarchical structure. In this paper, we explore how
people form hierarchically-structured plans, using an experimental paradigm
that makes hierarchical representations observable: participants create
programs that produce sequences of actions in a language with explicit
hierarchical structure. This task lets us test two well-established principles
of human behavior: utility maximization (i.e. using fewer actions) and minimum
description length (MDL; i.e. having a shorter program). We find that humans
are sensitive to both metrics, but that both accounts fail to predict a
qualitative feature of human-created programs, namely that people prefer
programs with reuse over and above the predictions of MDL. We formalize this
preference for reuse by extending the MDL account into a generative model over
programs, modeling hierarchy choice as the induction of a grammar over actions.
Our account can explain the preference for reuse and provides the best
prediction of human behavior, going beyond simple accounts of compressibility
to highlight a principle that guides hierarchical planning.
