A Smooth Jump Point Search Algorithm for Mobile Robots Path Planning Based on a Two-Dimensional Grid Model
To address the problems of the traditional A∗ algorithm in solving paths with many expansion nodes, high memory overhead, low operation efficiency, and many path corners, this paper improved the traditional A∗ algorithm by combining jump point search strategy and adaptive arc optimization strategy....
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-01-01
|
| Series: | Journal of Robotics |
| Online Access: | http://dx.doi.org/10.1155/2022/7682201 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850224203745198080 |
|---|---|
| author | Zhen Yang Junli Li Liwei Yang Hejiang Chen |
| author_facet | Zhen Yang Junli Li Liwei Yang Hejiang Chen |
| author_sort | Zhen Yang |
| collection | DOAJ |
| description | To address the problems of the traditional A∗ algorithm in solving paths with many expansion nodes, high memory overhead, low operation efficiency, and many path corners, this paper improved the traditional A∗ algorithm by combining jump point search strategy and adaptive arc optimization strategy. Firstly, to improve the safety of our paths, the risk area of the obstacles was expanded. Then, the A∗ algorithm was combined with the jump point search strategy to achieve the subnode jump search, reducing the calculation scale and memory overhead, and improving search efficiency. Considering the influence of the density of obstacles on search efficiency, the heuristic function was enhanced according to the special effects of the density of obstacles. Finally, the redundant jump point and adaptive arc optimization strategies were used to shorten the path length further and enhance the initial path’s smoothness. Simulation results showed that our algorithm outperforms traditional A∗ and literature algorithms in path length, security, and smoothness, and then was further validated and applied in large-scale marine environments and realistic settings. |
| format | Article |
| id | doaj-art-5237201410cb44c2b69684b9d07b319e |
| institution | OA Journals |
| issn | 1687-9619 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Robotics |
| spelling | doaj-art-5237201410cb44c2b69684b9d07b319e2025-08-20T02:05:42ZengWileyJournal of Robotics1687-96192022-01-01202210.1155/2022/7682201A Smooth Jump Point Search Algorithm for Mobile Robots Path Planning Based on a Two-Dimensional Grid ModelZhen Yang0Junli Li1Liwei Yang2Hejiang Chen3School of Information Engineering and AutomationSchool of Information Engineering and AutomationSchool of Information Engineering and AutomationSchool of Information Engineering and AutomationTo address the problems of the traditional A∗ algorithm in solving paths with many expansion nodes, high memory overhead, low operation efficiency, and many path corners, this paper improved the traditional A∗ algorithm by combining jump point search strategy and adaptive arc optimization strategy. Firstly, to improve the safety of our paths, the risk area of the obstacles was expanded. Then, the A∗ algorithm was combined with the jump point search strategy to achieve the subnode jump search, reducing the calculation scale and memory overhead, and improving search efficiency. Considering the influence of the density of obstacles on search efficiency, the heuristic function was enhanced according to the special effects of the density of obstacles. Finally, the redundant jump point and adaptive arc optimization strategies were used to shorten the path length further and enhance the initial path’s smoothness. Simulation results showed that our algorithm outperforms traditional A∗ and literature algorithms in path length, security, and smoothness, and then was further validated and applied in large-scale marine environments and realistic settings.http://dx.doi.org/10.1155/2022/7682201 |
| spellingShingle | Zhen Yang Junli Li Liwei Yang Hejiang Chen A Smooth Jump Point Search Algorithm for Mobile Robots Path Planning Based on a Two-Dimensional Grid Model Journal of Robotics |
| title | A Smooth Jump Point Search Algorithm for Mobile Robots Path Planning Based on a Two-Dimensional Grid Model |
| title_full | A Smooth Jump Point Search Algorithm for Mobile Robots Path Planning Based on a Two-Dimensional Grid Model |
| title_fullStr | A Smooth Jump Point Search Algorithm for Mobile Robots Path Planning Based on a Two-Dimensional Grid Model |
| title_full_unstemmed | A Smooth Jump Point Search Algorithm for Mobile Robots Path Planning Based on a Two-Dimensional Grid Model |
| title_short | A Smooth Jump Point Search Algorithm for Mobile Robots Path Planning Based on a Two-Dimensional Grid Model |
| title_sort | smooth jump point search algorithm for mobile robots path planning based on a two dimensional grid model |
| url | http://dx.doi.org/10.1155/2022/7682201 |
| work_keys_str_mv | AT zhenyang asmoothjumppointsearchalgorithmformobilerobotspathplanningbasedonatwodimensionalgridmodel AT junlili asmoothjumppointsearchalgorithmformobilerobotspathplanningbasedonatwodimensionalgridmodel AT liweiyang asmoothjumppointsearchalgorithmformobilerobotspathplanningbasedonatwodimensionalgridmodel AT hejiangchen asmoothjumppointsearchalgorithmformobilerobotspathplanningbasedonatwodimensionalgridmodel AT zhenyang smoothjumppointsearchalgorithmformobilerobotspathplanningbasedonatwodimensionalgridmodel AT junlili smoothjumppointsearchalgorithmformobilerobotspathplanningbasedonatwodimensionalgridmodel AT liweiyang smoothjumppointsearchalgorithmformobilerobotspathplanningbasedonatwodimensionalgridmodel AT hejiangchen smoothjumppointsearchalgorithmformobilerobotspathplanningbasedonatwodimensionalgridmodel |