  Several approaches have been developed for answering users' specific
questions about AI behavior and for assessing their core functionality in terms
of primitive executable actions. However, the problem of summarizing an AI
agent's broad capabilities for a user is comparatively new. This paper presents
an algorithm for discovering from scratch the suite of high-level
"capabilities" that an AI system with arbitrary internal planning
algorithms/policies can perform. It computes conditions describing the
applicability and effects of these capabilities in user-interpretable terms.
Starting from a set of user-interpretable state properties, an AI agent, and a
simulator that the agent can interact with, our algorithm returns a set of
high-level capabilities with their parameterized descriptions. Empirical
evaluation on several game-based scenarios shows that this approach efficiently
learns descriptions of various types of AI agents in deterministic, fully
observable settings. User studies show that such descriptions are easier to
understand and reason with than the agent's primitive actions.
