SOAR: Simultaneous Exploration and Photographing with Heterogeneous UAVs for Fast Autonomous Reconstruction
Mingjie Zhang Chen Feng Zengzhi Li Guiyong Zheng Yiming Luo Zhu Wang Jinni Zhou Shaojie Shen Boyu Zhou

*
    Michiel Rollier, Aisling J. Daly, Jan M. Baetens
    Received 2024; accepted 2024
====================================================




§ ABSTRACT 
Unmanned Aerial Vehicles (UAVs) have gained significant popularity in scene reconstruction. This paper presents SOAR, a LiDAR-Visual heterogeneous multi-UAV system specifically designed for fast autonomous reconstruction of complex environments. Our system comprises a LiDAR-equipped explorer with a large field-of-view (FoV), alongside photographers equipped with cameras. To ensure rapid acquisition of the scene's surface geometry, we employ a surface frontier-based exploration strategy for the explorer. As the surface is progressively explored, we identify the uncovered areas and generate viewpoints incrementally. These viewpoints are then assigned to photographers through solving a Consistent Multiple Depot Multiple Traveling Salesman Problem (Consistent-MDMTSP), which optimizes scanning efficiency while ensuring task consistency. Finally, photographers utilize the assigned viewpoints to determine optimal coverage paths for acquiring images. We present extensive benchmarks in the realistic simulator, which validates the performance of SOAR compared with classical and state-of-the-art methods. For more details, please see our project page at
https://sysu-star.github.io/SOARsysu-star.github.io/SOAR.










§ INTRODUCTION















With the increasing demand for three-dimensional (3D) reconstruction in various fields, including urban planning, digital cultural heritage, and structural inspection, the utilization of unmanned aerial vehicles (UAVs) for autonomous reconstruction has garnered significant attention. Due to their agility and flexibility, UAVs have emerged as ideal platforms for rapidly acquiring images and reconstructing 3D models. An effective planning method is pivotal to fully realizing the potential of UAVs and advancing the efficiency and quality of reconstruction.

Most UAV planning methods for reconstruction can be categorized into two categories: model-based and model-free methods. Model-based methods employ an "explore-then-exploit" strategy <cit.>, typically involving pre-scanning the field or relying on up-to-date prior information, such as satellite images<cit.>, to construct a rough prior model. The prior model is then utilized for viewpoint generation and path planning. However, constructing a prior model can be time-consuming and relies heavily on the available data. On the other hand, model-free methods <cit.> partially eliminate the need for a prior model through autonomous exploration. Unfortunately, without the guidance of a prior model, they are limited to conducting local planning to explore unknown regions while simultaneously scanning the known surface. As a result, the efficiency of the reconstruction process is limited.

In this paper, we propose SOAR, a LiDAR-Visual heterogeneous multi-UAV planner that enables simultaneous exploration and photographing for fast autonomous reconstruction of complex scenes.
Our approach combines the strengths of both model-based and model-free methods. By utilizing a team of collaborative UAVs, it allows for the object to be scanned in parallel with the coarse model generation, which significantly enhances the efficiency of the reconstruction process.
The system incorporates an explorer UAV equipped with a LiDAR sensor that has a large sensing range, which enables rapid acquisition of surface geometry. Similar to the prior model in model-based methods, the surface provides abundant information for conducting long-range viewpoint generation and path planning. Simultaneously, the task of scanning the already-explored surface is assigned to multiple photographers equipped with RGB cameras, working collaboratively to achieve comprehensive scene coverage. As the explorer progressively acquires surface information, we propose an efficient viewpoint generation method capable of incrementally generating a minimal number of viewpoints necessary to cover the surface. These viewpoints are then clustered and assigned to the photographers by solving a Consistent-MDMTSP. This iterative process optimizes the scanning efficiency of the photographers while ensuring consistency in consecutive task assignments. Finally, each photographer plans the shortest path to capture images based on the assigned clusters, utilizing them as global guidance for efficient image acquisition.

