Skip to content

N-Dimensional Fast Methods: Fast Marching, Fast Sweeping, Group Marching, Fast Iterative, etc.

License

Notifications You must be signed in to change notification settings

jvgomez/fast_methods

Repository files navigation

N-Dimensional Fast Methods Library v0.7

Authors:

  • Javier V. Gomez javvgomez at gmail.com
  • Jose Pardeiro jose.pardeiro at gmail.com
  • Pablo Gely

ALGORITHMS

All the theory and algorithms implemented in this library can be found in my PhD thesis. In fact, all the benchmarking data in chapter 4 has been produced with this library and it is stored on the experiments branch.

Fast Marching Methods:

  • FMM: Fast Marching Method with Binary Queue and Fibonacci Queue (binary by default).
  • FMM*: FMM with CostToGo heuristics.
  • SFMM: Simplified Fast Marhching Method.
  • SFMM*: SFMM with CostToGo heuristics..

O(n) Fast Marching Methods:

  • GMM: Group Marching Method.
  • UFMM: Untidy Fast Marching Method.
  • FIM: Fast Iterative Method.

Fast Sweeping Methods:

  • FSM: Fast Sweeping Method.
  • LSM: Lock Sweeping Method.
  • DDQM: Dynamic Double Queue Method.

Fast Marching Square motion planning algorithms:

  • FM2: Fast Marching Square Method.
  • FM2*: Fast Marching Square Star FM2 with CostToGo heuristics.

ROS

ROS nodes using this code (tested in the TurtleBot) are provided in a separate repo

DISCLAIMER and IMPORTANT NOTES

  • The code is not deeply tested. I've just tested it works for the cases I need. If you find any problem, have any question (or whatever), please write to: javvgomez at gmail.com

  • The compilation time is highly increased due to CImg library. Please, omit it when possible as it is used only for visualization purposes.

  • License GNU/GPL V3

  • This is a source code intended for my research. Although I want it to be useful for other people it is not intended to act as a library (there are many many points to improve). However, if you show interest or have feature request do not hesitate to contact me and I will try my best to improve the code for whoever needs it. I am also open to contributions and to create a formal library if necessary.

Documentation

Building the code

Check the building section of the documentation.

Design and folder structure

Check the design section of the documentation.

KNOWN ISSUES

  • Gradient Descent for FM2* could fail if very narrow passages are in the way of the path.
  • It seems that UFMM can fail in maps with random (or similar) velocity changes.