## 5 Task Allocation Scheme
### Coordination Method  
In order to take advantage of the individual computing power of the robots, to avoid the single point of failure, and to deal better with the presence of real communication constraints during the exploration, a decentralised approach is followed. Typically, estimation of travelling costs and target benefits, as well as mapping and localisation, are the tasks chosen to be made locally by the robots.  
However, to achieve a cooperative behaviour, both the local map and localisation information must be shared among team members.  
Additionally, the relation between \(|T|\) and \(|R|\) can result in two somewhat different behaviours: (i) If \(|T|<|R|\), not all robots would be needed to reach all targets. Some robots may choose to keep quiet; (ii) When \(|T|\geq|R|\) all robots would be needed in order to reach the maximum amount of targets at a time. When robots decide to explore, the task selection is made coordinately. Robots coordinate their actions implicitly, sharing specific information (such as locations, eventually already-done-selections, and local maps) and running the same selection algorithm. Thus, it is possible for the multi-robot system to compute a coordinated-tasks-to-robots distribution in a decentralised way [15; 17; 44].  
To do so properly, the exchanging information time is carefully set up. The system is fully asynchronous, meaning that: (i) Robots do not wait for others; (ii) After selecting a task, the robots do exchange their selection in order to prevent future overlappings; (iii) Local maps and--by means of this --the sets of new available tasks are periodically exchanged, each time two conditions are met: (1) A waypoint of the planned path is reached; (2) New information has been gathered; (iv) Localisation data is exchanged at a higher rate than maps because its influence on the task selection algorithm is higher too.  
While localisation data is exchanged periodically, the rest of data exchanging is triggered by events instead. These policies make the system more efficient and flexible because: (i) No data is transmitted when there is no new information to exchange; (ii) There is no need to set up any rate parameter when exploring different environments. The robot life-cycle algorithm is sketched in Algorithm 1.  
```
1:functionexplore(i,R,HO-Threshold)
2:\(\triangleright\) i stands for the robot position in vector R.
3:\(\triangleright\) R stands for the robots location vector.
4:\(atT\gets true\)\(\triangleright\) atTarget flag.
5:\(pose\gets R[i]\)\(\triangleright\)
```
6:\(gMap\gets getMap(pose)\)\(\triangleright\) Occupancy Grid map.
7:while true do
8:\(R^{*}\leftarrow\mathcal{Q}\)\(\triangleright\) Vector of connected robot locations.
9:for\(j\in R\wedge j\
eq i\)do
10:if\(\Gamma_{i}(j,gMap)>0\)then\(\triangleright\) Connected robot.
11:\(R^{*}[j]=rcvPose(j)\)\(\triangleright\) Asking for localisation data.
12:\(s\mathit{andPose}(pose,j)\)\(\triangleright\) Sending own localisation data.
13:\(gMap=mapMerge(gMap,rcvMap(j))\)\(\triangleright\) Asking for local maps.
14:endif
15:endfor
16:if\(atT\)then
17:\(T=getFrontierTasks(gMap)\)\(\triangleright\) Tasks location vector.
18:\(task\gets getAssignment(i,R^{*},T,|R|,\text{HO-Threshold})\)
19:\(goto(task)\)
20:endif
21:\(pose=getPose()\)\(\triangleright\) Global localisation.
22:\(atT\leftarrow pose=task\)
23:\([gMap,ni]=mapMerge(gMap,getMap(pose))\)\(\triangleright\) Mapping.
24:if\(atT\lor ni\)then\(\triangleright\)\(R_{i}\) arrives at task or new information was gathered.
25:for\(j\in R^{*}\wedge j\
eq i\)do
26:\(s\mathit{ndMap}(gMap,j)\)\(\triangleright\) Sending local map.
27:endfor
28:endif
29:endwhile
30:endfunction ```
**Algorithm 1** Robotic Agent Life-cycle algorithm.