Staff View: A new weighted pathfinding algorithm to reduce the search time on grid maps

A new weighted pathfinding algorithm to reduce the search time on grid maps

Artificial Intelligence (AI) techniques are utilized widely in the field of Expert Systems (ES) - as applied to robotics, video games self-driving vehicles and so on. Pathfinding algorithms are a class of heuristic algorithms based on AI techniques which are used in ES as decision making functions f...

Full description

Saved in:

Bibliographic Details
Main Authors:	Abd-Algfoor, Zeyad, Sunar, Mohd. Shahrizal, Abdullah, Afnizanfaizal
Format:	Article
Published:	Elsevier Ltd. 2017
Subjects:	QA75 Electronic computers. Computer science
Online Access:	http://eprints.utm.my/id/eprint/66137/ http://dx.doi.org/10.1016/j.eswa.2016.12.003
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my.utm.66137
record_format	eprints
spelling	my.utm.661372017-07-11T07:51:19Z http://eprints.utm.my/id/eprint/66137/ A new weighted pathfinding algorithm to reduce the search time on grid maps Abd-Algfoor, Zeyad Sunar, Mohd. Shahrizal Abdullah, Afnizanfaizal QA75 Electronic computers. Computer science Artificial Intelligence (AI) techniques are utilized widely in the field of Expert Systems (ES) - as applied to robotics, video games self-driving vehicles and so on. Pathfinding algorithms are a class of heuristic algorithms based on AI techniques which are used in ES as decision making functions for the purpose of solving problems that would otherwise require human competence or expertise. ES fields that use pathfinding algorithms and operate in real-time face many challenges: for example time constraints, optimality and memory overhead for storing the paths which are found. For these algorithms to work, appropriate problem-specific maps must be constructed. In relation to this, the uniform-cost grid set-up is the most appropriate for ES applications. In this method, each node in a graph is represented as a tile, and the weight “between” tiles is set at a constant value, usually this is set to 1. In the state-of-the-art heuristic algorithms used with this data structure, multiplying the heuristic function by a weight greater than one is well-known technique. In this paper, we present three new techniques using various weights to accelerate heuristic search of grid maps. The first such technique is based on the iteration of a heuristic search algorithm associated with weight-set w. The second technique is based on the length between the start node and goal node, which is then associated with w. The last technique is based on the travel cost and is associated with a weight-set α. These techniques are applicable to a wide class of heuristic search algorithms. Therefore, we implement them, here, within the A, the Bidirectional A (Bi-A*) and Jump Point Search (JPS) algorithms; thus obtaining a family of new algorithms. Furthermore, it is seen that the use of these new algorithms results in significant improvements over current search algorithms. We evaluate them in path-planning benchmarks and show the amended JPS technique's greater stability, across weight values, over the other two techniques. However, it is also shown that this technique yields poor results in terms of cost solution. Elsevier Ltd. 2017-01-04 Article PeerReviewed Abd-Algfoor, Zeyad and Sunar, Mohd. Shahrizal and Abdullah, Afnizanfaizal (2017) A new weighted pathfinding algorithm to reduce the search time on grid maps. Expert Systems with Applications, 71 . pp. 319-331. ISSN 09574174 http://dx.doi.org/10.1016/j.eswa.2016.12.003 DOI:10.1016/j.eswa.2016.12.003
institution	Universiti Teknologi Malaysia
building	UTM Library
collection	Institutional Repository
continent	Asia
country	Malaysia
content_provider	Universiti Teknologi Malaysia
content_source	UTM Institutional Repository
url_provider	http://eprints.utm.my/
topic	QA75 Electronic computers. Computer science
spellingShingle	QA75 Electronic computers. Computer science Abd-Algfoor, Zeyad Sunar, Mohd. Shahrizal Abdullah, Afnizanfaizal A new weighted pathfinding algorithm to reduce the search time on grid maps
description	Artificial Intelligence (AI) techniques are utilized widely in the field of Expert Systems (ES) - as applied to robotics, video games self-driving vehicles and so on. Pathfinding algorithms are a class of heuristic algorithms based on AI techniques which are used in ES as decision making functions for the purpose of solving problems that would otherwise require human competence or expertise. ES fields that use pathfinding algorithms and operate in real-time face many challenges: for example time constraints, optimality and memory overhead for storing the paths which are found. For these algorithms to work, appropriate problem-specific maps must be constructed. In relation to this, the uniform-cost grid set-up is the most appropriate for ES applications. In this method, each node in a graph is represented as a tile, and the weight “between” tiles is set at a constant value, usually this is set to 1. In the state-of-the-art heuristic algorithms used with this data structure, multiplying the heuristic function by a weight greater than one is well-known technique. In this paper, we present three new techniques using various weights to accelerate heuristic search of grid maps. The first such technique is based on the iteration of a heuristic search algorithm associated with weight-set w. The second technique is based on the length between the start node and goal node, which is then associated with w. The last technique is based on the travel cost and is associated with a weight-set α. These techniques are applicable to a wide class of heuristic search algorithms. Therefore, we implement them, here, within the A, the Bidirectional A (Bi-A*) and Jump Point Search (JPS) algorithms; thus obtaining a family of new algorithms. Furthermore, it is seen that the use of these new algorithms results in significant improvements over current search algorithms. We evaluate them in path-planning benchmarks and show the amended JPS technique's greater stability, across weight values, over the other two techniques. However, it is also shown that this technique yields poor results in terms of cost solution.
format	Article
author	Abd-Algfoor, Zeyad Sunar, Mohd. Shahrizal Abdullah, Afnizanfaizal
author_facet	Abd-Algfoor, Zeyad Sunar, Mohd. Shahrizal Abdullah, Afnizanfaizal
author_sort	Abd-Algfoor, Zeyad
title	A new weighted pathfinding algorithm to reduce the search time on grid maps
title_short	A new weighted pathfinding algorithm to reduce the search time on grid maps
title_full	A new weighted pathfinding algorithm to reduce the search time on grid maps
title_fullStr	A new weighted pathfinding algorithm to reduce the search time on grid maps
title_full_unstemmed	A new weighted pathfinding algorithm to reduce the search time on grid maps
title_sort	new weighted pathfinding algorithm to reduce the search time on grid maps
publisher	Elsevier Ltd.
publishDate	2017
url	http://eprints.utm.my/id/eprint/66137/ http://dx.doi.org/10.1016/j.eswa.2016.12.003
_version_	1643655767664885760
score	13.211869

A new weighted pathfinding algorithm to reduce the search time on grid maps

Similar Items