A new weighted pathfinding algorithms to reduce the search time on grid maps. (1st April 2017)

• Record Type: Journal Article
• Authors: Algfoor, Zeyad Abd; Sunar, Mohd Shahrizal; Abdullah, Afnizanfaizal
• Is Part Of: Expert systems with applications. Volume 71(2017)
• Page Start: 319
• Page End: 331
• Publication Date: 2017-04-01
• Subjects: Pathfinding -- JPS, A* -- Bi-A* -- Weight techniques -- Pathfinding benchmarks maps; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2016.12.003
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: Three new weight techniques for pathfinding algorithm are proposed. Theoretical analysis shows the approximate details strengths/weaknesses of our techniques and previous techniques. Experiment on benchmark pathfinding dataset showed large improvement over existing standard algorithms. Abstract: 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.