Pathfinding

What is Pathfinding?

In computer science, pathfinding is understood to be algorithms with which the optimal path between two or more points is to be found. The optimal path can be defined on the basis of different parameters.

The optimal path always depends on the respective application. In addition to the shortest path, for example, the most cost-effective path can also be defined as the optimum. For example, other constraints such as avoiding certain waypoints or route sections can also influence the determination of the optimal path.

This behaviour is generally known in route planners when motorways or toll roads are to be avoided.

Algorithms

Depending on the requirements of the objective, various algorithms can be used within the framework of pathfinding.

At A* algorithm This is what is known as an informed Search algorithmwhich determines the shortest graph between two points using an estimation function/heuristic. The search examines (from the starting point) the next node that is likely to lead quickly to the destination or reduce the distance to the destination node. If an examination of a node does not lead to the goal, it is marked as such and the search is continued with another node. According to this algorithm, the shortest path to the destination node is examined.

Another algorithm for determining the shortest path is the Dijkstra algorithm. This is not based on Heuristicsbut on the basis of the procedure that, starting from the starting node, all nodes with the shortest partial routes lead to each other to the optimal solution, in that the sum of the shortest partial routes leads to the overall shortest total path. Thus, the procedure works in the form of the most promising partial solution.

In contrast to the procedures described so far, the Bellman-Ford algorithm (or Moore-Bellman-Ford algorithm) also the consideration of graphs with negative edge weights to determine the shortest paths. This means that the costs (e.g. time) between two nodes can also be negative. However, it must be ensured that cycles through negative weights are excluded, as otherwise the path is reduced by repeatedly traversing the negative edge weights. All the approaches considered so far optimise the path as seen from a particular node.

The Min-plus matrix multiplication algorithm on the other hand, searches for the optimum of all node pairs in relation to each other.

The same applies to the Floyd-Warshall algorithm. The method makes use of the dynamic programming approach. In order to find the optimum, the overall problem is divided into similar subproblems and then, by solving and storing them, the overall problem is optimised. The operation is split into two, with Floyd's part ensuring that the shortest distances between nodes are calculated, while Warshall's part is responsible for constructing the shortest paths. The consideration of negative edge weights is also possible with this algorithm.

While some methods have the optimisation between two nodes as their objective, others optimise all nodes in relation to each other. This naturally leads to an increase in computing power. Therefore In addition to the consideration of the objective in the choice of the algorithm, the demand on resources is also a decisive factor.. In addition to the computing power, the required storage space and the runtime can also be relevant variables when choosing a method.

For some of the described methods, there are prefabricated algorithms that can be implemented in own solutions. For example, the library NetworkX can be implemented in Python and used as a framework for pathfinding problems.

Examples for the application of pathfinding in practice

The application possibilities of pathfinding are manifold. They range from simple as well as complex Controls and route planning in the computer game sector up to the solution of transport logistics problems and the optimisation of routing problems in the network sector.. To support the optimisation solutions, sub-areas of the Artificial intelligence be implemented.

As mentioned at the beginning, the optimum to be achieved can be defined individually. The limitation of the cost size can be represented by minimising the factor of time, money, intermediate stops and many other parameters.

Data Navigator Newsletter