Skip to main content
Top
Published in:

09-05-2024

Research of hybrid path planning with improved A* and TEB in static and dynamic environments

Authors: Lin Zhang, Ning An, Zongfang Ma

Published in: The Journal of Supercomputing | Issue 12/2024

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this study, we introduce a new approach to path planning suitable for both static and dynamic environments. Our method combines the Obstacle Avoidance Improved A* (OA-IA*) algorithm with the Time Elastic Band (TEB) technique. The OA-IA* incorporates four key elements: utilization of robot direction information, adaptive adjustment of bandwidth, enhancement of evaluation function, and path smoothing operations. We conducted experiments to validate our approach, including simulations and real-world verifications in various environments. In the simulation experiments, we compared our method with two previous approaches: Improved Local Particle Swarm Optimization (ILPSO) and Obstacle Avoidance RRT (OA-RRT) method. Across seven different simulated maps, the OA-IA* algorithm showed an average improvement of 0.19 in Path Optimal Degree (POD) compared to the ILPSO algorithm, along with an average time savings of 11 s. Furthermore, compared to the OA-RRT algorithm, the OA-IA* algorithm achieved an average POD increase of 0.36, resulting in an average time savings of 60.37 s. Moreover, we compared our method with APF-RRT*, APF-RRT, RRT, and RRT* approaches across 50 simulation maps. On average, our method achieved higher POD values by 0.54, 0.31, 0.85, and 0.26 compared to APF-RRT*, APF-RRT, RRT, and RRT* methods, respectively. Additionally, the average running time of our method was significantly reduced by 90 s, 64.7 s, 38.13 s, and 19.4 s compared to APF-RRT*, APF-RRT, RRT, and RRT* methods, respectively. In the experimental verification section, we tested our method in a real office, laboratory, and workshop environments. In two real-world environments spanning 9.4 m\(^2\) and 9.2 m\(^2\), our enhanced A* method integrated with TEB exhibited an average POD value that at least 0.125 higher compared to that of ILPSO combined with TEB. These results demonstrate the effectiveness of our hybrid path planning method in complex dynamic environments, achieving optimal outcomes in terms of path length, smoothness, and speed. In addition, it also ensures the smoothness of the path and speed, and the smoothness is less than 0.05 rad/s\(^2\).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Sang H, You Y, Sun X, Zhou Y, Liu F (2021) The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations. Ocean Eng 223:108709CrossRef Sang H, You Y, Sun X, Zhou Y, Liu F (2021) The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations. Ocean Eng 223:108709CrossRef
2.
go back to reference Iswanto I, Wahyunggoro O, Cahyadi AI (2016) Path planning based on fuzzy decision trees and potential field. Int J Electr Comput Eng 6(1):212 Iswanto I, Wahyunggoro O, Cahyadi AI (2016) Path planning based on fuzzy decision trees and potential field. Int J Electr Comput Eng 6(1):212
3.
go back to reference Raja R, Dutta A (2017) Path planning in dynamic environment for a rover using A\(^*\) and potential field method (2017). In: 2017 18th International Conference on Advanced Robotics (ICAR) Raja R, Dutta A (2017) Path planning in dynamic environment for a rover using A\(^*\) and potential field method (2017). In: 2017 18th International Conference on Advanced Robotics (ICAR)
5.
go back to reference Qureshi AH, Ayaz Y (2017) Potential functions based sampling heuristic for optimal path planning. Online Qureshi AH, Ayaz Y (2017) Potential functions based sampling heuristic for optimal path planning. Online
6.
go back to reference Wang G, Jiang C, Tao G, Ye C (2023) Dynamic path planning based on the fusion of improved RRT and DWA algorithms. In: 2023 4th International Conference on Mechatronics Technology and Intelligent Manufacturing (ICMTIM). IEEE, pp 534–538 Wang G, Jiang C, Tao G, Ye C (2023) Dynamic path planning based on the fusion of improved RRT and DWA algorithms. In: 2023 4th International Conference on Mechatronics Technology and Intelligent Manufacturing (ICMTIM). IEEE, pp 534–538
7.
go back to reference Yu Z, Xiang L (2021) Npq-rrt\(^{*}\): An improved rrt\(^{*}\) approach to hybrid path planning. Complexity 2021:1–10 Yu Z, Xiang L (2021) Npq-rrt\(^{*}\): An improved rrt\(^{*}\) approach to hybrid path planning. Complexity 2021:1–10
8.
go back to reference Kiani F, Seyyedabbasi A, Aliyev R, Gulle MU, Basyildiz H, Shah MA (2021) Adapted-RRT: novel hybrid method to solve three-dimensional path planning problem using sampling and metaheuristic-based algorithms. Neural Comput Appl 33:15569–15599CrossRef Kiani F, Seyyedabbasi A, Aliyev R, Gulle MU, Basyildiz H, Shah MA (2021) Adapted-RRT: novel hybrid method to solve three-dimensional path planning problem using sampling and metaheuristic-based algorithms. Neural Comput Appl 33:15569–15599CrossRef
9.
go back to reference Abhishek B, Ranjit S, Shankar T, Eappen G, Rajesh A (2020) Hybrid PSO-HSA and PSO-GA algorithm for 3D path planning in autonomous UAVs. SN Appl Sci 2(11):1–16CrossRef Abhishek B, Ranjit S, Shankar T, Eappen G, Rajesh A (2020) Hybrid PSO-HSA and PSO-GA algorithm for 3D path planning in autonomous UAVs. SN Appl Sci 2(11):1–16CrossRef
10.
go back to reference Yong Z, Ling C, Xiaolong X, Feiteng L (2015) Research on time optimal tsp based on hybrid PSO-GA. Application Research of Computers Yong Z, Ling C, Xiaolong X, Feiteng L (2015) Research on time optimal tsp based on hybrid PSO-GA. Application Research of Computers
11.
go back to reference Algabri M, Mathkour H, Ramdane H, Alsulaiman M (2015) Comparative study of soft computing techniques for mobile robot navigation in an unknown environment. Comput Hum Behav 50:42–56CrossRef Algabri M, Mathkour H, Ramdane H, Alsulaiman M (2015) Comparative study of soft computing techniques for mobile robot navigation in an unknown environment. Comput Hum Behav 50:42–56CrossRef
12.
go back to reference Wei Q, Song R, Zhang P, Wu Z, Huang R, Qin C, Li JL, Lan X (2023) Path planning of mobile robot in unknown dynamic continuous environment using reward-modified deep-Q-network. Optim Control Appl Methods 44:1570CrossRef Wei Q, Song R, Zhang P, Wu Z, Huang R, Qin C, Li JL, Lan X (2023) Path planning of mobile robot in unknown dynamic continuous environment using reward-modified deep-Q-network. Optim Control Appl Methods 44:1570CrossRef
13.
go back to reference Lin X, Chen X (2023) Realization of Ackermann robot obstacle avoidance navigation based on multi-sensor fusion slam. In: 2023 5th International Conference on Electronics and Communication, Network and Computer Technology (ECNCT). IEEE, pp 354–359 Lin X, Chen X (2023) Realization of Ackermann robot obstacle avoidance navigation based on multi-sensor fusion slam. In: 2023 5th International Conference on Electronics and Communication, Network and Computer Technology (ECNCT). IEEE, pp 354–359
15.
go back to reference Shi J, Su Y, Bu C, Fan X (2020) A mobile robot path planning algorithm based on improved A. In: Journal of Physics: Conference Series, vol. 1486. IOP Publishing, p. 032018 Shi J, Su Y, Bu C, Fan X (2020) A mobile robot path planning algorithm based on improved A. In: Journal of Physics: Conference Series, vol. 1486. IOP Publishing, p. 032018
16.
go back to reference Zhongyu W, Guohui Z, Bo H, Zhijun F (2019) Global optimal path planning for robots with improved A* algorithm. J Comput Appl 39:2517 Zhongyu W, Guohui Z, Bo H, Zhijun F (2019) Global optimal path planning for robots with improved A* algorithm. J Comput Appl 39:2517
17.
go back to reference Roesmann C, Feiten W, Woesch T, Hoffmann F, Bertram T (2012) Trajectory modification considering dynamic constraints of autonomous robots. In: Germany Conference on Robotics Roesmann C, Feiten W, Woesch T, Hoffmann F, Bertram T (2012) Trajectory modification considering dynamic constraints of autonomous robots. In: Germany Conference on Robotics
18.
go back to reference Quinlan S, Khatib O (1993) Elastic bands: connecting path planning and control. In: [1993] Proceedings IEEE International Conference on Robotics and Automation. IEEE, pp 802–807 Quinlan S, Khatib O (1993) Elastic bands: connecting path planning and control. In: [1993] Proceedings IEEE International Conference on Robotics and Automation. IEEE, pp 802–807
19.
go back to reference Grisetti G, Kümmerle R, Strasdat H, Konolige K (2011) G2o: a general framework for (hyper) graph optimization. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp 9–13 Grisetti G, Kümmerle R, Strasdat H, Konolige K (2011) G2o: a general framework for (hyper) graph optimization. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp 9–13
20.
go back to reference Sturtevant NR (2012) Benchmarks for grid-based pathfinding. IEEE Trans Comput Intell Ai Games 4(2012):144–148CrossRef Sturtevant NR (2012) Benchmarks for grid-based pathfinding. IEEE Trans Comput Intell Ai Games 4(2012):144–148CrossRef
21.
go back to reference Zhang L, Zhang Y, Li Y (2020) Path planning for indoor mobile robot based on deep learning. Opt Int J Light Electron Opt 219(10):165096CrossRef Zhang L, Zhang Y, Li Y (2020) Path planning for indoor mobile robot based on deep learning. Opt Int J Light Electron Opt 219(10):165096CrossRef
23.
go back to reference Huang S (2021) Path planning based on mixed algorithm of RRT and artificial potential field method. In: 2021 4th International Conference on Intelligent Robotics and Control Engineering (IRCE). IEEE, pp 149–155 Huang S (2021) Path planning based on mixed algorithm of RRT and artificial potential field method. In: 2021 4th International Conference on Intelligent Robotics and Control Engineering (IRCE). IEEE, pp 149–155
Metadata
Title
Research of hybrid path planning with improved A* and TEB in static and dynamic environments
Authors
Lin Zhang
Ning An
Zongfang Ma
Publication date
09-05-2024
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 12/2024
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-024-06155-0

Premium Partner