# Coordination of Multiple Autonomous Agents Using Naturally Generated Languages in Task Planning
## 5 Experiments and Results
### Coordination Example  
A path-planning problem in a grid-world domain involving two agents, \(agent_{b}\) and \(agent_{r}\), is shown in Figure 2. The numbered white cells are reachable for the agents and the black cells are the obstacles. In each step, the agent can move to an adjacent cell or remain where it is. Agents are not allowed to stay in the same cell or move to each other's place at the same step. Given target points, the goal of the agents is to arrive at the points with the least time and energy cost. As mentioned before, we assume that observation and communication are only available during the planning phase.  
Figure 2: Navigation example. A Required Coordination (RC) task is that \(agent_{b}\) moves from point 1 to 3, and \(agent_{r}\) moves from point 9 to 4.  
We apply the algorithm to the environment with different RC tasks. The size of the language and the computation time of the algorithm, along with the increase of the number of RC tasks, are denoted by the blue and red curves in Figure 3, respectively.  
We observe that the number of language words does not always increase as more RC tasks are included, since the generated language could apply to other RC tasks. The language of the environment involving all RC tasks is \(L=\{W_{1},W_{2},W_{3},W_{4},W_{5},W_{6}\}\). The states of each word are shown in Table 1.  
Where state \(S_{x,y}\) indicates that \(agent_{b}\) is at point \(x\) and \(agent_{r}\) is at point \(y\). For a planning instance, the task of \(agent_{b}\) and \(agent_{r}\) is moving from 1 and 9 to 3 and 4. Assume that every time step and movement take a cost of 1, respectively. Thus, there are seven optimal plans for the two agents, which are shown as follows:  
\[\begin{array}{ll}P_{1}:S_{1,9},S_{1,8},S_{4,7},S_{5,6},S_{6,2},S_{7,6},S_{8,5},S_{9,4},S_{3,4};&B_{1}:W_{5}\#W_{2}\\ P_{2}:S_{1,9},S_{4,8},S_{4,7},S_{5,6},S_{6,2},S_{7,6},S_{8,5},S_{9,4},S_{3,4};& B_{2}:W_{5}\#W_{2}\\ P_{3}:S_{1,9},S_{4,8},S_{5,7},S_{5,6},S_{6,2},S_{7,6},S_{8,5},S_{9,4},S_{3,4};&B_{3}: W_{5}\#W_{2}\\ P_{4}:S_{1,9},S_{4,9},S_{5,8},S_{6,7},S_{7,11},S_{8,7},S_{9,6},S_{3,5},S_{3,4};& B_{4}:W_{6}\#W_{3}\\ P_{5}:S_{1,9},S_{4,8},S_{5,8},S_{6,7},S_{7,11},S_{8,7},S_{9,6},S_{3,5},S_{3,4};& B_{5}:W_{6}\#W_{3}\\ P_{6}:S_{1,9},S_{4,8},S_{5,7},S_{6,7},S_{7,11},S_{8,7},S_{9,6},S_{3,5},S_{3,4};& B_{6}:W_{6}\#W_{3}\\ P_{7}:S_{1,9},S_{4,8},S_{5,7},S_{6,11},S_{7,11},S_{8,7},S_{9,6},S_{3,5},S_{3,4};& B_{7}:W_{3}\\ \end{array}\]  
In this case, the agents may choose any plan to follow if they do not communicate. However, they conflict with each other in task execution if an agent chooses anyone from the first three plans and its partner chooses another plan from the last four plans. In other words, RC is present for the task. Based on the language L, we generate the sentences of the seven plans, which are shown following the plans. Sentence \(W_{5}\#W_{2}\) can express agents' preference for plan, which specifies a no RC plan set including \(P_{1}\), \(P_{2}\), and \(P_{3}\). Similarly, sentence \(W_{6}\#W_{3}\) can specify a plan set that includes \(P_{4}\), \(P_{5}\), and \(P_{6}\), and sentence \(W_{3}\) can specify \(P_{4}\), \(P_{5}\), \(P_{6}\), and \(P_{7}\). Thus, the potential conflicts between the agents can be solved by communicating one of the sentences.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**The Words in L** & **The States in W** \\ \hline \(W_{1}\) & \(S_{4,1},S_{7,8}\) \\ \(W_{2}\) & \(S_{4,5},S_{7,6}\) \\ \(W_{3}\) & \(S_{4,10},S_{7,11}\) \\ \(W_{4}\) & \(S_{6,5},S_{9,12}\) \\ \(W_{5}\) & \(S_{6,2},S_{9,3}\) \\ \(W_{6}\) & \(S_{6,7},S_{9,8}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Generated language for the example.  
Figure 3: Language size and algorithm computation time in different task settings.