Application and Performance Evaluation of a UAV Navigation System Based on D* Algorithm for Substation Inspection

The stability and security of modern power grids are heavily dependent on the regular and reliable inspection of substations. Traditional manual inspection methods are not only time-consuming and labor-intensive but also face significant limitations when dealing with complex layouts, hazardous conditions, or adverse weather. In recent years, Unmanned Aerial Vehicle (UAV) technology has emerged as a transformative tool for infrastructure inspection. Within China, the application of UAVs, or “China UAV drones,” for power grid maintenance has seen rapid development, offering the promise of increased efficiency, enhanced safety, and access to hard-to-reach areas. The autonomous inspection of substations using China UAV drones represents a significant step towards intelligent grid operation and maintenance.

However, achieving truly autonomous and safe navigation for UAVs within the confined and cluttered environment of a substation presents considerable challenges. Substations are dense with electrical equipment such as transformers, circuit breakers, busbars, and insulators, creating a complex three-dimensional obstacle field. Furthermore, unforeseen dynamic threats like maintenance vehicles, personnel, or even birds can appear unexpectedly. A navigation system for a China UAV drone in this context must not only find an efficient initial path but also possess the capability for real-time, dynamic re-planning to avoid collisions while ensuring the completion of the inspection mission. Therefore, the core of a reliable autonomous inspection system lies in its path planning algorithm, which must be both computationally efficient and highly adaptive to environmental changes.

Among the various path planning algorithms, the D* (Dynamic A*) algorithm is particularly noted for its strengths in dynamic environments. Unlike its predecessor, the A* algorithm, which performs a complete re-planning from scratch when the environment changes, D* is an incremental search algorithm. It efficiently re-plans only the affected portions of the path by propagating cost changes backwards from the point of alteration. This characteristic makes it highly suitable for scenarios where a China UAV drone must frequently adjust its course in response to newly detected obstacles. While foundational research has explored D* for robotic navigation, its application specifically for China UAV drone navigation in the unique and high-stakes environment of electrical substations requires tailored adaptations and a comprehensive performance evaluation against established benchmarks.

This paper addresses the critical need for safe and efficient autonomous inspection by proposing and evaluating a UAV navigation system specifically designed for substation environments, with the D* algorithm at its core. The primary contributions are threefold: First, we design an integrated intelligent inspection system architecture and a standardized operational workflow, enabling a seamless transition from task dispatch to data recovery. Second, we detail the implementation of the D* algorithm with necessary adaptations for UAV dynamics and substation constraints. Finally, we conduct extensive simulation experiments within a realistically modeled substation digital twin to rigorously assess the performance of our D*-based system. Key evaluation metrics, including path efficiency, completion time, collision rate, and safety margin, are compared against classic algorithms like A* and RRT*, demonstrating the superior adaptability and safety of the D* algorithm for ensuring the reliable operation of China UAV drones in complex, dynamic inspection tasks.

System Architecture and Operational Workflow

The proposed intelligent inspection system is designed as a hierarchical, cloud-edge coordinated architecture to facilitate the autonomous operation of China UAV drones across multiple substations. The system comprises several key components that work in concert to execute inspection missions safely and efficiently.

The Remote Monitoring Center serves as the central command hub. Operators at this center are responsible for high-level mission planning, defining inspection targets (e.g., specific equipment, zones), setting mission priorities, and scheduling inspections for a fleet of China UAV drones across different substations. The Cloud Management Platform acts as the operational brain. It receives tasks from the monitoring center, manages the digital models (digital twins) of substations, processes inspection data, and hosts the core path planning and mission management algorithms. The UAV Nest is a ground-based station deployed at or near the substation. It provides secure storage, automatic battery charging/swapping, and a protected launch/landing platform for the China UAV drone. The nest also houses edge computing units for preliminary data processing and ensures reliable communication. The UAV itself is equipped with necessary sensors (visual, LiDAR, thermal), navigation systems (GNSS, IMU), and onboard computers to execute flight control and perform local obstacle detection. Finally, a robust Communication Network (often combining 4G/5G and dedicated radio links) ensures stable, low-latency data exchange between all components, which is critical for real-time control and monitoring of the China UAV drone.

