# Coordination of Multiple Autonomous Agents Using Naturally Generated Languages in Task Planning
## 3 Problem Formulation
### Language Construction  
**Definition 1**. : _(Required Coordination, RC): For a multi-agent planning problem, RC is present in a situation when there are several feasible plans that incur a conflict._  
For example, two agents, \(agent_{1}\) and \(agent_{2}\), are assigned to do a task for which there are only two optimal plans, \(p_{A}\) and \(p_{B}\). Without communication, \(agent_{1}\) may act following plan \(p_{A}\), while \(agent_{2}\) acts according to plan \(p_{B}\). As a result, they execute the task sub-optimally or in failure. **Definition 2**. : _(Language): Given the state set \(S\) of a multi-agent planning domain \(M\), where \(s\in S\) is the joint state of agents, a language for the domain is a tuple \(L=(W,R)\), where \(W\) represents a set of words, and \(R\) is the concatenation operator, denoted as \"#\", which can be used to combine words. Each word \(w\in W\) denotes an abstraction of joint states and is a subset of \(S\)._A sentence is defined as a sequence of words combined by operators. In this paper, we only consider the concatenation operator, so the sentence including \(n\) words has the following form:  
\[Word_{1}\#Word_{2}\#...\#Word_{n}\]  
For planning agents, to avoid potential conflicts or improve team performance, the sentence as a communicative message is considered to be a constraint on agents' actions. Since agents are rational, the receiver agents choose an optimal plan that is consistent with the communicated sentence. Please note that in this work, plans specified by a sentence refer to the optimal plans which satisfy the constraint of the sentence, and we mean a joint optimal plan when mentioning a plan. We give an intuitive example to explain the language defined above. For a multi-agent task instance \((S_{i},S_{g})\), there are three optimal plans, shown as follows:  
\[P_{1}:S_{i},S_{11},S_{12},S_{13},S_{14},S_{g}\] \[P_{2}:S_{i},S_{21},S_{22},S_{23},S_{24},S_{g}\] \[P_{3}:S_{i},S_{31},S_{32},S_{33},S_{34},S_{g}\]  
where there is RC between \(P_{1}\) and \(P_{2}\) or \(P_{3}\), and no RC between \(P_{2}\) and \(P_{3}\). One of the valid languages is \(L=\{W_{1}=(S_{14},S_{22},S_{31}),W_{2}=(S_{11},S_{23},S_{33})\}\). For instance, sentence \(W_{2}\#W_{1}\) means that agents must be in a grounding state of \(W_{2}\) at some moment and be in a grounding state of \(W_{1}\) at a later moment in task execution. Thus, the state sequence of plans specified by \(W_{2}\#W_{1}\) has the following form:  
\[S_{i},...,S_{11}\text{ or }S_{23}\text{ or }S_{33},...,S_{14}\text{ or }S_{22}\text{ or }S_{31},...,S_{g}\]  
Symbol \"...\" denotes an omitted state sequence that can be void. Here, only \(P_{1}\) is consistent with the state sequence, i.e., \(W_{2}\#W_{1}\) can specify \(P_{1}\). Similarly, sentence \(W_{1}\#W_{2}\) can specify a plan set including \(P_{2}\) and \(P_{3}\). Definition 3: (Language Generation Problem, LGP): Given a multi-agent planning model \(M\), we must find a language \(L\) that can be used to resolve the RC for any given task. Definition 4: (Sentence Generation Problem, SGP): Given a multi-agent planning model \(M\), a language \(L\), and a task, we must find a sentence that can specify a plan set without RC. Specifically, the LGP is about how to construct a language, and the SGP is about how to use the language to remove RC. As shown in Figure 1, words are constructed based on the states and tasks of the environment where agents act. This optimization process is operated offline. After that, given the words and tasks, sentences are generated online by agents to communicate with their teammates. Figure 1: Problem formulation diagram. Blue segments: language generation process; Red segments: sentence generation process. Next, we look at a few language properties that may be required. _Optimality_: A language is optimal if plans specified by it are also optimal. _Completeness_: A language is complete if it can specify a plan set that includes any plan. _Minimality_: A language is minimal if the number of words is the smallest.