© Y. Wu et al., published by EDP Sciences, 2024

1 Introduction

The widely used natural gas has greatly facilitates the daily life of residents, and a large number of the urban gas pipe networks have been laid underground [1]. However, the risk of leakage increases with the service life of the pipeline, especially in the valve wells, pressure regulator boxes and other pipe connections [2]. Gas leakage can lead to fire, explosion and other accidents, posing serious threats to human lives and property [3]. Under the background of the gradual expansion of urban natural gas pipe coverage, traditional manual inspection method can not meet the needs of daily gas safety supervision. The automatic mobile platforms equipped with gas sensors are a research hotspot of urban gas pipe network monitoring. Gas sensors such as methane gas sensors based on tunable diode laser absorption spectroscopy (TDLAS) technology, can be used to detect the natural gas leakage [4–7]. As an automatic mobile platform, quadruped robots have advantages in environmental adaptability and obstacle-crossing ability [8]. Quadruped robots can be programmed to perform specific operations, thus replacing manual labor for heavy, complex and dangerous inspection tasks [9]. Therefore, the quadruped robot is suitable for complex inspection objects including valve wells, transformer boxes and complex environments in urban residential areas. Automatic leakage detection based on quadruped robot platform is an effective means of urban gas pipeline inspection.

To realize autonomous inspection of natural gas pipe leakage in urban residential areas using quadruped robot, path planning technology is crucial. Path planning can be generally categorized into global path planning and local path planning [10]. Common global path planning algorithms include Dijkstra algorithm [11] and A* algorithm [12] based on graph search, as well as various heuristic methods [13–15]. However, these algorithms are prone to lose efficiency in complex environments [16]. The sampling-based rapid-exploration random tree (RRT) algorithm and its derivative, RRT*, are frequently employed to address path planning issues [17]. Although the RRT algorithm is simple in structure and fast in computation, it suffers from drawbacks such as poor convergence and non-optimal paths [18]. In contrast, the RRT* algorithm can find the asymptotic optimum, but exhibits relatively low path planning efficiency [19]. J.D. Gammell et al. proposed the informed RRT* algorithm(IRRT*) to enhance optimization efficiency by constructing a hyper-ellipsoidal space to constrain sampling [20]. Nevertheless, IRRT* still employs a fixed-step for path optimization, resulting in poor optimization accuracy.

Meanwhile, the real-time obstacle avoidance of quadruped inspection robots necessitates local path planning algorithms. The predominant methods currently in use are the artificial potential field method based on the potential fields [21], and the dynamic window algorithm (DWA) based on the velocity space [22]. The computation of velocity space in the DWA algorithm facilitates effective motion control, but it is prone to fall into the local minima.

To address the above challenges, a hybrid path planning algorithm combining optimized RRT* and DWA (ORRT*-DWA) is proposed to enhance the path planning capabilities of the quadruped robot in urban environment. The performance of the ORRT*-DWA algorithm is evaluated through simulation and the results are compared with RRT* algorithm and IRRT* algorithm. Additionally, field tests are conducted in an urban residential area to validate the effectiveness of the ORRT*-DWA algorithm, enabling a quadruped robot to autonomously detect urban gas pipe leakage.

2 ORRT*-DWA algorithm

2.1 ORRT* algorithm

2.1.1 Probability-based sampling strategy

RRT* algorithm works by incrementally growing a tree of connected nodes in a planned robot or system configuration space. It starts from a start point and iteratively builds the tree by randomly sampling points in the space and connecting those points to the nearest existing nodes in the tree until the tree grows to the goal point. This process ensures a thorough exploration of the configuration space, but causes the algorithm to explore a lot of useless space, which slows down the convergence of the algorithm. To further improve the search efficiency of the RRT* algorithm, uniform random sampling is replaced by probabilistic sampling following a Gaussian distribution. In this approach, the probability that a sample point X_rand is sampled in the state space X is inversely proportional to its Euclidean distance from the centerline, using the line connecting the start and goal points as the centerline. The probability density function is expressed in equation (1).

$$f(X_{rand})=\frac{1}{\sigma \sqrt{2\pi }}\exp (\frac{-d^2}{2{\sigma }^2})$$(1)

