Online Path Planning Based on MILP for Unmanned Surface Vehicles

This paper presents an algorithm for online path planning of USVs to navigate safely in dynamic, sophisticated environments of oceans. The proposed algorithm is based on Mixed Integer Linear Programming (MILP) which integrated with Velocity Obstacle (VO) approach. MILP is an optimization method under multiple constraint conditions of objective function maximization or minimization. The constraints of environment and maneuverability all can be considered and appended to the constraints conditions expressed in the form of inequality. The objective function and constraint conditions are required in linear by MILP, however, the motion of USV and its path planning are nonlinear. So the principle problem is to transform the nonlinear problem into the linear problem. On the other hand, VO makes a linear prediction, which is well appended into the constraint conditions. MILP has advantages in astringency, optimization, real-time and VO also has the advantages in real-time. The combination of MILP and VO utilized the advantages of rapidity of computations, which is well suited for embedded system of robotic applications. The algorithm is demonstrated via simulation with more safety and acclimation in sophisticated environments of oceans.