Optimization Online


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 (ivorra***at***mat.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

Download: [PDF]

Entry Submitted: 12/05/2015
Entry Accepted: 12/06/2015
Entry Last Modified: 06/30/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society