Fast Unfolding-Based Indoor Space Partitioning and Rapid Complementary Search Planning for High-Rise Fire Rescue

This paper introduces a swift solution for the complementary coverage path planning issue for multiple uncrewed aerial vehicles (UAV) in 3-dimensional, non-convex, and trap-laden indoor environments. A topology graph is constructed by sampling the blueprint. To divide the indoor environment into several convex areas and form tasks for the UAVs, the Louvain (fast unfolding) algorithm is utilized twice for space partitioning and task assigning. Finally, to ascertain the path for each UAV, a tiny-scale traveling salesman problem (TSP) is formed and solved. The simulation result reveals that the proposed strategy has significantly improved efficiency in both 2-dimensional and 3-dimensional path planning, underscoring the algorithm’s practical relevance for high-rise fire rescue operations. Note to Practitioners—This paper is motivated by the requirement of urgent task assignment and route finding for multiple uncrewed aerial vehicles (UAV) in indoor searching, especially for high-rise fire rescue. A rapid task allocation and pathfinding framework that balances efficiency and optimization levels is proposed. Unlike other complex environments, community-detection-based task allocation methods are recommended for actual indoor space rather than clustering-based ones. Additionally, the degree of each node in the sampling graph can be used to rapidly determine the sensor’s detection range at that node and the distance to obstacles. Making reasonable use of this can further enhance the efficiency of task allocation and pathfinding. Extensive experimental results in actual indoor maps show the effectiveness of the proposed task allocation and pathfinding framework. Note that our method is designed only for indoor environments divided into multiple rooms by continuous walls, and the effectiveness in other types of environments cannot be guaranteed.