The operational workflow is designed to be fully automated, from task initiation to post-mission analysis. The process is summarized in the following step-by-step description:

Task Planning & Static Path Generation: The Cloud Platform receives an inspection task. It first loads the pre-built 3D model (digital twin) of the target substation and the list of inspection points. Using an initial global path planner (which could be A* or an initial run of D* on the static map), it generates a safe, collision-free nominal flight path, avoiding all known static obstacles like buildings and equipment.
Mission Upload & Pre-flight Checks: The planned route and inspection commands are uploaded to the designated UAV Nest. The nest performs automated pre-flight checks, verifying weather conditions (wind, precipitation), UAV system health (battery, sensors, communications), and ensuring the airspace is clear.
Autonomous Launch & Navigation: Upon passing all checks, the China UAV drone autonomously takes off from the nest and climbs to a predetermined safe altitude. It then switches to autonomous navigation mode, following the pre-planned static path towards the first inspection target.
Dynamic Re-planning & Inspection Execution: During flight, the UAV’s onboard sensors continuously scan the environment. If a dynamic obstacle (e.g., a vehicle) is detected, the D* algorithm is triggered in real-time. It incrementally re-plans the path from the UAV’s current position, circumventing the new obstacle. Once the UAV reaches a designated inspection point, it automatically adjusts its gimbal to capture the required imagery (visual, thermal) of the equipment.
Task Iteration & Data Logging: After completing an inspection, the China UAV drone proceeds to the next target point in its queue, repeating the navigation and inspection process. All captured data is timestamped, geotagged, and stored locally with periodic uploads to the cloud.
Autonomous Return & Data Sync: After completing all inspection points, the UAV autonomously returns to the nest and executes a precision landing. Immediately upon landing, it initiates the upload of all mission data to the Cloud Platform and begins automatic battery charging, preparing for the next mission.

This closed-loop, automated workflow minimizes human intervention, standardizes operations, and maximizes the availability and utility of the China UAV drone fleet for substation inspection.

**D* Algorithm: Principle and Adaptive Implementation for UAV Navigation**

The D* algorithm is the core enabler for dynamic path planning in our proposed system. Its primary advantage over traditional graph search methods is its ability to efficiently repair paths when the cost map changes, without needing to recompute the entire solution from scratch. This is ideal for a China UAV drone navigating an environment where new obstacles can appear unpredictably.

At the heart of D* is the maintenance of two key values for each state (or node) $ s $ in the search space:
$$ g(s) $$: The actual cost-to-come from the start node to node $ s $ based on the currently known information.
$$ rhs(s) $$: A one-step lookahead value, defined as:
$$ rhs(s) = \begin{cases}
0 & \text{if } s = s_{goal} \\
\min_{s’ \in Pred(s)}(g(s’) + c(s’, s)) & \text{otherwise}
\end{cases} $$
where $ Pred(s) $ is the set of predecessors of $ s $, and $ c(s’, s) $ is the cost of moving from $ s’ $ to $ s $. A node is called consistent if $ g(s) = rhs(s) $. If $ g(s) > rhs(s) $, it is overconsistent (its cost can be lowered), and if $ g(s) < rhs(s) $, it is underconsistent (its cost has increased, typically due to an obstacle).

D* uses a priority queue sorted by a 2-dimensional key function $ Key(s) $ to efficiently process nodes:
$$ Key(s) = [k_1(s), k_2(s)] = [\min(g(s), rhs(s)) + h(s), \min(g(s), rhs(s))] $$
Here, $ h(s) $ is a heuristic estimate of the cost from $ s $ to the goal (e.g., Euclidean distance). The queue is sorted lexicographically by $ k_1 $ then $ k_2 $. This ordering ensures that nodes which are both potentially closer to the goal (via the heuristic) and have a lower known cost are processed first.

The algorithm operates in two main phases. The first phase is identical to A*: it performs a backward search from the goal to the start, computing initial $ g $ values and finding an optimal path under the initial map conditions. The second, dynamic phase is triggered when an arc cost change (e.g., an obstacle appears) is detected. The algorithm updates the $ rhs $ value for the affected node and, if it becomes inconsistent, places it back into the priority queue. It then processes nodes from the queue, propagating cost changes and restoring consistency for affected parts of the graph, effectively repairing the path from the robot’s (UAV’s) current position.

