MPC with MILP for Multi-Vehicle Collision Avoidance
This model predictive algorithm proposed a innovative approach to time-optimal and fuel-optimal planning of multiple vehicles using a mixed integer programming. The basic problem formulation is to have the vehicles find the optimal dynamically feasible trajectory subject to multiple control and state constraints, without colliding with each other, while at the same time avoiding other stationary and moving obstacles.
Background
A classical approach to collision avoidance, especially in the field of vehicle motion planning, is the use of potential functions. Other developed techniques include such approaches as randomized algorithms (RRT, RRT*, or FMT) or Graph-based algorithms (A*, D*).
Here we provided an alternative approach that used the model predictive control with MILP to solve the obstacles and inter-vehicle collision avoidance.
Here we provided an alternative approach that used the model predictive control with MILP to solve the obstacles and inter-vehicle collision avoidance.
Approach
The optimization for MPC is solved by using hte CPLEX professional version with MATLAB interface.
Here, we used a simple double integrator for each vehicle to simplify the problem. Of course, this algorithm can be extended to much complicated dynamic model.
Here, we used a simple double integrator for each vehicle to simplify the problem. Of course, this algorithm can be extended to much complicated dynamic model.
Cost Function
Dynamic Constraints
State Constraints
Control Constraints
Inter-Collision Constraints
Obstacles-Collision Constraints
Simulations
Here are some simulation results for the inter-vehicle collision avoidance. The dash-red line represents the safe region. Each different squares denote different vehicles. The predicted trajectories are also shown in the simulation.
Control Horizon
Different Control Horizon (N=40, N=10) will produce different trajectory. The larger control horizon means that the vehicles are able to see further, so the predicted trajectory is longer.
Problems
The simulations point out some problems for this type of algorithm. When the vehicle start and target states are symmetric, the vehicles will stuck and cannot move anymore. The simulation in the right shows that once the symmetry is broken, the MPC is able to find a predictive trajectory that leads both vehicles to find the final position.