Path Planning Using Mixed Integer Linear Programming

UPDATED 2022/07/28

Before you fork and use this repo, please review the license which has already been attached. Please do not commit the plagiarism and inform me for the further use.

This project focuses on the theme of path planning using MILP. I took this as my M.Sc. Dissertation project under supervision of Dr. Paul Trodden.

Abstract

A comprehensive study on the Mixed Integer Linear Programming (MILP) path planning is carried out under the mathematical programming framework. Various control architectures for different purposes are studied, implemented and compared in this paper. The concept of the MILP is introduced at the beginning, then its combination with the path planning is illustrated in detail along with its applications under separated scenarios considering various requirements, such as collision avoidance between the agents, obstacle avoidance and waypoint handling when multiple tasks existed. Moreover, iterative algorithm is also studied from two different perspectives in this paper which significantly reduce the computation time. Apart from global planning, the control architecture with the combination of the local planning scheme is also studied under the framework of Receding Horizon Control. The different resolutions of the MILP-RHC enables the vehicle not only to navigate through the environment safely and without falling into the entrapment using the high-level map information, but also to merely consider the low-level sensed environment. Such online fashioned planning relieves the computational burden significantly. In the last section, the extended capabilities of the MILP path planner is also studied both in finer trajectory generation for Quadrotor UAV and in 3D climber as well. Extensive simulations and results are shown in each section for the MILP path planning studies.

Structure

1. One-time global planning using MILP

Ref [1] has given the detailed guidance, the whole implementation in this project is illustrated in the dissertation pdf, the code is available in matlab folder for various scenarios. Current MILP solver is GLPK and CPLEX. The C/C++ version using COPT （杉树科技） solver would be proposed later.

Example: Single Vehicle with Obstacle Avoidance

Example: Collision Avoidance

Example: Multiple Waypoint Handling

Example: Wind Disturbance (with perfect knowledge of the disturbance)

2. Iterative Time Selection / Iterative Obstacle Growing Algorithm

Aiming to reduce the computation time of one-time global planning for the path, the iterative algorithm is proposed for relieving such burden. The collision check point quantity is shrinking down significantly compared to the fixed step size simulation.

Iterative Time Selection Algorithm

Iterative Obstacle Growing Algorithm

3. MPC-MILP (Receding Horizon Control - Mixed Integer Linear Planning)

MPC framework

1. The MILP is used to optimize, starting from current state s_cur and current time t to stop at the time t + H at target state s_tar. H is the prediction horizon.

2. Only implement the first step of the control sequence resulting from the optimizer.

3. Repeat until reach the goal.

   

Cost Function Design in MILP to avoid local minima

Extended Capacity

1. Forest Flight for crazyflie quadrotor

2. 3D wall climber

   

Reference

[1] A. Richards and J.P. How. Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In Proceedings of the 2002 American Control Conference (IEEE Cat. No.CH37301), volume 3, pages 1936–1941 vol.3, 2002.