Given a goal, the algorithm is able to generate a trajectory, which will be then followed by the local planner. Despite of the fact that this level is aimed to perform a background planning in which we do not need to react to the dynamic obstacles, we have implemented our method in such a way in which it would be able to modify its trajectory if a dynamic obstacle intercepts it.
The method we designed for this task uses a Multiclass Support Vector Machine for the generation of smooth, safe and short paths. Several approaches have been made in this sense, but as far as we are concerned this is the first time that Multiclass SVM are used. The idea is that for each class (corresponding to an obstacle in the map), we train a SVM so we can use the decision boundary as a path that can be followed to avoid the obstacle. By repeating the same process for all objects, we will get all the paths capable of avoiding an obstacle, which will be crossed with other paths in certain points. Using these points as nodes, it is possible to create a graph which can be used to find a fast way between any two points in the map.
The main advantages of using SVM are:
- With SVM, it is possible to generate non-linear hyperplanes which limit areas in the ground, allowing the generation of smooth paths.
- Margin maximization allows performing a safe search strategy, ensuring that the path will always be at a certain distance the obstacles.
- By using SVMs, the uncertainty due to the errors introduced by sensors is reduced, since they try to maximize the distance to the points that define different obstacles. If it is not possible to define a line that clearly divides two different regions, a function that tries to minimize this effect is generated.
- In addition to these features, the use of MSVM adds another advantage. By using them, all possible routes in a map can be generated ensuring that they will be safe (the distance to the obstacles will be optimal) and smooth.
The most updated version of this code can be accessed at:
https://github.com/nestormh/svm_path_planner
Creative Commons Attribution-ShareAlike 4.0