We compare our method with classic and state-of-the-art methods in simulation. Results demonstrate that our method achieves higher efficiency and superior reconstruction quality in benchmark scenarios. In summary, the contributions of this paper are summarized as follows:

1) A novel LiDAR-Visual heterogeneous multi-UAV system that enables rapid and efficient completion of reconstruction tasks.

2) An incremental viewpoint generation method that produces a minimal number of viewpoints to ensure full coverage as the surface information is incrementally acquired.

3) A task assignment method that iteratively optimizes the scanning efficiency while ensuring consistency in consecutive task assignments.



4) The proposed method has been extensively validated in two realistic simulation environments. The source code[<https://github.com/SYSU-STAR/SOAR>] of our system will be released.



§ RELATED WORK





 §.§ UAV-based Reconstruction



In UAV-based reconstruction research, identifying suitable imaging positions and devising efficient paths are extensively explored topics. Most methods can be classified as either model-based or model-free.

The majority of model-based methods utilize the "explore-then-exploit" strategy, which consists of two phases. The first phase is called the exploration phase, which acquires the coarse prior model from pre-flight <cit.> or satellite images<cit.>. In the exploitation phase, global optimal viewpoints and paths are generated based on the coarse prior model to acquire proper images for 3D reconstruction. However, decomposing tasks into two stages incurs high costs and adds complexity to the process.
The model-free method means reconstructing target scenes without a prior model. Therefore, this method has to find the best scanning trajectory in an online manner from a partially constructed model.<cit.> adopt surface-based planning, which concentrates on reconstructing a precise 3D surface model instead of exploring whole unknown spaces.<cit.> extract incomplete surface elements via TSDF and generate a list of candidate viewpoints to cover them. Due to the absence of a prior model, model-free methods cannot avoid the occurrence of a local optimal dilemma.

In this study, we leverage the strengths of both model-free and model-based approaches by employing a heterogeneous multi-UAV system. The explorer rapidly explores the environment, supplying ample scene information to photographers, thus facilitating efficient online planning.



 §.§ Multi-robot Planninng



Multi-robot systems have been extensively explored in various studies related to scene reconstruction, where they offer reduced reconstruction time. The efficiency of a multi-robot system heavily relies on the effectiveness of task assignment. Traditionally, unknown areas or viewpoints were often considered as assigned tasks in prior works. For instance, Jing et al. <cit.> formulate a multi-agent Coverage Path Planning (CPP) problem, solved using a Set-Covering Vehicle Routing Problem (SC-VRP) approach, to inspect structures. Additionally, Hardouin et al. <cit.> utilize a TSP-Greedy assignment algorithm to assign viewpoints to each robot. To achieve better task partitioning and enhance robustness against communication loss and failure, Zhou et al. <cit.> devise a Capacitated Vehicle Routing Problem (CVRP) formulation to minimize the overall lengths of robot coverage paths. However, in scenarios involving the rapid and incremental generation of viewpoints, the accumulation of unvisited viewpoints becomes significant. It becomes impractical and lacks consistency to include all unvisited viewpoints in each task assignment, as some may have been appropriately assigned in previous iterations.

In this paper, we introduce the task assignment method Consistent-MDMTSP, which leverages previous assignment results for rapid iterative optimization of scanning efficiency. Additionally, we introduce costs related to task consistency to enhance the uniformity of assignments.



§ PROBLEM FORMULATION



We consider a heterogeneous multi-UAV system to reconstruct the scene in an unknown and spatially limited 3D space V⊂ℝ^3 with a bounding box B. Our system comprises one explorer and N_p photographers. The explorer is equipped with a large-scale perception LiDAR for rapid exploration. Photographers are equipped with a gimbaled RGB camera with 2 degrees of freedom (pitch angle θ_cam and yaw angle ψ_cam) and limited FoV for scene scanning. Due to the explorer's faster speed and larger perception range compared to the photographers, we assume that the speed of rough exploration exceeds that of fine scanning. Additionally, assume that all agents are allowed to communicate with each other at any time.

The space V is represented as a set of cubic voxels v ∈ V, initially designated as unknown and continuously updated by the explorer to be occupied or free. Let V_ukn∈ V, V_occ∈ V, and V_free∈ V denote the sets of unknown, occupied, and free voxels, respectively. Also, let S be the set of surfaces. A voxel v ∈ S if and only if:
v ∈ V_occ∃nbr_v^6∈ V_free
Here, nbr_v^6 represents the 6-connected neighbors of v. Our objective is to leverage the explorer to identify all surfaces S while simultaneously deploying photographers to achieve full coverage of all surfaces S in the shortest time possible.



§ SYSTEM OVERVIEW



As depicted in Fig. <ref>, the system comprises an explorer and multiple photographers. The explorer utilizes a surface frontier-based exploration approach (Sect.<ref>) to rapidly acquire geometric information about the scene. Concurrently, as more surfaces are explored, viewpoints are incrementally generated (Sect.<ref>). These viewpoints are uniformly and efficiently distributed to each photographer through the Consistent-MDMTSP method with high task consistency (Sect.<ref>). Photographers utilize the received viewpoint cluster tasks as global guidance for local path planning and generation trajectory (Sect.<ref>), ensuring the completion of their assigned tasks in the shortest time possible. Finally, the image-pose pairs are sent for offline 3D reconstruction, resulting in textured 3D models.



§ METHODOLOGY




 §.§ Surface Frontier-based Exploration



To provide sufficient prior structure information for scene coverage, we aim for the explorer to focus on the surface of the scene. Inspired by <cit.>, we adopt surface frontier-guided planning for rapid exploration.



  §.§.§ Surface Frontier Detection and Viewpoint Generation.


A surface frontier voxel v_sf can be defined as a free voxel with an occupied neighbor v_o and an unknown neighbor v_u, where v_o and v_u are also neighbors. Similar to <cit.>, all v_sf are first clustered based on connectivity, and then larger clusters are split into smaller ones using a PCA-based clustering approach. As the map is gradually updated, the outdated clusters are deleted, and the new clusters are detected. The exploration will end if there is no surface frontier.

We calculate the centroid of N_c clusters and sample a set of viewpoints with different yaw angles at a certain radius from the centroid on horizontal planes. To better observe inclined planes such as the roof, we add different sampling heights to viewpoint generation. For each cluster, we select the viewpoint with the most visible v_sf as the representative of this cluster, denoted as vp_i = (p_i, ψ_i), where p_i and ψ_i respectively represent the position and the yaw angle of the viewpoint. vp_i will be reserved for the cluster to guide the path planning. 





  §.§.§ Exploration Planning.


Finding the shortest visit tour of N_c viewpoints will increase the efficiency of exploration. We model this problem as an Asymmetric Traveling Salesman Problem (ATSP) and design the cost matrix 𝐂_atsp that is needed by the Lin-Kernighan-Helsgaun heuristic solver<cit.>(LKH-Solver). The 𝐂_atsp is a N_c + 1 dimensions square matrix, the major (N_c + 1) × N_c block is composed of the cost between each pair of viewpoints and explorer's current position (p_0,ψ_0)to the viewpoint, which is presented as:

    𝐂(i,j)    = max{Len(P(p _i,p_j))/v_max,
               |ψ_i-ψ_j|/ψ̇_max}

where P(p_i, p_j) means the collision-free path between P_i and P_j searched by A* algorithm, v_max and ψ̇_max are the maximum velocity and angular change rate of yaw.
The cost from other vp_i to the current position will be set to zero since our method does not consider the cost of the return. Finally, the 𝐂_atsp can be present as:

    𝐂_atsp(i,j)     = {
     0,    j  = 0 
    𝐂(i,j)     0≤ i≤ N_c,0 < j ≤ N_c
    .

By solving the ATSP problem, we can determine the next viewpoint to visit and then utilize MINCO<cit.> to generate a continuous collision-free trajectory from the current position to the next viewpoint, thereby exploring the scene surface rapidly.



 §.§ Incremental Viewpoint Generation



To comprehensively cover the scene, it is essential to generate reasonable viewpoints for coverage. As the scene surface information is obtained by the explorer progressively, it is important that the viewpoint generation process can adapt to the dynamically changed surface. To this end, we propose an incremental viewpoint generation method aimed at achieving full scene coverage with minimal viewpoints. 







  §.§.§ Uncovered Surface Extraction.


As the environment is gradually explored, the surfaces of the scene also expand, including some unstable or uncertain surfaces that are not suitable for generating corresponding viewpoints at the current moment. Therefore, we incrementally select stable surfaces, as depicted in Fig. <ref>: 
First, we detect known surfaces based on connectivity and then utilize a clustering method based on Euclidean distance to partition the detected surfaces into smaller surface clusters (Fig. <ref>-(a)). Subsequently, we identify which cluster has been fully explored (Fig. <ref>-(b)), designating it as a "completely explored surface," denoted as S_exp. Here, the S_exp is defined as a surface cluster devoid of any surrounding surface frontiers.
For finer coverage, we extract the point cloud PT_new within each voxel of S_exp from the point cloud map maintained by the ikdtree <cit.>, while concurrently labeling each voxel as "extracted." During the next update of the map, we repeat the aforementioned process. However, it's worth noting that the extracted surface will not be involved in the above operation again. This ensures that each point cloud on the surface of the entire scene is only extracted once, thereby avoiding redundant computations (Fig. <ref>-(c),<ref>-(d)).

To reduce the generation of invalid viewpoints, we need to filter out the points in PT_new that have already been covered by point clouds. The specific operations are as follows: We utilize all CV_hq to perform ray-casting on PT_new within the camera FoV, where CV_hq are all the high-quality viewpoints obtained through the updates in Sect. <ref>. We merge the point cloud from PT_new, which has not been intersected by collision-free ray-casting, with the previously uncovered point cloud PT_unc,prev to obtain the current uncovered surface point cloud PT_unc.





  §.§.§ Viewpoint Sampling and Iterative Update.


Our method employs 5-DoF viewpoints, denoted as 𝐜𝐯 = [p_c, θ_c, ψ_c], where p_c represents the position of the camera, while θ_c and ψ_c respectively indicate the gimbal's pitch and yaw angles.
We conduct viewpoint sampling guided by the normal vectors of the uncovered point cloud P_unc. For each point cloud 𝐩𝐭 = [pt_x, pt_y, pt_z] within P_unc and its associated normal vector 𝐧𝐯 = [n_x, n_y, n_z], we sample a viewpoint at a distance D away according to the following procedure:

    p_c = 𝐩𝐭 + D ·𝐧𝐯
       θ_c = arctan(n_z,√(n_x^2 + n_y^2)) 
       ψ_c = arctan(-n_y, -n_x)

However, as the direction of each normal vector 𝐧𝐯 cannot be determined, we sample viewpoints in both directions. We then filter them based on whether they are within a free area and whether a collision-free ray can be projected to the corresponding point cloud.
This process yields the initial set of viewpoints CV_ini.

Below, we evaluate the coverage capability of each viewpoint. We enumerate through each viewpoint cv in CV_ini to compute the number of point clouds from P_unc that can be observed, denoted as n_obs. Concurrently, for each observed point cloud, we identify the viewpoint with the maximum n_obs as its truly covering viewpoint, labeled as cv_cover. The count of point clouds truly covered by each viewpoint, n_cover, is updated accordingly. In the above process, frequent queries of the correspondence between point clouds and viewpoints are required to perform update operations. Therefore, we maintain a pair of hash tables for both viewpoints and point clouds, enabling quick mapping from the position of a point cloud to the corresponding covering viewpoint.

Building on our previous work <cit.>, we use a gravitation-like model to update the viewpoints in CV_ini. This model merges viewpoints that cover fewer areas into those covering more, thus replacing the less effective viewpoints and eliminating redundancy. Specifically, we first sort the viewpoints in CV_ini in descending order based on n_cover. Then, for each viewpoint cv_i, we sequentially query the neighboring viewpoints CV_q within a radius r_q. The pose of cv_i is then updated using the gravitational force exerted by CV_q:

    p_i = p_i + ∑_cv_q∈CV_qn_cover,q/n_cover,i(p_q - p_i)

where p_i is the updated position of cv_i. Similarly, we obtain the updated pitch θ_i and yawψ_i. Then, we label each viewpoint in CV_q as "dormant," ensuring that these viewpoints no longer participate in the aforementioned update process. After one round of enumeration, we obtain the updated viewpoint set CV_u and update the uncovered point cloud PT_unc. We repeat the above procedure of viewpoint sampling and updating until the current coverage rate reaches a threshold.




 §.§ Consistent-MDMTSP for Task Assignment



In this section, we introduce a novel task assignment approach that is based on a viewpoint cluster task structure (Sect. <ref>), while simultaneously ensuring scanning efficiency and consistency in consecutive task assignments (Sect. <ref>).



  §.§.§ Viewpoint Clustering Task Structure.


The broad perception range and rapid exploration pace of the explorer result in a considerable number of viewpoints needing assignment to photographers, imposing significant time overhead if assigned directly. To address this challenge, we draw inspiration from <cit.> and employ a viewpoint clustering method to partition the entire set of viewpoints into several subsets. Additionally, we design a viewpoint clustering task (VCT) structure to incrementally maintain the status of VCTs.

Each VCT_i consists of four parameters: VP_i, p_avg,i, h_cost,i, and L_cost,i. VP_i represents the positions of all viewpoints contained in VCT_i. p_avg,i denotes the average position of VP_i. h_cost,i stands for the execution cost of VCT_i, which is approximated to be dependent only on the number of viewpoints in VP_i. The mathematical expression is as follows:

    h_cost,i = λ_h * (NUM(VP_i)-1) * d_thr

Here, NUM(VP_i) represents the number of viewpoints in VCT_i, and d_thr denotes the distance threshold for viewpoint clustering. L_cost,i represents the A* path distance between p_avg,i and all the average positions of other VCTs. The mathematical expression is as follows:

    L_cost,i,j = Len[P(p_avg,i,p_avg,j)]

Note that d_thr is relatively small compared to the entire scene, so it is assumed that p_avg,i remains relatively stable throughout subsequent computations. Therefore, we can maintain L_cost,i incrementally.

The proposed viewpoint clustering method primarily relies on visibility and distance for clustering. It ensures that there are no obstructions between any pair of viewpoints within a cluster, and the distance between them is less than the distance threshold d_thr.
Whenever a new viewpoint is added, it is first iteratively matched with the existing VCTs based on distance priority within the range of d_thr. If the new viewpoint can undergo unobstructed ray-casting with VP_i in VCT_i and the pairwise distances are all less than the threshold d_thr, then the viewpoint is merged into VCT_i. Otherwise, it initializes itself as a new VCT.
When a viewpoint in VP_j is visited, we remove the viewpoint from VP_j in VCT_j, and update p_avg,j and 𝐡_cost,j. If VP_j has no viewpoints, VCT_j will be removed.





  §.§.§ Consistent-MDMTSP.



The optimization problem of assigning multiple tasks to multiple drones while minimizing the maximum travel time of each drone can be formulated as a Multiple Traveling Salesman Problem (MTSP). Despite the availability of mature solvers <cit.> for solving MTSP, there are two main issues with using them directly:
1) Due to incomplete map information, obtaining only a locally optimal solution each time leads to poor consistency, resulting in unnecessary detours for photographers.
2) Since tasks are updated incrementally with minor changes each time, recalculating the overall assignment results is unnecessary.
To address these issues, we propose the Consistent-MDMTSP method based on genetic algorithms (GA). This method incorporates the cost term related to task consistency and iteratively generates new assignment results by leveraging the previous results.



