Improved A* and DWA fusion algorithm based path planning for intelligent substation inspection robot

Abstract

To solve the intelligent substation inspection robot path planning with low global efficiency, search node redundancy, and may even fail under a dynamic obstacle environment, which is normally based on the A* or dynamic window approach (DWA) algorithms. This study attempted to use the improved A* algorithm and an enhanced DWA algorithms for intelligent substation inspection robot path planning to improve its path planning ability under dynamic inspection. In this study, The neighborhood traversal rule of the A* is refined, and the DWA evaluation function is adjusted to align with the specific demands of intelligent substation inspection. Simulation results demonstrate that combining the improved A* algorithm with the enhanced DWA significantly reduces the inspection path length by 24.4% compared to traditional A* in fixed point inspection condition. This integration greatly enhances the dynamic path-planning performance of substation inspection robots, particularly in terms of path smoothness and inspection efficiency.

Introduction

With the optimization and upgrading of the power grid structure and the continuous expansion of the scale of the power system, intelligent substations are an important part of the power grid, ¹ and the security and reliability of their power supply directly affect the operation of the power grid. To ensure secure and reliable operation of an intelligent substation, the equipment in the substation must be inspected. Recently, more and more inspection robots are being used for substation inspection as the robotics industry continues to evolve and become more intelligent. ²

Traditional robot path planning algorithms include the simulated annealing algorithm, ³ A* algorithm, ⁴ genetic algorithm, ⁵ neural network algorithm, ⁶ and dynamic window approach (DWA) algorithms. ⁷ However, the A* algorithm suffers from low efficiency and requires many search nodes. ⁸ Xu et al. ⁹ investigated an improved A* algorithm that replaced the traditional obstacle-free area with a rectangular boundary. This approach reduced the time consumption and improved the efficiency of the algorithm by allowing bidirectional exploration from both the starting point and the target point. Wang et al. ¹⁰ explored an adaptive bidirectional A* algorithm designed to reduce path planning time. Chen et al. ¹¹ introduced A* integrated with artificial potential fields, aiming to reduce path planning time and minimize the number of search nodes. There are also some studies on the A* combined with the heuristic method^12,13 to determine the shortest path planning and improve its efficiency. Razzaq et al. ¹⁴ combined A-star algorithm with chaotic particle swarm optimization algorithm to find the shortest planning path. To satisfy the requirements for path smoothness, Wang et al. ¹⁵ applied the Bezier curve theory to smooth the path.

Although many researchers have studied algorithms that integrate the A* algorithm, the problem of robot path planning with dynamic obstacles in complex environments remains unsolved. The DWA is an effective method for dynamic obstacle path planning, ¹⁶ but tends to get trapped in local optimal solutions. Recently, researchers have been investigating robot path planning methods integrate the A* with the DWA. Zhong et al. ¹⁷ introduced a composite path planning procedure that implements the A* algorithm with an adaptive window approach to achieve global path planning, timely tracking, and obstacle prevention for mobile robots in large-scale and dynamic environments. An enhanced DWA with the A* algorithm has been proposed ¹⁸ to help robots avoid obstacles and track targets in complex environments. Li et al. ¹⁹ proposed a routing method that fuses the A* algorithm with DWA technology, enhancing the A* through a subnode optimization technique to address issues such as low global path planning reliability and susceptibility to deadlock. Xing ²⁰ developed an algorithm that combines A* with an inertial window approach to improve navigation in confined environments. Guan and Wang ²¹ presented an upgraded A* method for USV path planning along with an optimized dynamic window approach for conflict rejection. However, they are less likely to consider the characteristics of power substations and the potential encounter of dynamic obstacles during the inspection process, this study focuses on dynamic path-planning methods for inspecting robot.

At present, there are few studies on substation inspection robot path planning, and the influence of dynamic obstacles in the inspection process and the path planning problem under emergency working conditions are not considered. In this paper, Sections “Enhanced DWA algorithm” and “Fusion strategy of improved A* and enhanced DWA” describe the improved A* algorithm and the enhanced DWA, respectively. Subsequently, a fusion strategy of improved A* and enhanced DWA was presented. The proposed algorithm-based dynamic path planning for a substation inspection robot with dynamic obstacles for urgent tasks during the inspection process is simulated and analyzed in Section “Simulation analysis.” Finally, Section “Conclusion” presents the conclusions.

Improved A* algorithm

Traditional A* algorithm

A* algorithm as the most commonly used path search algorithm. It describes the path between two points on a map using a cost function, and uses a recursive search to determine the shortest path that minimizes the cost. The A* algorithm is evaluated as:

