From Abstractions to "Natural Languages" for Coordinating Planning
  Agents
  Despite significant advancements in developing autonomous agents,
communication between them often relies on a set of pre-specified symbols for a
given domain. In this paper, we investigate the automatic construction of these
symbols from abstractions to form "natural languages" for such agents. The
focus of this initial investigation is on a task planning setting where one
agent (the speaker) directly communicates a "plan sketch" to another agent (the
listener) to achieve coordination. In contrast to prior work, we view language
formation as a fundamental requirement for resolving miscoordination. This view
enables us to "compute" a language from the ground up by mapping physical
states to symbols, thus reverse engineering the function of languages.
Languages that arise from this process are only approximately expressive of the
actual plans, meaning that they specify abstractions over the plan space, which
is not only theoretically appealing as it provides the desired flexibility to
the listener to choose its plan during execution, but also practically useful
since it both reduces the communication cost of the speaker and computational
cost of the listener. We formulate this language construction problem and show
that it is NEXP-complete. An approximate solution is then developed to relate
this problem to task planning problems that have efficient off-the-shelf
solutions. Finally, we discuss a multi-agent path-finding domain in our
evaluation to provide a comprehensive set of results to illustrate the benefits
of the constructed languages and their applications.