where d is the Euclidean distance from the sample point to the line connecting the start point and the target point, and σ is the standard deviation of the sampling probability of the sampling point.

Taking a two-dimensional space of size 40*40 as an example, set the start point and a goal point for path planning, and sample all unoccupied points in the state space. As shown in Figure 1, multiple sampling is performed in the state space, and the sampling points take the straight line connecting the initial point and the destination point as the center line, and the farther away from the center line, the sparser the sampling points. High probability sampling points close to the centerline enable the tree to grow faster towards the goal point, while low probability sampling points far from the connecting line give the algorithm the ability to get rid of the local optimum.

Fig. 1 Probability sampling.

2.1.2 Extended node filtering strategy

To improve the low efficiency of RRT* path optimization, this paper proposes a method where the to-be-expanded node X_wait is obtained by probabilistic sampling after the RRT* algorithm identifies the initial path. A screening strategy is then applied to the to-be-expanded node X_wait that passes the collision detection. First, the cost function f of the to-be-extended node is constructed to represent the cost of the path from the start point X_init through the to-be-extended node X_wait to reach the goal point X_goal, and the value of the cost function is computed using equation (2).

$$f\left(X_{wait}\right)=h(X_{wait},X_{init})+g(X_{wait},X_{goal})$$(2)

where the function h () is used to calculate the Euclidean distance between two points.

As shown in Figure 2, if the cost function value of X_wait, f(X_wait), is greater than the current path length, then any new path that passes through node X_wait (e.g., X_init→X₁→X₂→X_wait→X₃→X_goal) will have a path length greater than the current path length.

Therefore, the cost function value of X_wait is compared to the current path length, if f(X_wait) is less than the current path length then it is added to the tree node, otherwise it is discarded directly then re-sampling is conducted to attempt expanding new nodes. The screening strategy can avoid adding useless new nodes to the tree, thereby improving the efficiency of the path optimization.

Fig. 2 Schematic diagram of node filtering.

2.1.3 Adaptive step size strategy

The RRT* algorithm uses a fixed step size to expand the root node throughout the path planning process, so the step size directly affects the speed of path finding. A small step size will enhance the accuracy but sacrifice the time cost of the algorithm, while a large step size will accelerate initial pathfinding but reduce the efficiency of subsequent path optimization. To solve this problem, an adaptive step factor k is introduced in this paper, which satisfies equation (3).

