Decision Making for Autonomous Aerospace Systems

2021 Spring SNU AE “Decision making for Autonomous Aerospace Systems”

Course Description

  • Path planning
    • Potential field
    • Graph search
    • Sampling-based algorithms
  • Control
    • Controllability of non-holonomic systems
    • Sliding mode control
    • Adaptive control
    • Back stepping control
    • Model predictive control
  • Multi-agent systems
    • Graph network
    • Basic game theory

Term project subject : The review of FMT* and its comparison with other sampling-based algorithms.

Fast Marching Tree* (FMT*) is a sampling-based method for optimal motion planning proposed by L. Janson. In the “Decision making for Autonomous Aerospace Systems” class, I presented a comparison of FMT* and its variation DFMT* with previous sampling-based path planning algorithms, Rapidly exploring Random Tree* (RRT*) and Probabilistic Roadmap * (PRM*) link.

The characteristic of FMT* is that it chooses sample points like PRM and grows trees like RRT*. It expands outward, which means it never backtrack over previous node.
Due to this characteristic, FMT* outperforms previous sampling-based algorithms in terms of computational time. However, this characteristic could lead to suboptimal connections.

We can directly find their difference with visualized simulation. Simulation is based on MATLAB environment.

FMT star
FMT* algorithm
PRM star
PRM* algorithm
RRT star
RRT* algorithm

[1] Janson, Lucas, et al. “Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions.” The International journal of robotics research 34.7 (2015): 883-921.
[2] Schmerling, Edward, Lucas Janson, and Marco Pavone. “Optimal sampling-based motion planning under differential constraints: the driftless case.” 2015 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2015.
[3] Karaman, Sertac, and Emilio Frazzoli. “Sampling-based algorithms for optimal motion planning.” The international journal of robotics research 30.7 (2011): 846-894.