This article is about the path planning content of the UAV formation system, including the application of UAVs in the Internet, autonomous navigation and motion planning of quad-rotor aircraft, trajectory optimization and challenges in the formation flight system, etc.
1. Application of drones in the Internet
With their flexibility and mobility, unmanned aerial vehicles (UAVs) have gradually become an important part of the Internet of Things (IoT), especially in scenarios that deal with communication congestion and insufficient network coverage. With the explosive growth of the number of devices, the amount of data generated in the Internet of Things is increasing, and traditional terrestrial infrastructure is difficult to handle such a huge data load. Unmanned Aerial Vehicles (UAVs) are widely used to improve the performance of IoT networks due to their flexibility, maneuverability and low cost. UAVs can not only provide wireless access in the absence of terrestrial networks, but can also perform a variety of tasks such as video surveillance, cargo transportation, data collection, etc., greatly enhancing the flexibility and adaptability of IoT networks. However, UAV-assisted IoT networks have many challenges due to their high dynamics, heterogeneity, and complexity, such as communication resource management, energy management, and flight control issues.[1]. Below we will elaborate on the flight control issue.
2. Autonomous navigation and motion planning of quad-rotor aircraft
With their high maneuverability and flexibility, quadcopters have been widely used in the field of aerial robotics, especially in tasks such as aerial photography, search and rescue, environmental monitoring, and cargo transportation. However, in order to efficiently perform these tasks in complex environments, quadcopters must have fully autonomous navigation capabilities. This means that they must not only be able to sense the surrounding environment, but also need to independently plan flight paths and adjust in real time to avoid obstacles to ensure the smooth completion of the mission. The key to autonomous navigation ismotion planningmodule, which is responsible for the coordination of the overall system and making decisions based on the environment and mission requirements[2]。The motion planning system of a quadcopter can generally be divided into two main stages:
1 · Front-end path planning (Path Planning)
Path planning is the primary task in autonomous navigation, aiming to find a safe path from the starting point to the target point and avoid collision with obstacles.Path planning methods are mainly divided into two categories: sampling-based methods and search-based methods.
(1) Sampling basis method
The sampling base path planning method is as follows:Probabilistic Roadmap Method (PRM)andRapidly expanding random trees (RRT)Generate paths by randomly sampling points from a free configuration space[3]. PRM generates a graph model by connecting random sampling points and finds paths through a graph search algorithm. RRT, on the other hand, grows a tree starting from the starting position, with each node representing a feasible free space configuration. The tree grows through random configurations and connections to its nearest neighbor nodes until the target configuration is found.
The advantage of these methods is that they can quickly generate feasible paths and are suitable for dynamic environments. However, the asymptotic optimality of the RRT method is insufficient, and improved versions such asRRT*By locally reconnecting tree nodes, the optimality of paths is improved. The sampling basis method performs well when dealing with complex, nonlinear environments, but is relatively weak for path optimization.
Path planning based on RRT algorithm
(2) Search basis method
Search base path planning method such asA*andDijkstraThe algorithm discretizes the configuration space and uses a graph search algorithm to find the optimal path.[4]。A*The algorithm introduces a heuristic function to ensure that an optimal path is found by evaluating the current path cost and the estimated cost to the target point during the search process. Dijkstra's algorithm gradually selects the node with the shortest distance among the currently unvisited nodes, updates the distance of neighboring nodes, and finally finds the shortest path.
Search basis methods excel in path optimality, especially in static or known environments. However, in dynamic or complex environments, its search efficiency may be affected by heuristic function design, resulting in greater computational overhead.
A* path planning algorithm[10]
2
Backend trajectory optimization
（Trajectory Optimization）
Trajectory optimizationis a critical step to ensure that the path is not only geometrically feasible, but also dynamically executable. Path planning usually only generates geometric paths, and in order to ensure the dynamic feasibility of the quadcopter, the geometric path needs to be parameterized as time and generate dynamically feasible trajectories. This process is usually performed by minimizing the control cost or other optimization objective functions and optimizing under the conditions of satisfying safety and dynamic constraints. Trajectory optimization methods can be divided into two categories:hard constraint methodandsoft constraint method。
(1) Hard constraint method
Hard constraint methods strictly require trajectories to satisfy specific constraints throughout the optimization process. A typical hard constraint method isMinimum-Snap Trajectory Generation Algorithm (Minimum-Snap Trajectory Generation), this algorithm uses the differential flatness characteristic of the quadcopter to simplify the state space of the aircraft into 3D position and yaw angle, and express the trajectory through piecewise polynomials[5]. by solvingQuadratic planning problem, this algorithm is able to generate smooth, continuous trajectories, ensuring that the acceleration, velocity and position derived constraints of the trajectory are satisfied.
This method is particularly suitable for tasks that require precise control, such as high-precision flight or complex obstacle avoidance environments. However, when dealing with dynamic and unpredictable environments, hard-constraint methods may require multiple iterations to ensure the feasibility of the trajectory.
Minimum-Snap algorithm results under flight corridor constraints[5]
(2) Soft constraint method
Soft constraint methods deal with constraint violations by introducing a penalty term in the objective function. Typical soft constraint methods includeCHOMP（Covariant Hamiltonian Optimization for Motion Planning）andSTOMP（Stochastic Trajectory Optimization for Motion Planning）[6]. CHOMP generates trajectories by minimizing the local objective function of smoothness and collision cost, while STOMP is based on the gradient-free optimization method and generates the optimal path through the combination of candidate trajectories. The soft constraint method has certain flexibility when dealing with complex environments and can better cope with dynamic scenes. However, soft constraint methods are prone to falling into local optimal solutions and have low success rates in collision-intensive environments.
Results of HMC dual CHOMP and RRT* in the same path planning problem[6]
In order to further improve the efficiency and accuracy of trajectory optimization, many new technologies have been proposed. For example, based onB-splinesThe trajectory representation method can generate smooth and less locally constrained trajectories, making it more efficient in local re-planning. At the same time, by combiningSampling method based on polyhedral safe flight corridor or point cloud map, which can significantly improve the computational efficiency of trajectory optimization, especially in complex environments.
3. Trajectory optimization and challenges in formation flight system
Trajectory optimization and challenges in formation flight systems are an important part of UAV swarm flight research. As the application of drone swarms in search and rescue, agricultural monitoring, urban management and other fields continues to increase, how to effectively optimize trajectories to ensure that drone swarms maintain formation, avoid obstacles and perform tasks in complex environments is a very challenging problem. The following is a detailed elaboration of the core issues, optimization methods, and current challenges in this field.
1 · Core challenges in formation flight systems
The goal of formation flying is to allow multiple UAVs to perform tasks in a coordinated manner, maintain a predetermined formation, and respond to dynamic changes in the outside world.[7]. Here are some of the most challenging aspects of formation flying:
(1) Conflict between formation maintenance and obstacle avoidance
In formation flying, drones need to maintain a certain formation (such as linear, rectangular, circular, etc.) with each other to complete specific tasks. However, the conflict between maintaining formation shape and avoiding obstacles is often difficult to reconcile. When obstacles appear in the environment, the drones need to adjust their flight paths to avoid the obstacles while trying to keep the original formation structure from being destroyed.
(2) Coping in a dynamic environment
Formation flight systems must be able to respond to dynamic environments in real time, such as moving obstacles, sudden environmental changes, or adjustments to mission requirements. Traditional static path planning methods cannot cope with these rapidly changing conditions, requiring the formation flight system to have a high degree of flexibility and adaptive capabilities in order to adjust the trajectory in real time according to environmental changes during flight.
(3) Scalability of large-scale formations
When the formation size is small (e.g., several UAVs), trajectory optimization is less computationally intensive and easier to manage. However, as the formation size increases, the computational complexity and communication overhead of trajectory optimization increase dramatically. In particular, when the number of drones in the formation reaches dozens or even hundreds, it is a great challenge to maintain the coordination of the global formation while ensuring the safe flight of each drone.
(4) Formation recovery and reorganization capabilities
During formation flying, external conditions (such as strong winds, obstacles) or internal system failures may cause the formation structure to be damaged. In this case, the system needs to have the ability to quickly reorganize the formation so that it can return to the original formation or re-plan a new formation as soon as possible and continue to perform the mission. This requires the formation system to be highly elastic and resilient.
2· Trajectory optimization method in formation flight
Trajectory optimization is the core to ensure that the formation flight system operates efficiently in complex environments. Trajectory optimization not only needs to ensure the feasibility of the path, but also minimizes energy consumption and maintains coordination between drones. The following are several common trajectory optimization methods.
(1) Distributed trajectory optimization
Distributed trajectory optimization allocates trajectory planning tasks to individual UAVs, allowing each UAV to independently optimize its path while ensuring the overall coordination and consistency of the formation. The advantage of distributed optimization is that it can reduce the computational complexity of global optimization, making it more suitable for large-scale UAV formations.
· Distributed Model Predictive Control (DMPC)
DMPC ensures that its trajectory is feasible in the future period and consistent with the trajectories of other drones by optimizing the trajectory of each drone within the prediction time period. This approach enables each drone to make decisions based on local information while taking into account the goals of the overall formation[8]。
· Distributed optimization based on game theory
In this method, each drone is treated as a game player, constantly adjusting its trajectory through interaction with surrounding drones. The advantage of the game theory method is that it can establish an adaptive collaboration mechanism between drones and achieve distributed trajectory optimization.[9]。
(2) Dynamic obstacle avoidance and real-time re-planning
Dynamic obstacle avoidance is a critical issue in formation flying, especially when there are moving obstacles or other aircraft in the environment. In order to solve this problem, the real-time re-planning method came into being:
·Dynamic Window Approach (DWA)
DWA is an obstacle avoidance method based on local perception. Each drone dynamically adjusts its flight speed and direction based on environmental information acquired by its sensors to avoid collisions with obstacles. This method is suitable for dealing with real-time changing environments.
· Combination of local planning and global path
Local path planning is used to make obstacle avoidance adjustments in the short term, while global path planning is responsible for maintaining the long-term mission goals of the entire formation. By combining local and global planning, the formation can maintain efficient operation in complex environments.
(3) Formation adjustment and flexible planning
In narrow corridors or confined spaces, fixed formations may make drones impenetrable or inefficient. To this end, the formation system needs to have elastic adjustment capabilities so that the drones can dynamically adjust the formation according to the environment.
· Deformable Formation
The morphing formation method allows UAVs to adjust the shape, size or spacing of the formation based on environmental constraints such as obstacles or mission requirements. For example, when passing through a narrow passage, the formation can change from rectangular to linear to ensure that each drone can pass smoothly.
· Task reorganization and task allocation optimization
In complex missions, some drones may take on more important roles, such as serving as formation leaders or performing specific tasks. In this case, the overall efficiency and flexibility of the formation can be further improved by reorganizing and optimally allocating tasks.
References
[1] N. Cheng et al., "AI for UAV-Assisted IoT Applications: A Comprehensive Review", IEEE Internet Things J., Volume 10, Issue 16, Pages 14438–14461, August 2023, doi: 10.1109/JIOT.2023.3268316.
[2] L. Quan, L. Han, B. Zhou, S. Shen and F. Gao, "Survey of UAV motion planning", IET Cyber-Syst. Robot., Volume 2, Issue 1, Pages 14–21, March 2020, doi: 10.1049/iet-csr.2020.0004.
[3] Y. Guo, X. Liu, Q. Jia, X. Liu and W. Zhang, "HPO-RRT*: a sampling-based algorithm for UAV real-time path planning in a dynamic environment", Complex Intell. Syst., Volume 9, Issue 6, Pages 7133–7153, December 2023, doi: 10.1007/s40747-023-01115-2.
[4] Y. Du, "Multi-UAV Search and Rescue with Enhanced A ∗ Algorithm Path Planning in 3D Environment", Int. J. Aerosp. Eng., Volume 2023, Pages 1–18, February 2023, doi: 10.1155/2023/8614117.
[5] B. Shi et al., "UAV Trajectory Generation Based on Integration of RRT and Minimum Snap Algorithms", in 2020 Chinese Automation Congress (CAC), Shanghai, China: IEEE, November 2020, pages 4227–4232. doi: 10.1109/CAC51589.2020.9326562.
[6] "A new local path planning approach based on improved dual covariant Hamiltonian optimization for motion planning method - Bo You, Zhi Li, Liang Ding, Haibo Gao, Jiazhong Xu, 2019". Published on: October 12, 2024. [Online]. In: https://journals.sagepub.com/doi/full/10.1177/1687814019851007
[7] H. Do et al., "Formation Control Algorithms for Multiple-UAVs: A Comprehensive Survey", EAI Endorsed Trans. Ind. Netw. Intell. Syst., Volume 8, Issue 27, Page 170230, June 2021, doi: 10.4108/eai.10-6-2021.170230.
[8] Z. Cai, L. Wang, J. Zhao, K. Wu and Y. Wang, "Virtual target guidance-based distributed model predictive control for formation control of multiple UAVs", Chin. J. Aeronaut., Volume 33, Issue 3, Pages 1037–1056, March 2020, doi: 10.1016/j.cja.2019.07.016.
[9] C. Han, A. Liu, K. An, G. Zheng and X. Tong, "Distributed UAV Deployment in Hostile Environment: A Game-Theoretic Approach", IEEE Wirel. Commun. Lett., Volume 11, Issue 1, Pages 126–130, January 2022, doi: 10.1109/LWC.2021.3122127.
[10] C. W. Warren, "Fast path planning using modified A* method", In Proceedings [1993] Proceedings IEEE International Conference on Robotics and Automation, Atlanta, GA, USA: IEEE Comput. Soc. Press, 1993, pp. 662–667. doi: 10.1109/ROBOT.1993.291883.
Machine-translated from the Chinese original 无人机编队系统的路径规划 (published 2024-10-21). WeChat original ↗