3 years ago

From Abstractions to "Natural Languages" for Coordinating Planning Agents. (arXiv:1905.00517v2 [cs.AI] UPDATED)

Yu Zhang, Li Wang
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.

Publisher URL: http://arxiv.org/abs/1905.00517

DOI: arXiv:1905.00517v2

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.