introduction
As robotics technology matures and robot operating environments become more complex, path planning becomes a primary challenge for mobile robots as they move and complete assigned tasks in real-world environments. The optimal path, in essence, is a path found within the robot's workspace that is either the shortest route, the shortest travel time, or the lowest possible work cost, based on certain criteria or principles.
In recent years, solving the path planning problem for mobile robots in dynamic and unknown environments has been a persistent challenge. Many scholars both domestically and internationally have proposed effective planning algorithms, such as the artificial potential field method, ant colony optimization, random landmark map (PRM) method, and genetic algorithms. Tang et al. proposed treating dynamic obstacles as static over a period of time, allowing the path planning problem to be solved using a grid method, known as the dynamic grid method. Guo Yu applied the ant colony optimization algorithm to complex static environments, solving the collision avoidance problem in path planning and improving the efficiency of path search. Huai Chuangfeng et al. proposed using an autoregressive model to predict the trajectory of dynamic obstacles, and experiments have demonstrated that this model has good obstacle avoidance capabilities.
This paper employs a Support Vector Regression (SVR) model to predict dynamic obstacle trajectories, which offers better accuracy and timeliness. The artificial potential field method suffers from high computational complexity and slow execution speed, making it difficult to meet real-time requirements in complex, dynamic, and unknown environments. This paper combines the SVR and PRM algorithms for robot path planning, eliminating the need for precise mathematical modeling of obstacles in the workspace. Simulation experiments demonstrate that the proposed algorithm achieves good accuracy and real-time performance, effectively solving path planning problems in dynamic workspaces.
1. Algorithm Description
1.1 Support Vector Regression Machine
When the trajectory of a dynamic obstacle approaches linearity, consider using a linear regression function:
Table 1 Comparison of prediction errors for four kernel functions
t | j(mm 2 ) | m(m) | n(m) | a | R |
0 | 22.4133 | 0.0218 | 0.0003 | 0.0050 | 0.9306 |
1 | 120.3743 | 0.0194 | 0.0002 | 0.0263 | 0.5974 |
2 | 15.4970 | 0.0184 | 0.0001 | 0.0035 | 0.9798 |
3 | 21.7410 | 0.0221 | 0.0003 | 0.0047 | 0.9646 |
The experimental flowcharts for the training and test sets are shown in Figure 1.
Figure 1. Experimental flowchart for training and test sets.
2.3 Verify SVR
The author conducted experiments on an Intel(R) Core(TM) Duo-E7500 CPU and a Linux operating system with 16GB of memory. Since different kernel functions affect prediction accuracy, comparative experiments were conducted to select the support vector regression model that maximizes the squared correlation coefficient R while minimizing the errors of the aforementioned methods. Table 1 shows that the Gaussian kernel function minimizes the error between the predicted and actual values in the support vector regression model. To verify the advantages of the proposed algorithm, the results obtained after testing were compared with those of two commonly used prediction algorithms: backpropagation neural networks and autoregressive algorithms.
In the experiment of predicting the trajectory of dynamic obstacles, the same set of data was selected to test the three algorithms. The comparison of the relative error between the predicted value and the actual value is shown in Figure 2.
Figure 2. Experimental results of relative error comparison
As shown in Figure 2, the SVR algorithm has a smaller prediction error, while the BP neural network performs poorly. This may be because the optimal solution obtained by the neural network algorithm is not necessarily the global optimum, but rather a local optimum. The experimental results using the autoregressive algorithm are quite good, but not as accurate as the SVR algorithm.
Figure 3. Results of the timeliness comparison experiment.
The timeliness comparison results are shown in Figure 3. The SVR algorithm has a certain advantage in timeliness, that is, within a certain time, the SVR algorithm can predict the trajectory of dynamic obstacles more quickly.
2.3 Timeliness Comparison Test
Simulation experiments demonstrate the superiority of the SVR algorithm in predicting dynamic obstacle trajectories. A comparative experiment is then conducted on the PRM algorithm (integrated with SVR) and other algorithms in path planning. Under a dynamic, known environment, given initial and target positions, the proposed algorithm, ant colony algorithm, and dynamic grid method are used to plan the robot's path, and their timeliness is compared. Ten different initial and target positions are selected for experimental comparison, and the results are shown in Figure 4. Figure 4 shows that the proposed method combining SVR and PRM algorithms, compared to the ant colony algorithm and dynamic grid method, achieves the shortest path planning time, demonstrating better timeliness, and also plans the shortest path.
Figure 4 Comparison results of timeliness experiment
Experiments demonstrate that smaller grid sizes result in less environmental information storage, longer planning times, and a tendency towards the optimal path; therefore, timeliness and optimal path optimization cannot be simultaneously achieved. While ant colony optimization exhibits good robustness, it is prone to getting trapped in local optima and suffers from long planning times. Given the same initial and target positions, the algorithm presented in this paper achieves the shortest planning time.
3 Path Planning
This experiment was conducted on an Intel(R) Core(TM) Duo-E7500 CPU with 16GB of memory and a Linux operating system. By organically combining the SVR algorithm and the PRM algorithm, the path planning problem of robots in dynamic environments was effectively solved. The position information of dynamic obstacles was used as input to the support vector regression model. Then, the support vector regression model was used to predict the position information of the dynamic obstacles at the next moment. At this time, the dynamic obstacles can be regarded as instantaneously static, transforming the problem into instantaneous static path planning. To find the optimal path at this moment, the PRM algorithm can be used for path planning and the path can be updated in real time, ultimately achieving the optimal or near-optimal path from the starting point to the destination. To demonstrate the superiority of the algorithm presented in this paper, it was compared with the ant colony algorithm and the dynamic grid method. The simulation results are as follows.
Figure 5. Path planning using ant colony algorithm in static and dynamic environments.
Figure 6. Path planning using the dynamic grid method in both static and dynamic environments.
Figure 7 Path planning of the algorithm in this paper under static and dynamic environments.
The experiment was conducted in a simulation environment measuring 17 meters long and 15 meters wide, as shown in Figures 5, 6, and 7. The results of the robot's path planning using three algorithms were presented in both static and dynamic environments. In static environments, the planned path lengths were 16.03m, 15.14m, and 14.73m, respectively; in dynamic environments, the path lengths were 16.85m, 16.64m, and 15.4m, respectively. The results show that the algorithm presented in this paper plans the shortest path with better timeliness. It avoids the drawback of ant colony optimization (ACO) easily getting trapped in local optima and also avoids the difficulty in balancing environmental information storage and planning time in dynamic grid methods, thus approaching the optimal path more closely.
4. Summary
This paper conducts an in-depth study and analysis of the path planning problem for mobile robots in dynamic and unknown environments, and verifies the feasibility and timeliness of the proposed algorithm through extensive simulation experiments. The Support Vector Regression (SVR) algorithm is used to predict the trajectory of the robot over dynamic obstacles, transforming the dynamic path planning problem into a static path planning problem. Then, the PRM algorithm is used for instantaneous static path planning for the robot. By organically combining these two algorithms, an optimal or near-optimal obstacle-free path is found for the mobile robot in a dynamic environment.