$$f\left(n\right)=g\left(n\right)+h\left(n\right)$$

(1)

As shown in equation (1): $n$ represents the current node, $f\left(n\right)$ represents the evaluation function of the inspection robot, $g\left(n\right)$ represents the actual generation value from the starting node of the inspection robot to the current node, $g\left(n\right)$ means the actual cost for the inspection robot from the start node to the current node, while $h\left(n\right)$ describes the estimated cost from the current node $n$ to the target node.

This paper uses the Euclidean distance as the heuristic function $h\left(n\right)$ in equation (2).

$$h\left(n\right)=\sqrt{{(x_1-x_2)}^2+{(y_1-y_2)}^2}$$

(2)

The improved A* algorithm

In most cases, the A* algorithm is in accordance with the eight search directions for selecting the expansion node; in some redundant search directions, the redundancy of the search direction will result in too many planning nodes, resulting in too many path turns, making each section of the planning path too short, resulting in the inspection robot moving the process of traveling a very short distance and lagging. The improved A* is used to make the path of the intelligent substation inspection robot smoother.

Firstly, optimize the A* neighborhood traversal rule. In other words, among the eight possible movement directions of the inspection robot, the direction opposite to the target node is eliminated, while the direction aligned with it is retained, thereby improving the efficiency of the A* algorithm. According to Figure 1, in the selection of the moving direction of the Type I node, note 1–8 total eight selection directions. By positional relationship between current node and target node, 1, 3, 5, and 7 are defined as type I target nodes; 2 and 6 are defined as type II target nodes; and 4 and 8 are defined as type III target nodes. When the position of the target node conforms to Type I, moving direction 7 opposite to 3 and moving directions 6 and 8 adjacent to the left and right of 7 are eliminated.

Figure 1.

Node movement direction.

Secondly, a key node extraction algorithm is proposed. This method focuses on retaining essential nodes that must be included in the planned path while filtering out redundant nodes in the A* algorithm. This process aims to shorten and smooth the path generated by the A* algorithm. The concrete steps are as follows.

(1) Full node is obtained. set $\mathbf{Y}\{{\mathbf{K}}_i,1\le i\le n\}$ planned by the A* algorithm after optimizing the traversal rule, where $K_1$ denotes the starting node, and $K_n$ denotes the target node. (2) Creating a key node. Set G to store the key nodes optimized by the algorithm. (3) Delete co-located nodes. Starting from the starting point $K_1$ along the planned path, to determine whether the next node and the current node are on the same straight line, if they are co-located, the previous node is considered as a redundant node that can be deleted, and it is not included in the key node set $G$ . Instead, it is included. (4) Delete redundant folds. Connect the current key node and the next key node based on key node set G after step (3). If this segment of the connecting line does not pass through the obstacle, and the obstruction is greater than the safe distance (set to $\sqrt{2}/4$ for subsequent simulations), the key node $K_i$ is retained. If it does not satisfy the requirement, it continues to verify that the connecting line with the next key node $K(i+1)$ satisfies the requirement. This step is repeated until the requirement to retain the key node is met. (5) Sequentially connect all nodes in the key node set G to complete the path planning after optimizing the A* algorithm. Figure 2 demonstrates the optimization effect of the key nodes, where the black dotted line represents the distance between the key points.

Figure 2.

Key node extraction schematic.

Enhanced DWA algorithm

In the complex inspection environment of intelligent substation inspection robots, this study explores dynamic path planning by integrating the improved A* for global path planning with the enhanced DWA for local dynamic path planning.

Traditional DWA algorithm

Inspection robot kinematics model

Fox ²³ introduced the DWA algorithm, which transforms the position control problem of a moving inspection robot into a velocity control problem. Specifically, the linear and angular velocities of the inspection robot are discretely sampled within the allowable velocity range, and the trajectories of these velocity combinations are simulated and evaluated using a function over a forward prediction time $T(T=10~30\mathrm{\Delta }t)$ .The inspection robot’s velocity $(v_{t+1},{\omega }_{t+1})$ at $t+1$ should satisfy the following constraints:

