From Abstractions to "Natural Languages" for Coordinating Planning Agents

  • 2020-03-18 02:16:19
  • Yu Zhang, Li Wang
  • 0

Abstract

Despite significant advancements in developing autonomous agents,communication between them often relies on a set of pre-specified symbols for agiven domain. In this paper, we investigate the automatic construction of thesesymbols from abstractions to form "natural languages" for such agents. Thefocus of this initial investigation is on a task planning setting where oneagent (the speaker) directly communicates a "plan sketch" to another agent (thelistener) to achieve coordination. In contrast to prior work, we view languageformation as a fundamental requirement for resolving miscoordination. This viewenables us to "compute" a language from the ground up by mapping physicalstates to symbols, thus reverse engineering the function of languages.Languages that arise from this process are only approximately expressive of theactual plans, meaning that they specify abstractions over the plan space, whichis not only theoretically appealing as it provides the desired flexibility tothe listener to choose its plan during execution, but also practically usefulsince it both reduces the communication cost of the speaker and computationalcost of the listener. We formulate this language construction problem and showthat it is NEXP-complete. An approximate solution is then developed to relatethis problem to task planning problems that have efficient off-the-shelfsolutions. Finally, we discuss a multi-agent path-finding domain in ourevaluation to provide a comprehensive set of results to illustrate the benefitsof the constructed languages and their applications.

 

Quick Read (beta)

loading the full paper ...