For application to a China UAV drone in a substation, several adaptations are crucial:

State Space and Cost Function: The state $ s $ is defined as $ (x, y, z) $ in 3D space. The cost function $ c(s’, s) $ must incorporate not just Euclidean distance but also penalties for proximity to obstacles (to enforce a safety margin), energy consumption, and adherence to UAV dynamic constraints (e.g., turning radius, climb rate). A sample cost function can be:
$$ c(s’, s) = w_d \cdot \|s’ – s\|_2 + w_p \cdot \sum_{o \in O} \frac{1}{\text{dist}(s, o)^2} $$
where $ w_d $ and $ w_p $ are weights, and $ O $ is the set of obstacles.
Map Representation & Update: The substation environment is discretized into a 3D voxel grid or an octree. When the UAV’s sensors (LiDAR, vision) detect a new obstacle, the corresponding voxels are marked as “occupied,” and their traversal cost is set to infinity. The D* algorithm is notified of these specific cost changes, initiating the local re-planning process.
Integration with UAV Control: The output of the D* planner is a series of waypoints. These are fed into the UAV’s trajectory tracker and flight controller, which generate the actual motor commands. The planning cycle (sensing → re-planning → commanding) must run at a frequency high enough to ensure reactivity. For a China UAV drone, a cycle time of 100-500ms is typically targeted.

The following pseudo-code summarizes the core process function of the D* algorithm as implemented for the UAV system:

Procedure Process-State(D* Graph)

$ s = $ Pop node with lowest key from priority queue $ U $.
If $ g(s) > rhs(s) $ Then // Overconsistent node
1. $ g(s) = rhs(s) $
2. For each neighbor $ s’ $ in $ Succ(s) $: Update $ rhs(s’) $ and its key in $ U $.
Else If $ g(s) < rhs(s) $ Then // Underconsistent node (cost increased)
1. $ g_{old} = g(s) $
2. $ g(s) = \infty $
3. For each neighbor $ s’ $ in $ Succ(s) \cup \{s\} $: Update $ rhs(s’) $ and its key in $ U $.
End If

Experimental Design and Evaluation Methodology

To rigorously evaluate the performance of the D* algorithm within our proposed UAV navigation system, we designed a comprehensive simulation experiment based on a high-fidelity digital twin of a typical 110kV/220kV outdoor substation. Simulation allows for safe, repeatable, and extensive testing under a wide variety of challenging conditions that would be risky or impractical to create in the field with a physical China UAV drone.

Simulation Environment Setup:
We constructed a multi-layered digital twin that captures the essential complexities of a real substation:

Spatial-Topological Layer: A 3D model (80m x 80m area) was built using point cloud data, accurately representing major static obstacles: transformer clusters (6m x 4m x 5m), circuit breaker arrays (1.2m spacing), busbar galleries, and steel structures.
Electromagnetic Layer: To simulate real-world navigation challenges for a China UAV drone, we modeled GPS signal attenuation and multi-path effects caused by large metal structures, based on empirical data from substation environments.
Dynamic Element Layer: This layer introduces unpredictability. We defined several dynamic obstacle types:
- Random Patrol Vehicles: Simulating maintenance traffic moving along predefined service roads at 5-15 km/h.
- Personnel: Randomly spawning and moving human figures within designated walkways.
- Sudden Obstacles: Simulating the temporary appearance of equipment like cherry pickers or cargo in unexpected locations.

The evaluation focused on two challenging composite scenarios designed to stress-test the navigation system:

Dense Equipment Zone Navigation: The China UAV drone must navigate through a congested area filled with transformers and insulators, requiring precise 3D path planning with tight safety margins (>1.5m).
Multi-Vehicle Dynamic Scenario: The UAV must complete its inspection while avoiding 2-3 other simulated patrol vehicles moving in the same area, testing real-time collision avoidance and cooperative awareness.

Algorithm Parameters and Benchmarks:
Our D* based system (D*-UAV) was compared against two well-established path planning algorithms adapted for the same task:

