Decentralized Multi-UAV Cooperative Exploration: History
View Latest Version
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor:
Jianjun Gui
,
Tianyou Yu
,
Baosong Deng
,
Xiaozhou Zhu
,
Wen Yao

Efficient exploration is a critical issue in swarm UAVs with substantial research interest due to its applications in search and rescue missions.

  • path planning
  • collaborative exploration
  • area partition
  • swarm UAVs

1. Multi-UAV Coordination for Exploration

Using multiple UAVs to increase exploration efficiency is a common practice, and related issues have been extensively studied [1]. One classic method involves maximizing overall utility while minimizing the potential overlap of measurements among UAVs [2]. This idea has been employed in many works such as [3][4][5]. However, as the number of UAVs increases, uncertainty [6] and redundant scanning between them become more prevalent, especially in larger environments where the sensor range is relatively small compared to the scale of the environment.
In conventional multi-agent allocation problems, a TSP-greedy allocation (TSGA) planner with ideal centralized architecture and communication assumptions is utilized to optimize global utility [7]. This approach considers the whole global task, which may be time-consuming for collecting tasks in the center. Alternatively, a dynamic Voronoi partition has been utilized in [3][8] to assign different target locations to individual UAVs, guaranteeing the separateness between them. However, this area partition-based method may not always be optimal as it does not consider the exploring process of each UAV, resulting in less efficient task allocation.
Therefore, a dynamic centroid-based area partition is proposed, which considers the exploration process of each UAV for more reasonable task allocation. When a UAV has an insufficient number of candidates, it will be assigned a larger partitioned area to explore. The partition is processed dynamically to adapt to changing situations.

2. Multi-UAV Mapping for Exploration

To perform target selection and quantitative calculation in planning, it is necessary to have a map that depicts the environment and further exploration areas. Two representative volumetric mapping methods used in UAV exploration are truncated signed distance field (TSDF) [9] and occupancy [10]. When employing multi-UAV mapping methods, the key issue is often the map merging [11]. Previous works such as [2][5] involve each UAV maintaining its local map and correcting odometry errors while exploring. They then transmit their local maps with uncertain information to a central work station who can combine local maps into a global one for further optimization. In [12], sensor messages are shared among UAVs, and Gaussian mixture models (GMMs) are adopted to assist the exploration planner of each UAV. In [4], two maps are utilized: a low-resolution map for navigation and a high-resolution map for reconstruction. In order to achieve efficient coordination in a decentralized method, it is crucial to share the global map message among UAVs as quickly as possible.

3. Exploration in Unknown Environments

While fully functional UAVs possess autonomous sensing and computing capabilities, the exploration planner enables them to independently perform tasks in unknown environments. Existing works fall into two categories when executing under unknown: frontier-based methods [13][14][15] and sampling-based methods [4][16][17][18]. With given frontier clusters [19] or sampled viewpoints [18], an information-theoretic measure is optimized to calculate information gain, resulting in reduced map uncertainty. The frontier-based method explicitly computes the boundary between the known and unknown areas and assigns UAVs to frontiers iteratively, but the frontier selection process can be time-consuming as it traverses all surface voxels in a large environment [13]. Some methods reject unsuitable frontiers during selection [20] to ease the computational burden. On the other hand, the sampling-based method randomly selects viewpoints in free areas, such as the rapidly-exploring random tree (RRT) [16] and probabilistic roadmap planner (PRM) [21], which deliver speed and probabilistic completeness. However, these two methods could converge locally.
The two mentioned categories were widely used in the exploration planning of a single UAV. However, for multi-UAV exploration, a coordination module is required to prevent collisions and redundancies. The NBV method [22] is commonly utilized in such scenarios. This method iteratively selects viewpoints in free space to refresh candidates’ paths, ensuring a consistent update rate. The proposed method follows this approach by integrating the strengths of the sampling-based method. This enables frequent recollection of viewpoints to avoid collisions and facilitate flexible collaboration between UAVs.

4. Evaluation in Practical Experiments

