Efficient Multi-agent Epistemic Planning: Teaching Planners About Nested
  Belief
  Many AI applications involve the interaction of multiple autonomous agents,
requiring those agents to reason about their own beliefs, as well as those of
other agents. However, planning involving nested beliefs is known to be
computationally challenging. In this work, we address the task of synthesizing
plans that necessitate reasoning about the beliefs of other agents. We plan
from the perspective of a single agent with the potential for goals and actions
that involve nested beliefs, non-homogeneous agents, co-present observations,
and the ability for one agent to reason as if it were another. We formally
characterize our notion of planning with nested belief, and subsequently
demonstrate how to automatically convert such problems into problems that
appeal to classical planning technology for solving efficiently. Our approach
represents an important step towards applying the well-established field of
automated planning to the challenging task of planning involving nested beliefs
of multiple agents.