$$\{\begin{array}{c}\hfill k=\max [0.5,\exp (-b\times {(t/T)}^a)]\hfill \\ \hfill step=k\times ste{p}_0\hfill \end{array}$$(3)

where b, a are the tuning parameters, t and T are the current and maximum number of iterations, and step₀ is the initial step size.

The step factor k decreases with the increase of search time. This step setting means a larger step size is used at the beginning of the algorithm, leading to quickly search for the initial path, and then a smaller step size in the middle and late stages to refine the path. Besides, the minimum step size is limited to half of the initial step size to prevent excessively small steps from huge computation. With an adaptive step size that changes over the number of iterations, the path can asymptotically converge to the optimal path faster.

2.2 ORRT*-DWA algorithm

The dynamic window algorithm mainly samples various velocities (including linear velocity v and angular velocity ω) in velocity space and uses these velocities to simulate the trajectories of the robot in a given time. After obtaining several sets of corresponding velocity trajectories, it evaluates them using certain evaluation rules and selects the corresponding velocity of the optimal trajectory to move the robot forward.

The traditional DWA algorithm utilizes the heading function heading(v,ω), the distance evaluation function dist(v,ω), and the velocity evaluation function vel(v,ω) to form an evaluation function G(v,ω). The heading evaluation function heading(v,ω) denotes the offset angle between the predicted trajectory and the goal. The distance evaluation function dist(v,ω) denotes the distance between the predicted trajectory and the obstacle. The velocity evaluation function vel(v,ω) denotes the current motion velocity. The evaluation function G(v,ω) is used to evaluate all predicted trajectories.

The main purpose of this paper is to realize local obstacle avoidance using DWA. In obstacle avoidance, the local path planned by the original DWA usually deviate from the global path, which leads to the deterioration of the global optimality of the path [23]. Therefore, to enhance the goal tracking capability of the robot, a new sub-evaluation function astar(v,ω) of the DWA algorithm is introduced, which is inspired by the heuristic function of the A* algorithm. The modified evaluation function G(v,ω) is shown in equation (4).

$$\{\begin{array}{c}\hfill \begin{array}{c}G(v,\omega )=\alpha \cdot normal(heading(v,\omega ))\\ +\beta \cdot normal(dist(v,\omega ))\\ +\gamma \cdot normal(vel(v,\omega ))\\ +\eta \cdot normal(astar(v,\omega ))\end{array}\hfill \\ astar(v,\omega )=h_1+h_2\hfill \end{array}$$(4)

where h₁ denotes the Euclidean distance between the current position of the robot and the end of the predicted trajectory, and h₂ denotes the Euclidean distance between the end of the predicted trajectory and the goal point. α, β, γ, η are the weight of each evaluation indicator. normal() denotes the normalization function.

After modifying the DWA algorithm, we combine it with ORRT* algorithm to create a hybrid path planning algorithm, the ORRT*-DWA algorithm. In the ORRT*-DWA algorithm, the ORRT* algorithm is used to plan the global optimal path, and the path nodes of the global path serve as intermediate guidance points for the DWA algorithm. The flow chart of the ORRT*-DWA algorithm is shown in Figure 3.

Fig. 3 ORRT*-DWA algorithm flowchart.

3 Comparison of algorithm simulation

3.1 ORRT* algorithm simulation

Two 300 m×300 m simulation environments were designed on the platform of MATLAB R2018a to compare the path planning capabilities of ORRT* with RRT, RRT* and IRRT*. The basic simulation parameter settings are shown in Table 1.

The four algorithms are first tested in a simple environment and the results are shown in Figure 4. In these visualizations, black areas represent obstacles while the folded lines connected by triangles depict the final paths planned by the algorithms. From Figure 4a, in the simple environment, the RRT algorithm demonstrates the longest and most tortuous path due to its lack of path optimization. Figures 4b and 4c showcase the RRT* and the IRRT* algorithm, which optimize the initial path to some extent. Despite these optimization efforts, the final path still suffers from the problem of being tortuous and long due to the inefficiencies of the optimization process. Figure 4d illustrates the performance of the ORRT* algorithm, which outperforms the other three algorithms in terms of final planned paths for the same number of iterations. This superiority is attributed to the utilization of multiple strategies aimed at enhancing the efficiency of path optimization.

Next, the performance of the four algorithms is tested in a complex environment, and the results are shown in Figure 5. In Figure 5a, the RRT algorithm is the least effective, producing the most inefficient path. Figures 5b and 5c display the performance of the RRT* and the IRRT* algorithms, respectively. As the complexity of the environment increases, these algorithms exhibit worse path planning outcomes compared to the simple environment, with paths becoming more tortuous and less optimal. In Figure 5d, the ORRT* algorithm still maintains a superior path planning result. Despite the increased environmental complexity, this algorithm continues to generate paths that are closer to the asymptotically optimal route, demonstrating its robustness and efficiency in more challenging scenarios.

Considering the contingency of a single experiment, several experiments were conducted on each of the four algorithms in a complex environment. The average results were recorded in Table 2.

In Table 2, the ORRT* algorithm demonstrates the ability to find the initial path faster due to its probabilistic sampling strategy. The adaptive step size and extended node filtering strategy effectively improve the efficiency of the path optimization, allowing for better path planning within the same number of iterations. Compared with IRRT* algorithm, the number of iterations required to find the initial path is reduced by 8.28% and the final path length is decreased by 4.22% in complex environments. These results indicate that the ORRT* algorithm has better robustness than the other three algorithms.

Fig. 4 Simulation of path planning in simple environment. (a) RRT algorithm. (b) RRT* algorithm. (c) IRRT* algorithm. (d) ORRT* algorithm.

Fig. 5 Simulation of path planning in complex environment. (a) RRT algorithm. (b) RRT* algorithm. (c) IRRT* algorithm. (d) ORRT* algorithm.

3.2 ORRT*-DWA algorithm simulation

After global path planning, the quadruped inspection robot still needs to achieve local obstacle avoidance. To test the performance of the ORRT*-DWA algorithm, dynamic path planning simulations are conducted in a 42 m × 42 m simulation environment with unknown obstacles. The ORRT*-DWA algorithm is compared with the DWA algorithm and the A*-DWA algorithm. The simulation results are shown in Figure 6 and 7.

In Figure 6a, the robot is guided to the goal point through the traditional DWA algorithm primarily using the azimuth evaluation subfunction. Obstacles encountered along the way can easily cause the robot to deviate into a path farther from the goal point, resulting in a longer final path. In Figures 6b and 6c, both the A*-DWA algorithm and the ORRT*-DWA algorithm enable the robot to travel along the global path while avoiding obstacles. However, the ORRT*-DWA algorithm benefits from the better global path generated by the ORRT*, leading to a shorter overall path for the robot.

The lengths of the global path and the actual traveling path using the three algorithms with different goal points are recorded in Table 3.

In Table 3, the DWA algorithm, lacking global path guidelines, results in final path lengths of 50.57 m and 62.75 m, which are significantly longer than those produced by the A*-DWA algorithm and the ORRT*-DWA algorithm. Specifically, the ORRT*-DWA algorithm reduces the global path length by 8.9% and the final path length by 4.2% compared to the A*-DWA fusion algorithm. The ORRT*-DWA algorithm is proved to enable the robot to reach the goal point with a shorter path and to effectively achieve dynamic avoidance of unknown obstacles, outperforming the other two algorithms.

Fig. 6 Simulation results[ Xinit= (38,7); Xgoal= (4,25)]. (a) DWA. (b) A*-DWA. (c) ORRT*-DWA.

Fig. 7 Simulation results[ Xinit= (38,7); Xgoal= (4,30)]. (a) DWA. (b) A*-DWA. (c) ORRT*-DWA.

4 Field test

4.1 Test site

To verify the effectiveness of the ORRT*-DWA algorithm in the autonomous detection of gas pipe leakage in urban residential areas by a quadruped robot, we conducted a path planning test. The test site is located in a 100 m×50 m residential area in China. The 3D overhead map and the natural gas pipe network map of the test site are shown in Figure 8.

The quadruped robot used in this test is shown in Figure 9. The quadruped robot is equipped with lidar to sense the external environment. Before the path planning test is started, a 2D map of the test area is constructed using simultaneous localization and mapping (SLAM) technology. SLAM is a technique used in robotics and computer vision to construct a map of an unknown environment while simultaneously keeping track of an agent's location within that environment. The map is shown in Figure 10.

Fig. 8 3D overhead map of the test site and gas pipe network map. (a) 3D overhead map. (b) gas pipe network map.

Fig. 9 Quadruped robot used in the test.

Fig. 10 2D environmental map and key points.

4.2 Global path planning test

First, the valve well is used as the initial point of the path and the pressure regulator box as the goal point of the path, both circled in Figure 10. The IRRT* algorithm and the ORRT* algorithm are applied to carry out global path planning tests, respectively, and the experimental results are shown in Figure 11.

In Figure 11a, the IRRT* algorithm successfully plans the path, but due to its lower optimization efficiency, the final global path is zigzagged with a path length of 63.8 m. In Figure 11b, the ORRT* algorithm, which incorporates a variety of improved strategies, successfully plans a smoother global path. The path length of the ORRT* algorithm is 57.6 m, representing a 9.7% reduction in path length compared to the IRRT* algorithm. From the overall perspective, the path planned by the ORRT* algorithm is smoother and avoids passing through narrow areas. Between the same initial point and goal point, a shorter and smoother path can save time, energy costs, and reduce the risk of collision between the robot and obstacles.

Fig. 11 Global path planning test. (a) IRRT* algorithm. (b) ORRT* algorithm.

4.3 Local obstacle avoidance test

Then, to test the dynamic obstacle avoidance ability of the quadruped robot, an experimenter is arranged to stand on the inspection path as an unknown obstacle, and the experimental results are shown in Figure 12. In Figure 12, the quadruped robot follows the global path until encountering an unknown obstacle. Upon an unknown obstacle is detected with its lidar, the quadruped robot successfully avoids it. After bypassing obstacles, the quadruped robot resumes moving towards the next intermediate guidance point of the global path. This proves that the ORRT^*-DWA algorithm can enable the quadruped robot to inspect and avoid obstacles, maintaining an optimal path.

The main component of natural gas is methane (CH₄), with a content of about 90%. During the test, natural gas leakage are simulated using natural gas bags placed near the valve well. The methane concentration of the natural gas bags is between 400 and 1500 ppm.m (100 ppm.m means: 100 ppm of the CH₄ is evenly distributed in an air mass of 1 m thickness). The quadruped robot equipped with a TDLAS methane sensor inspects the area following the path planned by the ORRT*-DWA algorithm. As shown in Figure 13, the quadruped robot is able to autonomously inspect between the valve well and the pressure regulator box with a reasonable path. During the inspection, the TDLAS methane sensor successfully detected a methane gas leakage with a concentration of about 800 ppm.m near the valve well. This proves the feasibility of using the quadruped robot, applying the ORRT*-DWA path planning algorithm proposed in this paper, for autonomous inspection of natural gas leakage at the key nodes (pressure regulator box, valve well et al.) in urban natural gas pipe.

Fig. 12 Path planning with unknown obstacle.

Fig. 13 Autonomous inspection of natural gas leakage using quadruped robot.

5 Conclusion

To solve the path planning problem of a quadruped robot for urban natural gas leak detection, a hybrid path planning algorithm combining ORRT* and DWA (ORRT*-DWA) is proposed. The ORRT* algorithm can plan inspection paths more efficiently, allowing the quadruped robot to inspect the target area more quickly, thereby reducing inspection time and costs. The DWA algorithm can help the quadruped robot avoid obstacles in real time during the inspection process, ensuring safety and effectiveness. And the ORRT*-DWA combines the advantages of the two algorithms. The performance of the ORRT*-DWA algorithm was tested through simulations, demonstrating a reduction of 8.9% in the global planning path length and 4.2% in the actual traveling path length compared to the traditional algorithm. Subsequently, path planning experiments were conducted in a 100 m × 50 m urban residential area. The ORRT*-DWA algorithm achieved a 9.7% reduction in planning path length compared to the IRRT* algorithm. Simultaneously, a simulated gas leakage inspection test was performed alongside the path planning test. The effectiveness of the ORRT*-DWA algorithm, applied in the quadruped robot with the TDLAS methane sensor is successfully verified for autonomous inspection of urban gas pipe leakage.

Funding information

This research was supported by National Key Research and Development Program of the China (No. 2023YFF0611600) and the “Leading Talents Program” of Zhejiang Province Key Research and Development Program (No. 2022C03179).

Conflict of interest

We declare that there is no conflict of interest in this paper.

Data availability statement

The data that have been used are confidential.

Author contribution statement

Writing-original draft: Yuhang Wu, Qiang Wang, Yao Xiao. Writing-review and editing: Yun Song. Resources: Wei Mao, Peng Wang.

References

All Tables

All Figures

	Fig. 1 Probability sampling.
In the text

	Fig. 2 Schematic diagram of node filtering.
In the text

	Fig. 3 ORRT*-DWA algorithm flowchart.
In the text

	Fig. 4 Simulation of path planning in simple environment. (a) RRT algorithm. (b) RRT* algorithm. (c) IRRT* algorithm. (d) ORRT* algorithm.
In the text

	Fig. 5 Simulation of path planning in complex environment. (a) RRT algorithm. (b) RRT* algorithm. (c) IRRT* algorithm. (d) ORRT* algorithm.
In the text

	Fig. 6 Simulation results[ Xinit= (38,7); Xgoal= (4,25)]. (a) DWA. (b) A*-DWA. (c) ORRT*-DWA.
In the text

	Fig. 7 Simulation results[ Xinit= (38,7); Xgoal= (4,30)]. (a) DWA. (b) A*-DWA. (c) ORRT*-DWA.
In the text

	Fig. 8 3D overhead map of the test site and gas pipe network map. (a) 3D overhead map. (b) gas pipe network map.
In the text

	Fig. 9 Quadruped robot used in the test.
In the text

	Fig. 10 2D environmental map and key points.
In the text

	Fig. 11 Global path planning test. (a) IRRT* algorithm. (b) ORRT* algorithm.
In the text

	Fig. 12 Path planning with unknown obstacle.
In the text

	Fig. 13 Autonomous inspection of natural gas leakage using quadruped robot.
In the text