$$\{\begin{array}{c}{v}_t-a_{v.\max }t\le v_{t+1}\le v_t+a_{v.\max }t\hfill \\ {\omega }_t-a_{\omega .\max }t\le {\omega }_{t+1}\le v_t+a_{\omega .\max }t\hfill \end{array}$$

(3)

In equation (3), $v_t$ represents the linear velocity, and ${\omega }_t$ denotes its angular velocity. The parameters $a_{v.\max }$ and $a_{\omega .\max }$ correspond to the maximum linear and angular accelerations, respectively, determined by the inspection robot performance.

Traditional DWA algorithm evaluation function

The DWA algorithm predicts the next step based on the robot’s model and finds the best path using equation (4).

$$G(v,\omega )=K[\alpha H(v,\omega )+\beta D(v,\omega )+\gamma V(v,\omega )]$$

(4)

In equation (4), $H(v,\omega )$ denotes the target azimuth angle; $D(v,\omega )$ denotes the minimum distance; $V(v,\omega )$ represents the current forward speed of the inspection robot; $\alpha$ , $\beta$ , and $\gamma$ are the weighting factors; and $K$ denotes the degree of normalization.

Improved DWA Algorithm

The DWA algorithm has good avoidance capabilities, yet it easily falls into its own local optimum, ²² which leads to local path planning terminated near the obstacles and cannot reach the inspection target node. In this paper, we will improve the target azimuth evaluation $H(v,\omega )$ and design an evaluation function that is more suitable for intelligent substation inspection scenarios. Replace $H(v,\omega )$ with flowing equation:

$$H_1=\arctan 2(y_t-y_0,x_t-x_0)-{\theta }_t$$

(5)

In equation (5), $(x_0,y_0)$ denotes the current position of the inspection robot, $(x_t,y_t)$ indicates the target position of the inspection robot, and ${\theta }_t$ denotes the inspection robot’s facing angle.

Improved DWA algorithm evaluation function:

$$G\left(v,\omega \right)=K[\alpha H_1\left(v,\omega \right)+\beta D\left(v,\omega \right)+\gamma D\left(v,\omega \right)+\delta O_{bs}\left(v,\omega \right)]$$

(6)

In equation (6), $O_{\mathrm{bs}}(v,\omega )$ measures the distance from the inspection robot’s trajectory to obstacles and reflects the robot’s ability to avoid them. $\delta$ denotes the weighting coefficient of the $O_{\mathrm{bs}}(v,\omega )$ function, and the optimal local path is obtained when the value of $G(v,\omega )$ is obtained as the smallest. The simulation parameter settings for the DWA-based inspection robot are $v_{\max }(m/s)$  = 1.0, ${\omega }_{\max }(\mathrm{rad}/s)$  = 0.2375, $a_{v.\max }(m/s^2)$  = 3.0, $a_{\omega .\max }(\mathrm{rad}/s^2)$  = 0.2386, $\mathrm{\Delta }t\left(s\right)$  =0.1, $\alpha$  = 0.6, $\gamma$  = 0.5, and $\delta$  = 0.5.

Fusion strategy of improved A* and enhanced DWA

This study addresses the limitations of the A* and DWA algorithms for a substation inspection robot. The improved A* and DWA algorithms are combined to ensure optimal path planning.

As shown in Figure 3, the main steps of the fusion strategy are initializing the parameters of each node of the A* algorithm, establishing the full node set Y and the key node set G containing the starting node; then, select the node based on the optimization idea, first determining whether the node is co-located with the previous key node; if co-located, then do not select the node, if not continue to determine whether the node is a valid folding point; if so, the output is to the key node set G; otherwise, return the node to the full node set Y, and then return the node to the key node set G. Node to all node sets Y, output the best global key node set G and use it as the node input set of the enhanced DWA algorithm, and then use the enhanced DWA algorithm to further screen the key nodes, and finally judge whether the key node inspection path before the end point is the optimal one. If yes, the final inspection path is output, and vice versa.

Figure 3.

The proposed path planning method.

Simulation analysis

To evaluate the performance of the proposed algorithm in path planning for intelligent substation inspection robots, a simulation analysis was performed using MATLAB modeling of a substation. Figure 4 shows the substation grid map, where $1\times 1$ represents $5\mathrm{m}\times 5\mathrm{m}$ , black grids are the equipment areas of the intelligent substation, including the main control building, 10 kV main transformer, 220 kV equipment area, main transformer, 10 kV high voltage equipment area, and 220 kV equipment capacitor area, which are non-passable areas. White grids represent passable areas for the substation inspection robot, △ represents the starting point of the inspection robot, and is the destination point of the inspection robot.

Figure 4.

The substation inspection robot fixed-point path planning.

Fixed-point inspection path planning

A comparative simulation analysis was conducted to evaluate the performance improvements of the A* and DWA algorithms. This analysis includes the A*, DWA, and fusion algorithms in the context of path planning for intelligent substation inspection robots. The simulation evaluates path planning performance under fixed-point and emergency inspection conditions. Figure 4 illustrates fixed-point inspection, while Table 1 compares the substation robot’s path planning performance.

Table 1.

The comparison of substation robot path planning performance.

Inspection point	Algorithm	Path length (m)	Inflection points	Turning angle (°)
	Traditional A*	256.06	3	135.00
No. 1	Improved A*	252.49	1	62.90
Main	Traditional DWA	312.63	2	176.50
Transformer	Improved DWA	267.38	2	145.50
	The proposed method	249.32	1	126.00
	Traditional A*	764.62	8	360.00
10 kV	Improved A*	592.61	3	89.50
High voltage	Traditional DWA	716.32	6	179.60
Equipment	Improved DWA	667.51	4	172.50
Area	The proposed method	578.35	3	165.30

As shown in Figure 4 and supported by the data in Table 1, for the substation inspection robot planning the path from the starting point S (4.5,7.5) to the target point T1 (8.5,14.5) for the No. 1 Main Transformer inspection, the results based on different algorithms indicate that, compared to the traditional A* algorithm, the enhanced A* algorithm shortens the path, inflection points, and turning angle. However, the planned path does not maintain an adequate safe distance from the inspection equipment. The introduction of DWA algorithm, and its improvement, reduced the inspection path from 312.63 to 267.38 m by 14.5% in comparison to the traditional DWA. The proposed algorithm effectively shortens the inspection path, reduces the number of turns, and lowers the turning angles in comparison with to the traditional A*, resulting in a smoother path. A further comparative analysis of the path planning simulation from the inspection point S (4.5,7.5) to the 10 kV high-voltage equipment area T2 (21.5,19.5) shows that the proposed method outperforms the conventional. Specifically, inspection path shortened from 764.62 to 578.35 m, the path length shortened with 24.4% in comparison to the traditional A*, turning points reduced from 8 to 3, turning angle decreased from ${360}^{°}$ to $165.{30}^{°}$ .

Multi-point traversal inspection path planning

To verify the substation inspection robot’s path planning performance, followed by simulation to analyze the substation inspection robot multi-objective inspection and dynamic inspection conditions of the path planning performance.

Figure 5 illustrates the inspection robot multi-point traversal planning path. Starting from point A (3.5,7.5) at the control building, the robot proceeds to the 10 kV main transformer fixed-point inspection point B (5.5,17.5), then to the 220 kV equipment area fixed-point inspection point C (18.5,17.5), point D (21.5,19.5), No. 2 main transformer fixed-point inspection point E (18.5,11.5), No. 1 main transformer fixed-point inspection point F (11.5,11.5), and the 10 kV high-voltage equipment area fixed-point inspection point G (8.5,7.5), covering a total of six inspection target points. The robot then returns to the control building at point A, completing a multi-objective traversal inspection. This demonstrates that the proposed algorithm is capable of successfully executing the intelligent substation traversal inspection task. When random obstacles appear in the inspection process, it can realize dynamic routing, which verifies the proposed algorithm’s functionality in the multi task inspection.

Figure 5.

Inspection robot multi-point traversal path planning comparison.

Path planning under emergency condition

To further evaluate substations robot path planability with an improved fusion algorithm, we simulated and analyzed the robot’s dynamic path planning capabilities under emergency conditions.

Figure 6 illustrates that the blue and cyan squares represent random static and dynamic inspection obstacles. The inspection robot begins its task from point A. When performing an inspection at point C, the 10 kV high-voltage equipment at point G experiences an emergency fault. In response, the inspection robot adjusts its path, successfully avoiding both static and dynamic obstructions to reach point G. These results confirm that the fusion algorithm introduced in this study can effectively dynamically plan the inspection path even with random obstacles during emergency tasks, ensuring the inspection robot reaches the destination point. This confirms the algorithm’s superiority and practical applicability.

Figure 6.

Substation inspection path planning with emergency task.

Conclusion

A proposed method combining an improved A* and an enhanced DWA is used to optimize the path planning performance of substation inspection robots in dynamic environments. Comparative simulations were conducted to analyze the robot’s dynamic path planning capabilities across different scenarios, including fixed-point inspection, multi-target inspection, and emergency conditions, using the traditional A*, improved A*, traditional DWA, enhanced DWA, and the proposed fusion algorithm. Simulation results demonstrate that the intelligent substation inspection robot, utilizing the improved fusion algorithm, successfully completes inspection tasks while significantly reducing path length. Specifically, under fixed-point conditions, the enhanced DWA reduces the inspection path by 14.5% compared to the traditional DWA. Furthermore, the proposed fusion algorithm shortens the path length by 24.4% compared to the traditional A*. The fusion algorithm effectively avoids random obstacles and enables dynamic path planning in emergency conditions, highlighting its efficiency and adaptability.