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

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	ZHANG Qing, LIU Xu, PENG Li, ZHU Fengzeng
Formato:	article
Lenguaje:	ZH
Publicado:	Journal of Computer Engineering and Applications Beijing Co., Ltd., Science Press 2021
Materias:	mobile robot path planning a* algorithm jump-point-search (jps) chebyshev distance Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/5cc355a853b84230a57692b1306116ab
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:5cc355a853b84230a57692b1306116ab
record_format	dspace
spelling	oai:doaj.org-article:5cc355a853b84230a57692b1306116ab2021-11-10T08:34:04ZPath Planning for Mobile Robots Based on JPS and Improved A* Algorithm10.3778/j.issn.1673-9418.21010201673-9418https://doaj.org/article/5cc355a853b84230a57692b1306116ab2021-11-01T00:00:00Zhttp://fcst.ceaj.org/CN/abstract/abstract2961.shtmlhttps://doaj.org/toc/1673-9418In 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.ZHANG Qing, LIU Xu, PENG Li, ZHU FengzengJournal of Computer Engineering and Applications Beijing Co., Ltd., Science Pressarticlemobile robotpath planninga* algorithmjump-point-search (jps)chebyshev distanceElectronic computers. Computer scienceQA75.5-76.95ZHJisuanji kexue yu tansuo, Vol 15, Iss 11, Pp 2233-2240 (2021)
institution	DOAJ
collection	DOAJ
language	ZH
topic	mobile robot path planning a* algorithm jump-point-search (jps) chebyshev distance Electronic computers. Computer science QA75.5-76.95
spellingShingle	mobile robot path planning a* algorithm jump-point-search (jps) chebyshev distance Electronic computers. Computer science QA75.5-76.95 ZHANG Qing, LIU Xu, PENG Li, ZHU Fengzeng Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm
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.
format	article
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
title	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_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_sort	path planning for mobile robots based on jps and improved a* algorithm
publisher	Journal of Computer Engineering and Applications Beijing Co., Ltd., Science Press
publishDate	2021
url	https://doaj.org/article/5cc355a853b84230a57692b1306116ab
work_keys_str_mv	AT zhangqingliuxupenglizhufengzeng pathplanningformobilerobotsbasedonjpsandimprovedaalgorithm
_version_	1718440375579836416

Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm

Ejemplares similares