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

作者：Ivorra Benjamin^*

来源：Journal of Scientific Computing, 2018, 74(2): 1163-1187.

DOI：10.1007/s10915-017-0489-5

• Pathfinding
• Computational fluid dynamics
• Comsol Multiphysics
• Spatial constraints
• Artificial intelligence

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. Then, we propose and validate a numerical implementation of this methodology by using Comsol Multiphysics (i.e., a finite element methods software) and by considering various experiments. We compare the obtained results with those returned by a classical pathfinding algorithm. Finally, we perform a sensitivity analysis of the proposed algorithms with respect to some key parameters.

• 出版日期2018-2