Autonomous Detection and Coverage of Unknown Target Areas by Multi-Agent Systems

1. Problem Statement

The paper addresses the challenge of multi-agent coverage control in unknown environments. Unlike traditional coverage problems where agents are provided with prior knowledge of the target area's shape, location, and boundaries, this scenario assumes agents have zero prior information.

• Key Challenges:
  • Unknown Target Distribution: Agents must explore to discover target regions.
  • Multiple Disconnected Targets: Existing algorithms often struggle with multiple, spatially separated, or irregularly shaped target areas.
  • Safety Constraints: Agents must avoid collisions and prevent sensor overlap while covering the area.
  • Local Minima: Heuristic methods (like Artificial Potential Fields) often get trapped in local minima, failing to achieve global optimality.

2. Methodology

The authors propose a novel control framework that integrates Centroidal Voronoi Tessellation (CVT) with a dynamically constructed density function and Control Barrier Functions (CBFs). The system operates under a centralized control architecture.

A. Dynamic Density Function Construction

To guide agents toward unknown targets without a pre-defined map, the paper introduces a time-varying density function, $\phi(q, t)$, defined as:
$$\phi(q, t) = \phi_0 + \sum_{i=1}^{N} \rho_i(t) \cdot \mathcal{G}(q; \mu_i, \sigma_i)$$

• $\phi_0$: A small positive constant ensuring the density is strictly positive everywhere.
• $\rho_i(t)$: A binary switching variable (0 or 1). It becomes 1 only when agent $i$ detects a target area within its sensor range.
• $\mathcal{G}$: A Gaussian component centered at the detecting agent's position ($\mu_i$).
• Mechanism: When an agent detects a target, it "activates" a Gaussian peak in the density function. As more agents detect the same or different targets, these peaks superimpose, creating a multimodal density landscape that attracts other agents to the discovered regions.

B. Coverage Optimization via CVT

The agents aim to minimize a locational cost function $H(p, t)$, which represents the weighted distance between agents and points in their Voronoi cells:
$$H(p, t) = \sum_{i=1}^{N} \int_{V_i} \|q - p_i\|^2 \phi(q, t) \, dq$$

• Voronoi Partitioning: The domain is divided into Voronoi cells $V_i$ based on agent positions.
• Centroidal Convergence: Agents move toward the centroid ($c_i$) of their respective Voronoi cells calculated with respect to the current density function. This ensures an optimal spatial distribution where agents are evenly spread across the detected high-density (target) regions.

C. Safety via Control Barrier Functions (CBF)

To ensure collision avoidance and non-overlapping sensor coverage, the nominal CVT control input is modified using a Quadratic Program (QP) constrained by CBFs.

• Safety Set: Defined by a minimum safety distance $d_{min}$ between any pair of agents.
• QP Formulation: At each time step, the controller solves for the control input $u_i$ that minimizes the deviation from the nominal CVT input while satisfying the safety constraint:
  $$\dot{h}_{ij}(t) + \gamma h_{ij}(t) \geq 0$$
  where $h_{ij}$ is the barrier function related to the distance between agents $i$ and $j$.

3. Key Contributions

1. Autonomous Detection without Prior Knowledge: The method enables agents to discover, identify, and cover target areas solely based on local sensor data, eliminating the need for pre-mapped environments.
2. Handling Multiple Disconnected Targets: Unlike methods designed for single continuous regions, this approach naturally handles multiple, scattered, and irregularly shaped targets by dynamically updating the density function as new targets are found.
3. Size-Aware Distribution: The density function implicitly encodes the "importance" or size of a target. Larger targets generate more overlapping Gaussian peaks, naturally attracting a proportionally larger number of agents without explicit size estimation.
4. Formal Safety Guarantees: The integration of CBFs provides mathematical guarantees for collision avoidance and maintains safe inter-agent distances throughout the exploration and coverage phases.

4. Simulation Results

The authors validated the algorithm using Python simulations with varying configurations:

• Scenario 1 (2 Targets, 10 Agents): Agents started in a grid. Upon detecting two separate square targets, they dispersed, formed density peaks, and converged to cover both areas evenly. The minimum inter-agent distance remained above the safety threshold ($d_{min} = 0.64$ m).
• Scenario 2 (3 Targets, 15 Agents): The system scaled to three targets. Agents self-organized into three distinct groups, covering all targets efficiently without clustering or oscillation.
• Scenario 3 (Heterogeneous Targets, 15 Agents): Three targets of different sizes were used. The algorithm successfully distributed agents proportionally to the target sizes (e.g., the largest target attracted 6 agents, the smallest 4), demonstrating size-awareness without explicit geometric knowledge.
• Performance Metrics:
  • Collision Avoidance: The minimum pairwise distance consistently stayed above the safety threshold defined by the CBF.
  • Convergence: Trajectories were smooth, showing coordinated convergence without redundant clustering.

5. Significance and Limitations

Significance:

• The proposed method bridges the gap between theoretical coverage control and real-world applications where environment maps are unavailable (e.g., disaster response, search and rescue).
• It offers a robust solution for multi-target scenarios, which are common in complex environments but difficult for traditional single-region algorithms.
• The combination of CVT (for optimality) and CBF (for safety) creates a control law that is both efficient and safe.

Limitations & Future Work:

• Centralized Dependency: The current approach relies on a centralized controller to compute the global density function and Voronoi partitions. This limits scalability in very large-scale systems and introduces a single point of failure.
• Robustness to Agent Failure: If an agent fails or drops out, the centralized assignment may be disrupted, potentially leaving parts of the target area uncovered.
• Future Direction: The authors plan to develop a decentralized version of the algorithm to improve scalability and robustness for real-world deployment in cooperative transportation and environmental monitoring.