Sage Journals: Discover world-class research

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.

Keywords

Intelligent substation inspection robot path planning dynamic obstacles improved A* algorithm improved dynamic window approach algorithm

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 (n) = g (n) + h (n)

(1)

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

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

h (n) = \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 $Y {K_{i}, 1 \leq i \leq 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 Δ t)$ .The inspection robot’s velocity $(v_{t + 1}, ω_{t + 1})$ at $t + 1$ should satisfy the following constraints:

{\begin{matrix} v_{t} - a_{v . \max} t \leq v_{t + 1} \leq v_{t} + a_{v . \max} t \\ ω_{t} - a_{ω . \max} t \leq ω_{t + 1} \leq v_{t} + a_{ω . \max} t \end{matrix}

(3)

In equation (3), $v_{t}$ represents the linear velocity, and $ω_{t}$ denotes its angular velocity. The parameters $a_{v . \max}$ and $a_{ω . \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, ω) = K [α H (v, ω) + β D (v, ω) + γ V (v, ω)]

(4)

In equation (4), $H (v, ω)$ denotes the target azimuth angle; $D (v, ω)$ denotes the minimum distance; $V (v, ω)$ represents the current forward speed of the inspection robot; $α$ , $β$ , and $γ$ 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, ω)$ and design an evaluation function that is more suitable for intelligent substation inspection scenarios. Replace $H (v, ω)$ with flowing equation:

H_{1} = \arctan 2 (y_{t} - y_{0}, x_{t} - x_{0}) - θ_{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 $θ_{t}$ denotes the inspection robot’s facing angle.

Improved DWA algorithm evaluation function:

G (v, ω) = K [α H_{1} (v, ω) + β D (v, ω) + γ D (v, ω) + δ O_{b s} (v, ω)]

(6)

In equation (6), $O_{bs} (v, ω)$ measures the distance from the inspection robot’s trajectory to obstacles and reflects the robot’s ability to avoid them. $δ$ denotes the weighting coefficient of the $O_{bs} (v, ω)$ function, and the optimal local path is obtained when the value of $G (v, ω)$ is obtained as the smallest. The simulation parameter settings for the DWA-based inspection robot are $v_{\max} (m / s)$ = 1.0, $ω_{\max} (rad / s)$ = 0.2375, $a_{v . \max} (m / s^{2})$ = 3.0, $a_{ω . \max} (rad / s^{2})$ = 0.2386, $Δ t (s)$ =0.1, $α$ = 0.6, $γ$ = 0.5, and $δ$ = 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 m \times 5 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.

Footnotes

Author contributions

All authors contributed to the study conception and design, data collection and analysis were performed by Wei Zhang, Wanli Li, Xiang Zheng and Bing Sun. The first draft of the manuscript was written by Wei Zhang and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the National Natural Science Foundation of China under Grant 52271321 and Natural Science Foundation of Shanghai under Grant 22ZR1426700.

Data availability

Within the scope of this study, all utilized data and relevant materials are available upon request from the authors.

ORCID iD

Wei Zhang

References

Gaspar

Cruz

Lam

, et al. Smart substation communications and cybersecurity: a comprehensive survey. IEEE Commun Surv Tutorials 2023; 25(4): 2456–2493.

Javaid

Haleem

Singh

, et al. Substantial capabilities of robotics in enhancing industry 4.0 implementation. Cogn Robot 2021; 1: 58–75.

Dai

Jiang

, et al. Robot path planning based on artificial potential field with deterministic annealing. ISA Transact 2023; 138: 74–87.

Liu

Wang

Yang

, et al. Path planning techniques for mobile robots: review and prospect. Expert Sys Appl 2023; 227: 120254.

Gao

Zhang

Path optimization of welding robot based on ant colony and genetic algorithm. J Appl Math 2022; 2022: 88–99.

de Castro, Gabriel

Milena

F. Pinto

, et al. Dynamic path planning based on neural networks for aerial inspection. J Cont Autom Elect Sys 2023; 34(1): 85–105.

, et al. Deep reinforcement learning with dynamic window approach based collision avoidance path planning for maritime autonomous surface ships. Ocean Eng 2023; 284: 115208.

Reda

Onsy

Haikal

, et al. Path planning algorithms in the autonomous driving system: a comprehensive review. Robot Auton Sys 2024; 174: 104630.

Zeng

Zhao

, et al. Research on global path planning algorithm for mobile robots based on improved A. Expert Sys Appl 2023; 20: 122922.

10.

Wang

Mutahira

Kim

, et al. ABA*–Adaptive bidirectional A* algorithm for aerial robot path planning. IEEE Access 2023; 11: 103521–103529.

11.

Chen

Tan

Research on path planning of three-neighbor search A* algorithm combined with artificial potential field. Int J Adv Robot Sys 2021; 18: 17298814211026449.

12.

Fransen

van Eekelen

Efficient path planning for automated guided vehicles using A*(Astar) algorithm incorporating turning costs in search heuristic. Int J Prod Res 2023; 61(3): 707–725.

13.

Yahia

Mohammed

AS.

Path planning optimization in unmanned aerial vehicles using meta-heuristic algorithms: a systematic review. Environ Monit Assess 2023; 195(1): 30.

14.

Razzaq Abdul Wahhab

O. A

Al-Araji

A. S

. Path planning and control strategy design for mobile robot based on hybrid swarm optimization algorithm. Int J Intell Eng Sys 2021; 14(3): 565–579.

15.

Wang

, et al. Research on AGV task path planning based on improved A* algorithm. Virtual Real Intell Hardware 2023; 5(3): 249–265.

16.

Chang

Shan

Jiang

, et al. Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment. Auton Robots 2021; 45: 51–76.

17.

Zhong

Tian

, et al. Hybrid path planning based on safe A* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment. J Intell Robot Syst 2020; 99: 65–77.

18.

Yang

Teng

Mobile robot path planning based on enhanced dynamic window approach and improved A* algorithm. J Robot 2022; 1: 2183229.

19.

Gong

Tahir

, et al. Towards path planning algorithm combining with A-star algorithm and dynamic window approach algorithm. Int J Adv Comp Sci Appl 2023; 14(6): 45.

20.

Xing

Fan

, et al. Research on robot path planning by integrating state-based decision-making A* algorithm and inertial dynamic window approach. Intell Serv Robot 2024; 45: 1–14.

21.

Guan

Wang

Autonomous collision avoidance of unmanned surface vehicles based on improved A-star and dynamic window approach algorithms. IEEE Intell Transport Sys Mag 2023; 15(3): 36–50.

22.

Fox

Burgard

Thrun

The dynamic window approach to collision avoidance. IEEE Robot Autom Mag 1997; 4(1): 23–33.

23.

Wang

, et al. Research on adaptive obstacle avoidance algorithm of robot based on DDPG-DWA. Comp Elect Eng 2023; 109: 108753.

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

Abstract

Keywords

Introduction

Improved A* algorithm

Traditional A* algorithm

The improved A* algorithm

Enhanced DWA algorithm

Traditional DWA algorithm

Inspection robot kinematics model

Traditional DWA algorithm evaluation function

Improved DWA Algorithm

Fusion strategy of improved A* and enhanced DWA

Simulation analysis

Fixed-point inspection path planning

Multi-point traversal inspection path planning

Path planning under emergency condition

Conclusion

Footnotes

Author contributions

Declaration of conflicting interests

Funding

Data availability

ORCID iD

References