In critical missions such as search and rescue (SAR), industrial inspection, and environmental monitoring, Unmanned Aerial Vehicles (UAVs), particularly multi-rotor drones, are increasingly pivotal due to their agility, flexibility, and ability to cover large areas rapidly. However, autonomously searching for specific targets within vast, complex, and initially unknown environments presents a significant challenge. This task necessitates a delicate balance between two competing objectives: the exploration of the unmapped space to discover potential target locations, and the exploitation or detailed inspection of areas likely to contain targets. Traditional frontier-based exploration algorithms excel at complete coverage but are often slow and not optimized for terminating the mission once targets are found. Conversely, pure search strategies may lack the systematic coverage needed in completely unknown terrains. This paper addresses this gap by proposing a novel, distributed framework for rapid, cooperative target search using a swarm of UAV drones.
The core of our approach lies in a synergistic integration of efficient area coverage and active target detection. We employ a distributed strategy where UAV drones coordinate through pairwise interactions to dynamically allocate unexplored regions, ensuring non-overlapping coverage and load balancing. A key innovation is a dual-mode search policy that allows each UAV drone to intelligently switch between a cautious search mode for probing unknown volumes and a fast search mode for quickly scanning known safe spaces. This dynamic adjustment optimizes the trade-off between thoroughness and speed. Furthermore, we develop a modular target perception module that fuses data from LiDAR and depth cameras, leveraging the long-range, geometry-aware sensing of LiDAR with the high-fidelity visual recognition capabilities of depth cameras to reliably identify and localize targets. The overall system enables a swarm of UAV drones to autonomously and efficiently locate targets in large-scale unknown environments without requiring a prior map or centralized control.
1. Problem Formulation and System Overview
We consider the problem of deploying a team of \( N \) UAV drones to locate a known number of static targets within a bounded but initially unknown 3D environment \( \mathcal{W} \subset \mathbb{R}^3 \). The environment contains obstacles, and the targets are arbitrarily placed. Each UAV drone \( U_i \) is equipped with a proprioceptive sensor suite (IMU) for state estimation, a LiDAR for long-range geometric mapping, and a depth camera (e.g., RGB-D) for close-range target detection and recognition. The drones operate under communication constraints, relying on limited-range peer-to-peer links for coordination.
The objective is to minimize the total mission time \( T_{mission} \) until all \( K \) targets are found and localized with sufficient accuracy. The mission is considered successful if all targets are detected and their estimated positions are within a threshold distance \( \delta \) of their true positions before a timeout \( T_{max} \). The problem involves several coupled sub-problems: (1) Distributed Task Allocation: Dynamically partitioning the unexplored space among the UAV drones to avoid redundant work. (2) Online Path and Viewpoint Planning: Generating safe, dynamically feasible trajectories that maximize the efficiency of both exploration and target search. (3) Multi-Sensor Target Detection: Fusing LiDAR and camera data to reliably identify targets amidst clutter.
Our proposed system architecture is fully distributed. Each UAV drone maintains a local volumetric map (e.g., an OctoMap or ESDF) built from fused LiDAR and depth camera data. A high-level coordinator manages mode switching between cautious and fast search based on the local map’s uncertainty. A task allocator uses a hierarchical grid (HGrid) decomposition and pairwise negotiations to assign exploration frontiers. A trajectory optimizer plans smooth, collision-free paths to a sequence of informative viewpoints. The target detection module runs concurrently, processing camera images to identify targets and registering their 3D position using the fused map. This integrated approach allows the swarm of UAV drones to collaboratively and efficiently solve the target search problem.
2. Distributed Task Allocation via Pairwise Negotiation
Effective collaboration in a swarm of UAV drones requires intelligent partitioning of the search space. Centralized allocators create a single point of failure and require robust, long-range communication. We adopt a distributed method based on pairwise negotiations, inspired by and extending frontier-sharing concepts. This method scales well and is robust to intermittent communication failures.
2.1 HGrid-Based Spatial Decomposition
Each UAV drone maintains a hierarchical grid (HGrid) representation of the global environment in a shared coordinate frame, established through decentralized state estimation. The HGrid decomposes space into cells at multiple resolutions. Let \( \mathcal{S}_l \) represent the set of cells at level \( l \), with \( l=1 \) being the coarsest and \( l=L \) the finest. A cell \( C_{l}^{(i,j,k)} \) at level \( l \) with integer coordinates \((i, j, k)\) can be subdivided into \( m \) child cells at level \( l+1 \).
Each cell stores two key properties: (1) the count of unknown voxels \( u(C) \) within its volume, and (2) the centroid \( \mathbf{p}_c(C) \) of these unknown voxels. The UAV drone’s known space, updated from its sensor data, allows it to classify cells as Free, Occupied, or Unknown. The allocator works on a dynamically maintained list of assignable cells—those that are predominantly unknown and whose centroid is reachable (i.e., not inside an obstacle and within a navigable distance). Cells become assignable when their unknown ratio \( \rho_{unk}(C) = u(C) / V_{total}(C) \) is above a threshold \( \theta_{assign} \). Conversely, a cell is removed from the list if it becomes fully known (\( \rho_{unk} \approx 0 \)) or if its centroid is deemed unreachable.
2.2 Pairwise Negotiation and CVRP Formulation
Each UAV drone \( U_i \) maintains a personal task queue \( \mathcal{Q}_i \), a list of assignable cells it has committed to explore. To distribute the workload, drones periodically attempt to negotiate with a nearby neighbor \( U_j \). The goal of a negotiation between \( U_i \) and \( U_j \) is to find a better partition of their combined task sets \( \mathcal{Q}_i \cup \mathcal{Q}_j \) to minimize the estimated combined coverage path length.
This problem is formulated as a Capacitated Vehicle Routing Problem (CVRP) with two vehicles (drones). Let the combined set of \( M \) assignable cells be the “customers.” Each cell \( C_m \) has a demand \( d_m = u(C_m) \) (its unknown voxel count). The two drones, modeled as vehicles, have a starting depot at their current positions, \( \mathbf{p}_i \) and \( \mathbf{p}_j \). The capacity \( Q \) of each vehicle is set as a fraction \( \alpha \) of the total unknown voxels in the combined set: \( Q = \alpha \cdot \sum_{m=1}^{M} d_m \). This capacity constraint ensures workload balancing, preventing one UAV drone from receiving a disproportionate number of high-demand cells.
The cost \( c_{a,b} \) of traveling from location \( a \) to \( b \) is the length of the shortest collision-free path between them, estimated using a sparse graph built from the known map. The cost from a drone’s position to a cell is the path length to the cell’s centroid. The objective is to find two routes \( R_i \) and \( R_j \), starting at \( \mathbf{p}_i \) and \( \mathbf{p}_j \) respectively, covering all cells exactly once, respecting capacity constraints, and minimizing the total cost:
$$ \text{Minimize: } \sum_{r \in \{R_i, R_j\}} \left( c_{start(r), first(r)} + \sum_{consecutive\ (a,b)\ in\ r} c_{a,b} \right) $$
We solve this CVRP instance efficiently using the LKH heuristic solver. The output is two new sets of cells \( \mathcal{Q}’_i \) and \( \mathcal{Q}’_j \). The drones exchange these proposed sets. If both agree, they update their task queues. This pairwise negotiation is inherently local and requires minimal data exchange—only the list of cell centroids and demands—making it suitable for bandwidth-limited networks common in UAV drone swarms.
The negotiation process continually optimizes the global allocation. Over time, as UAV drones explore and update the map, cells are refined, removed, or added. The pairwise interactions ensure that the allocation adapts to these changes and that the swarm collectively covers the most promising unknown regions without overlap.
| Strategy | Communication Overhead | Scalability | Robustness to Link Failure | Load Balancing |
|---|---|---|---|---|
| Centralized | High (O(NM)) | Poor | Low (Single Point of Failure) | Good (Global Optimum) |
| Market-Based | Medium | Good | Medium | Good |
| Pairwise Negotiation (Ours) | Low (O(M)) | Excellent | High | Good (with CVRP) |
3. Dual-Mode Search and Trajectory Optimization
The search behavior of each UAV drone is governed by a dual-mode policy that dynamically adjusts the trade-off between exploratory coverage and efficient traversal. This is critical for minimizing mission time, as different phases of the search benefit from different flight regimes.
3.1 Cautious vs. Fast Search Mode
Each UAV drone operates in one of two modes, selected autonomously based on its immediate perceptual context:
- Cautious Search Mode: Activated when the UAV drone is assigned to explore a cell with a high ratio of unknown space (\( \rho_{unk} > \theta_{cautious} \)) or when flying near unknown frontiers. In this mode, the primary goal is safe exploration and detailed inspection. The maximum velocity \( v_{max} \) is limited to a lower value \( v_{safe} \) to ensure sufficient sensor data overlap (for dense mapping) and reaction time for obstacle avoidance. The planning horizon is shorter, and the drone prioritizes visiting carefully selected viewpoints that maximize information gain about the unknown volume, which also facilitates target detection.
- Fast Search Mode: Activated when the UAV drone is traversing through already-mapped, safe space (e.g., large free volumes) or servicing small, isolated unknown cells. Here, the goal is to quickly reposition or cover low-uncertainty areas. The velocity limit is raised to \( v_{fast} > v_{safe} \). Path planning in this mode prioritizes shortest-time trajectories, accepting less detailed perceptual coverage.
The mode switch is governed by a simple rule based on the local map. Let \( \mathcal{F}_{unk} \) be the set of unknown voxels within the depth camera’s field of view at the next planning step. If \( |\mathcal{F}_{unk}| > \gamma \), the drone switches to or remains in Cautious Mode. Otherwise, it operates in Fast Mode. This allows the swarm of UAV drones to rapidly deploy to new areas while still performing meticulous search where it matters most.
3.2 Viewpoint Selection and Trajectory Generation
In Cautious Mode, the UAV drone must select the next best viewpoint (NBV) from its allocated cells. For each assignable cell \( C \), we sample candidate viewpoints \( \mathbf{v} = (\mathbf{p}_v, \mathbf{q}_v) \) around its unknown centroid. The utility \( U(\mathbf{v}) \) of a viewpoint is a weighted sum of information gain \( I(\mathbf{v}) \) (estimated new volume observed) and a motion cost \( M(\mathbf{v}, \mathbf{v}_{current}) \):
$$ U(\mathbf{v}) = \omega_I \cdot I(\mathbf{v}) – \omega_M \cdot M(\mathbf{v}, \mathbf{v}_{current}) $$
The information gain \( I(\mathbf{v}) \) is approximated by raycasting from \( \mathbf{v} \) into the unknown voxels of cell \( C \) using the sensor model. The motion cost \( M \) is the estimated time to reach \( \mathbf{v} \) from the current state. The viewpoint with the highest utility is selected.
Given a sequence of target viewpoints (from the CVRP route and NBV selection), the trajectory planner generates a smooth, collision-free, and dynamically feasible path. We represent the trajectory as a uniform B-spline curve \( \mathbf{s}(t) \) of degree \( p_b \), defined by control points \( \{\mathbf{P}_0, \mathbf{P}_1, …, \mathbf{P}_N\} \) and a fixed time knot interval \( \Delta t \). A B-spline’s convex hull property and derivative continuity make it suitable for enforcing dynamic constraints and safety.
Dynamic Feasibility: The velocity \( \mathbf{V}_i \) and acceleration \( \mathbf{A}_i \) control points can be derived from the position control points:
$$ \mathbf{V}_i = \frac{\mathbf{P}_{i+1} – \mathbf{P}_i}{\Delta t}, \quad \mathbf{A}_i = \frac{\mathbf{V}_{i+1} – \mathbf{V}_i}{\Delta t} $$
We constrain \( \lVert \mathbf{V}_i \rVert_2 \leq v_{max}^{mode} \) and \( \lVert \mathbf{A}_i \rVert_2 \leq a_{max} \), where \( v_{max}^{mode} \) is \( v_{safe} \) or \( v_{fast} \) depending on the active mode.
Safety (Collision Avoidance): To ensure the entire spline segment between \( \mathbf{P}_i \) and \( \mathbf{P}_{i+3} \) (for cubic splines) is collision-free, it is sufficient to enforce that the distance between any control point \( \mathbf{P}_j \) and any obstacle is greater than a safety margin \( d_{safe} \). This is checked efficiently against the Euclidean Signed Distance Field (ESDF) \( \Phi(\mathbf{p}) \) built from the LiDAR map:
$$ \Phi(\mathbf{P}_j) > d_{safe}, \quad \forall j $$
The overall trajectory optimization problem is formulated as a minimization of control point displacements subject to these feasibility and safety constraints, often solved using gradient-based methods.
4. Multi-Sensor Target Detection and Localization
Accurate and reliable target detection is paramount. Relying on a single sensor is insufficient; cameras suffer in low-light or featureless regions, while LiDAR lacks semantic recognition. Our modular target search module fuses both, running asynchronously on each UAV drone.
LiDAR for Mapping and Geometry: The LiDAR point cloud is used to incrementally build a global 3D volumetric map (OctoMap) and its associated ESDF. This provides the geometric foundation for navigation and also defines “observable space.” When a potential target is detected visually, its hypothesized 3D position can be verified against this map—e.g., a detection floating in mid-air (where the map is free) is invalidated, reducing false positives.
Depth Camera for Detection and Identification: We assume targets are marked with fiducial markers (like AprilTags) or have a known visual signature. The RGB image from the depth camera is continuously processed using computer vision algorithms (e.g., contour detection, template matching, or a neural network) to identify potential target regions. For each detection, the corresponding depth pixel from the aligned depth image provides a 3D point \( \mathbf{p}_{cam} \) in the camera frame.
Sensor Fusion for Localization: The detected 3D point is transformed into the world frame using the UAV drone’s estimated pose \( \mathbf{T}_{world}^{cam} \):
$$ \mathbf{p}_{world} = \mathbf{T}_{world}^{cam} \cdot \mathbf{p}_{cam} $$
This world-frame coordinate is then cross-referenced with the LiDAR map. If \( \mathbf{p}_{world} \) lies within a known-free region (according to the OctoMap) and is not occluded by any known obstacle (checked via raycasting), the detection is confirmed. The position is then refined by fusing multiple observations from different UAV drones or viewpoints using a simple averaging or filtering scheme. This fusion significantly increases detection reliability compared to using either sensor alone, which is crucial for the autonomous decision-making of the UAV drone swarm.
| Sensor | Strength | Weakness | Role in Fusion |
|---|---|---|---|
| LiDAR | Accurate 3D geometry, long range, works in darkness. | No color/texture, poor at object identification. | Provides precise map for navigation, geometric verification of visual detections, defines searchable volume. |
| Depth Camera (RGB-D) | Rich visual texture for identification, provides dense depth. | Limited range, sensitive to lighting, narrow Field of View. | Identifies and initially localizes targets. Depth data aids in early fusion. |
| Fused Output | High-confidence target localization: Visual detections are geometrically validated. Reduced false positives/negatives. Enables semantic search in accurate geometric context. | ||
5. Experimental Evaluation and Results
We evaluated our proposed system extensively in simulation using a high-fidelity dynamic simulator (AirSim/Gazebo with ROS). The environment was a complex, cluttered area measuring 300m x 300m, featuring buildings, trees, and uneven terrain, with 5 target objects randomly placed. We tested with a swarm of \( N = \{2, 3, 4\} \) UAV drones.
5.1 Comparative Algorithms
We compared our complete system (labeled Ours-Dual) against three state-of-the-art baselines adapted for the target search task:
1. Frontier-Based Exploration (FB): A classic greedy frontier exploration algorithm where each UAV drone goes to the nearest frontier.
2. RACER: A state-of-the-art distributed multi-UAV exploration algorithm using HGrid and pairwise interaction, modified to stop upon target discovery.
3. Ours-Cautious: An ablation of our system using only the Cautious Search Mode (\( v_{max} = v_{safe} \)).
All baselines were integrated with the same multi-sensor target detection module for a fair comparison.
5.2 Performance Metrics
We measured: (1) Mission Time (s): Time taken to find all \( K \) targets. (2) Total Path Length (m): Sum of distances traveled by all UAV drones. (3) Success Rate: Percentage of trials where all targets were found within \( T_{max} \). (4) Average CPU Load: Per UAV drone computational usage, indicating scalability.
5.3 Results and Analysis
| Algorithm | Mission Time (s) | Total Path Length (m) | Success Rate | Avg. CPU Load (%) |
|---|---|---|---|---|
| Frontier-Based (FB) | 575.7 ± 160.7 | 955.6 ± 196.4 | 100% | ~65 |
| RACER | 193.2 ± 22.5 | 1576.4 ± 64.8 | 100% | ~72 |
| Ours-Cautious | 164.2 ± 36.9 | 1428.0 ± 120.8 | 100% | ~75 |
| Ours-Dual (Proposed) | 126.6 ± 57.6 | 1354.4 ± 77.2 | 100% | ~78 |
The results clearly demonstrate the superiority of our proposed framework. Ours-Dual achieved the shortest average mission time, reducing it by approximately 34.5% compared to RACER and 78% compared to basic frontier exploration. The success rate was 100% for all advanced algorithms, confirming the reliability of the underlying target detection module. While our algorithm had a slightly higher CPU load due to the mode switching logic and CVRP solving, the difference was marginal and did not affect real-time performance.
The key insights are:
1. Dual-Mode Efficacy: Comparing Ours-Dual with Ours-Cautious shows a significant time reduction (~23%), proving that the fast search mode effectively minimizes transit time in known spaces without compromising target discovery.
2. Efficient Allocation: Both our method and RACER outperformed the naive frontier approach dramatically, highlighting the importance of coordinated task allocation among UAV drones to prevent overlapping coverage.
3. Path Efficiency: Our method achieved a lower total path length than RACER for the same mission, indicating that our CVRP formulation with capacity constraints leads to more balanced and efficient routes for the UAV drone team.
Scalability tests with increasing numbers of UAV drones showed a near-linear decrease in mission time for our approach, confirming its distributed nature avoids central bottlenecks. The system was also tested successfully in a larger 500m x 500m environment, with mission time scaling sub-linearly due to the effective parallelization of search effort by the cooperating UAV drones.
6. Conclusion and Future Work
This paper presented a comprehensive, distributed framework for autonomous target search using a swarm of UAV drones in unknown, complex environments. The core contributions are threefold: (1) a distributed task allocation mechanism using HGrid decomposition and pairwise CVRP-based negotiation that efficiently partitions the search space among UAV drones; (2) a novel dual-mode search policy that dynamically switches between cautious and fast flight regimes, optimally balancing thorough inspection with rapid coverage; and (3) a robust, integrable target detection module that fuses LiDAR and depth camera data to reliably identify and localize targets.
Extensive simulation experiments demonstrated that our system enables a team of UAV drones to complete search missions significantly faster than state-of-the-art exploration and search methods while maintaining a 100% success rate. The framework is decentralized, scalable, and robust to realistic communication constraints, making it suitable for real-world applications like search and rescue, where time is critical and infrastructure is limited.
Future work will focus on several extensions. First, we plan to incorporate more advanced semantic understanding and probabilistic target existence maps to guide the search more intelligently, rather than treating all unknown space equally. Second, we will investigate heterogeneous swarms with different UAV drone capabilities (e.g., varying sensor suites). Third, extending the system to handle dynamic targets and moving obstacles is a crucial next step. Finally, rigorous real-world flight tests in challenging outdoor environments are necessary to validate the simulation results and refine the system’s robustness against wind, GPS-denied operation, and harsh sensor noise. The pursuit of fully autonomous, collaborative UAV drone systems for critical missions remains a vibrant and essential field of research.