Foundations and Trends® in Robotics > Vol 2 > Issue 4

Mathematical Programming Approaches for Multi-Vehicle Motion Planning: Linear, Nonlinear, and Mixed Integer Programming

By Pramod Abichandani, College of Engineering, Drexel University, USA, pva23@drexel.edu | Hande Benson, College of Business, Drexel University, USA, hvb22@drexel.edu | Moshe Kam, ECE Department, Drexel University, USA, kam@drexel.edu

 
Suggested Citation
Pramod Abichandani, Hande Benson and Moshe Kam (2013), "Mathematical Programming Approaches for Multi-Vehicle Motion Planning: Linear, Nonlinear, and Mixed Integer Programming", Foundations and Trends® in Robotics: Vol. 2: No. 4, pp 261-338. http://dx.doi.org/10.1561/2300000025

Publication Date: 14 Nov 2013
© 2013 P. Abichandani, H. Benson and M. Kam
 
Subjects
Multi-Robot Systems
 

Free Preview:

Download extract

Share

Download article
In this article:
1. The Future is Bright… and Driverless 
2. The Building Blocks 
3. General Mathematical Programming Structure of Multi-Vehicle Motion Planning problems 
4. Formulating and Solving Multi-Vehicle Motion Planning Problems 
5. Observations and Design Considerations 
A. Time-Optimal Control of a Double Integrator 
B. Spectral Graph Theory and Graph Laplacian 
C. Polygonal Approximations of a Circle 
D. Approximation of An Ellipse by Two Intersecting Circles 
E. Loiter Circles 
Acknowledgments 
Notations and Acronyms 
References 

Abstract

Real world Multi-Vehicle Motion Planning (MVMP) problems require the optimization of suitable performance measures under an array of complex and challenging constraints involving kinematics, dynamics, collision avoidance, and communication connectivity. The general MVMP problem is thus formulated as a Mathematical Programming (Optimization) problem. In this monograph, we present a Mathematical Programming (MP) framework that captures the salient features of the general MVMP problem. To demonstrate the use of MP for the formulation and solution of MVMP problems, we examine in detail four representative works and summarize several other related ones. Following this conceptual discussion, we provide a step-by-step demonstration of how to formulate, solve, and experimentally validate an MP problem that represents an MVMP. Finally, we discuss the advantages, technical challenges, and limitations of this framework. As solution algorithms and their implementations in solvers continue to develop, we anticipate that MP solution techniques will be applied to an increasing number of MVMP problems, and that the framework, formulations, and experimental approach presented here may serve as a guide for future MVMP research.

DOI:10.1561/2300000025
ISBN: 978-1-60198-722-8
80 pp. $70.00
Buy book (pb)
 
ISBN: 978-1-60198-723-5
80 pp. $115.00
Buy E-book (.pdf)
Table of contents:
1. The Future is Bright… and Driverless
2. The Building Blocks
3. General Mathematical Programming Structure of Multi-Vehicle Motion Planning problems
4. Formulating and Solving Multi-Vehicle Motion Planning Problems
5. Observations and Design Considerations
A. Time-Optimal Control of a Double Integrator
B. Spectral Graph Theory and Graph Laplacian
C. Polygonal Approximations of a Circle
D. Approximation of An Ellipse by Two Intersecting Circles
E. Loiter Circles
Acknowledgments
Notations and Acronyms
References

Mathematical Programming Approaches for Multi-Vehicle Motion Planning

Real world Multi-Vehicle Motion Planning (MVMP) problems require the optimization of suitable performance measures under an array of complex and challenging constraints involving kinematics, dynamics, collision avoidance, and communication connectivity. The general MVMP problem is thus formulated as a Mathematical Programming (Optimization) problem. This book presents a Mathematical Programming (MP) framework that captures the salient features of the general MVMP problem. To demonstrate the use of MP for the formulation and solution of MVMP problems, it examines in detail four representative works and summarizes several other related ones. Following this conceptual discussion, it provides a step-by-step demonstration of how to formulate, solve, and experimentally validate an MP problem that represents a MVMP. Finally, it discusses the advantages, technical challenges, and limitations of this framework.

As solution algorithms and their implementations in solvers continue to develop, it is anticipated that MP solution techniques will be applied to an increasing number of MVMP problems. The framework, formulations, and experimental approach presented here may serve as a guide for future MVMP research.

 
ROB-025