| dc.description.abstract | Path planning is an important part of many systems, especially autonomous systems.
Finding the optimal paths for various vehicles, given different optimization criteria such as the shortest, fastest, straightest or energy-optimized paths, is of interest for many applications. Testing different methods gives an overview of the benefits and drawbacks so that one can choose the best solution for a specific vehicle and a specific purpose.
One aim of this project is to find the shortest paths from one pose (position and orientation) to another using optimal control theory and numerical optimization methods. In addition, guidance techniques are used to make sure that vehicles under the influence of unknown disturbances still converge towards the target. The optimal control method used is dynamic programming with the Hamilton-Jacobi-Bellman (HJB) equation. It is further investigated how to solve this using the numerical approximation methods, semi-Lagrangian approximation scheme (SL) and the pseudospectral (PS) discretization method. When implementing the Legendre pseudospectral method in this thesis, it was decided that the MATLAB application package DIDO would be used. DIDO, however, uses the Legendre pseudospectral method to discretize the optimization problem itself, not the HJB equation.
Together, these methods are used to solve the shortest path problem for three different models. The two first models utilized are both nonholonomic mobile robots, called the Dubins car (DU) and the Reeds-Shepp car (RS). The shortest path problem has previously been solved for these two models and therefore the optimal paths for these models are already known. The results from SL and PS can therefore easily be compared to the known optimal solutions. After making sure that both numerical approximation methods work for these car models, the methods and techniques are used to solve the shortest path problem for a simplified boat model, both with and without an unknown ocean current.
In the first part of this thesis, relevant theory is presented. Subsequently, the numerical approximation schemes are implemented on all models and the results are discussed and compared to give an overview of accuracy, advantages and disadvantages. Since the optimization problem is solved with the use of numerical optimization methods, the paths are optimized, not optimal. Hence, the question to be answered is how good the results are and how close they are to the optimal paths. The difficulties and advantages when using the SL scheme and PS method are investigated and discussed. The solution from SL and PS is also compared to the optimized solution given by the numerical optimization method finite difference (FD) and the optimal solution given by Pontryagin's Minimum Principle, which were both researched in a pre-project for this master's thesis. In addition, it is shown that observers and a guidance system can be used to estimate unknown disturbances, for example the ocean current, and then further be used to either minimize position error or create new optimized paths in environments with and without static obstacles.
Two main contributions pertaining to optimal control theory and numerical optimization methods are included in this thesis. The first contribution is extending the use of the semi-Lagrangian approximation scheme by using the SL scheme to identify optimized paths for boats. The second contribution is combining the numerical optimization method PS with adaptive guidance in order to conduct unknown ocean current compensation. Two different approaches were tested in order to implement this: initial path planning with continuous current estimation and repeated path planning. Both approaches were tested in environments with and without static obstacles to determine how collision avoidance is handled. Both of them enable the boat to counteract the unknown current and follow the desired optimized path given by PS. By updating the path, repeated path planning gave a shorter and more feasible path than the initial path planning approach. In this thesis, however, the implementation of repeated path planning suffers from some numerical issues that must be further investigated. | |