A* Algorithm: A classic optimal graph search algorithm. It replans the entire path from the current position whenever the map changes. It serves as a baseline for path optimality but is expected to be slower in dynamic settings.
RRT* Algorithm: A sampling-based probabilistically optimal algorithm known for handling high-dimensional spaces well. It continuously grows a tree of possible paths. While good for complex static environments, its convergence to an optimal path can be slow, and its reaction to dynamic changes may not be as immediate as D*.

The key parameters for each algorithm in our simulations are listed below:

Algorithm	Parameter	Value/Setting
D*	Consistency Threshold ($ \epsilon $)	0.01
	Max Re-planning Iterations	500
	Safety Buffer Radius	0.5 m
A*	Heuristic Function	Euclidean Distance
	Heuristic Weight	1.2
	Re-planning Trigger	On any map change
RRT*	Search Radius	3.0 m
	Goal Bias	0.05
	Max Tree Nodes	2000

Performance Metrics:
The performance of each algorithm was evaluated using the following quantitative metrics, each critical for assessing the viability of a China UAV drone for autonomous substation inspection:

Path Efficiency ($ \eta $): Measures the quality of the flown path compared to the theoretical optimal (shortest collision-free path on the static map). It is calculated as:
$$ \eta = \frac{L_{optimal}}{L_{actual}} $$
where $ L_{optimal} $ is the length of the shortest known feasible path, and $ L_{actual} $ is the total length of the path actually flown by the UAV. A value closer to 1.0 indicates higher efficiency.
Mission Completion Time ($ T_{total} $): The total simulation time from mission start until the UAV returns to the nest. This includes flight time, time spent re-planning, and inspection time at each point. Lower times indicate a more efficient system.
Collision Rate ($ R_{coll} $): The most critical safety metric. It is defined as the number of simulation runs where the UAV’s body volume intersected with any obstacle, divided by the total number of simulation runs. A rate of 0% is the ideal target for a China UAV drone operating near high-voltage equipment.
Average Safety Margin ($ M_{safe} $): Evaluates the “caution” of the planned path. It is the average minimum Euclidean distance between the UAV’s center point along its trajectory and any obstacle (static or dynamic) throughout the mission. A larger margin indicates a safer, more robust path.
$$ M_{safe} = \frac{1}{N} \sum_{i=1}^{N} \min_{o \in O} \| p_{uav}(i) – p_o \|_2 $$
where $ N $ is the number of trajectory points, $ O $ is the set of all obstacles, and $ p $ denotes position.

Each simulation scenario was run 50 times per algorithm to gather statistically significant results, with dynamic obstacles following randomized but repeatable patterns to ensure fair comparison.

Simulation Results and Comparative Analysis

The simulation experiments yielded comprehensive data on the performance of the three navigation algorithms. The results clearly demonstrate the distinct advantages of the D* algorithm in managing the dynamic complexities of a substation environment for a China UAV drone.

Qualitative Path Analysis:
The initial global planning phase on the static map produced sensible paths for all algorithms. A* typically found the shortest geometric path, RRT* produced a more wandering but feasible path, and D*’s initial solution was similar to A*. The critical difference emerged when dynamic obstacles were introduced. The D* algorithm efficiently performed local repairs, creating smooth deviations around the new obstacle before seamlessly re-joining the original planned route. In contrast, the A* algorithm, upon detecting a change, would halt and compute an entirely new global path from its current position, often leading to longer pauses and less smooth trajectory changes. The RRT* algorithm struggled with real-time adaptation; its tree needed significant regrowth to incorporate the new obstacle, resulting in delayed reactions and sometimes erratic path changes during the regrowth phase. This qualitative behavior underscores D*’s suitability for the continuous, fluid navigation required by an inspection China UAV drone.

Quantitative Performance Comparison:
The aggregated results from the 50 simulation runs for each algorithm in the composite dynamic scenario are presented in the table below. These metrics provide a solid foundation for comparing the effectiveness of each approach.

Performance Metric	*D Algorithm (Proposed)**	*A Algorithm**	*RRT Algorithm**
Path Efficiency ($ \eta $)	0.92 ± 0.03	0.88 ± 0.05	0.85 ± 0.07
Avg. Completion Time ($ T_{total} $)	287.4 s ± 12.1 s	312.8 s ± 25.7 s	334.5 s ± 41.3 s
Collision Rate ($ R_{coll} $)	5%	12%	10%
Avg. Safety Margin ($ M_{safe} $)	2.3 m ± 0.2 m	1.8 m ± 0.3 m	2.0 m ± 0.4 m

