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.
Benjamin Ivorra (ivorramat.ucm.es)
Abstract: 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*.
Keywords: Pathfinding; Spatial Constraint; Computational Fluid Dynamics; Laminar Navier-Stokes Equations; Comsol Multiphysics
Category 1: Applications -- OR and Management Sciences (Transportation )
Category 2: Applications -- Science and Engineering (Other )
Category 3: Other Topics (Other )
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
Entry Submitted: 12/05/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|