Arthur Richards : Software

All software on this page is provided purely for demonstration to researchers.


Path Planner using Mixed-Integer Linear Programming

Version 1.0, 16 July 2007

This free Matlab utility and (optional) graphical front end allow you to solve 2-D path-planning problems with obstacle avoidance. You will need:

Software provided for research use only. Users are requested to cite the following paper in any work utilising this software: A. G. Richards and J. P. How, "Aircraft Trajectory Planning with Collision Avoidance using Mixed Integer Linear Programming," in Proceedings of the American Control Conference, 2002.


Model Predictive Control of UAV with Obstacle Avoidance

From this page you can download MATLAB and AMPL code to simulate robust Model Predictive Control (MPC) of a UAV with obstacle avoidance constraints using Mixed-Integer Linear Programming (MILP) (see figure at right: click to enlarge). The example runs within Matlab under Windows using the free trial edition of AMPL/CPLEX.

Downloading and Running

  1. Download the (free) student edition of AMLP from http://www.ampl.com
  2. Unpack the AMPL package to a directory of your choice (this is a simple unzipping operation - you do not need administrator rights to install AMPL)
  3. Click here to download the zip file of the example code.
  4. Unpack the example zip file to a directory.
  5. Edit the file 'myampl.bat' so that the AMPL directory from Step 2 is added to your 'path' variable.
  6. In Matlab, go the example directory from Step 4, and run the script 'uavsmall.m'. You should see some optimization messages and then the figure shown above.

Working with the Software


AMPL Interface for Matlab

These Matlab utilities generate parameter entries in AMPL data files to represent data values generated in Matlab. For example, the following Matlab code

rts = [3 -1;
       7  1.5]';
fid=fopen('milppath.dat','w');
AMPLmatrix(fid,'ro',rts);
fclose(fid);
produces a file named "milppath.dat" containing the following AMPL code
param ro :                    1                   2	:=
	   1    3.00000000000000    7.00000000000000
	   2   -1.00000000000000    1.50000000000000	;
As well as the matrix utility shown in this example, other functions are provided to generate scalars, vectors, 3-D matrices, and integer forms of all of these elements. See http://www.ampl.com for details about AMPL.

The author uses the interface to embed AMPL-based optimisation within Matlab programs. The AMPL model and script files are written by hand. A Matlab script is used to process and generate the data values, write the AMPL parameter file, invoke AMPL using a system call, read the AMPL output file and post-process the results. The UAV demonstration below employs these utilities.

The same utilities can be used with GLPK (GNU Linear Programming Kit). The GLPK MathProg language is a subset of AMPL. See http://www.gnu.org/software/glpk for details. The GLPSOL Interface for Matlab below provides a utility for reading in the results from GLPSOL.

Download

Either click here to download a zip file of all the utilities or use the individual links below (files have been renamed from ".m" extensions to ".m.txt" to prevent confusion by browsers).

GLPSOL Interface for Matlab

GLPSOL is the stand-alone MILP solver that comes with GLPK, the GNU Linear Programming Kit. See http://www.gnu.org/software/glpk for more information and access to GLPK download sites. GLPSOL can read most AMPL models and data using the "-m" and "-d" options (see GLPK documentation or use "glpsol -h" for details.) However, the detailed output format provided by the "-o" option is, to my knowledge, unique. The "glpkread.m" Matlab utility provided here reads the GLPSOL output file and returns solution values in Matlab variables. For example, the following Matlab command

>> [flag,xm,ym] = glpkread('data.txt','x','y')
will open the file "data.txt" and, if it can understand it as a GLPSOL output file and find the decision variables "x" and "y", it will read the value of GLPK variable "x" into Matlab variable "xm" and GLPK variable "y" into Matlab variable "ym". The Matlab variable "flag" will be set to 1 if a status line indicating successful solution was found, or will be 0 otherwise. Use
>>help glpkread
for details.

Download

File has been renamed from ".m" extension to ".m.txt" to prevent confusion by browsers