# CONCERTS: Coverage Competency-Based Target Search for Heterogeneous Robot Teams
## 2 Related Works  
For decades, CPP has received great attention for its relevance in navigation tasks. Early solutions offered an offline planner given a static map. A traditional method is to decompose the coverage region into cells using Boustrophedon decomposition [15]. We employ a similar cell decomposition to generate the set of waypoints for complete coverage. A common strategy in this form of the problem is to break down the map and perform simple back-and-forth behaviors. One alternative to such behavior is to generate the set of points to visit and solve a Traveling Salesman Problem (TSP) for optimal visitation order [6; 11]. Ref. [16] instead finds the optimal order of visitation using mixed-integer linear programming. There are also several geometric approaches [5; 17], which typically give global guarantees with respect to distance traveled during execution. However, such methods often make assumptions about perfect omni-directional sensing. Traditional methods for path planning are insufficient, however, when the goal is to operate in an online fashion to handle robot failure or dynamic environments. Sampling-based approaches are popular in mapping and exploration [2; 3; 4; 9; 18]. Such methods account for sensor noise and environment complexity. Early work used frontiers [19] to explore spaces. Frontiers are the boundaries between explored and unexplored regions of the search polygon. The critical factor in information-theoretic-based strategies [20; 21] is how to generate subsequent observation paths; i.e., how to provide quality candidates to the utility function. Early work [2] uses a laser range scanner to map a previously unknown small environment. In [3; 4], the authors leverage a utility function based on Cauchy-Schwartz quadratic mutual information to more efficiently generate plans to map 3D spaces. Ref. [9] proposes three planning structures for information-gathering missions such as signal monitoring. Ref. [18] focuses on mission speed with MAVs by taking a hybrid approach to frontier and sampling-based exploration strategies. Ref. [7] addresses the problem of scalable CPP by efficiently generating path plans with up to 150 agents in non-convex areas. The authors propose the robot team conducts auction and conflict resolution steps to determine the region of space they will cover. We benchmark our method against this path planner, which is state of the art in terms of coverage completion time. Our method features agent autonomy for search execution, a target prediction model, and automatic re-planning; however, when the target is static, the path-planning algorithm is equivalently a CPP problem, and therefore we use [7] as a state-of-the-art comparison in terms of mission completion time (see Table 1). There is an abundance of real-time algorithms for multi-robot teams in coverage and exploration tasks. Studies have emphasized resilience to robot failure [22; 23; 24], management of energy [25; 26; 27] or communications [28; 29; 30] constraints, and heterogeneous teaming [20; 31]. Ref. [26] also considers an information-gathering mission; however, their future work indicates increasing to \(n\) agents. Ref. [27] performs search and exploration with UAVs, which are limited in both communication and battery life. They use a state machine to help team members decide between exploring, meeting, sacrificing and relaying. They leverage a frontier-based method. In [28], they consider a model of communication strength between the agents and a central control strategy, and cleverly use a serial connection of the robots to maximize their exploration area. Instead of constraining the team to constant connectivity, [30] proposes a method of periodic communications at fixed intervals to update the full team. In [13], an algorithm for solving Multi-robot Efficient Search Path Planning (MESPP) for finding a non-adversarial moving target is proposed. This method provides theoretical bounds on search performance. However, it only scales up to five agents and does not provide resilience to robot failure.