Proceedings of the 2015 International Conference on Electrical, Computer Engineering and Electronics

A optimization of A* algorithm to make it close to human pathfinding behavior

Authors
ZhenGuo Zhao, RunTao Liu
Corresponding Author
ZhenGuo Zhao
Available Online June 2015.
DOI
10.2991/icecee-15.2015.140How to use a DOI?
Keywords
A* algorithm; Pathfinding optimization; Space vector operations; Common sense illation
Abstract

A* algorithm is considered to be the optimal heuristic search algorithm over time. But the biggest drawback is the consumption of resources as the growth risk of the processing scale is a exponential level. This article based on common sense reasoning of artificial intelligence and the vector calculation of mathematics put forward three strategies to optimize the number of intermediate nodes and the calculation times of heuristic function. These strategies make the computer in the process of pathfinding closer to human thinking. By comparison with the experimental data with the traditional algorithm, the result show that runtime is generally reduced by 40%~70% and count of intermediate node is reduced by 30%~60%. And exponential growth risk is also effectively reduced.

Copyright
© 2015, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 2015 International Conference on Electrical, Computer Engineering and Electronics
Series
Advances in Computer Science Research
Publication Date
June 2015
ISBN
978-94-62520-81-3
ISSN
2352-538X
DOI
10.2991/icecee-15.2015.140How to use a DOI?
Copyright
© 2015, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - ZhenGuo Zhao
AU  - RunTao Liu
PY  - 2015/06
DA  - 2015/06
TI  - A optimization of A* algorithm to make it close to human pathfinding behavior
BT  - Proceedings of the 2015 International Conference on Electrical, Computer Engineering and Electronics
PB  - Atlantis Press
SP  - 708
EP  - 714
SN  - 2352-538X
UR  - https://doi.org/10.2991/icecee-15.2015.140
DO  - 10.2991/icecee-15.2015.140
ID  - Zhao2015/06
ER  -