In our method, we adopt a multi-chromosome genetic representation<cit.>, which enables efficient decoding and encoding of the problem. As depicted in the example illustrated in Fig. <ref>, each individual with multiple chromosomes in the population represents a single solution to the problem. Suppose there are N_p photographers and N_vct VCTs that have not been completed yet. Let a single individual I = {PATH_1, …, PATH_N_p}, where PATH_i = {x_i,1, …, x_i, M_i} and ∑_l=1^N_p M_l = N_vct. Here, PATH_i represents the visit path sequence of the ith photographer, x_i,j denotes the id of the VCT to be visited jth in PATH_i, and M_i represents the number of VCTs in PATH_i.

Our fitness function is designed as a combination of distance cost and consistency cost.
To evaluate the distance cost, we introduce a weighted directed graph G = (V_d, E_d), where V_d contains N_p photographer nodes and N_vct VCT nodes, and E_d represents the set of edges. We maintain two weight matrices, 𝐂_d,vct and 𝐂_vct: the former represents the distance costs between all photographers and all VCTs:

    𝐂_d,vct(k_1,k_2) = 
            Len[P(p_d,k_1,p_avg,k_2)] + h_cost,k_2
       k_1 ∈{1,2,…,N_p},    k_2 ∈{1,2,…,N_vct}

