# Coordination of Multiple Autonomous Agents Using Naturally Generated Languages in Task Planning
## 2 Related Work  
Communication is one of the most basic and important issues in multi-agent coordination. Depending on how information is obtained, communication can be divided into implicit mechanisms, for example, pheromone [12], in which agents acquire information about their teammates through the world, and explicit mechanisms, in which agents directly transmit information through media, such as spoken languages. Explicit communication is often used in intentionally multi-agent systems, since it is efficient to share knowledge between agents [13]. In addition, a taxonomy of coordination models for mobile agent is proposed for internet applications. Based on the degrees of spatial and temporal coupling, coordination-mode is categorized into four kinds: direct, meeting-oriented, blackboard-based, and Linda-like [14]. For the multi-agent planning problem, there is work on learning communication policies, where information exchange is treated as an explicit choice that may be unreliable and incur a cost, and several approximation techniques are developed to solve the optimization problem [15; 16]. To overcome the high computational complexity of solving the decentralized multi-agent decision-making problem under uncertainty, there also exists work on developing efficient online planning with selective communication algorithms [17; 18]. Furthermore, a neural model trained via backpropagation is proposed to enable cooperating agents to learn to represent the information they observed and communicate it with other agents [19]. ACL (Agent communication language) is an important standard language for the communication of agents and has been well-studied in software-agent systems [20]. FIPA [21] and KQML [22] are the most popular languages, and both are constructed based on speech act theory. ACLs are composed of shared communication syntax and lexicon that are defined by a human group for different purposes. In the multi-agent cooperative control problem, information exchange between agents is often required to achieve expected goals, such as consensus [23], formation control [8], and flocking [24]. Generally, communication languages used in these methods are given in advance, and no attention is paid to the generation of the languages. Communication in natural languages is the most obvious manner when multi-agent systems include human partners. A representative approach is the inverse semantics model [10], by which the agent with a breakdown can ask humans for help using natural languages. Recent work has explored the interactive task learning in which humans teach robots to perform tasks through natural languages [25; 26]. Normally, the human-robot/agent interaction requires the agents to be able to understand natural language sentences [27], and to generate sentences representing their internal information [28]. This process requires a lot of effort and is error-prone. Our language generation problem has a connection with the work on the origin and evolution of natural languages, which has been studied earlier in evolutionary and computational linguistics [29; 30]. Most of the prior works studied language evolution in the context of evolutionary games[31], for example, the talking heads experiment [32]. In particular, a study [33] suggests a relation between natural languages and a hidden planning language that preexists in the mind. While our work addresses a similar problem, we take a step further by formulating the language generation problem in the computational model of rationality. It is worth noting that language evolution is quite a complicated problem, and many researchers from different disciplines continue to develop it. In this work, we study the language generation problem in a limiting cooperative multi-agent planning setting and hope that our work could shed some light on it. We studied the language generation problem for planning agents from different perspectives. The general idea and framework for language construction based on state abstraction are introduced in work [34].