Pathfinding problems consist in determining the optimal shortest path, or at least one path, between two points in the space. In this paper, we propose a particular approach, based on methods used in Computational Fluid Dynamics, that intends to solve such problems. In particular, we reformulate pathfinding problems as the motion of a viscous fluid via the use of the laminar Navier-Stokes equations completed with suitable boundary conditions corresponding to some characteristics of the considered problem: position of the initial and final points, a-priori information of the terrain, One-way routes and dynamic spatial configuration. The advantages of this technique, regarding existing ones (e.g., A* algorithm) is that it does not require a pre-processing method (e.g., graph conversion) of the environment and can manage complex geometries. Then, we propose a particular numerical implementation of this methodology by using Comsol Multiphysics (i.e., a modeling software based on Finite Element Methods). Finally, we validate our approach by considering several 2D and 3D benchmark cases. Results are compared with the ones returned by a simple A* algorithm. From those numerical tests, we deduce that our algorithms generate suitable routes (but not the shortest ones) for the studied problems in a computational time similar to the considered A*.
Citation
Ivorra, B. Application of the Laminar Navier–Stokes Equations for Solving 2D and 3D Pathfinding Problems with Static and Dynamic Spatial Constraints: Implementation and Validation in Comsol Multiphysics. J Sci Comput (2017). doi:10.1007/s10915-017-0489-5