and the latter represents the distance costs among all VCTs:

    𝐂_vct(k_3,k_4) =  
            𝐋_cost,k_3,k_4 + h_cost,k_4
       k_3, k_4∈{1,2,…,N_vct}

The calculation of the cost_dis,i for PATH_i is as follows:

    cost_dis,i =  𝐂_d,vct(i,x_i,1) + 
                        ∑_j=1^M_i-1𝐂_vct(x_i,j, x_i,j+1)











To improve task assignment consistency, we aim for the current assignment result to closely approximate the previous result when the distance costs are relatively similar. Given the ith photographer’s previous visit path sequence, denoted as  PATH_i^* = {x_i,1^*, …, x_i, M_i^*^*}, our objective is to maximize the length of the common prefix between PATH_i and PATH_i^*, assigning higher weights to initial segments, thereby enhancing overall planning consistency.

    cost_con,i =  -∑_k=1^K_same R · e^-α·DSUM(k)

The length of this common prefix is denoted by K_same, while DSUM(k) denotes the cumulative distance along PATH_i for the first k VCTs of the ith photographer. The parameters R and α control the weight of consistency and the distance decay rate, respectively. A lower cost_con,i signifies greater task consistency.

The overall cost of PATH_i is given by:

    cost_all,i = cost_dis,i + cost_con,i