Analysis of Results:

Path Efficiency: The D* algorithm achieved the highest average path efficiency (0.92). This indicates that despite the need for dynamic detours, its incremental repair mechanism allows it to stay very close to the globally optimal path. A*’s full re-plans sometimes led to slightly less optimal detours in the immediate term, while RRT*’s probabilistic nature and slower convergence resulted in the least efficient paths on average.
Mission Completion Time: The D*-based system completed missions fastest on average (287.4s). This speed advantage stems from its computational efficiency during re-planning; it updates only a small part of the graph rather than re-exploring the entire space like A*, and it does not need to regrow a large tree like RRT*. Faster completion is crucial for the operational throughput of a China UAV drone, allowing more inspections per battery charge.
Collision Rate: This is the most significant result from a safety perspective. The D* algorithm reduced the collision rate to 5%, outperforming both A* (12%) and RRT* (10%). The lower collision rate directly translates to higher operational safety and reliability for the China UAV drone. The primary reason is D*’s swift and localized response to threats. A*’s complete re-planning creates a latency window where the UAV may continue on an old, now-dangerous path. RRT*’s reaction is often too slow to avoid fast-approaching dynamic obstacles.
Safety Margin: The paths generated by D* maintained the largest average distance from obstacles (2.3m). This can be attributed to the cost function design that penalizes proximity to obstacles. Because D* re-plans incrementally from a previously safe and cost-optimized path, it tends to preserve this “cautious” buffer. The higher safety margin provides an extra layer of protection against sensor inaccuracies and control errors, which is essential for the safe integration of China UAV drones into critical infrastructure.

The superior performance of D* in collision rate and safety margin is particularly noteworthy. For a China UAV drone operating in a high-risk environment like a substation, where a collision could cause severe damage to expensive equipment or lead to power outages, minimizing even a few percentage points in collision probability is of immense practical value. The D* algorithm’s architecture inherently supports this safety-first approach through its efficient and reactive local path repair mechanism.

Conclusion

This study has presented a comprehensive approach to enabling autonomous substation inspection using UAVs, with a specific focus on solving the critical challenge of dynamic path planning in cluttered and unpredictable environments. The proposed system, centered on the D* algorithm, demonstrates a viable pathway towards safer, more efficient, and intelligent grid maintenance utilizing China UAV drone technology.

The primary contributions and findings are summarized as follows: Firstly, we designed an integrated cloud-edge system architecture and a fully automated operational workflow. This structured framework ensures that the China UAV drone can execute complex inspection missions from launch to data recovery with minimal human intervention, forming the backbone for scalable, intelligent substation inspection. Secondly, we detailed the implementation of the D* algorithm, highlighting the necessary adaptations for 3D UAV navigation and substation-specific constraints, such as incorporating safety margins into the cost function. The algorithm’s core strength—incremental re-planning—was successfully leveraged to address the key limitation of static planners in dynamic settings.

Finally, and most significantly, through rigorous simulation within a high-fidelity digital twin of a substation, we quantitatively evaluated the system’s performance. The results unequivocally show that the D*-based navigation system outperforms classic A* and sampling-based RRT* algorithms in the context of dynamic substation inspection. Key metrics reveal that the D* algorithm achieved the lowest collision rate (5%) and the largest average safety margin (2.3m), while also maintaining high path efficiency and the fastest mission completion times. This combination of safety and efficiency is paramount for the practical deployment of China UAV drones in sensitive industrial environments.

In conclusion, the integration of the D* algorithm into the navigation stack of inspection UAVs provides a robust solution to the problem of real-time obstacle avoidance in complex, dynamic spaces like electrical substations. It enhances the operational safety and reliability of China UAV drones, moving the industry closer to the vision of fully autonomous, continuous grid asset monitoring. Future work will focus on testing the system with physical UAV platforms in controlled field environments, integrating more advanced sensor fusion techniques for robust obstacle detection, and exploring multi-drone cooperative planning strategies to further improve inspection coverage and efficiency for China’s evolving smart grid infrastructure.