View source for Sailboat Motion Planning using the Level-Set Method

{{StudentProjectTemplate
|Title=Non-Isotropic Planar Motion Planning for Sailboat Navigation
|Summary=Explore the use of Level-Set and Fast-Marching Methods to create time-optimal motions of a point in a plane subject to direction-dependent velocity.
|Author=Lin Ge, Yifei Li
|Supervisor=Roland Philippsen,
|Level=Master
|Status=Finished
}}
=== Abstract ===

This Master's project explores the possibilities of using Level-Set and Fast-Marching Methods to plan time-optimal planar motions of a point which is subject to direction-dependent maximum velocities. A promising application for such a planning approach lies in sailboat navigation planning. A large body of related work exists and will need to be understood and analyzed during this project. A prototypical implementation will also be performed, along with appropriate visualization methods and a set of benchmarks to measure the effectiveness of algorithm variants.

=== Project Description ===

The Level-Set Method (LSM) is a general scheme for computing the evolution of boundaries, or wavefronts, according to a propagation speed that can depend on properties such as location or curvature. In past research, an efficient special algorithm (the Fast Marching Method FMM) has been used to develop a motion replanner called E* for holonomic vehicles in the plane. However, not all motion planning problems can be modeled according to the conditions that allow application of the FMM. In particular, non-isotropic boundary propagation speeds, such as required to model the motion of a sailboat, appear to violate several of these conditions.

In order to provide an application-relevant usage scenario, environment and boat properties need to be mapped into direction-dependend velocities in different locations of the environment. Elements that need to be taken into account include wind, current, and waves.
Some of these may need to be considerably simplified, but it is important to identify all the potentially relevant factors.

==== Work Description ====

The work can be split into separate aspects, which can be investigated jointly or separately by the two candidates, depending on the division of work to be defined at the beginning of the project.

===== Non-Isotropic Wavefront Propagation =====

The first phase of this project will this focus on understanding the theory behind LSM and FMM with a particular focus on the aspects that are relevant for planning planar motions for vehicles whose velocity depends on direction, such as sailboats. It is important to note that the direction-dependency is defined with respect to the global frame of reference, which is expected to simplify the problem and make it tractable within the framework of this thesis project.

===== Environment Modeling for Sailboat Motion Planning =====

An appropriate environment representation and corresponding data structures need to be developed and tested. An important aspect of environment representation is whether to use regular grids, multi-resolution grids, planar triangulations, or some other scheme. The applicability of the developed wavefront propagation approach will influence the applicability of these representational aspects. Creating a solution catalogue for environment representation, and a study of the relevant related work and understanding the mathematical underpinnings, are important parts of the thesis work.

===== Feasibility Study of Dynamic Replanning =====

The LSM and FMM compute the evolution of a wavefront for a given fixed set of environmental properties. In real-world planning scenarios, however, these properties change during execution of the planned motion. It is thus desirable to allow changes in the environment model and recompute the best motion. Dynamic replanning is achieved when it becomes possible to reuse old information to speed up the computation of a new path.

In the third part of the thesis work, the candidates will investigate to what extend dynamic replanning can be employed for the non-isotropic planner developed in the other parts. This is to be achieved by studying the original E* algorithm as well as more recent work by others who provide proper proofs on the set of environment locations that need to be re-visited after changes to the model.

It is possible that dynamic replanning will not produce significant performance boosts for non-isotropic planning. This part is thus a feasibility study to determine the theoretical and practical conditions under which dynamic replanning can be beneficial.