To achieve a balanced assignments of VCTs among photographers and maintain high task consistency, we define the fitness function for individual I as follows: 

    Fit(I) = -(max{cost_all,i}_i=1^M_i + ϵ * ∑_i=1^M_i cost_all,i)

To minimize the maximum cost incurred by any photographer, we identify the cost component with the highest value and optimize it accordingly.Additionally, a small penalty term is added to minimize the overall cost when the maximum costs are similar. The negative sign serves to invert the cost function into a fitness function.

Given that only a small subset of VCTs is modified between map updates, we adopt a strategy that leverages the previous best individual. Rather than randomly initializing the population for each iteration, we utilize the highest fitness individual from the preceding iteration, denoted as I_best,prev, as a foundation for generating the initial population P_init,cur. Specifically, we construct I_tmp by excluding executed VCTs from I_best,prev. Then, we randomly insert all newly added VCTs into the chromosomes of I_tmp, thereby obtaining one individual in P_init,cur. Repeating this random operation multiple times yields complete initial population. This approach significantly reduces the iteration times.

Finally, after K_GA iterations, the optimization process concludes, and the individual with the highest fitness is selected as the assignment result. This result is then communicated to all photographers.



 §.§ Coverage Planning for Photographers



In this section, the planning strategy for all photographers remains consistent. The strategy involves photographers receiving assigned viewpoint clusters and visitation order through communication between UAVs. Subsequently, they utilize this information as global guidance for local path planning (Sect. <ref>), generating collision-free trajectories (Sect. <ref>) to achieve rapid coverage.





  §.§.§ Local Path Planning.



