Source-linked AI summary
Safety-enhanced UAV Path Planning with Spherical Vector-based Particle Swarm Optimization
Manh Duong Phung, Quang Phuc Ha
TL;DR
UAV path planning in complex, threat-filled environments must produce safe and feasible paths while meeting application objectives. The paper formulates a constrained cost function and introduces SPSO, which searches the UAV configuration space through spherical-vector motion components. Across eight DEM-based scenarios, SPSO achieves the best-quality paths in most scenarios and experiments validate generated paths for practical UAV operations.
Problem
UAV path planning remains challenging when paths must be collision-free, feasible, and safe in environments containing multiple threats.
Method
The paper combines path requirements and UAV constraints in a cost function and uses SPSO to search configuration space through particle representations corresponding to UAV motion.
Results
SPSO achieves the best-quality paths in most of eight DEM-based benchmarking scenarios and outperforms PSO variants and GA, ABC, and DE in the reported comparisons.
Takeaways & Limitations
Experiments with real UAVs show the validity of SPSO-generated paths for practical operations.
Takeaways & Limitations
SPSO can prematurely converge to local optima in certain scenarios, including scenario 7 where DE performs better.
Abstract
from arXiv · showhide
This paper presents a new algorithm named spherical vector-based particle swarm optimization (SPSO) to deal with the problem of path planning for unmanned aerial vehicles (UAVs) in complicated environments subjected to multiple threats. A cost function is first formulated to convert the path planning into an optimization problem that incorporates requirements and constraints for the feasible and safe operation of the UAV. SPSO is then used to find the optimal path that minimizes the cost function by efficiently searching the configuration space of the UAV via the correspondence between the particle position and the speed, turn angle and climb/dive angle of the UAV. To evaluate the performance of SPSO, eight benchmarking scenarios have been generated from real digital elevation model maps. The results show that the proposed SPSO outperforms not only other particle swarm optimization (PSO) variants including the classic PSO, phase angle-encoded PSO and quantum-behave PSO but also other state-of-the-art metaheuristic optimization algorithms including the genetic algorithm (GA), artificial bee colony (ABC), and differential evolution (DE) in most scenarios. In addition, experiments have been conducted to demonstrate the validity of the generated paths for real UAV operations. Source code of the algorithm can be found at https://github.com/duongpm/SPSO.
1. Introduction
UAV path planning must balance application objectives with safety and feasibility constraints in complex environments. The paper motivates SPSO as a configuration-space search method for evaluating such paths.
- Motivation: UAV path planning supports tasks such as photography, mapping, inspection, surveillance, rescue, and dynamic target search.Objectives include minimizing distance or flight time, maximizing detection probability, and finding Pareto solutions.
- Motivation: Collision-free and feasible UAV motion remains challenging because planned paths must satisfy operational safety constraints.
- Existing approaches: Graph-based methods can generate feasible paths but may omit UAV maneuver constraints, producing large differences between planned and flown paths.
- Existing approaches: Cell decomposition uses grid-based heuristic search, but its capacity scales poorly as the number of cells grows exponentially with search-space dimension.
- Existing approaches: Nature-inspired algorithms are prevalent because they can handle UAV dynamic constraints and search for global optima in complex scenarios.Examples include GA, DE, ABC, ACO, and PSO.
- Particle swarm optimization: PSO uses cognitive and social information to search solutions, offering stable convergence and shorter computation time than other nature-inspired algorithms.
- Research direction: PSO variants differ in how particles represent the search space and encoded solutions, potentially producing different solutions under identical operating conditions.
- Research direction: The study formulates a constrained objective, proposes SPSO, evaluates it on eight DEM-based scenarios, and tests path feasibility for practical UAV operation.
2. Problem Formulation
The formulation converts UAV path planning into a weighted cost minimization problem combining path optimality, threat avoidance, altitude bounds, and smooth maneuvering. Waypoints define the decision variable, while the component costs encode operational constraints.
- 2.1. Path optimality: The path is represented by n waypoints Pij = (xij, yij, zij), and path length is minimized for photography, mapping, and surface inspection.
- 2.2. Safety and feasibility constraints: The threat model represents each obstacle as a cylinder with center Ck and radius Rk, then assigns cost according to waypoint distance from the threat.
- 2.2. Safety and feasibility constraints: The safety distance S depends on operating conditions and positioning accuracy, ranging from tens of meters in favorable static settings to hundreds of meters with moving objects or weak GPS.
- 2.2. Safety and feasibility constraints: Altitude cost maintains average flight height while penalizing waypoint heights outside the prescribed minimum hmin and maximum hmax.
- 2.2. Safety and feasibility constraints: Smooth cost evaluates turning and climbing rates, using turning and climbing angles to produce feasible paths.
- 2.2. Safety and feasibility constraints: Threat cost is zero beyond S + D + Rk, increases with proximity within the danger region, and becomes infinite inside D + Rk.
- 2.3. Overall cost function: The overall cost combines path length, threat, smoothness, and flight-height costs with weight coefficients bk.The decision variable is the waypoint list Xi within the UAV operating space O.
3. Related PSO algorithms for UAV path planning
The paper frames UAV path planning as optimization over candidate paths, then reviews PSO and variants that differ in how particles represent and update solutions. These representations include Cartesian waypoints, phase angles, and quantum-behaved position updates.
- Optimization formulation: The cost function turns UAV path planning into minimizing a path X∗, motivating heuristic and metaheuristic methods for complicated multimodal optimization.Classic methods such as hill climbing are described as unsuitable because of local maxima.
- Particle swarm optimization: PSO balances each particle’s local best position with the swarm’s global best position while updating particle positions and velocities.The inertial weight controls the compromise between global exploration and local exploitation, while η1 and η2 control attraction toward local and global bests.
- Particle swarm optimization: In UAV path planning, standard PSO encodes each candidate as N three-dimensional Cartesian waypoints, excluding fixed start and end points.A path with n waypoints is represented by a particle of dimension 3N, where N = n − 2.
- Phase angle-encoded PSO: θ-PSO replaces Cartesian coordinates with 3N phase angles and maps angular particles back to coordinate-space paths using a monotonic function.Its nonlinear mapping adds more waypoints to the middle section of candidate paths to improve search capacity there.
- Quantum-behaved PSO: QPSO models particles through a quantum state and updates positions probabilistically, using a local attractor and random variables rather than maintaining velocity.The supplied passages identify mbest as the swarm’s mean best position and β as the contraction-expansion coefficient.
4. Spherical vector-based PSO for UAV path planning
SPSO represents UAV paths with spherical vectors whose components correspond to maneuver characteristics, enabling configuration-space search with directly encoded flight constraints. The algorithm evaluates mapped paths and retains lower-cost local and global solutions during swarm evolution.
- Spherical path representation: SPSO encodes each path as spherical vectors describing UAV movement between waypoints through magnitude, elevation angle, and azimuth angle.A path with N nodes is represented by a hyper spherical vector of 3N dimensions.
- Particle updates: SPSO associates each particle position with an incremental velocity vector containing changes in magnitude, elevation angle, and azimuth angle.The velocity is represented componentwise across all N spherical vectors.
- Path evaluation: The algorithm maps each spherical vector uij to a Cartesian waypoint Pij so the corresponding direct path can be evaluated by the cost function.The mapping is denoted ξ : Ω→X, and local and global best positions are then computed from evaluated paths.
- Safety-oriented representation: The spherical components correspond to UAV speed, turning angle, and climbing angle, allowing turning and climbing constraints to be implemented directly.This representation searches the UAV configuration space rather than Cartesian space to pursue quality solutions with enhanced navigation safety.
- Algorithm procedure: SPSO retains a candidate as the best path when its fitness improves the current best, while infeasible solutions receive infinite cost and are excluded from final outputs.Its overall procedure includes initialization, swarm evolution, global-best updates, and saving the best position.
5. Results
SPSO was evaluated across increasingly complex DEM-based scenarios, comparisons with PSO variants and other metaheuristics, and real UAV flights. It generally produced strong, feasible paths, with particular advantages in complex environments, while premature convergence and cost-weight selection remained limitations.
- Evaluation setup: Eight benchmarking scenarios based on real LiDAR-derived DEM maps used terrain structures and threat placements with different complexity levels.Two areas of Christmas Island, Australia, were augmented to create the scenarios.
- Comparison between PSO algorithms: All algorithms generated feasible paths satisfying requirements for length, threats, turn angle, climb/dive angle, and height, but optimality varied by scenario.Differences were slight in simple scenarios and much larger in complicated scenarios.
- Comparison between PSO algorithms: SPSO statistically achieved the best fitness in most scenarios, especially the complicated cases where PSO and θ-PSO found relatively good solutions and QPSO struggled.The comparison used average fitness, standard deviation, and paired sample t-test results.
- Discussion and limitations: SPSO’s direct mapping to UAV parameters supported search-space exploration and smooth, valid paths, but premature convergence occurred in some scenarios and cost-term weights can be difficult to choose.Scenario 7 favored DE, while adding requirements such as fuel consumption may complicate weight selection and motivate multi-objective optimization.
- Scalability comparison: With n = 22 waypoints, SPSO remained effective in most scenarios, whereas PSO and θ-PSO degraded in larger search spaces and QPSO performed poorly in many cases.The spherical vector-based encoding enabled particle searches in the UAV configuration space.
- Comparison with other metaheuristic algorithms: Against GA, ABC, and DE, SPSO achieved increasing margins and D+ t-test results in complicated scenarios, while DE remained strong and GA was least stable.GA’s node-deletion operator reduced path resolution, limiting adaptation to complex threats.
- Experimental verification: Real 3DR Solo experiments produced collision-free flight paths that matched planned paths, including abrupt height changes over a monorail bridge.The experiments used Mission Planner and two threat-augmented scenarios in a Sydney park.
6. Conclusion
The paper presents SPSO for UAV path planning, combining optimality, safety, and feasibility constraints through a correspondence between UAV motion and the search space. Benchmark comparisons and real-UAV experiments support its performance and practical validity, while future work targets exact dynamic constraints.
- SPSO incorporates optimality, safety, and feasibility constraints simultaneously through a cost function for UAV path planning.
- Eight benchmarking scenarios generated from digital elevation model maps show SPSO achieving the best performance.
- Experiments with real UAVs validate the generated paths for practical operations.
- Future work will incorporate exact constraints in configuration space using UAV dynamic models.