# CONCERTS: Coverage Competency-Based Target Search for Heterogeneous Robot Teams
## 1 Introduction
(**d**) The next step solves instances of the single agent TSP [14] to provide high-quality candidate paths to the utility function. The utility function selects a direction along the TSP solution to maximize team information gain. complexity analysis. Furthermore, it is shown that CONCERTS is not only resilient to robot failure by re-planning online to re-assign the failed robot's search region, but also flexible to use prior knowledge of target information. Finally, we perform indoor experiments with three heterogeneous robots to validate our algorithm's performance in the real world. Overall, we present CONCERTS (see Algorithm 1 and Figure 1), an algorithm for heterogeneous robot teams capable of efficient target search. Our contributions are summarized as follows:  
* We propose a novel method for sample path generation that uniquely combines H-Clustering for waypoint assignment and TSP for optimal path generation to provide an information-theoretic utility function with high-quality candidates for minimizing search time while maintaining online planning speed. * We propose the metrics _coverage competency_ and _Waypoint Allocation Factor_ (WAF) to capture an agent's coverage ability to distribute regions equitably and improve search time. * We propose a new Heterogeneous Clustering (H-Clustering) algorithm that leverages coverage competency to efficiently assign search regions to each member of the team and validate that it results in an average of 25% reduction in search time. * CONCERTS is robust to team-member failure and re-plans online by monitoring team progress to guarantee the proposed algorithm always provides paths for complete coverage after the mission starts. * We show that our method outperforms a state-of-the-art CPP algorithm [7] by 9% in coverage completion time. In situations without prior target information, CONCERTS is a CPP algorithm if not terminated upon target object detection. * We deploy CONCERTS with a team comprised of two quadrupedal and one mobile robot on the floor of a university building to demonstrate that they can find the target rapidly. This paper is organized as follows. Section 2 discusses related works. In Section 3, we give background formulations. In Section 4, we formally introduce our problem and describe our methods. In Section 5, we present our experiments with discussion and finally Section 6 concludes our work. ```
Input:\(M,\mu,SR\)  Entropy Map, Robot Pose, Coverage Competency Output:\(P^{*}=\{p_{1}^{*},p_{2}^{*},\ldots,p_{N}^{*}\}\) (A set of paths) \(\mathcal{W}\gets ExtractionUnknownRegions()\) \(\mathbb{C}=HeterogenousClustering(\mathcal{W})\) for\(n\gets 1\) to \(N\)do\(\triangleright\) for each cluster \(c_{n}\) in \(\mathbb{C}\) \(r_{n}=TravelingSalesmanProblem(c_{n})\) endfor for\(n\gets 1\) to \(N\)do\(\triangleright\) for each agent \(p_{n}^{*}=SamplingPaths(r_{n})\) for\(k\gets 1\) to \(|p_{n}|\)do\(\triangleright\)\(|\hat{p_{n}}|\): number of candidate paths \(U(p_{n}^{k})=IG(p_{n}^{k})-c(p_{n}^{k})\)\(\triangleright\)\(p_{n}^{k}\): \(k\)-th candidate for \(n\)-th agent, Equation (8) endfor \(p_{n}^{*}=p_{n}^{k}\leftarrow\)\(U(p_{n}^{k})\)\(\triangleright\) Get the best path \(P^{*}(n)=p_{n}^{*}\)\(\triangleright\) Save the best path for \(n\)-th agent endfor return\(P^{*}\)
```  
**Algorithm 1** Multi-Agent Search()