Each photographer performs refined local path planning guided by the received global viewpoint cluster path. We select all M_local viewpoints from the first K_local VCTs along the global path to plan a local path. We construct an (M_local+1)-dimensional square cost matrix to solve an ATSP with the photographer’s current position as the starting point and the center of the (K_local+1)-th VCT in the global path as the endpoint (K_local≥ 1). This ATSP cost matrix resembles <ref>.





  §.§.§ Trajectory Optimization.



To achieve smooth navigation, we generate a collision-free and continuous trajectory passing through the first M_kc viewpoints P_kc = {v_c^1,…,v_c^M_kc} of the path P_c. Specifically, we partition the trajectory into M_kc pieces and enforce boundary conditions between trajectory pieces:

    tp_c^i(0)=p_c^i-1, 
           tp_c^i(T_c^i) = p_c^i,   ∀ 1≤ i ≤ M_kc

Specifically, p_c^0 represents the current position of the drone.
To ensure safety, we maintain an ESDF map to impose position constraints:

    D_ESDF(tp_c^i(t)) ≥ r_s,   ∀ t ∈ [0,T_c^i],  ∀ 1≤ i ≤ M_kc

where D_ESDF(·) represents the signed distance between the drone and the nearest obstacle boundary, tp_c^i denotes the i-th trajectory segment with a duration of T_c^i, and r_s denotes the drone's safe distance.
We also impose kinodynamic constraints, including: v(t)≤ v_max, a(t)≤ a_max, and j(t)≤ j_max, to mitigate visual blur caused by aggressive flight. Additionally,
The yaw and pitch trajectories are generated with similar constraints as mentioned above.
We employ MINCO <cit.> to optimize the trajectory while satisfying the aforementioned constraints.







