Pathfinding and AI
![250px-ArtificialFictionBrain[1]](ai_fichiers/image009.gif)
Pathfinding Algorithms
1 – BPA (Basic Pathfinding Algorithm in Comsol):
Example file
illustrating how reformulating a pathfinding problem as the motion of a viscous
fluid via the use of the laminar Navier-Stokes
equations and solving this problem with Comsol Multiphysics and Matlab.
1 – DPA (Diffusion Pathfinding Algorithm):
DPA is a 2D
pathfinding algorithm in Matlab based on a diffusion
technique starting from the target point up to the initial point of the path.
Research articles
Title:
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.
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*.
Published article:
Authors:
Benjamin Ivorra
Title: 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.
Journal:
Journal
of Scientific Computing
Online:
https://link.springer.com/article/10.1007/s10915-017-0489-5
Volume: 74(2) Pages: 1163-1187 Year: 2018
Publisher:
Springer
Impact
Factor-2017: 1.814 Category: Math., applied Ranking-2017: 39/252 (Q1)