MILP Path Planning Implementation

This folder contains MATLAB implementations of Mixed Integer Linear Programming (MILP) based path planning algorithms for autonomous vehicles, based on the work by Schouwenaars et al. (2001).

Overview

The implementations solve the multi-vehicle path planning problem using MILP optimization, considering:
- Double integrator vehicle dynamics
- Rectangular obstacle avoidance
- Fuel consumption minimization (L1 norm)
- State and control constraints

Main Algorithms

1. Fixed Time Arrival (fixed_time_arrival.m)

This implementation uses a fixed-arrival approach where the entire trajectory is planned in a single optimization step with a predetermined arrival time.

Key Features:
- Single-shot optimization for the complete trajectory
- Fixed terminal time constraints
- Full MILP formulation with binary variables for obstacle avoidance
- Suitable for scenarios with known arrival time requirements

Results:
Fixed-arrival sweep (similar to Table 2 in Schouwenaars et al., 2001)
 Tarr(s)       Etot     Tcomp(s)
    9.20       1.64        13.88
    9.00       1.67         9.60
    8.40       1.81         6.48
    8.20       1.86         6.82
    8.00       1.91         5.36

Chosen horizon: 40 steps (T = 8.00 s)
exitflag = 1, fuel = 1.91, solve time = 5.36 s

Performance Notes:
- Can reach most locations on the map
- Becomes infeasible for very distant destinations
- Computation time increases with longer horizons

2. Receding Horizon Control (true_receding_horizon.m)

This implementation uses a true receding horizon approach where only the first control input is applied at each iteration, and the optimization is repeated with updated initial conditions.

Key Features:
- Iterative optimization with horizon rolling
- Only first control input applied per iteration
- State updates based on vehicle dynamics
- Suitable for real-time applications and long-distance planning

Results:
Table 1: Arrival times, fuel consumption and computation times for different horizon lengths.
 Thor(s)    Tarr(s)         Etot     Tcomp(s)       Tit(s)
     3.0        0.0          0.0            0         0.00
     3.5       10.6          3.9            9         0.17
     4.0       12.4          3.6           15         0.25
     4.5       14.6          3.1           29         0.40
     5.0       15.8          2.9           34         0.44

Performance Notes:
- Short horizons (Thor < 3.5s) become infeasible due to insufficient planning window
- Longer horizons provide better solutions but require more computation time
- Can handle longer distances by breaking the problem into manageable segments

Scenario Configuration

Both algorithms use the same scenario setup:
- Sampling time: 0.2s
- Start position: [0, 0, 0, 0] (position and velocity)
- Goal position: [5, 2, 0, 0] (position and velocity)
- Obstacles: 10 rectangular obstacles with 0.25m buffer
- State bounds: Position [-5, 20] × [-10, 12], Velocity [-5, 5] × [-5, 5]
- Control bounds: Acceleration [-1.8, 1.8] × [-1.8, 1.8]

Usage

To run the algorithms:

% Fixed time arrival approach
run('Matlab_MILP_Yunus/fixed_time_arrival.m')

% Receding horizon approach
run('Matlab_MILP_Yunus/true_receding_horizon.m')

Dependencies

- MATLAB Optimization Toolbox (for intlinprog)
- MATLAB Signal Processing Toolbox (for plotting functions)

Reference

Schouwenaars, T., De Moor, B., Feron, E., & Boyd, S. (2001). Mixed integer programming for multi-vehicle path planning. European Journal of Control, 7(2-3), 174-188.