To further validate the proposed method, practical indoor experiments were conducted with three self-assembly UAVs equipped with depth cameras flying in a room with obstacles, as shown in Figure 1b. A 10×8×3m310×8×3m3 bounding box was used to constrain the space for exploration. Due to the UAV structure, the cameras could only be mounted with a downward pitch angle of 5∘5∘ on the front side, and the UAVs’ precise location was ensured through the use of VICON, a motion capture system, for safe piloting. Parameter values for the practical experiments were set based on the simulation experiments conducted for the indoor scenario. Although limitations such as hardware restrictions, network bandwidth, and flight trajectory control were not the primary focus, multiple trials were carried out to ensure the proposed method’s usability.
Drones 07 00337 g008 550
Figure 1. The practical experiments. (a) shows the initial status of three UAVs; they are placed on the same side of a room. (b) shows three UAVs are performing exploration in one trial; a 10×8×3m310×8×3m3 virtual boundary is set to bound the exploring space.
The proposed algorithm was tested in a practical experiment involving a team of three UAVs, as shown in Figure 1. The UAVs were initially positioned closely together on the same side of the exploration area, which is typical for real deployments. The exploration process was repeated 20 times, with a maximum exploration time of 232.2s232.2s, a minimum of 194.6s194.6s, and an average of 209.4s209.4s. The decentralized nature of the planner ensures that the UAVs can perform their tasks robustly, with interruptions to one UAV having no impact on the work of others, as demonstrated in Figure 2. The effectiveness and usability of the proposed method in a practical scenario are demonstrated by the exploration maps at six different sampling times, as shown in Figure 3. The virtual centroid in three colors dynamically changes during the exploration process, and the working area of each UAV is partitioned reasonably and iteratively. The UAV denoted as the yellow on the left moves gradually to the lower-left area after completing its task in the upper-left corner and collaborates with the UAV in the lower-right section to adjust the task areas. In the final map of Figure 3, the gap areas on the ground were detected, which were affected by the range of the depth camera. It is assumed that using more robust sensors such as 3D LiDAR could alleviate this phenomenon, but such an approach requires greater consideration of the comprehensiveness of the experimental system and its applicability to different settings, which needs to be further considered in future research.
Drones 07 00337 g009 550
Figure 2. Robust coordination case. (a) shows UAV represented by the red arrow has stopped exploring due to insufficient power at an early stage; (b) shows other UAVs continue to finish the task. The yellow one helps the red to explore the bottom right corner of this environment.
Drones 07 00337 g010 550
Figure 3. The mapping process of one practical experiment. The sampling times display the complete process of three UAVs collaborating on exploration, with each UAV’s designated area being continuously updated. The UAV represented by the yellow icon on the left gradually moves towards the lower region, collaborating with the other UAVs to adjust the exploration area. In the final map, gaps on the ground were influenced by the depth camera’s perception range. It is assumed that using more powerful sensors such as 3D LiDAR [23] may mitigate this phenomenon, but this approach necessitates further consideration of the experimental system’s applicability.

This entry is adapted from the peer-reviewed paper 10.3390/drones7060337

