SVM-inspired dynamic safe navigation using convex hull construction
Ondrej Linda, Todd Vollmer, Milos Manic · 2009
The navigation of mobile robots or unmanned autonomous vehicles (UAVs) in an environment full of obstacles has a significant impact on its safety. If the robot maneuvers too close to an obstacle, it increases the probability of an accident. Preventing this is crucial in dynamic environments, where the obstacles, such as other UAVs, are moving. This kind of safe navigation is needed in any autonomous movement application but it is of a vital importance in applications such as automated transportation of nuclear or chemical waste. This paper presents the Maximum Margin Search using a Convex Hull construction (MMS-CH), an algorithm for a fast construction of a maximum margin between sets of obstacles and its maintenance as the input data are dynamically altered. This calculation of the safest path is inspired by the Support Vector Machines (SVM). It utilizes the convex hull construction to preprocess the input data and uses the boundaries of the hulls to search for the optimal margin. The MMS-CH algorithm takes advantage of the elementary geometrical properties of the 2-dimensional Euclidean space resulting in 1) significant reduction of the problem complexity by eliminating irrelevant data; 2) computationally less expensive approach to maximum margin calculation than standard SVM-based techniques; and 3) inexpensive recomputation of the solution suitable for real time dynamic applications.