Abstract
Unmanned Aerial Vehicles (UAVs) have become pivotal in military, agricultural, and logistics applications, necessitating efficient trajectory planning algorithms. Traditional RRT* algorithms suffer from prolonged search times, slow convergence, and suboptimal paths. This paper introduces an enhanced APF-RRT* algorithm that integrates Artificial Potential Field (APF) principles with RRT* to address these limitations. The proposed method incorporates a target attraction strategy, redundant node pruning via greedy algorithms, and cubic B-spline smoothing to optimize path quality. Simulation and physical experiments demonstrate significant improvements in path length, planning time, node count, and iteration efficiency compared to conventional RRT* and APF-RRT algorithms.
1. Introduction
UAV trajectory planning involves generating collision-free paths from a start to a goal point while minimizing energy consumption and ensuring flight stability. Existing algorithms, such as A, Dijkstra, and RRT, face challenges in dynamic environments. The RRT* algorithm, while asymptotically optimal, exhibits computational inefficiencies due to random sampling. This paper presents an APF-RRT* hybrid algorithm that leverages APF’s directional guidance and RRT*’s optimality to enhance performance.
Key contributions:
- Integration of APF’s target attraction and obstacle repulsion into RRT*.
- Redundant node elimination using greedy algorithms.
- Path smoothing via cubic B-spline curves for kinematic compliance.
2. Methodology
2.1 RRT* Framework
RRT* improves upon RRT by rewiring nodes to minimize path cost. For a new node XnewXnew, the algorithm:
- Identifies nearest neighbors within radius rr:Xnear={Xi∈T∣∥Xi−Xnew∥≤r}Xnear={Xi∈T∣∥Xi−Xnew∥≤r}
- Selects the parent node XparentXparent that minimizes cost:Xparent=argminXi∈Xnear(Cost(Xi)+∥Xi−Xnew∥)Xparent=argXi∈Xnearmin(Cost(Xi)+∥Xi−Xnew∥)
- Rewires the tree to optimize paths for neighboring nodes.
2.2 APF Integration
The APF component introduces gravitational and repulsive forces:
- Attractive Potential toward the goal XgoalXgoal:Uatt(X)=12ka∥X−Xgoal∥2Uatt(X)=21ka∥X−Xgoal∥2
- Repulsive Potential from obstacles:Urep(X)={12kr(1ρ(X)−1ρ0)2ρ(X)≤ρ00ρ(X)>ρ0Urep(X)=⎩⎨⎧21kr(ρ(X)1−ρ01)20ρ(X)≤ρ0ρ(X)>ρ0where ρ(X)ρ(X) is the distance to the nearest obstacle.
The resultant force guides RRT* sampling:Ftotal=−∇Uatt−∇UrepFtotal=−∇Uatt−∇Urep
2.3 Node Pruning and Smoothing
- Greedy Pruning: Redundant nodes are removed if the direct path between non-consecutive nodes is collision-free.
- Cubic B-spline Smoothing: Ensures C2C2 continuity for UAV kinematics:P(t)=∑i=0nPiFi,3(t)P(t)=i=0∑nPiFi,3(t)where Fi,3(t)Fi,3(t) are basis functions derived recursively.
3. Experimental Results
3.1 Simulation Setup
- Environment: 1000×1000 unit area with 8 circular obstacles.
- Parameters:ParameterValueAttraction gain kaka1Repulsion gain krkr1Step size20Safety margin ρ0ρ050
3.2 Performance Metrics
| Algorithm | Path Length | Time (s) | Nodes | Iterations |
|---|---|---|---|---|
| RRT* | 1624.7 | 13.67 | 55 | 804 |
| APF-RRT | 1651.2 | 9.47 | 57 | 1017 |
| APF-RRT* | 1379.8 | 8.69 | 34 | 653 |
Improvements over RRT*:
- 15.1% shorter paths, 36.4% faster planning.
- 38.2% fewer nodes, 18.8% fewer iterations.
3.3 Physical Validation
Tests on the QBot2e platform confirmed the algorithm’s real-world applicability, with smoother and shorter trajectories compared to baseline methods.
4. Conclusion
The APF-RRT* algorithm synergizes APF’s directional efficiency with RRT*’s optimality, achieving superior performance in UAV trajectory planning. Future work will extend the method to 3D environments and dynamic obstacles.
Keywords: UAV, APF, RRT*, trajectory planning, B-spline, node pruning.
Tables and Equations
Table 1: Obstacle parameters.
| Obstacle | Center | Radius |
|---|---|---|
| 1 | (200,500) | 120 |
| … | … | … |
Equation 1: Revised APF repulsion force:Frep=kr(1ρ−1ρ0)ρgnρ2Frep=kr(ρ1−ρ01)ρ2ρgn
Equation 2: B-spline basis function:Fi,k(t)=t−titi+k−tiFi,k−1(t)+ti+k+1−tti+k+1−ti+1Fi+1,k−1(t)Fi,k(t)=ti+k−tit−tiFi,k−1(t)+ti+k+1−ti+1ti+k+1−tFi+1,k−1(t)
This structured approach ensures clarity and reproducibility, aligning with the goal of advancing UAV autonomy.