Optimal Path Planning and the Fast Marching Method
Joe Clark · Digital Commons - USU (Utah State University) · 2021
The problem of determining an optimal path for an object moving through some obstacle space presents several nontrivial subproblems. The foremost being the computational complexity that is involved and how to best deal with the associated large data volume. For example, a non-symmetric object moving in three dimensions possesses six degrees of freedom. This can lead to a computational grid that may easily be on the order of 1012. Furthermore, for every point in the computational domain, several complex calculations must be performed. These include performing tests to determine if the object and obstacles intersect, and numerically solving the eikonal equation in multiple dimensions. The latter is accomplished via the Fast Marching Method (FMM), which this report outlines. At the heart of all of these problems is the way in which the configuration of the object is best represented. Thus, due to these and other complications, it is crucial that efficient algorithms are developed and the best possible representations are used to make path planning problems solvable.