Modeling Metaheuristic Algorithms to Optimal Pathfinding for Vehicles

Finding optimal path (pathfinding problem) in terrain for vehicles, robots, and network routes (roads, pipes for water or gas, and network cables) is very complex and costly. Exhausted, heuristic, and meta-heuristic algorithms can be utilized to solve pathfinding problems. In this paper, we proposed a framework that finds an optimal path based on the objectives of the specifications and requirements of the pathfinding problems, terrain characteristics, and a metaheuristic algorithm. In this framework, a pathfinding problem is represented in a graph and a metaheuristic algorithm is modeled with optimal objective function F to find the optimal path. Thus, we present an overview of the most common metaheuristic pathfinding algorithms with heuristic objective functions. Many objective functions are modeled to find the optimal path in terms of distance, time, cost, energy, … etc., or in terms of a combination of two or more of these terms. The F is evaluated to find an optimal path from a starting point to a target point, subjective to constraints such as obstacles, barriers, and other constraints to satisfy the characteristics of the terrain. In this framework, the problem locations and links in terrain are represented in graph vertices and edges, respectively. The graph is implemented in adjacent matrices and the paths as vectors. We overview these algorithms with examples of their applications in vehicle scenarios. The framework will help interested readers understand how pathfinding algorithms work and pick the best fit for a particular application.