# CONCERTS: Coverage Competency-Based Target Search for Heterogeneous Robot Teams
## 1 Introduction  
This article tackles the problem of path planning and execution of multi-robot search for a static target in urban and indoor environments with teams of heterogeneous robots. In particular, the problem of an efficient search for a static target has a variety of applications related to exploration and Coverage Path Planning (CPP). Search, exploration, and CPP have received attention from the robotics community for a long time to equip robots with the skills to quickly generate high-quality path plans for several tasks requiring the robot's field of view inspect a region or a portion of a region. These skills are critical to a variety of important real-world tasks including map building [1; 2; 3; 4], cleaning/covering indoor areas [5; 6], security, surveillance and information gathering [7; 8; 9; 10], and reconnaissance or search and rescue [11; 12; 13]. In traditional CPP, a robot or a team of robots must find the optimal paths such that the sensor footprint, or Field of View (FoV), passes over the entire region or search polygon. A common strategy for CPP and exploration is to find informative next viewpoints or paths using sampling-based approaches to discover unseen regions of the map within some defined search polygon. Static target search is a variation on Coverage Path Planning(CPP) or Exploration, depending on map knowledge, in which the searching agent(s) must additionally detect some predefined target. This manuscript relates closely to the former, where static map information is known a priori. Prior information about the target may also be given. In situations without prior knowledge of the target (i.e., the target prior is a uniform distribution over the search region), we posit that search for a static target and CPP are similar. The team must generate plans optimally to have the FoV, or sensor footprint, cover the entire region of interest. This is the baseline scenario for our simulation and hardware experiments, wherein the target prediction model is uniform over unseen space. In other scenarios, the team may be provided with prior information, for example to search near buildings first in a Search and Rescue (SAR) mission while attempting to help injured people or to leverage the most recent sensor data from a missing team member to determine where on the map they may be lost. The purpose of this manuscript is to further improve coverage and search speed for situations when the mission completion time is critical, for example SAR or surveillance. We propose an algorithm for generating efficient paths for heterogeneous robot teams, which attempts to maximize the utility of each team member to complete the search in minimum time. An overview of the path-generation algorithm is given by Figure 1.  
By uniquely combining an H-Clustering step with a TSP step, CONCERTS generates high-quality sample paths for the information-theoretic utility function. We propose a measure of heterogeneity, or _coverage competency_, which is a score based on the individual robot's FoV size and movement speed. The H-Clustering step takes advantage of coverage competency and distributes waypoints to each robot to ensure they are assigned a search region that represents their coverage skill with respect to their teammates. We also provide a new metric, Waypoint Allocation Factor (WAF), to measure how evenly waypoints are divided among agents based on their coverage competency score. We demonstrate our algorithm has linear complexity with respect to the number of teammates and provide a  
Figure 1: Four steps to generate a path for each agent. (**a**) Given a static map, a search region can be defined using a set of boundary points. (**b**) CONCERTS uses cell decomposition to generate a set of waypoints, which, if visited, provide full sensor coverage over the high entropy regions. (**c**) We perform a weighted clustering over all waypoints and assign sub-regions (clusters) to each agent based on their coverage competency.