§ EXPERIMENTS





 §.§ Implementation Details



We set D = 5m in Eq.<ref>, λ_h = 0.6 and d_thr = 6.0m in Eq.<ref>, ϵ = 10^-4 in Eq.<ref>, R = 50, α = 0.1 in Eq.<ref>, and the number of iterations in the genetic algorithm K_GA = 700.

All experiments were conducted using the MARSIM <cit.> simulator to simulate quadrotor UAVs equipped with a MID360 LiDAR. A 2-axis gimbal camera was employed as the sensor for each photographer.
In exploration planning (Sect. <ref>) and local path planning (Sect. <ref>), the ATSPs are solved using LKH-Solver<cit.>.
All the above modules run on an Intel Core i7-13700F CPU.





 §.§ Benchmark Comparisons and Analysis



To evaluate our proposed framework, we conduct simulations in two complex environments: the Sydney Opera House (30 x 36 x 14 m³) and the Pisa Cathedral (29 x 37 x 15 m³). 
Our proposed method is compared to both a model-free method and a model-based method, namely the multi-robot version of Star-Searcher <cit.> (SSearchers) and Multi-EE, respectively.
All experiments employ four UAVs, with sensor configurations detailed in Table <ref>.

The LiDAR-equipped UAV, not involved in image capture, has relaxed dynamic limits of v_max = 2.0  m/s, ω_max = 2.0  rad/s, a_max = 2.0  m/s^2, and j_max = 2.0  m/s^3. 
 The image capture UAVs adhere to stricter limits of v_max = 1.0  m/s, ω_max = 1.0  rad/s, a_max = 1.0  m/s^2, and j_max = 1.0  m/s^3 to ensure image quality. All cameras possess a [80^∘, 60^∘] FoV and capture images at a resolution of 640 × 480 pixels. 
