In exploratory domains, agents’ behaviors include switching between activities, extraneous actions, and mistakes.
Such settings are prevalent in real world applications such as interaction with open-ended software,
collaborative office assistants, and integrated development environments. Despite the prevalence of such
settings in the real world, there is scarce work in formalizing the connection between high-level goals and
low-level behavior and inferring the former from the latter in these settings. We present a formal grammar
for describing users’ activities in such domains. We describe a new top-down plan recognition algorithm
called CRADLE (Cumulative Recognition of Activities and Decreasing Load of Explanations) that uses this
grammar to recognize agents’ interactions in exploratory domains. We compare the performance of CRADLE
with state-of-the-art plan recognition algorithms in several experimental settings consisting of real and
simulated data. Our results show that CRADLE was able to output plans exponentially more quickly than
the state-of-the-art without compromising its correctness, as determined by domain experts. Our approach
can form the basis of future systems that use plan recognition to provide real-time support to users in a
growing class of interesting and challenging domains