# Coordination of Multiple Autonomous Agents Using Naturally Generated Languages in Task Planning
## 1 Introduction  
Compared with single-agent systems, multi-agent systems have the distribution properties of time, space, and function, and have several advantages in task applicability, execution efficiency, and system robustness [1]. Real-world applications of multi-agent systems include logistics [2], construction [3], search and rescue [4], warehouse automation [5], infrastructure placement [6], computer animation [7], etc. Due to the lack of complete knowledge, agents usually need to exchange their states, actions, or goals to collectively carry out system tasks. Consequently, a communication language or protocol should be predefined to inform cooperative strategies when designing multi-agent systems.  
Two methods are commonly used to construct languages for agent communication. One is to design a certain artificial language for agents [8; 9]. The other is to let agents communicate in natural languages [10; 11]. Most of the studies on multi-agent planning and distributed control use the former method to exchange messages. The latter approach is helpful for human partners to understand the behavior of agents. However, agents must learn two different internal representations of themselves and humans, which can be counterproductive. In fact, it is not necessary for agents to use human languages in a situation where only artificial agents exist. In this paper, we try to create the agents' own languages that can be used to coordinate them. The languages are not predefined case-by-case and are naturally generated based on the abstraction of agents' states in the environment.  
Our work is motivated by a fundamental question from agent coordination: what kind of information do agents need to communicate? We set out to answer the question by considering a particular situation in which communication is only available in task planning phase. In this case, thecommon way for agents is to send a feasible plan to their teammates to be followed when cooperation is needed. The objective of this work is to construct a kind of language that can be used to specify plans, while not bringing many constraints for agents and reducing the cost of communication as much as possible.  
The contributions of this work have three aspects: First, we formulate a language generation problem for multi-agent systems and introduce some fundamental features of the language that appear in agent coordination; Second, we give sufficient and necessary conditions of valid abstraction, based on which an efficient algorithm is developed to generate languages that are complete and optimal. Third, we apply the algorithm to dozens of environments and compare the advantages of languages generated by our algorithm with other similar languages in a path-planning domain.  
The rest of the paper is organized as follows. We review the related work in Section 2. Section 3 introduces the background of multi-agent planning and presents the problem formulation of language generation. Section 4 provides the conditions of valid abstraction and describes a language generation algorithm. Section 5 implements the algorithm and evaluates the languages. Conclusions and future work are given in Section 6.