Three-dimension collision-free trajectory planning of UAVs based on ADS-B information in low-altitude urban airspace

Chao Dong, Yifan Zhang, Ziye Jia, Yiyang Liao, Lei Zhang, Qihui Wu

TL;DR

This paper introduces a novel approach for three-dimensional, collision-free trajectory planning for Unmanned Aerial Vehicles (UAVs) in complex low-altitude urban airspace. By leveraging ADS-B information and dividing the airspace into manageable sub-airspaces, the proposed Secure Sub-airSpaces Planning (SSP) and PSO-RRT algorithms significantly improve safety and efficiency compared to existing methods.

What Problem Does This Paper Address?

Low-altitude urban airspace presents a significant challenge for UAV operations due to its complexity, including numerous static obstacles (buildings), dynamic obstacles (birds, other aircraft), and limited onboard sensing capabilities. Ensuring collision-free flight is paramount for safety and security. Traditional trajectory planning methods often struggle with the real-time acquisition of comprehensive situational awareness, leading to potential risks. While ADS-B is a mature technology in civil aviation for broadcasting aircraft information, its effective integration for dynamic UAV trajectory planning in dense urban environments remains an open problem. The paper aims to address the need for a robust, efficient, and safe trajectory planning system that can handle the dynamic and unpredictable nature of urban airspace.

Methods

The paper proposes a two-pronged approach:

  1. Secure Sub-airSpaces Planning (SSP):
    • Airspace Division: The urban airspace is divided into a grid of smaller, manageable sub-airspaces. This simplifies the planning problem by allowing UAVs to focus on local conditions.
  2. ADS-B Integration: UAVs are equipped with ADS-B devices to broadcast their own information and receive data from other aircraft and ground stations. This provides crucial real-time situational awareness.
  3. Dynamic Programming & Sliding Window: SSP uses dynamic programming to plan a coarse-grained trajectory across sub-airspaces. A "sliding window" mechanism is employed to dynamically adjust the planned path based on the number of UAVs in upcoming sub-airspaces, aiming to reduce congestion.
  4. Attraction Mechanism: An attraction mechanism is incorporated within the sliding window to guide the endpoint of a sub-airspace trajectory, further shortening path lengths and improving efficiency.
  5. Particle Swarm Optimization-Rapidly-exploring Random Trees (PSO-RRT):
    • Hybrid Approach: This algorithm combines the strengths of RRT (and its variant Bi-RRT) for exploring collision-free paths with the optimization capabilities of Particle Swarm Optimization (PSO).
  6. Fine-grained Planning: After SSP determines a coarse trajectory between sub-airspaces, PSO-RRT is used for detailed, collision-free trajectory planning within each sub-airspace.
  7. Cost Function: A comprehensive cost function is defined, considering factors like the number of static and sudden obstacles, distance to obstacles, and trajectory length (energy consumption).
  8. Obstacle Modeling: Both static (buildings) and sudden (birds, other UAVs) obstacles are modeled, with distinct layer structures to represent their spatial extent.

Datasets

Not discussed in the paper. The evaluation relies on simulated environments.

Key Insights and Ideas

  • Airspace Segmentation is Key: Dividing the complex urban airspace into smaller sub-airspaces is a fundamental strategy for making trajectory planning tractable and improving safety by localizing the problem.
  • ADS-B as a Game Changer: Leveraging ADS-B data for both broadcasting and receiving information is crucial for achieving the necessary situational awareness in a dynamic environment.
  • Dynamic Adjustment is Essential: A fixed trajectory is insufficient. The SSP's sliding window and attraction mechanism allow for real-time adjustments based on changing UAV densities, preventing bottlenecks.
  • PSO-RRT Balances Safety and Efficiency: The hybrid PSO-RRT approach effectively balances the need for collision avoidance (safety) with minimizing trajectory length and energy consumption (efficiency) within each sub-airspace.
  • Obstacle Modeling Matters: Differentiating between static and sudden obstacles, and modeling them appropriately, is vital for accurate collision detection and avoidance.

Key Results

  • SSP reduces UAV density: The SSP algorithm, particularly with the sliding window, significantly reduces the maximum number of UAVs in any given sub-airspace compared to methods without this dynamic adjustment.
  • SSP shortens trajectory length: The sliding window and attraction mechanism in SSP contribute to shorter overall trajectory lengths between sub-airspaces.
  • PSO-RRT reduces trajectory cost: The PSO-RRT algorithm consistently achieves lower trajectory costs within sub-airspaces compared to using RRT or Bi-RRT alone, indicating a better balance of safety and efficiency.
  • Improved safety margin: The PSO-RRT planned trajectories maintain a greater distance from obstacles, providing a larger safety margin even in the presence of positioning errors.

Limitations and Future Work

  • Real-time Performance: While simulations demonstrate effectiveness, the paper acknowledges the need to investigate real-time performance, UAV peak values in airspace, and average computation time using actual hardware (Raspberry Pi, ADS-B devices).
  • Cooperation and Communication: Future work will incorporate cooperation between UAVs for conflict avoidance and investigate the impact of Network-Assisted Communication (NACv) and Network-Assisted Communication (NACp) on ADS-B message reception.
  • Hardware Validation: The authors plan to conduct more practical experiments using constructed ADS-B devices for validation.
  • Dynamic Obstacle Prediction: While sudden obstacles are handled, more advanced prediction and reaction mechanisms for highly dynamic obstacles could be explored.

Summary updated

Abstract

The environment of low-altitude urban airspace is complex and variable due to numerous obstacles, non-cooperative aircraft, and birds. Unmanned Aerial Vehicles (UAVs) leveraging environmental information to achieve three-dimension collision-free trajectory planning is the prerequisite to ensure airspace security. However, the timely information of surrounding situation is difficult to acquire by UAVs, which further brings security risks. As a mature technology leveraged in traditional civil aviation, the Automatic Dependent Surveillance-Broadcast (ADS-B) realizes continuous surveillance of the information of aircraft. Consequently, we leverage ADS-B for surveillance and information broadcasting, and divide the aerial airspace into multiple sub-airspaces to improve flight safety in UAV trajectory planning. In detail, we propose the secure Sub-airSpaces Planning (SSP) algorithm and Particle Swarm Optimization Rapidly-exploring Random Trees (PSO-RRT) algorithm for the UAV trajectory planning in law-altitude airspace. The performance of the proposed algorithm is verified by simulations and the results show that SSP reduces both the maximum number of UAVs in the sub-airspace and the length of the trajectory, and PSO-RRT reduces the cost of UAV trajectory in the sub-airspace.
BibTeX
@inproceedings{dong2024three,
  author = {Chao Dong and Yifan Zhang and Ziye Jia and Yiyang Liao and Lei Zhang and Qihui Wu},
  title = {{Three-dimension collision-free trajectory planning of UAVs based on ADS-B information in low-altitude urban airspace}},
  booktitle = {Chinese},
  year = {2024},
  doi = {10.1016/j.cja.2024.08.001},
}
Figure