Online path planning for kinematic-constrained UAVs in a dynamic environment based on a Differential Evolution algorithm

Technical Summary: Online Path Planning for Kinematic-Constrained UAVs in Dynamic Environments

Problem Statement
This research addresses the challenge of online path planning for fixed-wing Unmanned Aerial Vehicles (UAVs) operating in dynamic environments. Unlike quadrotors, fixed-wing UAVs face unique kinematic constraints, including maximum curvature, minimum turning radius, and specific orientation requirements (yaw and pitch angles). The core problem is to generate a feasible, collision-free path in real-time that satisfies these motion constraints while navigating through environments containing both static and dynamic obstacles. The system must operate within a limited sensing range ($R_{view}$), detecting obstacle positions and velocity vectors at discrete re-planning intervals ($t_s$), and ensure the UAV remains within the free space ($\Omega_{free}$) while avoiding no-fly zones and potential collisions.

Methodology
The proposed solution integrates a Non-Uniform Rational B-Spline (NURBS) path representation with a Differential Evolution (DE) optimization algorithm, enhanced by concepts from the Velocity Obstacle (VO) approach.

• Path Representation: The path is modeled as a NURBS curve defined by control points ($P$) and weights ($w$). To satisfy orientation constraints at the start and end of the path, three collinear points are added to the first and last control points, scaled by factors $\lambda_1$ and $\lambda_2$.
• Optimization Strategy: Unlike previous offline approaches that optimized curve parameters directly, this online method optimizes the variation of these parameters ($\Delta\chi = [\Delta P, \Delta w, \lambda_1, \lambda_2]$) relative to an initial feasible path. This strategy aims to accelerate convergence.
• Objective Function: The optimization minimizes flight energy cost, defined as the path length (assuming constant speed and ignoring wind), subject to:
  1. Kinematic Constraints: Curvature $\kappa(s)$ must not exceed the maximum allowable curvature ($\kappa_{max}$).
  2. Obstacle Avoidance: The UAV position $p_u$ must not enter restricted zones ($\Omega_{obs}$).
  3. Dynamic Collision Avoidance: The relative velocity of the UAV with respect to obstacles must not fall within the Velocity Obstacle cone ($VO^{\tau}_{o_i/u}$) for a prediction horizon $\tau$. This constraint is applied to all detected obstacles ($N_{obs}$) within the sensing range.
• Algorithm: The Linear-Success-History Based Adaptive Differential Evolution for Constrained Optimization Problems (LSHADE-COP) is employed to solve the constrained optimization problem at each re-planning interval.
• Control Implementation: Once a feasible NURBS curve is generated, it is mapped into a vector field control law (based on prior work [10]) to guide the UAV along the path.

Key Contributions

1. Online Deliberative Planning: The authors transition their previous offline DE-NURBS framework into an online planner capable of handling dynamic obstacles and re-planning at intervals of approximately $t_s \approx 0.1$ seconds.
2. Integration of Velocity Obstacles: A novel constraint function incorporating the Velocity Obstacle approach is embedded directly into the DE optimization process. This allows the algorithm to penalize future collisions with moving obstacles during the path generation phase, rather than relying solely on a reactive local planner.
3. Parameter Variation Optimization: By optimizing the variation of NURBS parameters rather than the parameters themselves, the method achieves faster convergence suitable for real-time applications.
4. Feasibility in 2D: The system successfully generates paths for fixed-wing UAVs in 2D dynamic environments, maintaining constant altitude and adhering to kinematic limits.

Results
Simulation results demonstrate that the proposed planner successfully navigates UAVs through crowded environments with moving obstacles.

• Performance: The online planner is reported to be approximately 12,000 times faster than the authors' previous offline planner [5].
• Safety: The inclusion of the Velocity Obstacle constraint enables safe navigation in scenarios where a re-planning approach without this constraint would fail or lead to collisions.
• Efficiency: The system can modify only the necessary sections of an initial NURBS curve to avoid dynamic obstacles, rather than replanning the entire mission path from scratch.
• Visual Validation: Snapshots of the deliberative planning process (Fig. 1) and supplementary video evidence confirm the planner's ability to generate smooth, feasible curves that avoid dynamic threats.

Significance and Claims
The paper claims to provide a feasible foundation for online path planning for kinematic-constrained UAVs in dynamic settings. The authors emphasize that their approach avoids the need for additional smoothing steps often required by other fixed-wing planners. While the current study is limited to 2D scenarios with constant altitude, the authors state that the method is designed to be extensible to three-dimensional (3D) environments. The work is presented as a step toward solving the challenging open problem of planning motion to avoid dynamic obstacles without guiding the UAV into local minima or unfeasible situations, a limitation noted in simpler local planner approaches.