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.

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

Article

Download

View 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.