Skip to main content
Erschienen in:

09.05.2024

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

verfasst von: Lin Zhang, Ning An, Zongfang Ma

Erschienen in: The Journal of Supercomputing | Ausgabe 12/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Literatur
1.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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
Metadaten
Titel
Research of hybrid path planning with improved A* and TEB in static and dynamic environments
verfasst von
Lin Zhang
Ning An
Zongfang Ma
Publikationsdatum
09.05.2024
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 12/2024
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-024-06155-0