A Path-Planning Approach for an Unmanned Vehicle in an Off-Road Environment Based on an Improved A* Algorithm
Abstract
:1. Introduction
- (1)
- This paper designed a grid map with a pixel as the cell. An artificial potential field model was used to describe the distribution of risk in the environment, as presented. In addition, according to the ground conditions and the performance of the vehicle, the passing-time cost of the vehicle was analyzed, and a passing-time cost distribution map was established.
- (2)
- A multi-direction search method was used to select the child nodes. In addition, combining the distribution of risk and the distribution of time-cost, a new calculation method of cost function was designed.
- (3)
- Path-planning simulation experiments validated that the improved A* algorithm proposed in this paper can determine the path with the shortest length, the path with the least risk, and the path associated with the least amount of time.
2. Identification of Environment
2.1. Set Pixel Points to Grid Points
2.2. Identification of Risk Areas
2.3. Identification of Ground Conditions
3. Improved A* Algorithm
3.1. Principle of the A* Algorithm
3.2. Multi-Direction Search Method
3.3. Set Cost Function
Algorithm 1 Main Function |
1: function Improved A* Function () |
2: Map(obstacle); Map(risk); Map(time cost); Steplength; Case(j)j ∈ {1,2,3}; |
3: start_point; end_point; |
4: openlist() = Ø; closedlist() = Ø; |
5: openlist(1) = start; |
6: while openlist() ≠ Ø; |
8: Fmin= FunctionMin (openlist()); |
9: if Fmin_h < L |
10: return ‘get path’ |
11: end if |
12: closedlist = [closedlist: Fmin] |
13: roundlist() = FunctionSearch(Fmin,Case(j)); |
14: for i = 1: length(roundlist) |
15: if roundlist(i) ∉ closedlist() |
16: if roundlist(i) ∉ openlist() |
17: openlist = [openlist: roundlist(i)]; |
18: else |
19: FunctionReelect(roundlist(i)) |
20: end if |
21: end if |
22: end for |
23: end while |
24: end function |
FunctionMin |
1: function FunctionMin () |
2: openlist(); Case(j) j ∈ {1,2,3}; |
3: for i = 1: length(openlist) |
4: switch Case(j) |
5: case Case(1) |
6: openlist(i)_f = openlist(i)_gshort + openlist(i)_h |
7: Fmin = min(openlist(i)_f) |
8: case Case(2) |
9: openlist(i)_f = openlist(i)_grisk + openlist(i)_h |
10: Fmin = min(openlist(i)_f) |
11: case Case(3) |
12: openlist(i)_f = openlist(i)_gtime + openlist(i)_h |
13: Fmin = min(openlist(i)_f) |
14: end switch |
15: end for |
16: end function |
FunctionSearch |
1: function FunctionSearch () |
2: Fmin_coord_row; Fmin_coord_col; Fmin_ directedangle |
3: Steplength; Case(j); Angleelement; |
4: roundlist() = Ø |
5: for k = 1: int(2pi/Angleelement) |
6: roundlist(k)_coord_row = int(Fmin_coord_row+ Steplength×sin(Fmin_ directedangle + k×Angleelement)) |
7: roundlist(k)_coord_col = int(Fmin_coord_col+ Steplength×cos(Fmin_ directedangle + k×Angleelement)) |
8: roundlist(k)_directedangle = atan((roundlist(k)_coord_row-Fmin_coord_row)/(round list(k)_coord_col-Fmin_coord_col)) |
9: if Functionlineofsight (roundlist1(k)) = Y |
10: roundlist() = roundlist1(k) |
11: end if |
12: end for |
13: return ‘roundlist()’ |
14: end function |
FunctionReelect |
1: function FunctionReelect () |
2: Fmin; roundlist(i)_parent; Case(j) j ∈ {1,2,3}; |
3: If Fmin_f < roundlist(i)_parent_f |
4: roundlist(i)_parent = Fmin |
5: End if |
6: End function |
Functionlineofsight |
1: function Functionlineofsight () |
2: Fmin; roundlist(i)_row; roundlist(i)_col; |
3: numx = roundlist(i)_row-Fmin_row |
4: numy = roundlist(i)_col-Fmin_col |
5: For m = 1: numx |
6: for n = 1: numy |
7: p = (Fmin_row + m, Fmin_col + n) |
8: dis = abs(det([Fmin − roundlist(i),p-roundlist(i)]))/norm(Fmin − roundlist(i)); |
9: if dis < 1 |
10: If Map(p) = 0 |
11: return ‘N’ |
12: else |
13: return ‘Y’ |
14: End if |
15: End if |
16: End for |
17: End for |
18: End function |
4. Simulation Results and Analysis
4.1. Design of a Map
4.2. Path Comparison
4.3. Less-Risk Path Simulation
4.4. Less Time-Cost Path Simulation
5. Actual Condition Verification
5.1. Experimental Settings
5.2. Path Planning
5.3. Analysis of Algorithm Optimization Effect
6. Conclusions
- –
- The improved algorithm can complete the path planning for the path with the less risk in a risky environment.
- –
- The improved algorithm can obtain the path-planning scheme involving the less time in a complex ground environment.
- –
- The improved algorithm can obtain a smoother short path.
Author Contributions
Funding
Institutional Review Board Statement
Informed Consent Statement
Data Availability Statement
Conflicts of Interest
References
- Wang, R.; Wan, J.; Ye, Q.; Ding, R. Path Tracking and Anti-Roll Control of Unmanned Mining Trucks on Mine Site Roads. World Electr. Veh. J. 2024, 15, 167. [Google Scholar] [CrossRef]
- Pham, N.N.; Bloudicek, R.; Leuchter, J. Comparative Analysis of Energy Storage and Buffer Units for Electric Military Vehicle: Survey of Experimental Results. Batteries 2024, 10, 43. [Google Scholar] [CrossRef]
- Huang, S.; Wang, T.; Tang, Y. Distributed and Scalable Cooperative Formation of Unmanned Ground Vehicles Using Deep Reinforcement Learning. Aerospace 2023, 10, 96. [Google Scholar] [CrossRef]
- Wang, N.; Li, X.; Zhang, K. A survey on path planning for autonomous ground vehicles in unstructured environments. Machines 2024, 12, 31. [Google Scholar] [CrossRef]
- Dawid, W.; Pokonieczny, K. Methodology of using terrain passability maps for planning the movement of troops and navigation of unmanned ground vehicles. Sensors 2021, 21, 4682. [Google Scholar] [CrossRef] [PubMed]
- Wang, K.; Li, J.; Xu, M.; Chen, Z.; Wang, J. LiDAR-Only Ground Vehicle Navigation System in Park Environment. World Electr. Veh. J. 2022, 13, 201. [Google Scholar] [CrossRef]
- Alharbi, M.; Karimi, H.A. A global path planner for safe navigation of autonomous vehicles in uncertain environments. Sensors 2020, 20, 6103. [Google Scholar] [CrossRef] [PubMed]
- Wang, L.; Sun, L. Path planning algorithm based on obstacle clustering analysis and graph search. Symmetry 2023, 15, 1498. [Google Scholar] [CrossRef]
- Baumann, M.; Léonard, S.; Croft, E.A. Path planning for improved visibility using a probabilistic road map. IEEE Trans. Robot. 2010, 26, 195–200. [Google Scholar] [CrossRef]
- Ou, Y.; Fan, Y.; Zhang, X. Improved A* path planning method based on the grid map. Sensors 2022, 22, 6198. [Google Scholar] [CrossRef] [PubMed]
- Remolina, E.; Kuipers, B. Towards a general theory of topological maps. Artif. Intell. 2004, 152, 47–104. [Google Scholar] [CrossRef]
- Hou, Y.; Gao, H.; Wang, Z. Path Planning for Mobile Robots Based on Improved A* Algorithm. In Proceedings of the International Conference on Neural Computing for Advanced Applications, Jinan, China, 8–10 July 2022; Springer Nature: Singapore, 2022; pp. 1169–1183. [Google Scholar]
- Wang, P.; He, A.; Shao, J.; Sun, H.; Chen, D.; Liu, W.; Liu, J. Numerical and theoretical investigations of shock-induced material ejection and ejecta-gas mixing. Sci. Sin. Phys. Mech. Astron. 2018, 48, 094608. [Google Scholar] [CrossRef]
- Zhe, L.; Yibin, L.; Xuewen, R. Path planning based on ADFA* algorithm for quadruped robot. IEEE Access 2019, 7, 111095–111101. [Google Scholar] [CrossRef]
- Jiang, L.; Huang, H.; Ding, Z. Path planning for intelligent robots based on deep Q-learning with experience replay and heuristic knowledge. IEEE/CAA J. Autom. Sin. 2019, 7, 1179–1189. [Google Scholar] [CrossRef]
- Phung, M.D.; Ha, Q.P. Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization. Appl. Soft Comput. 2021, 107, 107376. [Google Scholar] [CrossRef]
- Lai, Y.K.; Vadakkepat, P.; Xiang, C. Optimal vector-based and any-angle 2D path planning with non-convex obstacles. Robot. Auton. Syst. 2023, 172, 104606. [Google Scholar] [CrossRef]
- Qu, X.; Ding, Y.; Xie, Y. Improved intelligent path selection algorithm based on grid map. Electron. Meas. Technol. 2022, 5, 86–93. [Google Scholar]
- Niu, Q.; Fu, Y.; Dong, X. Omnidirectional AGV Path Planning Based on Improved Genetic Algorithm. World Electr. Veh. J. 2024, 15, 166. [Google Scholar] [CrossRef]
- Sánchez-Ibáñez, J.R.; Pérez-del-Pulgar, C.J.; García-Cerezo, A. Path planning for autonomous mobile robots: A review. Sensors 2021, 21, 7898. [Google Scholar] [CrossRef] [PubMed]
- Patle, B.K.; Pandey, A.; Parhi, D.R.K.; Jagadeesh, A.J.D.T. A review: On path planning strategies for navigation of mobile robot. Def. Technol. 2019, 15, 582–606. [Google Scholar] [CrossRef]
- Terapaptommakol, W.; Phaoharuhansa, D.; Koowattanasuchat, P.; Rajruangrabin, J. Design of obstacle avoidance for autonomous vehicle using deep Q-network and CARLA simulator. World Electr. Veh. J. 2022, 13, 239. [Google Scholar] [CrossRef]
- Yu, F.; Shang, H.; Zhu, Q.; Zhang, H.; Chen, Y. An efficient RRT-based motion planning algorithm for autonomous underwater vehicles under cylindrical sampling constraints. Auton. Robot. 2023, 47, 281–297. [Google Scholar] [CrossRef]
- Salzman, O.; Halperin, D. Asymptotically near-optimal RRT for fast, high-quality motion planning. IEEE Trans. Robot. 2016, 32, 473–483. [Google Scholar] [CrossRef]
- Gao, H.; Hou, X.; Xu, J.; Guan, B. Quad-Rotor Unmanned Aerial Vehicle Path Planning Based on the Target Bias Extension and Dynamic Step Size RRT* Algorithm. World Electr. Veh. J. 2024, 15, 29. [Google Scholar] [CrossRef]
- Miao, C.; Chen, G.; Yan, C. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Comput. Ind. Eng. 2021, 156, 107230. [Google Scholar] [CrossRef]
- Liu, J.; Yang, J.; Liu, H. An improved ant colony algorithm for robot path planning. Soft Comput. 2017, 21, 5829–5839. [Google Scholar] [CrossRef]
- Luo, Q.; Wang, H.; Zheng, Y. Research on path planning of mobile robot based on improved ant colony algorithm. Neural Comput. Appl. 2020, 32, 1555–1566. [Google Scholar] [CrossRef]
- Maoudj, A.; Hentout, A. Optimal path planning approach based on Q-learning algorithm for mobile robots. Appl. Soft Comput. 2020, 97, 106796. [Google Scholar] [CrossRef]
- Low, E.S.; Ong, P.; Cheah, K.C. Solving the optimal path planning of a mobile robot using improved Q-learning. Robot. Auton. Syst. 2019, 115, 143–161. [Google Scholar] [CrossRef]
- Sonny, A.; Yeduri, S.R.; Cenkeramaddi, L.R. Q-learning-based unmanned aerial vehicle path planning with dynamic obstacle avoidance. Appl. Soft Comput. 2023, 147, 110773. [Google Scholar] [CrossRef]
- Yu, M.; Luo, Q.; Wang, H.; Lai, Y. Electric Logistics Vehicle Path Planning Based on the Fusion of the Improved A-Star Algorithm and Dynamic Window Approach. World Electr. Veh. J. 2023, 14, 213. [Google Scholar] [CrossRef]
- Persson, S.M.; Sharf, I. Sampling-based A* algorithm for robot path-planning. Int. J. Robot. Res. 2014, 33, 1683–1708. [Google Scholar] [CrossRef]
- Fu, B.; Chen, L.; Zhou, Y. An improved A* algorithm for the industrial robot path planning with high success rate and short length. Robot. Auton. Syst. 2018, 106, 26–37. [Google Scholar] [CrossRef]
- Guruji, A.K.; Agarwal, H.; Parsediya, D.K. Time-efficient A* algorithm for robot path planning. Procedia Technol. 2016, 23, 144–149. [Google Scholar] [CrossRef]
- Liu, X.; Zhang, D.; Zhang, T. Novel best path selection approach based on hybrid improved A* algorithm and reinforcement learning. Appl. Intell. 2021, 51, 9015–9029. [Google Scholar] [CrossRef]
- Liu, X.H.; Zhang, D.G.; Yan, H.R. A new algorithm of the best path selection based on machine learning. IEEE Access 2019, 7, 126913–126928. [Google Scholar] [CrossRef]
- Yu, J.; Li, J.; Zhang, T.; Yan, B.; Li, S.; Meng, Z. Speed-First: An Aggressive Gradient-Based Local Planner for Quadrotor Faster Flight. Drones 2023, 7, 192. [Google Scholar] [CrossRef]
- Xie, L.; Xue, S.; Zhang, J. A path planning approach based on multi-direction A* algorithm for ships navigating within wind farm waters. Ocean. Eng. 2019, 184, 311–322. [Google Scholar] [CrossRef]
- Yuan, M.; Chen, M. Improved lazy theta∗ algorithm based on octree map for path planning of UAV. Def. Technol. 2023, 23, 8–18. [Google Scholar] [CrossRef]
- Zhang, T.; Xiang, Q.; Zheng, W. Application of path planning based on improved A* algorithm in war gaming of naval warfare. Acta Armamentarii 2022, 43, 960. [Google Scholar]
- Peta, K.; Wlodarczyk, J.; Maniak, M. Analysis of trajectory and motion parameters of an industrial robot cooperating with a numerically controlled machine tools. J. Manuf. Process. 2023, 101, 1332–1342. [Google Scholar] [CrossRef]
- Wang, Z.H.; Lv, Q. Tactical Path Planning Method for Military Unmanned Vehicle in Battlefield. J. Acad. Armored Force Eng. 2012, 26, 72–79. [Google Scholar]
- Liu, Y. Vehicle Route Planning Method Integrated Battlefield Situation andIts Implementation. Command Inf. Syst. Technol. 2021, 12, 91–95. [Google Scholar]
- Han, Z.; Chen, M.; Zhu, H. Ground threat prediction-based path planning of unmanned autonomous helicopter using hybrid enhanced artificial bee colony algorithm. Def. Technol. 2023, 32, 1–22. [Google Scholar] [CrossRef]
Ground Type | Picture | Feature | Time Cost | Display Color |
---|---|---|---|---|
Hardened road | High speed | 0.1 | ||
Hardened ground | Relatively high speed | 0.2 | ||
Gravel ground | Medium speed | 0.3 | ||
Rough ground | Medium speed | 0.4 | ||
Grass | Slow | 0.6 | ||
Muddy ground | Relatively slow | 0.7 | ||
Farmland | Hyperslow | 0.8 |
Algorithm | Computation Time/ms | Number of Nodes | Length/m |
---|---|---|---|
A* | 166 ms | 25 | 757.07 m |
RRT* | 273 ms | 15 | 737.23 m |
Improved A* (shortest) | 226 ms | 24 | 729.64 m |
Algorithm | Computation Time/ms | Length/m | The Risk Factor of Path |
---|---|---|---|
A* | 166 ms | 757.07 m | 306.28 |
RRT* | 273 ms | 737.23 m | 261.20 |
Improved A* (less risk) | 426 ms | 812 m | 201.83 |
Algorithm | Computation Time/ms | Length/m | Time-Cost of Path |
---|---|---|---|
A* | 166 ms | 757.07 m | 306.28 |
RRT* | 273 ms | 737.23 m | 261.20 |
Improved A* (less time) | 383 ms | 847.07 m | 180.62 |
Model | Value | Model | Value |
---|---|---|---|
Length | 5316 mm | Wheel radius | 478.3 mm |
Width | 2144 mm | Left and right wheel-base | 1873 mm |
Height | 2182 mm | Ground clearance | 462.3 mm |
Wheelbase | 3466 mm | Maximum Traction | 96 kN |
Weight | 2169 kg | PTO power | 323 kW |
Path | Length/m | Risk Value of Path | Time-Cost of Path |
---|---|---|---|
Path1 | 510.4 m | 200.29 | 414.12 |
Path2 | 519.49 m | 99.9 | 402.63 |
Path3 | 690.7 m | 225.89 | 195.13 |
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. |
© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Xie, G.; Fang, L.; Su, X.; Guo, D.; Qi, Z.; Li, Y.; Che, J. A Path-Planning Approach for an Unmanned Vehicle in an Off-Road Environment Based on an Improved A* Algorithm. World Electr. Veh. J. 2024, 15, 234. https://doi.org/10.3390/wevj15060234
Xie G, Fang L, Su X, Guo D, Qi Z, Li Y, Che J. A Path-Planning Approach for an Unmanned Vehicle in an Off-Road Environment Based on an Improved A* Algorithm. World Electric Vehicle Journal. 2024; 15(6):234. https://doi.org/10.3390/wevj15060234
Chicago/Turabian StyleXie, Gaoyang, Liqing Fang, Xujun Su, Deqing Guo, Ziyuan Qi, Yanan Li, and Jinli Che. 2024. "A Path-Planning Approach for an Unmanned Vehicle in an Off-Road Environment Based on an Improved A* Algorithm" World Electric Vehicle Journal 15, no. 6: 234. https://doi.org/10.3390/wevj15060234
APA StyleXie, G., Fang, L., Su, X., Guo, D., Qi, Z., Li, Y., & Che, J. (2024). A Path-Planning Approach for an Unmanned Vehicle in an Off-Road Environment Based on an Improved A* Algorithm. World Electric Vehicle Journal, 15(6), 234. https://doi.org/10.3390/wevj15060234