Star-Searcher <cit.> extends exploration by incorporating surface observation. We implement SSearchers by partitioning the scene into bounding boxes based on prior knowledge and independently applying the Star-Searcher planner within each box. The Multi-EE approach involves an exploration phase where multiple UAVs capture images along predefined trajectories to construct a coarse 3D model using Reality Capture[<https://www.capturingreality.com/>]. Subsequently, in the exploitation phase, global viewpoints are generated based on the coarse model using our proposed method and then distributed among UAVs by solving the MTSP with LKH-Solver <cit.>. Fig. <ref> provides a detailed overview of our approach. To simulate image acquisition, we rendered images in Blender[<https://www.blender.org/>] at a 2 Hz frequency along the drone trajectories and processed these image-pose pairs using Reality Capture to produce the final 3D model.


We evaluate performance using two metrics: efficiency (flight time and path length) and reconstruction quality (recall, precision, and F-score)<cit.>, with an F-score threshold of 0.01 m. 
Due to SSearchers lacking an explicit assignment algorithm, reported times represent the average across all UAVs, while for Ours and Multi-EE, the maximum time among the four UAVs is considered. Table <ref> and Fig. <ref> present the comparison results.

Our proposed heterogeneous system outperforms competing methods in both flight time and reconstruction quality, demonstrating its suitability and potential for reconstructing complex, large-scale scenes. This improvement is primarily attributed to our incremental viewpoint generation approach and efficient task assignment strategy.

































 §.§ Ablation Study



1) Incremental viewpoint generation: To validate the superiority of our incremental viewpoint generation strategy, we compared it to the global viewpoint generation approach of FC-Planner <cit.> (Global). In our method, viewpoints are incrementally generated as the explorer gradually explores the environment, while the global method generates viewpoints directly based on the entire map information. As shown in <ref> and <ref>, our method generates a comparable number of viewpoints and achieves a similar coverage rate to the global method, indicating its ability to maintain a high level of global optimality.






























2) Task assignment: To evaluate the impact of our Consistent-MDMTSP, we conducted an ablation study (Exp.MTSP) by replacing it with LKH-Solver's MTSP <cit.> while maintaining other experimental settings. As shown in Table <ref>, our method demonstrates shorter computation time, flight time, and flight length, especially in the complex scenario (Sydney). These improvements are attributed to our Consistent-MDMTSP's iterative optimization process, which leverages the previous optimal solution and accelerates the iteration process. Additionally, by increasing the consistency cost, our method ensures higher task consistency.





§ CONCLUSION



This paper presents a LiDAR-Visual heterogeneous multi-UAV system for rapid and autonomous aerial reconstruction. An explorer provides comprehensive scene information through surface frontier-based exploration, while viewpoints are incrementally generated from uncovered surfaces and assigned to photographers using Consistent-MDMTSP. Our approach exhibits superior efficiency and reconstruction quality compared to state-of-the-art methods, as demonstrated through rigorous evaluations in complex simulation environments.

While SOAR demonstrates promising results, several limitations remain to be addressed in future research. The current system primarily relies on simulated environments and assumes ideal communication conditions. Real-world applications necessitate considering additional factors such as image overlap and inter-UAV occlusion during the reconstruction process. To address these limitations, future work will concentrate on optimizing the system architecture to enable robust operation in complex, real-world communication environments.






























