# Coordination of Multiple Autonomous Agents Using Naturally Generated Languages in Task Planning
## 4 Approach
### Algorithm  
The language generation process includes four procedures: finding plan pairs; finding state set; finding state pairs; word generation. _Finding plan pairs_: For each task \(t\), we find the optimal plans by a modified \(A*\) algorithm. The standard \(A*\) algorithm [37] stops to search nodes when the minimum estimate of the cost value of explored nodes is equal to or greater than the value of the goal. The modified \(A*\) algorithm continuesthe search process until the value of nodes is greater than the value of the goal. For any two plans, we put them into plan pairs set \(P_{s}\) if RC is present. _Finding state set_: With \(P_{s}\), we need to find a state set \(S_{m}\) that could specify any plan pair of \(P_{s}\). To make it true, a different state should at least appear in the two plan sequences. Here, we do not intend to find the minimal language, so we only need to get a state set that is approximately the smallest. First, we set state set \(S_{m}\) as void. Then, for each plan pair \((x,y)\) in \(P_{s}\), we remove their common states. For each plan, if no state in its sequence is the element of \(S_{m}\), we add the first state of the plan into \(S_{m}\). Otherwise, we address the next plan pair. _Finding state pairs_: State pairs denote that the two states cannot be abstracted as the same word. First, we set state pairs set \(C_{s}\) as void. For each plan pairs \((x,y)\) in \(P_{s}\), we remove the states that do not appear in \(S_{m}\) and obtain the reduced plan sequences. If the two plan sequences have different lengths, we cut the longer plan into several subsequences, the length of which equals that of the shorter plan. Then, we check to see whether there are two states that are in the same place of plan sequences and appear in \(C_{s}\). If they do not, we add the first state pair into \(C_{s}\). _Word generation_: Under the restriction of the state pairs of \(C_{s}\), a greedy CSP (Constraint Satisfaction Problem) solver is used to assign the states of \(S_{m}\) to several state sets in which any pair of states does not appear in \(C_{s}\). We define each state set as a word, and a language is then constructed. The pseudo-code of the algorithm is presented in Algorithm 1. ```
1:Input: Domain \(M\); Tasks \(\{I,G\}\). 2:Output: Word set \(W\). 3:Initialization: Plan pairs set \(P_{s}\leftarrow\{\}\); State set \(S_{m}\leftarrow\{\}\); Equal sequence pairs set \(E_{s}\); State pairs set \(C_{s}\leftarrow\{\}\); Conflicting state set of words \(F\leftarrow\{\}\); Word set \(W\leftarrow\{\}\). 4:procedureFinding plan pairs
5:for task \(t\in\{I,G\}\)
6: Get optimal plans \(P\) of \(t\)
7: if \(P(i)\) and \(P(j)\) introduce RC then Put \((P(i),P(j))\) in \(P_{s}\)
8:procedureFinding state set
9:for plan pairs \((x,y)\in P_{s}\)
10: Remove common states of plan \(x\) and \(y\)
11:if not all states of \(x\) or \(y\) appear in Sm then Put a state of \(x\) or \(y\) in \(S_{m}\)
12: Get reduced sequence \(R(x)\), \(R(y)\) of \(x\), \(y\)
13:if\(R(x)\) equals \(R(y)\) then Put \((R(x),R(y))\) in \(E_{s}\)
14:elseif\(R(x)\) is longer than \(R(y)\)then
15: Get the subsequence \(SR(x)\) whose length equals \(R(y)\); Put \((SR(x),R(y))\) in \(E_{s}\)
16:procedureFinding state pairs
17:for sequence pairs \((e_{1},e_{2})\in E_{s}\)
18:for each step \(i\in|e_{1}|\)
19:if state pairs \((e_{1}(i),e_{2}(i))\in C_{s}\) then break
20:elseif\(i=|e_{1}|\)then Put \((e_{1}(i),e_{2}(i))\) in \(C_{s}\)
21:procedureWord generation
22:for state \(s\in S_{m}\)
23:for word \(w\in W\)
24:if\(s\) is not a member of \(F(w)\) then Abstract \(s\) as \(w\); Add \(s_{c}\) into \(F(w)\), \((s,s_{c})\in C_{s}\)
25:elseif\(w=W(|W|)\)then Abstract \(s\) as \(w_{n}\), put \(w_{n}\) in \(W\)
```  
**Algorithm 1** Language Generation Process  
Theorem 2: _Given a multi-agent planning domain, the languages generated by the algorithm are optimal and complete._  
Proof of Theorem 2.: For any RC plan pair, \(p_{1}\) and \(p_{2}\), we assume that the two abstracted sentence sequences are \(b_{1}\) and \(b_{2}\), respectively.