Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm
In order to solve the problems of A* algorithm in raster map path planning, such as large memory consump-tion and slow computing speed due to the traversal of many redundant nodes, an improved strategy for A* algorithm is proposed. Firstly, the specific calculation method of the heuristic function i...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Journal of Computer Engineering and Applications Beijing Co., Ltd., Science Press
2021-11-01
|
| Series: | Jisuanji kexue yu tansuo |
| Subjects: | |
| Online Access: | http://fcst.ceaj.org/CN/abstract/abstract2961.shtml |
| _version_ | 1818985392164044800 |
|---|---|
| author | ZHANG Qing, LIU Xu, PENG Li, ZHU Fengzeng |
| author_facet | ZHANG Qing, LIU Xu, PENG Li, ZHU Fengzeng |
| author_sort | ZHANG Qing, LIU Xu, PENG Li, ZHU Fengzeng |
| collection | DOAJ |
| description | In order to solve the problems of A* algorithm in raster map path planning, such as large memory consump-tion and slow computing speed due to the traversal of many redundant nodes, an improved strategy for A* algorithm is proposed. Firstly, the specific calculation method of the heuristic function is improved. The Chebyshev distance is used to replace the Euclidean distance so that the heuristic function is exactly equal to the actual optimal path and the number of A* node extension is reduced. Secondly, jump-point-search (JPS) strategy is used to screen out a large number of unnecessary neighboring nodes added to OpenList and ClosedList instead of A* algorithm. Long distance jumps are achieved through the hops, thereby reducing the memory footprint and evaluation of nodes until the final path is generated. In order to verify the improved effect of the A* algorithm, the simulation test is carried out in the two-dimensional raster map with five sizes. The results show that the improved A* algorithm reduces a large number of nodes in pathfinding process evaluation and improves pathfinding speed. Moreover, with the increase of map size, the improved A* algorithm can increase pathfinding speed by more than one order of magnitude. Finally, the improved algorithm can be applied to experiment on mobile robot path planning. Under the same planning tasks, the improved A* algorithm under JPS strategy than traditional A* algorithm, path search consuming time is decreased by 92.2%, and expanded nodes are decreased by 97.37%, which can satisfy the mobile robot fast path planning requirements in large scenarios. |
| first_indexed | 2024-12-20T18:34:10Z |
| format | Article |
| id | doaj.art-5cc355a853b84230a57692b1306116ab |
| institution | Directory Open Access Journal |
| issn | 1673-9418 |
| language | zho |
| last_indexed | 2024-12-20T18:34:10Z |
| publishDate | 2021-11-01 |
| publisher | Journal of Computer Engineering and Applications Beijing Co., Ltd., Science Press |
| record_format | Article |
| series | Jisuanji kexue yu tansuo |
| spelling | doaj.art-5cc355a853b84230a57692b1306116ab2022-12-21T19:29:57ZzhoJournal of Computer Engineering and Applications Beijing Co., Ltd., Science PressJisuanji kexue yu tansuo1673-94182021-11-0115112233224010.3778/j.issn.1673-9418.2101020Path Planning for Mobile Robots Based on JPS and Improved A* AlgorithmZHANG Qing, LIU Xu, PENG Li, ZHU Fengzeng0Engineering Research Center of Internet of Things Technology Applications of the Ministry of Education, School of Internet of Things Engineering, Jiangnan University, Wuxi, Jiangsu 214122, ChinaIn order to solve the problems of A* algorithm in raster map path planning, such as large memory consump-tion and slow computing speed due to the traversal of many redundant nodes, an improved strategy for A* algorithm is proposed. Firstly, the specific calculation method of the heuristic function is improved. The Chebyshev distance is used to replace the Euclidean distance so that the heuristic function is exactly equal to the actual optimal path and the number of A* node extension is reduced. Secondly, jump-point-search (JPS) strategy is used to screen out a large number of unnecessary neighboring nodes added to OpenList and ClosedList instead of A* algorithm. Long distance jumps are achieved through the hops, thereby reducing the memory footprint and evaluation of nodes until the final path is generated. In order to verify the improved effect of the A* algorithm, the simulation test is carried out in the two-dimensional raster map with five sizes. The results show that the improved A* algorithm reduces a large number of nodes in pathfinding process evaluation and improves pathfinding speed. Moreover, with the increase of map size, the improved A* algorithm can increase pathfinding speed by more than one order of magnitude. Finally, the improved algorithm can be applied to experiment on mobile robot path planning. Under the same planning tasks, the improved A* algorithm under JPS strategy than traditional A* algorithm, path search consuming time is decreased by 92.2%, and expanded nodes are decreased by 97.37%, which can satisfy the mobile robot fast path planning requirements in large scenarios.http://fcst.ceaj.org/CN/abstract/abstract2961.shtmlmobile robotpath planninga* algorithmjump-point-search (jps)chebyshev distance |
| spellingShingle | ZHANG Qing, LIU Xu, PENG Li, ZHU Fengzeng Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm Jisuanji kexue yu tansuo mobile robot path planning a* algorithm jump-point-search (jps) chebyshev distance |
| title | Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm |
| title_full | Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm |
| title_fullStr | Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm |
| title_full_unstemmed | Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm |
| title_short | Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm |
| title_sort | path planning for mobile robots based on jps and improved a algorithm |
| topic | mobile robot path planning a* algorithm jump-point-search (jps) chebyshev distance |
| url | http://fcst.ceaj.org/CN/abstract/abstract2961.shtml |
| work_keys_str_mv | AT zhangqingliuxupenglizhufengzeng pathplanningformobilerobotsbasedonjpsandimprovedaalgorithm |