References

  1. Ju, S.; Wang, J.; Dou, L. MPC-Based Cooperative Enclosing for Nonholonomic Mobile Agents Under Input Constraint and Unknown Disturbance. IEEE Trans. Cybern. 2023, 53, 845–858.
  2. Simmons, R.; Apfelbaum, D.; Burgard, W.; Fox, D.; Moors, M.; Thrun, S.; Younes, H. Coordination for Multi-Robot Exploration and Mapping; AAAI Press: Palo Alto, CA, USA, 2020; pp. 852–858.
  3. Masaba, K.; Li, A.Q. GVGExp: Communication-Constrained Multi-Robot Exploration System based on Generalized Voronoi Graphs. In Proceedings of the 2021 International Symposium on Multi-Robot and Multi-Agent Systems (MRS), Cambridge, UK, 4–5 November 2021; pp. 146–154.
  4. Mannucci, A.; Nardi, S.; Pallottino, L. Autonomous 3D Exploration of Large Areas: A Cooperative Frontier-Based Approach. In Proceedings of the Modelling and Simulation for Autonomous Systems, Rome, Italy, 24–26 October 2017; Mazal, J., Ed.; Springer International Publishing: Cham, Switzerland, 2018; pp. 18–39.
  5. Fox, D.; Jonathan, K.O.; Konolige, K.; Limketkai, B.; Schulz, D.; Stewart, B. Distributed Multirobot Exploration and Mapping. Proc. IEEE 2006, 94, 1325–1339.
  6. Tang, Y.; Chen, Y.; Zhou, D. Measuring uncertainty in the negation evidence for multi-source information fusion. Entropy 2022, 24, 1596.
  7. Hardouin, G.; Moras, J.; Morbidi, F.; Marzat, J.; Mouaddib, E.M. Next-Best-View planning for surface reconstruction of large-scale 3D environments with multiple UAVs. In Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Las Vegas, NV, USA, 24 October 2020–24 January 2021; pp. 1567–1574.
  8. Hu, J.; Niu, H.; Carrasco, J.; Lennox, B.; Arvin, F. Voronoi-Based Multi-Robot Autonomous Exploration in Unknown Environments via Deep Reinforcement Learning. IEEE Trans. Veh. Technol. 2020, 69, 14413–14423.
  9. Oleynikova, H.; Taylor, Z.; Fehr, M.; Siegwart, R.; Nieto, J. Voxblox: Incremental 3D Euclidean Signed Distance Fields for on-board MAV planning. In Proceedings of the 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, Canada, 24–28 September 2017; pp. 1366–1373.
  10. Hornung, A.; Wurm, K.M.; Bennewitz, M.; Stachniss, C.; Burgard, W. OctoMap: An efficient probabilistic 3D mapping framework based on octrees. Auton. Robot. 2013, 34, 189–206.
  11. Li, H.; Tsukada, M.; Nashashibi, F.; Parent, M. Multivehicle Cooperative Local Mapping: A Methodology Based on Occupancy Grid Map Merging. IEEE Trans. Intell. Transp. Syst. 2014, 15, 2089–2100.
  12. Corah, M.; O’Meadhra, C.; Goel, K.; Michael, N. Communication-Efficient Planning and Mapping for Multi-Robot Exploration in Large Environments. IEEE Robot. Autom. Lett. 2019, 4, 1715–1721.
  13. Schmid, L.; Reijgwart, V.; Ott, L.; Nieto, J.; Siegwart, R.; Cadena, C. A Unified Approach for Autonomous Volumetric Exploration of Large Scale Environments Under Severe Odometry Drift. IEEE Robot. Autom. Lett. 2021, 6, 4504–4511.
  14. Zhou, B.; Zhang, Y.; Chen, X.; Shen, S. FUEL: Fast UAV Exploration Using Incremental Frontier Structure and Hierarchical Planning. IEEE Robot. Autom. Lett. 2021, 6, 779–786.
  15. Lee, E.M.; Choi, J.; Lim, H.; Myung, H. REAL: Rapid Exploration with Active Loop-Closing toward Large-Scale 3D Mapping using UAVs. In Proceedings of the 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Prague, Czech Republic, 27 September–1 October 2021; pp. 4194–4198.
  16. Lindqvist, B.; Agha-Mohammadi, A.A.; Nikolakopoulos, G. Exploration-RRT: A multi-objective Path Planning and Exploration Framework for Unknown and Unstructured Environments. In Proceedings of the 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Prague, Czech Republic, 27 September–1 October 2021; pp. 3429–3435.
  17. Zhu, H.; Cao, C.; Xia, Y.; Scherer, S.; Zhang, J.; Wang, W. DSVP: Dual-Stage Viewpoint Planner for Rapid Exploration by Dynamic Expansion. In Proceedings of the 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Prague, Czech Republic, 27 September–1 October 2021; pp. 7623–7630.
  18. Schmid, L.; Pantic, M.; Khanna, R.; Ott, L.; Siegwart, R.; Nieto, J. An Efficient Sampling-Based Method for Online Informative Path Planning in Unknown Environments. IEEE Robot. Autom. Lett. 2020, 5, 1500–1507.
  19. Charrow, B.; Kahn, G.; Patil, S.; Liu, S.; Goldberg, K.; Abbeel, P.; Michael, N.; Kumar, V. Information-Theoretic Planning with Trajectory Optimization for Dense 3D Mapping. In Proceedings of the Robotics: Science and Systems, Rome, Italy, 13–17 July 2015; Volume 11, pp. 3–12.
  20. Cieslewski, T.; Kaufmann, E.; Scaramuzza, D. Rapid exploration with multi-rotors: A frontier selection method for high speed flight. In Proceedings of the 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, Canada, 24–28 September 2017; pp. 2135–2142.
  21. Xu, Z.; Deng, D.; Shimada, K. Autonomous UAV Exploration of Dynamic Environments Via Incremental Sampling and Probabilistic Roadmap. IEEE Robot. Autom. Lett. 2021, 6, 2729–2736.
  22. Bircher, A.; Kamel, M.; Alexis, K.; Oleynikova, H.; Siegwart, R. Receding Horizon “Next-Best-View” Planner for 3D Exploration. In Proceedings of the 2016 IEEE International Conference on Robotics and Automation (ICRA), Stockholm, Sweden, 16–21 May 2016; pp. 1462–1468.
  23. Li, S.; Tian, B.; Zhu, X.; Gui, J.; Yao, W.; Li, G. InTEn-LOAM: Intensity and Temporal Enhanced LiDAR Odometry and Mapping. Remote Sens. 2022, 15, 242.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
This entry is offline, you can click here to edit this entry!
ScholarVision Creations
Feedback