In the field of autonomous robotics, path planning is a fundamental task that enables machines to navigate from a start point to a goal while optimizing specific performance criteria. For quadrotor unmanned aerial vehicles (UAVs), this process is particularly challenging due to their dynamic flight characteristics and operational constraints. Traditional path planning methods for quadrotors often focus on single objectives, such as minimizing path length or maximizing safety, but real-world scenarios require balancing multiple, often conflicting, goals. These include path length, smoothness, and safety, which are influenced by uncertainties like sensor errors, environmental noise, and random disturbances. In this paper, we address these challenges by proposing a novel multi-objective path planning algorithm for quadrotors that integrates fuzzy entropy and cloud model to handle uncertainties and optimize multiple criteria simultaneously.
Quadrotor UAVs have gained prominence in various applications, including surveillance, delivery, and environmental monitoring, due to their agility and versatility. However, their path planning must account for factors like energy efficiency, flight stability, and obstacle avoidance. Single-objective approaches are insufficient because optimizing one goal often degrades others; for instance, a shorter path may increase collision risk or require more turns, leading to inefficiencies. Multi-objective optimization provides a framework to balance these trade-offs, but it must incorporate uncertainties inherent in quadrotor operations. We introduce a method that combines fuzzy entropy, which quantifies uncertainty in fuzzy sets, with cloud model, which captures both fuzziness and randomness, to determine optimal weight coefficients for the objectives. Subsequently, we employ particle swarm optimization (PSO) to find Pareto-optimal paths, ensuring comprehensive performance evaluation.
The core of our approach lies in modeling the quadrotor’s path planning as a multi-objective optimization problem with three key criteria: path length, sum of turning angles, and total hazard degree. Path length minimization reduces energy consumption and flight time, which is critical for quadrotor endurance. The sum of turning angles affects the quadrotor’s stability and control efficiency, as frequent turns necessitate speed adjustments. The total hazard degree quantifies the risk of collision with obstacles, considering sensor inaccuracies and environmental uncertainties. By formulating these objectives mathematically and leveraging fuzzy entropy-cloud model for weight allocation, we achieve a robust path planning solution that adapts to real-world complexities. Simulation results demonstrate that our method outperforms traditional techniques, offering lower energy consumption, higher efficiency, and improved safety for quadrotor navigation.
Multi-objective Path Planning Model for Quadrotor
We begin by constructing a multi-objective path planning model for quadrotor UAVs using a grid-based environment representation. The environment is discretized into cells, with obstacles marked, and the quadrotor must traverse from a start point $(x_s, y_s)$ to a goal point $(x_g, y_g)$. A path is defined as a sequence of nodes $P = \{(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)\}$, where $k$ is the total number of nodes, including start and goal. The optimization objectives are designed to reflect practical quadrotor operational needs, and their mathematical formulations are as follows.
The first objective is path length minimization, which directly impacts the quadrotor’s energy usage and mission duration. For a path with nodes $(x_i, y_i)$, the total length $f_1$ is computed as the sum of Euclidean distances between consecutive nodes:
$$f_1 = \sum_{i=1}^{k-1} L(i, i+1) = \sum_{i=1}^{k-1} \sqrt{(x_i – x_{i+1})^2 + (y_i – y_{i+1})^2}$$
The second objective is to minimize the sum of turning angles, which promotes smoother paths and reduces control efforts for the quadrotor. The turning angle $\theta(i, i+1, i+2)$ at node $i+1$ is the angle between the vectors from $i$ to $i+1$ and from $i+1$ to $i+2$. The cumulative sum $f_2$ is given by:
$$f_2 = \sum_{i=1}^{k-2} \theta(i, i+1, i+2) = \frac{\pi}{180} \sum_{i=1}^{k-2} \arccos \left( \frac{(x_{i+1} – x_i)(x_{i+2} – x_{i+1}) + (y_{i+1} – y_i)(y_{i+2} – y_{i+1})}{\sqrt{(x_{i+1} – x_i)^2 + (y_{i+1} – y_i)^2} \cdot \sqrt{(x_{i+2} – x_{i+1})^2 + (y_{i+2} – y_{i+1})^2}} \right)$$
The third objective is total hazard degree minimization, which enhances safety by penalizing proximity to obstacles. Given the quadrotor’s sensor limitations, we consider hazard significant only within two grid cells of an obstacle. Let $L(i, \text{obj})$ be the distance from node $i$ to the nearest obstacle center; then, the total hazard $f_3$ is:
$$f_3 = \sum_{i=1}^{k} \frac{2}{L(i, \text{obj})} \quad \text{for} \quad L(i, \text{obj}) \leq 2$$
The overall multi-objective evaluation function $F$ integrates these objectives with weight coefficients $w_1$, $w_2$, and $w_3$, which represent their relative importance. Let $f_1’$, $f_2’$, and $f_3’$ be the ideal minimum values of $f_1$, $f_2$, and $f_3$, respectively. Then, $F$ is defined as:
$$F = w_1 |f_1 – f_1’| + w_2 |f_2 – f_2’| + w_3 |f_3 – f_3’|$$
where $0 < w_1, w_2, w_3 < 1$ and $w_1 + w_2 + w_3 = 1$. The weights are determined using the fuzzy entropy-cloud model to account for uncertainties in quadrotor operations.
| Objective | Symbol | Mathematical Formulation | Purpose |
|---|---|---|---|
| Path Length | $f_1$ | $\sum_{i=1}^{k-1} \sqrt{(x_i – x_{i+1})^2 + (y_i – y_{i+1})^2}$ | Minimize energy and time |
| Sum of Turning Angles | $f_2$ | $\frac{\pi}{180} \sum_{i=1}^{k-2} \arccos \left( \frac{(x_{i+1} – x_i)(x_{i+2} – x_{i+1}) + (y_{i+1} – y_i)(y_{i+2} – y_{i+1})}{\sqrt{(x_{i+1} – x_i)^2 + (y_{i+1} – y_i)^2} \cdot \sqrt{(x_{i+2} – x_{i+1})^2 + (y_{i+2} – y_{i+1})^2}} \right)$ | Enhance stability and smoothness |
| Total Hazard Degree | $f_3$ | $\sum_{i=1}^{k} \frac{2}{L(i, \text{obj})}$ for $L(i, \text{obj}) \leq 2$ | Improve safety |
Fuzzy Entropy-Cloud Model for Uncertainty Handling
Uncertainties in quadrotor path planning arise from various sources, such as sensor inaccuracies, environmental dynamics, and computational errors. These uncertainties exhibit both fuzziness (imprecise information) and randomness (probabilistic variations). To address this, we propose a hybrid approach that combines fuzzy entropy and cloud model. Fuzzy entropy measures the uncertainty in fuzzy sets, while cloud model provides a bridge between qualitative concepts and quantitative data, capturing both fuzziness and randomness through probabilistic membership functions.
Fuzzy entropy is applied to the time series data of each objective function derived from quadrotor operations. For a time series $u(1), u(2), \dots, u(N)$ of length $N$, we reconstruct the phase space with dimension $m$ to analyze its complexity. The reconstructed vectors $X_m(i)$ are defined as:
$$X_m(i) = \{u(i), u(i+1), \dots, u(i+m-1)\} – u_0(i)$$
where $u_0(i) = \frac{1}{m} \sum_{j=0}^{m-1} u(i+j)$ is the local mean. This reconstruction helps in capturing the dynamic behavior of the quadrotor’s path-related data.
Cloud model is characterized by three numerical parameters: expected value $Ex$, entropy $En$, and hyper-entropy $He$. $Ex$ represents the central value of the qualitative concept (e.g., average path length), $En$ measures the dispersion or uncertainty range, and $He$ describes the uncertainty of $En$, indicating randomness. For a given input $x$, the cloud model generates a membership degree $\mu_A(x)$ using a normal distribution-based function:
$$\mu_A(x) = \exp \left( -\frac{(x/r – Ex)^2}{2E_n’^2} \right)$$
where $r$ is the similarity tolerance (typically set between 0.1 and 0.25), and $E_n’$ is a normal random number with mean $En$ and variance $He$. This function replaces traditional fuzzy membership functions, as it incorporates randomness through $E_n’$.
To compute fuzzy entropy with cloud model, we first define the maximum absolute distance $d_{ij}^m$ between reconstructed vectors $X_m(i)$ and $X_m(j)$:
$$d_{ij}^m = \max_{p=1,2,\dots,m} \left| \left( u(i+p-1) – u_0(i) \right) – \left( u(j+p-1) – u_0(j) \right) \right|$$
The cloud-based fuzzy membership function $A_{ij}^m$ is then:
$$A_{ij}^m = \exp \left( -\frac{(d_{ij}^m / r – Ex)^2}{2E_n’^2} \right)$$
For each $i$, we calculate the average $C_i^m(r)$ over all $j \neq i$:
$$C_i^m(r) = \frac{1}{N-m} \sum_{j=1, j \neq i}^{N-m+1} A_{ij}^m$$
Then, we define $\Phi^m(r)$ as the mean of $C_i^m(r)$ values:
$$\Phi^m(r) = \frac{1}{N-m+1} \sum_{i=1}^{N-m+1} C_i^m(r)$$
The fuzzy entropy based on cloud model (FuzzyEn) is finally computed as:
$$\text{FuzzyEn}(m,r,N) = \ln \Phi^m(r) – \ln \Phi^{m+1}(r)$$
This FuzzyEn value quantifies the uncertainty in each objective function for the quadrotor. Higher FuzzyEn indicates greater complexity and uncertainty, which influences the weight allocation in the multi-objective model. The weights $w_1$, $w_2$, and $w_3$ are proportional to the FuzzyEn values, ensuring that objectives with higher uncertainty receive appropriate emphasis in the optimization.
| Parameter | Description | Typical Value |
|---|---|---|
| $Ex$ | Expected value (center of concept) | Calculated from data |
| $En$ | Entropy (uncertainty range) | $\sqrt{\frac{\pi}{2} \times \frac{1}{n} \sum_{i=1}^{n} |x_i – Ex|}$ |
| $He$ | Hyper-entropy (uncertainty of $En$) | $\sqrt{S^2 – E_n^2}$, where $S^2$ is sample variance |
| $r$ | Similarity tolerance | 0.1 to 0.25 |
Particle Swarm Optimization for Multi-objective Path Planning
Particle swarm optimization (PSO) is an evolutionary algorithm inspired by social behavior, such as bird flocking, and is well-suited for multi-objective optimization due to its efficiency in searching large solution spaces. In our approach, we employ multi-objective PSO to solve the path planning problem for quadrotor UAVs, focusing on finding a set of Pareto-optimal paths that balance the objectives of path length, turning angles, and hazard degree.
In PSO, a swarm of particles represents potential paths, with each particle’s position encoding a sequence of nodes in the grid environment. The velocity and position of each particle are updated iteratively based on personal and global best solutions. The update equations for particle $i$ in dimension $d$ at iteration $t$ are:
$$v_{id}(t+1) = w \cdot v_{id}(t) + c_1 r_1 (p_{id} – x_{id}(t)) + c_2 r_2 (g_d – x_{id}(t))$$
$$x_{id}(t+1) = x_{id}(t) + v_{id}(t+1)$$
where $v_{id}$ is the velocity, $x_{id}$ is the position, $p_{id}$ is the personal best position, $g_d$ is the global best position, $w$ is the inertia weight, $c_1$ and $c_2$ are acceleration coefficients, and $r_1$, $r_2$ are random numbers in [0,1]. For quadrotor path planning, the position $x_{id}$ corresponds to the coordinates of path nodes, and the velocity influences the direction of path exploration.
To handle multiple objectives, we use a Pareto-based approach where solutions are compared based on non-domination. A path $A$ dominates path $B$ if $A$ is better in at least one objective and not worse in all others. The algorithm maintains an archive of non-dominated solutions, which form the Pareto front. The steps of the multi-objective PSO for quadrotor path planning are as follows:
- Initialization: Generate a swarm of $M$ particles with random positions and velocities within the grid environment. Set personal bests and initialize the global best archive.
- Evaluation: For each particle, compute the objective functions $f_1$, $f_2$, and $f_3$ based on the encoded path. Calculate the evaluation function $F$ using weights from the fuzzy entropy-cloud model.
- Non-domination Check: Update the personal best for each particle if the current position is non-dominated. Update the global best archive by adding non-dominated solutions and removing dominated ones.
- Velocity and Position Update: Adjust velocities and positions using the update equations. Ensure that new positions remain within feasible grid cells, avoiding obstacles.
- Termination: Repeat steps 2-4 until the maximum iteration count $T_{\text{max}}$ is reached. Output the Pareto-optimal set from the global best archive.
The final path selection from the Pareto set is based on the minimum value of $F$, which incorporates the optimized weights. This ensures that the chosen path for the quadrotor balances all objectives effectively, considering uncertainties.
| Parameter | Symbol | Value |
|---|---|---|
| Swarm size | $M$ | 150 |
| Maximum iterations | $T_{\text{max}}$ | 300 |
| Inertia weight | $w$ | 0.7 |
| Acceleration coefficients | $c_1$, $c_2$ | 2.0 |
| Random numbers | $r_1$, $r_2$ | Uniform in [0,1] |
Simulation Experiments and Results Analysis
We conducted extensive simulations in MATLAB to evaluate the performance of our proposed fuzzy entropy-cloud model based multi-objective PSO (FEC-MOPSO) for quadrotor path planning. The environment was a 30×30 grid with obstacles randomly placed, start point at (0.5, 0.5), and goal point at (29.5, 29.5). Parameters for the fuzzy entropy-cloud model were set as: time series length $N=1000$, phase space dimension $m=2$, similarity tolerance $r=0.3$, and cloud drop number $CN=1500$. For PSO, we used swarm size $M=150$ and maximum iterations $T_{\text{max}}=300$.
We compared our method against two baseline approaches: standard fuzzy entropy based multi-objective PSO (FE-MOPSO) and single-objective PSO (SO-PSO) that minimizes only path length. The evaluation metrics included path length, sum of turning angles, total hazard degree, and the overall evaluation function $F$. Table 4 presents a comparison of typical paths obtained from each method, highlighting the trade-offs between objectives.
| Method | Path Length | Sum of Turning Angles (°) | Total Hazard Degree | Evaluation Function $F$ |
|---|---|---|---|---|
| FEC-MOPSO (Proposed) | 52.90 | 10.99 | 118 | 46.5 |
| FE-MOPSO | 56.07 | 10.99 | 130 | 51.2 |
| SO-PSO | 50.97 | 13.35 | 138 | 55.8 |
As shown, our FEC-MOPSO method achieves a balanced performance, with moderate path length, low turning angles, and reduced hazard degree, resulting in the lowest $F$ value. In contrast, SO-PSO yields the shortest path but higher turning angles and hazard, indicating poor smoothness and safety. FE-MOPSO performs better than SO-PSO but worse than FEC-MOPSO, demonstrating the advantage of incorporating cloud model for uncertainty handling.
To further analyze the multi-objective nature, we examined the Pareto-optimal set generated by FEC-MOPSO. Table 5 lists four representative Pareto-optimal paths, illustrating the diversity of solutions available for the quadrotor.
| Path ID | Path Length | Sum of Turning Angles (°) | Total Hazard Degree |
|---|---|---|---|
| 1 | 52.90 | 10.99 | 118 |
| 2 | 58.48 | 6.28 | 134 |
| 3 | 55.65 | 7.85 | 104 |
| 4 | 51.55 | 12.56 | 124 |
Path 1 offers a balance between length and hazard, Path 2 prioritizes smoothness with minimal turns, Path 3 emphasizes safety with the lowest hazard, and Path 4 focuses on shortness. This variety allows the quadrotor to select a path based on specific mission requirements, such as energy conservation or risk avoidance.
The convergence behavior of the evaluation function $F$ over iterations is depicted in Figure 1. Our FEC-MOPSO converges faster and to a lower value compared to FE-MOPSO and SO-PSO, indicating efficient optimization and better handling of uncertainties. The equation for $F$ convergence can be modeled as:
$$F(t) = F_{\text{min}} + (F_0 – F_{\text{min}}) e^{-\alpha t}$$
where $F_0$ is the initial value, $F_{\text{min}}$ is the minimum value, and $\alpha$ is the convergence rate. For FEC-MOPSO, $\alpha$ is higher, leading to quicker stabilization.
Additionally, we evaluated the robustness of our method by introducing random noise in the obstacle positions and sensor data. The fuzzy entropy-cloud model effectively adapted to these uncertainties, maintaining consistent path quality. In contrast, FE-MOPSO and SO-PSO showed significant degradation in hazard degree and turning angles under noisy conditions. This underscores the importance of our approach for real-world quadrotor applications where uncertainties are prevalent.
Conclusion
In this paper, we have presented a comprehensive multi-objective path planning algorithm for quadrotor UAVs that integrates fuzzy entropy and cloud model to address uncertainties in optimization. By formulating path length, sum of turning angles, and total hazard degree as key objectives, we developed a model that reflects practical quadrotor operational needs. The fuzzy entropy-cloud model enables dynamic weight allocation, capturing both fuzziness and randomness in the data, while multi-objective PSO efficiently explores the solution space to generate Pareto-optimal paths. Simulation results confirm that our method outperforms traditional approaches, providing paths that are energy-efficient, smooth, and safe for quadrotor navigation.
The proposed approach offers several advantages for quadrotor applications: it handles real-world uncertainties robustly, allows flexible path selection based on mission priorities, and ensures overall performance optimization. Future work will extend this method to three-dimensional environments, incorporate dynamic obstacles, and integrate real-time sensor data for adaptive path planning. Additionally, we plan to explore other evolutionary algorithms and uncertainty models to further enhance the quadrotor’s autonomy and reliability in complex scenarios.