FDA*: a focused single-query grid based path planning algorithm

Abstract

Square grid representations of the state‐space are a commonly used tool in path planning. With applications in a variety of disciplines, including robotics, computational biology, game development, and beyond. However, in large scale and/or high dimensional environments the creation and manipulation of such structures become too expensive, especially in applications when an accurate representation is needed.In this paper, we present a method for reducing the cost of single‐query grid‐based path planning, by focusing the search to a smaller subset, that containsthe optimal solution.

This subset is represented by a hyper‐rectangle, the location, and dimensions of which are calculated departing from an initial feasible path found by a fast search using the RRT* algorithm. We also present an implementation of this focused discretization method called FDA*, a resolution optimal algorithm, where the A* algorithm is employed in searching the resulting graph for an optimal solution. We also demonstrate through simulation results, that the FDA* algorithm uses less memory and has a shorter run‐time compared to classic A* and thus other graph based planning algorithms, and in the same time, the resulting path cost is less than that of regular RRT based algorithms.

Gallery

Citation

@article{Boumediene2021FDA,
  title = {FDA*: a focused single-query grid based path planning algorithm},
  author = {Mouad Boumediene and Lamine Mehennaoui and Abderezzak Lachouri},
  journal = {Journal of Automation, Mobile Robotics and Intelligent Systems},
  pages = {37-43},
  year = {2021}
}